《运筹学》课后习题答案 第2章 对偶原理与灵敏度分析

一、选择题

1.2.3.4.5.6.7.8.9.10.

二、判断题

1.2.3.4.5.6.7.8.9.10.

三、写出下列线性规划问题的对偶问题

=2xl+2X2+4X3(a)MaxW=2yl+3%+5%

2xl4-3X2+5X3>22y+3%+为42

3玉+x+7X<3对偶问题：3y+%+4%<2

23s.t.

xl+4X2+6尤3<55必+7%+6%«4

xpx2,x3>0y>0,y2,y3<0

(2)MaxZ=2xj-4x24-3x3(b)MinW=l2y1+10y2+15%

xt-3X2+2&<12必+0・%+为22

2X4-X>10对偶问题：3必-2%+0・%24

23s.t

x1-2X3=152必+%-2%>3

%1,x3>0,x2<0y>0,y2<0,y3/ree

(3)MaxZ=2%]+x2-3X3(c)MinW=25y+3y2+10%

西+2X2-3X3<25乂+%+%N2

%)-x+x>3对偶问题：2%-%+为<1

s.t.<23s.t.

x,+x2=103必-%+。・％=3

%>0,x2<Q,x3freeXN0,%<0,yjree

(4)Mi〃Z=X]+2X2-3X3(d)MaxW=3y+10%+8%

X1+3冗323y+()•%+2%21

2X+2X<10对偶问题：+2%+为=2

23s.t.

2xx+x2=83乂+2y2+0.%4-3

Xj<0,x2free.x3>0y>O,y2<^,yifree

四、应用对偶单纯形法求解下列线性规划问题

()

yMinZ=x]+x2McucZ=-Xj-x2

2xj+x>4

2标准型:—2x-Z+%3=—4

s.tAx}+7X2>5-Xj-7X2+七二一5

x,,x2>0Xj,x2>0

对偶单纯形法一用电子表格求解

价值系数-1.000“•0000.0000.000

基变量价值系数基变量

解答列XIX2X3X4

0X3-4.000-2.000-1.0001.0000.000

0X4-5.000-1.000-7.0000.0001.000

目标函数相反数0.000-1.00()-1.0000.0000.000

比值：10.142857

0X3-3.286-1.8570.0001.000-0.143

-1X20.7140.1431.0000.000-0.143

目标函数相反数0.714-0.8570.0000.000-0.143

比值：0.4614971

-1X11.7691.0000.000-0.5390.077

-1X20.4610.0001.0000.077-0.154

目标函数相反数2.2310.0000.000-0.461-0.077

对偶单纯形法求解

Cj-1-100

CBXB

bXjXIX2X3X4

0X3-4-2-110

0X4-5-1-701

0-1-100

比值：-1/-1-1/-7

0X3-23/7-13/701-1/7

-1X25/71/710-1/7

-775/7-6/700-1/7

比值：6/131

-1X123/1310-7/131/13

-1X26/13011/13-2/13

-7:29/1300-6/13-1/13

X*=(23/13,6/13,0,0)T,Z,max=-29/13f原问题X*=(23/13,6/13,0,0)T,

Zmin=29/13.

(2)A/mZ=4玉+2X2+X3MaxZ'=-4x,-2X2-

2x,+4X2+5X3>10—2xj—4x?—5玉+%=—10

3Xj-x+6x>3标准型：-3X1+-6X3+=-3

s.t.<23s.t.<

5x,+2X2+>12-5X|-2超一工3+尤6=-12

x,,x2,x3>0%］，x2，，X5，Xg>0

Cj-4-21000

CBXB

bXjXIX2X3X4X5X6

0X4-10-2-4-5100

0X5-3-31-6010

0X6-12-5-2-1001

-Z'0-4-2-1

比勺I：-4/-5-2/-2-1/-1

0X4-26/50-14/5-23/510-2/5

0X521/5011/5-27/501-3/5

-4XI12/512/51/500-1/5

-Z'48/5-2/5-1/500-4/5

比。1：1/81/232

0X326/23016/231-5/2302/23

0X5237/230137/230-27/231-3/23

-4XI50/2316/2301/230-5/23

-Z'226/230-2/5-1/500-4/5

X*=(50/23,0,26/23,0,237/23)[Z'max=-226/23X原问题X*=(50/23,0,26/23,0,

237/23)T,Zmin=226/23.

MeixZ二="2Xj-2%2—4M

2毛+3X2+5X3>2

3.3X1+x2+7%<3

s.t.

卜4X2+6W<5

>0,7=1,2,3

解：

-

MaxZ=一2芭一2X2-4尤3MaxZ二2Xj-2%2-4尤3

2%+3X2+5%3>22%+3X2+5X3-x4=2

3%+x2+7x3<3标准型：3玉+%+7七+/=3

s.t.<

%1+4元2+6X3<5%+4X2+6七+x6=5

x.>0,y=l,2,3与之0,/=1,2,3,4,5,6

Cj-2-2-4000

CbXb

bXjXIX2X3X4X5X6

0X4-2-2-3-5100

0X53317010

0X65146001

-Z'0-2-2-4

比偃1：12/34/5

-2X22/32/315/3-1/300

0X57/34/3016/31/310

0X67/3-5/30-2/38/301

Z|4/3I-2/3I0I-2/3|-2/3|00|

*277Tr4

X=(0,-,0,0,-,-)Zmax=--

五、应用对偶理论证明如下线性规划问题有可行解，但无最优解

六、灵敏度分析题

'5_P

99

1,解:依题意知，X*=(-,—,0,0/,Zmax=—,B'=,:.B

99max3」2

<-99>

C=(1,2,0,0),b=(3,7)7,0=-；；/=-；

(1)若目标函数Z=X1+2z变为Z=3X1+5z，则

'5

-9fl

9107

6N=CN-CBB"N=(0,0)—(3,5)210、

_J_1尸『5)

J99>

因此，最优解不变，但最优值变为Zmmaax=?9。

单纯形法一目标函数价值系数变化

价值系数3.0005.0000.0000.000

基变量价值系数基变量0

解答列XIX2X3X4

0X33.0002.0001.0001.0000.0003.000

0X47.0001.0005.0000.0001.0001.400

目标函数相反数0.0003.0005.0000.00()0.000

0X31.6001.8000.0001.000-0.2000.889

5X21.4000.2001.0000.0000.2007.000

目标函数相反数-7.0002.0000.0000.000-1.000

3XI0.8891.0000.0000.556-0.111

5X21.2220.0001.000-0.1110.222

目标函数相反数-8.7780.0000.000-1.111-0.778

'50(29、

(2)当b=(3,7)，变为bj&ll)7'时，b=B“b=；

214

9JI9>

57W

因此，最优解结构不变，数值变为X*=("，上,0,0)77

99max丁一H

单纯形法一右端常数变为bl=8,b2=ll

价值系数1.00()2.0000.0000.000

基变量价值系数基变量0

解答列XIX2X3X4

0X38.0002.0001.0001.0000.0008.000

0X411.0001.0005.0000.0001.0002.200

目标函数相反数0.0001.00()2.0000.0000.000

1X35.8001.8000.0001.000-0.2003.222

2X22.2000.2001.0000.0000.20011.000

目标函数相反数-4.4000.6000.0000.000-0.400

XI3.2221.00()0.0000.556-0.111

X21.5560.0001.000-0.1110.222

目标函数相反数-6.3330.0000.000-0.333-0.333

（3）新产品C3=l,6=（1,B）7"，则在系数矩阵中要增加一列，对应决策变量当

5」

199kn1

•••%=。3-。理飞=1一(1,2)[2Lj=~3-°

9)

所以最优解和最优值不变，该产品不宜生产。

单纯形法一增加新产品C（单价I,al3=l,a23=3）

价值系数1.0002.0001.0000.0000.000

基变量价值系数基变量e

解答列XIX2X3X4X5

0X33.0002.0001.0001.0001.0000.0003.000

0X47.0001.0005.0003.0000.0001.0001.400

目标函数相反数0.0001.0002.0001.0000.0000.000

1X31.6001.8000.0000.4001.000-0.2000.889

2X21.4000.2001.0000.6000.0000.2007.000

目标函数相反数-2.8000.6000.000-0.2000.000-0.400

XI0.8891.0000.0000.2220.556-0.111

X21.2220.0001.0000.556-0.1110.222

目标函数相反数-3.3330.0000.000-0.333-0.333-0.333

（4）若产品1的消耗系数由々=（2,1/'变为耳=（1,2尸则

、

’51、

,g9

=0

22)

J9

97

'5

9-9"1O'

•.PN=CLCBB」N=(0,0)—(1,2)

2

「597

故最优解改变，但最优值没变，产品结构无变化。

单纯形法一产品1消耗系数变化

价值系数1.0002.0000.0000.000

基变量价值系数基变量e

解答列XIX2X4X5

0X33.0001.0001.0001.0000.0003.000

0X47.0002.0005.0000.000L0001.400

目标函数相反数0.0001.0002.0000.00()0.000

1X31.6000.6000.0001.000-0.2002.667

2X21.4000.4001.0000.0000.2003.500

目标函数相反数-2.8000.2000.0000.000-0.400

XI2.6671.0000.0001.667-0.333

X20.3330.0001.000-0.6670.333

目标函数相反数-3.3330.0000.000-0.333-0.333

2.解：设甲、乙两种产品的产量分别为占和4件。

原料A消耗花费的钱：（2%+4Z）x1（元）。

原料B消耗花费的钱：（3%+24）x2（元）

产品销售收益：13%+16々

扣除成本后的利润：Z=13%+16%-（2玉+4%）-2x（3玉+2x2）

MaxZ=5%+8X2

2x+4%W160

（1）利润最大化模型为：}

3%1+2々<180

,x2>0

单纯形法一用电子表格求解

价值系数5.0008.0000.0000.0000

基变量价值系数基变量

解答列XIX2X3X4

0X3160.0002.0004.0001.0000.00040

0X4180.0003.0002.0000.0001.00090

目标函数相反数0.0005.0008.0000.0000.000

8X240.0000.5001.0000.2500.00080

0X4100.0002.0000.000-0.5001.00050

目标函数相反数-320.0001.0000.000-2.0000.000

8X215.0000.0001.0000.375-0.250

5XI50.0001.0000.000-0.2500.500

目标函数相反数-370.0000.0000.000-1.750-0.500

解得：最优解X*=(50,15,0,0)、最优值21„”=370(元)。

(2)从最优表中可知，原料A的影子价格为y：=-q=L75(7/4),原料B的影

子价格为y；=-2=0.5(1/2),显然原料A更珍贵。

(3)若市场上有A原料出售，企业应该购入以扩大生产。假设在保持最优解不

变的前提下，最多购入Q(kg)。(请注意这里的逆矩阵先写第二行再第一行)

50--2^0

4.2<200