1. 用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是 无可行解。

max Z = Xi + X2 6xi +10x2 "20

* 5兰x1兰10

【3乞X2乞8

惟一最优解

最优点(10, 6)最优值Z二16

戸 5 si = 10 /

2. 将下述线性规划问题化成标准形式。

min Z = -3x^ 4X2 - 2x^ 5x4

Mx1 - x2 + 2x3 - X4 = -2

为中 X2 — X3 + 2x4 兰 14

（1）

j - 2x1 + 3x2 + X3 - X4 A 2

1x1, x2, x3 H 0,x4无约束

解：令 z' = —Z，X4 =X4 — x；

max z^ 3X] - 4x^ 2X3 - 5x4 5x4

[—4X] + X2 - 2X3 + x4 - x； = 2

j X] + X2 - X3 + 2x4 - 2x4 十 X5 = 14 |- 2x1 + 3x2 + X3 - X4

+ x4 - Xe = 2 _X1，X2，X3，X4，X4，X5，X6 k 0

3. 分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应、

、

1 、 1 ^2=®

0X|+1OZ2-12O

护 ____________

寸 v/ max Li 10 图解法中的可行域的哪个顶点。

max =10x

+ 4x2 <9 {5捲

+2x2 <8

[Xi,X2 >0

解：①图解法：

②单纯形法：

max Z =10xi +5x2

：3捲 +4x2 +x3 =9

{5xi +2x2 +x4 =8

I

[Xi,X2,X3,X4 >0

Cj 10 5 0 0

0 对应图解法 中的点 CB B b X1 X2 X3 X4

0 X3 9 3 4 1 0 3

0 X4 8 [5] 2 0 1 8/5 0点

Oj 0 10 5 0 0

0 X3 21/5 0 [14/5] 1 -3/5 3/2

10 X1 8/5 1 2/5 0 1/5 4 C点

宵 -16 0 1 0 -2

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

10 X1 1 1 0 -1/7 2/7

B点

35/2 0 0 -5/14 -25/14

最优解为(1,3/2,0,0),最优值Z=35/2。 单纯型法步骤：转化为标准线性规划问题；找到一个初始可行解，列出 初始单纯型表；最优性检验，求 cj-zj，若所有的值都小于0,则表中 的解便是最优解，否则，找出最大的值的那一列，求出 bi/aij ，选取

最小的相对应的 刈，作为换入基进行初等行变换，重复此步骤。

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

m n

min z = S 送 cij xij

■ n

无 Xij = ai

j 二

m

z

i 二 (i = 1,…，m )

(1)

s.tXij =bj (j =1,…，n) Xij (i =1,…,m; j = 1,…，n )

n

maxw = 2 aiy^Z byj如

i 二

(i T, ,m； j T,…，n) i 二

fyi 中 ym+j 乞 Cij s.t. { n* jXi,yj无约束

n

maxz cjxj

j吕

L n

S aij xj j吕

n

S.t.jW aij xj

j4

Xj >0

[Xj无约束

m

min w = Z bi yi

i T

L m

送 aij yi

i吕

m (i =1,…mi < m )

=bi

(j (i = m-^ +1,m1 +2"' , m)

=1,…rn

(j =n1

(j 72,…n^ n)

s.t.書 aij

yi :

i占

y^o (j = n- +1,…,n )

(i = 1,2，…m^

m ) 5. 给出线性规划问题

max z = 2为 + 4x2 +

x3

要求：（1）写出其对偶问题；（2）已知原问题最优解为 X* =（2,2,4,OT，试根据对偶理论，直 接求出对偶问题的最优解。

解：

min w =8yi +6y2 +6y3 +9y4

例已知原问题

Max z =x 1 + 2 x2 +

Xi + 2 X2 + 2 X3 + 2x

1 + x2 + 3 x3 +

Xi、 x 2、 x 3、

和对偶问题

Min w =20y 1 + 20 y2

yi + 2y2绍

2y 1 + y2>2

2y 1 + 3 目 2 >3

3y 1 + 2 y2 >4

yi、 y2> 0

已知对偶问题的最优解 yr = 1.2、y2 =0.2，最优值 min w=28 + X4

Xi

2xi + 3x2 + x4

+ x2 <8

st.{ X2 +X3 +X4 + X2 +X3

xj >0(j =1,…4 ) Xi <9

(1) y1 +2y2

3y1十 s.t「 5兰2 y2 + y3 +

y4 > 4

y3 + y4 31

5 31 y1

yj 网=1,…4）

、2）因为X1,X2,X3>0，第四个约束取等号，根据互补松弛定理得:

丫1 +2y2 +丫4 =2

3% + 丫2 中丫3 +丫4 =4

=1 y3 +y4

+ y4

求得对偶问题的最优解为: =0

* 「4 3 \

Y = — ,-,1,0 I，最优值 min w=16。

V5 5丿

3 X3 + 4 X4

3 x4 w 20

2X4'w20

x4 > 0

可用如下方法求解：

引入将原问题和对偶问题化为标准形式。 Max z =xi + 2x2 + 3x3 + 4x4

xi + 2 X2 + 2x3 + 3x4 + X5 =

20

2xi + X2 + 3X3 + 2X4 Xi、X2、X3、X4、X5、 + X6 =20

X6 > 0

Min w =20y 1 + 20

y2

y1+药2 ― y3

2y1 + y2

2y1 + 3y2

3y1 +^2 -y4

-壮 =1

=2

=3

—¥6 = 4 y1、72、y3、y4、yg、y》0

y1=1.2>0，而¥1与Xg中至少有一个为零，故x5 =00

同理，¥2=0.2>0,所以 x6=0 0

对偶问题的第一个约束条件在取最优值时

y1+2y2=1.2+2X 0.2=1.6>1

这就表示该约束条件的松弛变量：

¥3=1.6— 1=0.6>0

¥3与冷中至少有一个为零，故x1=0o

(4)同理，对于第2个约束条件在取得最优值时

2y1+y2= 2X 1.2+0.2=2.6>2

¥4=2.6— 2=0.6>0

y4与X2中至少有一个为零，故x2=0o (1) (5) 同理，对于第3个约束条件在取得最优值时

2yi+3y2= 2X 1.2+ 3 X 0.2=3

y5=3 — 3=0

y5与X3中至少有一个为零，故X3>0或者X3=0。

(6) 对于第4个约束条件的分析也可得到 X4>0或者X4=0。 对于(5)和(6)的分析，对于确定原问题的最优解没有

任何帮助。但从(1)至U( 4)的分析中得知，原问题取得 最优解时：

X5= 0，X6= 0，Xi= 0，X2= 0

代入原问题的约束方程组得：

2X3+3X4= 2 0 3X3+2X4= 2 0

解此方程组，可求得原问题的最优解为：

Xi=0，X2= 0 ，X3= 4 ，X4 = 4 ，X5= 0，X6= 0

弱对偶性的推论：

(1) 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界； 反之对偶问

题任一可行解的目标函数值是其原问题目标函数值的上界

(2) 如原问题有可行解且目标函数值无界(具有无界解)，则其对偶问题无可行解； 反之对偶问题有可行解且目标函数值无界，则其原问题无可行解。

注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无 可行解，反之亦然。

(3) 若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对 偶问题有可行解而其原问题无可行解，贝w偶问题的目标函数值无界。

强对偶性(或称对偶定理)

若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的 目标函数值相等。

互补松弛性

在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则 该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一 定为零。

影子价格

资源的市场价格是其价值的客观体现，相对比较稳定，而它的影子价格则有赖于资 源的利用情况，是未知数。因企业生产任务、产品结构等情况发生变化，资源的影 子价格也随之改变。

影子价格是一种边际价格。

资源的影子价格实际上又是一种机会成本。随着资源的买进卖出，其影子价格也将 随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。

生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源