运筹学复习题

一．非标准形式化为标准

例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

σ1=-137/33

σ4=4/11 σ5=-17/22

由于σ4大于0所以对最优解有影响

五．运输问题

例1：某建材公司所属的三个水泥厂A1,A2,A3生产水泥运往四个销售点B1,B2,B3,B4。已知各水泥厂的日产量（百吨），各销售点的日销售量（百吨）以及各工厂到各销售点的单位运价（百元/百吨）如表所示，问该公司应如何调运产品，在满足各销售点销量的前提下，使总运费为最小？ 销地 产地 A1 A2 B1 B2 B3 B4 产量 10 90 40 7 7 4 20 8 4 2 30 3 5 9 40 2 1 6 50 A3 销量 解：用伏格尔法得到初始方案如下 销地 产地 A1 B1 B2 B3 B4 产量 2 10 行位势 7 8 10 3 0 A2 7 4 20 20 4 20 30 2 10 4 30 2 5 50 9 40 3 50 -1 1 90 2 A3 6 40 0 销量 列位势 用位势法进行检验 令u1?0由u1?v3?3得v3?3；

由u2?v3?5得u2?2；由u2?v2?4得v2?2

5

V1 (5,0) (3,3) (3,3)

VS （4,1） V2

(4,0) (9,3)

(8,4)

V3 Vt (6,0) 最大流为：14

V1 (5,3) (3,3) (3,0) V2 Vs (4,4) (4,1) (9,7) (8,8) Vt V3 (6,6)

7. 求如图所示的网络的最大流和最小截集(割集)，每弧旁的数字是（cij , fij ）。（10分） V1 (4,4 ) V3

(9,5) (6,3)

VS (3,1) (3,0) (4,1) Vt

(5,3) (7,5) V2 (5,4) V4

解：

V1 (4,4) V3 (9,7) (6,4) (3,2) (4,0) Vs Vt (5,4) (7,7)

V2 (5,5) V4 最大流＝11

11

本文来源：https://www.bwwdw.com/article/z9x8.html