运筹学上机作业

运筹学实验指导书

实验目的：充分发挥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、最短路线问题：用软件完成作业中最短路线问题的求解 …… 此处隐藏：2582字，全部文档内容请下载后查看。喜欢就下载吧 ……