运筹学1至6章习题参考答案.doc

80
运筹学(第3版) 习题答案
运筹学1至6章习题参考答案

第1章 线性规划
1.1 工厂每月生产A、B、C三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示．
表1－23
产品
资源
A
B
C
资源限量
材料(kg)
1.5
1.2
4
2500
设备(台时)
3
1.6
1.2
1400
利润(元/件)
10
14
12

根据市场需求,预测三种产品最低月需求量分别是150、260和120,最高月需求是250、310和130.试建立该问题的数学模型,使每月利润最大．
【解】设x1、x2、x3分别为产品A、B、C的产量，则数学模型为

1.2 建筑公司需要用5m长的塑钢材料制作A、B两种型号的窗架．两种窗架所需材料规格及数量如表1－24所示：
表1－24 窗架所需材料规格及数量

型号A
型号B
每套窗架需要材料
长度（m）
数量(根)
长度(m)
数量(根)
A1：2
2
B1：2.5
2
A2：1.5
3
B2：2
3
需要量（套）
300
400
问怎样下料使得（1）用料最少；（2）余料最少．
【解】 第一步：求下料方案，见下表。
　方案
一
二
三
四
五
六
七
八
九
十
需要量
B1
2.5
2
1
1
1
0
0
0
0
0
0
800
B2
2
0
1
0
0
2
1
1
0
0
0
1200
A1
2
0
0
1
0
0
1
0
2
1
0
600
A2
1.5
0
0
0
1
0
0
2
0
2
3
900
余料(m)

0
0.5
0.5
1
1
1
0
1
0
0.5

第二步：建立线性规划数学模型
设xj（j=1,2,…，10）为第j种方案使用原材料的根数，则
（1）用料最少数学模型为

（2）余料最少数学模型为

1.3某企业需要制定1～6月份产品A的生产与销售计划。已知产品A每月底交货，市场需求没有限制，由于仓库容量有限，仓库最多库存产品A1000件，1月初仓库库存200件。1～6月份产品A的单件成本与售价如表1－25所示。
表1－25
月份
1 2 3 4 5 6
产品成本(元/件)
销售价格(元/件)
300 330 320 360 360 300
350 340 350 420 410 340
（1）1～6月份产品A各生产与销售多少总利润最大，建立数学模型；
（2）当1月初库存量为零并且要求6月底需要库存200件时，模型如何变化。
【解】设xj、yj（j＝1，2，…，6）分别为1～6月份的生产量和销售量，则数学模型为
（1）
（2）目标函数不变，前6个约束右端常数800改为1000，第7～11个约束右端常数200改为0，第12个约束“≤200”改为“＝－200”。

1.4 某投资人现有下列四种投资机会, 三年内每年年初都有3万元（不计利息）可供投资：
方案一：在三年内投资人应在每年年初投资，一年结算一次，年收益率是20％，下一年可继续将本息投入获利；
方案二：在三年内投资人应在第一年年初投资，两年结算一次，收益率是50％，下一年可继续将本息投入获利，这种投资最多不超过2万元；
方案三：在三年内投资人应在第二年年初投资，两年结算一次，收益率是60％，这种投资最多不超过1.5万元；
方案四：在三年内投资人应在第三年年初投资，一年结算一次，年收益率是30％，这种投资最多不超过1万元．
投资人应采用怎样的投资决策使三年的总收益最大，建立数学模型.
【解】是设xij为第i年投入第j项目的资金数，变量表如下

项目一
项目二
项目三
项目四
第1年
第2年
第3年
x11
x21
x31
x12

x23

x34
数学模型为

最优解X=(30000，0，66000，0，109200，0)；Z＝84720

1.5 炼油厂计划生产三种成品油，不同的成品油由半成品油混合而成，例如高级汽油可以由中石脑油、重整汽油和裂化汽油混合，辛烷值不低于94，每桶利润5元，见表1－26。
表1－26
成品油
高级汽油
一般汽油
航空煤油
一般煤油
半成品油
中石脑油
重整汽油
裂化汽油
中石脑油
重整汽油
裂化汽油
轻油、裂化油、重油、残油
轻油、裂化油、重油、残油按10:4:3:1调合而成
辛烷值
≥94
≥84

蒸汽压：公斤／平方厘米

≤1

利润(元/桶)
5
4.2
3
1.5
半成品油的辛烷值、气压、及每天可供应数量见表1－27。
表1－27
半成品油
1中石脑油
2重整汽油
3裂化汽油
4轻油
5裂化油
6重油
7残油
辛烷值
80
115
105

蒸汽压：公斤／平方厘米

1.0
1.5
0.6
0.05
每天供应数量(桶)
2000
1000
1500
1200
1000
1000
800
问炼油厂每天生产多少桶成品油利润最大，建立数学模型。
解 设xij为第i（i＝1,2,3,4）种成品油配第j(j=1,2,…,7)种半成品油的数量（桶）。
总利润：
高级汽油和一般汽油的辛烷值约束

航空煤油蒸气压约束

一般煤油比例约束

即

半成品油供应量约束

整理后得到

1.6 图解下列线性规划并指出解的形式：
(1)
【解】最优解X＝（3，2）；最优值Z=19

(2)
【解】有多重解。最优解X（1）＝（0，5/4）；X（2）＝（3，1/2）最优值Z=5

(3)
【解】最优解X＝（4，1）；最优值Z=－10，有唯一最优解

(4)
【解】最优解X＝（2，3）；最优值Z=26，有唯一最优解

(5)
【解】无界解。

(6)
【解】无可行解。

1.7 将下列线性规划化为标准形式
(1)
【解】（1）令为松驰变量 ，则标准形式为

(2)
【解】（2）将绝对值化为两个不等式，则标准形式为

(3)
【解】方法1：

方法2：令

则标准型为

(4)
【解】令，线性规划模型变为

标准型为

1.8 设线性规划

取基分别指出对应的基变量和非基变量，求出基本解，并说明是不是可行基．
【解】B1：x1、x3为基变量，x2、x4为非基变量,基本解为X=（15，0，10，0）T，B1是可行基。B2：x2、x4是基变量，x1、x3为非基变量，基本解X=（0，20，0，100）T，B2是可行基。

1.9分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点．
(1)
【解】图解法
单纯形法：
C(j)
1
3
0
0
b
Ratio
　C(i)
Basis　
X1
X2
X3
X4
0
X3
-2
[1]
1
0
2
2
0
X4
2
3
0
1
12
4
C(j)-Z(j)
1
3
0
0
0

3
X2
-2
1
1
0
2
M
0
X4
[8]
0
-3
1
6
0.75
C(j)-Z(j)
7
0
-3
0
6

3
X2
0
1
0.25
0.25
7/2

1
X1
1
0
-0.375
0.125
3/4

C(j)-Z(j)
0
0
-0.375
-0.875
45/4

对应的顶点：
基可行解
可行域的顶点
X(1)=（0，0，2，12）、
X(2)=（0，2，0，6，）、
X(3)=（、
（0，0）
（0，2）

最优解

(2)
【解】图解法

单纯形法：
C(j)
-3
-5
0
0
0
b
Ratio
Basis　
C(i)　
X1
X2
X3
X4
X5
X3
0
1
2
1
0
0
6
3
X4
0
1
[4]
0
1
0
10
2.5
X5
0
1
1
0
0
1
4
4
C(j)-Z(j)
-3
-5
0
0
0
0

X3
0
[0.5]
0
1
-0.5
0
1
2
X2
-5
0.25
1
0
0.25
0
2.5
10
X5
0
0.75
0
0
-0.25
1
1.5
2
C(j)-Z(j)
-1.75
0
0
1.25
0
-12.5

X1
-3
1
0
2
-1
0
2
M
X2
-5
0
1
-0.5
0.5
0
2
4
X5
0
0
0
-1.5
[0.5]
1
0
0
C(j)-Z(j)
0
0
3.5
-0.5
0
-16

X1
-3
1
0
-1
0
2
2

X2
-5
0
1
1
0
-1
2

X4
0
0
0
-3
1
2
0

C(j)-Z(j)
0
0
2
0
1
-16

对应的顶点：
基可行解
可行域的顶点
X(1)=（0，0，6，10，4）、
X(2)=（0，2.5，1，0，1.5，）、
X(3)=（2，2，0，0，0）
X(4)=（2，2，0，0，0）

（0，0）
（0，2.5）
(2，2)
（2，2）
最优解：X=（2，2，0，0，0）；最优值Z＝－16
该题是退化基本可行解，5个基本可行解对应4个极点。

1.10用单纯形法求解下列线性规划
(1)
【解】单纯形表：
C(j)
3
4
1
0
0
R. H. S.
Ratio　
Basis
C(i)
X1
X2
X3
X4
X5
X4
0
2
[3]
1
1
0
4
4/3
X5
0
1
2
2
0
1
3
3/2
C(j)-Z(j)
3
4
1
0
0
0

X2
4
[2/3]
1
1/3
1/3
0
4/3
2
X5
0
-1/3
0
4/3
-2/3
1
1/3
M
C(j)-Z(j)
1/3
0
-1/3
-4/3
0
－16/3

X1
3
1
3/2
1/2
1/2
0
2

X5
0
0
1/2
3/2
-1/2
1
1

C(j)-Z(j)
0
-1/2
-1/2
-3/2
0
-6

最优解：X=（2，0，0，0，1）；最优值Z＝6

(2)
【解】单纯形表：

C(j)
2
1
-3
5
0
0
0
R. H. S.
Ratio
Basis
C(i)
X1
X2
X3
X4
X5
X6
X7
X5
0
1
5
3
-7
1
0
0
30
M
X6
0
3
-1
[1]
1
0
1
0
10
10
X7
0
2
-6
-1
[4]
0
0
1
20
5
C(j)-Z(j)
2
1
-3
5
0
0
0

X5
0
9/2
-11/2
5/4
0
1
0
7/4
65
M
X6
0
5/2
[1/2]
5/4
0
0
1
-1/4
5
10
X4
5
1/2
-3/2
-1/4
1
0
0
1/4
5
M
C(j)-Z(j)
-1/2
17/2
-7/4
0
0
0
-5/4

X5
0
32
0
15
0
1
11
-1
120
M
X2
1
5
1
5/2
0
0
2
-1/2
10
10
X4
5
8
0
7/2
1
0
3
-1/2
20
M
C(j)-Z(j)
-43
0
-23
0
0
-17
3

因为λ7＝3>0并且ai7<0(i=1,2,3)，故原问题具有无界解，即无最优解。

(3)
【解】
C(j)
3
2
-0.125
0
0
0
R. H. S.
Ratio　
Basis
C(i)
X1
X2
X3
X4
X5
X6
X4
0
-1
2
3
1
0
0
4
M
X5
0
[4]
0
-2
0
1
0
12
3
X6
0
3
8
4
0
0
1
10
10/3
C(j)-Z(j)
3
2
-1/8
0
0
0
0

X4
0
0
2
5/2
1
1/4
0
7
3.5
X1
3
1
0
-1/2
0
1/4
0
3
M
X6
0
0
[8]
11/2
0
-3/4
1
1
1/8
C(j)-Z(j)
0
2
11/8
0
-3/4
0
9

X4
0
0
0
9/8
1
7/16
-1/4
27/4
6
X1
3
1
0
-1/2
0
1/4
0
3
M
X2
2
0
1
[11/16]
0
-3/32
1/8
1/8
0.181818
C(j)-Z(j)
0
0
0
0
-9/16
-1/4
37/4

X3进基、X2出基，得到另一个基本最优解。

C(j)
3
2
-0.125
0
0
0
R. H. S.
Ratio
Basis

X1
X2
X3
X4
X5
X6
X4
0
0
-18/11
0
1
13/22
-5/11
72/11
6
X1
3
1
8/11
0
0
2/11
1/11
34/11
M
X3
-0.125
0
16/11
1
0
-3/22
2/11
2/11
0.1818
C(j)-Z(j)
0
0
0
0
-9/16
-1/4
37/4

原问题具有多重解。
基本最优解,最优解的通解可表示为即

（4）
【解】单纯形表：
C(j)
3
2
1
0
0
R. H. S.
Ratio
Basis
C(i)　
X1
X2
X3
X4
X5
X4
0
5
4
6
1
0
25
5
X5
0
[8]
6
3
0
1
24
3
C(j)-Z(j)
3
2
1
0
0
0

X4
0
0
1/4
33/8
1
-5/8
10

X1
3
1
3/4
3/8
0
1/8
3

C(j)-Z(j)
0
-1/4
-1/8
0
-3/8
9

最优解：X=（3，0，0，10，0）；最优值Z＝9

1.11 分别用大M法和两阶段法求解下列线性规划：
(1)
【解】大M法。数学模型为

C(j)
10
-5
1
0
-M
R. H. S.
Ratio
Basis
C(i)
X1
X2
X3
X4
X5
X5
-M
5
3
1
0
1
10
2
X4
0
-5
1
-10
1
0
15
M
C(j)-Z(j)
10
-5
1
0
0
0

* Big M
5
3
1
0
0
0

X1
10
1
3/5
1/5
0
1/5
2

X4
0
0
4
-9
1
1
25

C(j)-Z(j)
0
-11
-1
0
-2
20

* Big M
0
0
0
0
-1
0

最优解X＝(2,0,0)；Z=20
两阶段法。
第一阶段：数学模型为

C(j)
0
0
0
0
1
R. H. S.
Ratio
Basis
C(i)
X1
X2
X3
X4
X5
X5
1
[5]
3
1
0
1
10
2
X4
0
-5
1
-10
1
0
15
M
C(j)-Z(j)
-5
-3
-1
0
0

X1
0
1
3/5
1/5
0
1/5
2

X4
0
0
4
-9
1
1
25

C(j)-Z(j)
0
0
0
0
1

第二阶段
C(j)
10
-5
1
0
R. H. S.
Ratio
Basis
C(i)
X1
X2
X3
X4　
X1
10
1
3/5
1/5
0　
2
2
X4
0
0
4
-9
1　
25
M
C(j)-Z(j)
0
-11
-1
0　

最优解X=(2,0,0)；Z=20

(2)
【解】大M法。数学模型为

C(j)
5
-6
-7
0
0
M
M
R.H.S.
Ratio
Basis
C(i)
X1
X2
X3
S1
S2
A1
A3
A1
M
1
[5]
-3
-1
0
1
0
15
3
S2
0
5
-6
10
0
1
0
0
20
M
A3
M
1
1
1
0
0
0
1
5
5
C(j)-Z(j)
5
-6
-7
0
0
0
0

* Big M
-2
-6
2
1
0
0
0
X2
-6
1/5
1
-3/5
-1/5
0
1/5
0
3　
M
S2
0
31/5
0
32/5
-6/5
1
6/5
0
38
95/16
A3
M
4/5
0
[8/5]
1/5
0
-1/5
1
2
5/4
C(j)-Z(j)
31/5
0
-53/5
-6/5
0
6/5
0

* Big M
-4/5
0
-8/5
-1/5
0
6/5
0
X2
-6
1/2
1
0
-1/8
0
1/8
3/8
15/4　

S2
0
3
0
0
-2
1
2
-4
30

X3
-7
1/2
0
1
1/8
0
-1/8
5/8
5/4

C(j)-Z(j)
23/2
0
0
1/8
0
-1/8
53/8

* Big M
0
0
0
0
0
1
1
两阶段法。
第一阶段：数学模型为

C(j)
0
0
0
0
0
1
1
R.H.S.
Ratio
Basis
C(i)
X1
X2
X3
S1
S2
A1
A3
A1
1
1
[5]
-3
-1
0
1
0
15
3
S2
0
5
-6
10
0
1
0
0
20
M
A3
1
1
1
1
0
0
0
1
5
5
C(j)-Z(j)
-2
-6
2
1
0
0
0

X2
0
1/5
1
-3/5
-1/5
0
1/5
0
3
M
S2
0
31/5
0
32/5
-6/5
1
6/5
0
38
95/16
A3
1
4/5
0
[8/5]
1/5
0
-1/5
1
2
5/4
C(j)-Z(j)
-4/5
0
-8/5
-1/5
0
6/5
0

X2
0
1/2
1
0
-1/8
0
1/8
3/8
15/4　

S2
0
3
0
0
-2
1
2
-4
30

X3
0
1/2
0
1
1/8
0
-1/8
5/8
5/4

C(j)-Z(j)
0
0
0
0
0
1
1

第二阶段：
C(j)
5
-6
-7
0
0
R.H.S.
Ratio
Basis
C(i)
X1
X2
X3
S1
S2
X2
-6
1/2
1
0
-1/8
0
15/4　
3
S2
0
3
0
0
-2
1
30
M
X3
-7
1/2
0
1
1/8
0
5/4
5
C(j)-Z(j)
23/2
0
0
1/8
0

最优解：

(3)
【解】大M法。数学模型为

C(j)
10
15
0
0
0
-M
R. H. S.
Ratio
Basis
C(i)
X1
X2
X3
X4
X5
X6

X3
0
[5]
3
1
0
0
0
9
1.8
X4
0
-5
6
0
1
0
0
15
M
X6
-M
2
1
0
0
-1
1
5
2.5
C(j)-Z(j)
10
15
0
0
0
0
0

* Big M
2
1
0
0
-1
0
0

X1
10
1
3/5
1/5
0
0
0
9/5

X4
0
0
9
1
1
0
0
24

X6
-M
0
-1/5
-2/5
0
-1
1
7/5

C(j)-Z(j)
0
9
-2
0
0
0
18

* Big M
0
-1/5
-2/5
0
-1
0
0

因为X6>0,原问题无可行解。
两阶段法
第一阶段：数学模型为

C(j)
0
0
0
0
0
1
R. H. S.
Ratio
Basis
C(i)
X1
X2
X3
X4
X5
X6

X3
0
[5]
3
1
0
0
0
9
1.8
X4
0
-5
6
0
1
0
0
15
M
X6
1
2
1
0
0
-1
1
5
2.5
C(j)-Z(j)
-2
-1
0
0
1
0
5
14
X1
0
1
3/5
1/5
0
0
0
9/5

X4
0
0
9
1
1
0
0
24

X6
1
0
-1/5
-2/5
0
-1
1
7/5

C(j)-Z(j)
0
1/5
2/5
0
1
0

因为X6>0,原问题无可行解。图解法如下：

(4)
【解】大M法。X7是人工变量，数学模型为

Cj
4
2
5
0
0
0
－M
R.H.S.
Ratio
CB
XB
X1
X2
X3
X4
X5
X6
X7

0
X4
6
-1
4
1

10

0
X5
3
-3
-5

1

8

－M
X7
1
[2]
1

－1
1
20
10
C(j)-Z(j)
4
2
5

* Big M
M
2M
M

－1

0
X4
13/2

[9/2]
1

-1/2
1/2
20

0
X5
9/2

-7/2

1
-3/2
3/2
38

2
X2
1/2
1
1/2

-1/2
1/2
10

C(j)-Z(j)
3

4

1
-1

* Big M

-1

5
X3
13/9

1
2/9

-1/9
1/9
40/9

0
X5
86/9

7/9
1
-17/9
17/9
482/9

2
X2
-2/9
1

-1/9

-4/9
4/9
70/9

C(j)-Z(j)
-25/9

-8/9

13/9
-13/9

* Big M

-1

无界解。
两阶段法。第一阶段：

Cj

0
0
0
1
R.H.S.
Ratio
CB
XB
X1
X2
X3
X4
X5
X6
X7

0
X4
6
-1
4
1

10

0
X5
3
-3
-5

1

8

1
X7
1
[2]
1

－1
1
20
10
C(j)-Z(j)
－1
－2
－1

1

0
X4
13/2

[9/2]
1

-1/2
1/2
20

0
X5
9/2

-7/2

1
-3/2
3/2
38

2
X2
1/2
1
1/2

-1/2
1/2
10

C(j)-Z(j)

1

第二阶段：
Cj
4
2
5
0
0
0
R.H.S.
Ratio
CB
XB
X1
X2
X3
X4
X5
X6

0
X4
13/2

[9/2]
1

-1/2
20

0
X5
9/2

-7/2

1
-3/2
38

1
X2
1/2
1
1/2

-1/2
10

C(j)-Z(j)
7/2

9/2

1/2

0
X3
13/9

1
2/9

-1/9
40/9

0
X5
86/9

7/9
1
-17/9
482/9

2
X2
-2/9
1

-1/9

-4/9
70/9

C(j)-Z(j)
-3

-1

1

原问题无界解。

1.12 在第1.9题中，对于基求所有变量的检验数,并判断B是不是最优基．
【解】,

B不是最优基，可以证明B是可行基。
1.13已知线性规划

的最优基为，试用矩阵公式求（1）最优解；(2)单纯形乘子；(3)(4)
【解】
则
(1)
(2)
(3)

(4)

注：该题有多重解：
X(1)=(0，5，0，5/2)
X(2)=(0，10/3，10/3，0)
X(3)=(10，0，0，0)，x2是基变量，X(3)是退化基本可行解
Z＝50
1.14 已知某线性规划的单纯形表1－28, 求价值系数向量C及目标函数值Z．
表1－28
Cj
c1
c2
c3
c4
c5
c6
c7
b
CB
XB
x1
x2
x3
x4
x5
x6
x7
3
x4
0
1
2
1
－3
0
2
4
4
x1
1
0
－1
0
2
0
－1
0
0
x6
0
－1
4
0
－4
1
2
3/2
λj
0
－1
－1
0
1
0
－2

【解】由有
c2＝－1＋（3×1＋4×0＋0×（－1））＝2
c3＝－1＋（3×2＋4×（－1）＋0×4）＝1
c5＝1＋（3×（－3）＋4×2＋0×（－4））＝0
c7＝-2＋（3×2＋4×(－1)＋0×2）＝0
则C＝(4,2,1,3,0,0,0,)，Z=CBXB=12

1.15 已知线性规划

的最优单纯形表如表1－29所示，求原线性规划矩阵C、A、及b，最优基B及．
表1－29
Cj
c1
c2
c3
c4
c5
b
CB
XB
x1
x2
x3
x4
x5
c1
x1
1
0
4
1/6
1/15
6
c2
x2
0
1
－3
0
1/5
2
λj
0
0
－1
－2
－3

【解】由c4＝c5＝0，
由公式得

由
得
由
得
1.16思考与简答
（1）在例1.2中，如果设xj(j=1，2，…，7)为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化。
（2）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路。
（3）在例1.4中，若允许含有少量杂质，但杂质含量不超过1％，模型如何变化。
（4）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化。
(5)在单纯形法中，为什么说当时线性规划具有无界解。
(6)选择出基变量为什么要遵循最小比值规则，如果不遵循最小比值规则会是什么结果。
（7）简述大M法计算的基本思路，说明在什么情形下线性规划无可行解。
（8）设X(1)、X(2)、X(3)是线性规划的3个最优解，试说明

也是线性规划的最优解。
（9）什么是基本解、可行解、基本可行解、基本最优解，这四个解之间有何关系。
（10）简述线性规划问题检验数的定义及其经济含义。

返回顶部

第2章 线性规划的对偶理论
2.1某人根据医嘱，每天需补充A、B、C三种营养，A不少于80单位，B不少于150单位，C不少于180单位．此人准备每天从六种食物中摄取这三种营养成分．已知六种食物每百克的营养成分含量及食物价格如表2-22所示．（1）试建立此人在满足健康需要的基础上花费最少的数学模型；（2）假定有一个厂商计划生产一中药丸，售给此人服用，药丸中包含有A，B，C三种营养成分．试为厂商制定一个药丸的合理价格，既使此人愿意购买，又使厂商能获得最大利益，建立数学模型．
表2-22
含量 食物

营养成分

一

二

三

四

五

六

需要量
A
13
25
14
40
8
11
≥80
B
24
9
30
25
12
15
≥150
C
18
7
21
34
10
0
≥180
食物单价（元/100g）
0.5
0.4
0.8
0.9
0.3
0.2

【解】（1）设xj为每天第j种食物的用量，数学模型为

（2）设yi为第i种单位营养的价格，则数学模型为

2.2写出下列线性规划的对偶问题
（1） 【解】
（2） 【解】
（3） 【解】
（4） 【解】
对偶问题为：
2.3考虑线性规划

(1)说明原问题与对偶问题都有最优解；
(2)通过解对偶问题由最优表中观察出原问题的最优解；
(3)利用公式CBB－1求原问题的最优解；
(4)利用互补松弛条件求原问题的最优解．
【解】(1)原问题的对偶问题为

容易看出原问题和对偶问题都有可行解，如X＝(2，1)、Y＝(1，0，1)，由定理2.4知都有最优解。
(2)对偶问题最优单纯形表为
C(j)
4
2
7
0
0
R. H. S.
Basis
C(i)
y1
y2
y3
y4
y5
y3
7
0
-1/5
1
4/5
-1/5
28/5
y1
4
1
7/5
0
-3/5
2/5
4/5
C(j)-Z(j)
0
-11/5
0
-16/5
-1/5
w=42.4
对偶问题的最优解Y＝(4/5,0,28/5)，由定理2.6，原问题的最优解为X=(16/5，1/5)，Z＝42.4
（3）CB=(7,4),,
(4)由y1、y3不等于零知原问题第一、三个约束是紧的，解等式

得到原问题的最优解为X=(16/5，1/5)。

2.4证明下列线性规划问题无最优解

证明：首先看到该问题存在可行解，例如x=(2,1,1)，而上述问题的对偶问题为

由约束条件①②知y1≤0，由约束条件③当y2≥0知y1≥1，对偶问题无可行解，因此原问题也无最优解(无界解)。

2.5已知线性规划

的最优解，求对偶问题的最优解．
【解】其对偶问题是：

由原问题的最优解知，原问题约束③的松弛变量不等于零()，x1、x3不等于零，则对偶问题的约束①、约束③为等式，又由于知y3＝0；解方程

得到对偶问题的最优解Y=(5/2,5/2,0)；w＝55/2＝27.5
2.6用对偶单纯形法求解下列线性规划

【解】将模型化为

对偶单纯形表：
cj
3
4
6
0
0

CB
XB
X1
X2
X3
X4
X5
b
0
0
X4
X5
－1
[－2]
－2
－2
－3
－1
1
0
0
1
－10
－12
C(j)-Z(j)
3
4
6
0
0
0
0
3
X4
X1
0
1
[－1]
1
－5/2
1/2
1
0
－1/2
－1/2
－4
6
C(j)-Z(j)
0
1
9/2
0
3/2
－18
5
3
X2
X1
0
1
1
0
5/2
－2
－1
1
1/2
－1
4
2
C(j)-Z(j)
0
0
2
1
1
－22
b列全为非负，最优解为x＝(2，4，0)；Z＝22

【解】将模型化为

5
4
0
0
b
XB
CB
X1
X2
X3
X4
X3
0
[-1]
-1
1
0
-6
X4
0
2
1
0
1
2
Cj－Zj
3
4
0
0

X1
3
1
1
-1
0
6
X4
0
0
[-1]
2
1
-10
Cj－Zj
0
1
3
0

X1
3
1
0
1
1
-4
X2
4
0
1
-2
-1
10
Cj－Zj
0
0
5
1

出基行系数全部非负，最小比值失效，原问题无可行解。

【解】将模型化为

cj
2
4
0