2024年4月21日发(作者：淦冰冰)

运筹学习题答案

第一章（39页）

1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最 优

解、无界解还是无可行解。

（1） max

z

=论

x

2

5

x

1

+10

x

2

<50

x

1

+

x

2

_ 1

x

2

_4

为，

X

2 _0

（2） min z=

x

1

+1.5

x

2

x-

i

+3

X

2

_3

x-

i

+

x

2

丄 2

x-

i

，

x

2

亠 0

（3） max z=2

x

1

+2

x

2

x-

1

-

x

2

_-1

-0.5x-

i

+

x

2

-2

x-

i

，

x

2

-0

（4） max z=

x

j

+

x

2

x-

i

-

x

2

-0

3

X

r

_

X

2

__3

x

1

，

x

2

-0

解：

（1） （图略）有唯一可行解，max z=14

（2） （图略）有唯一可行解，min z=9/4

（3） （图略）无界解

（4） （图略）无可行解

1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。

(1) min 2=-3捲+4乂

2

-2乂

3

+5乂

4

4

X

i

-

X

2

+2

X

3

-

X

4

=-2

x-

i

+

x

2

+3

x

3

- < 14 -2 x-

i

+3

x

2

-

x

3

+2

x

4

亠 2

x

-

,

X

2

,

X

3 _0

,

X

4

无约束

n m

J 二、、'

i =1 k 4

a

ik

x

ik

m

为

-X

k

= -1( =1,…,n)

k 4

x

ik

丄0 (i=1 …n; k=1,…,m)

(1)解：设 z=-z ,

X

4

=

X

5

-

X

6

,

X

5

,

X

6

_0

标准型：

Max z =3

x

1

-4

x

2

+2

x

3

-5(

x

5

-

x

6

)+0

x

7

+0

x

8

-M

x

9

-M

x

10

s. t .

-4

x

1

+

x

2

-2

x

3

+

x

5

-

x

6

+

x

10

=2

x-

i

+

x

2

+3

x

3

-

x

5

+

x

6

+

x

7

=14

-2 x-

i

+3

x

2

-

x

3

+2

x

5

-2

x

6

-

x

8

+

x

9

=2

X

,

X

2

,

X

3

,

X

5

,

X

6

,

X

7

,

X

8

,

X

9

,

-0

X

10

初始单纯形表

：

Cj T

C

B

X

B

3

b

X

-4

X

2

2

X

3

-5

X

5

5

X

6

0

X

7

0

X

8

-M

X

9

-M

e

X

10

-M

X

10

2

X

7

-4

1

1

1

-2

3

1

-1

-1

1

0

1

0

0

0

0

1

0

2

14

0

14

-M

X

9

r

2

-2

[3]

-1

2

-2

0

-1

-M

1

0

0

0

2/3

-z

4M 3-6M 4M-4 2-3M 3M-5 5-3M

0

(2)解：加入人工变量

X

i

,

X

2

,

X

3

,…

X

n

，得:

n m

Max s=(1/

p

k

)二 二

ik

x

ik

-M

x

1

-M

x

2

-…..-M

x

n

i=1 7

s.t.

m

x

+ 迟

X

ik

=1

k=4

(i=1,2,3…,n)

(i=1,2,3…n; k=1,2….,m)

x

k

兰0,

X

j

20,

C

B

M是任意正整数 初始单纯形表：

-M •

a

如/

12/

C

j

…

M M

/ P

k

/ P

k

b

…

H rn/^

/ P

k

…

a

n1/

/P

k

X

n1

a

n2/

/ P

k

…

a

mn

0i

X

B

X

1

X

2

X

n

X

11

X

12

X

1m

X

n2

X

nm

-M

-M

…

-M

-s

X

1

X

2

1

1

…

1

n

M

1 0

0 1

… …

0 0

0 0

•

…

0 1

•

0

…

…

… …

•

1 0

…

1

0

…

0

%+M

•

…

0

0

0

…

1

%+

M

•

…

0

…

X

n

•

…

… …

•

0

…

0

…

1

•

0

…

… …

•

1

…

0

%枷

陥/

/ 4

-+M

%+

M

7和

1.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行 解，并代入目标函

数，确定最优解。

(1) max z=2

x

4

+3

x

2

+4

x

3

+7

x

4

2

x

4

+3

x

2

-

x

3

-4

x

4

=8

X

1

-2

X

2

+6

x

3

-7

X

4

=-3

(2) max z=5

x

1

-2

x

2

+3

x

3

-6

x

4

X

1

,

X

2

,

X

3

,

X

4

-0

x

1

+2

x

2

+3

x

3

+4

X

4

=7

2

x

1

+

x

2

+

x

3

+2

X

4

=3

x

1

x

2

x

3

x

4

_0

(1) 解：

系数矩阵A是：

2

*

3-1^

_2 6 —7 一

令 A=(

R

,

P

2

,巳,

P

4

)

P

与卩

2

线形无关，以(

R

,

P

2

)为基，捲,

X

2

为基变量。

有 2

X

!

+3

x

2

=8+

x

3

+4

x

4

x-

i

-2

x

2

=-3-6

x

3

+7

x

4

令非基变量

X

3

，

X

4

=0

解得：捲=1;

x

2

=2

基解X

=( 1, 2, 0, 0

)

为可行解

(

1

)

T

乙=8

同理，以(

P

，巳)为基，基解X

⑵

=(45/13, 0,-14/13, 0

)

是非可行解； 以(

P

, R )为基，基解

T

X=(34/5, 0, 0, 7/5

)

T

是可行解，

Z

3

=117/5； 以(

F

2

,巳)为基，基解 X

⑷

=(0, 45/16, 7/16, 0

)

是

(3)T

可行解，

Z

4

=163/16； 以(

P

2

,

P

4

)为基，基解X

⑸

=(0, 68/29, 0, -7/29

)

是非可行解；

T

以(

P

4

,巳)为基，基解X

=(0, 0, -68/31, -45/31

)

是非可行解；

(6)T

最大值为

Z

3

=117/5;最优解 X

⑶

=(34/5, 0, 0, 7/5

)

。

T

(2) 解：

系数矩阵A是：

12 3 4

$112-

令 A=（

R

,

P

2

,巳,

P

4

）

R

,

P

2

线性无关，以(

P

i

,

P

2

)为基，有:

x-

i

+2

X

2

=7-3

x

3

-4

x

4

2

X

1

+

X

2

=3-

X

3

-2

X

4

令

X

3

,

X

4

=0 得

X

-

I

=-1/3,

X

2

=11/3

基解 X

= (-1/3,11/3, 0, 0

)

为非可行解；

(1)T

同理，以(

P

,

P

j

)为基，基解 X

= (2/5, 0, 11/5, 0

)

是可行解

Z

2

=43/5;

(2)T

以(

P

, R )为基，基解X

⑶

=(-1/3, 0, 0, 11/6

)

T

是非可行解；

以(

P

2

,

P

j

)为基，基解X

⑷

=(0, 2, 1, 0

)

是可行解，

Z

4

=-1；

T

以(

P

4

,

P

j

)为基，基解 X

=(0, 0, 1, 1

)

是

Z

6

=-3

；

(6)T

最大值为

Z

2

=43/5;最优解为X⑵=(2/5, 0, 11/5, 0

)

。

T

1.4分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每一步

相当于图形的哪一点。

（1） max

Z

=2

X

1

+

X

2

3

X

1

+5

X

2

乞 15

6

X

1

+2

x

2

虫24

X

1

,

X

2

-0

（2） max

Z

=2

X

1

+5

X

2

X

<^4

2

x

2

辽 12

3

X

1

+2

X

^

18

X

-

I

,

X

2

-0

解：（图略）

（1） max z=33/4 最优解是

（

15/4,3/4） 单纯形法：

标准型是 max z=2 为 +

x

2

+0

x

3

+0

x

4

s.t. 3

x

!

+5

x

2

+

x

3

=15

6捲 +2

X

2

+

x

4

=24

X

i

,

X

2

,

X

3

,沧

—0

单纯形表计算：

C

j

C

B

X

B

X

3

X

4

2

b

15

24

0

3

4

-8

3/4

15/4

-33/4

X

1

1

X

2

0

X

3

0

X

4

4

0

0

3

[6]

2

0

1

0

0

1

0

5

1

0

0

1

0

0

1/4

-1/12

-1/12

0

1

5

4

2

1

[4]

1/3

1/3

1

0

0

-z

0

2

X

3

X

1

0

-1/2

1/6

3/4

12

-z

1

2

X

2

X

1

-1/3

-1/8

5/24

-7/24

-z

解为：（15/4, 3/4, 0, 0

）

T

Max z=33/4

迭代第一步表示原点；第二步代表 C点（4, 0，3，0

）

；

T

第三步代表B点（15/4，3/4，0，0

）

。

T

（2）解：（图略）

Max z=34 此时坐标点为（2，6）

单纯形法，标准型是：

s.t.

x

1

+

x

3

=4

Max z=2

x

1

+5

x

2

+0

x

3

+0

x

4

+0

x

5

2

X

2

+

X

4

=12

3

X

-

I

+2

X

2

+

X

5

=18

X

i

,

X

2

,

X

3

,

X

4

,

X

S

-0

俵略)

最优解 X= (2, 6, 2, 0, 0

)

T

Max z=34

迭代第一步得X

(1)

= (0, 0, 4, 12, 18

)

T

表示原点，迭代第二步得X

⑵

=(0, 6,

4, 0, 6

)

T

，第三步迭代得到最优解的点。

1.5以1.4题(1)为例，具体说明当目标函数中变量的系数怎样变动时，满足约

个顶点，都可能使得目标函数值达到最优。

解：目标函数： max z=C|

X

1

+

c

2

X

2

(1) 当 C

2

=0 时

X

2

=- ( &/

c

2

)

X

1

+z/

c

2

其中，k=_G/

c

2

k

AB

=-3/5 ,

k

Bc

=-3

k「k

Bc

时，

c

1

, 9 同号。

当

C

2

・、0时，目标函数在C点有最大值

当cr 0时，目标函数在原点最大值。

k

B

C

- k-

k

A

B

时，

c

1

, $ 同号。

当

C

2

0,目标函数在B点有最大值；

当cr 0, 目标函数在原点最大值。

k

A

B

- k - 0

时，

c

1

,

c

2

同号。

当c^ 0时，目标函数在A点有最大值

当

c

2

0时，目标函数在原点最大值。

k -0时，

C

l

, °异号。

束条件的可行域的每一

当

C2,

0,

C

l

- 0时，目标函数在A点有最大值；

当

C

2

0,

C

l

0时，目标函数在C点最大值。

k=

k

AB

时，q,

C

2

同号

当

C

2

・、0时，目标函数在AB线断上任一点有最大值

当C

2

- 0,目标函数在原点最大值。

k=

k

B

C

时，

C

l

，

C

2

同号。

当

C2-

0时，目标函数在BC线断上任一点有最大值

当C

2

- 0时，目标函数在原点最大值。

k=0 时，

C

l

=0

当

C

2

・、0时，目标函数在A点有最大值

当

C

2

■ 0，目标函数在OC线断上任一点有最大值

（2）当

C

2

=0 时，max z=

C

l

x

i

C

1

-0时，目标函数在C点有最大值

C

l

0时，目标函数在OA线断上任一点有最大值

C

l

=0时，在可行域任何一点取最大值。

1.6分别用单纯形法中的大 M法和两阶段法求解下列线性问题,

解。

（1）max z=2

x

1

+3

x

2

-5

x

3

x

1

+

x

2

+

x^

- 15

2

x

1

-5

x

2

+ x<^ 24

x

1

,

x

2

亠0

(2) min z=2

x

1

+3

x

2

+

x

3

X

+4

x

2

+2

X

3

_ 8

并指出属于哪类

3 禺 +2

x

2

- 6

X

i

,

X

,

X

3

- 0

(3) max z=10

x

1

+15

x

2

+12

x

3

5

x

1

+3

x

2

+

X

3

- 9

-5x-

i

+6

X

2

+15

x

3

_ 15

2

x

1

+

x

2

+ x^ 5

X

1

,

X

2

,

X

3

-0

(4) max z=2

x

1

-

x

2

+2

x

3

x-

i

+

x

2

+

x

3

丄 6

-2 x-

i

+

x

3

亠 2

2

x

2

-

x

3

_0

X

1

,

X

2

,

X

3

-0

解：(1)解法一：大M法

化为标准型：

Max z=2

x

1

+3

x

2

-5

x

3

-M

x

4

+0

x

5

-M

x

6

s.t. x-

i

+

x

2

+

x

3

+

x

4

=7

2 x-

i

-5

x

2

+

x

3

-

x

5

+

x

6

=10

x

1

,

x

2

,

x

3

, ,

x

4

,

x^

0 M 是任意大整数。

单纯形表：

C

j

C

B

2

b

7

x

-

3

X

2

-5

X

3

-M

X

4

0

X

5

-M

X

6

0

i

X

B

X

4

-M

1 1 1 1 0 0

7

-M

X

6

10

17M

2

5

2M-10

4/7

45/7

-102/7

[2]

-5

1

2M-5

1/2

1/2

0

0

1

0

0

2/7

5/7

-1

-M

1/2

-1/2

1

0

-1/2

1/2

5

-z

-M

X

4

X

i

3M+2 3-4M

[7/2]

0

1

0

0

1

0

-5/2

4/7

-

2

-z

3

(7/2)M+8 0.5M-6

1/7

6/7

-50/7

0.5M+1 -1.5M-1

1/7

-1/7

-1/7

1/7

-M+1/7

X

2

X

i

1

0

0

2

-z

最优解是：

-M-16/7 -1/7

X= (45/7, 4/7, 0, 0, 0

)

T

目标函数最优值 max z=102/7

有唯一最优解。

解法二：

第一阶段数学模型为 min w=

x

4

+

x

6

S.t. % +

x

2

+

x

3

+

x

4

=7

2 x-

i

-5

x

2

+

x

3

-

x

5

+

x

6

=10

X

!

,

X

2

,

X

3

,

X

4

，

x

5

,

x

6

-0

(单纯形表略)

最优解

X=(45/7，4/7，0，0，0

)

T

目标函数最优值 min w=0 第二阶段单纯形表为：

3

C

j

2

C

B

X

B

X

2

X

1

-5

X

3

0

X

5

q

b

4/7

45/7

-102/7

X

1

X

2

3

2

最优解是

0

1

0

1

0

0

1/7

6/7

-50/7

1/7

-1/7

-z

-1/7

X= (45/7, 4/7, 0, 0, 0

)

T

Max z=102/7

(2) 解法一：大M法

z =-z 有 max z =-min (-

z

) =-min z

化成标准形：

Max

z

=-2 x-

i

-3

x

2

-

x

3

+0

x

4

+0

%

5

-M

x

6

-M

x

7

S.T.

捲 +4

x

2

+2

x

3

-

x

4

+

x

6

=4

3

x

-

+2

X

2

-

X

5

+

x

=6

X

!

,

X

2

,

X

3

,

X

4

,

X

5

,

x

e

,

X

7

—0

(单纯性表计算略)

线性规划最优解X=(4/5, 9/5, 0, 0, 0 , 0

)

T

目标函数最优值min z=7

非基变量

X

3

的检验数

-3

=0,所以有无穷多最优解。

两阶段法：

第一阶段最优解X=(4/5, 9/5, 0, 0, 0, 0

)

是基本可行解,min w=0

T

第二阶段最优解(4/5, 9/5, 0, 0, 0, 0

)

min z=7

T

非基变量

x

3

的检验数二

3

=0,所以有无穷多最优解

（3）解：大M法

加入人工变量，化成标准型：

Max z=10

X

!

+15

X

2

+12

X

3

+0

x

4

+0

x

5

+0

x

6

-M

x

7

s.t. 5

x

-

+3

X

2

+

X

3

+

X

4

=9

-5 捲+6

x

2

+15

x

3

+

x

5

=15

2

x

2

+

x

3

-

x

6

+

x

7

=5

X

i

,

X

2

,

X

3

,

X

4

,

0

X

5

,

X

6

,

X

7

—

单纯形表计算略

当所有非基变量为负数，人工变量

X

7

=0.5

,

所以原问题无可行解

两阶段法（略）

（4）解法一：大M法

单纯形法，（表略）非基变量

X

4

的检验数大于零，此线性规划问题有无界解

两阶段法略

1.7求下述线性规划问题目标函数 z的上界和下界;

Max z=

G

% +

c

2

x

2

a^x-

i

a

12

x

2

- b

i

a

2i

X

1 ■ 822

X

2 — b2

其中：1_

G

—3,4_g _6,8_0 _12 ,10_b

2

_14

,

-1 _a

1

^3,2_a

12

_5

,

2 _ a

21

_ 4 , 4 _ a

22

_ 6

解：

求Z的上界

Max z=3

X

-

I

+6

X

2

s.t.-论 +2

x

2

_ 12

2 为 +4

x

2

_ 14

加入松弛变量，化成标准型，用单纯形法解的，最优解

X=(0, 7/2, 5, 0

)

T

目标函数上界为z=21

存在非基变量检验数等于零，所以有无穷多最优解 求z的下界

线性规划模型：

Max Z=

X

-

I

+4

X

2

s.t. 3

X

1

+5

x

2

岂 8

4

X

1

+6

X

^10

X

2

,

X

^0

加入松弛变量，化成标准型，解得:

最优解为

X= （0, 8/5, 0, 1/5

）

T

目标函数下界是z=32/5

1.8表1-6是某求极大化线性规划问题计算得到的单纯形表。表中无人工变 量，

a1

，，，d，，为待定常数，试说明这些常数分别取何值时，以下 结论成立。

（1）表中解为唯一最优解；（2）表中解为最优解，但存在无穷多最优解；

a2a3C102

（3）该线性规划问题具有无界解；（4）表中解非最优，对解改进，换入变量为为，

换出变量为

x

6

基b

4

X

1

X

2

X

3

X

4

X

a

2

X

6

X

3

d

x

4

2

X

3

C

j _Zj

a

-3

-5

C

2

1

0

0

0

0

1

0

0

0

0

1

0

-1

a

3

C

1

-1

-4

-3

解：

（1） 有唯一最优解时，d—O,

c

「0,

c<

0

（2） 存在无穷多最优解时，d_0,

G

_0,

C

2

=0或d_0,

C

1

=0,

C

2_

0.

（3） 有无界解时，d_0, c$0, q、0且a$0

（4） 此时，有 d 丄0,

c<

0 并且 & _

c

2

,

a

3

> 0

, 3/

a

3

“ d/4

班次

1

2

3

4

5

6

设司机和乘务人员分别在各时间区段一开始时上班，并连续上班8小时，问该公 交线

路至少配备多少司机和乘务人员。列出线型规划模型。

解：

设

X

k

（k=1 , 2, 3, 4, 5, 6）为

X

k

个司机和乘务人员第k班次开始上班

1.9某昼夜服务的公交线路每天个时间段内所需司机和乘务员人数如下:

时间 所需人数

6点到10点

[60

10点到14点

70

14点到18点

：

60

18点到22点

50

22点到2点

”0

2点到6点

30

建立模型：

Min z= x-

i

+

x

2

+

x

3

+

x

4

+

x

5

+

x

6

s.t. x-

i

+ x^ _ 60

X

i

+

x

2

亠 70

x

2

+

x

3

亠 60

x

3

+

x

4

_50

x

4

+

x

5

_20

x

5

+

x

6

_30

X

l

,

X

2

,

X

3

,

x

4

,

X

5

,

X

6

-0

1.10某糖果公司厂用原料 A、B、C加工成三种不同牌号的糖果甲乙丙，已知各 种糖

果中ABC含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单 位加工费

用及售价如表所示：

原料 甲 乙 丙

原料

成本（元/ 千

每月 限制用

量 （千克）

克）

I 2

A >60% >15% 2000

B 11.5 2500

C <20% <60% <50%

1 1200

加工费

0.5 0.4 0.3

售价

3.4 2.85 2.25

问该厂每月应当生产这三种牌号糖果各多少千克，使得获利最大？建立数学模 型。

解

：

解：设

X

i

，

X

2

，

X

3

是甲糖果中的A，B，C成分，

X

4

，

x

，

X

6

是乙糖果的A，

B，C成分，

X

7

，

X

8

，

X

9

是丙糖果的A，B，C成分。

线性规划模型：

Max z=0.9

X

i

+1.4

X

2

+I.9

X

3

+0.45

x

4

+0.95

x

+1.45 冷-0.05%

+0.45

X

+0.95%

79

s.t. -0.4

x

1

+0.6

x

2

+0.6

x

3

^0

-0.2 x-

i

-0.2

x

2

+0.8

x

3

_0

-0.85 沧+0.15

x

5

+0.15

x

e

_0

-O.6

x

4

-O.6

x

5

+0.4

X

6

_0

-0.7X

7

-0.5

x

+0.5X

9

岂0

x

1

+

x

4

+

x

<2000

x

2

+

x

5

+

x

<2500

8

x

3

+

x

6

+ < 1200

x

)

X

i

,

X

2

,

X

3

,

X

4

,

X

5

,

X

6

,

x

7

x

8

x

g

,

,

78

-0

1.11某厂生产三种产品I、丨【、III。每种产品经过AB两道加工程序，该厂 有

两种设备能完成A工序，他们以A,A

2

表示；有三种设备完成B工序，分别为

，

B

2

，

B

3

;产品I可以在AB任何一种设备上加工，产品丨【可以在任何规格 的A

设备上加工，但完成B工序时，只能在

B

1

设备上加工；产品III只能在

A

，

B

2

上加工。已知条件如下表，要求安排最优生产计划，使该厂利润最大化

设备

I

5

7

6

产品

II

III

A

A

2

Bi

B

2

B

3

10

9

设备有效台

满负荷时的

时

设备费用

300

6000

10000

4000

321

250

783

200

12

8

11

4

7

7000

4000

原料费

单价

解：

0.25

1.25

0.35

2.00

0.5

2.8

产品1,设

A

1

,

A

2

完成A工序的产品

X

1

，

X

2

件；B工序时，

B

1

,

B

2

，

B

3

完成

B工序的

X

3

,

X

4

,

X

5

件，产品丨【，设

A

I

,

A

2

完成A工序的产品

X

6

,

X

7

件；B工 序

时，B完成B的产品为

X

8

件；产品111,

1

A

完成A工序的

X

件，B完成B

292

工序的

X

9

件；

X

1

+

X

2

=

X

3

+

X

4

+

x

5

x

7

X

6

+ =

7

X

8

8

建立数学模型：

Max z=(1.25-0.25)*(人 +

x

)+(2-0.35)*(沧 +

X

)+(2.8-0.5)

X

-(5 洛+10

79

X

e

)300/6000-(7

x

2

+9

X

+12

X

)321/10000-(6

x

3

+8 沧

)

250/4000-(4

x

4

+11

79

X

9

)783/7000-7

X

5

*200/4000

s.t

5

x

1

+10

x

6

三6000

7

X

2

+9

X

+12

X

9

乞 10000

7

6

X

3

+8

X

<4000

8

4

X

4

+11

X

< 7000

9

7

x

5

<4000

X

1

+

X

2

=

X

3

+

X

4

+

x

5

x

7

x

8

X

6

+ =

78

X

7

X X

9 “

人兀皿凶必风，,,

-0

T

最优解为 X= （1200，230，0，859，571，0，500，500，324

）

最优值

1147.

试题：

1. （2005年华南理工大学）设某种动物每天至少需要 700克蛋白质、30克矿物

质、100毫

克维生素。现有5种饲料可供选择，每种饲料每公斤营养成分的含量及单价 如下

表所示：

试建立既满足动物生长需要，又使费用最省的选用饲料方案的线性规划模

表1—1

矿物质（克）

1

饲料

1

蛋白质（克）

3

维生素（毫克）

0.5

价格（元/公

斤）

0.2

0.5

2 2 1

3

1 0.2 0.2

4

6 2 2

5 0.5

18 0.8

解题分析：这是一道较简单的数学规划模型问题，根据题意写出约束即可

0.7

0.4

0.3

0.8

解题过程：

min z = 0.2x

「

0.7x

2

0.4x

3

0.3x 0.8x

5

3% + 2x

2

+ x

3

+6x

4

+ 18x

5

K 700

x, +0.5x

2

+0.2x

3

+2x

4

+0.5卷 X 30 s.t彳

0.5x

,

+x

2

+0.2x

3

+2x

4

+0.8x

5

兰 100

X

,

,X

2

,X

3

,x

4

,X

5

X0

第二章（67页）

2.1用改进单纯形法求解以下线性规划问题。

（1） Max z= 6

x

1

-2

x

2

+3

x

3

2

x

1

-

x

2

+3

x

3

二2

为+4

x

3

乞4

人，

X

2

，

X

3

— 0

（2） min z=2

x

1

+

x

2

3

x

1

+

x

2

=3

4

X

J

+3

X

2

_6

x-

i

+2

x

2

-3

x-

i

,

x

2

-0

解：

（1）

先化成标准型：

Max z=6

x

1

-2

x

2

+3

x

3

+0

x

4

+0

x

5

s.t. 2

x

1

-

x

2

+2

x

3

+

x

4

=2

x-

i

+4

x

3

+

x

5

=4

X

l

,

X

2

,

X

3

,

X

4

,

X

5 _0

令

B

o

= (

P

4

,

P

5

)=

■

N

o

=(

P

，

P

2

，

P

3

)

=

2

-1

0

1

0

0

= (

X

4

,

X

5

)

,

C

B

=(O,O)

、

X

B

°

T

o

h

2

、

4

，

b0

，

N

=(

X

!

，

X

2

，

X

3

)

X

0

T

J

C

N

°

=

(6,-2,3)

，

B

0

=

=l4 丿

非基变量的检验数

口 _

C

N

°

'-N

。-

-

C

B

0

耳二

N

0

=

C

N

=

0

=(6,-2,3)

因为

X

i

的检验数等于6,是最大值，所以，

X

i

为换入变量,

B

A

0

b

°

=

I

0

4

」

—1

‘2

；

B

0

P

i

=

、

由二规则

得:

X

4

为换出变量

'2

0

,

X

B

-= (

X

I

,

X

5

)

T

,

C

B

, =(6,0).

B

l

=(

P

4

,

P

5

)

=

1

」

N

=(

X

4

，

X

2

，

X

3

)

N

I

=(R,

P

2

,

P

3

)

,

X

i

T

C

N

I

=

(0

,

, ,

B

i

」

-23)

0.5 0

-0.5 b

,bi =

非基变量的检验数

叫=(

-

3，

1

，-3)

因为

X

2

的检验数为

1,是正的最大数。所以

X

2

为换入变量;

B

0

P

2

=

A

-0.5

0.5

由二规则得：

=6

所以

X

5

是换出变量

B

2

=(

R

,

P

2

)

=

N

2

=(

F

4

,

P

5

,

P

3

),

-1

0

X

,

X

B

2

=

(

x

1

x

2

)

,

,

C

B

=

(6,-2)

.

2

N

2

= (

X

4

,

x

,

X

3

)

T

1

0 1

-

1

2

C

N

2

=(0

,

0, 3)，

B

2-

,

b

2

=

6

2

I

」

」

非基变量的检验数

；邛= (-2, -2,-9)

非基变量的检验数均为负数，愿问题已达最优解。

最优解X=

广4、

0

即：X= (4,6,0

)

T

目标函数最优值 max z=12

（2）

解：

Min z=2

S.T.

3 捲 +

x

2

+

x

4

=3

4 捲+3

x

2

-

X

3

+

X

5

=6

x-

i

+2

x

2

+

x

6

=3

x

2

+0

x

3

+M

x

4

+M

x

5

+0

x

6

X

6

- 0

M是任意大的正数。

（非基变量检验数计算省略）

原问题最优解是X= （0.6，1.2，0）

目标函数最优值：z=12/5

2.2已知某线性规划问题，用单纯形法计算得到的中间某两步的加算表见

表，试将空白处数字填上。

3 5 4

C

j

0 0 0

C

B

X

B

X

2

X

5

b

8/3

14/3

X

1

X

2

X

3

X

4

X

5

X

6

5 2/3

-4/3

1

0

0

5

1/3

-2/3

0

1

0

0 0

0

X

6

C

j

-

Z

j

20/3 5/3

-1/3

0

0

.

4

4

-2/3

-5/3

0

0

1

0

X

2

15/41

-6/41

-2/41

8/41

5/41

-12/41

-10/41

4/41

15/41

X

3

X

i

C

j

-

Z

j

解:

C

j

3

b

8/3

14/3

20/3

5 4

0

X

4

0

X

5

0

X

6

C

B

X

B

X

2

X

5

X

6

C

j

-

Z

j

X

1

X

2

X

3

5

0

0

■

5

4

3

X

2

X

3

X

1

C

j

-

Z

j

80/41

50/41

44/41

0

0

1

0

1

0

0

0

0

1

0

0

15/41

-6/41

-2/41

-45/41

2.3写出下列线性规划问题的对偶问题。

(1) min z= 2

x

1

+2

x

2

+4

x

3

2 论+3

X

2

+5

x

3

_2

3

X

1

+

X

2

+7

X

3

辽3

X

-

I

+4

X

2

+6

X

3

< 5

X

i

必，

X

3 —0

(1)

解：对偶问题是：

Max w=2 y-

i

-3

y

2

-5

y

3

s.t.

2

y

i

-3

y

2

-

y

-2

3

y

i

-

y

2

-4

y^~

2 5%-7

y

2

-6

y

3

-4

y

i

,

y

2

,

y

3

-0

(2) max z=

X

-

I

+2

X

2

+3

X

3

+4

X

4

-

X

-

I

+

X

2

-

X

3

-3

X

4

=5

6 x

i

+7

X

2

+3

X

3

-5

X

4

_ 8

12

X

-

I

-9

X

2

-9

X

3

+9

X

^

20

X

i

,

X

2

一 0

；

X

3

-0

；

X

4

无约束

解：

对偶问题：

Min w=5 y-

i

+8

y

3

+20

y

4

S.t. -

y

i

+6

y

3

+i2

y

-i

y

i

+7

y

3

-9

y

-2 -

y

i

+3

y

3

-

44

9* 乞 3 -3

y

i

-5

y

3

+9 *=4

y

无约束，y

3

乞0;

m n

* -0

(3) min z二二二 qx

j

il j 4

n

' X

ij =4

j 4

m

i=1,…,m

' X

ij

=b

j

j=1,…,n

i 4

X

ij

-0

解：

m n

对偶冋题:max w=^

a

i

y

i

+送

b

j

y

m

岀

s.t.

y

i'

+y

；

卅兰q

''

''

yy

m j

,

无约束 i=1,2,….m; j=1,2,….n

⑷

n

Max z=二

c

j

x

j

jm

n

' a/ _ b , i=1,….,g _ m

j

吕

n

■-

j

a

ij

x

j

二

i=

m

1

1,m

1

- 2,..., m

b

i

,

三

X

j

-0,当 j=1 , ….,m乩

Xj

无约束，当 j=

n

「

1,..., n

解：

m

Min w八

b

j

y

i T

II

s.t.

m

' a* - C

j

i ±

j=1,2,3-

n1

、

a

j

y

；

- c

j

j=

n

+1, 口+2,….n

i

i 4

y

i

-0

n

y

m

i=1,2 ….

m

无约束，

)

=^+1, E+2….m

2.4判断下列说法是否正确，并说明为什么.

(1)如线性规划问题的原文题存在可行解，则其对偶问题也一定存在可行解。

(2) 如线性规划的对偶问题无可行解，则原问题也一定无可行解。

(3) 如果线性规划

问题的原问题和对偶问题都具有可行解， 则该线性规划

问题一定有有限最优解。

(1) 错误，原问题有可行解，对偶问题可能存在可行解，也可能不存在；

(2) 错误，对偶问题没有可行解，原问题可能有可行解也可能有无界解；

(3) 错误，原问题和对偶问题都有可行解，则可能有有限最优解也可能 有

无界解；

2.5设线性规划问题1是：

n

Max

z

1

=二

C

j

为

j

旦

，i=1，2…，m

x

j

-0, j =, n

(

y

1

,..., y

m

)是其对偶冋题的最优解 又设线性规划问题2是

n

Max

Z

2 ='

C

j

X

j

jm

n

' a

j

X

j

虫

b

+

k

i

， i=1，2…，m

j

毘

x

j

-0, j = , n

其中

k

i

是给定的常数，求证：

m

max z

2

_ max

乙

+ ' k

i

y

i

i =1

解：

证明：把原问题用矩阵表示：

Max z-

i

= AX _b

X _0

b= (

D

,

b

2

...

b

m

)

T

设 可行解为

X

i

,对偶问题的最优解

Y

1

= (

y

i

,

y

…

y

m

)已知。

Max

z

2

=CX

s.t. AX mb+k

X -0

k= (

k

i

,

k

2

...

k

m

)

T

设可行解为

X

2

，对偶问题最优解是丫

2

,对偶问题是，

Min w=Y(b+k)

S.t. YA -C

Y -0

因为％是最优解，所以丫

(b+k)乞丫

1

(b+k)

2

X

是目标函数

Z

2

的可行解，A

X

2

乞b+k ； ^A%

岂丫

(b+k)岂

Y

b+Yk 原问题

222

和对偶问题的最优函数值相等，所以不等式成立，证毕。

2.6已知线性规划问题

Max z=

C

|

X-

|

c

2

x

2

c

3

x

3

X

j -

j

_ 1

，

...

，

0,5

用单纯形法求解，得到最终单纯形表如表所示，要求：

(1) 求

a

ii

，

a

i2

，

a

i3

，

a

2i

，

a

22

，

a

23

，

b

i

，

b

2

的值;

(2

)求

C

i

,C

2

,C

3

的值;

X

B

X

3

b

3/2

X

i

X

2

X

3

X

4

X

5

1 0 1

1/2 -1/2

x

C

j — Zj

2

1/2

-3

1

0

0

0

-1

2

-4

0

解：

(1) 初始单纯形表的增广矩阵是:

C

i

=

a

i3

_a

2i

1 0

0.5 1

1

a

3

1 0.5

1

0 b

i

0

1 b

2

-0.5 1.5

2 2

22

最终单纯形表的增广矩阵为

C

2

=

C

是C作初等变换得来的，将C作初等变换，使得C的第四列和第五列 的矩

2

阵成为C的单位矩阵。有：

2

an=9/2；印

2

=1;盹=4;

b

=9；

b

2

=5

由检验计算得：

C| =-3；

C

2

=

C

3

=0

2.7已知线性规划问题

Max z=2

x

1

+

x

2

+5

x

3

+6

x

4

s.t. 2

x

1

+

x

3

+

x

4

空 8

2

x

1

+2

x

2

+

x

3

+2

x^

- 12

X

j

-0, j=1,…4

a

21

=5/2；

a

22

=1；

a

23

=2；

对偶变量

y

1

,

y

2

，其对偶问题的最优解是

y

；

=4,

y

；

=1

，试应用对偶问题 的性

质，求原问题的最优解。

解：

对偶问题是：

Min w=8

y

1

+12

y

2

s.t. 2

y

1

+2

y

2

丄2

2

y

2

-1

y

i

+

y

2

-5 %+2

y

2

- 6

y

i

,

y

2

- o

互补松弛性可知，如

卞,

Y

是原问题和对偶问题的可行解，那么，

Y?X

s

=0

和

Y

S

X?=0，当且仅当

X

，

Y?

是最优解。

设X,Y是原问题和对偶问题的可行解，

Y

s

=（

y

3

，

y

，

y

，

y

）

4

有：

X

Y =0;且

Y

S

X=0

S

X

5

=

X

6

=0，原问题约束条件取等号，

X

3

=4；

X

4

=4

最优解 X=（0, 0, 4, 4

）

T

目标函数最优值为44。

2.8试用对偶单纯形法求解下列线性规划问题。

（1）min z=

x

1

+

x

2

2 为 +

x

2

_ 4

x

1

+7

x

2

_ 7

X

i

,

X

2

— 0

（2） min z=3 捲 +2

x

2

+

x

3

+4

x

4

2

x

1

+4

x

2

+5

x

3

+

x

4

- 0

3

x

1

-

x

2

+7

x

3

-2

x

4

-2

5

x

1

+2

x

2

+

x

3

+10

x

4

-15

为，X

2

, X

3

, &

解：

（1）

取w=-z，标准形式：

-0

Max w=- x-

i

-

x

2

+0

x

3

+0

x

4

s.t.

-2

X

-

-

X

2

+

X

3

=-4

-

X

-

-7

X

2

+

X

4

=-7

X

i

,

X

2

,

X

3

,

X

4

一 U

单纯形法求解(略)： 最优解：

X= (21/13, 10/13, U, U

)

T

目标函数最优值为31/13。

(2) 令：w=-z,转化为标准形式：

Max w=-3

X

1

-2

X

2

-

X

3

-4

X

4

+0

X

5

+0

X

6

+0

X

7

s.t.

-2

X

1

-4

X

2

-5

X

3

-

X

4

+

X

5

=0

-3 x-

i

+

x

2

-7

x

3

+2

x

4

+

x

6

=-2

-5 x-

i

-2

x

2

-

x

3

-6

x

4

+

x

7

=-15

X

1

，

X

2

，

X

3

，

X

4

，

X

5

，

X

6

，

X

7 .

单纯形法略 原问题最优解：

X=（3，0，0，0，6，7，0

）

T

目标函数最优值为9。

2.9现有线性规划问题

max z=- 5

x

1

+5

x

2

+13

x

3

-x-

i

+

x

2

+3

x

3

- 20

12 x-

i

+4

x

2

+10

x

3

- 90

X

1

，

X

2

，

X

3

-0

先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什

么变化？

（1

约束条件1的右端常数20变为30

(2) 约束条件2的右端常数90变为70

(3) 目标函数中

x

3

的系数变为8

(4)

x

i

的系数向量变为

1

J2丿

(5) 增加一个约束条件2

X

i

+3 « +5怡乞50

(6) 将约束条件2变为10^+5

x

2

+10

x

3

空100

解：

把原问题化成标准型的：

Max z=-5

x

1

+5

x

2

+13

X

3

+0

x

4

+0

x

s.t

-x-

i

+

x

2

+3

x

3

+

x

g

=20

12 x-

i

+4

x

2

+10

x

3

+

x

g

=90

%，

x

，

X

3

，

x

4

，

X

5

- 0

单纯形法解得：

最优解：

X= (0，20，0，0，10

)

T

目标函数最优值为100。

非基变量x-

i

的检验数等于0，原线性问题有无穷多最优解

(1) 约束条件二的右端常数变为30

有

：

^B

J

b

因此b =b「b

单纯形法解得：

最优解：

X= (0，0，9，3，0

)

T

目标函数最优值为117。

(2) 约束条件Q右端常数变为70

有 b=B‘

：

b

因此b =b 比

单纯形法解得，最优解：

X= (0，5，5，0，0

)

T

目标函数最优值为90。

(3)

X

3

的系数变成8,

X

3

是非基变量，检验数小于0,所以最优解不变

(4)

x

i

的系数向量变为

x

i

是非基变量，检验数等于-5,所以最优解不变。

(5) 解：加入约束条件

0

3

用对偶单纯形表计算得：

X= (0, 25/2, 5/2, 0, 15, 0

)

T

目标函数最优值为95。

(6) 改变约束条件，巳,巳,

P

5

没有变化, 线性规划问题的最优解不变。

2.10已知某工厂计划生产1,11」11三种产品，各产品在ABC设备上加工，数 据如

下表，

I II III

设备代号

每月设备 有效

台时

A

B

C

单位产品利润

/千兀

8

10

2

3

2

5

13

2

10

8

10

2.9

300

400

420

(1)如何充分发挥设备能力，使生产盈利最大?

(2) 如果为了增加产量，可借

用其他工厂的设备 B，每月可借用60台时，

租金为1.8万元，问借用是否合算？

(3) 若另有两种新产品IV,V ,其中IV为10台时，单位产品利润2.1千元； 新

产品V需用设备A为4台时，B为4台时，C为12台时，单位产品盈利1.87 千元。

如A,B,C设备台时不增加，分别回答这两种新产品投产在经济上是否划 算？

(4) 对产品工

艺重新进行设计，改进结构，改进后生产每件产品 I，需要

设备A为9台时，设备B为12台时，设备C为4台时，单位产品利润4.5千元， 问

这对原计划有何影响？

解：

(1)

设：产品三种产品的产量分别为，

X

1

,

X

2

,

X

3

，建立数学模型：

s.t.

Max z=3

x

1

+2

x

2

+2.9

X

3

8

x

4

+2

x

2

+10

x

3

乞300

10

x

1

+5

x

2

+8

x

3

- 400

2^+13

x

2

+10

x

3-

420

X

i

,

X

2

,

X

3

一0

把上述问题化为标准型，用单纯形法解得：

最优解：

X=（ 338/15, 116/5, 22/3，0，0，0

）

T

目标函数最优值为2029/15。

（2）

设备B的影子价格为4/15千元/台时，借用设备的租金为

所以，借用B设备不合算。

（3）

设备V,V生产的产量为

x

，

X

8

，系数向量分别为：

P

7

=（12,5,10）

丁

P

8

=（4,4,12）

丁

检验数二

7

=-0.06,所以生产 V不合算，

6=37/300,生产V合算。

单纯形法计算得：

最优解：

X=（ 107/4，31/2，0，0，0，0，55/4

）

T

目标函数最优值为10957/80。

（4） 改进后

，

检验数二

1

=253/300，大于零。

所以，改进技术可以带来更好的效益。

2.11分析下列参数规划中当t变化时最优解的变化情况

（1）Max

z

（

t

）

=（3-6t）捲+（2-20

X

2

+（5-5t）

X

3

（t_0）

s.t.

x-

i

+2

x

2

+

x

3

- 430

3

X

1

+2

X

3

- 460

0.3千兀每台时。

x-

i

+4

x

2

- 420

x

i

,

X

2

,

X

3

_ 0

(2) Max

z

(

t

)

=(7+2t)

x

1

+(12+t)

x

2

+(10-t)

x

3

(t 亠 0)

s.t.

x-

i

+

x

2

+

x

3

- 20

2

x

1

+2

x

2

+

x

3

- 30

X

i

,

x

,

X

3

一0

(3) Max

Z

(t)

=2

x

1

+

x

2

(0 ^t 乞25)

s.t.

X

1

- 10+2t

x-

i

+

x

2

- 25-t

x

2

- 10+2t

x-

i

,

x

2

-0

(4) Max

z

(t)

=21 x-

i

+12

x

2

+18

x

3

+15

x

4

(0 -1 - 59)

s.t.

6

x

1

+3

x

2

+6

x

3

+3 & - 30+t

6*3

x

2

+12

x

3

+6

x

4

- 78-t

9

x

1

+3

x

2

-6

x

3

+9

x

4

135-2t

人,

X

2

,

X

3

,

x

4

-0

解：

(1)化成标准形式：

Max

Z

(t)

=(3-6t)

X

1

+(2-2t)

x

?

+(5-5t)

X

3

+0

X

4

+0

X

5

+0

X

s

(t - 0)

s.t.

x-

i

+2

x

2

+

x

3

+

X

4

=430

x-

i

+4

x

2

- 420

3

x

1

+2

x

3

+

x

5

=460

x-

i

+2

x

2

+

x

3

+

X

4

=430

x-

i

+4

x

2

+

x

6

=420

X

i

,

X

2

,

X

3

,

X

4

,

X

5

,

X

6

_0

令t=0,用单纯形表计算，

3-6t

C

j

2-2t 5-5t

0

X

4

0

X

5

0

X

6

9i

C

B

X

B

X

2

X

3

X

6

B

X

1

X

2

X

3

2-2t

5-5t

0

-z

100

230

20

-1/4

3/2

2

1

0

0

0

1

0

0.5 -1/4

1/2

[1]

0

0

1

-

460

20

0

-2

t-1 2t-2

1350t -

t-4

0 0 0

1350

t增大，t大于1,首先出现二

4

，二

5

大于0,所以当0乞2 1时有最优解

X=（0，100，230，0，0，20

）

T

目标函数最优值为1350（t-1）

t=1是第一临界点

t大于1时，

X

6

是换出变量。

t 大于 1,最优解是：X=（0，0， 0, 430，460, 420

）

T

（0乞2 1）。

目标函数最优值为

Max

z

（

t

）

=0, （ t 大于 1）

（2）

化成标准型，然后令t=0,单纯形法解得：

t开始增大时，当t大于8/3时，首先出现二

大于0,所以0^2 8/3，得最 优解。

4

目标函数最优值 Max

z

（

t

）

=220,（ 0乞2 8/3）

所以，t=8/3为第一临界点。

当8/3

x

3

为换出变量，使用单纯形法 继续迭

4

代，t继续增大，当t>5,首先J大于0, 8/3

目标函数最优值为180+15t

所以，t=5为第二临界点。

, (8/3

X= (0, 15, 0, 5

)

T

当t>5时，捲是换入变量，

x

为换出变量，单纯性法计算，

当t继续增大，所有检验数都非正，所以当 t>5,最优解：

X=( 15，0，0，5

)

T

目标函数最优值为105+30t， t> 0

(3)化成标准型，令t=0,用单纯形法计算得：

当t开始增大，t大于5时，首先出现

b

2

小于0,当0岂M5，最优解为：

X= (10+2t, 0, 10+2t, 5-t, 0

)

T

目标函数最优值为6t+30

所以t=5是第一临界点。

, (0空仁5)。

当t大于5时，

X

4

是换出变量，

X

5

是换入变量。用对偶单纯形法计算，

当t大于5时，最优解为：

X= (10+2t, 15+t, 0, 0, t-5

)

T

目标函数最优值为35+5t。

(4) 解: 先化为标准型，令t=0,用单纯形法计算，得：

当t开始增大，当t大于6时，首先出现

b

2

小于0,当0乞仁6,有最优解：

X= (0, 0, 0, 10+t/3, 0, 18-3t, 45-5t

)

T

目标函数最优值为150+5t (0^2 6)。

当t大于6时，首先出现

b

2

小于0,

X

是换出变量，

X

2

是换入变量，使用单

纯形法计算得：t继续增大，当t大于11时，

b

3

首先小于零，

X

是换出变量，

X

3

为换入

变量，对偶单纯形法迭代得：

当t< 59,有最优解：

X= (0, t/3-2, t/8-11/8, 59/4-t/4, 0, 0, 0

)

T

目标函数最优值为 5t/2+345/2 , (11

试题：

1. (2006年西北工业大学)已知线性规划：

max z = 3x

!

2x

2

—为

+2x

2

兰

4

3

洛

+2x

2

兰

12 st {

| X

1

- X

2

— 3

X

i

, X

2

_ o

（1） 用单纯形法求解该线性规划问题的最优解和最优值；

（2） 写出线性规划的对偶问题；

（3） 求解对偶问题的最优解和最优值。

解题分析：本题考察了线性规划与对偶问题的知识，要求读者熟知对偶理论。

解题过程：X二

18 3 32

IL5 5 5

0 0

maxz =12，有无穷多解。

对偶问题为：

min w = 4y

1

12y

2

3y

3

-力

3y

2

y

3

一

3 st 2y

1

2y

2

-y

3

-2

.%”2”3-

0

Y - 0 1 0.

* F

w = z =12

T * *

2. （2005年东南大学）写出如下线性规划问题的对偶问题:

max z = x

「

2x

2

x

3

st

花一

X

2

于

X

3 =

1

2 x

1

- x

2

x

3

_ 2

人一

0, X

2

岂

0

无限制

并利用弱对偶性说明

z

的最大值不大于1 解题过程：原问题的对偶问题为：

min w = 2y

1

y

2

2y

3

Y

1

+

Y

2

+

2y^1

4」

l-y

％

^y

- y

2 5

^ya =1

兰 2 s.t 5

% _0,y

3

gy

2

由于（0，1, 0）是上述对偶问题的可行解，由弱对偶性可知，对原问题的

可行解

X

都有

C X— Yb

任一

而

Yb = b 1 O] 1 =1

，所以

z

的最大值不大于1。

第三章（86页）

3.1判断表中给出的调运方案能否作为用表上作业法求解时的最初解？为 什么？

表3 — 1

1 2 3 4

销地 产量

1

2

3

销量

0

15

15

10

15

25

5 5

5

表3—2

1 2

15

3

15

4

10

5

产量

销 地 产

地、

1 150

2

3

4 90

5

销量

240

解：

250

200

300

250

400

500

50 300

300

100

210

410 550

80

330

20

70

表3— 1 中,有5个数字格，作为初始解，应该有m+n-1=3+4-1=6个数字格, 所以表

3-1的调运方案不能作为用表上作业法求解时的初始解。

表3-2中，有10个数字格，而作为初始解，应该有 m+n-1=9个数字格，所 以表3-2

的调运方案不能作为表上作业法的初始解。

3.2

表3-3和表3-4中分别给出两个运输问题的产销平衡表和单位运价表，

伏格尔法直接给出近似最优解

表3-3

销地

3

产量

1 2

产地

5

2

3

9

1

4

6

10

8

1

7

11

12

14

4

试用

1

2

3

销量

表3-4

1

销 地、

产地

'、、

1

2

3

4

销量

2 3 4 5

产量

10

5

15

20

20

2 「

20

5

15

20

3

15

14

13

30

15

2

7

M

10

9

4

15

8

25

25

30

20

30

解：

(1)在表3-3中分别计算出各行和各列的次最小运费和最小运费的差额, 填入该表的最

右列和最下列。得到：

1 2 3

行差额

、、销地 产地

4

1 8

2 2 1 1

3 3 6 [7 3

列差额

3

1 6

从行差额或者列差额中找出最大的， 选择它所在的行或者列中的最小元素， 上表

中，第三列是最大差额列，此列中最小元素为 1,由此可以确定产地2的产 品应先供

应给销售地3,得到下表：

1

4

1 [

5

销地

1

2

3

产量

产地

1 ]

2

3 n

销量

9 10

同时将运价表第三列数字划去，得

、^销地

1 2

11

12

14

4

11

产量

产地

1 12

2 4 14

3 6 4

|

9 10

对上表中的元素，计算各行和各列的次最小运费和最小运费的差额，填入 该表的最右

列重复上面的步骤，直到求出初始解，最终结果是：

和最下列，

1

2

3

销量

5

代、销地

产地

1 [

2

3

销量

1 2 3

产量

2

3

4

9

10

11

12

14

4

10 11

（2） 3-4分别计算出各行和各列的次最小运费和最小运费的差额，填入该 表的最右

列和最下列。从行差额或者列差额中找出最大的， 选择它所在的行或者 列中的最小

元素。（方法同3-3相同）

最终得出原问题的初始解:

2 3 4 5

销地

1

产量

产地

1

2

3

4

销量

20

25

30

20

30

30 25

20 20 10

3.3用表上作业法求给出运输问题的最优解（M是任意大正数）

(1)

甲 乙 丙 丁

、销地

产地

产量

1

2

3

销量

解：

3

2

4

3

7

4

3

3

6

3

8

2

2

I'

2

5

2

3

（1） CD计算出各行和各列的次最小运费和最小运费的差额， 填入该表的最

右列和最下列。

②从行差额或者列差额中找出最大的， 选择它所在的行或者列中的最 小

元素，丙列中的最小元素为3,由此可以确定产地2的产品应先供应丙的需要， 而产地

2的产量等于丙地的销量，故在（2,丙）处填入0,同时将运价表中的

丙列和第二行的数字划去，得到:

、、销地 甲 乙 丙 丁

产地

产量

1

3

7 4 5

2

3

销量

2

O

对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额,

4

3

3

3

2

3

填入该标的最右列和最下行，重复步骤

O

1②，直到求出初始解为止。得到下表:

销地

产地

1

2

3

销量

甲 乙 丙 丁 产量

x

3

2

A

0

5

2

3 0

3

3

3

2

2

u

i

(i=1 ,

使用位势法进行检验：

&上表中，数字格处填入单位运价并增加一行一列，在列中填入

ii

2, 3)，在行中填入

V

j

(j=1，2, 3, 4)，先令

U

+

V

= q (i，j^B，B 为基，下

同)来确定

U

和

V

，得到下表:

销地 甲 乙

ii

丙 丁

U

i

产地

1

2

3

v

i

'、、、

3

4

3

0

-2

1

4

3

3

2

i

5 4

②由r=

Cj

- (

U

+

V

) (i，j为非基，下同)计算所有空格的检验数，并在 每个格的右上角

i

填入单位运价，得到下表

销地 甲

产地

1

2

3

乙 丙 丁

U

i

、.

0

1

0

3

5

2

4

0

7

1

4

4

3

2

0

6

3

4

0

0

2

5

0

0

-2

8 1

V

i

3

2

5 4

由上表可以看出，所有的非基变量检验数》 0, 此 尤问题达到最优解。

又因为二

34

=0，此问题有无穷多最优解

总运费 min z=3*3+3*3+2*3+2*4=32

(2)

、、销地

产地

1

2

3

销量

甲 乙 丙 丁 产量

'、

10

16

5

5

6

10

4

2

7

5

10

4

M2

9

[10

6

4

9

4

解：(2

)(5

计算出各行和各列的次最小运费和最小运费的差额，填入该表 的最

右列和最下列。

②从行差额或者列差额中找出最大的， 选择它所在的行或者列中的最 小

元素，甲列是最大差额列，甲列的最小元素是 5,所以产地3的产品先供应甲 的需

求，同时将运价表中产地3所在行的数字划去。

5

对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，

填入该标的最右列和最下行，重复步骤

O

1②，直到求出初始解为止。得到下表:

、、销地 甲 乙 丙 丁 产量

产地

1

2

3

销量

1

2

1

3

4

6

4

5 2

使用位势法进行检验：

9

4

4 6

&上表中，数字格处填入单位运价，并增加一行一列，在列中填入

U

i

(i=1，

2, 3)，在行中填入

V

j

(j=1，2, 3, 4)，先令 5=0，由

U

+

V

=

C

j

(i，产 B, B 为基，

ii

下同)来确定

U

和

V

.

ii

5

由

Fj

=

Cj

- (

U

+

V

) (i, j N )计算所有空格的检验数，并在每个格的右 上角填入

ii

单位运价，得到下表

肖地

产地

1

2

3

、、

甲 乙 丙 丁

U

i

0

8

0

10

16

5

3

6

6

10

4

8

7

7

1

5

0

10

0

4

11

12 0

9 -2

-5

6

10

V

i

10

由上表可以看出，所有的非基变量检验数》 0,此问题达到最优解

此问题有唯一最优解。

总运费min z=118

(3)

甲 乙 丙 丁 戊 产量

销地

产地、

1

2

3

4

销量

10

2

1

8

4

20

10

20

6

4

5

8

7

3

6

9

30

10

7

2

10

6

4

5

4

5

；

6

2

解：（3）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售 地

己，令单位运价为0。销量为2。这样就达到了产销平衡。

用伏格尔法求初始解：

CD

计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列 和

最下列。

C

从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元 素，

产地1所在的行是最大差额行，最小元素 0,说以一产地的产品应该优先供 应己的需

要，同时划掉己列的数字。

③对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 填入该标的

最右列和最下行，重复步骤

O

1②，直到求出初始解为止。得到下表:

甲 乙 丙 丁 戊 己 产量

销地

产地、、

1 3 2 5

4

2 2 6

3

2 2

4 4 3 2 9

销量

4 4 6 2 4 2

使用位势法进行检验：

C

上表中，数字格处填入单位运价，并增加一行一列，在列中填入

u

i

（i=1，

2, 3, 4),在行中填入

V

j

(j=1 , 2, 3, 4, 5, 6),先令

U

i

=0，由

U

+

V

=

C

j

(i, j

ii

B, B为基，下同)来确定

U

和

V

.

ii

O

由F=

Cj

- (

U

+

V

) (i, j N )计算所有空格的检验数，并在每个格的右 上角填入

ii

单位运价。

由上表可以看出，所有的非基变量检验数》 0,此问题达到最优解。

又因为二

14

=0，此问题有无穷多最优解。

总运费min z=90

(4)

甲 乙

、、销地

产地

1

2

3

4

5

丙

29

丁

13

14

3

18

30

60

戊 产量

10

13

18

M

22

16

100

120

M 140

19

34

21

11

23

36

100

0

9

24

100 120

6

11

28

80

60

销量

80

解：(4)此问题是一个产销不平衡的问题，产大于销。增加一个假象销售 地己，

令单位运价为0。销量为40。这样就达到了产销平衡。

用伏格尔法求初始解：

O

计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列 和最

下行。

O

从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元 素，

同时划掉所在列或行的元素。

③对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 填入

该标的最右列和最下行，重复步骤

O

1②，直到求出初始解为止。

并用位势法进行检验:

乙 己

甲 丙 丁 戊

销地 产

U

i

地、

29 13

1 10 18 22 0 0

2 8 0 6 12

13 M 14

2 21 16 0 0

3 M-16 0 1 0 12

3 3 M -10

6 11 0

0

0

4

4

5

2

v

i

0

9

0

24

0

16

11

28

0

23

7

36

3

21

0

10

5

13

18

30

M-6

19

8

34

6

16

22

17

0

-12

0

-5

12

10

由上表可以看出，所有的非基变量检验数》 0,此问题达到最优解 又因为二

31

=0，此问题有无穷多最优解。

总运费min z=5520

3.4

已知运输问题的产销平衡表、单位运价表及最优调运方案如下表所示 表1

产量

销 地

B

1

B

2

B

3

B

4

产地

A

A

A

3

5

10

15

25

0

10

15

5

5

15

B

1

10

B

2

1

7

14

C22

销量

表2

产地

5

销地

15

B

3

20

9

16

10

B

4

11

20

18

A

A

12

2

22

A

（1）A

到B的单位运价在什么范围变化时，上述最优方案不变?

（2） A到B的单位运价变为何值时，有无穷多最优方案。除表

24

1中方案

外，至少写出其他两个。

解：

（1） CD在对应表的数字格处（

C

22

未知）填入单位运价，并增加一行，在列中

填入

U

i

（i=1，2，3），在行中填入

V

j

（j=1，2，3，4），先令

U

i

=0，由

U

+

V

=

C

ij

ii

(i, j B)来确定

U

和

V

.

ii

O

由F=

Cj

- (

U

+

V

) (i, j N )计算所有空格的检验数，并在每个格的右 上角填入

ii

单位运价(

c

22

未知)。

最优调运方案不变，则所有非基变量的检验数都是非负。所以：

C

22

-3 — 0

c

22

+10-0

10-

C

22

- 0

24-

C

22

- 0

18-

Q

2

一 0

解得

：

3 -

C

22

- 10

单位运价在此区间变化时，最优调运方案不变。

(2

)0

在对应表的数字格处(

C

22

未知)填入单位运价，并增加一行，在

列中填入

U

i

(i=1 , 2, 3)，在行中填入

V

j

(j=1，2, 3, 4)，先令 5 =0，由

U

+

V

= q

ii

(i，j

，

B)来确定

U

和

V

.

ii

O

由F=

Cj

- (

U

+

V

) (i，

j・

N )计算所有空格的检验数，并在每个格的右 上角填

ii

入单位运价(

C

22

未知)。

有无穷多最优方案，则至少有一个非基变量的检验数为 0.

取5-17=0,所以单价变为17时，该问题 有无穷多最优调运方案。

另外的两种调运方案：

销地

产地

B

1

B

2

B

3

B

4

产量

A

15

0

0

15

10

15

25

A

2

A

3

5

5

5

10

销量

15 15

、、销地

产地

B

1

B

2

B

a

B

4

产量

A

A

2

A

3

15 15

25

5

0

5

5

0

15

10

销量

15 15 10

3.5

某百货公司去外地采购 ABCD四种规格的服装，数量分别为： A,1500套;

B, 2000套；C，3000套；D，3500套；有三个城市可以供应上述服装，分别为:

I，2500套，II，2500套；III，5000套。已知下表，求预期盈利最大的采购方 案。

A B C D

I 10 5 6 7

II 8 2 7 6

9 3 4 8

III

解：

因为利润表中的最大利润是10，所以令M=10，用M减去利润表上的数字, 此问题变

成一个运输问题，见下表：

A B

D

销地

C

产量

产地

、、

I

II

III

销量

0 5

2 8

1 7

1500 2000

使用伏格尔法计算初始解：

4

3

6

3000

A

4

2500

2500

5000

3500

CD

计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列

和最下行。

C

从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元 素，

同时划掉所在列或行的元素。

C

对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 填入

该标的最右列和最下行，重复步骤

O

1②，直到求出初始解为止。

销地

产地

A B C D

产量

I

II

III

销量

1500

500

500

2500

3000

1500

使用位势法检验：

1500

2000

[3500

3500

2500

2500

5000

①数字格处填入单位运价，并增加一行一列，在列中填入

ii

u

i

（i=1 , 2, 3）,

i

在行中填入

V

j

（j=1，2，3, 4），先令

u

i

=0，由

U

+

V

= q （i，产B,）来确定

U

和

V

.

i

②由F=

Cj

-（

U

+

V

） （i，j

・

N ）计算所有空格的检验数，并在每个格的右

ii

上角填入单位运价。

如果没有得到最优解，用逼回路法进行改进 盈利最大方案：

A B C D

、、销地 产

地

I

、、

II

3

III

0

V

i

U

i

0

2

5

0

8

4 0

7

1

5

1

4

0

4

2

3

4

6

1

3

4

2

0

-1

1

1

0

此时，总运费为28000元;最大盈利为72000元。

3.6甲乙丙三个城市每年需要煤炭分别为： 320万吨、250万吨、350万吨,

由A、B两处煤矿供应。煤炭供应量分别为：A,400万吨；B,450万吨；运价如下

表，由于需大于供应，经研究平衡决定，甲城市供应量可以减少 0~30万吨，乙

城市需要完全供应，丙城市供应不少于270万吨。试求将供应量分配完又使总运 费最

低的调运方案。

甲

乙 丙

A

B

15

21

18

25

22

16

解:

此问题的供应量小于需求量，假设供应地 C,产量为70万吨。 用伏格尔法求解

得：

甲 甲‘ 乙 丙 丙‘ 供应

、销地 产

地、

A 150 250 400

B 140 30 270 10 450

C 70 70

需求

290 30 250 270 80

使用位势法检验:

CD

数字格处填入单位运价，并增加一行一列，在列中填入

U

i

(i=1 , 2, 3),

在行中填入

V

j

(j=1 , 2, 3, 4),先令

U

i

=0,由

U

+

V

=

q

(i,产B,)来确定

U

和

V

.

iii i

C

由

Gj

=

Cj

- (

U

+

V

) (i, j N )计算所有空格的检验数，并在每个格的右 上角填入

ii

单位运价。

如果没有得到最优解，用闭回路法进行改进。

最优解时，最小运费是14650万元。

3.7某造船厂根据合同要从当年起连续三年末各提供三条规格型号相同的

大型客货轮。已知该厂这三年内生产大型客货轮的能力及每艘客货轮成本如下 表，

正常生产时间内 加班生产时间内

正常生产时的 每艘

年度

可完成的客货轮 可完成的客货轮

成本/万元

数 数

1

2

2

4

3

2

500

600

3 1 3 550

已知加班生产时，每艘客货轮的成本比正常生产高出 70万元，又知道造出 来的可货

轮如当年不交货，每艘积压一年造成积压损失 40万元，在签合同时，

该厂已经存储了 2艘客货轮，而该厂希望在第三年木完成合同后还能存储一艘备

用，问该厂如何安排每年的生产量，能够在满足上述要求的情况下，总的生产费 用加

积压损失最少？

解：

设

A

l

,

A

,

A

是三年的需求订货，

B

i

,

B

2

,

B

3

是三年的正常生产能力；区,

B

2

,

B

3

是三年的加班能力，S是事先积压产生的供货能力。第三年的需求量是 4

艘。此问题产销不平衡，增加设想销地

A

4

，运价0,销量7. 使用伏格尔法求初始解：

并用位势法检验： 此问题有无穷多最优解，

总运费 min z=4730万元

销地 产

地'

Bi

B

；

供应量

A

i

A

2

A

3

A

500

540

0

0

600

60

60

60

-10

B

2

B

2

0

0

B

3

550

620

B

3

0

60

-460 40

500 540

试题：（2001年上海大学

）

S

需求量

560 -60

某产品由产地A

i

发往销地B

j

的每吨运费如下表:

元/吨

B

i

B

2

A

i

50 40 150

A

2

45 30 200

A

3

20 10 250

需求量

150

220

为满足各销地需求，应如何确定运输方案使总费用最小?

（1） 建立此运输问题的数学模型。

（2） 将此问题化为产销平衡的运输问题，并求出一个初始基本可行解。

B

3

60

65

50

180

供应量（吨）

解：（1）设

X

j

某产品为从A

i

发往销地B

j

的吨数，贝吐匕运输问题的数学模型为:

max z =50x“ 40x

12

60x

13

- 245x

21

30x

22

65x

23

20x

31

10x

32

- 50x

33

X

1

1

'

x

12 '

x

13

= 150

'

x

23

x

31

x

x

'

22

21

二

'

x

32 '

x

33

200

-250

=150

= 220

-180

st ^x

11

X

12

x

13

'

x

21

'X

22

'

X

23

X

31

' X

32

'

X

33

-0 , i , j =1 ,2,3

、

X

j

(2)增加一个虚拟销地B

4

,其需求量为50吨，各产地到虚拟销地B

4

的每吨运 费分

别为0,贝冋将此问题化为如下产销平衡的运输问题：

元/吨

A

1

A

2

B

1

50

45

B

2

40

30

B

3

60

65

r 0

B

4

0

0

供应量

150

200

250 A

3

20 10 50

需求量

150 220 180

由最小元素法可得到如下的一个初始基本可行解:

50

元/吨

B

1

B

2

A

1

A

2

A

3

需求量

120

30

150

B

3

100

80

B

4

50

供应量

150

200

250

220

220 180

50

第四章(98页)

4.1若用以下表达式作为目标规划的目标函数，试述其逻辑是否正确?

(1)

max=

djd

1

(2) max z=

df

-

d

1

(3)

min z=

d

+

d

(4)

+

min z=

d

-

d

解: (1)不正确

(2)

正确

.—.+

1 1

，

-

，

(3)

正确

(4) 正确

4.2

试用图解法找出以下目标函数的满意解;

(1) min z=

p

(小厂+小广)+

P

2

(2d^+d^)

s.t.

X

1

-10

X

2

+

d

i--

d

i

=50

3

x

1

+5

x

2

+ df-

d

2

=20

8

x

1

+6

X

2

+

d

3

：

d

3

=100

X

i

,

X

2

, dj

d

1

,

d

2

,

d

?—

,

d

3_

,

d

3

一0

(2)

min z=

R

(

d^+ d/

)

+

P

2

d/+

P

3

d

2

_

+

P

4

(

d

3

_

+1.5

d

4^

s.t.

X

-

I

+

x

2

+

d

1

：

d

1

=40

X

-

I

+

x

2

+

d

2

-

d

2

"=100

X

+

d

3

-

d

3

=30

_

X

2

+

d

4

-

d

4

=15

X

i

,

X

2

,

d

i_

,

d

i

,

d

2

,

d

2_

,

d

3_

,

d

3

,

d

「,

d

4

_0

(3) min z=

R

(

d

「+

d

i

) + R, df +

P

3

d

3

s.t.

X

-

I

+

X

2

+

d

1

_

-

d

1

=10

3

X

1

+4

X

2

+

d

2-

d

2

=50

8

X

1

+10

X

2

+

dr

-

d

3

=300

X

i

,

X

2

,

d

「，

d

i

,

d

2

,

d

2_

,

d

3_

,

d

3

—0

解

(1) 满意解是：(50, 0)

(2) 满意解是：(25, 15)

(3) 满意解是：(10, 0)

4.3使用单纯形法求解下列目标规划问题。

(1) min z=

R d^

+

F

2

d^

+

P

3

(5

d^

+3

df

) +

P

4

d/

s.t.

X

-

I

+

x

2

+

d

1

：

d

1

=80

X

1

+

x

2

+

d

2

_

-

d

2

=90

X

i

+小

3

-小

3

=70

X

2

+

dr

-

d

4

=45

X

i

,

X

2

,

d

i_

,

d

i

,

d

2

,

d

?—

,

d

3_

,

d

3

,d<^,

d

；

_0

(2)

min z=

P d^

+

P d2~

+

P

2

dr

s.t.

X

i

+2

x

?

+

d

i

-

d

i

=10

10论 +12

x

2

+

d

2

-

-

d

2

=62.4

x

i

+2

x

2

_8

X

i

,

X

2

, de

d

i

,

d

2

,

d

2

一

-0

(3)

min z=

R

( dr

+ d^

)

+

F

2

d

3

_

s.t.

X

i

+

X

2

+

d

i

-

d

i

=i