运筹学上机作业

运筹学实验指导书

实验目的：充分发挥WinQSB这一先进的计算机工具的强大功能，理论与应用

结合，丰富教学内容，提高学习兴趣，使学生能基本掌握WinQSB软件常用命令和功能。

实验要求：能用软件求解运筹学中常见的数学模型。

实验一 线性规划与对偶问题

1．用软件完成求解案例1 配料方案问题

软件说明： （1）WinQSB软件求解LP不必化为标准型，对于有界变量及无约束变量可不转化为标准型，只要修改系统变量类型即可，对于不等式约束也不必转化为标准型，直接输入不等式符号。 （2）调用LP和ILP程序（点击开始→程序→WINQSB→Linear and Integer Programming）。 （3）打开已存在的文件（系统自动带几个典型例题供学习）。

观赏例题：点击File→Load Problem→lp.lpp，点击菜单栏Solve and Analyze→Solve the problem或点击工具栏中的图标用单纯形法求解，直接得到最终单纯形表。观赏一下用单纯形法迭代步骤：点击菜单栏Solve and Analyze→Solve and Display steps，再在菜单栏中点击simplex iteration→next iteration则可。

（4）建立新问题，输入数据。在选择输入格式时，选择spread sheet matrix form则以电子表格形式输入变量系数矩阵和右端常数矩阵。

2、产品产量问题

某企业生产两种产品，分别使用4种原材料，4种原材料目前库存量分别为300吨，400吨，500吨和500吨，两种产品所需各种原材料数量如表示。又知两种产品的单位利润分别为2800吨和3200吨，如何计划两种产品的产量，使利润达到最大。 原材料 产品 A B 库存量 1 1.4 1.6 300 2 1.3 1.7 400 3 1.4 1.5 500 4 1.4 1.7 500 产量 x1 x2 （1）建立该问题的线性规划模型，并用软件求出最优解。 （2）写出该问题的对偶问题，并由原问题的最优结果（表），分析对偶解。 软件说明：

（1）启动线性规划与整数规划程序，建立新问题，输入数据，存盘。 （2）点击Format─→Switch to Dual Form ,得到对偶问题的数据表，点击Format─→Switch to Normal Model Form ,得到对偶模型，点击Edit─→Variable Name,分别修改变量名，回车后得到以y为变量名的对偶模型。

（3）再一次求对偶返回到原问题，查看最优表中影子价格（Shadow Price）对应列的数据就

1

是对偶问题的最优解。

（4）观察最优表中最后两列可得价值系数（cj）与右端常数（bi）的最大最小（allowable min /allowable max）允许变化范围。(灵敏度分析)

3、用软件完成求解案例13生产计划及灵敏度分析。

实验二 运输问题与整数规划

1、女子体操团体赛规定：

（1）每个代表队由5名运动员组成，比赛项目是高低杠、平衡木、鞍马和自由体操。 （2）每个运动员最多参加3个项目，并且每个项目只能参赛一次。 （3）每个项目至少要有人参赛一次，并且总的参赛人次数等于10。

（4）每个项目采用10分制计分，将10次比赛的得分求和，并排序，分数越高成绩越好。已知代表队5名运动员各单项的预赛成绩如表所示。 甲 乙 丙 丁 戊 高低杠 8.6 9.2 8.8 8.5 8.0 平衡木 9.7 8.3 8.7 7.8 9.4 鞍马 8.9 8.5 9.3 9.5 8.2 自由体操 9.4 8.1 9.6 7.9 7.7 为安排运动员的参赛项目使团体总分最高，试建立该问题的线性规划模型，并用软件求解。

2、某商场规定：营业员每周连续工作5天后休息2天，轮流休息。根据统计，商场每天

需要的营业员如表所示。

商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。 星期 一 二 三 四 需要人数 300 300 350 400 星期 五 六 日 需要人数 480 600 550 试建立该问题的线性规划模型，并用软件求解。

3、 对典型案例5（运输问题）：用软件求出最优调运方案。

软件说明：

（1） 调用子程序network modeling，新建问题，选择运输问题（transportation Problem）,

输入标题、产地及销地数。

（2） 输入数据，并重命名产地和销地。

（3） 求解，点击菜单栏solve and analyze,下拉菜单有四个选项：solve the problem（只求

出最优解，）solve and display steps-networks（网络图求解并显示迭代步骤）solve and display steps-tableuau（表格求解并显示迭代步骤）和只求初始解，根据要求选择其中的一种方法。

2

（4） 显示图解结果。点击菜单栏results－graphic solution,系统以网络流的形式显示最优调

运方案。

实验三 动态规划问题

1、背包问题。这是运筹学中一个著名的问题。某人外出旅游，需将5个物品装入背包，

但背包装物重量有限制，总重量W不得超过15千克。物品重量及其价值的关系如下表所示。试问：如何装入这些物品，使背包的总价值最大？

物品 A B C D E 重量(千克) 6 5 2 3 1 价值(元) 18 15 8 10 6

软件说明：

（1）调用子程序DP，新建问题，选择背包问题（Knapsack Problem）,输入标题和物品的品种数。

（2）在弹出的表格中输入有关数据，见图1。

图1 背包问题数据输入窗口

第一列item identification为物品名称。

第二列units available为物品限量和背包载重量限制。 第三列units capacity requried为单位物品重量。 最后一列return function为物品价值函数。

2、最短路径问题：用软件求出图2中的最短路线。

设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到达目的地，其间的运输费用如题图中数字所示(单位：百元)。试求：总运费最低廉的路线（用动态规划方法求解）。 软件说明：

（1）调用子程序DP，新建问题，选择问题（stagecoach [shorted route]Problem）,输入标题和节点数。

3

（2）在弹出的表格中输入两点间的距离，两点间没有弧连接时不输入数据。

70 10 BC 1 1 40 60 D40 1 30 20 30 60 40 E 20 A BC 2 2 30

40 30 40 D 2 30 40 10

30 BC 3 3

50 出口港 进口港 机器制造厂 城市 某工厂

图2

3、生产与存储问题：某配送中心销售的某一商品在未来4个月的估计量如表所示。进价每百件1000元，保管费用每百件50元，每批进货杂费3000元。假定1月初的存货和5月初的存货为0。设每批最多进货量为6件，试求该配送中心在这4个月的最优进货计划。要求建立该问题的动态规划模型，并用软件求解。 月份 销售量ak 1 2 2 3 3 2 4 4 软件说明：

（1）调用子程序DP，新建问题，选择生产与存储问题（Production and Inventory scheduling Problem）,输入标题和生产时期数。 （2）在弹出的表格中输入数据。

数据输入界面如图3所示，图中的第2列period identification为阶段标识，第3列demand为各期的需求量，第4列production capacity为每期产品的最大生产能力约束，能力无限制，输入M，第5列storage capacity为每期的库存限制，第6列production setup cost为生产时的固定成本，最后一列为每期的变动成本函数，P是产量，H是存量。

图3

4

实验四 网络图

1、最短路线问题：用软件完成作业中最短路线问题的求解。

软件说明：

（1）调用子程序Network Modeling，新建问题，选择问题（Shorted Path Problem）,输入标题和节点数。

（2）在弹出的表格中输入数据，如果是有向图就按弧的方向输入数据，若是无向图，每一条边必须输入两次，无向边变成两条方向相反的弧。点击solve and anayze后系统提示选择图的起点和终点，求解结果不仅给出v1到终点的最短路径和路长，还给出v1到其余各点的最短路径和路长。

2、网络最大流问题：用软件完成作业中网络最大流问题的求解。

软件说明：

调用子程序Network Modeling，新建问题，选择最大流问题（Maximal Flow Problem）,输入节点数,求解与最短路方法相同。结果还可显示为网络图，点击results ─→graphics solution，输出最大流网络图。

实验五 存贮论

1、某公司经理一贯采用不允许缺货的经济批量公式确定订货批量，因为他认为缺货虽

然随后补上总不是好事。但由于激烈竞争迫使他不得不考虑采用允许缺货的策略。已知对该公司所销产品的需求为R＝800件一年。每次的订货费用为150元，存贮费为3元／（件·年），发生短缺时的损失为20元／（件·年），试分析：

（1）计算采用允许缺货的策略较之原先不允许缺货策略带来的费用上的节约；

（2）如果该公司为保持一定信誉，自己规定缺货随后补上的数量不超过总量的15％，任何一名顾客因供应不及时需等下批货到达补上的时间不得超过3周。问这种情况下，允许缺货的策略能否被采用? 软件求解

不允许缺货时，数据输入界面如图1，数据输出如图2所示。

5

图1 经济订货批量的数据输入窗口

图2 经济订货批量的数据输出窗口

允许缺货时，输入窗口中，输入项“Unit shortage cost per year”改为M即可。 结果说明：

（1）由图2知：不允许缺货时，订购量Q0＝283件，存贮总费用f1=848.53元／年； （2）同理可求得允许缺货时，订购量Qs＝303件，存贮总费用f2=791.27元／年。 最大缺货量S＝40件。 （3）分析

由求解数据知，允许缺货比不允许缺货每年节约费用57.26元，节约率为6.74%。

又最大缺货量S＝40件，故缺货比例为等待的最大时间为：

40?13.2%，小于最大缺货量15％。而缺货30340，小于3周，故允许缺货的策略可以接受。 ?365?18.25（天）

800从这个例题我们可以看出，如果缺货造成的损失很小时，缺货模型是一种使存贮总费用较低的存贮模型。

2、 某食品店出售生日蛋糕，每盒成本5元，售价7元。若到期卖不完，则削价为每

盒4元销售完毕。已知蛋糕销售量Q服从λ＝8的泊松分布。问应订购多少盒蛋糕为宜？ 解：（1）建模

这个问题可视为一个需求为随机的简单单周期存贮模型。据题意有：单位产品的利润 α＝7－5＝2（元），滞销损失β＝1，则最佳订购量Q*应满足下面的公式：

6

Q*－1x?0?p(x)??????p(x)

x?0?Q*（2）软件求解

我们调用存贮论中的“Single-period Stochastic Demand (Newsboy)Problem”模型求解，数据输入界面如图3所示，数据输出界面如图4所示。

图3 单周期随机存贮模型数据输入窗口

图4 单周期随机存贮模型数据输出窗口

（3）分析

从图4，我们知道最佳订购量Q*＝9盒，期望利润为12.87元。我们还知道服务水平为71.66%，这里的服务水平实际上就是蛋糕需求量小于等于9的概率。

7

本文来源：https://www.bwwdw.com/article/9mup.html