4第四章 对偶单纯形法和对偶问题课件

第四章对偶问题及对偶单纯形法§4.1对偶问题的提出4第四章对偶单纯形法和对偶问题一、问题的提出ABC拥有量工时1113材料1479单件利润233例1现有工厂生产A、B、C三种产品，单位产品所需要消耗的工时、材料及拥有量如下表，已知每单位A、B、C产品的利润分别为2、3、3，如何分配资源可以使得利润最大4第四章对偶单纯形法和对偶问题建立模型如下4第四章对偶单纯形法和对偶问题ABC拥有量工时1113材料1479单件利润233

假设有客户提出要求，购买工厂所拥有的工时和材料，为客户加工别的产品，由客户支付工时费和材料费。那么工厂给每单位工时和材料制订的最低价格应是多少，才值得出卖工时和材料?

同样是这个问题，现在我们来换一个角度思考4第四章对偶单纯形法和对偶问题ABC拥有量工时1113材料1479单件利润233在考虑这个问题时我们应做到：1、价格应该尽量低，这样，才能有竞争力;2、出卖资源获利应不少于生产产品的获利;3、价格应该是非负的目标约束条件非负约束4第四章对偶单纯形法和对偶问题ABC拥有量工时1113材料1479单件利润233

现在我们用数学语言描述，设y1和y2分别表示单位工时和材料的出售价格总价格最小minW=3y1+9y2保证获利大于A产品利润y1+y2≥2保证获利大于B产品利润y1+4y2≥3保证获利大于C产品利润y1+7y2≥3售价非负y1≥0y2≥04第四章对偶单纯形法和对偶问题ABC拥有量工时1113材料1479单件利润2334第四章对偶单纯形法和对偶问题二、对偶问题概念

任何一个线性规划问题都有一个与之相对应的线性规划问题，如果前者称为原始问题，后者就称为“对偶”问题。对偶问题是对原问题从另一角度进行的描述.其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。

4第四章对偶单纯形法和对偶问题第四章对偶问题及对偶单纯形法§4.2建立对偶问题的规则4第四章对偶单纯形法和对偶问题一、建立对偶问题的规则可以用如下形式表示原问题与对偶问题之间的关系原问题maxz=CXAX≤bX≥0对偶问题minw=bTY ATY≥CT Y≥0其中Y=（y1,y2,……ym）4第四章对偶单纯形法和对偶问题二、对偶问题的特点（1）目标函数在一个问题中是求最大值在另一问题中则为求最小值（2）一个问题中目标函数的系数是另一个问题中约束条件的右端项（3）一个问题中的约束条件个数等于另一个问题中的变量数（4）原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵4第四章对偶单纯形法和对偶问题对偶问题对应表原问题（对偶问题）对偶问题（原问题）目标函数max目标函数min变量数：n个第j个变量≥0第j个变量≤0第j个变量是自由变量

目标函数中变量的系数约束条件：n个第j个约束类型为“≥”第j个约束类型为“≤”第j个约束类型为“＝”约束条件右端项约束条件：m个第i个约束类型为“≤”第i个约束类型为“≥”第i个约束类型为“＝”约束条件右端项变量数：m个第i个变量≥0第i个变量≤0第i个变量是自由变量

目标函数中变量的系数4第四章对偶单纯形法和对偶问题三、例题原问题：对偶问题：maxZ=70X1+120X2minω=360y1+200y2+300y3

9X1+4X2≤3609y1+4y2+3y3≥704X1+5X2≤2004y1+5y2+10y3≥1203X1+10X2≤300y1≥0,

y2≥0,

y3≥0X1≥0X2≥0习题：课本P51例24第四章对偶单纯形法和对偶问题练习写出如下LP问题的对偶问题4第四章对偶单纯形法和对偶问题第四章对偶问题及对偶单纯形法§4.3对偶问题的基本性质(选学)4第四章对偶单纯形法和对偶问题一、对称性定理1、对偶问题的对偶就是原始问题定理2（可行解的目标函数值之间的关系）设X、Y分别是原始问题和对偶问题的可行解，则

CX≤YTb二、弱对偶性4第四章对偶单纯形法和对偶问题1.如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。2.若原问题可行,而对偶问题不可行,则原问题的目标函数值无界3.若对偶问题可行,而原问题不可行,则对偶问题的目标函数值无界推论:4第四章对偶单纯形法和对偶问题例如试用对偶理论证明原问题无界。

解：=（0.0.0）是原问题的一个可行解，而对偶的第一个约束条件不能成立（因为y1,

y2≥0)。因此，原问题无界。习题P603.4第四章对偶单纯形法和对偶问题定理3三、可行解是最优解的性质4第四章对偶单纯形法和对偶问题四、对偶定理

定理4如果原问题有最优解，则其对偶问题也一定有最优解，且两者的目标函数值相等

定理5若X为原问题的满足最优检验的基本解。则Y=CBb-1为对偶问题的可行解

(原问题在得到基本可行解的同时，其检验数的相反数就构成对偶问题的一个基本解，且各自目标函数值恒相等。)补充：对比原问题和对偶问题的最优单纯形表P54表4－2，4－34第四章对偶单纯形法和对偶问题Cj→-6-3-2000θjCBXBb

X1

X2

X3

X4

X5

X6-20-3X3X6X216104001-240-100-1011101-40σj=cj-zj-300-1-40Cj→20610000θjCBYBb

Y1

Y2

Y3

Y4

Y5

Y60620Y4Y2Y134100111-1001004-41010-12σj=cj-zj00-100-4-16原问题对偶问题4第四章对偶单纯形法和对偶问题第四章对偶问题及对偶单纯形法§4.4对偶单纯形法4第四章对偶单纯形法和对偶问题

当一个线性规划问题是求目标函数值最小，约束方程是≥时，求解时用大M法或两阶段法比较麻烦，此时较有效的算法是将要介绍的对偶单纯形法对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。一、原理4第四章对偶单纯形法和对偶问题第一步找出一个初始正则解B0，要求对应的单纯形表中的全部检验数≤0，但右边项中允许有负数第二步若右边项中各数均非负，则B0已是最优基，即已求得最优解，计算终止；否则转为下一步第三步取右边项中取值最小（即负的最多）的数所对应的变量为换出变量。二、对偶单纯形法的计算步骤4第四章对偶单纯形法和对偶问题第四步按公式

其中σj＝cj–zj计算最小比值θ,则该列所对应的变量即为换入变量第五步以换出变量的行和换入变量列交点处的元素为主元进行单纯形迭代，再转入第二步。<4第四章对偶单纯形法和对偶问题

用对偶单纯形法求解线性规划问题：

minw=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1yj≥0，对一切j解：先将问题改写为

maxw’=-15y1-24y2-5y3maxw’=-15y1-24y2-5y36y2+y3-y4=2-6y2-y3+y4=-25y1+2y2+y3-y5=1-5y1-2y2-y3+y5=-1yj≥0，对一切jyj≥0，对一切j三、例题4第四章对偶单纯形法和对偶问题第一步建立一个初始单纯形表，使表中检验行的值全部≤0

即对其对偶问题而言是一基本可行解。Cj→-15-24-500CBYBbY1Y2Y3Y4Y500Y4Y5-2-10-6-110-5-2-101σj=cj-zj-15-24-5004第四章对偶单纯形法和对偶问题第二步检验当前可行解是否可行，若可行，已得最优解，否则转入下一步Cj→-15-24-500CBYBbY1Y2Y3Y4Y500Y4Y5-2-10-6-110-5-2-101σj=cj-zj-15-24-500检验数均为非正数，但右边项仍有负数，并非最优解，继续迭代4第四章对偶单纯形法和对偶问题第三步选择b列中取值最小（即负的最多）的数所对应的变量为出基变量。Cj→-15-24-500CBYBbY1Y2Y3Y4Y500Y4Y5-2-10-6-110-5-2-101σj=cj-zj-15-24-5004第四章对偶单纯形法和对偶问题第四步按公式

计算最小比值θ,则该列所对应的变量即为入基变量。（其中σj＝cj–zj

）<Cj→-15-24-500CBYBbY1Y2

Y3Y4Y500Y4Y5-2-10[-6]-110-5-2-101σj=cj-zj-15-24-500θ/45//4第四章对偶单纯形法和对偶问题第五步用换入变量替换对偶问题中的换出变量得到一个新的单纯形表。表中数字计算同用单纯形法时完全一样。新表中对偶问题仍保持基本可行解

Cj→-15-24-500CBYBbY1Y2Y3

Y4Y5-240Y2Y51/3-1/3011/6-1/60-50[-2/3]-1/31σj=cj-zj-150-1-40θ3/3/212/4第四章对偶单纯形法和对偶问题第六步：重复第二～四步，一直到找出最优解为止。Cj→-15-24-500CBYBbY1Y2Y3Y4Y5-24-5Y2Y31/41/2-5/410-1/41/415/2011/2-3/2σj=cj-zj-15/200-7/2-3/2θ

此时右边项全为非负值，达到最优，Y1=0，Y2=1/4,Y3=1/2,W最优为17/2

4第四章对偶单纯形法和对偶问题四、练习课本60页24第四章对偶单纯形法和对偶问题第四章对偶问题及对偶单纯形法§4.5对偶问题的经济意义——影子价格4第四章对偶单纯形法和对偶问题定义：约束条件方程右端的bi增加一单位时，最优目标函数z的变化量称为资源i的影子价格.影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0q’i4第四章对偶单纯形法和对偶问题第四章对偶问题及对偶单纯形法§4.6对偶单纯形法的一个应用（增加约束条件）4第四章对偶单纯形法和对偶问题

在求出线性规划问题的最优解后，又增加一个约束条件，此时可以利用对偶单纯形法求解，不必对原问题从头做起。其步骤如下：1、将最优解代入新的约束条件，若满足，则最优解不变2、若不满足，则当前最优解要发生变化；将新增约束条件加入松弛变量或剩余变量后加入到原来的最优单纯形表，令原来的基变量和新增加的变量组成新的基，进行初等变换将基变量对应的系数矩阵变为单位矩阵。3、利用对偶单纯形法继续迭代一、原理及步骤4第四章对偶单纯形法和对偶问题二、例题2x1+3x2+x3+2x4+x5=8005x1+4x2+3x3+4x4+x6=12003x1+4x2+5x3+3x4+x7=1000xj≥0转化为标准型：4第四章对偶单纯形法和对偶问题Cj→1534000CBXBbX1X2X3X4X5X6X7045X5X4X21002001001/40-13/4011/4-120-2101-1-3/4111/400-3/41σj=cj-zj-13/40-11/400-1/4-1以达到最优，此时X1=0，X2=100，X3=0，X4=200，X5=100，X6=0，X7=0,Z=1300若此时增加约束条件X1+2X2+3X3+3X4≤650，代入当前的最优解检验不符合条件，应继续迭代加入新条件，将原问题变为：利用单纯形法迭代，求得：4第四章对偶单纯形法和对偶问题转化为标准型：2x1+3x2+x3+2x4+x5=8005x1+4x2+3x3+4x4+x6=12003x1+4x2+5x3+3x4+x7=1000x1+2x2+3x3+3x4+x8=650xj≥0，对一切j4第四章对偶单纯形法和对偶问题Cj→15340000CBXBbX1X2X3X4X5X6X7X80450X5X4X2X81002001006501/40-13/4011/4-1020-2101-10-3/4111/400-3/41012330001Cj→15340000CBXBbX1X2X3X4X5X6X7X80450X5X4X2X81002001004501/40-13/4011/4-1020-2101-10-3/4111/400-3/4105/20-5/2303/2-21Cj→15340000CBXBbX1X2X3X4X5X6X7X80450X5X4X2X8100200100-1501/40-13/4011/4-1020-2101-10-3/4111/400-3/410-7/207/200-3/2114第四章对偶单纯形法和对偶问题Cj→15340000CBXBbX1X2X3X4X5

X6X7X80450X5X4X2X8100200100-1501/40-13/4011/4-1020-2101-10-3/4111/4