运筹学习题(8)

3 2 1 0

1 2 3 4 5 6 x1 【例3】有如下目标规划模型 minz= p1 (d1- + d1+ )+ p1 d2-

x1≤ 6

2 x1 -x2 + d1- - d1+ =2 2 x1 -3x2 + d2- - d2+ =6 xi≤≥0; di- , di+ ≥0

试用单纯形法求其满意解，若有多个满意解，求出其中的两个出来。 解 如表5.1所示求解过程 Cj 0 0 0 xi≤ xi≤ xi≤ xi≤ CB XB 6 0 x3 6 p1 d1- 2 0 d2- 6 cj - zj p1 p2 0 x3 5 0 x1 1 0 d2- 4 cj - zj p1 p2 0 x2 10 0 x1 6 0 d2- 24 x1 x2 x3 d1- d1+ d2- d2+ 1 0 1 0 0 0 0 [2 ] -1 0 1 -1 0 0 2 -3 0 0 0 1 -1 -2 1 2 1 0 [1/2 ] 1 -1/2 1/2 0 0 1 -1/2 0 1/2 -1/2 0 0 0 -2 0 -1 1 1 -1 0 1 1 1 0 1 2 -1 1 0 0 1 0 1 0 0 0 0 0 0 4 -3 3 1 -1 cj - zj p1 0 1 1 1 p2 所以两个满意解为（1，0），（6，10）。Zmin=0

【例4】某种牌号的酒系由三种等级的酒兑制而成。已知各种等级酒的每天供应量和单位成本如下：

等级ⅰ：供应量1500单位/天，成本6元/单位； 等级ⅱ：供应量2000单位/天，成本4.5元/单位； 等级ⅲ：供应量1000单位/天，成本3元/单位； 该种牌号的酒有三种商标（红、黄、蓝），各种商标酒的混合及售价如表5.2所示。

表5.2 商 标 总制配比要求 单位售价/元 红 黄 ⅲ 少于10% ⅰ多于50% ⅲ 少于70% ⅰ少于20% 5.5 5.0 蓝 ⅲ 少于50% ⅰ多于10% 4.8

为保持声誉，确定经营目标为： p1 兑制要求配比必须严格满足； p2 企业获取尽可能多的利润；

p3 红色商标酒每天量不低于2000单位。 试对该问题建立目标规划模型；

解 设j=1,2,3分别代表红、黄、蓝三种商标的离序号，则 Xij ——第i等级酒在第j种商标酒中所占数量； yj ——第j等商标酒的生产数量 可建立目标规划数学模型如下：

minz= p1 (d1- + d1+ + d2- + d2+ + d3- + d3+ + d4- + d4++ d5- + d5++ d6- + d6+)+ p2d7- + p3 d8- y1 = X11+X21 + X31

y2= X12+X22 + X32 （产量关系约束） y3 = X13+X23 + X33

X11+X12 + X13 ≤1500

X21+X22 + X23 ≤2000 （原料限制约束） X31+X32 + X33 ≤1000 p1 X 31+ d1- - d1+=10% y1

X 11+ d2- - d2+=50% y1 X 32+ d3- - d3+=70% y2

X 12+ d4- - d4+=20% y2 （配比限制） X 33+ d5- - d5+=50% y3 X 13+ d6- - d6+=10% y3

P2 5.5 y1 +5.0 y2+4.8 y3 + d7- - d7+ =5.5×4500 (利润限制) P3 y1 + d8- - d8+ =2000 (红色商标酒产量限制)

yj ≥0, Xij≥0, dk- ,dk+≥0,(i=1,2,3; j=1,2,3;k=1,2,3,…8) 【例5】已知某实际问题的线性规划模型为 max z=100 x1 +50 x2

10x1 +16 x2≤200 (资源1) 11x1 +3 x2≥25 (资源2) x1 ，x2≥0

假定重新确定这个问题的目标为： P1 ：z的值应不低于1900； P2：资源1必须全部利用。

将此问题转换为目标规划问题，列出数学模型。

解 这是将线性规划模型转化为目标规划模型的典型例子。转化后的模型为 max z= P1d2-+ P2 d1-

10x1 +16 x2+ d1- - d1+=200 11x1 +3 x2≥25

100x1 +50x2+ d2- - d2+=1900

x1 ，x2≥0，di- , di+≥0 (i=1,2)

【例6】已知目标规划问题

min z= p1 d1- + p2d2- + p3（5d3- + 3d4- ） + p4 d1+ x1 +2x2 + d1- - d1+ =6 x1 +2x2 + d2- - d2+ =9 x1 -2x2 + d3- - d3+ =4

x2 + d4- - d4+ =2

x1 ，x2≥0，di- , di+≥0 (i=1,2,3,4)

(a) 分别用图解法和单纯形法求解； (b) 分析目标函数分别变为①、②两种情况时（②中分析ω1 ，ω2 的比例变动）解的变 化。 ① min z= p1 d1- + p2d2+ + p3 d1++ p4（5d3+ + 3d4- ） ② min z= p1 d1- + p2d2+ + p3（ω1d3+ + ω2 d4- ）+ p4d1+

x2

5 d2+ 4

d2- 3

d4d3- + d1 +2

A d1- d4- d3+ 1 B 0

2 4 6 8 x1

图5.2 解 （a）如图5.2所示，用图解分析可得出满意解为A(13/2,5/4)，zmin =3 p3 d4- + p4 d1+，其中 d4- =3/4,d1+ =-3。其单纯形算法的单纯形表如表5.3所示。

（b）①当目标函数变为minz= p1 d1- + p2d2+ + p3 d1++ p4（5d3+ + 3d4- ）时，图上分析，其满

意解应在B点。用单纯形法可做灵敏度分析，如表5.4所示。其满意解为x1 =5，x2 =1/2。 ③ 当目标函数变为minz= p1 d1- + p2d2+ + p3（ω1d3+ + ω2 d4- ）+ p4d1+ 时，用单纯 形 法做灵敏度分析，如表5.5所示。 可见，当

1、 ω1 / ω2≥1/4（ω1 ，ω2 ）0 ）时，满意解为，x1 =13/2，x2 =5/4。 2、 ω1 / ω2≤1/4（ω1 ，ω2 ）0 ）时，满意解为，x1 =5，x2 =2。

表5.3 Cj 0 0 p1 p4 0 p2 5p3 0 3 p3 0 CB XB 6 p1 d1- 6 0 d2- 9 5p3 d3- 4 3p3 d4- 2 cj - zj p1 p2 p3 p4 p1 d1- 2 x1 x2 d1- d1+ d2- d2+ d3- d3+ d4- d4+ 1 2 1 -1 0 0 0 0 0 0 1 2 0 0 1 -1 0 0 0 0 1 -2 0 0 0 0 1 -1 0 0 0 [1 ] 0 0 0 0 0 0 1 -1 -1 -2 1 1 -5 7 5 3 [1 ] 0 1 -1 0 0 0 0 -2 2 0 d2- 5 5p3 d3- 8 0 x2 2 cj - zj p1 p2 p3 p4 0 x1 2 0 d2- 3 5p3 d3- 6 0 x2 2 cj - zj p1 p2 p3 p4 0 x1 5 0 d2- 3 3p3 d4- 3/2 0 x2 1/2 cj - zj p1 p2 p3 p4 0 x1 13/2 p4 d1- 3 3p3 d4- 3/4 0 x2 5/4 cj - zj p1 p2 p3 p4 1 0 0 0 1 -1 0 0 -2 2 1 0 0 0 0 0 1 -1 2 -2 0 1 0 0 0 0 0 0 1 -1 -1 1 2 -2 1 -5 7 5 -7 10 1 0 1 -1 0 0 0 0 -2 2 0 0 -1 1 1 -1 0 0 0 0 0 0 -1 1 0 0 1 -1 [4] -4 0 1 0 0 0 0 0 0 1 -1 1 5 -5 1 5 -17 20 1 1 0 1/2 -1/2 0 0 1/2 -1/2 0 0 0 0 -1 [1 ] 1 -1 0 0 0 0 0 0 -1/4 1/4 0 0 1/4 -1/4 1 -1 0 1 1/4 -1/4 0 0 -1/4 1/4 0 0 1 1 3/4 -3/4 17/4 3/4 3 1 1 0 0 0 1/2 -1/2 1/2 -1/2 0 0 0 0 -1 1 1 -1 0 0 0 0 0 0 0 0 -1/4 1/4 1/4 -1/4 1 -1 0 1 0 0 1/4 -1/4 -1/4 0 0 0 1 1 3/4 -1/4 17/4 3/4 3 1 -1 1 表5.4 0 0 p1 p3 0 p2 5p4 0 3 p4 0 x1 x2 d1- d1+ d2- d2+ d3- d3+ d4- d4+ 1 0 0 0 1/2 -1/2 1/2 -1/2 0 0 0 0 -1 1 [1 ] -1 0 0 0 0 0 0 0 0 -1/4 1/4 1/4 -1/4 1 -1 0 1 0 0 1/4 -1/4 -1/4 1/4 0 0 1 1 1 -1 1 3/4 -3/4 17/4 3/4 3 1 0 1/2 -1/2 0 0 1/2 -1/2 0 0 Cj CB XB 6 0 x1 13/2 p3 d1+ 3 3p4 d4- 3/4 0 x2 5/4 cj - zj p1 p2 p3 p4 0 x1 5 0 d2- 3 0 0 -1 1 1 -1 0 0 0 0 3p4 d4- 3/2 0 0 -1/4 1/4 0 0 1/4 -1/4 1 -1 0 x2 1/2 0 1 1/4 -1/4 0 0 -1/4 1/4 0 0 cj - zj p1 p2 p3 p4 1

1 1 3/4 -3/4 17/4 3/4 3

表5.5 0 0 p1 p4 0 p2 ω1p3 0 ω2p3 0 x1 x2 d1- d1+ d2- d2+ d3- d3+ d4- d4+ 1 0 0 0 1/2 -1/2 1/2 -1/2 0 0 0 0 -1 1 1 -1 0 0 0 0 0 0 0 0 -1/4 1/4 [1/4 ] -1/4 1 -1 0 1 0 0 1/4 -1/4 -1/4 0 0 0 0 0 p1 p4 0 p2 ω1p3 0 ω2p3 0 1 1 ω2 /4 -ω2 /4 4ω1-ω2 /4 ω2 /4 ω2 /4 ω2 1 -1 1 1 0 0 0 1 -1 0 0 -2 2 0 0 -1 1 1 -1 0 0 0 0 0 0 0 0 -1 1 1 -1 4 -4 0 1 0 0 0 0 0 0 1 -1 1

1 ω1 -ω1 ω1 ω2 -4ω1 4ω1

1 -1 1 Cj CB XB 6 0 x1 13/2 p4 d1+ 3 - ω2p3 d43/4 0 x2 5/4 Cj cj - zj p1 p2 p3 p4 0 x1 5 p4 d1+ 3 - ω1p3 d33 0 x2 2 cj - zj p1 p2 p3 p4 第五章 整数规划习题

5.1 考虑下列数学模型

minz?f1(x1)?f2(x2) 且满足约束条件

（1）或x1?10，或x2?10； （2）下列各不等式至少有一个成立：

?2x1?x2?15??x1?x2?15?x?2x?152 ?1

x?x2?0（3）1或5或10 （4）x1?0，x2?0

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库运筹学习题(8)在线全文阅读。