运筹学实验报告 2

运筹学实验报告

学院： 专业班级： 姓名： 学号：

实验一 线性规划

一、实验目的

学习WinQSB软件的基本操作，利用Linear Programming功能求解线性规划问题。掌握线性规划的基本理论与求解方法，重点在于单纯形法的应用以及灵敏度分析方法。

二、实验内容

安装WinQSB软件，了解WinQSB软件在Windows环境下的文件管理操作，熟悉软件界面内容，掌握操作命令。利用Linear Programming功能建立线性模型，输入模型，求解模型，并对求解结果进行简单分析。

三、实验步骤

1．将WinQSB文件复制到本地硬盘；在WinQSB文件夹中双击setup.exe。 2．指定安装WinQSB软件的目标目录（默认为C:\\ WinQSB）。

3．安装过程需要输入用户名和单位名称（任意输入），安装完毕之后，WinQSB菜单自动生成在系统程序中。

4．熟悉WinQSB软件子菜单内容及其功能，掌握操作命令。 5．求解下面线性规划问题：

某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D。已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价分别见下表1和2。该厂应如何安排生产，使利润收入为最大？

表1 产品名称 A B D 规格要求 原材料C不少于50% 原材料P不超过25% 原材料C不少于25% 原材料P不超过50% 不限 表2 原材料名称 C P H

列出该线性规划问题的模型如下：

每天最多供应量（kg） 100 100 60 单价（元/kg） 65 25 35 单价（元/kg） 50 35 25 以AC表示产品A中C的成分，AP表示产品A中P的成分，依次类推。则约束条件为：

AC+BC+DC≤100 AP+BP+DP≤100 AH+BH+DH≤60

在约束条件中共有9个变量，为计算和叙述方便，分别用x1,…,x9表示。令

x1=Ac, x2=Ap, x3=AH, x4=BC, x5=BP, x6=BH, x7=DC, x8=DP, x9=DH. 则：

1214x1x11234x2x21214x3x3x1x2x3x1,,x903412x4x41412x5x51412x6x6x7x5x6x80000100100x960x4启动程序 开始→程序→WinQSB→Linear and Integer Programming，点击菜单栏File中的New Problem项，建立新问题。

在LP-ILP Problem Specification对话框中：输入问题名Problem Title为1，变量个数（Numberof Variables）为9，约束条件个数（Number of Constraints）为7，选择目标函数的准则Objective Criterion为Maximization表示最大化，变量类型Default Variable Type为Nonnegative continuous表示非负连续，选择数据输入模式为电子表格Spreadsheet Matrix Form，按OK键后填写处如下电子表格：

点击菜单栏Solve and Analyze中的Solve the Problem项或者点击工具栏中的图标用单纯形法求解，查看求解得出的结果；如下图所示，最优解为x1=100，x2=50，x3=50，

x4=x5=x6=x7=x8=x9=0，目标函数最大。即A产品生产200个，B、C产品部生产，可使利

润最大，最大为500.

经验证，此结果与手算结果一致。

实验二 运输问题

一、 实验目的

掌握运输问题和指派问题的求解方法，并能够熟练运用WinQSB软件的Network Modeling功能求解给出的问题。

二、 实验内容

对于给出的运输和指派问题，建立新模型，利用WinQSB软件的Network Modeling进行求解，并对求解结果进行分析。同时手工求解给出的问题，将两种方式的求解结果进行对比。

三、 实验步骤

1.求解下面该运输问题：

设有三个化肥厂（A, B, C）供应四个地区（I, II, III, IV）的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价表如下表所示。试求出总的运费最节省的化肥调拨方案。

需求地区 化肥厂 A B C 最低需求 最高需求 I 16 14 19 30 50 II 13 13 20 70 70 III 22 19 23 0 30 IV 17 15 — 10 不限 产量 50 60 50 注意：表格中的运价可以填入M（任意大正数）。

启动程序，开始→程序→WinQSB→Network Modeling，点击菜单栏File中的New Problem项，建立新问题。

首先，在Net Problem Specification对话框的Problem Type中选择Transportation Problem（运输问题），Objective Criterion中选择Minimization（最小化），Data Entry Format（数据输入格式）中选择Spreadsheet Matrix Form（电子表格形式）。在Problem Title中键入问题名2，输入Number of Sources（产地数量）4、Number of Destinations（销地数量）6。确定后在获得的电子表格中输入各项数据如下表所示：

点击菜单栏Solve and Analyze中的Solve the Problem项求解问题，观察求解结果如下表：最低运费为2460元。

经检验，与手算结果一致。 2.求解下面指派问题

人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核五人在不同岗位的成绩（百分制）如下表所示，如何安排他们的工作使总成绩最好，应淘汰哪一位。

工作 人员 甲 乙 丙 丁 戊 人力资源 85 95 82 86 76 物流管理 92 87 83 90 85 市场营销 73 78 79 80 92 信息管理 90 95 90 88 93 点击菜单栏File中的New Problem项，建立新问题。

在Net Problem Specification对话框的Problem Type中选择Assignment（指派问题），Objective Criterion中选择Maximization，Data Entry Format（数据输入格式）中选择Spreadsheet Matrix Form（电子表格形式）。在Problem Title中键入问题名3，输入Number of Objects（人员数量）5、Number of Assignments（任务数量）4。确定后在获得的电子表格中输入各项数据如下表所示:

点击菜单栏Solve and Analyze中的Solve the Problem项求解问题，观察求解结果如下表：应安排甲做物流管理、乙做人力资源、丙做信息管理、戊做市场营销，淘汰丁，这样可以使他们的工作总成绩最好。

经检验，此结果与手算结果一致。

实验三 整数规划

一、 实验目的

掌握常见整数规划问题的基本形式，以及相应的求解方法。能够熟练运用WinQSB软件的Integer Programming功能求解整数规划（纯整数、混合整数）、0-1规划问题。

二、 实验内容

对于给出的问题，建立整数规划模型，利用WinQSB软件进行求解，并对求解结果进行简单分析。

三、 实验步骤

1．求解以下整数规划问题

某厂拟建两种不同类型的冶炼炉。甲种炉每台投资为2个单位，乙种炉每台需投资为1个单位，总投资不能超过10各单位；又该厂被允许可用电量为2个单位，乙种炉被许可用电量为2个单位，但甲种炉利用余热发电，不仅可满足本身需要，而且可供出电量1个单位。已知甲种炉每台收益为6个单位，乙种炉每台收益为4个单位。试问：应建甲、乙两种炉各多少台，使之收益为最大？ 对该问题建立数学模型如下：

MaxZ=6x1+4x2

2x1x210x12x22x1,x2为非负整数

启动程序 开始→程序→WinQSB→Linear and Integer Programming，点击菜单栏File中的New Problem项，建立新问题。

在LP-ILP Problem Specification对话框中：输入问题名Problem Title为4，变量个数（Numberof Variables）为2，约束条件个数（Number of Constraints）为2，选择目标函数的准则Objective Criterion为Maximization表示最大化，变量类型Default Variable Type为Nonnegative integer表示非负整数，选择数据输入模式为电子表格Spreadsheet Matrix Form，

按OK键后填写处如下电子表格：

点击菜单栏Solve and Analyze中的Solve the Problem项求解问题，观察求解结果如下表：应建甲种炉4台，乙种炉2台可获得最大收益，最大收益为32.

经检验，此结果与手算结果一致。 2.求解以下整数规划问题

某厂拟在A、B、C、D、E五个城市建立若干产品经销联营点，各处设点都需资金、人力、设备等，而这样的需求量及能提供的利润各处不同，有些点可能亏本，但却能获得贷款和人力等。而相关数据如下表所示，为使总利益最大，问厂方应作出何种最优点决策？

资源 城市 A B C D E 资源限制 应投资金 4 6 12 -8 1 20 应投人力 5 4 12 3 -8 15 应投设备 1 1 1 0 0 2 获利 4.5 3.8 9.5 -2 -1.5 对该问题建立数学模型如下：

MaxZ=4.5X1+3.8X2+9.5X3-2X4-1.5x5

4x16x212x38x4x5205x14x212x33x48x515 x1x2x32x1,...x5为非负整数启动程序 开始→程序→WinQSB→Linear and Integer Programming，点击菜单栏File中的New Problem项，建立新问题。

在LP-ILP Problem Specification对话框中：输入问题名Problem Title为5，变量个数（Numberof Variables）为5，约束条件个数（Number of Constraints）为3，选择目标函数的准则Objective Criterion为Maximization表示最大化，变量类型Default Variable Type为Nonnegative integer表示非负整数，选择数据输入模式为电子表格Spreadsheet Matrix Form，按OK键后填写处如下电子表格：

点击菜单栏Solve and Analyze中的Solve the Problem项求解问题，观察求解结果如下表：在C投入资源量为2，在D投入资源量为1，在E投入资源量为2，可使总收益最大，最大为14.

经检验，此结果与手算结果一致。

实验四 网络优化

一、 实验目的

掌握最小支撑树、最短路、最大流的求解方法，并能够熟练运用WinQSB软件的Network Modeling功能求解不同问题。

二、 实验内容

利用WinQSB软件的Network Modeling功能求解最小支撑树、最短路、最大流问题，掌握求解步骤，分析求解结果。

三、 实验步骤

对下面问题进行分析求解

某市政公司在未来5~8月份内需完成四项工程：（A）修建一条地下通道，（B）一座人

行天桥，（C）一条道路和（D）一个街心花园，工期和所需劳动力见下表。该公司共有劳动力120人，任何一项工程在一个月内的劳力投入不能超过80人。问该公司如何分配劳动力完成所有工程以及能否按期完成。试将此问题归结为最大流问题，并进行求解。

工程 A B C D 工期 5~7月 6~7月 5~8月 8月 需要劳动力（人） 100 80 200 80 启动程序，开始→程序→WinQSB→Network Modeling，点击菜单栏File中的New Problem项，建立新问题。

在Net Problem Specification对话框的Problem Type中选择Maximal Flow Problem（最大流问题）；Objective Criterion中选择Maximization（最大化）；Data Entry Format选择Graphic Model Form；在Problem Title中键入问题名6，Number of Nodes输入节点数量10，按OK键建立如下网络图：

点击菜单栏Solve and Analyze中的Solve the Problem项，在Select Start and End Nodes对话框中选择起点与终点，求解模型，观察求解结果如下图所示：

其表格结果如下表所示：

经检验，此结果与手算结果一致。