《目标规划的图解法PPT演示文稿》由会员分享，可在线阅读，更多相关《目标规划的图解法PPT演示文稿（32页珍藏版）》请在金锄头文库上搜索。
1、1,图解法同样适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。,图解法解题步骤如下： 1、确定各约束条件的可行域，即将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）在坐标平面上表示出来； 2、在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；,2 求解目标规划问题的图解法,2,3、求满足最高优先等级目标的解； 4、转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解； 5、重复4，直到所有优先等级的目标都已审查完毕为止； 6、确定最优解和满意解。,例一、用图解法求解目标规划问
2、题,3,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,A,x2,x1,B,C,B (0.6250 , 4.6875) C (0 , 5.2083) ， B、C 线段上的所有点均是该问题的解（无穷多最优解）。,4,例二、已知一个生产计划的线性规划模型为,其中目标函数为总利润，x1,x2 为产品A、B产量。现有下列目标： 1、要求总利润必须超过 2500 元； 2、考虑产品受市场影响，为避免积压，A、B的生产量不超过 60 件和 100 件； 3、由于甲资源供应比较紧张，不要超过现有量140。 试建立目标规划模型，并用图解法求解。,5,解：以产品 A、B 的单件利润比 2.5 ：1
3、为权系数，模型如下：,6,0,x2,0,x1,140 120 100 80 60 40 20,20 40 60 80 100,A,B,C,D,结论：C(60 ,58.3)为所求的满意解。,作图：,7,检验：将上述结果带入模型，因 0； 0； 0， 存在； 0， 存在。所以，有下式： minZ=P3,将 x160， x2 58.3 带入约束条件，得,30601258.32499.62500； 260+58.3=178.3 140； 16060 158.358.3 100,由上可知：若A、B的计划产量为60件和58.3件时，所需甲资源数量将超过现有库存。在现有条件下，此解为非可行解。为此，企业必须
4、采取措施降低A、B产品对甲资源的消耗量，由原来的100降至78.5（140178.30.785），才能使生产方案（60，58.3）成为可行方案。,8,练习：用图解法求解下列目标规划问题,9,C,D,结论：有无穷多最优解。C（2，4）D（10/3，10/3）,10,2.2 求解目标规划问题的单纯形法,（一）、一般形式：,11,1、建立初始单纯形表。 一般假定初始解在原点，即以约束条件中的所有负偏差变量或松弛变量为初始基变量，按目标优先等级从左至右分别计算出各列的检验数，填入表的下半部 。,2、检验是否为满意解。判别准则如下： .首先检查k (k=1.2K)是否全部为零？如果全部为零，则表示目标均
5、已全部达到，获得满意解，停止计算转到第6步；否则转入。,（二）、单纯形法的计算步骤,12,.如果某一个k 0。说明第k个优先等级的目标尚未达到,必须检查Pk这一的检验数kj(j=1.2n+2m).若Pk这一行某些负检验数的同列上面（较高优先等级）没有正检验数，说明未得到满意解，应继续改进，转到第3步；若Pk这一行全部负检验数的同列上面（较高优先等级）都有正检验数，说明目标虽没达到，但已不能改进，故得满意解，转到第6步。,3、确定进基变量。 在Pk行，从那些上面没有正检验数的负检验数中，选绝对值最大者，对应的变量xs就是进基变量。若Pk行中有几个相同的绝对值最大者，则依次比较它们各列下部的检验数
6、，取其绝对值最大的负检验数的所在列的xs为进基变量。假如仍无法确定，则选最左边的变量（变量下标小者）为进基变量。,13,4、确定出基变量 其方法同线性规划，即依据最小比值法则 故确定xr为出基变量，ers为主元素。若有几个相同的行可供选择时，选最上面那一行所对应得变量为xr 。,5、旋转变换（变量迭代）。 以为主元素进行变换，得到新的单纯形表，获得一组新解，返回到第2步。,6、对求得的解进行分析 若计算结果满意，停止运算；若不满意，需修改模型，即调整目标优先等级和权系数，或者改变目标值，重新进行第1步。,14,例一、用单纯形法求解下列目标规划问题,15,= min2500/30,140/2,6
7、0/1=60 ,故 为换出变量。,16,= min700/30,20/2, =10 ,故 为换出变量。,17,= min400/15, =10 ,故 为换出变量。,18,= min,350/6,1250/6,100/1=75 ,故 为换出变量。,19,表中3115/30，说明P3 优先等级目标没有实现，但已无法改进，得到满意解 x1 60， x2 175/3， 115/3， 125/3。,20,结果分析：计算结果表明，工厂应生产A产品60件，B产品175/3件，2500元的利润目标刚好达到。 125/3，表明产品比最高限额少125/3件，满足要求。 115/3 表明甲资源超过库存115/3公斤
8、，该目标没有达到。 从表中还可以看到，P3 的检验数还有负数，但其高等级的检验数却是正数，要保证 P1目标实现，P3等级目标则无法实现。所以，按现有消耗水平和资源库存量，无法实现2500元的利润目标。 可考虑如下措施：降低A、B产品对甲资源的消耗量，以满足现有甲资源库存量的目标；或改变P3等级目标的指标值，增加甲资源115/3公斤。 若很难实现上述措施，则需改变现有目标的优先等级，以取得可行的满意解果。,21,练习：用单纯形法求解下列目标规划问题,22,= min,10/2,56/10,11/1= 5,故 为换出变量。,23,= min10/3,10,6/3,12/3= 2,故 为换出变量。,
9、24,最优解为x12， x2 4。 但非基变量 的检验数为零，故此题有无穷多最优解。 = min4 , 24 , 6= 4,故 为换出变量。,25,最优解为x110/3,，x2 =10/3。,26,1、某厂生产A、B、C三种产品，装配工作在同一生产线上完成，三种产品时的工时消耗分别为6、8、10小时，生产线每月正常工作时间为200小时；三种产品销售后，每台可获利分别为500、650和800元；每月销售量预计为12、10和6台。 该厂经营目标如下：1、利润指标为每月16000元，争取超额完成；2、充分利用现有生产能力；3、可以适当加班，但加班时间不得超过24小时；4、产量以预计销售量为准。试建立目标规划模型。,作业：,27,2、用图解法求解下列目标规划问题：,满意解为由x1 =（3， 3）, x2 =（3.5，1.5） 所连线段。,28,3、用图解法解下列目标规划模型。,x1=400, x2=0, Z=80p3,29,0,100 200 300 400 500,100 200 300 400,x2,x1,4,30,4、用单纯形法求解下列目标规划问题：,x =（10，20，10）,31,5、用目标规划的单纯形方法解以下目标规划模型。,5、x1=12, x2=10, =14, Z=14p4,32,答案：,
