运筹学练习试题部分参考答案1

运筹学试题 答案

线性规划问题

1、某工厂生产I、II、III三种产品，分别经过A、B、C三种设备加工。已知生

（2）产品III每件的利润增加到多大时才值得安排生产；

（3）如有一种新产品，加工一件需设备A、B、C的台时各为1，4，3小

时，预期每件的利润为8元，是否值得安排生产。

解：（1）设x1，x2，x3分别为I、II、III三种产品的产量，z表示利润。该问题的线性规划模型为：

maxz=10x1+6x2+4x3

x1+x2+x3≤100 10x+4x+5x≤600 23s..t 1

2x1+2x2+6x3≤300 x1,x2,x3≥0

用单纯形法求上述线性规划问题。化为标准形式：

maxz=10x1+6x2+4x3+0x4+0x5+0x6 x1 +x2 +x3+x4 =100 10x+4x+5x +x =600 1235s..t

2x1+2x2+6x3 +x6=300 xj≥0,j=1,2, ,6

cj→cB

xB

b

1064000

x1x2x3x4x5x6

θ

x4

100111100100

00

x5x6

600300

[10]2

42

56

00

10

01

60150

运筹学试题 答案

σj0

0100

6[0.6]

40.5

01

0-0.1

00

200/3

x4

40

100

x1x

6

60180

10

0.41.2

0.55

00

0.1-0.2

01

150150

σj6100

-6000010

2100

-15/61/64

05/3-2/3-2

-1-1/61/60

0001

x2x1x6

200/3100/3100

σj

-2200/300-8/3-10/3-2/30

所以最优解为x*=(100/3，200/3，0，0，0，100)T，即产品I、II、III的产量分别为：100/3，200/3，0；最优解目标函数值z*=2200/3

（2）设产品III每件的利润为c3

σ3=c3 CBB 1P3=c3 CBP3′

5/6

=c 20/3≥0 c≥20/3=c3 (6,10,0) 1/63 3

4

产品III每件的利润增加到20/3时才值得安排生产。

（3）设x7 1

102

σ7=c7 cBB 1P7=8 (,,0) 4=2>0 值得投产 33

3

运筹学试题 答案

5/3 1/60 1 1

4 = 0 P7′=B 1P7= 2/31/60 01 2 3 1

cj→cB

xB

b

10640008

x1x2x3x4x5x6x7

θ

6100

x2x1x6

200/3100/3100

010

100

5/61/64

5/3-2/3-2

-1/61/60

001

[1]01

200/3-100

σj

-2200/300-8/3-10/3-2/302

cj→cB

xB

b

10640008

x1x2x3x4x5x6x7

θ

8100

x7x1x6

200/3100/3100/3

010

10-1

5/61/619/6

5/3-2/3-11/3

-1/61/61/6

001

100

σj

-2600/30-2-13/3-20/3-1/300

所以最优解为x*=(100/3，0，0，0，0，200/3)T，即产品I的产量：100/3，新产品的产量：200/3；最优解目标函数值z*=2600/32、已知下列线性规划问题：

运筹学试题 答案

maxz=6x1 3x2+3x3 3x1+x2+x3≤60 2x 2x+4x≤20 23s..t 1

3x1+3x2 3x3≤60 x,x,x≥0

123求：（1）用单纯形法求解，并指出问题属于哪一类解；（2）写出该问题的对偶问题，并求出对偶问题的最优解；

解：（1）将原问题划为标准形得：

maxz=6x1 3x2+3x3+0x4+0x5+0x6

3x1 +x2+x3+x4 =60s..t

2x1 2x2+4x3 +x5 =20 3x1+3x2 3x3 +x6=60

xj≥0,j=1,2, ,6cj

6-33000

cB

xB

b

x1x2x3x4x5xθ

6

x4

6031110020

0x520[2]-24010100

x6

60

3

-3

3

1

20

σj06-330000

x4

30

4

-5

1

-3/2

15/2

6x1101-1201/20-0

x6

30

[6]

-9

-3/2

1

5

运筹学试题 答案

σj-6003-90-30

x4

100

1

1

-1/2-2/3

6x115101/201/41/6-3

x2

5

1

-3/2

-1/4

1/6

σj

-7500-9/20-9/4-1/2

所以最优解为x*=(15，5，0，10，0，0)T最优解目标函数值z*=75非基变量的检验数<0,为唯一最优解.（2）该问题的对偶问题为：

minw=60y1+20y2+60y3 3y1+2y2+3y 3≥6s..t y1

2y2+3y3≥ 3 y1+4y2 3y3≥3 y1,y2,y3≥0

对偶问题的最优解：y*=(0，9/4，1/2)3、已知线性规划问题：

maxz=x1+2x2 2x1+x2s..t ≤8

x 2≤4 x1,x2

≥0求：（1）用图解法求解；（2）写出其对偶问题；

（3）根据互补松弛定理，写出对偶问题的最优解。

解：（1）图解法

运筹学试题 答案

由上图可知：在B(2,4)处，目标函数达到最大值。即最优解为x*=(2,4)T

最优解目标函数值z*=10minw=8y1+4y2 2y1≥1 s..t y1+y2≥2 y≥0,y≥0

2 1

（3）原问题的最优解x*=(2,4)T代入约束条件，可知约束条件取等式，因为

为唯一最优解

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

x1*，x2*不为0，在对偶问题中相应的约束条件为紧约束，

即2y1=1,y1+y2=2

对偶问题的最优解及最优目标函数值为：y =(1/2,3/2)w =10

运输问题

1、某百货公司到甲、乙、丙三地采购A、B、C、D四种规格服装，预计销售后每套服装可得利润如下表：

ABCD供应量

105642500甲

82773000乙

93465000丙

需求量1500200030003000请帮助该公司设计一个预期利润最大的方案。

先用Vogel法或最小元素法求初始基可行解；用位势法或闭回路法求出非基变量的检验数；若还未得到最优解，则用闭回路调整法，得到改进方案，再检验最优性。

①求初始基可行解（Vogel法）

运筹学试题 答案

初始解：x11=1500,x12=1000,x23=3000,x24=0,x32=1000,x34=3000,x35=1000,其余变量为0

②最优性检验（位势法）：根据基变量的检验数为0，即σij=cij–ui–vj=0

σ11=c11–u1–v1=0–u1–v1=0σ23=c23–u2–v3=3–u2–v3=0σ32=c32–u3–v2=7–u3–v2=0σ35=c35–u3–v5=10–u3–v5=0

σ12=c12–u1–v2=5–u1–v2=0σ24=c24–u2–v4=3–u2–v4=0σ34=c34–u3–v4=4–u3–v4=0

u1=0易得：u2=1，u3=2，v1=0，v2=5，v3=2，v4=2，v5=8计算非基变量的检验数：

σ13=c13–u1–v3=4–0–2=2σ15=c15–u1–v5=10–0–8=2σ22=c22–u2–v2=8–1–5=2σ31=c31–u3–v1=1–2–0=-1<0

σ14=c14–u1–v4=6–0–2=4σ21=c21–u2–v1=2–1–0=1σ25=c25–u2–v5=10–1–8=1σ33=c33–u3–v3=6–2–2=2

运筹学试题 答案

销地产地

甲乙丙需求量

A50002100011500

72000

63000

43000

58B2000

4

6

D

10033000

10100010

1000E

C供应量250030005000

30003

基变量的检验数为0，即σij=cij–ui–vj=0

σ11=c11–u1–v1=0–u1–v1=0σ23 …… 此处隐藏：7113字，全部文档内容请下载后查看。喜欢就下载吧 ……