运筹学复习例题

1.某制药厂在计划期内要安排生产I、II两种药品，这些药品分别需要在四种不同的设备

上加工.按工艺规定，每千克药品I和II在各台设备上所需要的加工台时数如表1.已知各

设备在计划期内有效台时数（1台设备工作1小时称为1台时）分别是12.8、16和12.该制

药厂每生产1千克药品I可得利涧200元，每生产1千克药品II可得利润300元.

衰1A、B两种药品每千克在各台设备上所需的加工台时数

药品4BCD

I2140

II2204

（1）问应如何安排生产计划，才能使制药厂利润最大？分别利用软件和最终

单纯型表回答剩余问题。

解设口，口分别表示在计划期内药品I和II的产量（千克），口表

示这个期间的制药厂利润.则计划期内生产I,II两种药品的利润总额为口

（元）.但是生产I、II两种药品在口设备上的加工台时数必须满足口；在口设

备上的加工台时数必须满足口；在口设备上的加工台时数必须满足口；在口设备

上的加工台时数必须满足口；生产I、II两种药品的数量应是非负的数，即口.于

是上述的问题归结为：

目标函数Max7=200^+300x2

’2工1+2X2<12

$+2X2<8

约束条件<4x,<16

4X2<12

、xpx2>0

单纯型法求解：

首先将线性规划问题标准化，即在约束条件中引入松弛变量、、

、，则标准化后的线性规划模型为：

MaxZ-200Aj十300A2

2X1+2X2+x3=12

X)+2占+=8

s.t.《尤1+x5=16

4々+X6=12

1内,12,…，工6NO

此时约束方程组已为典型方程组，根据上述线性规划模型可以列出初始单纯形

表(表2-4):

表2-4单纯形法求解例27(1)

Cj2003000000

be

X1%*3匕X%

XB\5

0巧221000126

012010084

%

0X540001016

0

*60[4]0001123

2003000000Z=0

表2-4中：为典型方程组中变量的系数，为规划中出现的变

量，为变量在目标函数中的系数，为基本变量，为基本变量在目标函数

中的系数，为典型方程组右端常数项(非负值)，为确定出基变量的商值，

(),为变量的检验数，，为此时目标函数值，.

根据初始单纯形表可以看出：

初始基本可行解是，，，，，

。2、

Q

此时目标函数值Z=（o000）-,=0

16

□

，2、

检验数C=G—Gr<=200—（0000）-4=200

O

—/、2

c

2=C2-CS-P2=300-（0000）-=300

4

C3=C4=C5=C6=0（基本变量的检酚数总等于零）

由于，，所以初始基本可行解非最优解.又由于，所以确定为进

基变量.

进一步求最小值:

b.128

min也}=mm%>0"=min<,,=min{6,4,3}=3

PikT2TJ

即从第4个方程中算出的商值最小，而第4个方程中的基本变量是，于

是为出基变量.表中给第4个约束方程中的系数4加上方括号以突出其为枢

元.

接下去的工作是将取代，表2-4中的约束方程化为以、、和

为基本变量，和为非基本变量的典型方程，以便求出新的基本可行解.从

表2-4中可以看到，只需对方程组实行初等变换，使枢元位置变成1,而枢列中

的其它元素变为零（即以枢元为中心的初等变换）就可以了.

此处可先将第4人方程除以4,使枢元位置变成1；然后用新得到的第4个

方程乘以（-2）后分别加到第1个和第2个方程上，使枢列中的第1个和第二个

方程所在位变为零.这样我们可以得到新的单纯形表（表2-5）.

表2-5给出的新的基本可行解是=0,=3,=6,=2,=16,

=0

’6、

2

此时目标函数值Z=(o00300)-=900

16

，2、

检验数弓=q-品，片二？。。-。)00300)-=200

3D1

/

z>

f1

I-

一

'2

1

-

OO3'一

2

。6=。6-或•乙=0一(°)0'

0)

'1

•-

I-

4>

XI

c2=C3=C4=C5=0(基本变量的检验数总等于零)

表2-5单纯形法求解例27(2)

2003000000

CJ

h0

X]XxxX,x

X2346

0X20100_163

32

0[1]0010.122

乙2

0%400010164

30001000£3

x24

2000000-75Z=900

由于，所以此时基本可行解非最优解，确定为进基变量.

进一步计算最小值：

min{2}—min->0■—min--,—、一min{3,2,4}-2

.Bik.214,

即从第2个方程中算出的商值最小，而第2个方程中的基本变量是，于

是为出基变量.

接着进行第二次迭代，将取代，表2-5中的约束方程化为以、、

和为基本变量，和为非基本变量的典型方程，以便求出新的单纯形

表.重复单纯形法计算第2步〜第5步，一直到没有新的非基本变量可以改善

目标函数为止(见表2-6和表2-7).

表2-6单纯形法求解例27(3)

CJ2003000000

be

巧xxxxx

X23456

0修001-20124

2

20010010_12

再2

0X5000-41[2]84

300010001312

4

000-200025Z=1300

表2-7单纯形法求解例2-1(4)

Cj2003000000

b0

CB

X]xxxXjx

XB\2346

0001-1-100

•q4

2001000104

再4

0000-2114

%2

300X01o1.102

228

000-150_250Z=1400

2

表2-7中:

4

目标函数值Z=(O2000300)-=1400

4

0

检验数Oc4—g-=0-(()2000300)-=-150

-2

<2>

▲

4

1

4一

-

C=C-C„«B=0-(02000300)-1225

5

2一

4

==

C]=C2=C3C60(基本变量的检验数总等于零)

由于，，所以此基本可行解，，，，，，即为最优解，最优值

为Z*=1400.与前面图解法求解结果一致.为了加深对单纯形法基本思想的理

解，不妨将表2-4.表2-5.表2-6.表2-7和图27进行对照，可以发现表2-4给

出的基本可行解对应于图中可行域顶点0,表2-5给出的基本可行解对应于顶点

,表2-6给出的基本可行解对应于顶点，表2-7给出的最优解对应于顶点

.线性规划问题有无穷多个可行解，应用单纯形法可以高效率地求解此类问

题.

（2）药品II的价格在什么范围内变动，不影响原天的生产计划安排，但制药厂收益变

化了.

设基本变量在目标函数中的系数变化了；这时表2-7的最终计算表便成为

表2-16所示.

表276基本变量利润系数变化的灵敏度分析

2000000

%300+AC2

xb

CB

匹W工3Z&4

00011_100

马4

2001000104

再4

0000-2114

勺2

390+ACX0101_102

2228

000-15O--Ac,--+-AC0Z=1400

2~282-

+2AC2

这时要保持最优解不变，则必须满足下列不等式:

-1

°1

-150-（（）00\c2）_2=-150--AC2<0

1

[2>

_!

-4

£

■y-（000AcJ4

2

2

2

<-8>

-300<Ac*2<100

即可在［0,400］间变动，不影响原来的生产计划安排，但制药厂收益变化了.

(3)设备C在计划期内有效台时数在什么范围内变动时，原来最优解的基本变量不变,

但最优解的值发生变化.

第三个约束条件发生变化，变化量为，为了使最后的解仍为可行

解，应满足下列不等式：

1、

1--△

。）、1-43

-1。41

1A

4-3

o-4

41

1

4-12-△

o-23

一2

21

-

仇J

O^-△

88.Z

4+—及）3

>0

4+g△/

2千打

V0

A/?3>-16

地--8

△d-16

-8<A/J3<0

所以在［—8,0］之间变动时（即的变化范围在［8,16］时），原来最优解

的基本变量不变，但最优解的值发生变化.例如，为一2时（即=14）,则

-

2

7

-

2

3

9

-

4

表2-17右端常数变化后的最优解

ci2003000000

Xb0

%”2*3“416

0001-1_10

42

1000107

20041

42

0%6000-2113

2

3000101_109

兀1284

3000-150_25oZ=1375

2

如果的变化超出了［-8,0］的范围，这时最优解的基本变量就发生变化.

在这种情况下要用时偶单纯形法继续求出新的最优解.

例如为2时（即=18）,贝I」

i--

2

9

4+0-

b'=b'+B7&b=2

45

07

a-

4

0

则最终单纯形表变为表2-18.

表2-18右端常数变化后的对偶单纯形法求解

2003000000

CJ

Xb

CB

X

X2£6

0001-1(_；)0

X3~2

2001000109

1142

0000-2115

42

3000101_107

匕284

000-150—至0Z=1425

2

015050

000-44102

%

200101-1004

再

0002-4014

%

30001_11002

2

300-50-10000Z=14()0

新的最优解*=,最优值Z*=1400.

(4)若计划生产的药品I的工艺结构有了改进，相应地生产单位药品I所

需设备的台时改为（3,2,5,2）,它的利润也提高到每千克400元.试分析已

求得的最优计划有何变化？

解当范的系数列向量变化后，原最终单纯形表（表2-7）中》的系数列向

量变成：

（1、

1-1——0

4/5

-

_00-094

邛二夕由二4一1

-

2

3

-

原最终单纯形表变成表2-19:

表2T9决策变量系数改变对最优解的影响（1）

ci4003000000

\

CBb

占x2x3x4x5x6

0

0X4IT00

3、4」

400070

400%4

44

\o0-211

0“64

3002101-102

x

2828

£

由的系数列向量可知，到此尚未完成行变换，所以需继续使的系数列向量

变成单位列向量，于是得到表2-20.

表2-20决策变量系数改变对最优解的影响（2）

ci4003000000

b

CB

X占入2X3%工6

0001-1_104

15」5

40010001016

*5~5

12

0X000-2£1

65T

4

300X0101_10

2255

()00-150-200Z=1520

因为0,所以新的最优解，最优值*=1520元.

（5）设该制药厂除生产药品I、II以外，还有第三种药品可供选择.

生产药品III每千克需要使用设备的台时分别为3,2,6,3；每千克可得利润

500元.问该制药厂的计划中要不要安排这种药品的生产，若要安排，应当生

产多少？

解设口表示计划期内生产药品川的数量（单位为千克），则原最

终单纯形表（表2-7）中增加了一列，这新的一列为：

\_、

1-10\

-43、\_

]_~2

30002

==4—

26

0-21

23

2

00

2"81

将新增一列列入原最终单纯形表中，计算检验数，见表2-21.由于此时相应的检脸数

为正值，所以此单纯形表给出的基本可行解不是最优解，继续用单纯形法求解结果，最后

得最优解，最优值*=1650元，比原计划增加了利涧250元.

表2-21增加变量的灵敏度分析

2003000000500

Cj

\b0

X?巧工4工51617

0001-1-10.10

42

200looolo248

演423

0000-211[2]42

%2

3000101-10128

12284

000-150_250125Z=1400

2

0ooi-2-llo1

284

200Ioo2_1_2o1

284

500000-11112

42

300o1o2_2_1o3

41682

000-25_1Z50Z=1650

42

（6）若制药厂为了提高药品质量，考虑给药品I、II增加一道精加工工序、并在设备

上进行.I、II两种药品分别需要的加工台时数为（2,2.4）.已知设备的计划工作时间

为12个台时，试问增加一道精加工工序后，对原计划有何影响？

解上述问题相当于在原问题的基础上增加了一个约束条件

<12

2x}+2.4X2

设为新增的松弛变量，则得到

2.+2AX2+X7-12

原最终单纯形表（表2-7）新增一行和一列，见表2-22.此时原最终单纯形表中

的和的系数列向量不再是单位向量了，所以继续进行行变换.在行变换后

得到的新单纯形表中，检脸数均小于等于零，但右端项出现负值，所以可用对

偶单纯形法继续运算.最后得最优解，最优值*=1350元.

表2-22增加约束条件的灵敏度分析

0

%2003000000

\b

CB

X|x2“3工4”5”6”7

0001-1-1000

4

20010001004

阳4

0000-21104

工62

3003101_1002

28

0X?21200c)0112

5

0001-1_1000

4

20010001004

再4

0000-21104

%2

3000101_1002

工228

0000_6_1o14

55~5

000-150_2500

百2

0125125

2

0001100_51

24

200100.20013

再24

0工000-50152

62

3000105005

482

0%000610-54

V

2.某医院有一批长度为15分米的胶皮管原料.为了作输液管、止血带和听诊器

胶管，需要截成长度分别为5.7分米，4.2分米和3.1分米的短管各100根，100

根和200根.试问应如何安排截法，所用的胶管原材的总根数最少，而且每根

料头不能超过2分米？

解先分析一下截取短管的方法.如果先考虑尽输液管截，然后考虑尽止血带

截，再考虑尽听诊器胶管截，则截取的方法如下表2-23:

表2-23短管截取方去

输液管止血带听诊器胶管

截法5.7（分米）4.2（分米）3.1（分米）总长（分米）料头（分米）

120114.50.5

212014.10.9

311113.02.0

410315.00.0

502214.60.4

601313.51.5

为了得到短管5.7分米100根，4.2分米100根和3.1分

米200根，需混合截取原料.令表示第种截法所用原材的根数，得到如下

线性规划模型：

6

MinZ=Zxj

'21]+x2+x3+x4=100

2X2+xy+2X5+x6=100

s.t.<

+当+

A13X4+2X5+3xb=200

<,且为整数

在，述约束条件中添加人工变量、、，得到其典型方

程组:

MinZ=ZXj+Mx?