线性规划对偶理论与方法演示文稿课件

湖州师范学院商学院湖州师范学院商学院运筹学运筹学（operations research,OR）第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法商学院电子商务系商学院电子商务系7/16/20241湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法一一.对偶问题的提出对偶问题的提出二二.写对偶问题写对偶问题 三三.对偶问题的性质对偶问题的性质四四.对偶单纯形法对偶单纯形法7/16/20242湖州师范学院商学院湖州师范学院商学院一、对偶问题的提出一、对偶问题的提出第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法什么是对偶？对同一事物（或问题），从不同的角度（或立场）提出相对的两种不同的表述。有诗为证：窗含西岭千秋雪，门泊东吴万里船。有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。7/16/20243湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法一、对偶问题的提出一、对偶问题的提出对例对例1 1从对偶的角度进行表述。从对偶的角度进行表述。假设该工厂的决策者决定不生产产品甲、乙，而将其所有资源出租或外售。这时工厂的决策者就要考虑给每种资源如何定价的问题。设用y1，y2，y3分别表示出让单位原材料和出租生产设备A，B生产台时的租金的收益。在做决策时，做如下比较：若生产一件产品甲，可获利3元，那么生产每件产品甲的设备台时和原材料出租或出让的所有收入应不低于生产一件产品甲的利润，这就有 y1+4y23.7/16/20244湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法一、对偶问题的提出一、对偶问题的提出对例1从对偶的角度进行表述。同理将生产每件产品乙的设备台时和原材料出租或出让的所有收入应不低于生产一件产品乙的利润，这就有：2y1+4y33 把工厂所有设备台时和资源都出租或出让，其收入为：w=8y1+16y2+12y37/16/20245湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法一、对偶问题的提出一、对偶问题的提出例1的对偶数学模型为：min w=8y1+16y2+12y3 y1+4y2 3 2y1 +4y34 yi0，i=1,2,37/16/20246湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法一、对偶问题的提出一、对偶问题的提出从数学逻辑上提出对偶问题由前可知检验数的表达式是：由前可知检验数的表达式是：CNCBB-1N与与CBB-1即：包含所有变量在内的检验数为：即：包含所有变量在内的检验数为：CCBB-1A 将将 Y=CBB-1两两边右乘右乘b，得到，得到:Yb=CBB-1b=z z 因因Y的上界的上界为无限大，所以只存在最小无限大，所以只存在最小值。令：令：Y=CBB-1，称，称Y为单纯形乘子，由最优解的判为单纯形乘子，由最优解的判定条件可得：定条件可得：Y0即：即：CCBB-1A=CYA0 YAC7/16/20247湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法一、对偶问题的提出一、对偶问题的提出从数学逻辑上提出对偶问题 从这里可以得到另一个线性规划问题从这里可以得到另一个线性规划问题:min w=YbYAC Y0 称称为原原线性性规划划问题max z=CXAXb，X0的的对偶偶规划划问题。7/16/20248湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题标准型对偶关系对偶对偶7/16/20249湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题规范形式原问题与对偶问题变换规则规范形式原问题与对偶问题变换规则 观察分析上述规范形式下线性规划的原问题及其对偶问题观察分析上述规范形式下线性规划的原问题及其对偶问题的模型形式，可发现，按如下规则，可从线性规划原问题得到的模型形式，可发现，按如下规则，可从线性规划原问题得到其对偶问题：其对偶问题：（3 3）对偶问题约束为）对偶问题约束为型，有型，有?行；行；（1 1）目标函数由）目标函数由maxmax型变为型变为minmin型；型；（2 2）对应原问题，每个约束行有一个对偶变量）对应原问题，每个约束行有一个对偶变量 ;（4 4）原问题的价值系数）原问题的价值系数C C 变换为对偶问题的右端项；变换为对偶问题的右端项；（5 5）原问题的右端项）原问题的右端项b b 变换为对偶问题的价值系数；变换为对偶问题的价值系数；（6 6）原问题的系数矩阵）原问题的系数矩阵A A转置后成为对偶问题的系数矩阵。转置后成为对偶问题的系数矩阵。根据上述变换规则，可直接写出规范形式下线性规划问题对偶问题。根据上述变换规则，可直接写出规范形式下线性规划问题对偶问题。7/16/202410湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题标准型原问题与对偶问题的关系7/16/202411湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题标准型原问题与对偶问题的关系例例2 2 根据下表写出原问题与对偶问题的表达式根据下表写出原问题与对偶问题的表达式 x y x1x2by1128y24016y30412c347/16/202412湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题标准型原问题与对偶问题的关系 原问题（LP）对偶问题(DP)对偶对偶7/16/202413湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题练习题练习练习1 1、写出下列线性规划问题的对偶问题、写出下列线性规划问题的对偶问题7/16/202414湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题非标准型对偶关系原问题的约束条件中含有等式约束条件时，按以下步骤处理：原问题的约束条件中含有等式约束条件时，按以下步骤处理：设等式约束条件的线性规划问题为：设等式约束条件的线性规划问题为：第一步：先将等式约束条件分解为两个不等式约束条件第一步：先将等式约束条件分解为两个不等式约束条件7/16/202415湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题非标准型对偶关系第二步：按对称形式变换关系可写出它的对偶问题第二步：按对称形式变换关系可写出它的对偶问题 设设y yi i，y yi i是对应上式的对偶变量，是对应上式的对偶变量，i=1,2,i=1,2,，m m7/16/202416湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题非标准型对偶关系将上述规划问题的各式整理后得到：将上述规划问题的各式整理后得到：7/16/202417湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题线性规划的原问题与对偶问题的关系可表示为：7/16/202418湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题例题写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题7/16/202419湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题练习题17/16/202420湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法练习题2=y10，y20，y3无约束二、写对偶问题二、写对偶问题7/16/202421湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质线性规划对偶问题的基本性质 下面下面介绍介绍对偶基本性质时，一般假定是如下规范对偶关系。对偶基本性质时，一般假定是如下规范对偶关系。设原问题是（记为设原问题是（记为LPLP）：）：对偶问题是（记为对偶问题是（记为DPDP）：）：这这里里A A是是m mn n矩矩阵阵X X是是n n11列列向向量量，Y Y是是11m m行行向向量量。假设假设X Xs s与与Y Ys s分别是分别是（LPLP）与与（DPDP）的松驰变量。的松驰变量。7/16/202422湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性质1】对称性 对偶问题的对偶是原问题。【证】设原问题是【证】设原问题是它与下列线性规划问题是等价的：它与下列线性规划问题是等价的：再写出它的对偶问题：再写出它的对偶问题：它与下列线性规划问题是等价的它与下列线性规划问题是等价的即是原问题。即是原问题。可知，它的对偶问题是可知，它的对偶问题是7/16/202423湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性质2】弱对偶性 设X、Y分别为LP(max)与DP(min)的可行解，则 【证】因为【证】因为X X、Y Y是可行解，故有是可行解，故有AXAXb b,X X00及及Y YA AC C，Y Y0,0,将不等式将不等式 AXAXb b两边左乘两边左乘Y Y，得，得Y Y0 0AXAXY Y0 0b b再将不等式再将不等式Y YA AC C两边右乘两边右乘X X，得，得C XC XYAXYAX故故 C XYAXYb 这这一一性性质质说说明明了了两两个个线线性性规规划划互互为为对对偶偶时时，求求最最大大值值的的线线性性规规划划的的任任意意目目标标值值都都不不会会大大于于求求最最小小值值的的线线性性规规划划的的任任一一目目标标值值，不不能能理理解解为为原原问问题题的的目目标标值值不不超超过过对偶问题的目标值对偶问题的目标值。7/16/202424湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性质3】无界性 若原问题（对偶问题）有无界解，则其对偶问题（原问题）无可行解。证：假定原问题有无界解，对偶问题有可行解证：假定原问题有无界解，对偶问题有可行解 Y Y，Yb Yb。原问题有无界解，即存在。原问题有无界解，即存在C X C X，根据，根据若对偶性有，若对偶性有，Yb C X Yb C X ，显然矛盾，故命题，显然矛盾，故命题成立。成立。可可理理解解为为：在在互互为为对对偶偶的的两两个个问问题题中中，若若一一个个问问题题可可行行且且具具有有无界解，则另一个问题无可行解。无界解，则另一个问题无可行解。注意注意：（1 1）这个定理的逆定理不成立，即若一个问题无可行这个定理的逆定理不成立，即若一个问题无可行解，另一问题不一定有无界解，也可能无可行解；解，另一问题不一定有无界解，也可能无可行解；（2 2）若原问题可行且另一个问题不可行，则原问题）若原问题可行且另一个问题不可行，则原问题具有无界解。具有无界解。7/16/202425湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性质4】最优性定理 设X、Y分别是（LP）与（DP）的可行解，则当C X=Yb 时，X、Y是（LP）与（DP）的最优解。【证证】若若C C X X0 0=Y Y0 0b b ，由由性性质质2 2，对对偶偶问问题题的的所所有有可可行行解解YY都都存存在在 Y Ybb CXCX。因因为为C C X X0 0=Y Y0 0b b ，所所以以Y Y b b Y Y0 0b b ，可可见见Y Y0 0是是使使目目标标函函数数取取值值最最小小的的可行解，因而可行解，因而Y Y0 0是最优解。同理可证，是最优解。同理可证，X X0 0是最优解。是最优解。7/16/202426湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性质5】弱对偶性若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。【证证】设设（LPLP）有有最最优优解解X X0 0,那那么么对对于于最最优优基基B B必必有有C-CC-CB BB B-1-1A A00与与C CB BB B-1-100，即即有有Y YAAC C与与Y Y00，这这里里Y Y=C CB BB B-1-1 ，从从而而Y Y是可行解，对目标函数有是可行解，对目标函数有由性质由性质4 4知知Y Y是最优解。是最优解。由由性性质质 5 5 还还可可推推出出另另一一结结论论：若若（LPLP）与与（DPDP）都都有有可可行行解解，则则两两者者都都有有最最优优解解，若若一一个个问问题题无无最最优优解解，则则另另一一问问题题也也无无最最优解。优解。7/16/202427湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性质6】互补松弛定理 设X0、Y0分别为（LP）与（DP）的可行解，XS和YS分别是（LP）与（DP）的松弛变量，则当且仅当X0 和Y0 是最优解时，有YSX0=0和和Y0XS=0。【证证】设设X X和和Y Y是是最最优优解解,由由性性质质4 4，C C X X0 0=Y Y0 0b b，由由于于X XS S和和Y YS S是松弛变量，则有是松弛变量，则有A X0XSbY0AYS=C将第一式左乘将第一式左乘Y Y0 0，第二式右乘，第二式右乘X X0 0得得:Y0A X0Y0XSY0bY0A X0YS X0=C X07/16/202428湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性质6】互补松弛定理:YSX0=0和和Y0XS=0 显然有显然有:Y0XS=YS X0又因为又因为Y Y、X Xs s、Y Ys s、X X00，所以有所以有:YXS=0和和YS X=0反之，反之，当当YXS=0和和YS X=0时，有时，有:YA XYbYA X=C X 显显然然有有Y0b=C X,由由性性质质4 4知知:Y与与X是是（LP）与与（DP）的的最优解。最优解。思考：性质六有何作用？思考：性质六有何作用？7/16/202429湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质性性质质6 6告告诉诉我我们们已已知知一一个个问问题题的的最最优优解解时时求求另另一一个个问问题题的的最最优优解解的方法，即已知的方法，即已知Y*求求X*或已知或已知X*求求Y*。Y*XS=0和和YS X*=0两式称为互补松弛条件。将互补松弛条件写成下式两式称为互补松弛条件。将互补松弛条件写成下式由由于于变变量量都都非非负负，要要使使求求和和式式等等于于零零，则则必必定定每每一一分分量量为为零零，因而有下列关系：因而有下列关系：(1)当yi*0时，,反之当 时yi*=0；7/16/202430湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法【例】【例】已知线性规划已知线性规划的最优解是：的最优解是：求对偶问题的最优解。求对偶问题的最优解。【解】对偶问题是【解】对偶问题是因因为为X10，X20，所所以以对对偶偶问问题题的的第第一一、二个约束的松弛变量等于零，即二个约束的松弛变量等于零，即 解解此此线线性性方方程程组组得得y1=1,y2=1,从从而而对对偶偶问问题题的的最最优优解解为为Y=（1，1），），最优值最优值w=26。7/16/202431湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质练习题练习题1 1 例：例：已知线性规划问题已知线性规划问题min w=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53 xj0，j=1，2，5 已知其对偶问题的最优解为已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解试用对偶理论找出原问题的最优解 。7/16/202432湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质练习题练习题 2 27/16/202433湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性性质质7】互互补补对对偶偶性性LP(max)的的检检验验数数的的相相反反数对应于数对应于DP(min)的一组基本解的一组基本解.其其中中第第j个个决决策策变变量量xj的的检检验验数数的的相相反反数数对对应应于于（DP）中中第第j个个松松弛弛变变量量 的的解解，第第i个个松松弛弛变变量量 的的检检验验数数的的相相反反数数对对应应于于第第i个个对对偶偶变变量量yi的的解解。反反之之，（DP）的的检检验验数数（注注意意：不不乘乘负负号号）对应于（对应于（LP）的一组基本解。）的一组基本解。互补的两个基解所对应的目标值相等。互补的两个基解所对应的目标值相等。7/16/202434湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性质【性质7】互补对偶性】互补对偶性 设原问题是设原问题是max z=CX;AX+XS=b;X,XS0 它的对偶问题是它的对偶问题是min w=Yb;YA YS=C;Y,YS0 则则原原问问题题单单纯纯形形表表的的检检验验数数行行对对应应其其对对偶偶问问题题的的一一个基解，其对应关系如表。个基解，其对应关系如表。YS1是对应原问题中基变量是对应原问题中基变量XB的剩余变量，的剩余变量，YS2是对应原问题中非基变量是对应原问题中非基变量XN的剩余变量。的剩余变量。7/16/202435湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法 证证:设设B B是原问题的一个可行基，于是是原问题的一个可行基，于是A A=(=(B B,N N)；原问题可改写为：；原问题可改写为：max z=CBXB+CNXNBXB+NXN+XS=bXB，XN，XS0相应地对偶问题可表示为：相应地对偶问题可表示为：min w=Yb YB YS1=CB YN YS2=CN Y，YS1,YS20这里这里YS=(YS1，YS2)。当求得原当求得原问题的一个解：的一个解：XB=B-1b,其相其相应的的检验数数为 CN CBB-1N 与与 CBB-1现分分析析这些些检验数数与与对偶偶问题的的解解之之间的的关关系系：令令Y=CBB-1,将将它代入得：它代入得：YS1=0,YS2=CN CBB-1N。7/16/202436湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法【练习题】【练习题】线性规划线性规划（1 1）用单纯形法求最优解；）用单纯形法求最优解；（2 2）写出每步迭代对应对偶问题的基本解；）写出每步迭代对应对偶问题的基本解；（3 3）从最优表中写出对偶问题的最优解；）从最优表中写出对偶问题的最优解；7/16/202437湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法对偶问题的经济解释-影子价格 7/16/202438湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法对偶问题的经济解释-影子价格 7/16/202439湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法对偶问题的经济解释-影子价格 7/16/202440湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法四、对偶单纯法四、对偶单纯法对偶单纯形法的计算步骤如下：(1)(1)检查检查b b列的数字时，若至少还有一个负分量，列的数字时，若至少还有一个负分量，检验数保持非正，那么进行以下计算。检验数保持非正，那么进行以下计算。(2)(2)确定换出变量。按确定换出变量。按minmin(B B-1-1b b)i i(B B-1-1b b)i i00(B B-1-1b b)l l对应的基变量对应的基变量x xi i为换出变量为换出变量 (3)(3)确定换入变量。在单纯形表中检查确定换入变量。在单纯形表中检查x xl l所在行的所在行的各系数各系数l lj j(j j=1,2,=1,2,，n n)。若所有。若所有l lj j00，则无可行解，停，则无可行解，停止止 计算。若存在计算。若存在l lj j0 (0 (j j=1,2,=1,2,，n n),),计算计算 (4)(4)以以l lk k为主元素，按原单纯形法在表中进行迭为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。代运算，得到新的计算表。重复步骤重复步骤(1)(1)(4)(4)。7/16/202441湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法四、对偶单纯法四、对偶单纯法例例 用对偶单纯形法求解用对偶单纯形法求解min w=2x1+3x2+4x3x1+2x2+x332x1x2+3x34x1，x2，x30解：先将此解：先将此问题化成下列形式，以便得到化成下列形式，以便得到对偶偶问题的初始可的初始可行基行基：max z=2x1 3x2 4x3 x1 2x2 x3+x4 =32x1+x2 3x3 +x5 =4xj0，j=1,2,57/16/202442湖州师范学院商学院湖州师范学院商学院 x 5x 4x 3x 2x 1B1bXBCB 00-4-3-2cjX4x500-3-3-4-4-1-1-2-2-2-21 1-1-1-3-31 10 00 01 1-2-3-400 B1bXBCBx 1x 2x 3x 4x 5X4x10 0-2-20 0-5/2-5/21/21/21 1-1/2-1/2-1-11 1-1/2-1/23/23/20 0-1/2-1/22 2-4-4-1-10 0-1-10 0 B1bXBCBx 1x 2x 3x 4x 5X2x1-3-3-2-21 10 07/57/5-1/5-1/5-2/5-2/511/511/50 01 1-1/5-1/5-2/5-2/51/51/52/52/50 0-9/5-9/5-8/5-8/5-1/5-1/50 0第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法例题例题7/16/202443湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法上上表表中中，b b列列数数字字全全为为非非负负，检检验验数数全全为为非非正正，故故问问题题的的最最优解为优解为X X*=(11/5=(11/5，2/52/5，0 0，0 0，0)0)T T例题例题 若若对对应应两两个个约约束束条条件件的的对对偶偶变变量量分分别别为为y y1 1和和y y2 2，则则对对偶偶问问题题的最优解为的最优解为Y Y*=(y=(y1 1*,y,y2 2*)=(8/5,1/5)=(8/5,1/5)7/16/202444湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法从以上求解过程可以看到对偶单纯形法有以下优点：l(1)初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。l(2)当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。l(3)在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。7/16/202445湖州师范学院商学院湖州师范学院商学院第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法四、对偶单纯法四、对偶单纯法练习题练习题试用对偶单纯形法求解下列线性规划问题：试用对偶单纯形法求解下列线性规划问题：7/16/202446