《--目标规划及图解法--运筹学》由会员分享，可在线阅读，更多相关《--目标规划及图解法--运筹学（29页珍藏版）》请在金锄头文库上搜索。
1、清华大学出版社运筹学教程（第三版）运筹学基础运筹学基础胡运权 主编教 材第四章 目标规划例1产品资源A B限量1车间 2车间2 1.51 25040 单位利润 80 100求利润最大的生产方案利润 max z= 80 x1 + 100x2约束 条件2x1 + 1.5x2 50x1 + 2x2 40x1，x2 0例2由于各种原因，对例1的提出一些要求：1、B产品不超过10单位2、利润不低于1600元3、充分利用2车间的生产能力，尽量不加班。目标的含义本题三个目标依次表示为：1、B产品不超过10单位x2 =16003、充分利用2车间的生产能力，尽量不加班 。 x1 + 2x2 = 40?问题分析1
2、）问题中有些限制是必须满足的，不能有丝毫妥协 余地的，如对资源的约束：2x1 + 1.5x2 50 (1)x1 + 2x2 40 (2)这些约束条件是一种刚性约束，称之为系统约束or绝对约束问题分析2）除了前面提到的刚性约束外，例2中还提出一 些的希望达到的目标。这些要求实际上也是约 束条件，当然这些目标能到达最好，实在无法 达到也是可以接受的，我们称之为 目标约束如：1、B产品不超过10单位2、利润不低于1600元3、充分利用2车间的生产能力，尽量不加班。问题分析3）目标约束的目标一定要明确，给出确切的量值， 即目标期望值k=1,2,K目标约束系统约束目标规划的图解法例22x1 + 1.5x
3、2 50 x2 + d1- - d1+ = 1080x1 + 100x2 + d2- - d2+ = 1600x1 + 2x2 + d3- - d3+ = 40x1 ，x2 ，di-，di+ 0 ,i=1,2,3目标函数 min Z=P1 d1+ , P2 d2- , P3( d3- +d3+)约 束 条 件301020304010 2040Ox1x2d1-d1+图解法d2+d2-d3+d3-4.3 解目标规划的单纯形法4.3 解目标规划的单纯形法 目标规划的数学模型结构与线性规划的数学模型结构没有 本质的区别，所以可用单纯形法进行求解。但要考虑目标 规划数学模型的一些特点：(1) 因目标规划
4、问题的目标函数都是求最小化，所以检验 数的最优准则与我们前面讲到的线性规划检验准则是相反 的，即以所有的j0为最优准则；(2) 因为非基变量的检验数中含有不同等级的优先因子，且 Pi Pi+1，i = 1,2,L-1. 所以在判断各检验数大小时得小心；解目标规划的单纯形法计算步骤(1) 建立初始单纯形表，在表中将检验数行按优先因 子个数分别列成L行，置k=1。(2) 检查该行中是否存在负数，且对应的前k-1行的系 数是0。若有，则取其中最小者对应的变量为换入变量， 转(3)；否则，转(5)。(3) 按最小比值规则确定换出变量，当存在两个或两 个以上相同的最小比值时，选取具有较高优先级别的变量
5、为换出变量。 (4) 按单纯形法进行基变换运算，建立新的单纯形表 。 (5) 当k=L时，计算结束，表中解即为满意解。否则置 k=k+1，返回(2) 。例5 用单纯形法来解例2引入松弛变量x3 ，将例2的目标规划中约束 条件转换成线性规划标准形式，如下： Min P1d1-，P2 d2+，P3 d3- s.t. 5x1 + 10x2 + x3 = 60 x1 - 2x2 + d1- - d1+ = 0 4x1 + 4x2 + d2- -d2+ = 36 6x1 + 8x2 + d3- -d3+ = 48 x1 , x2 , x3 , di- ,di+ 0 , i = 1,2,3. Min z
6、= P1d1- + P2 d2+ + P3 d3- s.t. 5x1 + 10x2 + x3 = 60 x1 - 2x2 + d1- - d1+ = 0 4x1 + 4x2 + d2- -d2+ = 36 6x1 + 8x2 + d3- -d3+ = 48 x1 , x2 , x3 , di- ,di+ 0 , i = 1,2,3. 该目标规划和下面线性规划问题等价C 0 0 0 P1 0 0 P2 P3 0CB XBb x1 x2 x3 d1 d1+ d2 d2+ d3 d3+0P10 P3x3d1d2d360036485 10 1 0 0 0 0 0 0 1 2 0 1 1 0 0 0 0
7、4 4 0 0 0 1 1 0 06 8 0 0 0 0 0 1 1P1P2P31 2 0 0 1 0 0 0 00 0 0 0 0 0 1 0 06 8 0 0 0 0 0 0 1建立初始单纯形表C 0 0 0 P1 0 0 P2 P3 0CB XBb x1 x2 x3 d1 d1+ d2 d2+ d3 d3+ 000 0x3x1d2x21224/536/512/50 0 1 1 1 0 0 1 11 0 0 2/5 2/5 0 0 1/10 1/100 0 0 2/5 2/5 1 1 3/5 3/50 1 0 3/10 3/10 0 0 1/20 1/20P1P2P30 0 0 1 0 0
8、 0 0 00 0 0 0 0 0 1 0 00 0 0 0 0 0 0 1 0最终单纯形表最优解 X1 = （24/5，12/5）C 0 0 0 P1 0 0 P2 P3 0 CB XBb x1 x2 x3 d1 d1+ d2 d2+ d3 d3+ 000 0x3x1d2d1+208480 10/3 1 0 0 0 0 5/6 5/61 4/3 0 0 0 0 0 1/6 1/60 4/3 0 0 0 1 1 2/3 2/30 10/3 0 1 1 0 0 1/6 1/6P1P2P30 0 0 1 0 0 0 0 00 0 0 0 0 0 1 0 00 0 0 0 0 0 0 1 0O C 0 0 0 P1 0 0 P2 P3 0 CB XBb x1 x2 x3 d1 d1+ d2 d2+ d3 d3+ 000 0d3+x1d2x2126030 0 1 1 1 0 0 1 11 0 1/10 1/2 1/2 0 0 0 00 0 3/5 1 1 1 1 0 00 1 1/20 1/4 1/4 0 0 0 0P1P2P30 0 0 1 0 0 0 0 00 0 0 0
