线性规划习题附答案.doc

习题
2-1 判断下列说法是否对的：
（1） 任何线性规划问题存在并具有惟一的对偶问题；P
（2） 对偶问题的对偶问题一定是原问题；P
（3） 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；O
（4） 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；O
（5） 若线性规划问题中的bi，cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；O
（6） 应用对偶单纯形法计算时，若单纯形表中某一基变量xi<0，又xi所在行的元素所有大于或等于零，则可以判断其对偶问题具有无界解。O
（7） 若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增长5个单位时，相应的目的函数值将增大5k；O
（8） 已知yi为线性规划的对偶问题的最优解，若yi>0，说明在最优生产计划中第i种资源已经完全耗尽；若yi=0，说明在最优生产计划中的第i种资源一定有剩余。O
2-2将下述线性规划问题化成标准形式。

解：(1)令，增长松弛变量，剩余变量，则该问题的标准形式如下所示：

(2)令，，，增长松弛变量，则该问题的标准形式如下所示：

2-3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解相应图解法中可行域的哪一顶点。

解：(1)图解法

最优点为B点，最优解为x1=1,x2=3/2，最优值为35/2。
单纯形表计算过程：
j初始单纯形表（相应O点）

z’
x1
x2
x3
x4
RHS

z’
1
-10
-5
0
0
0

x3
0
3
4
1
0
9
9/3
x4
0
[5]
2
0
1
8
8/5
k第一次迭代（相应A点）

z’
x1
x2
x3
x4
RHS

z’
1
0
-1
0
2
16

x3
0
0
[14/5]
1
-3/5
21/5
21/5/14/5
x1
10
1
2/5
0
1/5
8/5
8/5/4/5
l第二次迭代（相应B点，即最优解）

z’
x1
x2
x3
x4
RHS

z’
1
0
0
5/14
25/14
35/2

x2
5
0
1
5/14
-3/14
3/2

x1
10
1
0
-1/7
2/7
1

(2)图解法

最优点为B点，最优解为x1=15/4,x2=3/4，最优值为33/4。
单纯形表计算过程：
j初始单纯形表（相应O点）

z’
x1
x2
x3
x4
RHS

z’
1
-2
-1
0
0
0

x3
0
3
5
1
0
15
15/3
x4
0
[6]
2
0
1
24
24/6
k第一次迭代（相应A点）

z’
x1
x2
x3
x4
RHS

z’
1
0
-1/3
0
1/3
8

x3
0
0
[4]
1
-1/2
3
3/4
x1
2
1
1/3
0
1/6
4
4/1/3
l第二次迭代（相应B点，即最优解）

z’
x1
x2
x3
x4
RHS

z’
1
0
0
1/12
7/24
33/4

x2
1
0
1
1/4
-1/8
3/4

x1
2
1
0
-1/12
5/24
15/4

2-4已知线性规划问题，写出其对偶问题：
（1）

(2)

解：(1)原问题的对偶问题为：

(2)原问题的对偶问题为：

2-5运用对偶理论求解以下各问题：
（1）已知线性规划问题：

其最优解为
（a）求k的值；
（b）写出并求出其对偶问题的最优解。
解：原问题的对偶问题为：

设该对偶问题的三个人工变量为，由于原问题的最优解中的，则根据互补松弛性，所增长的人工变量，则：
，。
此外，原问题的最优值，也为对偶问题的最优值，即：。
结合上述三式可得：

（2）已知线性规划问题：

其对偶问题的最优解为， 。
试根据对偶理论求出原问题的最优解。
解：一方面写出原问题的对偶问题如下：

由于该对偶问题的最优解为，代入对偶问题的约束条件中可得
，即对偶问题中的松弛变量。则根据互补松弛性可知，原问题中的决策变量必为0。
将=0代入原问题中的约束条件，可得：
。又由于均不为0，则同样根据互补松弛性可知，。则有：。求解该方程组可得：。
（3）已知线性规划问题:

试根据对偶问题性质证明上述线性规划问题目的函数值无界。
解：一方面写出原问题的对偶问题如下：

由于该对偶问题中前两个约束条件所拟定的可行域为空集，可知该对偶问题无解。则根据对偶性质可知，原问题无解可无界。
此外，必为原问题的解之一，则可证原问题无界。
2-6已知某求极大值线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如表2-44所示，求表中各括弧内未知数的值。
表2-44 初始单纯形表及最终单纯形表

z
x1
x2
x3
x4
x5
x6
RHS

z
1
-3
-2
-2
0
0
0
0

x4
0
1
1
1
1
0
0
（b）

x5
0
(a)
1
2
0
1
0
15

x6
0
2
(c)
1
0
0
1
20

：：

z
x1
x2
x3
x4
x5
x6
RHS

z
1
0
（k）
（g）
0
5/4
（j）
95/4

x4
0
0
0
（d）
(l)
-1/4
-1/4
5/4

x1
3
1
0
（e）
0
3/4
（i）
25/4

x2
2
0
1
（f）
0
（h）
1/2
5/2

解：由初始单纯形表中的基变量为可知，为最终单纯形表中所相应的消耗系数矩阵，即：

则有：，可求得：
。
此外：，可求得。
再由检查数计算公式可求得；而基变量的检查数必为零，所以。即。
2-7用对偶单纯形法求解下列线性规划问题。

解：(1) 令z，=- z引进松弛变量x4，x5≥0，标准化

列出初始单纯形表

z，
x1
x2
x3
x4
x5
RHS
z，
1
4
12
18
0
0
0
x4
0
-1
0
-3
1
0
-3
x5
0
0
[-2]
-2
0
1
-5

-12/-2
-18/-2

选取x2进基。即选取a22=-2为主元，进行旋转运算，得到以下单纯形表。

z，
x1
x2
x3
x4
x5
RHS
z，
1
4
0
6
0
6
-30
x4
0
-1
0
[-3]
1
0
-3
x2
-12
0
1
1
0
-1/2
5/2

-4/-1

-6/-3

选取x4出基，a13=-3为主元进行旋转运算。

z，
x1
x2
x3
x4
x5
RHS
z，
1
2
0
0
2
6
-36
x3
-18
1/3
0
1
-1/3
0
1
x2
-12
-1/3
1
0
1/3
-1/2
3/2
当前基既是原始可行基，又是对偶可行基，因而是最优基。最优解为
x1=0，x2=3/2，x3=1，max z，=-36，即min z=36
(2) 令z，=- z引进松弛变量x4，x5≥0，标准化

列出初始单纯形表

z，
x1
x2
x3
x4
x5
RHS
z，
1
5
2
3
0
0
0
x4
0
-3
-1
-2
1
0
-4
x5
0
-6
-3
[-5]
0
1
-10

-2/-3
-3/-5

选取x3进基。即选取a23=-5为主元，进行旋转运算，得到以下单纯形表。

z，
x1
x2
x3
x4
x5
RHS
z，
1
7/5
1/5
0
0
3/5
-6
x4
0
-3/5
1/5
0
1
-2/5
0
x3
-3
6/5
3/5
1
0
-1/5
2
当前基既是原始可行基，又是对偶可行基，因而是最优基。最优解为
x1=0，x2=0，x3=2，max z，=-6，即min z=6

2-8已知2-45表为求解某线性规划问题的最终单纯形表，表中x4 , x5为松弛变量，问题的约束为≤形式。
表2-45 最终单纯形表

z
x1
x2
x3
x4
x5
RHS

z
1
0
4
0
4
2

X3

0
1/2
1
1/2
0
5/2

X1

1
-1/2
0
-1/6
1/3
5/2

（1）写出原线性规划问题；
（2）写出原问题的对偶问题；
（3）直接由原问题的最终单纯形表写出对偶问题的最优解。
解：（1）由于x4 , x5为松弛变量，则从表2-45可知，。设原问题模型为：

则由初始单纯形表和最终单纯形表之间的关系可得：
，则可得到，，，，，。
，则可得，。
此外，由最终单纯形表中检查数的计算公式可知，
则可得，，。
综上，原线性规划模型为：

（2）该模型的对偶问题为：

（3）由原问题的最终单纯形表可以得出，单纯形表中的检查数行是对偶问题决策变量的值。其中，相应对偶问题松弛变量的值，相应对偶问题决策变量的值。则对偶问题的最优解为：，。

2-9已知线性规划问题：

先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。
（1）目的函数变为
（2）约束右端项由变为;
（3）增添一个新的约束条件。
解：一方面用单纯形法得到原问题的最优单纯形表。

z
x1
x2
x3
x4
x5
RHS

z
1
0
3
1
2
0
12

x1
2
1
1
1
1
0
6

x5
0
0
3
1
1
1
10
且可得到，最终单纯形表中。
（1）由于x2在最优单纯形表中是非基变量，因此只影响它自身的检查数。计算：

得届时问题的最优解不变。但由于由-1变为3，此时必然导致检查数的符号发生变化，相应的单纯形表如下：

z
x1
x2
x3
x4
x5
RHS
z
1
0
-1
1
2
0
12
x1
2
1
1
1
1
0
6
x5
0
0
[3]
1
1
1
10
认为主元，对该单纯形表进一步迭代可得：

z
x1
x2
x3
x4
x5
RHS
z
1
0
0
4/3
7/3
1/3
46/3
x1
2
1
0
2/3
2/3
-1/3
8/3
x2
3
0
1
1/3
1/3
1/3
10/3
此时最优解变为。目的函数值变为46/3。
（2）当初始单纯形表中右端常数从(6,4)T变为(3,4)T时，即右端常数第一项减少3，则最终单纯形表中的右端常数项应为原最终单纯形表中的右端常数与B-1中第一列与（-3）乘积之和，即：(6,10) T+(-3)*(1,1) T =(6-3,10-3)=(3,7) T。
则可知，最优解变为，最优值变为27。
（3）先将原问题最优解变量值代入，因有
-6+0=-6< 2 ，即原问题的最优解不满足新的约束条件。
故将约束条件写成：
-x1+x3-x6=2
两边同乘以-1，得到
x1-x3+x6=-2
并取x6作为新的基变量，得到新的单纯形表：

z
x1
x2
x3
x4
x5
x6
RHS
z
1
0
3
1
2
0
0
12
x1
2
1
1
1
1
0
0
6
x5
0
0
3
1
1
1
0
10
x6
0
1
0
-1
0
0
1
-2
消去x1在第三个约束中的系数，使得基变量x1在约束条件中的系数成为单位向量：

z
x1
x2
x3
x4
x5
x6
RHS
z
1
0
3
1
2
0
0
12
x1
2
1
1
1
1
0
0
6
x4
0
0
3
1
1
1
0
10
x5
0
0
-1
[-2]
-1
0
1
-2
用对偶单纯形法继续求解，x6离基，x3进基：

z
x1
x2
x3
x4
x5
x6
RHS
z
1
0
5/2
0
5/3
0
1/3
8
x1
2
1
1/2
0
1/2
0
1/2
2
x4
0
0
5/2
0
1/2
1
1/2
6
x3
1
0
1/2
1
1/2
0
-1/2
1
新的最优解为（x1,x2,x3,x4,x5,x6）T=（2,0,1,6,0,0）T，max z=8。

2-10某厂生产A，B，C三种产品，其所需劳动力、材料等有关数据见表2-46。规定：（1）拟定利润最大的产品生产计划；（2）产品A的利润在什么范围内变动时，上述最优计划不变；（3）假如设计一种新产品D，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？（4）假如劳动力数量不增，材料局限性时可从市场购买，每单位0.4元。问该厂要不要购进原材料扩大生产，以购多少为宜。（5）由于某种因素该厂决定暂停A产品的生产，试重新拟定该厂的最优生产计划。

表2-46 产品单位利润及资源消耗
消耗定额产品
资源
A B C
可用量（单位）
劳动力
材料
6 3 5
3 4 5
45
30
产品利润（元/件）
3 1 4

解：（1）设生产A,B,C三种产品的件数分别为，则依据题意可得问题的线性规划模型如下：

用单纯形法求得该模型的最优单纯形表如下：

z
x1
x2
x3
x4
x5
RHS
z
1
0
2
0
1/5
3/5
27
x1
3
1
-1/3
0
1/3
-1/3
5
x3
4
0
1
1
-1/5
2/5
3
即：为使获得利润最大，产品A需生产5件，产品B不生产，产品C生产3件，此时获得总利润为27元。
（2）设产品A的利润为，由于决策变量在最优单纯形表中是基变量，此时的变化会带来所有非基变量检查数的变化。为使（1）所求得的最优计划不变，需要下表中所有非基变量检查数的值均为非负，即：

z
x1
x2
x3
x4
x5
RHS
z
1
0

0

27
x1
c1
1
-1/3
0
1/3
-1/3
5
x3
4
0
1
1
-1/5
2/5
3

解该不等式组可得：。即在[12/5,24/5]的范围内最优计划不变。
（3）设计新产品D相称于增长决策变量。一方面可由（1）中的最优单纯形表得到，，则由于增长决策变量带来最优单纯形表中的检查数为=-1/5，且消耗系数列=(2,-4/5)T。则新的单纯形表为：

z
x1
x2
x3
x4
x5
x6
RHS
z
1
0
2
0
1/5
3/5
-1/5
27
x1
3
1
-1/3
0
1/3
-1/3
2
5
x3
4
0
1
1
-1/5
2/5
-4/5
3
由于增长决策变量后求得的最优单纯形表为：

z
x1
x2
x3
x4
x5
x6
RHS
z
1
1/10
89/30
0
7/30
17/30
0
55/2
x6
3
1/2
-1/6
0
1/6
-1/6
1
5/2
x3
4
2/5
13/15
1
-1/15
4/15
0
5
由于生产产品D后带来最优总利润变为55/2>27，即该产品值得生产。
（4）由原问题的最优单纯形表可知，该问题对偶问题的最优解为：，即劳动力的影子价格为0.2，材料的影子价格为0.6。
而市场上材料的价格仅为0.4。由于影子价格>市场价格，此时可以通过购买材料进行生产。设从市场上购买个单位的材料，则问题的最优单纯形表变为：

z
x1
x2
x3
x4
x5
RHS
z
1
0
2
0
1/5
3/5
27+
x1
3
1
-1/3
0
1/3
-1/3
5-
x3
4
0
1
1
-1/5
2/5
3+
此时当，即时，问题的最优解为。但当时，右端项第一行<0，此时根据对偶单纯形法，需要x1出基，x5进基，可得x5的检查数为零，即材料的影子价格变为零。
因此，应从市场上购买15个单位的材料。
（5）暂停A产品的生产，相称于删除决策变量，对由剩余变量求解，可得问题的模型变为：

可求得最优解为：，最优值。
2-11已知运送问题的供求关系和单位运价表如表2-47所示，试用表上作业法求出问题的最优解。
（1）表2-47（a）
销地
产地
B1
B2
B3
B4
产量
A1
3
2
7
6
50
A2
7
5
2
3
60
A3
2
5
4
5
25
销量
60
40
20
15

解：采用Vogel法获得初始基本可行解。

B1
B2
B3
B4

A1
3

2

7

6

50

10

40

A2
7

5

2

3

60

25

20

15
A3
2

5

4

5

25

25

60
40
20
15

计算该解下各非基变量的检查数，可得：

B1
B2
B3
B4

7
2
A1
3

2

7

6

50

10

40

-1
A2
7

5

2

3

60

25

20

15
7
0
4
A3
2

5

4

5

25

25

60
40
20
15

X22的检查数<0，此时应将X22进基，更新解及非基变量的检查数可得：

B1
B2
B3
B4

6
8
A1
3

2

7

6

50

35

15

1
A2
7

5

2

3

60

25

20

15
6
6
4
A3
2

5

4

5

25

25

60
40
20
15

可知，该解中非基变量检查数均为非负，为最优解。即A1往B1运35，往B2运15；A2往B2、B3、B4分别运25、20、15单位；A3往B1运25单位。最优值为：395。

（2）表2-47（b）
销地
产地
B1
B2
B3
B4
产量
A1
18
14
17
12
100
A2
5
8
13
15
100
A3
17
7
12
9
150
销量
50
70
60
80

解：由于总产量为350，而总销量为260，即产大于销的运送问题。因此，通过增长一个假想的销地B5，销量为90，运价均为0，使其变为产销平衡的运送问题。问题更新为：
销地
产地
B1
B2
B3
B4
B5
产量
A1
18
14
17
12
0
0
100
100
A2
5
8
13
15
A3
17
7
12
9
0
150
销量
50
70
60
80
90

采用Vogel法获得初始基本可行解，并计算非基变量的检查数如下：

B1
B2
B3
B4

B5

-2
2
9
A1
18

14

17

12

0

100

10

90
4
5
0
A2
5

8

13

15

0

100

50

50

5
13
A3
17

7

12

9

0

150

70

0

80

50
70
60
80

90

X14的检查数<0，此时应将X14进基，更新解及非基变量的检查数可得：

B1
B2
B3
B4

B5

2
4
1
A1
18

14

17

12

0

100

10

90
2
5
0
A2
5

8

13

15

0

100

50

50

3
13
A3
17

7

12

9

0

150

70

10

70

50
70
60
80

90

可知，该解中非基变量检查数均为非负，为最优解。即A1往B4运10，往B5运90；A2往B1运50，往B3运50；A3往B2运70，B3运10，B4运70单位。最优值为：2260。

2-12 1，2，3三个城市每年需分别供应电力320,250,和350单位，由Ⅰ，II两个电站提供，它们的最大可供电量分别为400个单位和450个单位，单位费用如表2-23所示。由于需要量大于可供量，决定城市1的供应量可减少0~30单位，城市2的供应量不变，城市3的供应量不能少于270单位，试求总费用最低的分派方案（将可供电量用完）。
表2-48 供应电力单位费用表
城市
电站
1
2
3
I
15
18
22
II
21
25
16

解：建立该问题的表式模型如下：
城市
电站
1
1’
2
3
3’
供应量
I
15
15
18
22
22
400
II
21
21
25
16
16
450
III(虚拟)
M
0
M
M
0
70
需求量
290
30
250
270
80

对该运送问题进行求解，可得

1
1’
2
3

3’

2
2
5
I
15

15

18

22

22

400

150

250

1
5
II
21

21

25

16

16

450

140

270

40
M
M-8
M-5
III
M

0

M

M

0

70

30

40

290
30
250
270

80

为该问题的最优解，即I向城市1供电150单位，向2供电250单位；II向城市1供电140单位，向城市3供电310单位。此时总费用为：14650。

2-13已知某运送问题的运送表及给出的一个最优调运方案分别见表2-49，试拟定表2-49中k的取值范围。
表2-49 运送表及最优调运方案

1
2
3
4

K+10
K-3
1
10

1

20

11

15

5

10
10-K
2
12

k

9

20

25

0

10

15

18-K
17
24-K
3
2

14

16

18

5

5

5
15
15
10

解：计算表中非基变量的检查数，直接标示在表2-49中。
如该表为最优方案，则需：
k-3>=0,k+10>=0,10-k>=0,24-k>=0,18-k>=0。
取前述不等式解的交集，可得k的取值范围为：3<=k<=10。
2-14某糖厂每月最多生产糖270 t，先运至A1A2A3三个仓库，然后再分别供应
五个地区的需要。已知各仓库的容量分别为50,100,150（t），各地区的需要量分别为25,105,60,30,70（t）。已知从糖厂经各仓库然后供应各地区的运费和存储费如表2-50所示。
表2-50运费及存储费

B1
B2
B3
B4
B5
A1
10
15
20
20
40
A1
20
40
15
30
30
A1
30
35
40
55
25
试拟定一个使总费用最低的调运方案。（暂时不用考虑本题，待和出题老师核算后再公布该题答案）

2-15一艘货轮分前、中、后三个舱位，它们的容积与最大允许的载重量如表2-51和2-52所示，现有三种货品待运，已知有关数据列于表2-27（b）
2-51 容积及最大允许的载重量
项目
前舱
中舱
后舱
最大允许载重量（t）
2023
3000
1500
容积（m3）
4000
5400
1500
2-52 待运货品单件体积、重量及运价
商品
数量（件）
每件体积（m3/件）
每件重量（t/件）
运价（元/件）
A
600
10
8
1000
B
1000
5
6
700
C
800
7
5
600
又为了航运安全，前、中、后舱的实际载重量大体保持各舱最大允许载重量的比例关系。具体规定：前、后舱分别与中舱之间载重量比例的偏差不超过15%,前后舱之间不超过10%。问该货轮应装载A、B、C各多少件运费收入才最大？试建立这个问题的线性规划模型。
解：设决策变量（）表达由前、中、后舱装载货品、、的数量，则模型为：

s.t.
，，（船舱载重量约束）
， ，（船舱体积约束）
，，（货品数量约束）
，，，，，（载重量比例约束）

2-16一贸易公司专门经营某种杂粮的批发业务。公司现有库容5000担的仓库。1月1日，公司拥有库存1000担杂粮，并有资金20230元。估计第一季度杂粮价格如表2-53所示。
如买进的杂粮当月到货，但需到下月才干卖出，且规定“货到付款”。公司希望本季末库存为2023担。问：应采用什么样的买进与卖出的策略使3个月总的获利最大？（列出问题的线性规划模型，不求解）
表2-53 各月份的进货单价及出货单价
月份
进货价/（元/担）
出货价/（元/担）
1
2.85
3.10
2
3.05
3.25
3
2.90
2.95
解：设决策变量（）表达1、2、3月买进、卖出的杂粮担数，则模型如下：

s.t.
，
，（仓库容量约束）
，（季末库存约束）
，
，
（资金约束）
，，（“下月卖出”约束）

2-17某农户年初承保了40亩土地，并备有生产专用资金25 000元。该户劳动力情况为：春夏季4 000工时，秋冬季3 500工时。若有闲余工时则将为别的农户帮工，其收入为：春夏季5元/ 工时，秋冬季4元/ 工时。该户承包的地块只是以种植大豆、玉米、小麦，为此已备齐各种生产资料，因此不必动用钞票。此外，该农户还饲养奶牛和鸡。每头奶牛每年需投资4 000元，每只鸡需投资30元。每头奶牛需用地1.5亩种植饲草，并占用劳动力：春夏季50工时、秋冬季100工时，每年净收入4 000元。每只鸡占用劳动力：春夏季0.3工时、秋冬季0.6工时，每年净收入100元。该农户现有鸡舍最多能容纳300只鸡，牛棚最多能容纳8头奶牛。三种农作物一年需要的劳动力及收入情况见表2-54。问该农户应如何拟定经营方案才干使当年净收入最大？试建立该问题的数学模型。
表2-54 三种农作物需要的劳动力及收入情况
种类
需用工时（工时/ 亩）
春夏季需工时
秋冬季需工时
净收入/（元/ 亩）
大豆
20
50
500
玉米
35
75
800
小麦
10
40
400
解：设决策变量表达饲养牛、鸡的头数()，决策变量为种植大豆、玉米和小麦的亩数()，则模型如下：
s.t.
（土地面积约束）
（资金约束）
，（鸡舍、牛棚约束）
，
（劳动力约束）

2-18对某厂I，II，III三种产品下一年各季度的协议预订数如表2-55所示。
表2-55 三种产品下一年各季度的协议预订数
产品
季度
1
2
3
4
I
1 500
1 000
2 000
1 200
II
1 500
1 500
1 200
1 500
III
1 000
2 000
1 500
2 500

该三种产品1季度初无库存，规定在4季度末各库存150件。已知该厂每季度生产工时为15 000 h，生产I，II，III产品每件分别需时2、4、3 h。因更换工艺装备，产品I在2季度无法生产。规定当产品不能按期交货时，产品I、II每件每迟交一个季度补偿20元，产品III补偿10元；又生产出的产品不在本季度交货的，每件每季度的库存费用为5元。问该厂应如何安排生产，使总的补偿加库存费用为最小（规定建立数学模型，不需求解）。
解：设Xij为第j季度生产的产品i的数量，sij为第j季度末需库存的产品i的数量，Fij为第j季度末交货的产品i的数量，Rij为第j季度对产品i的预订数，则有