运筹学课程设计

1、内蒙古科技大学课程设计问题一：（类型：某物资运输企业货物运输方案的优化研究）三个水泥厂供应四个地区的建筑用水泥。假定等量的水泥在这些地区的使用效果相同，已知各水泥厂年产量，各地区的年需求量及各水泥厂到各地区单位水泥的运价表如下表所示，试给出一个基本可行方案。 运价：万元/万吨 地区水泥厂 北京 山东 河北 江苏 产量 保利 万科 恒大3 11 3 101 9 2 87 4 10 5 50 40 50 需求量 30 70 30 10表1.10解：（1）编制运输表，用最小元素法确定初始方案 地区水泥厂北京山东河北江苏产量保利31131050万科1303092840恒大7410550需求量30703

2、010表1.11 地区水泥厂北京山东河北江苏产量保利31131050万科19284030 10恒大7410550需求量30703010表1.12 地区水泥厂北京山东河北江苏产量保利3113201050万科1928403010恒大7410550需求量30703010表1.13 地区水泥厂北京山东河北江苏产量保利3113201050万科1928403010恒大7410550 50需求量30703010表1.14 地区水泥厂北京山东河北江苏产量保利311320101050万科1928403010恒大7410550 50需求量30703010表1.15 地区水泥厂北京山东河北江苏产量保利3113105

3、0202010万科1928403010恒大741055050需求量30703010表1.16初始方案为：x12=20, x13=20, x14=10x21=30, x23=10x32=50其余为 xij = 0相应的运输费用为：z = 630（万元）（2）最优性检验：用位势法算出上述方案中所有空格的检验数 地区水泥厂北京山东河北江苏行保利3 (1)1131010u1=72020万科130928 (-1)u2=6 (-1)10恒大7 (12)45010 (14)5 (2)u3=0列v1=-5v2=4v3=-4v4=3表1.17上表中存在检验数为负数，表明初始方案不是最优方案，需要进一步调整。（3

4、）用闭回路法进行方案调整，从而得到新的调运方案。 地区水泥厂北京山东河北江苏产量保利3 1110330101050万科1309 10208 40恒大7 45010 5 50 需求量30 70 3010表1.18新方案为：x12=10, x13=30, x14=10x21=30, x22=10, x23=0 x32=50其余为 xij = 0相应的运输费用为：z = 620（万元）(4)重复用位势法检验。 地区水泥厂北京山东河北江苏行保利3 (0)11103301010u1=7万科1309 10208 (0)u2=5恒大7 (11)45010 (13)5 (2)u3=0列v1=-4v2=4v3=

5、-3v4=3表1.19上表中不存在负检验数，表明新方案是最优方案。所以，最优方案为： x12=10, x13=30, x14=10x21=30, x22=10, x23=0 x32=50其余为 xij = 0相应的运输费用为：z = 620（万元）软件运行结果：最优解如下* 起 至 销点 发点 1 2 3 4 - - - - - 1 0 10 30 10 2 30 10 0 0 3 0 50 0 0此运输问题的成本或收益为: 620此问题的另外的解如下： 起 至 销点 发点 1 2 3 4 - - - - - 1 0 20 30 0 2 30 0 0 10 3 0 50 0 0此运输问题的成本

6、或收益为: 620此问题的另外的解如下： 起 至 销点 发点 1 2 3 4 - - - - - 1 20 0 30 0 2 10 20 0 10 3 0 50 0 0此运输问题的成本或收益为: 620问题二：（类型：某企业的生产计划安排及优化分析与研究）正华煤机厂生产焦炭、煤焦油两种产品，需要煤、电、劳动力三种资源。计划消耗定额、资源限额如下表。问焦炭、煤焦油两种产品的产量计划如何安排，才能使该厂获得最大利润？产品名称消耗定额资源名称 焦炭 煤焦油 资源限额 煤 电 劳动力 9 4 360吨 4 5 200千瓦 3 10 300工（日）单位产品利润（万元） 7 12 表2.10解：max z

7、 = 7x1+12x2s.t.（1） 确定可行域304090x1x2040501004x1+5x2=2003x1+10x2=3009x1+4x2=360图2.11（2） 从可行域内寻找最优解304090x1x2040501004x1+5x2=2003x1+10x2=3009x1+4x2=360y=-7/12xa图2.12（3） 确定最优点坐标a点坐标就是该问题的最优解，它是直线4x1+5x2200与直线3x1+10x2300的交点，解方程组得x1=20,x2=24;将其带入目标函数有z = 720+1224=428 这表明最优生产计划是焦炭、煤焦油的产量分别为20、24时，可获得最大利润为42

8、8万元。软件运行结果： *最优解如下* 目标函数最优值为 : 428 变量 最优解 相差值 - - - x1 20 0 x2 24 0 约束 松弛/剩余变量 对偶价格 - - - 1 84 0 2 0 1.36 3 0 .52 目标函数系数范围 : 变量 下限 当前值 上限 - - - - x1 3.6 7 9.6 x2 8.75 12 23.333 常数项数范围 : 约束 下限 当前值 上限 - - - - 1 276 360 无上限 2 150 200 226.923 3 227.586 300 4001线性规划1.1求解线性规划问题： min z =x1-x2+x3 软件运行结果： *最

9、优解如下* 目标函数最优值为 : -1.667 变量 最优解 相差值 - - - x1 0 2.722 x2 5 0 x3 3.333 0 约束 松弛/剩余变量 对偶价格 - - - 1 18.333 0 2 0 -.167 3 0 .389 目标函数系数范围 : 变量 下限 当前值 上限 - - - - x1 -1.722 1 无上限 x2 无下限 -1 3.083 x3 0 1 无上限 常数项数范围 : 约束 下限 当前值 上限 - - - - 1 1.667 20 无上限 2 40 60 无上限 3 0 30 451.2求解线性规划问题： max z = 2x1-4x2+5x3-6x4软

10、件运行结果： *最优解如下* 目标函数最优值为 : 31 变量 最优解 相差值 - - - x1 8 0 x2 0 66 x3 3 0 x4 0 130 约束 松弛/剩余变量 对偶价格 - - - 1 0 11 2 0 9 目标函数系数范围 : 变量 下限 当前值 上限 - - - - x1 -1.667 2 无上限 x2 无下限 -4 62 x3 -4 5 无上限 x4 无下限 -6 124 常数项数范围 : 约束 下限 当前值 上限 - - - - 1 -.667 2 无上限 2 -2 1 无上限1.3求解线性规划问题： min z = x1-3x2-2x3软件运行结果： *最优解如下*

11、目标函数最优值为 : 0 变量 最优解 相差值 - - - x1 0 5 x2 0 2.25 x3 0 6 约束 松弛/剩余变量 对偶价格 - - - 1 7 0 2 12 0 3 0 1 目标函数系数范围 : 变量 下限 当前值 上限 - - - - x1 -4 1 无上限 x2 无下限 -3 -.75 x3 -8 -2 无上限 常数项数范围 : 约束 下限 当前值 上限 - - - - 1 0 7 无上限 2 无下限 -12 0 3 0 0 91.4某工厂生产a、b、c三种产品，每种产品的原料消耗量、机械台时消耗量、资源限量及单位产品利润如下表所示。根据用户订货，三种产品的最低月需求量分别

12、为200、250和100件；又据销售预测，三种产品的最大生产量应分别为250、280和120件。如何安排这三种产品的 产量可使该厂的利润最大？列出该问题的线性规划模型并求解。 a b c 资源量 材料 1.0 1.5 4.1 2000 机械 2.0 1.2 1.0 1000 利润（元） 10 14 12 解：max z =10x1+14x2+12x3 软件运行结果： *最优解如下* 目标函数最优值为 : 7860 变量 最优解 相差值 - - - x1 250 0 x2 280 0 x3 120 0 约束 松弛/剩余变量 对偶价格 - - - 1 838 0 2 44 0 3 0 10 4 0

13、 14 5 0 12 目标函数系数范围 : 变量 下限 当前值 上限 - - - - x1 0 10 无上限 x2 0 14 无上限 x3 0 12 无上限 常数项数范围 : 约束 下限 当前值 上限 - - - - 1 1162 2000 无上限 2 956 1000 无上限 3 0 250 272 4 0 280 316.667 5 0 120 1642运输问题2.1某一物资调运问题如下表所示，试求最优调运方案。 销地单价产地 b1 b2 b3 b4 产量 a1 a2 a3 3 11 6 10 1 9 9 7 7 5 8 8 7 8 9 需求量 7 8 6 7 表2.01软件运行结果; 最

14、优解如下* 起 至 销点 发点 1 2 3 4 - - - - - 1 1 0 6 0 2 6 0 0 2 3 0 8 0 1此运输问题的成本或收益为: 107注释：总需求量多出总供应量 4 第4个销地未被满足，缺少 42.2求解运输问题： 销地单价产地 b1 b2 b3 b4 产量 a1 a2 a3 3 11 3 10 1 9 2 8 7 4 10 5 7 4 9 需求量 3 6 5 6 表2.02软件运行结果：最优解如下* 起 至 销点 发点 1 2 3 4 - - - - - 1 0 0 5 2 2 3 0 0 1 3 0 6 0 3此运输问题的成本或收益为: 85此问题的另外的解如下：

15、 起 至 销点 发点 1 2 3 4 - - - - - 1 2 0 5 0 2 1 0 0 3 3 0 6 0 3此运输问题的成本或收益为: 852.3某地区有三个化肥厂，估计每年可供应本地区的数字为：化肥厂a为7万吨，b为8万吨，c为3万吨。有四个产粮区需要该化肥，需求量为：甲地区为6万吨，乙地区为6万吨，丙地区为3万吨，丁地区为3万吨。已知从各化肥厂到各产粮区的每吨化肥的运价如下表所示。 （单位：万元/万吨）产区单价化肥厂 甲 乙 丙 丁 产量 a b c 5 8 4 3 4 9 10 7 8 4 2 9 7 8 3 需求量 6 6 3 3 表2.03软件运行结果： 最优解如下* 起 至

16、 销点 发点 1 2 3 4 - - - - - 1 0 1 3 3 2 6 2 0 0 3 0 3 0 0此运输问题的成本或收益为: 833整数规划3.1求解整数规划问题： max z = 11x1+4x2s.t. 软件运行结果：*最优解如下* 目标函数最优值为 : 34 变量 最优解 - - x1 2 x2 3 约束 松弛/剩余 - - 1 3 2 0 3 3 4 2 5 3 3.2求解整数规划问题： max z =9x1+6x2+5x3软件运行结果：*最优解如下* 目标函数最优值为 : 45 变量 最优解 - - x1 3 x2 3 x3 0 约束 松弛/剩余 - - 1 2.5 2 3

17、 3 3 4 3 5 0 3.3求解01规划问题： min z =2x1+5x2+3x3+4x4s.t. 软件运行结果：*最优解如下* 目标函数最优值为 : 4 变量 最优解 - - x1 0 x2 0 x3 0 x4 1 约束 松弛/剩余 - - 1 1 2 0 3 0 3.4某公司计划用集装箱托运甲、乙两种货物，每箱的体积、净载重、可获取的利润及托运所受限制如下表。 集装箱体积和载重情况表 货 物 体积（米3/箱） 净载重（吨/箱） 利润（元/箱） 甲 5 2 2000 乙 4 5 1000 托运限制 24（米3） 13（吨）表3.01问：该公司应当如何充分利用集装箱的空间和承重来获得最大

18、的利润？设：x1,x2分别为甲、乙两种货物的托运箱数，建立模型如下：max z = 2000x1+1000x2且为整数软件运行结果：*最优解如下* 目标函数最优值为 : 9000 变量 最优解 - - x1 4 x2 1 约束 松弛/剩余 - - 1 0 2 0 3 4 4 1 4图与网络分析4.1求解下图的最小支撑树。 v1v2v5v6v3v44357864479图4.01软件运行结果： 此问题的最小生成树如下：* 起点 终点 距离 - - - 1 4 3 1 2 4 2 3 5 3 5 4 5 6 4 此问题的解为:204.2求从起点v1到终点v5的最短路。 v1v2v3v4v562148212图4.02软件运行结果： 从节点 1到节点5的最短路* 起点 终点 距离 - - - 1 3 2