目标规划单纯形法

目标规划单纯形法目标规划单纯形法2.2.3 目标规划的图解法例，某电视机厂装配黑白和彩色电视，每装配一例，某电视机厂装配黑白和彩色电视，每装配一台占用装配线台占用装配线1 1小时，装配线每周计划开动小时，装配线每周计划开动4040小时。小时。预计市场每周彩色电视机的销售量为预计市场每周彩色电视机的销售量为2424台，每台台，每台获利获利8080元，黑白电视机销售量元，黑白电视机销售量3030台，每台可获利台，每台可获利4040元，该厂目标为：元，该厂目标为：第一级：充分利用装配线每周开动第一级：充分利用装配线每周开动4040小时小时第二级：允许装配加班，但每周尽量不超过第二级：允许装配加班，但每周尽量不超过1010小小时时第三级：允许装配电视机的数量尽量满足市需要，第三级：允许装配电视机的数量尽量满足市需要，因彩色利润高，故其权系数为因彩色利润高，故其权系数为2 22.2.4 目标规划的基本概念线性规划目标线性规划目标可行解可行解可接受解与不可接受解可接受解与不可接受解达成函数达成函数最优解最优解多重最优解多重最优解无界解无界解2.2.5 目标规划的单纯形法cj c1c2cn+2mCBXBb x1x2 xn+2m cj1xj1 bo1e11e12e1n+2mcj2xj2bo2e21e22e2n+2m cjmxjm bomem1em2emn+2mjP111121n+2mP221222n+2mPK m1m2mn+2m一般形式：一般形式：2.2.5 目标规划的单纯形法单纯形法的计算步骤单纯形法的计算步骤1 1、建立初始单纯形表、建立初始单纯形表 一般假定初始解在原点，即以约束条件中一般假定初始解在原点，即以约束条件中的所有负偏差变量或松弛变量为初始基变的所有负偏差变量或松弛变量为初始基变量，按目标优先等级从左至右分别计算出量，按目标优先等级从左至右分别计算出各列的检验数，填入表下半部的各列的检验数，填入表下半部的K K行中，置行中，置 k=1 k=1。2.2.5 目标规划的单纯形法2 2、检验是否为满意解、检验是否为满意解若若PkPk这一行某些负检验数的同列上面（较这一行某些负检验数的同列上面（较高优先等级）没有正检验数，说明未得到高优先等级）没有正检验数，说明未得到满意解，应继续改进，转到第满意解，应继续改进，转到第3 3步；若步；若PkPk这这一行全部负检验数的同列上面（较高优先一行全部负检验数的同列上面（较高优先等级）都有正检验数，说明目标虽没达到，等级）都有正检验数，说明目标虽没达到，但已不能改进，故得满意解，转到第但已不能改进，故得满意解，转到第6 6步。步。2.2.5 目标规划的单纯形法3 3、确定进基变量、确定进基变量在在PkPk行，从那些上面没有正检验数的负检行，从那些上面没有正检验数的负检验数中，选绝对值最大者，对应的变量验数中，选绝对值最大者，对应的变量xsxs就是进基变量。若就是进基变量。若PkPk行中有几个相同的绝行中有几个相同的绝对值最大者，则依次比较它们各列下部的对值最大者，则依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所检验数，取其绝对值最大的负检验数的所在列的在列的xsxs为进基变量。假如仍无法确定，为进基变量。假如仍无法确定，则选最左边的变量（变量下标小者）为进则选最左边的变量（变量下标小者）为进基变量，转第基变量，转第4 4步。否则，转第步。否则，转第6 6步。步。2.2.5 目标规划的单纯形法4 4、确定出基变量、确定出基变量其方法同线性规划，即依据最小比值法则其方法同线性规划，即依据最小比值法则故确定故确定xrxr为出基变量，为出基变量，ersers为主元素。若有几为主元素。若有几个相同的行可供选择时，选最上面那一行所对个相同的行可供选择时，选最上面那一行所对应得变量为应得变量为xr xr。2.2.5 目标规划的单纯形法5 5、旋转变换（变量迭代）、旋转变换（变量迭代）以以ersers为主元素进行变换，得到新的单纯形为主元素进行变换，得到新的单纯形表，获得一组新解，返回到第表，获得一组新解，返回到第2 2步。步。6 6、对求得的解进行分析、对求得的解进行分析当当k=Kk=K时，计算结束，停止运算；表中的解时，计算结束，停止运算；表中的解即为最终解。若不满意，需修改模型，即即为最终解。若不满意，需修改模型，即调整目标优先等级和权系数，或者改变目调整目标优先等级和权系数，或者改变目标值，重新进行第标值，重新进行第1 1步。否则置步。否则置k=k+1k=k+1，返，返回第回第2 2步。步。例例 用单纯形法求解下列目标规划问题用单纯形法求解下列目标规划问题cj00P100P302.5P20P2CBXBbx1x2P1250030121100000001402100110000060100000110001000100000011jP1 301201000000P2 00000002.501P3 0000010000=min2500/30,140/2,60/1=60,故故 为换出变量。为换出变量。2.2.5 2.2.5 目标规划的单纯形法目标规划的单纯形法cj 00P100P302.5P20P2CBXBbx1x2P1700012110030300002001001122000 x160100000110001000100000011jP1 0120100303000P2 00000002.501P3 0000010000=min700/30,20/2,=10,故故 为换出变量。为换出变量。2.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 0000010000=min400/15,=10,故故 为换出变量。为换出变量。2.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/15100000=min,350/6,1250/6,100/1=75,故故 为换出变量。为换出变量。2.2.5 2.2.5 目标规划的单纯形法目标规划的单纯形法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/200表中表中P P3行仍有负数行仍有负数，说明说明P3 优先等级目标没有实现，但已无法改优先等级目标没有实现，但已无法改进，得到满意解进，得到满意解 x1 60，x2 175/3，115/3，125/3。2.2.5 2.2.5 目标规划的单纯形法目标规划的单纯形法课堂练习：课堂练习：用单纯形法求解下列目标规划问题用单纯形法求解下列目标规划问题cj 000P1 P2 P2P3 00CBXBbx1x2 x3 00111100000P210120011000 P3 5681000001100 x3 11210000001jP1 000100000P2 120002000P3 8100000010=min,10/2,56/10,11/1=5,故故 为换出变量。为换出变量。2.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-5010=min10/3,10,6/3,12/3=2,故故 为换出变量。为换出变量。2.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 000000100 最优解为最优解为x12 2，x2 4 4。但非基变量但非基变量 的检验的检验数为零，故此题有无穷多最优解。数为零，故此题有无穷多最优解。=min4,24,6=4,故故 为换出变量。为换出变量。2.2.5 2.2.5 目标规划的单纯形目标规划的单纯形法法cj 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-11001jP1 000100000P2 000011000P3 000000100 最优解为最优解为x110/3,，x2=10/3。2.2.5 2.2.5 目标规划的单纯形目标规划的单纯形法法结束语结束语谢谢大家聆听！谢谢大家聆听！21