线性规划的对偶理论课件

线性规划的对偶理论对偶问题的提出

原问题与对偶问题的关系

对偶单纯形法

一、对偶问题的提出

对于上节中所介绍的资源利用问题考虑资源拥有者为了实现一定的收入目标，将其所拥有的资源出售，则需给每一种资源定价。

表示出售单位数量的第i种资源的价格，若将所有资源出售，则得到的总收入为

在做出决策时，考虑出售资源的收入不应该低于生产所获得的收入，则

资源拥有者出售每一种资源的最低估价，可通过求解线性规划问题而得到

这表明，从不同角度考虑同一问题可得到相互联系的线性规划模型，这就是线性规划的对偶问题。

一般地，称线性规划问题（I)

和(Ⅱ)互为对偶问题的标准形式。（I)(Ⅱ)

①对偶问题的变换关系为对称关系时，根据原问题的系数矩阵就能容易地写出对偶问题。如表5.2.1。表5.2.1yj

x1

x2

…

xn，

原关系

minW对偶关系

maxZ

②当原问题的约束条件中含有等式约束方程时，即变换关系为非对称形式，可按以下步骤求对偶问题：

首先将每一个等式约束方程都用两个不等式约束方程代替，所有约束方程都变为同号不等式约束。

按对称形式变换关系（表5.2.1）写出它的对偶问题。

例：对于线性规划问题

可以按下述步骤求出其对偶问题：第1步：将等式约束分解为不等式约束，变为

第2步，设和分别代表对应的对偶变量，按对称形式变换关系写出它的对偶问题

上述线性规划问题的各式，经过整理后得到

令，由于，可见不受正、负限制，将代入，可得到原线性规划问题的对偶问题。

二、原问题与对偶问题的关系

线性规划原问题与对偶问题之间的形式变换关系可以由表5.2.2予以概述。原问题（或对偶问题）

对偶问题（或原问题）

目标函数

目标函数

变

量

个数n≥0≤0无约束

约束方程

个数n≥≤=约束方程

个数m≤≥=变量

个数m≥0≤0无约束

约束方程右端项

目标函数中变量的系数

目标函数中变量的系数

约束方程右端项

表5.2.2

利用表5.2.2所描述的变换关系，可写出任何一个线性规划问题的对偶问题。譬如，对于线性规划问题其对偶问题为

对偶问题的基本性质

①对称性：即对偶问题的对偶是原问题。

②弱对偶性：即若是原问题的可行解，是对偶问题的可行解，则存在关系：。

③无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。

④对偶定理：若原问题有最优解，那么对偶问题也有最优解，而且它们的最优目标值相等。

⑤松紧定理：若和分别为原问题与对偶问题的可行解，则它们为最优解的充要条件为

⑥设原问题是

其对偶问题是

⑦互补松弛性：若和分别是原问题和对偶问题的可行解。那么，和，当且仅当和为最优解。

则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如表5.2.3。

0表5.2.3

三、对偶单纯形法

基本思想若保持对偶问题的解是基可行解，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也就得到了最优解。这种方法的优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。

基本原理对于原问题

设B是一个基，不失一般性,令，它对应的基变量为。当非基变量都为零时，可以得到。若在中至少有一个负分量，设，并且在单纯形表的检验数行中的检验数都非正，即对偶问题保持可行解，它的各分量是:①对应基变量的检验数是

②对应非基变量的检验数是

每次迭代是将基变量中的负分量取出，去替换非基变量中的，经过基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近，当原问题得到可行解时，便得到了最优解。计算步骤

①列出初始单纯形表，检查b列中的各分量，若都为非负，且检验数都为非正，则已得到最优解。若b列中至少有一个负分量，检验数保持非正，进行以下计算。

②确定换出变量。按照法则

确定对应的基变量为换出变量。

③确定换入变量。

若xj所在行有负系数，计算所对应的非基变量xk为换入变量。

④以为主元素，按原单纯形法迭代运算，得新单纯形表。

⑤重复①～④的步骤，直至求得最优解。

例1：试用对偶单纯形法求解如下线性规划问题

首先将该问题化为-2-3-400CBXBbX1X2X3X4X500X4X5-3-4-1[-2]-21-131001-2-3-400初始单纯形表，如表5.2.4所示表5.2.4b列各行为负，进行迭代计算，确定换出变量故X3为换出变量。

故X1为换入变量。换入、换出变量所在列、行的交叉处“2”为主元项。进行迭代运算，得表5.2.5。

-2-3-400CBXBbX1X2X3X4X50-2X4X1-1201[-5/2]-1/21/23/210-1/2-1/20-4-10-1表5.2.5

从表5.2.5可看出，b列中仍有负分量，继续迭代计算，重复上述步骤，得表5.2.6。

表5.2.6

-2-3-400CBXBbX1X2X3X4X5-3-2X2X1-2/511/50110-1/5