运筹学单纯形法的对偶问题实用教案

1、会计学1运筹学单纯形法的对偶运筹学单纯形法的对偶(du u)问题问题第一页，共20页。2 现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、c，那么该厂的厂长应该如何来确定合理的租金呢？ 设 分别为设备A、B、c的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润。作为出租者来说，生产单位 产品所需各设备的台时各总租金不应低于原利润50元，即 ，否则就不出租还是用于生产 产品以获利(hu l)50元；同样生产一单位 产品 所需各设备的台时的总租金也不应当低于原利润100元， 即 ，否则这些设备台时就不出租，还是用于生产 产品以获利(hu l)100元。但

2、对于租用者来说，他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，即min ，这样我们得到了该问题的数学模型： 目标函数： 约束条件： 这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。3, 21,yyy321250400300minyyyf50221yy100321yyy321250400300yyy0,10050232132121yyyyyyyy1 线性规划(xin xn u hu)的对偶问题第1页/共20页第二页，共20页。3 如果我们把求目

3、标函数最大值的线性规划问题看成原问题，则把求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。 1 求目标函数最大值的线性规划问题中有n 个变量 m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。 2 原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数(chngsh)项，并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数(chngsh)项。 3 原问题的约束条件的右边常数(chngsh)项为对偶问题的目标函数中的变量的系数。并

4、且原问题的第i个约束条件的右边常数(chngsh)项就等于对偶问题的目标函数中的第i个变量的系数。 4 对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置 。 设 A=则 mnmmnaaaaaa.21112111 线性规划的对偶(du u)问题mnnnmTaaaaaaA2112111TA第2页/共20页第三页，共20页。4如果我们用矩阵形式来表示，则有原问题： 其中A是 矩阵mn，该问题有m个约束条件n个变量(binling)， , , 对偶问题： 其中 是A的转置， 是b的转置, 是c的转置, y= 现在我们用单纯形法求对偶问题的解。0,maxxbAxcxz).,.,(21ncccc Tm

5、bbbb),.,(21TATbTcTmyyy),.,(210minycyAybfTTT1 线性规划(xin xn u hu)的对偶问题Tnxxxx,21第3页/共20页第四页，共20页。5 加上剩余变量 和人工(rngng)变量 ，把此问题化成标准型如下：把上述数据填入单纯形表计算。21,ss1a0,10050212132123211121assyyysyyyasyy1 线性规划(xin xn u hu)的对偶问题1231max300400250fyyyMa第4页/共20页第五页，共20页。6迭代变量基变量 b-300-400-25000-M 1-M1 0 -1 0 15050/2-250 1

6、 1 1 0 -1 0 100100/1-M-250-2M-250-250M250-M-50M-25000M-502M-1500-M-25002-4001/210-1/201/225-2501/2011/2-1-1/275-325-400-25075250-75-287502500-75-250-M+753-300120-10150-2500-111-1-150-300-350-25050250-50-275000-500-50-250-M+50bc1y2y3y2s1s1a1a3yjzjjzc 2y3y2/1752/125jzjjzc 1y3yjzjjzc 1 线性规划的对偶(du u)问题第

7、5页/共20页第六页，共20页。71y0, 0, 0,50, 012132assyy1 线性规划(xin xn u hu)的对偶问题第6页/共20页第七页，共20页。8 下面来阐述如何写出一个线性规划(xin xn u hu)问题的对偶问题。为了便于阐述，我们不妨以下面的线性规划(xin xn u hu)为例，写出它的对偶问题。 s.t. 321643maxxxxz0,20035,10046,440632321321321321xxxxxxxxxxxx1 线性规划的对偶(du u)问题第7页/共20页第八页，共20页。9 这是一个求最大值的线性规划问题，为了写出它的对偶问题，我们不妨把它的约束

8、条件都变换成取小于等于号的不等式。显然第一个约束条件已符合要求，不要做任何变动，而第二个约束条件，我们只要两边都乘以 -1，使不等号方向改变即可，得 这样第二个约束条件也就符合要求。对于(duy)第三个约束条件，我们可以用小于等于和大于等于两个约束条件来替代它。即有 显然，这两个约束条件与原来第三个约束条件是等价的，我们再把其中的两边都乘以-1，得 10046321xxx2003520035321321xxxxxx20035321xxx20035321xxx1 线性规划(xin xn u hu)的对偶问题第8页/共20页第九页，共20页。10 通过上面的一些变换，我们得到了一个和原线性规划等价

9、(dngji)的线性规划问题： s.t. 321643maxxxxz0,2003520035,10046,440632321321321321321xxxxxxxxxxxxxxx1 线性规划的对偶(du u)问题第9页/共20页第十页，共20页。11 这个(zh ge)求最大值的线性规划问题的约束条件都取小于等于号，我们马上可以写出其对偶问题： s.t.3 321200200100440minyyyyf, 0, 66, 43343, 355623 3213 3213 3213 321yyyyyyyyyyyyyyyy1 线性规划的对偶(du u)问题第10页/共20页第十一页，共20页。12 这

10、里 和 一样都是不同(b tn)的决策变量，为了表示这两个决策变量都来源于原问题的第三个约束条件，记为 。 因为在该对偶问题中 和 的系数只相差一个符号，我们可以把上面的对偶问题化为： s.t.3 3, yy21, yy3y3 y)(200100440min3 321yyyyf, 0, 6)(6, 4)( 343, 3)(5623 3213 3213 3213 321yyyyyyyyyyyyyyyy1 线性规划(xin xn u hu)的对偶问题3 3, yy第11页/共20页第十二页，共20页。13 进一步，我们可以令 ，这时当 时， ，当 时， 。这也就是说，尽管(jn gun) 但 的取

11、值可以为正，可以为0，可以为负，即 没有非负限制。 这样我们把原规划的对偶问题化为 s.t. 没有非负限制。 对照原线性规划问题，我们可以知道： 当原线性规划问题的第i个约束条件取等号时，则其对偶问题的 i个决策变量没有非负限制。 如果当原线性规划问题中的第 i个决策变量 没有非负限制时，我们也可以用 进行替换，这里 ， ，用类似的方法知道其对偶问题中第 i个约束条件取等号。3 33yyy3 3yy 0y3 3yy03y, 0,3 3yy3y3y321200100440minyyyf, 0, 66, 4343, 356221321321321yyyyyyyyyyy3yixiiixxx 0ix0

12、 ix1 线性规划的对偶(du u)问题第12页/共20页第十三页，共20页。14 另外，用大于等于0的两个决策(juc)变量之差来代替无非负限制的决策(juc)变量也是求解含有无非负限制的决策(juc)变量的线性规划问题的一种方法。 原线性规划问题为： s.t. 321493minxxxf无非负限制32121321321, 0,24035,6032,18032xxxxxxxxxxx1 线性规划(xin xn u hu)的对偶问题第13页/共20页第十四页，共20页。15首先(shuxin)在写对偶问题之前，我们先把第二个约束条件两边乘以-1得 然后按照上面的规则，我们可以得到其对偶问题为 s

13、.t. 1 线性规划的对偶(du u)问题6032321xxx;24060180max321yyyz没有非负限 0,439332352yyyyyyyyyyy第14页/共20页第十五页，共20页。16XYYXbcT第15页/共20页第十六页，共20页。17XXYnjijijbxa1*njijijbxa1*YYXbcT第16页/共20页第十七页，共20页。18。代入第二次迭代表25050100022505050XX111bbbbbB第17页/共20页第十八页，共20页。19迭代次数基变量cBx1 x2 S1 S2 S3b50 100 0 0 02x1501 0 1 0 -1100S200 0 -2 1 1-50 x21000 1 0 0 1250 zj50 100 50 0 50cj -zj0 0 -50 0 -501.确定出基变量，在常数列中找一个最小的负常量(chngling)，把这个常量(chngling)所在行的基变量为出基变量为主元得到新表表，本题以进行迭代运算，得到新为主元，按照单纯形法以作为入基变量的确定具有最小比值求出其中最小值，即数，计算所有对应的则无可行解，如果有负都大于等于零，如果所有的所在行的各系数形中检查出基变量确定入基变量，在单纯23tj. 3.0min,