目录
目录 ...................................................... 1 第一章 管理运筹学课程设计 ................................ 2
第一节 线性规划之生产计划问题 ......................... 2 第二节 物资的最小费用运输问题 ............................ 5 第三节 管理中的随机性决策问题 ........................ 10 第二章 运筹学软件练习题 ................................. 14
第一节 线性规划 ...................................... 14 第二节 运输问题 ...................................... 16 第三节 整数规划 ...................................... 19 第三节 决策分析 ...................................... 21 第三节 最短路问题 .................................... 23 第三节 最小支撑树 .................................... 25 第三节 网络最大流 .................................... 26 第三节 最小费用最大流 ......................................... 28 参考文献 ................................................. 30
第 1 页 共 31 页
第一章 管理运筹学设计 第一节 线性规划之生产计划问题
一﹑问题的提出：某大型公司在安徽合肥地区的工厂仅生产扳手和钳子，扳手和钳子是由钢铁制造的，并且制造过程先在浇铸机上浇铸，然后在装配机上装配。用于生产一个扳手和一个钳子的钢铁数量和每天可以得到的钢铁数量见表1—1的第一行，下两行是生产一个扳手和一个钳子所需要的机器使用时间以及这些机器的生产总时间，表的最后一行是每天这些变量（扳手和钳子）对本公司分厂的盈利贡献。
表1—1某大型公司在安徽亳州地区的工厂生产扳手和钳子的有关数据
钢铁（kg） 浇铸机工时（h） 装配机工时（h） 盈利贡献（百元/千件） 扳手 1.5 1.0 0.3 130 钳子 1.0 1.0 0.5 150 可获得的资源数量 每天27000kg 每天21000h 每天9000h 该公司想作出安徽合肥地区的工厂有关扳手和钳子每天的生产量的计划，使得对公司分厂的盈利贡献得到最大化。该公司要解决问题是：
（1）为使这个大型公司在安徽合肥地区的工厂的盈利贡献得到最大化，应该计
划每天生产多少件扳手和钳子？
（2）根据这个计划该公司分厂的最大盈利是多少？ （3）在这个计划中，哪些资源是最关键的因素？
二﹑建立数学模型：对于这个问题，主要目标是使经营对公司分厂的盈利贡献得到最大化。该公司必须对每天生产的扳手和钳子的数量作出决策，但由于资源数值比较大，可以定义如下：
x1为每天生产的扳手数量，以千件为单位 x2为每天生产的钳子数量，以千件为单位
在这个问题中，目标是确定生产计划中的X1和X2的数值，使对公司分厂的盈利贡献最大化。为了求出这两个数值，有一些必须满足的约束条件，这些约束条件是可供利用的钢铁数量限制、浇铸机工时限制和装配机工时限制，即：
钢铁约束：1.5 x1 + x2 ≤27 浇铸机约束：x1 + x2 ≤21
第 2 页 共 31 页
装配机约束：0.3x1 + 0.5x2 ≤9
因此该大型公司在安徽合肥地区的工厂生产计划问题的数学模型即线性规划问题模型为：
max z = 130x1 + 100x2
1.5 x1 + x2 ≤27 s．t． x1 + x2 ≤21 0.3x1 + 0.5x2 ≤9 x1 ， x2 ≥ 0 化为标准型：
max z = 130x1 + 100x2 +0 x3 + 0x4 + 0x5 1.5 x1 + x2 + x3 ≤27 s．t． x1 + x2 + x4 ≤21 0.3x1 + 0.5x2 + x5 ≤9
x1 ，x2 ，x3 ，x4 ，x5 ≥ 0
三﹑模型的解答：本线性规划问题模型可以利用单纯形法得出最优解和最优值。 cj CB XB b′ 0 x3 27 0 x4 21 0 x5 9 λj 130 x1 18 0 x4 3 0 x5 18/5 λj 130 x1 12 100 x2 9 0 x5 9/10 λj 表1—2 130 100 0 0 0 X1 X2 X3 X4 X5 [1.5] 1 1 0 0 1 1 0 1 0 0.3 0.5 0 0 1 130 100 0 0 0 1 2/3 2/3 0 0 0 [1/3 ] -2/3 1 0 0 3/10 -1/5 0 1 0 40/3 -260/3 0 0 1 0 2 -2 0 0 0 -2 3 0 0 0 2/5 -9/10 1 0 0 -60 -40 0 j
θ 18 21 30 27 9 12 由于所有的检验数λ为：
均已大于等于零，由此可知该线性规划问题的最优解
X﹡ = （12 ，9 ，0 ，0 ，9/10）T
所以该公司分厂的盈利贡献最大化的生产计划为：x1= 12 ， x2= 9
第 3 页 共 31 页
对公司分厂的盈利贡献的最大值为2460百元/天。
因此该大型公司在安徽合肥地区的分厂要解决的问题的答案为： （1） 该大型公司分厂应该计划每天生产12000件扳手和9000件钳子
（2） 对该大型分厂盈利的总贡献将是：max = 130 x1 + 100 x2 = 2460（百元/天） （3） 资源的使用率：
钢铁数量 = 1.5 × 12000 + 1 × 9000 = 27000 （kg）
这个结果正好等于每天可以得到的钢铁数量，所以钢铁数量是该大型公司分厂生产扳手和钳子的关键资源
浇铸机工时 = 1 × 12000 + 1 × 9000 = 21000（h）
这个结果正好等于每天浇铸机的生产能力，所以浇铸机的生产能力是该大型公司分厂生产扳手和钳子的关键资源
装配机工时 = 0.3 × 12000 + 0.5 × 9000 = 8100 （h）
这个结果小于每天9000h的装配机的生产能力，所以装配机的生产能力不是该大型公司分厂生产扳手和钳子的关键资源
四﹑运筹学软件检验
**********************最优解如下*************************
目标函数最优值为 : 2460
变量 最优解 相差值 ------- -------- -------- x1 12 0 x2 9 0
约束 松弛/剩余变量 对偶价格 ------- ------------- --------
1 0 60 2 0 40 3 5.4 0 目标函数系数范围 :
变量 下限 当前值 上限 ------- -------- -------- --------
x1 100 130 150 x2 86.667 100 130 常数项数范围 :
约束 下限 当前值 上限 ------- -------- -------- --------
1 21 27 31.5 2 18 21 27 3 3.6 9 无上限
第 4 页 共 31 页
第二节 物资的最小费用运输问题
一﹑问题的提出：包头市某食品生产公司在青山区有三个食品生产基地（可以认为是A1 、A2 、A3 ）和四个食品存储仓库分别在昆都仑区、东河区、青山区和固阳县（可以认为是B1、B2、B3、B4）这三个生产基地生产的食品需要及时运送到仓库区存储起来以防变质。各生产基地的生产能力（吨）和各村储仓库的存储量（吨）以及从生产基地到存储仓库的单位运价（百元/吨）见下表，问如何存储可以使总运费达到最小？
表2—1 单位运价表 （单位：百元/吨）
单 位 运 产 地 A1 A2 A3 存储量 价 3 7 2 60 2 5 5 40 7 2 4 20 6 3 5 15 50 60 25 仓 库 B1 B2 B3 B4 产量 二﹑建立数学模型：设xij表示从产地Ai（i=1，2，3）到存储仓库Bj（j=1， 2，3，4）的运输量，cij 表示表中所示的单位运价。经分析可建立线性规划数学模型表示如下： min z = ??cijxij
i?1j?134?i?13
xij = 135 （j=1，2，3，4）
s．t ． 错误！未找到引用源。 xij = 135 （i=1，2，3）
xij ≥ 0 （i=1，2，3；j=1，2，3，4）
三﹑模型的解答：此线性规划数学模型可知此问题相当于产销平衡问题，第 5 页 共 31 页
