第二章 线性规划的对偶理论和灵敏度分析

1、产品数据表产品数据表问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？最大利润？ 0,124164821222.32max2121212121xxxxxxxxtsxxz设设A A、B B、CC、D D设备的机时价分别为设备的机时价分别为y y1 1、y y2 2、y y3 3、y y4 4，在市场竞争的时代，厂长的最佳决策显然应符合两条：在市场竞争的时代，厂长的最佳决策显然应符合两条： （1 1）不吃亏原则。即机时定价所赚利润不能低于加工甲、）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则

2、，便构成了新规划的不等式乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。约束条件。 （2 2）竞争性原则。即在上述不吃亏原则下，尽量降低机）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。时总收费，以便争取更多用户。设设A A、B B、CC、D D设备的机时价分别为设备的机时价分别为y y1 1、y y2 2、y y3 3、y y4 4，0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy),.,1(0),.,1(.max11njxmibxatsxczjnjijijnjjj),.,1(0),.,1(

3、. .min11miynjcyatsybwimijiijmiii 0,124164821222.32max2121212121xxxxxxxxtsxxz 0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy0121681240042122. .32max212121xxxxtsxxz03240220412. .1216812min432143214321yyyyyyyytsyyyyz0A.CXmaxXbXtsz0. .minYCYAtsYbw原问题原问题对偶问题对偶问题0121681240042122. .32max212121xxx

4、xtsxxz03240220412.1216812min432143214321yyyyyyyytsyyyyz原问题原问题对偶问题对偶问题0121681240042122. .32max212121xxxxtsxxz03240220412.1216812min432143214321yyyyyyyytsyyyyz原问题原问题对偶问题对偶问题0121681240042122. .32max212121xxxxtsxxz03240220412.1216812min432143214321yyyyyyyytsyyyyz以上是依据经济问题推导出对偶问题，还可以用代数方以上是依据经济问题推导出对偶问题，

5、还可以用代数方法推导出对偶问题。法推导出对偶问题。原问题和对偶问题是互为对偶的两个线性规划问题，已原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可写出另一个问题。知一个问题就可写出另一个问题。上面两种形式的线性规划称为规范形式。上面两种形式的线性规划称为规范形式。规范形式（规范形式（Canonical FormCanonical Form）的定义：）的定义：目标函数求极大值时，所有约束条件为目标函数求极大值时，所有约束条件为号，号，变量变量非负；非负；目标函数求极小值时，所有约束条件为目标函数求极小值时，所有约束条件为号，号，变量变量非负。非负。规范形式的线性规划的对偶问题亦是规

6、范形式。规范形式的线性规划的对偶问题亦是规范形式。0) 1 . 2(maxXbAXCXZ0)2 . 2(wminYCYAbY练习：写出下列线性规划的对偶问题练习：写出下列线性规划的对偶问题0,15744325min321321321321xxxxxxxxxxxxZ【解】这是一个规范形式的线性【解】这是一个规范形式的线性规划，设规划，设Y Y= =（y y1 1，y y2 2），则有），则有0,15744325min321321321321xxxxxxxxxxxxZ0, 03527544max2121212121yyyyyyyyyyZ练习：写出下列线性规划的对偶问题练习：写出下列线性规划的对偶问

7、题0, 01038576534max2121212121xxxxxxxxxxZ【解】这是一个规范形式的线性规划，它的对偶问题求【解】这是一个规范形式的线性规划，它的对偶问题求最小值，有三个变量且非负，有两个最小值，有三个变量且非负，有两个“ “ ”约束，即约束，即3 , 2 , 1, 03324751086min321321321iyyyyyyyyyywi若给出的线性规划不是规范形式，可以先化成规范形式若给出的线性规划不是规范形式，可以先化成规范形式再写对偶问题。再写对偶问题。0, 030351546324624. .347min32132321321321xxxxxxxxxxxtsxxxz取

8、值无约束，的形式的形式0, 030351546324624. .347min32132321321321xxxxxxxxxxxtsxxxz取值无约束，0,3035530355154663246224. .3447min,3 2213 223 223 2213 2213 221 22211xxxxxxxxxxxxxxxxxxtsxxxxzxxxxx令针对决策变量进行针对决策变量进行的处理的处理针对约束方程为针对约束方程为等式进行的处理等式进行的处理针对约束方程为针对约束方程为进行的处理进行的处理0,333464556245562734. .30301524-max 3321 3321 3321

9、332121 3321yyyyyyyyyyyyyyyyyytsyyyyw0,3035530355154663246224. .3447min3 2213 223 223 2213 2213 221xxxxxxxxxxxxxxxxxxtsxxxxz 3321,yyyy令0, 030351546324624. .347min32132321321321xxxxxxxxxxxtsxxxz取值无约束，无约束32132132121321, 0, 033464562734. .301524maxyyyyyyyyyyytsyyyw 33311,yyyyy令0,333464556245562734. .303

10、01524-max 3321 3321 3321 332121 3321yyyyyyyyyyyyyyyyyytsyyyyw0, 030351546324624. .347min32132321321321xxxxxxxxxxxtsxxxz取值无约束，非规范形式可能出现下列三种情形。（设原问题是非规范形式可能出现下列三种情形。（设原问题是求最大值）求最大值）(1)(1)第第i i个约束是个约束是约束，可直接判断出第约束，可直接判断出第i i个个对偶变量是对偶变量是0 0，且系数仍是原问题对应的系，且系数仍是原问题对应的系数。数。0, 030351546324624. .347min3213232

11、1321321xxxxxxxxxxxtsxxxz取值无约束，无约束32132132121321, 0, 033464562734. .301524maxyyyyyyyyyyytsyyyw非规范形式可能出现下列三种情形。（设原问题非规范形式可能出现下列三种情形。（设原问题是求最大值）是求最大值）(2)(2)第第i i个约束是个约束是 = =约束，对应的第约束，对应的第i i个对偶变个对偶变量无符号约束；量无符号约束；0, 030351546324624. .347min32132321321321xxxxxxxxxxxtsxxxz取值无约束，无约束32132132121321, 0, 03346

12、4562734. .301524maxyyyyyyyyyyytsyyyw非规范形式可能出现下列三种情形。（设原问题是非规范形式可能出现下列三种情形。（设原问题是求最大值）求最大值）(3)(3)当当xjxj 0 0，第，第j j个对偶约束为个对偶约束为约束约束, ,当当xjxj无约束时，第无约束时，第j j个对偶约束为个对偶约束为 = =约束。约束。0, 030351546324624. .347min32132321321321xxxxxxxxxxxtsxxxz取值无约束，无约束32132132121321, 0, 033464562734. .301524maxyyyyyyyyyyytsyy

13、yw假设原问题是求最小值，可以得出下列结论假设原问题是求最小值，可以得出下列结论(1)(1)第第i i个约束是个约束是约束，可直接判断出第约束，可直接判断出第i i个对个对偶变量是偶变量是0 0。( (与原问题是求最大值不同与原问题是求最大值不同) )0, 030351546324624. .347min32132321321321xxxxxxxxxxxtsxxxz取值无约束，无约束32132132121321, 0, 033464562734. .301524maxyyyyyyyyyyytsyyyw假设原问题是求最小值，可以得出下列结论假设原问题是求最小值，可以得出下列结论(2)(2)第第i

14、 i个约束是个约束是 = =约束，对应的第约束，对应的第i i个对偶变个对偶变量无符号约束；量无符号约束；( (与原问题是最大值的情形相同与原问题是最大值的情形相同) )0, 030351546324624. .347min32132321321321xxxxxxxxxxxtsxxxz取值无约束，无约束32132132121321, 0, 033464562734. .301524maxyyyyyyyyyyytsyyyw假设原问题是求最小值，可以得出下列结论假设原问题是求最小值，可以得出下列结论(3)(3)当当xjxj 0 0，第，第j j个对偶约束为个对偶约束为约束约束, ,当当xjxj无无

15、约束时，第约束时，第j j个对偶约束为个对偶约束为 = =约束。约束。（与原问题是求最大值不同）（与原问题是求最大值不同）0, 030351546324624. .347min32132321321321xxxxxxxxxxxtsxxxz取值无约束，无约束32132132121321, 0, 033464562734. .301524maxyyyyyyyyyyytsyyyw例例2-3 2-3 写出下列线性规划的对偶问题写出下列线性规划的对偶问题 0, 0,1482105618827945min43213214243214321xxxxxxxxxxxxxxxxxZ无约束【解】目标函数求最小值，应

16、【解】目标函数求最小值，应将上页表的右边看作原问题，将上页表的右边看作原问题，左边是对偶问题，原问题有左边是对偶问题，原问题有3 3个约束个约束4 4个变量，则对偶问题个变量，则对偶问题有有3 3 个变量个变量4 4个约束，对偶问个约束，对偶问题为：题为：123131231312max1810147226885wyyyyyyyyyyyy=1549y10， y20，y3无约束0,44222326zmax32131321321xxxxxxxxxxx0,34226242ywmin212122121yyyyyyyy0,5643732532422zmin321321321321321xxxxxxxxxx

17、xxxxx0, 04675243232532yaxz321321321321321yyyyyyyyyyyyyym无约束43214321432143214321, 0, 0,20999128537653432axzxxxxxxxxxxxxxxxxxxxxm0, 0,4953-39-3-29-71126-2085ywi321321321321321321yyyyyyyyyyyyyyyyynm无约束0maxXbAXCXZ对偶问题是（记为对偶问题是（记为DPDP）：）：0minYCYAYbw【性质【性质1 1】 对称性对称性 对偶问题的对偶是原问题。对偶问题的对偶是原问题。 设原问题是（记为设原问题是

18、（记为LPLP）：）： 【性质【性质2 2】 弱对偶性弱对偶性 设设X X、Y Y分别为分别为LP(maxLP(max) )与与DP(minDP(min) )的的可行解可行解，则，则 性质说明了两个线性规划互为对偶时，求最大值的线性规划性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都的任意目标值都不会大于不会大于求最小值的线性规划的任一目标值。求最小值的线性规划的任一目标值。0maxXbAXCXZ对偶问题是（记为对偶问题是（记为DPDP）：）：0minYCYAYbw设原问题是（记为设原问题是（记为LPLP）：）： njmiiijjbyxcbYCX1100即即：由这个【性质由这

19、个【性质2 2】可得到下面几个结论：】可得到下面几个结论： (1)LP(1)LP的任一可行解的目标值是的任一可行解的目标值是DPDP的最优值下界；的最优值下界；DPDP的任一的任一可行解的目标是可行解的目标是LPLP的最优值的上界；的最优值的上界；(2)(2)在互为对偶的两个问题中，若一个问题可行且具有无界在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；解，则另一个问题无可行解；(3)(3)若原问题可行且另一个问题不可行，则原问题具有无界解。若原问题可行且另一个问题不可行，则原问题具有无界解。 例如：例如：0,22212min21212121xxxxxxxxz无可行解

20、，而对偶问题无可行解，而对偶问题0,221122max21212121yyyyyyyyw由结论（由结论（3 3）知该对偶问题必有无界解。）知该对偶问题必有无界解。有可行解有可行解(3)(3)若原问题可行且另一个问题不可行，则原问题具有无界解。若原问题可行且另一个问题不可行，则原问题具有无界解。0,1120,242minmax:2121212121212121yyyyyyxxxxxxyyxxzDPLP0,242212121xxxxxxy1y20112212121y,yyyyy例例2-4 2-4 证明下列线性规划无最优解：证明下列线性规划无最优解：3 , 2 , 1, 0324min3213132

21、1jxxxxxxxxxZj【证】容易看出【证】容易看出X X= =（4 4，0 0，0 0）是）是一可行解，故问题可行。对偶问题一可行解，故问题可行。对偶问题0, 0121134max212122121yyyyyyyyyw将三个约束的两端分别相加得将三个约束的两端分别相加得而第二个约束有而第二个约束有y y2 211，矛盾，故对，矛盾，故对偶问题无可行解，因而原问题具有无偶问题无可行解，因而原问题具有无界解，即无最优解。界解，即无最优解。 212y依据：由性质依据：由性质2 2得结论：若原问题可行且另一个问题得结论：若原问题可行且另一个问题不可行，则原问题具有无界解。不可行，则原问题具有无界解

22、。 【性质【性质3 3】最优性】最优性 设设X X0 0与与Y Y0 0分别是分别是LPLP与与DPDP的可行解，则当的可行解，则当X X0 0、Y Y0 0是是LPLP与与DPDP的的最优解最优解当且仅当当且仅当C XC X0 0 = = Y Y0 0b b【性质【性质4 4】强对偶性】强对偶性 若互为对偶的两个问题其中一个有最若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。优解，则另一个也有最优解，且最优值相同。 即即 max z=min wmax z=min w另一结论另一结论：若：若LPLP与与DPDP都有可行解，则两者都有最优解；都有可行解，则两者都有最优解；

23、若一个问题无最优解，则另一问题也无最优解。若一个问题无最优解，则另一问题也无最优解。【性质【性质5 5】互补松弛定理】互补松弛定理 设设X X* *、Y Y* *分别为分别为LPLP与与DPDP的可行解，的可行解，X XS S和和Y YS S是它的松弛变量的可行解，则是它的松弛变量的可行解，则X X* *和和Y Y* *是最优解是最优解当且仅当且仅当当YS X*=0和和Y*XS=0【性质【性质5 5】告诉我们已知一个问题的最优解时求另一个问题】告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知的最优解的方法，即已知Y Y* *求求X X* *或已知或已知X X* *求求Y Y*

24、*。Y Y * * X XS S=0=0和和Y YS S X X * * =0=0两式称为互补松弛条件。两式称为互补松弛条件。Y Y * * X XS S=0=0和和Y YS S X X * * =0=0将互补松弛条件写成下式将互补松弛条件写成下式*1*100ijmiSinSjjy xy x由于变量都非负，要使求和式等于零，则必定每一分由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：量为零，因而有下列关系：00, 002*jjSjjSyxxy时反之当时，）（00, 001*iSSiyxxyii时反之当时，）（利用上述关系，建立对偶问题（或原问题）的约束线利用上述关系，建立

25、对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。性方程组，方程组的解即为最优解。例例2-5 2-5 已知线性规划已知线性规划3 , 2 , 1, 0162210243max321321321jxxxxxxxxxxzj的最优解是的最优解是 求对偶问题的最优解。求对偶问题的最优解。TX)0 , 2 , 6(例例2-52-5【解】对偶问题是【解】对偶问题是0,1422321610min2121212121yyyyyyyyyyw因为因为X X1 100，X X2 200，所以对偶问，所以对偶问题的第一、二个约束的松弛变量题的第一、二个约束的松弛变量等于零，即等于零，即422322121yy

26、yy解此线性方程组得解此线性方程组得y y1 1=1,=1,y y2 2=1,=1,从而对偶问题的最优解从而对偶问题的最优解为为Y Y= =（1 1，1 1），最优值），最优值w w=26=26。例例2-6 2-6 已知线性规划已知线性规划 无约束321321321321, 0, 06422minxxxxxxxxxxxxz的对偶问题的最优解为的对偶问题的最优解为Y Y= =（0 0，-2-2），求原问题的最优），求原问题的最优解。解。【解】对偶问题是【解】对偶问题是021264max2121212121yyyyyyyyyyw无约，解方程组得：解方程组得：x x 1 1= =5,5,x x 3

27、3= =1, 1, 所以原问题的最优解为所以原问题的最优解为X X= =（5 5，0 0，1 1），最优值），最优值Z=Z=1212。643131xxxx因为因为y y2 200，所以原问题第二个松弛变量，所以原问题第二个松弛变量 =0=0，则，则y y1 1=0=0、y y2 2=-2=-2知，松弛变量知，松弛变量 故故x x2 2=0=0，则原问题的约束条件为线性方程组：，则原问题的约束条件为线性方程组： , 1, 021SSyy2SxDPDP的最优解是（的最优解是（0 0，-2-2）(1)(1)当当y yi i* *00时，时， , , 反之当反之当 时时y yi i* *=0=0；0i

28、Sx0iSx*(2)00,00jjSjjSyxxy时反之当时无约束321321321321, 0, 06422minxxxxxxxxxxxxz021264max2121212121yyyyyyyyyyw无约，DPDPLPLP4,.,1, 01222282. .652max43214314321jxxxxxxxxtsxxxxzj【性质【性质6 6】LP(maxLP(max) )的检验数的相反数对应于的检验数的相反数对应于DP(minDP(min) )的一组的一组基本解。基本解。)5,.,2 , 1(01551641222. .00032max524132154321jxxxxxxxxtsxxxx

29、xzj)5,.,2 , 1(0352242. .00151612ax53142154321iyyyyyyytsyyyyywmiLPLPDPDP注意：这里注意：这里做了处理做了处理)2 , 1(01551641222. .32max212121jxxxxxtsxxzj)3 , 2 , 1(0352242. .151612min3121321jyyyxytsyyywjy4y4y5y5y1y1y2y2y3y3x3x3x4x4x5x5x1x1x2x2原问题的松弛变量对应对偶问题的变量；原问题的松弛变量对应对偶问题的变量；对偶问题的剩余变量对应原问题的变量；对偶问题的剩余变量对应原问题的变量；y4y4y

30、5y5y1y1y2y2y3y3x3x3x4x4x5x5x1x1x2x2这些相互对应的变量如果在一个问这些相互对应的变量如果在一个问题的解中是基变量，那么在另一个题的解中是基变量，那么在另一个问题的解中是非基变量；问题的解中是非基变量；这些相互对应的变量如果在一个问这些相互对应的变量如果在一个问题的解中是基变量，那么在另一个题的解中是基变量，那么在另一个问题的解中是非基变量；问题的解中是非基变量；y4y4y5y5y1y1y2y2y3y3x3x3x4x4x5x5x1x1x2x2LP(maxLP(max) )的检验数的相反数对应于的检验数的相反数对应于DP(minDP(min) )的一组基本解。的一

31、组基本解。LP(maxLP(max) )的检验数的相反数对应于的检验数的相反数对应于DP(minDP(min) )的一组基本解。的一组基本解。例例2-8 2-8 线性规划线性规划0,4422226max32131321321xxxxxxxxxxxz（1 1）用单纯形法求最优解；）用单纯形法求最优解；（2 2）写出每步迭代对应对偶问题的基本解；）写出每步迭代对应对偶问题的基本解；（3 3）从最优表中写出对偶问题的最优解；）从最优表中写出对偶问题的最优解；【解】（【解】（1 1）加入松弛变量）加入松弛变量x x4 4、x x5 5后，单纯形迭代如：后，单纯形迭代如：X XB Bx x1 1x x2

32、 2x x3 3x x4 4x x5 5b b表表（1 1）x x4 4x x5 5221 11 10 02 24 41 10 00 01 1224 4j j662 21 10 00 0表表（2 2）x x1 1x x5 51 10 01/21/21/21/21 13 31/21/21/21/20 01 11 133j j0 0115 53 30 0表表（3 3）x x1 1x x2 21 10 00 01 14 46 60 01 11 12 24 46 6j j0 00 011112 22 20,4422226max543215314321321xxxxxxxxxxxxxxxz最优解最优解X

33、 X= =（4 4，6 6，0 0）T T，最优值最优值Z Z=6=64 42 26=126=12；（2 2）设对偶变量为）设对偶变量为y y1 1、y y2 2, ,松弛变量为松弛变量为y y3 3、y y4 4、y y5 5, ,Y Y= =（y y1 1，y y2 2，y y3 3，y y4 4，y y5 5），由性质），由性质6 6得到对偶问题的基本得到对偶问题的基本解解（y y1 1，y y2 2，y y3 3，y y4 4，y y5 5） = =（4 4，5 5，1 1，2 2，3 3），），即即表（表（1 1）中）中=（6 6，2 2，1 1，0 0，0 0），）， 则则Y Y（

34、1 1）= =（0 0，0 0，-6-6，2 2，1 1） 表（表（2 2）中）中=（0 0，1 1，5 5，3 3，0 0），）， 则则Y Y（2 2）= =（3 3，0 0，0 0，1 1，5 5）表（表（3 3）中）中=（0 0，0 0，1111，2 2，2 2），）， 则则Y Y（3 3）= =（2 2，2 2，0 0，0 0，1111）（3 3）因为表（）因为表（3 3）为最优解，故）为最优解，故 Y Y（3 3）= =（2 2，2 2，0 0，0 0，1111）为对偶问题最优解；）为对偶问题最优解；总结：我们学了六个对偶性质；这些性质是研究原问题总结：我们学了六个对偶性质；这些性质

35、是研究原问题与对偶问题解的对应关系；用下表来帮助我们了解这些与对偶问题解的对应关系；用下表来帮助我们了解这些性质。性质。1 1）任何线性规划都存在一个对应的对偶线性规划）任何线性规划都存在一个对应的对偶线性规划. .2 2）原问题第）原问题第ii个约束是个约束是“”约束，则对偶变量约束，则对偶变量y yii0.0.3 3）互为对偶问题，或者同时都有最优解，或者同时都无最优解）互为对偶问题，或者同时都有最优解，或者同时都无最优解. .4 4）对偶问题有可行解，则原问题也有可行解）对偶问题有可行解，则原问题也有可行解. .5 5）对偶问题有可行解，原问题无可行解，则对偶问题具有无界解）对偶问题有可

36、行解，原问题无可行解，则对偶问题具有无界解. .6 6）原问题无最优解，则对偶问题无可行解）原问题无最优解，则对偶问题无可行解. .7 7）对偶问题不可行，原问题可能无界解）对偶问题不可行，原问题可能无界解. .8 8）原问题与对偶问题都可行，则都有最优解）原问题与对偶问题都可行，则都有最优解. .9 9）原问题具有无界解，则对偶问题不可行）原问题具有无界解，则对偶问题不可行. .1010）对偶问题具有无界解，则原问题无最优解）对偶问题具有无界解，则原问题无最优解. .1111）若）若X X* *、Y Y* *是原问题与对偶问题的最优解，则是原问题与对偶问题的最优解，则X X* *= =Y Y

37、* *. .讨论对称形式：讨论对称形式：LP问题问题max z = cx s.t. Ax b x 0DP问题问题min w = yb s.t. yA c y 0 已知当已知当LPLP问问题求得最优解题求得最优解x x* *时，时，其其DPDP问题也得到问题也得到最优解最优解y y* *，且有，且有 b bi i 代表第代表第i i种资源的拥有量；对偶变量种资源的拥有量；对偶变量y yi i* *的意义的意义代表在资源最优利用条件下对单位第代表在资源最优利用条件下对单位第i i 种资源的估价。种资源的估价。这种估价不是资源的市场价格，而是这种估价不是资源的市场价格，而是根据资源在生产中根据资源在

38、生产中作出的贡献而作的估价作出的贡献而作的估价。 影子价格影子价格( (shadow priceshadow price) )*11nmjjiijizc xb yw(1)由于由于*iizyb边际价格边际价格例如：例如： 资源的合理利用问题资源的合理利用问题max z = 5x1+4x2 s.t. x1+3x2 90 2x1+ x2 80LP x1+ x2 45 x1，x2 0min w = 90y1+80y2+45y3 s.t. y1+ 2y2+ y3 5 DP 3y1+ y2+ y3 4 y1，y2，y3 0c x1 x2 x3 x4 x55 4 0 0 00 0 0 -1 -3b-215c

39、BxBx3 x1 x20 5 4 检验数 0 0 1 2 -5 1 0 0 1 -1 0 1 0 -1 225 35 10 x*= ( 35，10，25，0，0 )Tz*= 215y*=(0，1，3，0，0)w*=215第二种资源的影子价格为第二种资源的影子价格为y y2=12=1，第三种资源的影子价，第三种资源的影子价格为格为y y3=33=3，即当第二种资源增加一个单位时，即当第二种资源增加一个单位时，Z Z增加增加1 1个单位，当第三种资源增加一个单位时，个单位，当第三种资源增加一个单位时，Z Z增加增加3 3个单个单位。位。 y1=0y1=0说明增加第一种资源不会增加利润，因为第说明增

40、加第一种资源不会增加利润，因为第一种资源还没有用完。一种资源还没有用完。2 2、影子价格在经营管理中的应用、影子价格在经营管理中的应用（1 1）调节生产规模。）调节生产规模。资源的影子价格实际上是一种机会成本。若第资源的影子价格实际上是一种机会成本。若第i i 种种资源的单位市场价格为资源的单位市场价格为mi mi ，当，当yi yi mi mi 时，企业愿时，企业愿意购进这种资源（扩大生产规模），单位纯利为意购进这种资源（扩大生产规模），单位纯利为yi yimi mi ，则有利可图；如果，则有利可图；如果yi yi mi mi ，则企业有偿转，则企业有偿转让这种资源（缩小生产规模），可获单位

41、纯利让这种资源（缩小生产规模），可获单位纯利mimiyi yi ，否则，企业无利可图，甚至亏损。，否则，企业无利可图，甚至亏损。2 2、影子价格在经营管理中的应用、影子价格在经营管理中的应用（2 2）生产要素对产出贡献的分解。）生产要素对产出贡献的分解。通过影子价格分析每种资源获得多少产出例如，通过影子价格分析每种资源获得多少产出例如，企业获得企业获得100100万元的利润，生产过程中产品的直接万元的利润，生产过程中产品的直接消耗的资源有材料消耗的资源有材料A A、材料、材料B B、设备和工时，这些、设备和工时，这些资源各产生多少利润，由影子价格可以大致估计资源各产生多少利润，由影子价格可以大

42、致估计出来。出来。例如：例如：y y* *=(0=(0，1 1，3 3，0 0，0)0) 资源中应重点要考虑第资源中应重点要考虑第三种资源；三种资源；2 2、影子价格在经营管理中的应用、影子价格在经营管理中的应用（3 3）由性质）由性质5 5 互补松弛性知，第互补松弛性知，第i i个松弛变量大个松弛变量大于零时第于零时第i i个对偶变量等于零，并不能说明该资源个对偶变量等于零，并不能说明该资源在生产过程中没有作出贡献，只能理解为在生产过程中没有作出贡献，只能理解为第第i i种资种资源有剩余时再增加该资源量不能给企业带来利润源有剩余时再增加该资源量不能给企业带来利润或产值的增加。或产值的增加。例

43、如：例如：y y* *=(0=(0，1 1，3 3，0 0，0)0) 第一种资源影子价格为第一种资源影子价格为零，表示资源有剩余，增加购买不能转换为利润。零，表示资源有剩余，增加购买不能转换为利润。例如：原问题的最优解例如：原问题的最优解X X（24.2424.24，0 0，46.9646.96）对偶问题的最优解对偶问题的最优解Y Y（10.610.6，0.910.91，0 0，0 0）最优值最优值z=w=5712.12z=w=5712.12分析分析：1. y1. y1 1=10.6=10.6说明在现有的资源限量的条件下，增加一说明在现有的资源限量的条件下，增加一个单位第一种资源可以给企业带来

44、个单位第一种资源可以给企业带来10.610.6元的利润；如果元的利润；如果要出售该资源，其价格至少在成本价上加要出售该资源，其价格至少在成本价上加10.610.6元。元。2. y2. y3 3=0=0说明增加第三种资源不会增加利润，因为第三说明增加第三种资源不会增加利润，因为第三种资源还种资源还 没有用完。没有用完。2 2、影子价格在经营管理中的应用、影子价格在经营管理中的应用（ 4 4）影子价格是企业生产过程中资源的一种隐含）影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，与市场价格是的潜在价值，表明单位资源的贡献，与市场价格是不同的两个概念。同一种资源在不同的企业、生

45、产不同的两个概念。同一种资源在不同的企业、生产不同的产品或在不同时期影子价格都不一样。不同的产品或在不同时期影子价格都不一样。例如，某种钢板市场价格是每吨例如，某种钢板市场价格是每吨80008000元，一个企业元，一个企业用来生产汽车，另一个企业用来生产空调外壳，每用来生产汽车，另一个企业用来生产空调外壳，每吨钢板的产值是不一样的吨钢板的产值是不一样的2 2、影子价格在经营管理中的应用、影子价格在经营管理中的应用（5 5）影子价格是一个变量。）影子价格是一个变量。由由 的含义知影子价格是一种的含义知影子价格是一种边际产出边际产出，与与bibi的基数有关，在最优基的基数有关，在最优基B B不变的

46、条件下不变的条件下yiyi不变，不变，当某种资源增加或减少后，最优基当某种资源增加或减少后，最优基B B可能发生了变可能发生了变化，这时化，这时yiyi的值也随之发生变化的值也随之发生变化iibZy对偶单纯形法是求解线性规划的另一的基本方法。对偶单纯形法是求解线性规划的另一的基本方法。它是根据对偶原理和单纯形法的原理而设计出来的，它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。因此称为对偶单纯形法。由对偶的基本性质可以知道，用单纯形表求解线性由对偶的基本性质可以知道，用单纯形表求解线性规划问题时，在得到原问题的一个基可行解的同时，规划问题时，在得到原问题的一个基可行解的同时

47、，在检验数行得到对偶问题的一个基解，并且将两个在检验数行得到对偶问题的一个基解，并且将两个解分别代入各自的目标函数时，其值相等。解分别代入各自的目标函数时，其值相等。 考察如下的考察如下的 LP LP 问题及其对偶问题问题及其对偶问题 max z = cxLP s.t. Ax = b x 0 x1x2xmxB -z(0) 0 0 0检验数检验数b1b2bm 1 0 0 a1m+1 a1m+2 a1n 0 1 0 a2m+1 a2m+2 a2n 0 0 1 amm+1 amm+2 amnc1c2cmb x1 x2 xm xm+1 xm+2 xncB c1 c2 cm cm+1 cm+2 cn c

48、1m2mn单纯形法计算的基本思想是：保持原问题为可行解的单纯形法计算的基本思想是：保持原问题为可行解的基础上，通过迭代，增大目标函数，当其对偶问题也基础上，通过迭代，增大目标函数，当其对偶问题也是可行解的时候，就达到了目标函数的最优值。是可行解的时候，就达到了目标函数的最优值。单纯形表中单纯形表中b b的取值为正数的取值为正数所有的检验数都是负数的时候，所有的检验数都是负数的时候，其对偶问题也是可行解了！其对偶问题也是可行解了！对偶问题为可行解对偶问题为可行解所有的检验数都小于零所有的检验数都小于零原问题也可行解时原问题也可行解时单纯形表中的基解都大于零的时候单纯形表中的基解都大于零的时候(1

49、)(1)将线性规划的约束化为等式，求出一组基本解，将线性规划的约束化为等式，求出一组基本解，因为对偶问题可行，即全部检验数因为对偶问题可行，即全部检验数j j00（maxmax）或或j j00（minmin）, ,当基本解可行时，则达到最优解；当基本解可行时，则达到最优解；若基本解不可行，即有某个基变量的解若基本解不可行，即有某个基变量的解bibi00，则进，则进行换基计算；行换基计算；(2)(2)先确定出基变量。先确定出基变量。 l l 行对应的行对应的变量变量x x出基；出基；(3)(3)再选进基变量。求最小比值再选进基变量。求最小比值(4)(4)求新的基本解，用初等变换将主元素求新的基本

50、解，用初等变换将主元素alkalk化为化为l,l,k k列其它元素化为零，得到新的基本解，转到第列其它元素化为零，得到新的基本解，转到第一步重复运算。一步重复运算。min|0liiibb b 0|minljljjjkaamin z = 2x1+4x2+6x3 s.t. 2x1 - x2 + x3 10 x1+2x2+2x3 12 2x2 - x3 4 x1，x2，x3 0解：解：将问题化为：将问题化为：max z = -2x1- 4x2 - 6x3 s.t. -2x1 + x2 - x3+ x4=-10 x1+2x2+2x3 +x5=12 -2x2 + x3 +x6 =-4 xj 0 ( j=

51、1,2,6) 检验数ccBxB-2 -4 -6 0 0 0 x1 x2 x3 x4 x5 x6 000 x4x5x6-2 1 -1 1 0 0 1 2 2 0 1 0 0 -2 1 0 0 1-2 -4 -6 0 0 0 b-1012-40-2 1-1/2 1/2 -1/20050 x1-25/2 3/21/21070-5-1-50010 x2-2-401-1/200-1/22101/4-1/2 0-1/460011/41/215/4200 -15/2 -10 -5/220初始基解为初始基解为:x0=(0,0,0,-10,12,-4)T最优解为最优解为: :x*=(6,2,0,0,2,0)Tz

52、*= 20从表中看到，检验数行对应的对偶问题的解是可行解。从表中看到，检验数行对应的对偶问题的解是可行解。因因b b列数字为负，故需进行迭代运算。列数字为负，故需进行迭代运算。 max z= max z= 2x1 2x1 3x2 3x2 4x3 4x3 x1 x1 2x2 2x2 x3 + x4 = x3 + x4 = 3 32x1 + x2 2x1 + x2 3x3 +x5 = 3x3 +x5 = 4 4xj0 xj0，j=1,2,j=1,2,5,512234,22min由第由第2 2张单纯形表看出，对偶问题仍是可行解，而张单纯形表看出，对偶问题仍是可行解，而b b列中列中仍有负分量。故重复

53、上述迭代步骤。仍有负分量。故重复上述迭代步骤。第第2 2张单纯形表张单纯形表换出基变量：换出基变量：x4x4换入基变量：换入基变量：x2x2第第3 3张单纯形表中，张单纯形表中，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)