石河子大学：《运筹学》课程教学资源（实验指导）动态规划的WinQSB求解

(八)动态规划的WinQSB求解 WinQSB的动态规划模块(DP)包括3个方面内容： 马车驿站问题（最短路问题）(Stagecoach[Shortest Route]Problem) 背包问题(Knapsack Problem) 多生产存储问题(Production and Inventory Scheduling) 1马车驿站问题 实验内容：求解课本P198页例1 7 操作先蜜加下 执行：“程序WinQSB/Dynamic Programming/New/New Problem”弹出并设置如图1所示 对话框。 Problem Type C Knapsack Problem Production and Inventory Scheduling Problem Title 1 Number of Nodes 10 oK Cancel☐Heip 图1动态规划类型选项 ·最短路问题(Stagecoach[Shortest Route]Problem),节点数(Number of Nodes)输入IO, 单击OK,弹出数据输入窗口（图2）

（八） 动态规划的 WinQSB 求解 WinQSB的动态规划模块（DP）包括3个方面内容：  马车驿站问题（最短路问题）（Stagecoach[Shortest Route]Problem）  背包问题（Knapsack Problem）  生产存储问题（Production and Inventory Scheduling） 1 马车驿站问题 实验内容：求解课本 P198 页例 1 操作步骤如下： 执行：“程序/WinQSB/Dynamic Programming/New/New Problem”弹出并设置如图1所示 对话框。 图 1 动态规划类型选项 最短路问题（Stagecoach [Shortest Route]Problem），节点数（Number of Nodes）输入10， 单击OK，弹出数据输入窗口（图2）。 7 5 1 A B1 B2 B3 C3 C2 C1 D1 D2 E 2 5 3 5 6 3 2 4 5 1 4 6 3 3 3 3 4

de2|Node3 Node4 Node5|Node6|Node7|Node8|Node9 Node10 图2数据编辑寅口 ●执行菜单命令：Edit/Node Names,修改节点名称（图3）。 国ode Rames for创1 de Number Node Nam OK Cancel Help 图3更改节点名粉 ·单击OK,跳回数据窗口，输入数据（邻接矩阵）（图4） BI B2 B3 CI C2 C3 DI D2 E 图4棉入数据 ·执行菜单命令：Solve andAnalyze/Solve the Problemi得运行结果（见图5）

图2 数据编辑窗口 执行菜单命令：Edit/Node Names，修改节点名称（图3）。 图3 更改节点名称 单击OK，跳回数据窗口，输入数据（邻接矩阵）（图4） 图4 输入数据 执行菜单命令：Solve andAnalyze/Solve the Problem得运行结果（见图5）

B3 11 B3 C2 C2 D2 4 D2 11 4 ToE Min.Distance -11 CPU -0 图5运行结果 即最短路径：A→B3→C2一D2一E,最短路长11。 2背包问题(Knapsack Problem) 实验内容：求解课本P213页例8 有一艘货船，最大载重量为5，用以装载三种货物，每种货物的单位重量和相应单位价 值如表1所示。问如何装载才使总价值最大？ 表1货物质量价值表 货物编号 1 2 3 单位重量 2 3 1 单位价值 65 80 30 操作步骤如下： ●执行：“程序WinQSB/Dynamic Programming/New/New Problem”弹出并设置如图6所示 对话框。 DP Probles Specification Problem Type Stagecoach (Shortest Route)Problem Knapsack Problem Production and Inventor Scheduling Problem Title网B Number of items 3 各物品最大装载重 Cancel Help 量及总找重量 装载物品的价值 单件重量 图6动态规划类型选项 ·选择第2项，输入物品种类数(Number of Items)3,单击OK,弹出数据入窗口（图7）

图5 运行结果 即最短路径：A→B3→C2→D2→E，最短路长11。 2 背包问题（Knapsack Problem） 实验内容：求解课本 P213 页例 8 有一艘货船，最大载重量为5，用以装载三种货物，每种货物的单位重量和相应单位价 值如表1所示。问如何装载才使总价值最大？ 表 1 货物质量价值表 货物编号 1 2 3 单位重量 2 3 1 单位价值 65 80 30 操作步骤如下： 执行：“程序/WinQSB/Dynamic Programming/New/New Problem”弹出并设置如图6所示 对话框。 图6 动态规划类型选项 选择第2项，输入物品种类数（Number of Items）3，单击OK，弹出数据输入窗口（图7）。 各物品最大装载重 量及总载重量 单件重量 装载物品的价值

Knapsack Capacity 图7数据编辑窗 注：装载物品的价值必须是公式，该值物品的价值系数乘以表示装载数量。 ●执行菜单命令：Solve andAnalyze/Solve the Problemi得运行结果（图8） Name 65% 130 Item 0 80x 0 3 30 30 0 Total Return Value=160 CPU=0 图8运行结果 即物品1装载21，物品2装载0吨，总价值1货币单位

图7 数据编辑窗口 注：装载物品的价值必须是公式，该值=物品的价值系数乘以x；x表示装载数量。 执行菜单命令：Solve andAnalyze/Solve the Problem得运行结果（图8） 图8 运行结果 即物品1装载2t，物品2装载0吨，总价值1货币单位