目标规划单纯形法1

1、2.2.3 目标规划的图解法 例某企业生产两种产品，在单件利润等有关数据例某企业生产两种产品，在单件利润等有关数据已知条件下，要求制定一个获利最大的生产计划：已知条件下，要求制定一个获利最大的生产计划： 目标，第一级：允许加班，加班时间每周不超过目标，第一级：允许加班，加班时间每周不超过10小时；第二级：产品产量满足市场需求小时；第二级：产品产量满足市场需求产产 品品限限 量量销量（销量（kg/kg/件）件）2430时间（时间（h/h/件）件）1140利润（元利润（元/ /件）件）810 2.2.3 目标规划的图解法 例，某电视机厂装配黑白和彩色电视，每装配一例，某电视机厂装配黑白和彩色电视，

2、每装配一台占用装配线台占用装配线1 1小时，装配线每周计划开动小时，装配线每周计划开动4040小时。小时。预计市场每周彩色电视机的销售量为预计市场每周彩色电视机的销售量为2424台，每台台，每台获利获利8080元，黑白电视机销售量元，黑白电视机销售量3030台，每台可获利台，每台可获利4040元，该厂目标为：元，该厂目标为： 第一级：充分利用装配线每周开动第一级：充分利用装配线每周开动4040小时小时 第二级：允许装配加班，但每周尽量不超过第二级：允许装配加班，但每周尽量不超过1010小小时时 第三级：允许装配电视机的数量尽量满足市需要，第三级：允许装配电视机的数量尽量满足市需要，因彩色利润高

3、，故其权系数为因彩色利润高，故其权系数为2 22.2.4 目标规划的基本概念l 线性规划目标线性规划目标l 可行解可行解l 可接受解与不可接受解可接受解与不可接受解l 达成函数达成函数l 最优解最优解l 多重最优解多重最优解l 无界解无界解2.2.5 目标规划的单纯形法cj c1c2cn+2mCBXBb x1x2 xn+2m cj1xj1 bo1e11e12e1n+2mcj2xj2bo2e21e22e2n+2m cjmxjm bomem1em2emn+2mjP111121n+2mP221222n+2mPK m1m2mn+2m一般形式：一般形式：2.2.5 目标规划的单纯形法 单纯形法的计算步骤

4、单纯形法的计算步骤 1 1、建立初始单纯形表、建立初始单纯形表 一般假定初始解在原点，即以约束条件中一般假定初始解在原点，即以约束条件中的所有负偏差变量或松弛变量为初始基变的所有负偏差变量或松弛变量为初始基变量，按目标优先等级从左至右分别计算出量，按目标优先等级从左至右分别计算出各列的检验数，填入表下半部的各列的检验数，填入表下半部的K K行中，置行中，置 k=1 k=1 。2.2.5 目标规划的单纯形法 2 2、检验是否为满意解、检验是否为满意解 若若PkPk这一行某些负检验数的同列上面（较这一行某些负检验数的同列上面（较高优先等级）没有正检验数，说明未得到高优先等级）没有正检验数，说明未得

5、到满意解，应继续改进，转到第满意解，应继续改进，转到第3 3步；若步；若PkPk这这一行全部负检验数的同列上面（较高优先一行全部负检验数的同列上面（较高优先等级）都有正检验数，说明目标虽没达到，等级）都有正检验数，说明目标虽没达到，但已不能改进，故得满意解，转到第但已不能改进，故得满意解，转到第6 6步。步。2.2.5 目标规划的单纯形法 3 3、确定进基变量、确定进基变量 在在PkPk行，从那些上面没有正检验数的负检行，从那些上面没有正检验数的负检验数中，选绝对值最大者，对应的变量验数中，选绝对值最大者，对应的变量xsxs就就是进基变量。若是进基变量。若PkPk行中有几个相同的绝对行中有几个

6、相同的绝对值最大者，则依次比较它们各列下部的检值最大者，则依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在验数，取其绝对值最大的负检验数的所在列的列的xsxs为进基变量。假如仍无法确定，则选为进基变量。假如仍无法确定，则选最左边的变量（变量下标小者）为进基变最左边的变量（变量下标小者）为进基变量，转第量，转第4 4步。否则，转第步。否则，转第6 6步。步。2.2.5 目标规划的单纯形法 4 4、确定出基变量、确定出基变量 其方法同线性规划，即依据最小比值法则其方法同线性规划，即依据最小比值法则 故确定故确定xr xr为出基变量，为出基变量，ersers为主元素。若有几个为主元素。若

7、有几个相同的行可供选择时，选最上面那一行所对应相同的行可供选择时，选最上面那一行所对应得变量为得变量为xr xr 。rsorisissiebeeb0/min2.2.5 目标规划的单纯形法 5 5、旋转变换（变量迭代）、旋转变换（变量迭代） 以以ersers为主元素进行变换，得到新的单纯形为主元素进行变换，得到新的单纯形表，获得一组新解，返回到第表，获得一组新解，返回到第2 2步。步。 6 6、对求得的解进行分析、对求得的解进行分析 当当k=Kk=K时，计算结束，停止运算；表中的解时，计算结束，停止运算；表中的解即为最终解。若不满意，需修改模型，即即为最终解。若不满意，需修改模型，即调整目标优先

8、等级和权系数，或者改变目调整目标优先等级和权系数，或者改变目标值，重新进行第标值，重新进行第1 1步。否则置步。否则置k=k+1k=k+1，返，返回第回第2 2步。步。11232432121112221332441 2min2.530122500 2 140. . 60 1000,0 (1.2.3.4)llZPdP dP dPdxxddxxdds txddxddxddl例例 用单纯形法求解下列目标规划问题用单纯形法求解下列目标规划问题cj00P100P302.5P20P2CBXBbx1x2P1250030121100000001402100110000060100000110001000100

9、000011jP1 301201000000P2 00000002.501P3 00000100001d1d2d2d3d3d4d4d1d2d3d4d= min2500/30,140/2,60/1=60 ,故故 为换出变量。为换出变量。3d2.2.5 2.2.5 目标规划的单纯形法目标规划的单纯形法cj 00P100P302.5P20P2CBXBbx1x2P1700012110030300002001001122000 x160100000110001000100000011jP1 0120100303000P2 00000002.501P3 00000100001d1d2d2d3d3d4d4d

10、1d2d4d= min700/30,20/2, =10 ,故故 为换出变量。为换出变量。2d2.2.5 2.2.5 目标规划的单纯形法目标规划的单纯形法cj 00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000 x17011/2001/2-1/200000100010000001-1jP1 030115-150000P2 0-5/400-5/45/45/2001P3 00000100001d1d2d2d3d3d4d4d1d4d= min400/15, =10 ,故故 为换出变量。为换出变量。3d1d2.

11、2.5 2.2.5 目标规划的单纯形法目标规划的单纯形法cj 00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000 x1250/312/51/30-1/3000000001000100000011jP1 0010000000P2 0-1-1/121/12002/5001P3 01/5-1/151/151000001d1d2d2d3d3d4d4d4d= min,350/6,1250/6,100/1=75 ,故故 为换出变量。为换出变量。2d3d3d2.2.5 2.2.5 目标规划的单

12、纯形法目标规划的单纯形法cj 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/211jP1 0010000000P2 00000005/201P3 00-1/121/12101/2-1/2001d1d2d2d3d3d4d4d4d2d表中表中P P3行仍有负数行仍有负数，说明说明P3 优先等级目标没有实现，但已无法改优先等级目标没有实现，但已无法改进，得到满意解进，得到满意解 x1 60，

13、 x2 175/3， 115/3， 125/3。4d2d2.2.5 2.2.5 目标规划的单纯形法目标规划的单纯形法1122233121112221233121 2min() 0 210. .810562 110,. 0 (1.2.3)jjZPdP ddPdxxddxxdds txxddxxxddj课堂练习：课堂练习：用单纯形法求解下列目标规划问题用单纯形法求解下列目标规划问题cj 000P1 P2 P2P3 00CBXBbx1x2 x3 00111100000P210120011000 P3 5681000001100 x3 11210000001jP1 000100000P2 120002

14、000P3 81000000101d1d2d2d3d3d1d2d3d= min,10/2,56/10,11/1= 5,故故 为换出变量。为换出变量。2d2.2.5 2.2.5 目标规划的单纯形目标规划的单纯形法法cj 000P1 P2 P2P3 00CBXBbx1x2 x3 023/20111/2-1/20000 x251/21001/2-1/2000 P3 63000-551100 x3 63/2000-1/21/2001jP1 000100000P2 000011000P3 30005-50101d1d2d2d3d3d1d3d= min10/3,10,6/3,12/3= 2,故故 为换出变

15、量。为换出变量。3d2.2.5 2.2.5 目标规划的单纯形目标规划的单纯形法法cj 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/21jP1 000100000P2 000011000P3 0000001001d1d2d2d3d3d1d 最优解为最优解为x12 2， x2 4 4。 但非基变量但非基变量 的检验的检验数为零，故此题有无穷多最优解。数为零，故此题有无穷多最优解。= min4 , 24 , 6= 4,故故 为换出变量。为换出变量。1d3d2.2.5 2.2.5 目标规划