运筹学复习题

一.非标准形式化为标准

例1:下列线性规划问题化为标准型。(10分)

''''1、 minZ??x1+5x2-2x3 max(-z)=x1?5x2?2(x3?x3)

x1?x2?x3?62x1?x2?3x3?5x1?x2?10

满足

x1?0,x2?0,x3符号不限

二.用单纯形法求解线性规划的最优解

例1:1、某工厂拥有A,B,C三种类型的设备,生产甲、乙两种产品,每件产品在生产中需要使用的机时数,每件产品可以获得的利润,以及三种设备可利用的机时数见下表:

求:(1)线性规划模型;(5分) (2)利用单纯形法求最优解;(15分)

maxz?1500x1?2500x2答案:1. 解:(1)

3x1?2x2?65

满足 (2)

cB2x1?x2?40

x1,x2?0

xB3x2?75 b '1500 2500 x10 x30 x40 x5 ? x2 0 0 0 ?z x3x4x5 65 40 75 0 3 2 0 2 1 [3] 1 0 0 0 0 1 0 0 0 0 1 0 32.5 40 25 1500 2500 1

0 0 x3x4 15 15 [3] 2 0 0 0 1 0 0 0 1 0 1 0 0 0 1/3 -2/3 0 0 1 0 0 0 1 0 -2/3 -1/3 1/3 -2500/3 -2/9 1/9 1/3 -500 5 7.5 _ - _ _ _ 2500 x2 25 ?z -62500 1500 1 0 0 0 1500 x1 5 0 2500 ?z x4x2 5 25 -70000 T-500 0

最优解

x?(5,25,0,5,0)* 最优目标值 = 70000元

三.线性规划原问题如下,请写出对应的对偶模型

Smax?2x1?5x2

?x1?4??x2?3 ?x?x?82?1?x,x?0?12

Smin = 4y1+3y2+4y3

y1+y3≥2

y2+y3≥5

y1, y2, y3≥0

例2:写出下列问题的对偶问题 (10分)

minZ?4x1?2x2+3x3

4x1+5x2?6x3=7满足

答案:

8x1?9x2?10x3?1112x1?13x2?14x1?0,x2无约束,x3?0

maxW=7y1?11y2?14y3

2

四.灵敏度分析

?maxz?3x1?3x2?x1?x2?4???x1?x2?2??6x?2x?1812?x1?0,x2?0??

例1::用单纯形法求解

;并对以下情况作灵敏度分析:(1)求c2?5?的变化范围;(2)若右边常数向量变为b??2?,分析最优解的变化。

???20?

1、解:

加入人工变量,化问题为标准型式如下:

maxz?3x1?3x2?0x3?0x4?0x5?x1?x2?x3?4???x1?x2?x4?2s.t??6x1?2x2?x5?18?x,x,x,x,x?0?12345 (3分)

下面用单纯形表进行计算得终表为:

3 c j3 x2 0 x3 0 x4 0 x5CB 基 x3 x4 x1 cj?zj b x1 0 0 3 1 5 3 0 0 1 0 2/3 4/3 1/3 0 1 0 0 0 0 1 0 0 -1/6 1/6 1/6 -1/2 (5分) 所以原最优解为 X*?(3,0,1,5,0)T (2分)

3

(1)设c2变化?,将c2得变化带入最终单纯形表得c2的变化范围为c2?1;

(5分)

?5?(2)若右边常数向量变为b??2?,将变化带入最终单纯形表得:最优基解不

???20?变,最优解的值由(3,0)T变为(10/3,0)T。 (5分)

例2:考虑如下线性规划问题(24分) Max z=-5x1+5x2+13x3 s.t. -x1+x2+3x3≤20

12x1+4x2+10x3≤90 x1,x2, x3≥0

回答以下问题: 1)求最优解

2)求对偶问题的最优解

3)当b1由20变为45,最优解是否发生变化。

4)求新解增加一个变量x6,c6=10,a16=3,a26=5,对最优解是否有影响 5)c2有5变为6,是否影响最优解。 答:最优解为 1) Cj CB 0 0 Cj-Zj 13 0 Cj-Zj 13 5 X3 X5 X3 X2 20/3 70/3 185/33 35/11 XB X4 X5 b 20 90 -5 X1 -1 12 -5 -1/3 46/3 5 X2 1 4 5 1/3 22/3 13 X3 3 10 13 1 0 0 1 0 0 0 X4 1 0 0 1/3 -10/3 -13/3 2/11 -5/11 -1/11 0 X5 0 1 0 0 1 0 -1/22 3/22 -1/11 θ 20/3 9 20 70/22 -2/3 2/3 -34/33 0 23/11 1 -68/33 0 最优解为X1=185/33, X3=35/11 2)对偶问题最优解为

Y=(1/22,1/11,68/33,0,0)T 3)

当b1=45时 X= 45/11 -11/90 由于X2的值小于0,所以最优解将发生变化 4)P6’=(3/11,-3/4)T σ6=217/20>0

所以对最优解有影响。 5)当C2=6

4

联系客服:779662525#qq.com(#替换为@)