运筹学大作业

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

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

目的：借助运筹学软件的强大功能，通过小组的充分讨论，对管理实践中的实际问题进行建模、求解，并对求解结果进行分析（特别是敏感性分析），进而激发学生的学习兴趣和热情，克服对课程学习的“恐惧感”。

要求：熟练掌握lingo、winqsb等软件的基本功能和基本语法结构，能用软件对运筹学问题进行求解和分析。

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

三、作业务请写清学号、姓名、专业、班级，上机作业格式请用老师提供的模版。

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

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

六、各题目中的a，b，c，d，e，f为参数，除特别规定外，请自行设定，各个同学参数值不能相同，若发现完全一致的，作业以零分计。

a=1，b=2，c=2，d=4，e=4，f=1

第1题(线性规划)

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

(2)建立下列问题的数学模型并求解，讨论资源的影子**；

某造纸厂拟生产漂白松木浆、包装纸(水泥、松木包装纸、松木本色纸)、漂白桦木纸和胶版纸等四种产品，单位产品所需资源情况见表1，市场上胶版纸的需求量不超过6000吨。(a)制订该造纸厂的生产计划；(b)若电的资源可用量下降10%，重新制订该造纸厂的生产计划。

表1 单位产品用量。

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

hint: 若参数为5，5，5，5，5，5，则最优目标函数值为(a)167236800；(b)167236800。

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

先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

两阶段单纯形法也是一种人工变量法，它的算法可分为两个阶段：第一阶段，引入人工变量，构造一个具有标准基的新线性规划，求解这个新线性规划，其结果有两种可能：或者将原问题的约束方程组化成具有标准基的形式，或者提供信息，表明原问题没有可行解。

第二阶段，利用第一阶段所得的标准基，对原问题求解。

2)a、设分别生产漂白松木浆x1吨，包装纸x2吨，漂白桦木纸x3吨，胶版纸x4吨，则lp的数学模型为： max s=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;

x1+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

软件计算得知，当x1=5770.914，x2=26152.433，x3=13837.067，x4=0时，获得最大利润167669569.52。

3）**性规划的实际应用中，要明确lp问题的类型，然后套用数学模型。由于某种原因，有时线性规划的目标函数的系数和约束条件的常数不是固定的，不同情况出现的概率不同，这些参数与概率联系在一起，这是我们所关心的不同经济状况下的最优方案。

第2题(线性规划)

(1)介绍单纯型算法及其处理人工变量的大m法；

(2)某厂在今后六个月内需租用仓库堆存物资，各月所需仓库面积及租用单价见下表，租借合同每月初可办理，问如何签约使租借费用最小？(a)试把这个问题表示成一个lp模型；(b)求该问题的解。

表2a 各月所需仓库面积。

表2b 租用单价。

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

hint: 若参数为5，5，5，5，5，5，则最优目标函数值为222250。

解：设xij表示为第i 个月签订了为期为就个月的租用合同，i=1，2，3，4，5，6；j=1，2，3，4，5，6

1）建模：大m法就是在目标函数中加上一个惩罚因素m作为人工变量的系数，其值可以无穷大，迭代的目标就是要去掉目标函数中的大m，否则由于-m充分地小，目标函数就无法达到最优。

2）设租用情况如下表。

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

3）在企业的各项管理活动中，例如计划、生产、运输、技术等问题，如何做到最少的人力物力资源去完成一个任务，线性规划是指从各种限制条件的组合中，选择出最为合理的计算方法，建立线性规划模型从而求得最佳结果，有时要引入人工变量，用大m法或两阶段法进行求解。

第3题(对偶线性规划)

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

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

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

服务员由正式员工和临时工组成，每个正式员工每天连续工作6小时，每个临时工每天连续工作9小时，且在时段开始时上班，工作时正式员工数不得少于1/4。问题的目标是要求满足以上要求的最少上班人数。(a)试把这个问题表示成一个lp模型；(b)写出对偶lp；(c)求解该问题并尽可能求出所有的解。

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

hint: 若参数为5，5，5，5，5，5，则最优目标函数值为92。

解：1）对偶理论主要研究经济学中的相互确定关系，涉及到经济学的诸多方面。产出与成本的对偶、效用与支出的对偶，是经济学中典型的对偶关系。

经济系统中还有许多其他这样的对偶关系。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。

设原始问题为min，则其对偶问题（dual problem）为 max。当原始问题的一个基解满足最优性条件时，其检验数cbb-1a-c≤0。即知y=cbb-1（称为单纯形算子）为对偶问题的可行解。

所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。

2）设各时段工作的正式员工数为xi(i=1,2,3,…8)，临时员工数为xi（i=9,10,11…16)

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

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

x1=7,x2=7,x3=3,x4=8,x5=5,x6=7,x7=4,x8=0,x9=0,x10=15,x11=3,x12=4,x13=18,x14=0,x15=4,x16=4时，上班总人数最少，为89

对偶lp问题：

y1+y2+y9+y10<=1

y2+y3+y10+y11<=1

y3+y4+y11+y12<=1

y4+y5+y12+y13<=1

y5+y6+y13+y14<=1

y6+y7+y14+y15<=1

y7+y8+y15+y16<=1

y1+y8+y9+y16<=1

y9+y10+y11<=1

y10+y11+y12<=1

y11+y12+y13<=1

y12+y13+y14<=1

y13+y14+y15<=1

运筹学大作业

运筹学大作业

运筹学大作业

运筹学大作业

其他用户还读了