运筹学上机报告

福州大学至诚学院运筹学上机实验报告

姓名：

学号：

系别：经济管理

年级专业：2016级工业工程

指导老师：饶丽红

实验一线性规划问题建模和求解

?实验目的

本实验目的在于帮助我们学习如何运用Excel对复杂的实际系统进行描述与建模，并用计算机求解，训练学生的建模能力。

?实验要求

用Spreadsheet方法如何建立运筹学模型，并进一步求出最优解。

?实验内容

雅致家具厂生产计划优化问题。雅致家具厂生产4种小型家具，由于该四种家具具有不同的大小、形状、重量和风格，所以它们所需要的主要原料（木材和玻璃）、制作时间、最大销售量与利润均不相同。该厂每天可提供的木材、玻璃和工人劳动时间分别为600单位、1000单位与400小时，详细的数据资料见下表。

问题：应如何安排这四种家具的日产量，使得该厂的日利润最大？

表1—1 雅致家具厂基本数据

家具类型劳动时间

（小时/件）

木材（单位/件）

玻璃

（单位/件）

单位产品利润

（元/件）

最大销售量

（件）

1 2 4 6 60 100

2 1 2 2 20 200

3 3 1 1 40 50

4 2 2 2 30 100

可提供量 400小时 600单位 1000单位

?实验步骤

第一步：建立问题的线性规划模型

由题意可写出该问题的线性规划模型如下：

设四种家具的日常量分别为X1，X2，X3，X4。

Max Z=60*x1+20*X2+40*X3+30*X4

2*X1+X2+3*X3+2*X4<=400

4*X1+2*X2+X3+2*X4<=600

6*X1+2*X2+X3+2*X4<=1000

X1<=100

X2<=200

X3<=50

X4<=100

X1, X2, X3, X4>=0

第二步：用Speadsheet进行问题描述与建模。

如下图所示：

简要描述：

1）设单元格B13至E13分别表示决策变量X1到X4。

2）设单元格B15表示目标函数，它的值= 100X1+200X2+50X3+100X4。

3）设单元格B19至B26分别表示七个约束条件左边的值。

4) 设D19至D26分别表示七个约束条件右边的值，即可提供的资源数量。

第三步：在Excel规划求解功能中输入整数约束并求解在规划求解参数框中输入目标单元格

(目标函数地址)、可变单元格(决策变量地址)和四个约束条件，包括整数约束，其规划求解参数框。如下图所示：

然后在规划求解选项参数框中选择“采用线性模型”和“假定非负”，最后在规划求解参数对话框中单击“求解”得到本问题的最优解。如下图所示：

总结（至少100字）

通过上机学习学习如何运用Excel来进行规划求解，掌握求整数线性规划的使用方法和操作步骤，并且懂得了掌握建模思想的实用性。首先通过建立问题的线性规划模型，在进行用Speadsheet进行问题描述与建模，在规划求解功能中输入整数约束并求解在规划求解参数框中输入相关条件，最后得出结果。本实验就是利用Excel的规划求解来寻找该厂的日利润最大的最佳方案。通过上机实验，我对Excel表格的应用能力有了进一步的提高，达到计算机与运筹学同时掌握的效果。

实验二整数线性规划

?实验目的

学会利用Excel表格建模并求解0-1整数规划问题。在线性规划问题中，最优解可能是整数，也不可能是整数，但对于某些实际问题，要求答案必须是整数，因此我们通过使用“Excel”软件来解决整数规划的问题，避免用图解法求整数规划问题时慢以及避免只能解决两个变量的整数规划的缺点，更有效的解决整数规划问题。

?实验要求

能够写出求解模型、运用软件进行求解并对求解结果进行分析

?实验内容

一、人员安排问题

一家中型的百货商场对售货员的需求经过统计分析如表所示。

时间所需售货员数时间所需售货员数

星期一15 星期五31

星期二24 星期六28

星期三25 星期日28

星期四19

为了保证售货员充分休息，要求售货员每周工作五天，休息两天，并要求休息的两天是连续的，

问应该如何安排售货员的休息日期，既满足工作需要，又使配备的售货员的人数最少？

?实验步骤

第一步：建立整数规划模型

由题意可得如下整数线性规划模型：

设Xi为休息2天后星期一到星期日开始上班的营业员

MinZ=X1+X2+……X7

X1+X4+X5+X6+X7>=15

X2+X5+X6+X7+X1>=24

…

…

…

…

…

…

…

X7+X1+X2+X3+X4>=28

Xi>=0,i=1,2 (7)

第二步：用Spreadsheet进行问题描述与建模。

如下图所示：

第三步：在Excel规划求解功能中输入整数约束并求解在规划求解参数框中输入目标单元格(目标函数地址)、可变单元格(决策变量地址)和四个约束条件，包括整数约束，其规划求解参数框。如下图所示：

然后在规划求解选项参数框中选择“采用线性模型”和“假定非负”，最后在规划求解参数对话框中单击“求解”得到本问题的最优解。如下图所示：

二、垃圾处理问题---最小运费

题目：某地区有两个城镇，它们每周分别生产700吨和1200吨固体废物。现拟用三种方式（焚烧、填海、掩埋）分别在三个场地对这些废物进行处理（如图），每个场所的处理成本分为固定成本和变动成本两部分，数据如表。

填海

焚烧

掩埋

城镇1

城镇2

700吨

1300吨

1200吨

500吨

1000吨

两城镇到各处理场所的运费、应处理量及各处理场所的能力如下表所示：

运费((元/吨) 焚烧 Y1

填海 Y2

掩埋 Y3

应处理量

城镇1 城镇2

7.5 （X11） 5.0 (X21)

5 (X12) 7.5 (X22) 15 (X13) 12.5 (X23) 700 1200 处理能力（吨/周） 1000 500 1300 固定成本 3850 1150 1920 变动成本(元/吨)

12

16

6

试求使两城镇处理固体废物总费用最少的方案。

实验步骤

第一步：建立整数规划模型 由题意可得如下整数线性规划模型：

Min Z =12*（X11+X21）+16*（X12+X22）+6*(X13+X23）

+7.5*X11+5.0*X21+5*X12+7.5*X22+15*X13+12.5*X23+3850*Y1+ 1150*Y2+1920Y3

X11+X21≤1000*Y1 0 不采取i 种处理方法 X12+X22≤500*Y2 Yi=

X13+X23≤1300*Y3 1 采取i 种处理方法 X11 +X12 +X13=700 X21 +X22 +X23=1200

X11 ，X12 ，X13 ，X21 ，X22 ，X23≥0

第二步：用Spreadsheet 进行问题描述与建模。 如下图所示：

第三步：在Excel规划求解功能中输入整数约束并求解在规划求解参数框中输入目标单元格(目标函数地址)、可变单元格(决策变量地址)和四个约束条件，包括整数约束，其规划求解参数框。如下图所示：

然后在规划求解选项参数框中选择“采用线性模型”和“假定非负”，最后在规划求解参数

对话框中单击“求解”得到本问题的最优解。如下图所示：

总结

通过这个实验，我熟悉了整数线性规划的有关基本概念，掌握求整数线性规划的使用方法和操作步骤，而且更加懂得了掌握建模思想的重要性。本实验就是利用Excel的规划求解来寻找垃圾处理的最佳方案，能够使该地区用最少的金钱来处理垃圾。通过上机实验，我对Excel 表格的应用能力有了进一步的提高，达到计算机与运筹学同时掌握的效果。

实验三运输问题

实验内容：

一、运输问题

某自行车制造公司拥有两个装配厂，且在四个地区有销售公司。该公司生产和销售的相关数据如表3.1：

表3.1 两个装配厂的相关数据

装配厂 A B

产量（辆）1100 1000

装配费用（元/辆）45 55

表3.2 四个销售公司和需求量

表3.1 两个装配厂的相关数据

销售公司 1 2 3 4

需求量600 300 550 650

从两个装配厂到四个销售公司的运价表：

运输单价销售公司

1 2 3 4

装配厂A 9 4 7 18

装配厂B 2 17 15 8

各家销售公司所需的自行车应由哪个厂装配，才能保证公司获得最大利润？

实验步骤

第一步：建立运输问题模型：

Minz=9X11+4X12+7X13+18X14+2X21+17X22+15X23+8X24+45*1100+55*1000

X21+x22+x23+x24=1000

X11+X12=600

X22+x12=300

X13+x23=550

X14+x24=650

Xij>=0 i=1,2 j=1,2,3,4

第二步：用Spreadsheet进行问题描述与建模。

如下图所示：

第三步：在Excel规划求解功能中输入约束并求解在规划求解参数框中输入目标单元格(目标函数地址)、可变单元格(决策变量地址)和约束条件。如下图所示：

数对话框中单击“求解”得到本问题的最优解。如下图所示：

二、指派问题

某大型工程有五个工程项目，决定向社会公开招标，有五家建筑能力相当的建筑公司分别获得中标承建。已知建筑公司A i （I=1，2，3，4，5）的报价c ij （百万元）见表，问该部门应该怎样分配建造任务，才能使总的建造费用最小？

表2-2 各公司完成工程的报价表

? 实验步骤

? 第一步：建立运输问题模型： ? MinZ=4X11+8X12+……+10X54+6X55 约束条件：

工程

公司

B1 B2 B3 B4 B5 A1 4 8 7 15 12 A2 7 9 17 14 10 A3 6 9 12 8 7 A4 6 7 14 6 10 A5

6

9

12

10

6

连加Xij=1 j=1，2 (5)

连加Xij=1 i=1，2 (5)

Xij=0或1 i，j=1，2……，5

?第二步：用Spreadsheet进行问题描述与建模。

?如下图所示：

?

?第三步：在Excel规划求解功能中输入约束并求解在规划求解参数框中输入目标单元格(目标函数地址)、可变单元格(决策变量地址)和约束条件。如下图所示：

?

?

?然后在规划求解选项参数框中选择“采用线性模型”和“假定非负”，最后在规划求解参数对话框中单击“求解”得到本问题的最优解。如下图所示：

实验四 最短路问题

? 实验目的

学会将最短路径问题转化成线性规划问题，并学会用Excel 解决线性规划问题。

? 实验要求

用Excel 解决最短路径问题，掌握建模、规划求解出最短路径。 一、实验内容：求解V1到V8的最短距离。

? 实验步骤

第一步：在Excel 表中建立模型。如下图：

第二步：设置规划参数如下图：

V 6

V 4 V 2

V 3

V 1

V 5

V 7

V 8

4

6

5 4

4

7

9 7

5

6

4

1

5