用单纯形法求解目标规划PPT课件02

《用单纯形法求解目标规划PPT课件02》由会员分享，可在线阅读，更多相关《用单纯形法求解目标规划PPT课件02（31页珍藏版）》请在装配图网上搜索。

1、目标规划单纯形法的求解步骤例 *题目标规划求解问题过程目标规划求解问题过程明确问题，列出明确问题，列出(或修改或修改)目标的优先级和权系数目标的优先级和权系数构造目标构造目标规划的模型规划的模型求出求出满意解满意解满意否？满意否？分析各项目分析各项目表完成情况表完成情况据此制定出据此制定出决策方案决策方案是是否否 由目标规划数学模型的标准型可看出，它实质上是由目标规划数学模型的标准型可看出，它实质上是 最小化的线性规划，所以可用单纯形法求解最小化的线性规划，所以可用单纯形法求解 这时，我们应该把目标优先等级系数这时，我们应该把目标优先等级系数P Pi i（i i=1,2,=1,2,k k）理解

2、为一种特殊的正常数，且注意到各等级系数之间的理解为一种特殊的正常数，且注意到各等级系数之间的关系：关系：P P1 1P P2 2 P Pk k 而检验数就是各优先因子而检验数就是各优先因子P P1 1,P P2 2,P Pk k的线性组合。的线性组合。0jjjCcz当所有检验数都满足最优性条件（当所有检验数都满足最优性条件（）时，从）时，从最终表上即可得出目标规划的解最终表上即可得出目标规划的解ci-zj =kj Pk ,j=1,2,n;k=1,2,KP Pk k是指不同数量的很大的数是指不同数量的很大的数 d d-是松弛变量是松弛变量 d d+是剩余变量是剩余变量P Pk kMPMPk+1

3、k+1 (M(M是任意大的正数）是任意大的正数）用单纯形法求解下面目标规划问题用单纯形法求解下面目标规划问题:11223312112112122231233412Min 51060 2 0 s.t4 4 36 68 48 001 2 3()()()(),(,)iiZPdP dP dxxlxxddlxxddlxxddlxxddi引入松驰变量引入松驰变量 x x3 3,将它们化为标准型：将它们化为标准型：1122331231211122212331235106004366848001 2 3Min 2 s.t.4 ,(,)iiZP dP dP dxxxxxddxxddxxddxxxddi cj 0

4、 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 5 10 1 0 0 0 0 0 0 P1 0 1-2 0 1-1 0 0 0 0 0 36 4 4 0 0 0 1-1 0 0 P3 48 6 8 0 0 0 0 0 1-1 P1-1 2 0 0 1 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3-6-8 0 0 0 0 0 0 1 0 x3 60 0 20 1-5 5 0 0 0 0 0 x1 0 1-2 0 1-1 0 0 0 0 0 36 0 12 0-4 4 1-1 0 0 P3 48 020 0-6 6 0 0 1-1 P1

5、0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0-20 0 6-6 0 0 0 11d1d2d3d2d3d1d2d3d2d3djjjzc 单单纯纯形形表表1jjjzc 60166415000321313111PPPPPPPC1122331231211122212331235106004366848001 2 3Min 2 s.t.4 ,(,)iiZP dP dP dxxxxxddxxddxxddxxxddi cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 0 20 1-5 5 0 0 0 0 0 x1 0

6、1-2 0 1-1 0 0 0 0 0 36 0 12 0-4 4 1-1 0 0 P3 48 020 0-6 6 0 0 1-1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0-20 0 6-6 0 0 0 1 0 x312 0 0 1 1 -1 0 0 -1 1 0 x124/5 1 0 0 2/5-2/5 0 01/10-1/10 036/5 0 0 0-2/5 2/5 1-1-3/5 3/5 0 x212/5 0 1 0-3/10 3/10 0 01/20-1/20 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1

7、 0 0 P3 0 0 0 0 0 0 0 1 01d1d2d3d2d3d2d3djjjzc 2djjjzc 单单纯纯形形表表1全部检验数非全部检验数非负，计算结束。负，计算结束。1 1、建立初始单纯形表。、建立初始单纯形表。一般假定初始解在原点，一般假定初始解在原点，即以约束条件中的即以约束条件中的所有负偏差变量或松弛变量为初始基变量所有负偏差变量或松弛变量为初始基变量，按目标优先等级从左至右分别计算出各列的检验数，按目标优先等级从左至右分别计算出各列的检验数，填入表的下半部填入表的下半部 ，得检验数矩阵。，得检验数矩阵。（2 2）若检验数矩阵的若检验数矩阵的P Pi i 中有负系数，中有负

8、系数，且负系数所在列的且负系数所在列的前前i i-1-1行优先因子的系数全为行优先因子的系数全为0 0(例如例如 )，可判定该检验数为负可判定该检验数为负，则选该系数（若此类负系数有多个，则可选绝对值最大者）则选该系数（若此类负系数有多个，则可选绝对值最大者）所在列对应的非基变量为入基变量，继续进行基变换所在列对应的非基变量为入基变量，继续进行基变换 （3 3）若检验数矩阵的若检验数矩阵的P Pi i行中有负系数，行中有负系数，但负系数所在但负系数所在列的前列的前i i-1-1行优先因子的系数有行优先因子的系数有0 0，也有正数，也有正数，（例如（例如 ），即整个检验数的值可判为正），即整个检

9、验数的值可判为正（因（因P Pi i-1-1P Pi i），故也应转入对），故也应转入对P Pi i+1+1级目标的寻优，否则会级目标的寻优，否则会使高优先级别的目标函数值劣化使高优先级别的目标函数值劣化 入基变量的确定：入基变量的确定：在在P Pk k行，从那些上面没有行，从那些上面没有 正检验数正检验数 的负检验数中，选绝对值最大者，对应的变量的负检验数中，选绝对值最大者，对应的变量x xs s就是进基变就是进基变量。量。若若P Pk k行中有几个相同的绝对值最大者，则依次比较它们各列行中有几个相同的绝对值最大者，则依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在列的下部的检验

10、数，取其绝对值最大的负检验数的所在列的x xs s为为进基变量。进基变量。假如仍无法确定，则选最左边的变量（变量下标小者）为进假如仍无法确定，则选最左边的变量（变量下标小者）为进基变量。基变量。出基变量的确定：出基变量的确定：按最小非负比值规则确定出基变量，当存在两个或两个按最小非负比值规则确定出基变量，当存在两个或两个 以上相同的最小比值时，选取具有较高优先级别的变量为换以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。出变量。主元素的确定：主元素的确定：出基变量与入基变量在系数矩阵中对应的交叉点上的元素即出基变量与入基变量在系数矩阵中对应的交叉点上的元素即为主元素为主元素 迭代变

11、换：迭代变换：同线性规划的同线性规划的单纯形单纯形法法得到新的单纯形表，获得一组新解得到新的单纯形表，获得一组新解对求得的解进行分析：对求得的解进行分析：若计算结果满意，停止运算；若计算结果满意，停止运算；若不满意，需修改模型，即调整目标优先等级和权系数，若不满意，需修改模型，即调整目标优先等级和权系数，或者改变目标值，重新进行第或者改变目标值，重新进行第1 1步。步。4 4 每个单纯形表中常数列每个单纯形表中常数列b b，即为各基变量的相应取，即为各基变量的相应取值值本题最后一个单纯形表已为最优，它对应的基本可行解：本题最后一个单纯形表已为最优，它对应的基本可行解：x x1 1=24/5,=

12、24/5,x x2 2=12/5,=12/5,x x3 3=12,d=12,d2 2-=36/5=36/5，即为最优解这，即为最优解这与图解法得到结果一致与图解法得到结果一致 在最优单纯形表中非基变量在最优单纯形表中非基变量d d1 1+和和d d3 3+的检验数都是零，的检验数都是零，故知本题有多个最优解故知本题有多个最优解 如以如以 d d1 1+为入基变量继续迭代，可得单纯形表为入基变量继续迭代，可得单纯形表2 2，如以如以d d3 3+为入基变量继续迭代，可得单纯形表为入基变量继续迭代，可得单纯形表3 3 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3

13、 0 x3 60 0 20 1-5 5 0 0 0 0 0 x1 0 1-2 0 1-1 0 0 0 0 0 36 0 12 0-4 4 1-1 0 0 P3 48 020 0-6 6 0 0 1-1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0-20 0 6-6 0 0 0 1 0 x312 0 0 1 1 -1 0 0 -1 1 0 x124/5 1 0 0 2/5-2/5 0 01/10-1/10 036/5 0 0 0-2/5 2/5 1-1-3/5 3/5 0 x212/5 0 1 0-3/10 3/10 0 01/20-1/20 P1

14、 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 0 0 0 0 0 0 1 01d1d2d3d2d3d2d3djjjzc 2djjjzc 单纯形表单纯形表1 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 20 010/3 1 0 0 0 0-5/6 5/6 0 x1 8 1 4/3 0 0 0 0 0 1/6-1/6 0 4 0-4/3 0 0 0 1-1-2/3 2/3 0 8 010/3 0-1 1 0 0 1/6-1/6 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0

15、0 P3 0 0 0 0 0 0 0 1 01d1d2d3d2d3d2djjjzc 1d cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 12 0 0 1 1 -1 0 0-1 1 0 x1 6 1 0 1/10 1/2-1/2 0 0 0 0 0 0 0 0-3/5 -1 1 1-1 0 0 0 x2 3 0 1 1/20 -1/4 1/4 0 0 0 0 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 0 0 0 0 0 0 1 01d1d2d3d2d3d2djjjzc 3d )3,2,1i(0d,d,0

16、x,x11 x x256ddx10 x810ddx2 x 0ddx x dP)dd(PdPZminii21213321222111213322211 )3,2,1i(0d,d,0 x,x11 xx x256ddx10 x810ddx2 x 0ddx x dP)dd(PdPZminii213213321222111213322211Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 00111100000P210120011000 P3 5681000001100 x3 11210000001kjP1 0000100000P2-10120002000P3-568100000010 1

17、d 1d 2d 2d 3d 3d 1d 2d 3d )3,2,1i(0d,d,0 x,x11 xx x256ddx10 x810ddx2 x 0ddx x dP)dd(PdPZminii213213321222111213322211Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 053/20111/2-1/20000 x251/21001/2-1/2000 P3 63000-551100 x3 63/2000-1/21/2001kjP1 0000100000P2 0000011000P3-630005-5010 1d 1d 2d 2d 3d 3d 1d 3d=min10/3,

18、10,6/3,12/3=2,故故 为换出变量。为换出变量。3dCj 000P1 P2 P2P3 00CBXBbx1x2 x3 0200113-3-1/21/200 x2401004/3-4/3-1/61/600 x121000-5/35/31/3-1/300 x3 300002-2-1/21/21kjP1 0000100000P2 0000011000P3 0000000100 1d 1d 2d 2d 3d 3d 1d 最优解为最优解为x12 2，x2 4 4。但非基变量但非基变量 的检验数为的检验数为零，故此题有无穷多最优解。零，故此题有无穷多最优解。=min4,24,6=4,故故 为换出变

19、量。为换出变量。1d 3dCj 000P1 P2 P2P3 00CBXBbx1x2 x3 04002-26-6-1100 x210/301-1/31/31/3-1/30000 x110/3102/3-2/31/3-1/30000 x3 100-11-11001kjP1 0000100000P2 0000011000P3 000000100 1d 1d 2d 2d 3d 3d 3d 最优解为最优解为x110/3,，x2=10/3。则这两个解得凸组合都是本例的满意解。则这两个解得凸组合都是本例的满意解。例例 :用单纯形法求解下述目标规划问题：用单纯形法求解下述目标规划问题：)3,2,1i(0d,d

20、,x,x100ddx2x340ddxx210ddx.t.sdPddPzminii213321222111132111解解 :第一步：列出初始单纯形表第一步：列出初始单纯形表cj 0 0 P1 0 0 P1 P2 0 CB 基基 b x1 x2 d1-d1+d2-d2+d3-d3+P1 d1-10 1 0 1-1 0 d2-40 2 1 1-1 P2 d3-100 3 2 1-1 P1-1 1 1 cj-zj P2-3-2 1 第二步：确定换入变量第二步：确定换入变量 第三步：确定换出变量第三步：确定换出变量第四步：用换入变量替换基变量中的换出变量第四步：用换入变量替换基变量中的换出变量cj 0

21、 0 P1 0 0 P1 P2 0 CB 基基 b x1 x2 d1-d1+d2-d2+d3-d3+0 x1 10 1 0 1-1 0 d2-20 1-2 2 1-1 P2 d3-70 2-3 3 1-1 P1 1 1 cj-zj P2 -2 3-3 1 已知一个生产计划的线性规划模型为已知一个生产计划的线性规划模型为 0 x)(100 x )(60 x )(140 xx2x12x30Zmax21212121丙丙资资源源乙乙资资源源甲甲资资源源 其中目标函数为总利润，其中目标函数为总利润，x x1 1,x,x2 2 为产品为产品A A、B B产量。现有产量。现有下列目标：下列目标：1 1、要求

22、总利润必须超过、要求总利润必须超过 2500 2500 元；元；2 2、考虑产品受市场影响，为避免积压，、考虑产品受市场影响，为避免积压，A A、B B的生产量的生产量不超过不超过 60 60 件和件和 100 100 件；件；3 3、由于甲资源供应比较紧张，不要超过现有量、由于甲资源供应比较紧张，不要超过现有量140140。试建立目标规划模型，并用单纯形法求解。试建立目标规划模型，并用单纯形法求解。)4.3.2.1l(0d,d,0 x100dd x 60dd x 140dd x x2 2500ddx12x30dPdPdP5.2dPZminll214423312221112123423211

23、1 1、要求总利润必须超过、要求总利润必须超过 2500 2500 元；元；2 2、考虑产品受市场影响，为避免积压，、考虑产品受市场影响，为避免积压，A A、B B的生的生产量不超过产量不超过 60 60 件和件和 100 100 件；件；3 3、由于甲资源供应比较紧张，不要超过现有量、由于甲资源供应比较紧张，不要超过现有量140140。Cj00P100P302.5P20P2CBXBbx1x2P1250030121100000001402100110000060100000110001000100000011kjP1-2500301201000000P2 000000002.501P3 000

24、000100001d1d2d2d3d3d4d4d1d2d3d4d=min2500/30,140/2,60/1=60,故故 为换出变量。为换出变量。3dCj 00P100P302.5P20P2CBXBbx1x2P1700012110030300002001001122000 x160100000110001000100000011kjP1 7000120100303000P2 000000002.501P3 000000100001d1d2d2d3d3d4d4d1d2d4d=min700/30,20/2,=10,故故 为换出变量。为换出变量。2dCj 00P100P302.5P20P2CBXBb

25、x1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000 x17011/2001/2-1/200000100010000001-1kjP1-400030115-150000P2-250-5/400-5/45/45/2001P3 000000100001d1d2d2d3d3d4d4d1d4d=min400/15,=10,故故 为换出变量。为换出变量。3d1dCj 00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000 x1250/312/51

26、/30-1/3000000001000100000011kjP1 00010000000P2-175/30-1-1/121/12002/5001P3-80/301/5-1/151/151000001d1d2d2d3d3d4d4d4d=min,350/6,1250/6,100/1=75,故故 为换出变量。为换出变量。2d3d3dCj 00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000 x2175/3011/12-1/1200-5/25/2000 x160100000-11000125/300-1/121/12005/2-5/211k

27、jP1 00010000000P2 000000005/201P3-115/300-1/121/12101/2-1/2001d1d2d2d3d3d4d4d4d2d表中表中P P3 3检验数为负，说明检验数为负，说明P3 优先等级目标没有实现，但已无法改优先等级目标没有实现，但已无法改进，得到满意解进，得到满意解 x1 60，x2 175/3，115/3，125/3。4d2d 结果分析结果分析：计算结果表明，工厂应生产：计算结果表明，工厂应生产A A产品产品6060件，件，B B产品产品175/3175/3件，件，25002500元的利润目标刚好达到。元的利润目标刚好达到。d d4 4-125/

28、3125/3，表明产品，表明产品B B比最高限额少比最高限额少125/3125/3件，满足要求。件，满足要求。d d2 2+115/3 115/3 表明甲资源超过库存表明甲资源超过库存115/3115/3公斤，该目标没有达到。公斤，该目标没有达到。从表中还可以看到，从表中还可以看到，P3 的检验数还有负数，的检验数还有负数，但其高等级的检验数却是正数，但其高等级的检验数却是正数，要保证要保证 P1目标实现，目标实现，P3等级目标则无法实现。等级目标则无法实现。所以，按现有消耗水平和资源库存量，无法实现所以，按现有消耗水平和资源库存量，无法实现25002500元的利润目标。元的利润目标。可考虑如

29、下措施：可考虑如下措施：降低降低A A、B B产品对甲资源的消耗量，产品对甲资源的消耗量，以满足现有甲资源库存量的目标；以满足现有甲资源库存量的目标；或改变或改变P3等级目标的指标值，增加甲资源等级目标的指标值，增加甲资源115/3115/3公斤。公斤。若很难实现上述措施，则需改变现有目标的优先等级，若很难实现上述措施，则需改变现有目标的优先等级，以取得可行的满意结果。以取得可行的满意结果。)4.3.2.1l(0d,d,0 x100dd x 60dd x 140dd x x2 2500ddx12x30dPdPdP5.2dPZminll214423312221112123423211满意解满意解 x x1 1 6060，x x2 2 175/3175/3，d d2 2+115/3115/3，d d4 4-125/3125/3。1 1、要求总利润必须超过、要求总利润必须超过 2500 2500 元；元；2 2、考虑产品受市场影响，为避、考虑产品受市场影响，为避免积压，免积压，A A、B B的生产量不超过的生产量不超过 60 60 件和件和 100 100 件；件；3 3、由于甲资源供应比较紧张，、由于甲资源供应比较紧张，不要超过现有量不要超过现有量140140。