线性规划对偶理论与方法.pptx

《线性规划对偶理论与方法.pptx》由会员分享，可在线阅读，更多相关《线性规划对偶理论与方法.pptx（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1线性规划对偶理论与方法线性规划对偶理论与方法22023/4/17 6:48一、对偶问题的提出一、对偶问题的提出第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法什么是对偶？对同一事物（或问题），从不同的角度（或立场）提出相对的两种不同的表述。有诗为证：窗含西岭千秋雪，门泊东吴万里船。有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。第1页/共45页32023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法一、对偶问题的提出一、对偶问题的提出对例对例1 1从对偶的角度进行表述。从对偶的角度进行表述。假设该工厂的决策者

2、决定不生产产品甲、乙，而将其所有资源出租或外售。这时工厂的决策者就要考虑给每种资源如何定价的问题。设用y1，y2，y3分别表示出让单位原材料和出租生产设备A，B生产台时的租金的收益。在做决策时，做如下比较：若生产一件产品甲，可获利3元，那么生产每件产品甲的设备台时和原材料出租或出让的所有收入应不低于生产一件产品甲的利润，这就有 y1+4y23.第2页/共45页42023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法一、对偶问题的提出一、对偶问题的提出对例1从对偶的角度进行表述。同理将生产每件产品乙的设备台时和原材料出租或出让的所有收入应不低于生产一件产品乙的利润

3、，这就有：2y1+4y33 把工厂所有设备台时和资源都出租或出让，其收入为：w=8y1+16y2+12y3第3页/共45页52023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法一、对偶问题的提出一、对偶问题的提出例1的对偶数学模型为：min w=8y1+16y2+12y3 y1+4y2 3 2y1 +4y34 yi0，i=1,2,3第4页/共45页62023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法一、对偶问题的提出一、对偶问题的提出从数学逻辑上提出对偶问题由前可知检验数的表达式是：由前可知检验数的表达式是：CNCBB-1N

4、与与CBB-1即：包含所有变量在内的检验数为：即：包含所有变量在内的检验数为：CCBB-1A 将将 Y=CBB-1两边右乘两边右乘b，得到，得到:Yb=CBB-1b=z z 因因Y的上界为无限大，所以只存在最小值。的上界为无限大，所以只存在最小值。令：令：Y=CBB-1，称，称Y为单纯形乘子，由最优解的判为单纯形乘子，由最优解的判定条件可得：定条件可得：Y0即：即：CCBB-1A=CYA0 YAC第5页/共45页72023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法一、对偶问题的提出一、对偶问题的提出从数学逻辑上提出对偶问题 从这里可以得到另一个线性规划问题从

5、这里可以得到另一个线性规划问题:min w=YbYAC Y0 称为原线性规划问题称为原线性规划问题max z=CXAXb，X0的对偶规划问题的对偶规划问题。第6页/共45页82023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题标准型对偶关系对偶对偶第7页/共45页92023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题规范形式原问题与对偶问题变换规则规范形式原问题与对偶问题变换规则规范形式原问题与对偶问题变换规则规范形式原问题与对偶问题变换规则 观察分析上述规范形式下线性规

6、划的原问题及其对偶问题观察分析上述规范形式下线性规划的原问题及其对偶问题的模型形式，可发现，按如下规则，可从线性规划原问题得到的模型形式，可发现，按如下规则，可从线性规划原问题得到其对偶问题：其对偶问题：（3 3）对偶问题约束为）对偶问题约束为型，有型，有?行；行；（1 1）目标函数由）目标函数由maxmax型变为型变为minmin型；型；（2 2）对应原问题，每个约束行有一个对偶变量）对应原问题，每个约束行有一个对偶变量 ;（4 4）原问题的价值系数）原问题的价值系数C C 变换为对偶问题的右端项；变换为对偶问题的右端项；（5 5）原问题的右端项）原问题的右端项b b 变换为对偶问题的价值系

7、数；变换为对偶问题的价值系数；（6 6）原问题的系数矩阵）原问题的系数矩阵A A转置后成为对偶问题的系数矩阵。转置后成为对偶问题的系数矩阵。根据上述变换规则，可直接写出规范形式下线性规划问题对偶问题。根据上述变换规则，可直接写出规范形式下线性规划问题对偶问题。第8页/共45页102023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题标准型原问题与对偶问题的关系第9页/共45页112023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题标准型原问题与对偶问题的关系例例2 2 根据

8、下表写出原问题与对偶问题的表达式根据下表写出原问题与对偶问题的表达式 x y x1x2by1128y24016y30412c34第10页/共45页122023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题标准型原问题与对偶问题的关系 原问题（LP）对偶问题(DP)对偶对偶第11页/共45页132023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题练习题练习练习1 1、写出下列线性规划问题的对偶问题、写出下列线性规划问题的对偶问题第12页/共45页142023/4/17 6:4

9、8第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题非标准型对偶关系原问题的约束条件中含有等式约束条件时，按以下步骤处理：原问题的约束条件中含有等式约束条件时，按以下步骤处理：设等式约束条件的线性规划问题为：设等式约束条件的线性规划问题为：第一步：先将等式约束条件分解为两个不等式约束条件第一步：先将等式约束条件分解为两个不等式约束条件第13页/共45页152023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题非标准型对偶关系第二步：按对称形式变换关系可写出它的对偶问题第二步：按对称形式变换关系可写出

10、它的对偶问题 设设y yi i，y yi i是对应上式的对偶变量，是对应上式的对偶变量，i=1,2,i=1,2,，m m第14页/共45页162023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题非标准型对偶关系将上述规划问题的各式整理后得到：将上述规划问题的各式整理后得到：第15页/共45页172023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题线性规划的原问题与对偶问题的关系可表示为：第16页/共45页182023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法

11、线性规划对偶理论与方法二、写对偶问题二、写对偶问题例题写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题第17页/共45页192023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法二、写对偶问题二、写对偶问题练习题1第18页/共45页202023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法练习题2=y10，y20，y3无约束二、写对偶问题二、写对偶问题第19页/共45页212023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质线性规划对偶问题的基本性质

12、 下面下面介绍介绍对偶基本性质时，一般假定是如下规范对偶关系。对偶基本性质时，一般假定是如下规范对偶关系。设原问题是（记为设原问题是（记为LPLP）：）：对偶问题是（记为对偶问题是（记为DPDP）：）：这这里里A A是是m mn n矩矩阵阵X X是是n n11列列向向量量，Y Y是是11m m行行向向量量。假假设设X Xs s与与Y Ys s分别是分别是（LPLP）与与（DPDP）的松驰变量。的松驰变量。第20页/共45页222023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性质1】对称性 对偶问题的对偶是原问题。【证证

13、】设原问题是设原问题是它与下列线性规划问题是等价的：它与下列线性规划问题是等价的：再写出它的对偶问题：再写出它的对偶问题：它与下列线性规划问题是等价的它与下列线性规划问题是等价的即是原问题。即是原问题。可知，它的对偶问题是可知，它的对偶问题是第21页/共45页232023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性质2】弱对偶性 设X、Y分别为LP(max)与DP(min)的可行解，则 【证证】因为因为X X、Y Y是可行解，故有是可行解，故有AXAXb b,X X00及及Y YA AC C，Y Y0,0,将不等式将不等

14、式 AXAXb b两边左乘两边左乘Y Y，得，得Y Y0 0AXAXY Y0 0b b再将不等式再将不等式Y YA AC C两边右乘两边右乘X X，得，得C XC XYAXYAX故故 C XYAXYb 这这一一性性质质说说明明了了两两个个线线性性规规划划互互为为对对偶偶时时，求求最最大大值值的的线线性性规规划划的的任任意意目目标标值值都都不不会会大大于于求求最最小小值值的的线线性性规规划划的的任任一一目目标标值值，不不能能理理解解为为原原问问题题的的目目标标值值不不超超过过对对偶偶问题的目标值问题的目标值。第22页/共45页242023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线

15、性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性质3】无界性 若原问题（对偶问题）有无界解，则其对偶问题（原问题）无可行解。证：假定原问题有无界解，对偶问题有可行解证：假定原问题有无界解，对偶问题有可行解 YY，Yb Yb。原问题有无界解，即存在。原问题有无界解，即存在C X C X，根据，根据若对偶性有，若对偶性有，Yb C X Yb C X ，显然矛盾，故命题，显然矛盾，故命题成立。成立。可可理理解解为为：在在互互为为对对偶偶的的两两个个问问题题中中，若若一一个个问问题题可可行行且且具具有有无界解，则另一个问题无可行解。无界解，则另一个问题无可行解。注意注意：（1 1）这个定理

16、的逆定理不成立，即若一个问题无可行这个定理的逆定理不成立，即若一个问题无可行解，另一问题不一定有无界解，也可能无可行解；解，另一问题不一定有无界解，也可能无可行解；（2 2）若原问题可行且另一个问题不可行，则原问题具有）若原问题可行且另一个问题不可行，则原问题具有无界解。无界解。第23页/共45页252023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性质4】最优性定理 设X、Y分别是（LP）与（DP）的可行解，则当C X=Yb 时，X、Y是（LP）与（DP）的最优解。【证证】若若C C X X0 0=Y Y0 0b b

17、，由由性性质质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是最优解。是最优解。第24页/共45页262023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性质5】弱对偶性若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值

18、相同。【证证】设设（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）都都有有可可行行解解，则则两两者者都都有有最最优优解解，若若一一个个问问题题无无最最优优解解，则则另另一一问问题题也也无无最最优解。优解。第

19、25页/共45页272023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性质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

20、0得得:Y0A X0Y0XSY0bY0A X0YS X0=C X0第26页/共45页282023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性质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）的最优解。的最优解。思考：性质六

21、有何作用？思考：性质六有何作用？第27页/共45页292023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质性性质质6 6告告诉诉我我们们已已知知一一个个问问题题的的最最优优解解时时求求另另一一个个问问题题的的最最优优解解的方法，即已知的方法，即已知Y*求求X*或已知或已知X*求求Y*。Y*XS=0和和YS X*=0两式称为互补松弛条件。将互补松弛条件写成下式两式称为互补松弛条件。将互补松弛条件写成下式由由于于变变量量都都非非负负，要要使使求求和和式式等等于于零零，则则必必定定每每一一分分量量为为零零，因而有下列关系：因而有下

22、列关系：(1)当yi*0时，,反之当 时yi*=0；第28页/共45页302023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法【例例】已知线性规划已知线性规划的最优解是：的最优解是：求对偶问题的最优解。求对偶问题的最优解。【解解】对偶问题是对偶问题是因因为为X10，X20，所所以以对对偶偶问问题题的的第第一、二个约束的松弛变量等于零，即一、二个约束的松弛变量等于零，即 解解此此线线性性方方程程组组得得y1=1,y2=1,从从而而对对偶偶问问题题的的最最优优解解为为Y=（1，1），），最优值最优值w=26。第29页/共45页312023/4/17 6:48第四讲

23、第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质练习题练习题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。试用对偶理论找出原问题的最优解试用对偶理论找出原问题的最优解 。第30页/共45页322023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质练习题练习题

24、 2 2第31页/共45页332023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性性质质7】互互补补对对偶偶性性LP(max)的的检检验验数数的的相相反数对应于反数对应于DP(min)的一组基本解的一组基本解.其其中中第第j个个决决策策变变量量xj的的检检验验数数的的相相反反数数对对应应于于（DP）中中第第j个个松松弛弛变变量量 的的解解，第第i个个松松弛弛变变量量 的的检检验验数数的的相相反反数数对对应应于于第第i个个对对偶偶变变量量yi的的解解。反反之之，（DP）的的检检验验数数（注注意意：不不乘负号）对应于（乘负号

25、）对应于（LP）的一组基本解。）的一组基本解。互补的两个基解所对应的目标值相等。互补的两个基解所对应的目标值相等。第32页/共45页342023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法三、对偶问题的性质三、对偶问题的性质【性质性质7】互补对偶性互补对偶性 设原问题是设原问题是max z=CX;AX+XS=b;X,XS0 它的对偶问题是它的对偶问题是min w=Yb;YA YS=C;Y,YS0 则则原原问问题题单单纯纯形形表表的的检检验验数数行行对对应应其其对对偶偶问问题题的的一个基解，其对应关系如表。一个基解，其对应关系如表。YS1是对应原问题中基变量是对

26、应原问题中基变量XB的剩余变量，的剩余变量，YS2是对应原问题中非基变量是对应原问题中非基变量XN的剩余变量。的剩余变量。第33页/共45页352023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法 证证:设设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)。当

27、求得原问题的一个解：当求得原问题的一个解：XB=B-1b,其相应的检验数为其相应的检验数为 CN CBB-1N 与与 CBB-1现现分分析析这这些些检检验验数数与与对对偶偶问问题题的的解解之之间间的的关关系系：令令Y=CBB-1,将将它代入得：它代入得：YS1=0,YS2=CN CBB-1N。第34页/共45页362023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法【练习题练习题】线性规划线性规划（1 1）用单纯形法求最优解；）用单纯形法求最优解；（2 2）写出每步迭代对应对偶问题的基本解；）写出每步迭代对应对偶问题的基本解；（3 3）从最优表中写出对偶问题的

28、最优解；）从最优表中写出对偶问题的最优解；第35页/共45页372023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法对偶问题的经济解释对偶问题的经济解释对偶问题的经济解释对偶问题的经济解释-影子价格影子价格影子价格影子价格 第36页/共45页382023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法对偶问题的经济解释对偶问题的经济解释对偶问题的经济解释对偶问题的经济解释-影子价格影子价格影子价格影子价格 第37页/共45页392023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法对偶问题的经济解释

29、对偶问题的经济解释对偶问题的经济解释对偶问题的经济解释-影子价格影子价格影子价格影子价格 第38页/共45页402023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法四、对偶单纯法四、对偶单纯法对偶单纯形法的计算步骤如下：(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

30、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)。第39页/共45页412023/4/17 6:48

31、第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法四、对偶单纯法四、对偶单纯法例例 用对偶单纯形法求解用对偶单纯形法求解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,5第40页/共45页422023/4/17 6:48 x 5x 4x 3x 2x 1B1bXBCB 00-4-3-2cjX4x500-3-3-4-

32、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第四讲第四讲

33、 线性规划对偶理论与方法线性规划对偶理论与方法例题例题第41页/共45页432023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法上上表表中中，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)第42页/共4

34、5页442023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法从以上求解过程可以看到对偶单纯形法有以下优点：l(1)初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。l(2)当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。l(3)在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。第43页/共45页452023/4/17 6:48第四讲第四讲 线性规划对偶理论与方法线性规划对偶理论与方法四、对偶单纯法四、对偶单纯法练习题练习题试用对偶单纯形法求解下列线性规划问题：试用对偶单纯形法求解下列线性规划问题：第44页/共45页