运筹学大作业

运筹学课程上机实践要求及内容（2）

一、实验教学的目的和要求

目的：借助运筹学软件的强大功能，通过小组的充分讨论，对管理实

践中的实际问题进行建模、求解，并对求解结果进行分析（特别是敏

感性分析），进而激发学生的学习兴趣和热情，克服对课程学习的“恐

惧感”。

要求：熟练掌握LINGO、WinQSB等软件的基本功能和基本语法结构，

能用软件对运筹学问题进行求解和分析。

二、请于第1次-第6次上机时间及平时完成。

三、作业务请写清学号、姓名、专业、班级，上机作业格式请用老

师提供的模版。

四、编写的代码请用记事本单独保存。

五、要求所有题目用LINGO和教材自带的求解软件各做一遍。并分

析解释求解的结果。

六、各题目中的A,B,C,D,E,F为参数，除特别规定外，请自

行设定，各个同学参数值不能相同，若发现完全一致的，作业

以零分计。

A=l,B=2,C=2,D=4,E=4,F=1

第1题（线性规划）

（1）介绍单纯型算法及其处理人工变量的两阶段法；

（2）建立下列问题的数学模型并求解，讨论资源的影子价格；

某造纸厂拟生产漂白松木浆、包装纸（水泥、松木包装纸、松木本色纸）、漂

白桦木纸和胶版纸等四种产品，单位产品所需资源情况见表1,市场上胶版纸的

需求量不超过6000吨。（a）制订该造纸厂的生产计划；（b）若电的资源可用量下

降10%,重新制订该造纸厂的生产计划。

表1单位产品用量

产品漂白漂白资源

包装纸胶版纸

所需资源松木浆桦木纸可用量

松木4.2502.4155000®

桦木1153.5102000®

水19044043044018000000®

45000000千

电9208808801340

瓦

汽7889375000吨

单位产品

3500384034003960

利润（元/吨）

⑶结合本题，谈谈你对线性规划的认识。

Hint:若参数为5,5,5,5,5,5,则最优目标函数值为（a）167236800；

（6）167236800。

解：

（1）单纯形法是求解线性规划问题的通用方法。单纯形法的基本思想是：先找出

一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转

换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因

基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最

优解也可用此法判别。

两阶段单纯形法也是一种人工变量法，它的算法可分为两个阶段：第一阶段，引

入人工变量，构造一个具有标准基的新线性规划，求解这个新线性规划，其结果

有两种可能：或者将原问题的约束方程组化成具有标准基的形式，或者提供信息，

表明原问题没有可行解。第二阶段，利用第一阶段所得的标准基，对原问题求解。

(2)A、设分别生产漂白松木浆X1吨，包装纸X2吨，漂白桦木纸X3吨，胶版纸

X4吨，则LP的数学模型为：maxS=3500X1+2820X2+3400X3+3990X4

约束条件为：4.2X1+5X2+2,4X4<=155000

X1+X2+5X3+3.5X4<=102000

190X1+440X2+430X3+440X4<=18000000

920X1+880X2+880X3+1340X4<=45000000

7X1+8X2+8X3+9X4<=375000

软件计算得知，当X1=34224.319,X2=2251.572,X3=13104,822,X4=0时，

取得最大利润172987547.78

B、若电的可用量降低10%,则为45000000*0.9=40500000.

利润最大为maxZ=3500*x1+3840*x2+3400*x3+3960*x4;

'4.2*x1+5*x2+2.2*x4<=155000;

Ix1+x2+5*x3+3.5*x4<=103000;

190*x1+440*x2+390*x3+440*x4<=18000000;

920*x1+880*x2+880*x3+1340*x4<=40500000;

7*x1+8*x2+8*x3+9*x4<=375000;

x4<=6000;

x1,x2,x3,x4>=0

,线性规划

打开退出

输入

重新输入

变量个数约束条件个数目标函数

目标函数flXl果给出

价值系数C

约束条件目标函数量优值为：167669569.52

变量最忧解相差值

xl5770.914

x226152.433

x313837.067

x41123.68

约束松弛/剩余变量对偶价格

71.67

1891.320

1.633

3.14

14687.609

变量

正I负I无目标函数系数范围：

一变量=下限当前值上限

xl1840.47435003924.145

x23412.52638406030.647

x32209714

甯数项数范围无下限39605083.68

约束下限当前值上限

il152730.575155000221553.03

软件计算得知，

A、**********************最优解文口下*************************

寓函数最优值为:172987547.78

又里最优解相差值

o

xl34224.319o

x22251.572O

x313104.822

x40

约束松弛族1」余变量

0479.245

0489.057

4871614.2560

01.085

12578.6160

且标函数系数范围

工里卞限当前值上限

xl3359.38735003924.145

x23348.38738404037.143

x32720.0434008575

x4无下限3960

常遨项数范围：4315.66

约束下限当前值上限

152690.323155000165000

99675.325102000110000

13128385.74418000000无上限

41154306.9924500000045409142.857

362421.384375000无上限

B、**********************最优解文口下*************************

目标函数最优值为:167669569.52

又里最优解相差值

X15770.9140

x226152.4330

x313837.0670

x401123.68

约束松弛俅I余变量对偶价格

1071.67

21891.32

301.633

403.14

514687.609

60

目标函数系数范围

亦叁卞限

又里当前值上限

X11840.47435003924.145

x23412.52638406030.647

x32209714

x4无下限39605083.68

常数项数范围:

下限当前值上限

1152730.575155000221553.03

2101108.68103000无上限

39913690.4761800000018566404.612

437117948.7184050000040950104.123

5360312.391375000无上限

600无上限

当X1=5770.914,X2=26152.433,X3=13837.067,X4=0时，获得最大利润

167669569.52o

（3）在线性规划的实际应用中，要明确LP问题的类型，然后套用数学模型。

由于某种原因，有时线性规划的目标函数的系数和约束条件的常数不是固定的，

不同情况出现的概率不同，这些参数与概率联系在一起，这是我们所关心的不同

经济状况下的最优方案。

第2题（线性规划）

（1）介绍单纯型算法及其处理人工变量的大M法；

（2）某厂在今后六个月内需租用仓库堆存物资，各月所需仓库面积及租用单

价见下表，租借合同每月初可办理，问如何签约使租借费用最小？（a）试把这个

问题表示成一个LP模型；（b）求该问题的解。

表2A各月所需仓库面积____________________________________________

月份123456

更用面积（平方21。120520440340610

表2B租用单价_________________________________________________________

合同租用期限123456―

租用单价(元/平方

米)100195285370450525

⑶结合本题，谈谈你对线性规划的认识。

Hint:若参数为5,5,5,5,5,5,则最优目标函数值为222250。

解：设刈表示为第I个月签订了为期为就个月的租用合同，i=1,2,3,4,5,

6;j=1,2,3,4,5,6

(1)建模：大M法就是在目标函数中加上一个惩罚因素M作为人工变量的系

数，其值可以无穷大，迭代的目标就是要去掉目标函数中的大M,否则由于-M

充分地小，目标函数就无法达到最优。

(2)设租用情况如下表

123456

合同租用期限

1X11X21X31X41X51X61

2X12X22X32X42X52

3X13X23X33X43

4X14X24X34

5X15X25

6X16

minS=100(X11+X21+X31+X41+X51+X61)+195(X12+X22+X32+X42+X52)

+285(X13+X23+X33+X43)+370(X14+X24+X34)+450(X15+X25)+525X16

S.T.X11+X21+X31+X41+X51+X61>=210

X12+X22+X32+X42+X5>=120

X13+X23+X33+X43>=520

X14+X24+X34>=440

X15+X25>=340

X16>=610

**********************^p*d^]^角聿交口―1*^**************************

旦标函数取优值为：451300

变量最优解相差值

114o0

200

300

400

500

600

728O0

000

000

9

1000

1100

12190

1300

1400

1500

16290

1700

1800

192O0

2000

2250

^

也

2^集

T?T^—TT里-S-

1O

2O-100

3O-195

4O-285

5O-370

6O-450

-525

具整函数系数范围：

p艮

当前值上限

1OO100Hk

A±9

x6A195f

vx5

x7d95195t

x8AxFkp

I95195T艮

XXkj

无

x901951957艮

二J

9无

115195二07

202855艮

28无

3285285艮

-

无

4285285T艮

-r-J

2528无

585--Jt

-l

60370o艮

上

37无

737o370T艮

l-J

337上

87o0无

90450or

0445k

5O045无:R

二mM

525—

无

二MRL-

x21—\

曜项数范围:

当

前值

上

艮

艮

下a

Rp

Dt

—

上

i灵

1O14Oos

上

2O28O灵

上

3O19O灵

上

4O29O灵

灵

5O20O上

灵

OO上t

625>rs

(3)在企业的各项管理活动中，例如计划、生产、运输、技术等问题，如何做到

最少的人力物力资源去完成一个任务，线性规划是指从各种限制条件的组合中,

选择出最为合理的计算方法，建立线性规划模型从而求得最佳结果，有时要引入

人H变量，用大M法或两阶段法进行求解。

第3题(对偶线性规划)

(1)介绍对偶理论及对偶单纯型算法；

(2)一家宾馆，每天需要的服务员人数如表3所示：

表3不同时段需要的服务员人数_____________________

起迄时间服务员的最少人数一

0-315

3-633

6-928

9-1233

12-1538

15-1834

18-2133

21-2412

服务员由正式员工和临时工组成，每个正式员工每天连续工作6小时，每个

临时工每天连续工作9小时，且在时段开始时上班，工作时正式员工数不得少于

1/4。问题的目标是要求满足以上要求的最少上班人数。(a)试把这个问题表示成

一个LP模型；(b)写出对偶LP；(c)求解该问题并尽可能求出所有的解。

(3)结合本题，谈谈你对对偶线性规划的认识。

Hint:若参数为5,5,5,5,5,5,则最优目标函数值为92。

解：

(1)对偶理论主要研究经济学中的相互确定关系，涉及到经济学的诸多方面。

产出与成本的对偶、效用与支出的对偶，是经济学中典型的对偶关系。经济系统

中还有许多其他这样的对偶关系。对偶单纯形法则是从满足对偶可行性条件出发

通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行

性,而使不可行性逐步消失。设原始问题为min{cx|Ax=b,x>0},则其对偶问题

(DualProblem)为max(yb|yA<c}o当原始问题的一^基解满足最优性条件时,

其检验数CBB-1A-C40。即知y=cBB-1(称为单纯形算子)为对偶问题的可行解。

所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的

前提下，一当基解成为可行解时，便也就是最优解。

(2)设各时段工作的正式员工数为xi(i=1,2,3,…8),临时员H数为xi

(i=9,10,11...16)

要求最少上班人数，则目标函数为

minZ=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16

x1+x8>=5

x1+x2>=11

x2+x3>=10

x3+x4>=11

x4+x5>=13

x5+x6>=12

x6+x7>=11

x7+x8>=4

x1+x8+x9+x15+x16>=15

x1+x2+x9+x10+x16>=33

x2+x3+x9+x10+x11>=28

x3+x4+x10+x11+x12>=33

x4+x5+x11+x12+x13>=38

x5+x6+x12+x13+x14>=34

x6+x7+x13+x14+x15>=33

x7+x8+x14+x15+x16>=12

x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16>=0

翁

£I察i解决关于退出

输入

目标函数―112d重新输入

变量个数!约束条件个数

目标函数£|X10|xu|X12|X13|X14|X15|X16

价值系数c|1：111i!11

U*

约束条件XllX12|X13X14X15|X16b

1000000133

1110000028

1211000033

1311100038

1401110034

1500111033

1600011112-1

出口回I

**********************最忧解如下*************************

变量XI|X24

正1负1无>0>0目标函数量优值为：89

变量最忧解相差值

xl70

x270

x330

x480

x550

x670

x740

x800

xLx2,x3,x4,x5,x6,x7,x8.x900

xlO150

xll30

xl240

xl3180

xl40.5

xl540

xl640

约束松弛/剩余变量对偶价格

120

K14行10列230

30-.5

tw山如下所示:400

500V

1\**********************^^^彳^1^贪率女口"［、*************************

且标函数最优值为e：89

变量最优解相差值

1

270

370

430

580

650

770

840

900

1000

11150

1230

1340

14180

150.5

1640

-巨40

5F松弛律U余变量对偶价格

120

230

305

400

500

605

700

805

90