管理运筹学.pptx

《管理运筹学.pptx》由会员分享，可在线阅读，更多相关《管理运筹学.pptx（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、管管 理理 运运 筹筹 学学 绪论绪论 线性规划（运输问题）线性规划（运输问题） 整数规划整数规划 动态规划动态规划 存储论存储论 排队论排队论 对策论对策论 决策分析决策分析1第一章 绪论 运筹学（运筹学（Operational Research) Operational Research) 直译为直译为“运作研究运作研究” 运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 运筹学有广泛应用 运筹学的产生和发展21 1 决策、定量分析与管理运筹学决策、定量分析与管理运筹学决策过程（问题解决的过程）：决

2、策过程（问题解决的过程）：1）提出问题：认清问题2）寻求可行方案：建模、求解3）确定评估目标及方案的标准或方法、途径4）评估各个方案：解的检验、灵敏性分析等5）选择最优方案：决策6）方案实施：回到实践中7）后评估：考察问题是否得到完满解决1）2）3）：形成问题；4）5）分析问题：定性分析与定量分析。构成决策。32 运筹学的分支运筹学的分支 线性规划 非线性规划 整数规划 图与网络模型 存储模型 排队论 排序与统筹方法 决策分析 动态规划 预测* 多目标规划、随机规划、模糊规划等43 3运筹学在工商管理中的应用运筹学在工商管理中的应用 生产计划：生产作业的计划、日程表的编排、合理下 料、配料问题

3、、物料管理等 库存管理：多种物资库存量的管理，库存方式、库存 量等 运输问题：确定最小成本的运输线路、物资的调拨、 运输工具的调度以及建厂地址的选择等 人事管理：对人员的需求和使用的预测，确定人员编 制、人员合理分配，建立人才评价体系等 市场营销：广告预算、媒介选择、定价、产品开发与 销售计划制定等 财务和会计：预测、贷款、成本分析、定价、证券管 理、现金管理等 * 设备维修、更新，项目选择、评价，工程优化设计与管理等5运筹学方法使用情况运筹学方法使用情况( (美美1983)1983)0 01010202030304040505060607070统计统计计算机模拟计算机模拟网络计划网络计划线性

4、规划线性规划排队论排队论非线性规划非线性规划动态规划动态规划对策论对策论从不使用从不使用有时使用有时使用经常使用经常使用6运筹学方法在中国使用情况运筹学方法在中国使用情况( (随机抽样随机抽样) )0 0101020203030404050506060707080809090统计统计计算机模拟计算机模拟网络计划网络计划线性规划线性规划排队论排队论非线性规划非线性规划动态规划动态规划对策论对策论从不使用从不使用有时使用有时使用经常使用经常使用7运筹学的推广应用前景运筹学的推广应用前景 据美劳工局据美劳工局19921992年统计预测年统计预测: : 运筹学应用分析人员需求从运筹学应用分析人员需求从

5、19901990年到年到20052005年的增长百分比预测为年的增长百分比预测为73%,73%,增长速度排到各项增长速度排到各项职业的前三位职业的前三位. .结论结论: : 运筹学在国内或国外的推广前景是非常广阔的运筹学在国内或国外的推广前景是非常广阔的 工商企业对运筹学应用和需求是很大的工商企业对运筹学应用和需求是很大的 在工商企业推广运筹学方面有大量的工作要做在工商企业推广运筹学方面有大量的工作要做84 4如何学习运筹学如何学习运筹学 MBA学员学习运筹学要把重点放在结合实际的应用上，不要被一些概念、理论的困难吓倒，要用好计算机这个强有力的工具。 MBA学员学习运筹学要充分发挥自己实践经验

6、丰富和理论联系实际能力强的优势。 MBA学员学习运筹学要把注意力放在“入口”和“出口”两头，中间过程尽可能让计算机软件去完成： “入口”即结合实际问题建立运筹学模型； “出口”即解决问题的方案或模型的解。 本书附有运筹学教学软件，使用方法很简单。MBA学员必须尽快学会使用这个运筹学教学软件，并借助它来学好本课程。9第二章第二章 线性规划的图解法线性规划的图解法在管理中一些典型的线性规划应用在管理中一些典型的线性规划应用 合理利用线材问题：如何下料使用材最少 配料问题：在原料供应量的限制下如何获取最大利润 投资问题：从投资项目中选取方案，使投资回报最大 产品生产计划：合理利用人力、物力、财力等，

7、使获利最大 劳动力安排：用最少的劳动力来满足工作的需要 运输问题：如何制定调运方案，使总运费最小线性规划的组成：线性规划的组成： 目标函数 Max f 或 Min f 约束条件 s.t. (subject to) 满足于 决策变量 用符号来表示可控制的因素101 1问题的提出问题的提出例例1. 某工厂在计划期内要安排甲、乙两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的限制，如下表：问题：工厂应分别生产多少单位甲、乙产品才能使工厂获利最多？甲乙资 源 限 制设 备113 0 0 台 时原 料 A214 0 0 千 克原 料 B012 5 0 千 克单 位 产 品

8、 获 利5 0 元1 0 0 元线性规划模型：线性规划模型： 目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 011线线 性性 规规 划划 模模 型型一般形式一般形式目标函数： Max （Min） z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm

9、 x1 ，x2 ， ，xn 0标准形式标准形式目标函数： Max z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0122 2 图图 解解 法法例例1.目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (

10、E)得到最优解： x1 = 50， x2 = 250 最优目标值 z = 2750013进进 一一 步步 讨讨 论论线性规划的标准化内容之一：线性规划的标准化内容之一： 引入松驰变量（含义是资源的剩余量） 例1 中引入 s1， s2， s3 模型化为 目标函数：Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3 约束条件：s.t. x1 + x2 + s1 = 300 2 x1 + x2 + s2 = 400 x2 + s3 = 250 x1 , x2 , s1 , s2 , s3 0 对于最优解 x1 =50 x2 = 250 ， s1 = 0 s2 =5

11、0 s3 = 0 说明：生产50单位甲产品和250单位乙产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。 解的性质：解的性质： 1） 线性规划的最优解如果存在，则必定有一个顶点（极点）是最优解； 2） 有的线性规划问题存在无穷多个最优解的情况； 3） 有的线性规划问题存在无有限最优解的情况，也称无解； 4） 有的线性规划问题存在无可行解的情况。作业：作业：P24-1P24-1，2 2，3 3，4 4，5 5143 3图解法的灵敏度分析图解法的灵敏度分析灵敏度分析：灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci , aij , bj 变化时

12、，对最优解产生的影响。3.1 目标函数中的系数目标函数中的系数 ci 的灵敏度分析的灵敏度分析 考虑例1的情况， ci 的变化只影响目标函数等值线的斜率， 目标函数 z = 50 x1 + 100 x2 在 z = x2 (x2 = z 斜率为0 ) 到 z = x1 + x2 (x2 = -x1 + z 斜率为 -1 )之间时， 原最优解 x1 = 50，x2 = 100 仍是最优解。一般情况： z = c1 x1 + c2 x2 写成斜截式 x2 = - (c1 / c2 ) x1 + z / c2 目标函数等值线的斜率为 - (c1 / c2 ) 当 -1 - (c1 / c2 ) 0

13、（*） 时，原最优解仍是最优解假设产品乙的利润100元不变，即 c2 = 100，代到式（*）并整理得 0 c1 100 假设产品甲的利润 50 元不变，即 c1 = 50 ，代到式（*）并整理得 50 c2 + 假若产品甲、乙的利润均改变，则可直接用式（*）来判断。假设产品甲、乙的利润分别为60元、55元，则 - 2 - (60 / 55) - 1 那麽，最优解为 z = x1 + x2 和 z = 2 x1 + x2 的交点 x1 = 100，x2 = 200 。153.2 约束条件中右边系数约束条件中右边系数 bj 的灵敏度分析的灵敏度分析当约束条件中右边系数 bj 变化时，线性规划的可

14、行域发生变化，可能引起最优解的变化。考虑例1的情况： 假设设备台时增加10个台时，即 b1变化为310，这时可行域扩大，最优解为 x2 = 250 和 x1 + x2 = 310 的交点 x1 = 60，x2 = 250 。 变化后的总利润 - 变化前的总利润 = 增加的利润 (50*60+100*250) - (50*50+100*250) = 500 ， 500 / 10 = 50 元 说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。假设原料 A 增加10 千克时，即 b2变化为410，这时可行域扩大，但最优解仍为 x2 = 250 和

15、 x1 + x2 = 300 的交点 x1 = 50，x2 = 250 。 此变化对总利润无影响，该约束条件的对偶价格为 0 。 解释：原最优解没有把原料解释：原最优解没有把原料 A 用尽，有用尽，有50千克的剩余，因此增加千克的剩余，因此增加10千克值增加了千克值增加了库存，而不会增加利润。库存，而不会增加利润。在一定范围内，当约束条件右边常数增加在一定范围内，当约束条件右边常数增加1个单位时个单位时 1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）； 2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）； 3）若约束条件的对偶价格等于0，则其最优目标函数值不

16、变。作业：作业：P24-6P24-6，7 7，8 816第三章第三章 线性规划问题的计算机求解线性规划问题的计算机求解(1)(1)管理运筹学软件1.0版使用说明：（演示例1）一、系统的进入与退出：1、在WINDOWS环境下直接运行main.exe文件，或者在DOS下UCDOS中文平台环境下运行，也可直接运行各可执行程序。2、退出系统的方法可以在主菜单中选退出项，也可按Ctrl+Break键直接退出。3、在WINDOWS环境下直接运行软件，如果出现乱码，那是因为启用了全屏幕方式，解决办法是按ALT+ENTER键， 即可转换成非全屏的界面（一般就会消除乱码，如果还是乱码，可以点击菜单的“汉”选项）

17、；若要每次启动程序都没有乱码，则需要修改屏幕设置的相应属性。具体方法是：在非全屏界面下点击菜单的“属性”选项，再选择“窗口”选项，然后选中其中的“窗口”项，并取消“启动时恢复设置”项，这样就可保证每次运行软件时以非全屏方式显示。 二、输入部分：1、线性规划、整数规划的目标函数和约束的输入必须按由小到大的序号顺序输入，同时约束变量必须放在运算 符的左侧。如（x1+x2-x3=0，不能输为x2-x3+x1=0；x1-x2+x3=0，不能输为x1+x3=x2）2、输入的约束中不包括=或或=2,则输入 X12,而不是X1=2。17第三章第三章 线性规划问题的计算机求解线性规划问题的计算机求解(2)(2

18、)结果考察：（演示例1）1、当目标函数的系数 ci 单一变化时，只要不超过其上、下限，最优解不变；2、当约束条件中右边系数 bj 变化时，当其不超过上、下限，对偶价格不变（最优解仍是原来几个线性方程的解）； 3、当有多个系数变化时，需要进一步讨论。百分之一百法则：对于所有变化的目标函数决策系数（约束条件右边常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过100%时，最优解不变（对偶价格不变，最优解仍是原来几个线性方程的解） * 允许增加量 = 上限 - 现在值 c1 的允许增加量为 100 - 50 = 50 b1 的允许增加量为 325 - 300 = 25 * 允许减少量 =

19、 现在值 - 下限 c2 的允许减少量为 100 - 50 = 50 b3 的允许减少量为 250 - 200 = 50 * 允许增加的百分比 = 增加量 / 允许增加量 * 允许减少的百分比 = 减少量 / 允许减少量 18第三章第三章 线性规划问题的计算机求解线性规划问题的计算机求解(3)(3)例：例： c1 变为 74 , c2 变为 78, 则 (74 - 50) / 50 + (100 - 78 ) / 50 = 92%，故最优解不变。 b1 变为 315 , b3 变为 240, 则 (315 - 50) / 25 + (250 - 240 ) / 50 = 80%，故对偶价格不变

20、（最优解仍是原来几个线性方程的解）。 在使用百分之一百法则进行灵敏度分析时，要注意： 1）当允许增加量（允许减少量）为无穷大时，则对任意增加量（减少量），其允许增加（减少）百分比均看作0； 2）百分之一百法则是充分条件，但非必要条件； 3）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化的情况。这种情况下，只有重新求解。19第四章第四章 线性规划在工商管理中的应用线性规划在工商管理中的应用(1)(1)一、人力资源分配的问题 例1某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司

21、机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?班 次时 间所 需 人 数16： 00 10： 0060210： 00 14： 0070314： 00 18： 0060418： 00 22： 0050522： 2： 002062： 00 6： 0030 解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 + x6 约束条件：s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4

22、,x5,x6 020第四章第四章 线性规划在工商管理中的应用线性规划在工商管理中的应用(2)(2)一、人力资源分配的问题 例2福安商场是个中型的百货商场，它对售货员的需求经过统计分析如右表： 为了保证售货人员充分休息，售货人员每周工作 5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？时间所需售货员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六28 解：设 xi ( i = 1 - 7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 +

23、 x5 + x6 + x7 约束条件：s.t. x1 + x2 + x3 + x4 + x5 28 x2 + x3 + x4 + x5 + x6 15 x3 + x4 + x5 + x6 + x7 24 x4 + x5 + x6 + x7 + x1 25 x5 + x6 + x7 + x1 + x2 19 x6 + x7 + x1 + x2 + x3 31 x7 + x1 + x2 + x3 + x4 28 x1,x2,x3,x4,x5,x6,x7 021第四章第四章 线性规划在工商管理中的应用线性规划在工商管理中的应用(3)(3)二、生产计划的问题 例3明兴公司生产甲、乙、丙三种产品，都需要

24、经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如右表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？甲乙丙资 源 限 制铸 造 工 时 (小 时 /件 )51078000机 加 工 工 时 (小 时 /件 )64812000装 配 工 时 (小 时 /件 )32210000自 产 铸 件 成 本 (元 /件 )354外 协 铸 件 成 本 (元 /件 )56-机 加 工 成 本 (元 /件 )213装 配 成 本 (元 /件 )322产 品 售 价

25、(元 /件 )231816 解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数， x4,x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。 求 xi 的利润：利润 = 售价 - 各成本之和 可得到 xi （i = 1,2,3,4,5） 的利润分别为 15、10、7、13、9 元。这样我们建立如下的数学模型。 目标函数： Max 15x1 + 10 x2 + 7x3 + 13x4 + 9x5 约束条件： s.t. 5x1 + 10 x2 + 7x3 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 3x1 + 2x2 +

26、 2x3 + 3x4 + 2x5 10000 x1,x2,x3,x4,x5 022第四章第四章 线性规划在工商管理中的应用线性规划在工商管理中的应用(4)(4)二、生产计划的问题 例4永久机械厂生产、三种产品，均要经过A、B两道工序加工。设有两种规格的设备A1、A2能完成 A 工序；有三种规格的设备B1、B2、B3能完成 B 工序。可在A、B的任何规格的设备上加工； 可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；只能在A2与B2设备上加工；数据如右上表。问：为使该厂获得最大利润，应如何制定产品加工方案？产品单件工时 设备设备的有效台时满负荷时的设备费用A15106000300A

27、2791210000321B168400050B24117000783B374000200原料（元/件）0.250.350.50售价（元/件）1.252.002.80 解：设 xijk 表示第 i 种产品，在第 j 种工序上的第 k 种设备上加工的数量。 利润 = （销售单价 - 原料单价）* 产品件数之和 - （每台时的设备费用*设备实际使用的总台时数）之和。 这样我们建立如下的数学模型: Max 0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x12

28、3 s.t. 5x111 + 10 x211 6000 （ 设备 A1 ） 7x112 + 9x212 + 12x312 10000 （ 设备 A2 ） 6x121 + 8x221 4000 （ 设备 B1 ） 4x122 + 11x322 7000 （ 设备 B2 ） 7x123 4000 （ 设备 B3 ） x111+ x112- x121- x122- x123 = 0 （产品在A、B工序加工的数量相等） x211+ x212- x221 = 0 （产品在A、B工序加工的数量相等） x312 - x322 = 0 （产品在A、B工序加工的数量相等） xijk 0 , i = 1,2,3;

29、 j = 1,2; k = 1,2,323第四章第四章 线性规划在工商管理中的应用线性规划在工商管理中的应用(5)(5)三、套裁下料问题 例5某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？解： 设计下列 5 种下料方案方案 1方案 2方案 3方案 4方案 5方案 6方案 7方案 82.9 m120101002.1 m002211301.5 m31203104合计7.47.37.27.16.66.56.36.0剩余料头00.10.20.30.80.91.11.4 设 x1,x2,x3,x4,x5 分别

30、为上面前 5 种方案下料的原材料根数。这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 约束条件： s.t. x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3 + 3x5 100 x1,x2,x3,x4,x5 024第四章第四章 线性规划在工商管理中的应用线性规划在工商管理中的应用(6)(6)四、配料问题 例6某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如右表。问：该厂应如何安排生产，使利润收入为最大？产 品 名 称规 格 要 求单 价 （ 元 /kg）甲原 材 料

31、1 不 少 于 50%， 原 材 料 2 不 超 过 25%50乙原 材 料 1 不 少 于 25%， 原 材 料 2 不 超 过 50%35丙不 限25原 材 料 名 称每 天 最 多 供 应 量单 价 （ 元 /kg）11006521002536035 解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑： 对于甲： x11，x12，x13； 对于乙： x21，x22，x23； 对于丙： x31，x32，x33； 对于原料1： x11，x21，x31； 对于原料2： x12，x22，x32； 对于原料3： x13，x23，x33； 目标函数：

32、利润最大，利润 = 收入 - 原料支出 约束条件： 规格要求 4 个； 供应量限制 3 个。25第四章第四章 线性规划在工商管理中的应用线性规划在工商管理中的应用(6(6续续) )例6（续）目标函数：Max z = -15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 约束条件： s.t. 0.5 x11-0.5 x12 -0.5 x13 0 （原材料1不少于50%） -0.25x11+0.75x12 -0.25x13 0 （原材料2不超过25%） 0.75x21-0.25x22 -0.25x23 0 （原材料1不少于25%） -0.5 x21+0.5

33、x22 -0.5 x23 0 （原材料2不超过50%） x11+ x21 + x31 100 (供应量限制） x12+ x22 + x32 100 (供应量限制） x13+ x23 + x33 60 (供应量限制） xij 0 , i = 1,2,3; j = 1,2,3 * * * * *例例7 7由学员自己看懂由学员自己看懂26第四章第四章 线性规划在工商管理中的应用线性规划在工商管理中的应用(7)(7)五、投资问题 例8某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投

34、资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元； 据测定每万元每次投资的风险指数如右表：问：问：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？项 目风 险 指 数 （ 次 /万 元 ）A1B3C4D5.5 解：解： 1 1）确定决策变量：连续投资问题 设

35、 xij ( i = 1 - 5，j = 1、2、3、4)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量： A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x2427第四章第四章 线性规划在工商管理中的应用线性规划在工商管理中的应用(7(7续续) )2 2）约束条件：）约束条件：第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是 x11+ x12 = 200；第二年：B次当年末才可收回投资故第二年年初的资金为 x11，于是 x21 + x22+ x24 = 1.1x

36、11；第三年：年初的资金为 x21+x12，于是 x31 + x32+ x33 = 1.1x21+ 1.25x12；第四年：年初的资金为 x31+x22，于是 x41 + x42 = 1.1x31+ 1.25x22；第五年：年初的资金为 x41+x32，于是 x51 = 1.1x41+ 1.25x32； B、C、D的投资限制： xi2 30 ( I =1、2、3、4 )，x33 80，x24 100 3 3）目标函数及模型：目标函数及模型：a) a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 s.t. x11+ x12 = 200 x21 + x22+

37、 x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 30 ( I =1、2、3、4 )，x33 80，x24 100 xij 0 ( i = 1、2、3、4、5；j = 1、2、3、4） b) b) Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33

38、= 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 30 ( I =1、2、3、4 )，x33 80，x24 100 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 330 xij 0 ( i = 1、2、3、4、5；j = 1、2、3、4）28第七章第七章 运运 输输 问问 题（题（1 1）1 1 运运 输输 模模 型型例例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使

39、总运输费用最小？B1B2B3产量A1646200A2655300销量150150200解：解： 产销平衡问题： 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表： B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200 Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2

40、；j = 1、2、3）29第七章第七章 运运 输输 问问 题（题（2 2）设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型： m n Min f = cij xij i = 1 j = 1 n s.t. xij = si i = 1,2,m j = 1 m xij = dj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n) 一般运输模型：一般运输模型：产销平衡 A1、 A2、 Am 表示某物资的m个产地； B1、B2、Bn 表示某物质的n个销地；si 表示产地Ai的产量； dj 表示销地Bj 的销量； cij 表示把物资为从产

41、地Ai运往销地Bj的单位运价。变化：变化： 1）有时目标函数求最大 如求利润最大或营业额最大等； 2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束； 3）产销不平衡时，可加入虚设的产地（销大于产时）或销地（产大于销时）。30第七章第七章 运运 输输 问问 题（题（3 3）2 2 运输问题的计算机求解运输问题的计算机求解例例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解解：增加一个虚设的销地运输费用为0B1B2B3产量A1646300A265530

42、0销量150150200B1B2B3B4产量A16460300A26550300销量150150200100例例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解解：增加一个虚设的产地运输费用为0B1B2B3产量A1646200A2655300销量250200200B1B2B3产量A1646200A2655300A3000150销量25020020031第七章第七章 运输问题（运输问题（4 4）3 3 运输问题的应用运输问题的应用一、产销不平衡的运输问题一、产销不平衡的运输

43、问题例例4、石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为： 由于需大于供，经院研究决定一区供应量可减少0-200吨，二区必须满足需求量，三区供应量不少于1700吨，试求总费用为最低的调运方案。一区二区三区产量山西盂县1.651.701.754000河北临城1.601.651.701500需要量300010002000解：解： 根据题意，作出产销平衡与运价表：这里 M 代表一个很大的正数，其作用是强迫相应的 x31、 x33、 x34取值为0。 一区一区二区三区

44、三区产量山西盂县1.651.651.701.751.754000河北临城1.601.601.651.701.701500假想生产点M0MM0500需要量28002001000170030032第七章第七章 运输问题（运输问题（5 5）3 3 运输问题的应用运输问题的应用一、产销不平衡的运输问题一、产销不平衡的运输问题例例5、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表： 试求总费用为最低的化肥调拨方案。1234产量A1613221750B1413191560C192023-50最低需要量3070010最高需要量507030不限解：解： 根据题意，作

45、出产销平衡与运价表： 最低要求必须满足，因此把相应的虚设产地运费取为 M ，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为 0 。对应 4”的销量 50 是考虑问题本身适当取的数据，根据产销平衡要求确定 D的产量为 50。 11”2344”产量A16161322171750B14141319151560C19192023MM50DM0M0M050销量30207030105033第七章第七章 运输问题（运输问题（6 6）3 3 运输问题的应用运输问题的应用二、生产与储存问题二、生产与储存问题例例6、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴

46、油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。生产能力（台） 单位成本（万元）一季度2510.8二季度3511.1三季度3011.0四季度1011.3解：解： 设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那末应满足： 交货：x11 = 10 生产：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34

47、 30 x14 + x24 + x34 + x44 = 20 x44 10 把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：目标函数：目标函数：Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 第一季度第二季度第三季度第四季度D产量第一季度10.8010.9511.1011.2025第二季度M11.10

48、11.2511.40035第三季度MM11.0011.15030第四季度MMM11.30010销量101525203034第七章第七章 运输问题（运输问题（7 7）3 3 运输问题的应用运输问题的应用二、生产与储存问题二、生产与储存问题例例7、光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表： 已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓储费、维护费为0.2万元。在7-8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。

49、加班生产机器每台增加成本1万元。问应如何安排1-6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？正常生产能力（台） 加班生产能力（台） 销量（台）单台费用（万元）1 月份6010104152 月份501075143 月份902011513.54 月份10040160135 月份10040103136 月份80407013.5解：解： 这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地各月生产与交货分别视为产地和销地 1）1-6月份合计生产能力（包括上年末储存量）为743台，销量为707台。设一假想销地销量为36； 2）上年末库存103台，只有仓储费和运输费，

50、把它列为的0行； 3）6月份的需求除70台销量外，还要80台库存，其需求应为70+80=150台； 4）1-6表示1-6月份正常生产情况， 1-6表示1-6月份加班生产情况。35第七章第七章 运输问题（运输问题（8 8）3 3 运输问题的应用运输问题的应用产销平衡与运价表： 1 月 2 月 3 月 4 月 5 月 6 月 虚销地 正常产量 加班产量 0 0.3 0.5 0.7 0.9 1.1 1.3 0 103 1 15 15.3 15.5 15.7 15.9 16.1 0 60 1 16 16.3 16.5 16.7 6.9 17.1 0 10 2 M 14 14.3 14.5 14.7 1