《对偶线性规划PPT课件》由会员分享，可在线阅读，更多相关《对偶线性规划PPT课件（104页珍藏版）》请在金锄头文库上搜索。
1、第二章第二章线性规划的对偶理论线性规划的对偶理论2 2任一线线线线性性性性规规规规划划划划问题都存在另一与之伴随的线性规划问题，他们从不同角度对一个实际问题提出并描述，组成一对互为对偶的线性规划问题。2.1 对偶线性规划问题的提出对偶线性规划3 3一、对偶线性规划问题某工厂计划安排生产、两种产品，已知每种单位产品的利润、生产单位产品所需的设备台时及A、B两种原材料的消耗、现有原材料和设备台时的定额如下表所示：【例1】设设 备备128台时台时原原 材材 料料 A A4016Kg原原 材材 料料 B B0412Kg每单位产品利润（万元）每单位产品利润（万元）23n 原问题的策略原问题的策略: :n
2、 问应如何安排生产才能使问应如何安排生产才能使工厂获利最大？工厂获利最大？n 现在的策略现在的策略: :n 假设不生产假设不生产、产品产品 , ,而是计划而是计划将现有资源出租或出售将现有资源出租或出售, ,从而获得利润从而获得利润, ,这时需要考虑如何定价才合理这时需要考虑如何定价才合理? ?对偶线性规划4 4 设x1、x2分别表示计划生产产品、的单位数量，由题意原问题的模型为：工厂获得最大利润符合资源限制设设 备备128台时台时原原 材材 料料 A A4016Kg原原 材材 料料 B B0412Kg每单位产品利润（万元）每单位产品利润（万元）23n原问题的模型原问题的模型对偶线性规划5 5
3、 改变策略后，需要考虑如何给资源定价的问题！ 设y1、y2 、y3分别表示出租单位设备台时的租金和出售单位原材料A、B的利润.y y1 1+4y+4y2 222， 2y1+4y33则：qq 工厂出租设备工厂出租设备工厂出租设备工厂出租设备、原材料的租金要大于生产的利润才合算。、原材料的租金要大于生产的利润才合算。、原材料的租金要大于生产的利润才合算。、原材料的租金要大于生产的利润才合算。工厂把所有设备台时和资源都出租和出让，用户支付为：qq 要寻找使租用者支付的租金最少的策略。要寻找使租用者支付的租金最少的策略。要寻找使租用者支付的租金最少的策略。要寻找使租用者支付的租金最少的策略。设设 备备
4、128台时台时原原 材材 料料 A A4016Kg原原 材材 料料 B B0412Kg每单位产品利润（万元）每单位产品利润（万元）23n 新问题的模型对偶线性规划6 6工厂改变策略以后改变策略以后改变策略以后改变策略以后的数学模型为：工厂获得相应利润用户所付租金最少对偶线性规划7 7 联系在于，它们都是关于工厂生产经营的模型,并且使用相同的数据；n n 原模型和对偶模型既有联系又有区别原模型和对偶模型既有联系又有区别 区别在于,它们所反映的实质内容是完全不同的：前者是站在工厂经营者经营者经营者经营者的立场上追求工厂的销售收入最大销售收入最大销售收入最大销售收入最大，而后者则是站在谈判对手谈判对
5、手谈判对手谈判对手的立场上寻求应付工厂租金最少租金最少租金最少租金最少的策略。对偶线性规划8 8 所谓对偶规划对偶规划对偶规划对偶规划，就是与线性规划原问题相对应并使用同一组数据按照特定方法形成的另一种反映不同性质问题的线性规划模型。对偶线性规划9 9 二、对偶规划的一般数学模型 原模型与对偶模型有很多的内在联系和相似之处。如原问题如求目标函数最大化，对偶问题即求目标函数最小化；原问题目标函数的系数变成为对偶问题的右边项，而原问题的约束的右边项则变成为对偶问题目标函数的系数；对偶问题的系数矩阵是原问题系数矩阵的转置。就象一个人对着镜子会左右颠倒一样，原问题与对偶问题之间存在着严格的对应关系。原
6、问题的一般模型可定义为：nnxcxcxcZ+=.max2211s.t. 11212111.bxaxaxann+22222121.bxaxaxann+ .mnmnmmbxaxaxa+.22110,.,21nxxx相应的对偶问题的一般模型可定义为： mmybybybS+=.min2211 s.t. 11221111.cyayayamm+22222112.cyayayamm+ nmmnnncyayaya+.22110,.,21myyy对偶线性规划问题：如何由原模型写出对偶模型？其规律是什么问题：如何由原模型写出对偶模型？其规律是什么? ?1010三、原问题与对偶问题的对应关系三、原问题与对偶问题的对
7、应关系 当我们讨论对偶问题时必定是指一对问题，因为没有原问题也就不可能有对偶问题。原问题和对偶问题总是相依存在的。同时，原问题和对偶问题之间也并没有严格的界线，它们互为对偶，谁都可以是原问题，谁也都可以是对偶问题。 下列的表给出了原问题模型和模型的对应关系，这些也可以看作是一个线性规划原问题转化为对偶问题的一般规律。原问题线性规划模型原问题线性规划模型对偶线性规划模型对偶线性规划模型对偶线性规划1111原问题为maxZ的线性规划问题对偶关系表原问题原问题原问题原问题（或对偶问题） 对偶问题对偶问题对偶问题对偶问题（或原问题） 目标函数最大化(maxZ) n个变量 m个约束 约束条件限定向量（右
8、边项） 目标函数价值向量（系数） 0 变量 0 无限制 约束 目标函数最小化（minS） n个约束 m个变量 目标函数价值向量（系数） 约束条件限定向量（右边项） 约束 0 0 变量 0 无限制 同号同号反号反号对偶线性规划1212原问题原问题对偶问题对偶问题目标函数目标函数max目标函数目标函数minn原问题(maxZ)与对偶之关系原问题原问题原问题原问题(maxZ)(maxZ)口诀口诀口诀口诀: :约束决定变量是反号约束决定变量是反号约束决定变量是反号约束决定变量是反号原问题原问题原问题原问题(maxZ)(maxZ)口诀口诀口诀口诀:变量决定约束是同号变量决定约束是同号变量决定约束是同号变
9、量决定约束是同号对偶线性规划1313【解】由原模型三个约束条件确定对偶模型有三个变量y1,y2,y3（还可依对偶问题写出原问题）【例1】写出下列问题的对偶问题：变量决定约束是同号变量决定约束是同号变量决定约束是同号变量决定约束是同号, ,约束决定变量是反号约束决定变量是反号约束决定变量是反号约束决定变量是反号max Z=2x1+x2 5x2 15 6x1+2x2 24 x1+x2 5 x1 0, x2 0 min w=15y1+24y2+5y3 6y2+y3 2s.t. y1 0, y2 0, y3 无约束无约束 5y1+2y2+y3 1对偶线性规划1414原问题为minS的线性规划问题对偶关
10、系表原问题原问题原问题原问题（或对偶问题）对偶问题对偶问题对偶问题对偶问题（或原问题）目标函数最小化(minS) n个变量 m个约束 约束条件限定向量（右边项）目标函数价值向量 0 变量 0 无限制 约束 目标函数最大化（maxZ） n个约束 m个变量 目标函数价值向量（系数）约束条件限定向量 约束 0 0 变量 0 0无限制 同号同号反号反号对偶线性规划1515原问题原问题对偶问题对偶问题目标函数目标函数min目标函数目标函数maxn原问题(minS) 与对偶之关系：原问题原问题原问题原问题(minS)(minS)口诀口诀口诀口诀: :约束决定变量是同号约束决定变量是同号约束决定变量是同号约
11、束决定变量是同号原问题原问题原问题原问题(minS)(minS)口诀口诀口诀口诀:变量决定约束是反号变量决定约束是反号变量决定约束是反号变量决定约束是反号对偶线性规划1616【解】由原模型三个约束条件确定对偶模型有三个变量y1,y2,y332134maxyyyZ+-=s.t. 1232 1-yy2y-332 1 +-y4y42321=+yyy（还可依对偶问题写出原问题）【例2】写出下列问题的对偶问题：32143MinxxxS+-= s.t. 1321+-4xx2x423321-+-xxx3-23 1=+ x xx10,x20,x3无约束变量决定约束是反号变量决定约束是反号变量决定约束是反号变量
12、决定约束是反号, ,约束决定变量是同号约束决定变量是同号约束决定变量是同号约束决定变量是同号01y，02y3无约束y，对偶线性规划1717练习：试求下列线性规划问题的对偶问题321342maxxxxZ-+= s.t. 10321+-xxx534321-=-+-xxx8523321-+xxx01x，02x 对偶线性规划练习练习：试求下列线性规划问题的对偶问题试求下列线性规划问题的对偶问题 答案：答案：答案：答案：321342maxxxxZ-+= s.t. 10321+-xxx534321-=-+-xxx8523321-+xxx01x，02x 3218510minyyyS+-=s.t. 23321
13、+-yyy424321+-yyy353321-=-yyy01y，03y对偶线性规划变量决定约束是同号变量决定约束是同号变量决定约束是同号变量决定约束是同号, ,约束决定变量是反号约束决定变量是反号约束决定变量是反号约束决定变量是反号练习：试求下列线性规划问题的对偶问题 maxZ=5y1+4y2+6y3 y1+2y2 2 y1+2y2+y3 3 -3y1 +y3 -5y1 -y2 +y31 y1 0, y2 , y3 0 答案：答案：答案：答案：对偶线性规划变量决定约束是反号变量决定约束是反号变量决定约束是反号变量决定约束是反号, ,约束决定变量是同号约束决定变量是同号约束决定变量是同号约束决定
14、变量是同号原问题原问题目标函数目标函数maxn原问题(minS) 与对偶之关系符号小结同号同号变量变量对偶线性规划约束约束反号反号约束约束变量变量对偶问题对偶问题目标函数目标函数min2121线性规划的对偶理论包括以下几个基本定理。定理1 （对称性定理）2.2线性规划的对偶理论线性规划的对偶理论定理2 （弱对偶定理）即对偶问题的对偶是原问题。 设x和y分别是原问题和对偶问题的可行解，则必有cxyb，即原问题的目标值小于对偶问题的目标值互为对偶互为对偶对偶线性规划2222定理3 （无界性） 若原问题(对偶问题)为无界解无界解无界解无界解，则其对偶问题(原问题)无无可行解可行解。 反之，若原（对偶
15、）问题有可行解有可行解,对偶（原）问题无可行无可行解解，则原（对偶）问题一定无界无界；定理4 （可行解是最优解的性质）定理5 （强对偶定理） 设X*是原问题的可行解，Y*是对偶问题的可行解，当CX*=Y*b时， X*与Y*是最优解 。 若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等一般是：一般是：cxyb对偶线性规划2323 综上所述：原问题与对偶问题解的对应关系综上所述：原问题与对偶问题解的对应关系 由原问题与对偶问题的解的关系可以判定线性规划的解。对偶线性规划 对对对对 偶偶偶偶 问问问问 题题题题 有最优解有最优解有最优解有最优解 无界无界无界无界 无可行解无可行解无可行解无
16、可行解原原原原 有最优解有最优解有最优解有最优解 问问问问 无无无无 界界界界 题题题题 无可行解无可行解无可行解无可行解 可能可能可能可能 可能可能可能可能2424例4 已知线性规划问题 Max z=x1 + x2 S.t. x1 + x2 + x3 2 2x1 + x2 x3 1 xi 0 (i=1,2 ,3) Min w = 2y1 +y2 S.t. y1 2y2 1 y1 + y2 1 y1 y2 0 y1,y2 0n应用如上关系求解线性规划问题试用对偶理论证明上述规划问题无最优解。 由第一约束条件可知对偶问题无可行解，则原问题的解无界或无可行解， 由于原问题存在可行解，所以解无界。解
17、 该问题存在可行解，如X=(0，0，0)； 其对偶问题为：对偶问题无可行解对偶线性规划2525定理6（互补松弛定理） 在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零对偶变量值为非零对偶变量值为非零对偶变量值为非零，则该约束条件取严格等式严格等式严格等式严格等式；反之如果约约约约束条件取严格不等式束条件取严格不等式束条件取严格不等式束条件取严格不等式，则其对应的对偶变量一定为零对偶变量一定为零对偶变量一定为零对偶变量一定为零。注：证明过程参见教材注：证明过程参见教材5959页性质页性质5 5证明证明对偶线性规划2626【讨论】 互补松弛定理也称松紧定理，它描述了线性规划达到最优
18、时，原问题（或对偶问题）的变量取值和对偶问题（或原问题）约束松紧之间的对应关系。 当线性规划问题达到最优时，我们不仅同时得到了原问题和对偶问题的最优解，而且也还得到了变量和约束之间的一种对应关系。互补松弛定理即揭示了这一点。对偶线性规划2727线性规划达到最优最优最优最优时的关系：1.如果原问题的某一约束为紧约束（严格等式:松弛变量为零），该约束对应的对偶变量应大于或等于零；2.如果原问题的某一约束为松约束（严格不等式:松弛变量大于零），则对应的对偶变量必为零；3.如果原问题的某一变量大于零该变量对应的对偶约束必为紧约束(严格等式)；4.如果原问题的某一变量等于零，该变量对应的对偶约束可能是紧
19、约束(严格等式)，也可能是松约束(严格不等式)。对偶线性规划2828【又例又例】应用如上关系求解线性规划问题应用如上关系求解线性规划问题例5 已知线性规划问题 Min S=2x1 + 3x2 + 5x3 + 2x4 + 3x5 S.t. x1 + x2 + 2x3 + x4 + 3x5 4 2x1 x2 + 3x3 + x4 + x5 3 xi 0 (i=1,2 ,3,4,5)221/5 317/557/5 23=3 解：写出对偶问题为： Max Z = 4y1 + 3y S.t. y1 + 2y2 2 y1 y2 3 2y1 +3y2 5 y1 + y2 2 3y1 +y2 3 y1,y2
20、0已知对偶问题的最优解为 y1 = 4/5, y2 = 3/5, 试应用对偶理论求解原问题。x2 = 0x3 = 0x4 = 0等号又因y1,y2 0，故原问题的两个约束必为紧约束，即x1+3 x5= 42x1+ x5 = 3解得：x1 = x5 = 1。maxZ=5=minS=5得原问题的最优解X*=(1,0,0,0,1) minS=5对偶线性规划2929【练习】已知线性规划问题为： Max.Z=2x1+4x2+x3+x4 s.t. x1+3x2 +x48 2x1+x2 6 x2 + x3 +x46 x1 + x2 +x3 9 xj0（j=1,2,3,4）附 练习答案：y1=4/5, y2=
21、3/5, y3=1, y4=0已知原问题的最优解为:X*=(2,2,4,0)T，试根据互补松弛定理解出其对偶问题的最优解。 线性规划问题的对偶问题为： Min.Z=8y1+6y2+6y3+9y4 s.t. y1+2y2 +y4 2 3y1+y2 + y3 +y4 4 y3 +y4 1 y1 +y3 1 yj0（j=1,2,3,4）对偶线性规划3030为严格不等式，由互补松弛定知，必有y4 = 0； Max Z=2x1+4x2+x3+x4 s.t. x1+3x2 +x48 2x1+x2 6 x2 + x3 +x46 x1 + x2 +x3 9 xj0（j=1,2,3,4） 8=8 6=6 6=6
22、 80,故用单纯形法继续计算故用单纯形法继续计算-70213x6增加变量增加变量x6，已知，已知c6=3,P6=(3,4,2)T，试分析最优解的变化。，试分析最优解的变化。检验数检验数 j=cj-zi= cj y*Pj ， Pj*=B-1Pj对偶线性规划对偶线性规划7878继续迭代得下表Cj比比值值CBXBb检验数检验数 jx1x2x3x4x5x621000351/407/213/8-9/407/21001/4-1/203/401/20-1/83/41x3x1x6023-37/4 0-1/2 0-1/8-5/4 0由此得新的解为由此得新的解为x1=7/2，x2=0，x3=51/4，x4=0，x
23、5=0，x6=3/4，Maxz*=37/4对偶线性规划对偶线性规划7979四、分析四、分析a aijij变化的影响变化的影响 假如假如xj在最终表中为基变量，则在最终表中为基变量，则aij的变化将使最终表中的的变化将使最终表中的B B-1-1变化，因此有可能出现变化，因此有可能出现原问题与对偶问题均为非可行解原问题与对偶问题均为非可行解的情况。的情况。【例例】上例中，上例中， 若若c2=3=3，x2的系数向量变为的系数向量变为P P2=(8=(8，4 4，1)1)T T，试分析最优解的变化。试分析最优解的变化。 maxZ=2x1 + x2 5x2 15 6x1 + 2x2 24 x1 + x2
24、 5 x1 , x2 0 maxZ=2x1 +3x2 8x2 15 6x1 + 4x2 24 x1 + x2 5 x1 , x2 0对偶线性规划对偶线性规划8080 Cj比比值值CBXBb检验数检验数 jx1x2x3x4x52100315/20015/4-15/27/21001/4-1/23/2010-1/43/2x3x1x2021-17/2000-1/4-1/211/21/21/23/2对偶线性规划对偶线性规划【解解】同上例同上例 maxZ=2x1 +3x2 8x2 15 6x1 + 4x2 24 x1 + x2 5 x1 , x2 08181继续迭代得下表继续迭代得下表继续迭代得下表继续迭
25、代得下表因原问题与其对偶问题均为非可行解，通过引入人工变量因原问题与其对偶问题均为非可行解，通过引入人工变量将原问题转化为可行解，再用单纯形法继续计算。将原问题转化为可行解，再用单纯形法继续计算。将第一行将第一行x3+4x4 -24x5=-9化为标准型化为标准型-x3-4x4 +24x5=9再加上人工变量再加上人工变量x3 4x4 +24x5 +x6 =9Cj比比值值CBXBb检验数检验数 jx1x2x3x4x523000-90014-2421001/2-23010-1/23x3x1x2023-130001/2-5对偶线性规划对偶线性规划8282 Cj比比值值CBXBb检验数检验数 jx1x2
26、x3x4x5 x623000 -M900-1-424121001/2-203/2010-1/230x6x1x2023因因 5 0,故用单纯形法迭代计算故用单纯形法迭代计算x34x4 +24x5 +x6 =9-130001/2-5-M-13+9M00-M-4M-5+24M0对偶线性规划对偶线性规划8383继续迭代得下表继续迭代得下表继续迭代得下表继续迭代得下表Cj比比值值CBXBb检验数检验数 jx1x2x3x4x5x62300033/800-1/24-1/611/2411/410-1/121/301/1215/8011/800-1/8x5x1x2023-89/800-5/24-2/30-M+5
27、/24新的最优值为新的最优值为maxz*=89/8得到新最优解：得到新最优解：x1=11/4，x2=15/8，x3=0，x4=0，x5=3/8，x6=0对偶线性规划对偶线性规划8484五、增加一个约束条件的分析五、增加一个约束条件的分析 增加一个约束条件，在实际问题中相当于增添一道工序。分增加一个约束条件，在实际问题中相当于增添一道工序。分析的方法是先将原来的问题的最优解变量取值代入这个新增的约析的方法是先将原来的问题的最优解变量取值代入这个新增的约束条件中，如满足，说明新增约束未起到限制作用，原最优解不束条件中，如满足，说明新增约束未起到限制作用，原最优解不变。否则，将新增约束直接反映到最终
28、表中，再进行分析。变。否则，将新增约束直接反映到最终表中，再进行分析。【例例】上例中，上例中， 新增添一个约束条件新增添一个约束条件 3 3x1+2x2 12，试分析最优试分析最优解的变化。解的变化。【解解】先将原问题最优解先将原问题最优解x1=7/2,x2 =3/2代入新约束条件，因有代入新约束条件，因有故将约束条件写成故将约束条件写成3x1+2x2 +x6 = 12= 12，并取，并取x6为基变量，直接反映为基变量，直接反映到最终表中到最终表中37/2+23/2=27/212 maxZ=2x1 + x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 3x1 +2x2 12 x
29、1 , x2 0对偶线性规划对偶线性规划8585得下表得下表得下表得下表Cj比比值值CBXBb检验数检验数 jx1x2x3x4x5x621000015/20015/4-15/207/21001/4-1/203/2010-1/43/20x3x1x2x60210-17/2000-1/4-1/20x1与与x2的向量不是单位向量，要继续变换的向量不是单位向量，要继续变换12320001对偶线性规划对偶线性规划 3x1 +2x2 12 3x1 +2x2 +x6 =12 8686得下表得下表得下表得下表Cj比比值值CBXBb检验数检验数 jx1x2x3x4x5 x621000 015/200 15/4-1
30、5/2011/41001/4-1/2 03/2 010-1/43/2 0x3x1x2x60210-17/2 0 0 0-1/4-1/2 0用对偶单纯形法迭代继续变换用对偶单纯形法迭代继续变换-3/2 000-1/4-3/2 1对偶线性规划对偶线性规划8787得下表得下表得下表得下表Cj比比值值CBXBb检验数检验数 jx1x2x3x4x5x6210000150 0 15/20-541001/30-1/30 010-1/201x3x1x2x50210-8 000-1/60 -1/31 0001/61-2/3新的最优值为新的最优值为max z*=8得新的最优解为：得新的最优解为：x1=4，x2=0
31、，x3=15，x4=0，x5=1，x6=0，对偶线性规划对偶线性规划88882.7参数线性规划参数线性规划 参数参数aij、bi、 cj在什么范围内变化时最优解不变是实际问题中在什么范围内变化时最优解不变是实际问题中常常要研究的问题，当这些参数超出这个范围时，最优解会发生常常要研究的问题，当这些参数超出这个范围时，最优解会发生怎样的变化，即为参数线性规划要研究的问题。怎样的变化，即为参数线性规划要研究的问题。【例例】线性规划问题线性规划问题 maxZ(l l)=2x1 +x2 5x2 15 6x1 + 2x2 24 x1 + x2 5+l l x1 , x2 0第三个约束右端不断增大，分析最优
32、解会发生怎样的变化？第三个约束右端不断增大，分析最优解会发生怎样的变化？此时此时l l 0对偶线性规划对偶线性规划8989n参数线性规划求解步骤参数线性规划求解步骤1、令、令l l=0求解得最终单纯形表求解得最终单纯形表2、将参数的变化反映到最终单纯形表中；因、将参数的变化反映到最终单纯形表中；因对偶线性规划对偶线性规划9090反映到最终单纯形表中反映到最终单纯形表中反映到最终单纯形表中反映到最终单纯形表中Cj比比值值CBXBb检验数检验数 jx1x2x3x4x52100015/2-(15/2) l l0 0 15/4-15/27/2-(1/2) l l1001/4-1/23/2 +(3/2)
33、 l l010-1/43/2x3x1x2021-17/2-(1/2) l l0 00-1/4-1/23、让、让l l逐步增大，观察原问题与对偶问题解的变化，看哪一个逐步增大，观察原问题与对偶问题解的变化，看哪一个首先出现非可行解。首先出现非可行解。1515/2-(15/2)/2-(15/2)l l l l00x1= 7/2-(1/2)l lx2= 3/2+(3/2)l lZ*= 17/2+(1/2)l l7 7/2-(1/2)/2-(1/2)l l l l003 3/2+(3/2)/2+(3/2)l l l l00当当当当0 0 l l l l11 表中解为最优解。此时表中解为最优解。此时对偶
34、线性规划对偶线性规划9191 Cj比比值值CBXBb检验数检验数 jx1x2x3x4x52100015/2-(15/2)l l0015/4-15/27/2-(1/2)l l1001/4-1/23/2+(3/2)l l010-1/43/2x3x1x2021-17/2-(1/2) l l 0 0 0-1/4-1/2当当l1l1时，用对偶单纯形法迭代时，用对偶单纯形法迭代注：不用讨论注：不用讨论7/2-(1/2)l l0的情况，因为此时，的情况，因为此时，15/2-(15/2)l l也是也是负的，且绝对值更大。因此出基项仍然是负的，且绝对值更大。因此出基项仍然是x3 3（第一行）。（第一行）。对偶线
35、性规划对偶线性规划9292 Cj比比值值CBXBb检验数检验数 jx1x2x3x4x521000-1+ l l00-2/15-1/61310-1/151/603011/500x5x1x2021-900-1/15-1/30当当l l继续增大，原问题与对偶问题都保持可行解，故计算至此结束。继续增大，原问题与对偶问题都保持可行解，故计算至此结束。结论：结论： 0l01,x1=3,x2=3,maxZ=9对偶线性规划对偶线性规划9393 【图示图示】目标函数目标函数Z(l l)与与l l的变化关系图的变化关系图l lZ(l l)12l l8.51522.59 l l1,Z=17/2+(1/2)l ll
36、l1,Z=9注：问题中多个参数变化时，应使目标函数注：问题中多个参数变化时，应使目标函数z(l l)是是l l的线性函数。的线性函数。对偶线性规划对偶线性规划9494 【例例】求解下述参数求解下述参数线性规划问题线性规划问题 maxZ=（2+l l )x1+(1+2l l )x2 5x2156x1+2x224 x1+x25x1,x2 0【解解】按按参参数数线线性性规规划划求求解解问问题题的的第第一一、二二步步，令令l=0 l=0 求求得得最优解，并将最优解，并将cj的变化值反映到最终单纯形表中。的变化值反映到最终单纯形表中。对偶线性规划对偶线性规划9595反映到最终单纯形表中Cj比比值值CBX
37、Bb检验数检验数 jx1x2x3x4x52+l l1+2l l00015/20015/4-15/27/21001/4-1/23/2010-1/43/2x3x1x202+l l1+2l l-17/2 l l2l l0-1/4-1/2当当-1/5-1/5 l l11时，表中解为最优解。此时时，表中解为最优解。此时当当l l1111 ，变量，变量x4的检验数为的检验数为正值正值，用单纯形法继续迭代得，用单纯形法继续迭代得z*=7/2(=7/2(2+l)+3/2 (l)+3/2 (1+2l)= l)= 17/2+13l l/2-17/2-13l l/2000-1/4+l l/4-1/2-5l l/2-
38、1/4+l l/40-1/2-5l l/20-1/5l l1当当l l-1/5-1/5-1/51111，原问题与对偶问题都保持可行解，故计算至此结束。原问题与对偶问题都保持可行解，故计算至此结束。工厂的最优计划为工厂的最优计划为x1=2=2， x2=3=3，z*=2(=2(2+l)+3 (l)+3 (1+2l)= l)= 7+8l l当当l l1111 ，变量，变量x x4 4的检验数为正值，用单纯形法继续迭代得的检验数为正值，用单纯形法继续迭代得9797当l-1/5时 Cj比比值值CBXBb检验数检验数 jx1x2x3x4x52+l l1+2l l00015/20015/4-15/27/21
39、001/4-1/23/2010-1/43/2x3x1x202+l l1+2l l-17/2 l l2l l0-1/4-1/2当当l l-1/5-1/5-1/5-1/5时，时，变量变量x5的检验数为正值，用单纯形法继续迭代得的检验数为正值，用单纯形法继续迭代得-17/2-13l l/2000-1/4+l l/4-1/2-5l l/2对偶线性规划对偶线性规划9898当l-1/5-1/5-1/5-1/5，变量x5的检验数为正值，用单纯形法继续迭代得Cj比比值值CBXBb检验数检验数 jx1x2x3x4x52+l l1+2l l0001505100411/301/60102/30-1/61x3x1x5
40、02+l l0-8-4l l 01/3+5/3l l0-1/3-1/6l l0当当-2-2l l-1/5-1/5，原问题与对偶问题都保持可行解，故计算至此结束。原问题与对偶问题都保持可行解，故计算至此结束。工厂的最优计划为工厂的最优计划为x1=4，x2=0，x3=15，z*=4*(2+l l)=8+4l l1/3+5/3l l0-1/3-1/6l l0-2l l-1/5l l-2,Z(l l)8+4l l1111，z*=7+8l l当当-2-2l l-1/5-1/5， z*=8+4l l100100【例例】某某文文教教用用品品厂厂利利用用原原材材料料白白坯坯纸纸生生产产原原稿稿纸纸、日日记记本
41、本和和练练习习本本三三种种产产品品。该该厂厂现现有有工工人人100人人，每每天天白白坯坯纸纸供供应应量量为为3万万kg。如如果果单单独独生生产产各各种种产产品品时时，每每个个工工人人每每天天生生产产原原稿稿纸纸30捆捆，或或日日记记本本30打打，或或练练习习本本30箱箱。书书籍籍原原材材料料消消耗耗为为：每每捆捆原原稿稿纸纸用用白白坯坯纸纸10/3kg，每每打打日日记记本本用用白白坯坯纸纸40/3kg，每每箱箱练练习习本本用用白白坯坯纸纸80/3kg。又又知知每每生生产产一一捆捆原原稿稿纸纸可可盈盈利利2元元，每每生生产产一一打打日日记记本本可可盈盈利利3元元，每每生生产产一一箱箱练练习习本本
42、可可盈盈利利1元元。试试决决定定：（1）在在现现有有生生产产条条件件下下工工厂厂盈盈利利最最大大的的生生产产方方案案；（2）如如果果白白坯坯纸纸的的供供应应数数量量不不变变，当当工工人人人人数数不不足足时时，可可招招收收临临时时工工，临临时时工工工工资资支支出出为为每每人人每每天天40元元，问问该该厂厂要要不不要要招招收收临临时时工工，招多少人？招多少人？对偶线性规划对偶线性规划101101【解解】由已知条件得由已知条件得 maxZ=2x1+3x2 +x3 1/30 x1+1/30x2+1/30x3100 10/3x1+40/3x2+80/3x330000x1,x2 ,x3 0设设该该厂厂每每
43、天天生生产产原原稿稿纸纸x1捆捆，日日记记本本x2打打，练练习习本本x3箱箱。则则上上述问题的参数规划模型为：述问题的参数规划模型为：（1）在现有生产条件下工厂求盈利最大的生产方案）在现有生产条件下工厂求盈利最大的生产方案原稿纸原稿纸日记本日记本练习本练习本资源限制资源限制工人工人1/301/301/301/301/301/30100100白坯纸消耗白坯纸消耗10/310/340/340/380/380/33000030000盈利盈利2 23 31 1对偶线性规划对偶线性规划102102计算过程计算过程计算过程计算过程Cj比比值值CBXBb检验数检验数 jx1x2x3x4x5231003000
44、010/340/380/3101001/301/301/3001X4x500023100检验数检验数 j22501/4123/400251/400-1/30-1/4001x2X530-675005/40-5-9/4002250300090001000 maxZ=2x1 +3x2 +x3 10/3x1 + 40/3x2 +80/3x3 30000 1/30 x1 + 1/30 x2 + 1/30 x3 100检验数检验数 j2000017/31/10-10100010-4/3-1/1040X2X132-800000-10/3-1/10-50x1=1000,x2=2000，maxmaxz=8000
45、对偶线性规划对偶线性规划103103Cj比比值值CBXBb检验数检验数 jx1x2x3x4x5231002000017/31/10-10100010-4/3-1/1040x2x132-8000+40l l00-10/3-1/10-50检验数检验数 jl-200l-2000-1/10-7/30-1/100190001483/100x5x102-18000+40l l0-5-15-6/1000l2000l200l200Z=8000+10l lZ=18000-40l l所以该厂最多所以该厂最多招收招收200名临时工名临时工当且仅当当且仅当l=200l=200时，时，Z Z最大最大 maxZ=2x1
46、+3x2 +x3 -40l l10/3x1 + 40/3x2 +80/3x3 300001/30 x1 + 1/30 x2 + 1/30 x3100+l l2000-10l l1000+40l l-8000+40l l-50l l （2）用）用l l表示表示招收的临时工数，则上述问题的参数规划模型为：招收的临时工数，则上述问题的参数规划模型为：104104【图示图示】目标函数目标函数Z(l l)与与l l的变化关系图的变化关系图l lZ(l l)1002003003004000800012000 0l l200,Z=8000+10l ll l200,Z=18000-40l l对偶线性规划对偶线性规划
