1、第二章第二章 线性规划对偶理论线性规划对偶理论第一节第一节 线性规划对偶理论线性规划对偶理论第二第二节节 对偶问题基本性质对偶问题基本性质第三第三节节 影子价格影子价格第四第四节节 对偶单纯形法对偶单纯形法第五第五节节 灵敏度分析灵敏度分析1/66第一节第一节 线性规划对偶理论线性规划对偶理论一、对偶问题的提出一、对偶问题的提出例例2/66设备台时设备台时/件产品件产品可用台时可用台时（千小时）（千小时）产品产品1产品产品2下料设备下料设备A104机加工设备机加工设备B0212焊接设备焊接设备C3218产品单价产品单价3元元/件件5元元/件件3/66n生产是为赢利（取得收入）。还有生产是为赢利
2、（取得收入）。还有别的别的办法办法赢赢利（取得收入）利（取得收入）。例如，卖出或出租设备。例如，卖出或出租设备。n问，三种设备卖价问，三种设备卖价或租价各或租价各应是应是多少，进项才多少，进项才不不低于自己生产时的销售收入？低于自己生产时的销售收入？n原来的问题：原来的问题：两种产品各生产多少，利润总额两种产品各生产多少，利润总额最大？最大？4/66n用用y1、y2和和y3分别表示分别表示A、B和和 C三种设备单位三种设备单位台时卖价台时卖价或或租价，则，总进项租价，则，总进项w可表示可表示成成 w=4y1+12y2+18y3 生产两种产品消耗的设备台时的价值（或称出售生产两种产品消耗的设备台
3、时的价值（或称出售或出租两种产品所用设备或出租两种产品所用设备台时的进项）分别台时的进项）分别是是 1y1+0y2+3y3 和和 0y1+2y2+2y3 两种产品售价分别是两种产品售价分别是3和和5。出售或。出售或出租产品出租产品所用所用设备台时的设备台时的进项不能低于售价。所以，应有进项不能低于售价。所以，应有 1y1+0y2+3y3 3和和 0y1+2y2+2y3 5从另一个角度看从另一个角度看，w=4y1+12y2+18y3是总是总消耗。消耗。5/66n回答回答y1、y2和和y3各是多少的问题，可表示如下：各是多少的问题，可表示如下：Min w=4y1+12y2+18y3 s.t.y1
4、+3y3 3 2y2+2y3 5 y1,y2,y30 该问题该问题叫做叫做原问题原问题(P)的对偶问题的对偶问题(D)。可看出，。可看出，Max z=CX Min w=bTY(P)s.t.AXb (D)s.t.ATYCT X0 Y06/66cj35000icBxBB-1bx1x2x3x4x50 x320011/3-1/35x260101/203x12100-1/31/3z36000-3/2-1j若要问对偶问题的解是什么，可以看若要问对偶问题的解是什么，可以看解解(P)时得到的时得到的最终最终单纯形表单纯形表。最终单纯形表最终单纯形表7/66从该表松弛变量的检验数行得到：从该表松弛变量的检验数行
5、得到：3=0，4=-3/2，5=-1，y1=0，y2=3/2，y3=1，将其代入，将其代入(D):w=40+123/2+181=36 (1)0 +31=3 (2)23/2+21=5 (3)y1,y2,y30 (4)这是对偶问题有趣的一个方面。这是对偶问题有趣的一个方面。8/66二、对称的二、对称的对偶对偶问题一般形式问题一般形式上面的例子叫做对称的对偶问题。上面的例子叫做对称的对偶问题。三、非对称的三、非对称的对偶问题对偶问题请见请见教科书教科书第三版第三版第第52页或页或第四版第四版第第53页的页的表。表。9/66事项事项原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题
6、）AbC目标函数目标函数 n个个决策变量决策变量 xj0 xj0 xj无约束无约束m个个决策变量决策变量yi0yi0yi无约束无约束第二节第二节 对偶理论基本性质对偶理论基本性质一、对称一、对称形式单纯形法矩阵形式单纯形法矩阵表达表达 Max z=CX s.t.AXb X0化成标准形式化成标准形式 Max z=CX+0Xs s.t.AX+IXs=b X，Xs0 Xs=(xs1,xs2,xsm)T 是是松松弛变量弛变量10/66令令 X =XB ，(C,0)=(CB,CN)Xs XN (A,I)=(B,N)z=CBB-1b+(CN-CBB-1N)XN (1)CN-CBB-1N是非是非基变量基变量
7、xm+1,xm+2,xn的检验的检验数数，令，令j=cj-CBB-1Pj，若所有的，若所有的j 0，即，即 CN-CBB-1N0 (2)则则表示目前的基表示目前的基可行解最优可行解最优。另外，基变量。另外，基变量XB 的的检验数检验数是是 CB-CBB-1B=0 (3)11/66松弛变量松弛变量Xs=(xs1,xs2,xsm)T的检验数的检验数是是 0-CBB-1I 0，即，即-CBB-10 (4)将将(2)和和(3)写在一起：写在一起：(CB，CN)-(CBB-1B，CBB-1N)0或或 (CB，CN)-CBB-1(B，N)0，即，即 C-CBB-1A0 (5)12/66再将再将(1)z=C
8、BB-1b、(5)和和(4)写写在一起在一起：z=CBB-1b (1)C-CBB-1A0 (5)-CBB-10 (4)令令YT=CBB-1，w=YTb (1)C-YTA0 (5)-YT0 (4)或或 w=YTb ATYCT Y0 13/66 Min w=YTb(D)s.t.ATYCT Y0添加剩余变量后，变成添加剩余变量后，变成 Min w=YTb+0Ys(D)s.t.ATY-IYs=CT Y,Ys0 Ys=(ys1,ys2,ys,n-m)T 是剩余变量是剩余变量 14/6615/66 例例 Max z=3x1+5x2 s.t.x1 4 y1 (P)2x2 12 y2 3x1+2x2 18 y
9、3 x1，x2 0 Min w=4y1+12y2+18y3 s.t.y1 +3y3 3 x1 (D)2y2+2y3 5 x2 y1,y2,y30 Max z=3x1+5x2+0 x3+0 x4+0 x5 s.t.x1 +x3 =4 (P)2x2 +x4 =12 3x1+2x2 +x5 =18 x1，x2，x3，x4，x5 0 Min w=4y1+12y2+18y3+0y4+0y5+My6+My7 s.t.y1 +3y3 -y4 +y6 =3 (D)2y2+2y3 -y5 +y7=5 y1,y2,y3,y4,y5,y6,y7 0 16/10717/66bj4121800MMibByBB-1Cy1
10、y2y3y4y5y6y7My63103-1010-My750220-1015/2w8M4-M 12-2M 18-2MMM00j对偶问题初始对偶问题初始单纯形表单纯形表My63103-10103/312y25/20110-1/201/2 5/2w3M+304-M06-3MM60M-6j3应当是应当是18-5M，但错算为，但错算为18-2M，所以误选，所以误选y2为换入变量。以下将为换入变量。以下将错就错算下去。错就错算下去。18/66bj4121800MMibByBB-1Cy1y2y3y4y5y6y718y311/301-1/301/3012y23/2-1/3101/3-1/2-1/31/2w3
11、620026M-2M-6j对偶问题最终对偶问题最终单纯形表单纯形表19/66bj4121800MMibByBB-1Cy1y2y3y4y5y6y7My63103-10101My750220-1015/2w8M4-M12-2M 18-5MMM00j重新算一遍，重新算一遍，对偶问题初始对偶问题初始单纯形表单纯形表18y311/301-1/301/30-My73-2/3202/3-1-2/313/2w2M/3-212-M0-2M/3+6M5M/3-60j20/66对偶问题最终对偶问题最终单纯形表单纯形表bj4121800MMibByBB-1Cy1y2y3y4y5y6y718y311/301-1/301
12、/3012y23/2-1/3101/3-1/2-1/31/2w3620026M-2M-6j计算结果同上。计算结果同上。21/66事项事项原问题变量原问题变量原问题松弛变量原问题松弛变量xBB-1bx1x2x3x4x5x320011/3-1/3x260101/20 x12100-1/31/3z36000-3/2-1变量变量对偶问题剩余变量对偶问题剩余变量对偶问题变量对偶问题变量y4y5y1y2y3(P)最终单纯形表最终单纯形表22/66事项事项对偶问题变量对偶问题变量对偶问题剩余变量对偶问题剩余变量bByBB-1Cy1y2y3y4y518y311/301-1/3012y23/2-1/3101/3
13、-1/2w36原问题松弛变量原问题松弛变量原问题变量原问题变量x3x4x5x1x2(D)对偶问题最终对偶问题最终单纯形表单纯形表23/107推论推论1(P)任一可行解目标函数值是任一可行解目标函数值是(D)目标函目标函数数值下界。反之，值下界。反之，(D)任一可行解目标函数值任一可行解目标函数值是是(P)目标函数目标函数值上界。值上界。推论推论2 若若(P)有可行解且目标函数值无界，则有可行解且目标函数值无界，则(D)无可行解；反之无可行解；反之，(D)有可行解且目标函数有可行解且目标函数无界，则无界，则(P)无无可行解。当可行解。当(D)无可行解时，无可行解时，(P)无无可行解或可行解或目标
14、函数值无目标函数值无界。界。推论推论3 若若(P)有可行解，而有可行解，而(D)无可行解，则无可行解，则(P)目标函数目标函数值无值无界；反之界；反之，(D)有可行解有可行解，而，而(P)无无可行解，则可行解，则(D)目标函数值目标函数值无无界。界。24/6625/1073.对偶定理。若对偶定理。若(P)和和(D)均有可行解，则均有最均有可行解，则均有最优解，且两者优解，且两者的目标函数值相等的目标函数值相等。证明证明:由于由于(P)和和(D)均有可行解均有可行解，根据弱对偶性推，根据弱对偶性推论论1，(P)目标函数值有上界，目标函数值有上界，(D)目标函数值目标函数值有有下下界，因此，界，因
15、此，(P)和和(D)都有最优解。另外，根据都有最优解。另外，根据ATYCT，Y0，w=YT Tb b=CBB-1b b=z知道，当知道，当(P)取取得最优解时，得最优解时，(D)有可行解，且有有可行解，且有w=z，根据性质，根据性质2（最优性），（最优性），(D)的可行解也是最优解，的可行解也是最优解，证证毕。毕。26/10727/10728/107第三节第三节 影子价格影子价格一、影子价格一、影子价格在例子在例子 Max z=3x1+5x2 s.t.x1 4 (P)2x2 12 3x1+2x2 18 x1，x2 0bT=(4,12,18)是资源，即可利用的设备台班量是资源，即可利用的设备台班
16、量。在讨论如何才能赢利最多时，没有考虑三种。在讨论如何才能赢利最多时，没有考虑三种设备单位台班的价格。它们的价格藏在深处。设备单位台班的价格。它们的价格藏在深处。29/6630/66有些经济学家有些经济学家认为认为，自由的市场交易，商品成交，自由的市场交易，商品成交价格能够反映其真正价值。但是，资源的现实市价格能够反映其真正价值。但是，资源的现实市场价格并不反映其场价格并不反映其“真正真正”价值。还有些价值。还有些经济学经济学家家认为，影子价格是原本无交易的资源，在转为认为，影子价格是原本无交易的资源，在转为其他用途时的价格，或者说，另外再增加一个单其他用途时的价格，或者说，另外再增加一个单位
17、此种资源需要付出的价格。这个问题可以利用位此种资源需要付出的价格。这个问题可以利用对偶问题的解给予某种解释。对偶问题的解给予某种解释。Min w=4y1+12y2+18y3 s.t.y1 +3y3 3 (D)2y2+2y3 5 y1,y2,y30其解是其解是(Y,Ys)T=(y1,y2,y3,y4,y5)=(0,3/2,1,0,0)31/66这就是说，三种设备每台时的价格分别是这就是说，三种设备每台时的价格分别是0,3/2和和1。第一种。第一种设备每台时的设备每台时的价格为价格为0，这是什么意，这是什么意思？思？请请看原问题看原问题 Max z=3x1+5x2+0 x3+0 x4+0 x5 s
18、.t.x1 +x3 =4 (P)2x2 +x4 =12 3x1+2x2 +x5 =18 x1，x2，x3，x4，x5 0其解是其解是(X,Xs)T=(x1,x2,x3,x4,x5)=(2,6,2,0,0)32/6633/107612x1x26449x1=42x2=123x1+2x2=18(2,6)z=3x1+5x2=36z=15oABCDEFG34/107612x1x26449x1=42x2=123x1+2x2=18(2,6)z=3x1+5x2=36z=15oABCDEFGx1=5z=36-36=035/107612x1x26449x1=42x2=123x1+2x2=18(5/3,6.5)z=
19、3x1+5x2=36z=15oABCDEFG2x2=13z=3x1+5x2=37.5z=37.5-36=1.536/107612x1x26449x1=42x2=123x1+2x2=18z=3x1+5x2=36z=15oABCDEFGz=3x1+5x2=373x1+2x2=19z=37-36=1第第四四节节 对偶单纯形法对偶单纯形法一、对偶单纯形法思路一、对偶单纯形法思路 Min w=bTY-0Ys (D)s.t.ATY-IYs=CT Y，Ys037/66二、对偶单纯形法计算步骤二、对偶单纯形法计算步骤Step1：找出初始可行基、：找出初始可行基、初始初始单纯形表和单纯形表和初始初始基解。基解。
20、Step2：若：若B-1b0，初始基初始基解是最优解，停。解是最优解，停。否则，下一步。否则，下一步。Step3：取：取(B-1b)l=min(B-1b)i|(B-1b)i0，第，第l行基行基变量换出。若所有的变量换出。若所有的alj0，无可行解，停。，无可行解，停。Step4：计算：计算k/alk=minj/alj|alj0，第，第k列非基列非基变量换入。变量换入。Step5：求基的逆矩阵、新基解和：求基的逆矩阵、新基解和z。回。回Step2。38/10739/66例例1 Min w=4x1+12x2+18x3 s.t.x1 +3x3 3 2x2 +2x3 5 x1，x2，x3 0将将其改写
21、如下：其改写如下：Max-w=-4x1-12x2-18x3+0 x4+0 x5 s.t.-x1 -3x3 +x4 =-3 -2x2 -2x3 +x5 =-5 x1，x2，x3，x4，x5 040/66cj-4-12-1800cBxBB-1bx1x2x3x4x50 x4-3-10-3100 x5-50-2-201zj/alj初始单纯形表初始单纯形表cj-4-12-1800icBxBB-1bx1x2x3x4x50 x4-3-10-3100 x5-50-2-201z-4/0-12/-2-18/-200j/alj先确定换出变量，再换入变量先确定换出变量，再换入变量41/66cj-4-12-1800ic
22、BxBB-1bx1x2x3x4x50 x4-3-10-310-12x25/20110-1/2zj/alj求求B-1cj-4-12-1800icBxBB-1bx1x2x3x4x50 x4-3-10-310-12x25/20110-1/25/2z-4/-1-6/-3-j/alj再确定换出变量和换再确定换出变量和换入变量，入变量，42/66cj-4-12-1800icBxBB-1bx1x2x3x4x5-18x311/301-1/30-12x23/2-1/3101/3-1/2z-36j/alj求求B-1cj-4-12-1800icBxBB-1bx1x2x3x4x5-18x311/301-1/30-12
23、x23/2-1/3101/3-1/2z-200-2-6j判断是否最优判断是否最优第第五五节节 灵敏度分析灵敏度分析问题的由来，先问题的由来，先看看一个方程一个方程 x1+x2=10 1.01x1+x2=11,x1=100,x2=-90如果如果1.01增加到增加到1.011，该方程解会如何变化？，该方程解会如何变化？x1+x2=10 1.011x1+x2=11,x1=1/0.011=90.91,x2=-80.91 a21/a21=0.001/1.01=0.1%,x1/x1=(90.91-100)/100=-9%,43/66再看另外一个方程再看另外一个方程 x1+x2=10 2.02x1+x2=1
24、1,x1=0.980,x2=9.020如果如果2.02增加到增加到2.022，该方程解会如何变化？，该方程解会如何变化？x1+x2=10 2.022x1+x2=11,x1=0.978,x2=9.022 a21/a21=0.002/2.02=0.1%,x1/x1=(0.978-0.980)/0.980=0.2%,这时候这时候，可以说可以说，第一个方程组的解对于，第一个方程组的解对于a21敏感，而敏感，而第一个第一个方程组则否。方程组则否。44/66 实际问题的数学模型，应当避免第一种情实际问题的数学模型，应当避免第一种情况，因为实际中很难避免将况，因为实际中很难避免将1.011算成算成1.01。
25、LP问题也会遇到类似情况。其中问题也会遇到类似情况。其中A、b和和C都是从实际中收集、归纳和整理的数字，很难都是从实际中收集、归纳和整理的数字，很难保证与实际情况丝毫不差。保证与实际情况丝毫不差。如果如果LP问题的解因为这些数字与实际稍有问题的解因为这些数字与实际稍有偏差就会相差很大，那就说明利用偏差就会相差很大，那就说明利用A、b、C构构造造的的LP问题模型不能用做实际问题的模型。问题模型不能用做实际问题的模型。合理的合理的 LP问题问题模型不应敏感于模型不应敏感于A、b或或C的的些小变化。本节课学习，当些小变化。本节课学习，当 A、b或或C发生小变发生小变动时，最优解将如何变化，看一看对这
26、些变化动时，最优解将如何变化，看一看对这些变化的敏感性。的敏感性。45/66灵敏度分析的步骤：灵敏度分析的步骤：1.先用最终单纯形表中先用最终单纯形表中B-1变换变换A、b和和C的增量的增量 b=B-1b，Pj=B-1Pj，2.检查检查(P)是否仍为可行解。是否仍为可行解。3.检查检查(D)是否是否仍为可行解仍为可行解。4.根据下表中各种情况决定下一步行动。根据下表中各种情况决定下一步行动。46/66(P)(D)结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解非可行解非可行解非可行解非可行解 可行解可行解 非可行解非可行解 可行解可行解 非可行解非可行解问题的最优解或最优解不变
27、问题的最优解或最优解不变用单纯形法继续迭代求最优解用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新单纯形表重引进人工变量，编制新单纯形表重新计算新计算例例设备台时设备台时/件产品件产品可用台时可用台时（千小时）（千小时）产品产品1产品产品2下料设备下料设备A104机加工设备机加工设备B0212焊接设备焊接设备C3218产品单价产品单价3元元/件件5元元/件件一、分析一、分析C的变化的变化问题问题1 若两种产品单价分别变成若两种产品单价分别变成5元元/件和件和3.25元元/件，件，两种两种产品最优产量是否变化？产品最优产量是否变化？问题问
28、题2 使最使最优优产量不变的第二种单价变化范围产量不变的第二种单价变化范围多大？多大？47/6648/66cj53.25000icBxBB-1bx1x2x3x4x50 x320011/3-1/363.25x260101/20125x12100-1/31/3-z29.500025/600-1j为了回答为了回答问题问题1，将两种产品改变后的单价填入，将两种产品改变后的单价填入最终单纯形表，并重新计算检验数，得到：最终单纯形表，并重新计算检验数，得到：0 x460031-13.25x2301-3/201/25x1410100z29.7500-0.1250-3.25/2j为了回答为了回答问题问题2，用
29、，用5+c2表示表示第二第二种种产品改变产品改变后后的单价，并填入的单价，并填入最终单纯形表，并重新计算最终单纯形表，并重新计算检验数，得到检验数，得到：c4=-3/2-c2/2，若使最优解不变，则须有，若使最优解不变，则须有c40-3/2-c2/20，c2-349/66cj35+c2000icBxBB-1bx1x2x3x4x50 x320011/3-1/35+c2x260101/203x12100-1/31/3z000-3/2-c2/2-1j若若回答回答使使最优产量不变的最优产量不变的第一种第一种产品产品单价变化范单价变化范围，则用围，则用3+c1表示第一种表示第一种产品改变后产品改变后的单
30、价，并的单价，并填入填入最终单纯形表，并重新计算检验最终单纯形表，并重新计算检验数：数：c4=-3/2+c1/3，c5=-1-c1/3，若使最优解不变，若使最优解不变，则须有则须有c40，c50，-3/2+c1/30，-1-c1/30，-3c19/250/66cj3+c15000icBxBB-1bx1x2x3x4x50 x320011/3-1/35x260101/203+c1x12100-1/31/3z36+2c1000-3/2+c1/3-1-c1/3j二二、分析、分析b的变化的变化若若b=(0,b2,0)T，问最优解是否改变，为此，先，问最优解是否改变，为此，先计算计算 b2/3 b=B-1
31、b=b2/2 -b2/3将将其添入最终单纯形表中其添入最终单纯形表中，得到，得到：51/6611/3-1/3001/20b20-1/31/3052/66cj35000icBxBB-1bx1x2x3x4x50 x32+b2/30011/3-1/35x26+b2/20101/203x12-b2/3100-1/31/3zj为使第二种设备可用台时改变后的解仍然可行，为使第二种设备可用台时改变后的解仍然可行，须有：须有：2+b2/30，6+b2/20，2-b2/30，max-6,-12b2min 6,-6b26，对于对于b1和和b3，同样，同样处理。处理。三、分析增添新变量三、分析增添新变量xj的情况的
32、情况如果如果增加新产品增加新产品x6，单价为，单价为4元，问如何生产，总元，问如何生产，总收入最多。设收入最多。设其所需三种设备台时其所需三种设备台时为为 2 5/3 P6=0 ，变换，得，变换，得P6 =0 1 1/3 将将P6 填入填入最终单纯形表，并重新计算检验最终单纯形表，并重新计算检验数：数：53/6611/3-1/32 01/2000-1/31/314x61.2000.61/5-0.215x260101/2003x11.610-0.2-0.40.40z39.600-1.8-2.1-0.40j54/66cj350004icBxBB-1bx1x2x3x4x5x60 x320011/3-
33、1/35/36/55x260101/200-3x12100-1/31/31/36z36000-3/2-13j四四、分析技术系数、分析技术系数aij变化时的情况变化时的情况如果如果aij对应的对应的xj是非基变量，处理办法同是非基变量，处理办法同“三三”。如果如果xj是基变量，先变换是基变量，先变换Pj，Pj =B-1Pj 例例11第二种产品用设备台时由第二种产品用设备台时由 0 改为改为 0 2 P2=2 2 3/2 单价由单价由5元增加为元增加为5.5元元/件，用件，用x*2表示这种表示这种“新新”产品产量，先变换产品产量，先变换P2如下，然后添入最终如下，然后添入最终单纯形单纯形表，并重新
34、计算检验表，并重新计算检验数：数：55/66 1/6 P2 =1 -1/656/6611/3-1/30 01/2020-1/31/33/2cj355.5000icBxBB-1bx1x2x*2x3x4x50 x32001/611/3-1/3125x2601101/2063x1210-1/60-1/31/3-z360010-3/2-1j检验数均已非正检验数均已非正，说明已经得到最优解说明已经得到最优解，销售，销售收入增加了收入增加了(42-36)/36=16.7%。57/66cj355.5000icBxBB-1bx1x2x*2x3x4x50 x310-1/6011/4-1/35.5x*260110
35、1/203x1311/600-1/41/3z42000-2-1j如果第二种产品用设备台时由如果第二种产品用设备台时由 0 改为改为 1/2 2 P2=2 2 1/2 单价由单价由5元增为元增为5.5元，用元，用x*2表示这种表示这种“新新”产品产品产量，先变换产量，先变换P2如下，然后添入最终如下，然后添入最终单纯形表，单纯形表，并重新计算检验并重新计算检验数：数：58/66 1 P2 =1 -1/259/6611/3-1/31/2 01/2020-1/31/31/2cj355.5000icBxBB-1bx1x2x*2x3x4x50 x3200111/3-1/325x2601101/2063x
36、1210-1/20-1/31/3-z360020-3/2-1j需要需要将将x2排除在外，排除在外，办法是将其视为人工变量。办法是将其视为人工变量。60/66cj355.5000icBxBB-1bx1x2x*2x3x4x55.5x*2200111/3-1/35x24010-11/61/33x131001/2-1/61/6z000-2-13/6-1/3j61/66cj3-M 5.5000icBxBB-1bx1x2x*2x3x4x55.5x*2200111/3-1/3-Mx24010-11/61/3123x131001/2-1/61/618z000-M-7 M/6-4/3 M/3+4/3j5.5x*
37、260-101/200 x5120-0-31/213x111-01-1/40z360-0-3-20j可可将将X*=(x1,x2,x3,x4,x5)T=(1,6,0,0,12)T代入代入修改修改P2后后的原问题检查。的原问题检查。Max z=3x1+5.5x2s.t.x1+x2/2 4 2x2 12 3x1+x2/2 18 x1，x2 0不难发现不难发现，第一和第二种设备得到了充分利用，第一和第二种设备得到了充分利用，但第三种设备有，但第三种设备有12,000个台时空闲。个台时空闲。62/66五、增加五、增加约束条件约束条件现在现在，为了提高产品性能，需利用第四种设备，为了提高产品性能，需利用第
38、四种设备。两种两种产品需要的台时都是两个单位，这种设产品需要的台时都是两个单位，这种设备可用台时是备可用台时是14,000个。于是，原问题变成，个。于是，原问题变成，Max z=3x1+5x2s.t.x1+4 2x2 12 3x1+2x2 18 2x1+2x2 14 x1，x2 063/66先先将将P1,P2将将变换成单位列向量变换成单位列向量。第第4行行-2第第2行行-2第第3行行 -2 0 0 0 -1/3 -2/3 164/66cj350000icBxBB-1bx1x2x3x4x5x60 x320011/3-1/305x260101/2003x12100-1/31/300 x614220
39、001zj 4=-3/2 -1=5这是非可行解，用对偶单纯形法求解，先确定换这是非可行解，用对偶单纯形法求解，先确定换出变量，再确定换入变量。出变量，再确定换入变量。x6换出换出，x5换换入。入。65/66cj350000icBxBB-1bx1x2x3x4x5x60 x320011/3-1/305x260101/2003x12100-1/31/300 x6-2000-1/3-2/31z000-1.5-10jj/a4j-4.51.5-66/66cj350000icBxBB-1bx1x2x3x4x5x60 x330011/20-0.55x260101/2003x11100-1/200.50 x530001/21-1.5z33000-10-1.5j这是最优解。这是最优解。X*=(x1,x2,x3,x4,x5,x6)T=(1,6,3,0,3,0)T第一和第三种设备未得到充分利用。第一和第三种设备未得到充分利用。z*=33。
