管理运筹学-1

null管 理 运 筹 学管 理 运 筹 学 绪论 线性规划（运输问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ） 整数规划 动态规划 存储论 排队论 对策论 决策分析第一章 绪论第一章 绪论 运筹学（Operational Research) 直译为“运作研究” 运筹学是应用分析、试验、量化的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，以实现最有效的管理。 运筹学有广泛应用 运筹学的产生和发展§1 决策、定量分析与管理运筹学§1 决策、定量分析与管理运筹学决策过程（问题解决的过程）： 1）提出问题：认清问题 2）寻求可行方案：建模、求解 3）确定评估目标及方案的标准或方法、途径 4）评估各个方案：解的检验、灵敏性分析等 5）选择最优方案：决策 6）方案实施：回到实践中 7）后评估：考察问题是否得到完满解决 1）2）3）：形成问题；4）5）分析问题：定性分析与定量分析。构成决策。§2 运筹学的分支§2 运筹学的分支线性规划 非线性规划 整数规划 图与网络模型 存储模型排队论 排序与统筹方法 决策分析 动态规划 预测 *** 多目标规划、随机规划、模糊规划等§3运筹学在工商管理中的应用§3运筹学在工商管理中的应用生产 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 ：生产作业的计划、日程表的编排、合理下 料、配料问题、物料管理等 库存管理：多种物资库存量的管理，库存方式、库存 量等 运输问题：确定最小成本的运输线路、物资的调拨、 运输工具的调度以及建厂地址的选择等 人事管理：对人员的需求和使用的预测，确定人员编 制、人员合理分配，建立人才评价体系等 市场营销：广告预算、媒介选择、定价、产品开发与 销售计划制定等 财务和会计：预测、贷款、成本分析、定价、证券管 理、现金管理等 *** 设备维修、更新，项目选择、评价，工程优化设计与管理等 运筹学方法使用情况(美1983)运筹学方法使用情况(美1983)运筹学方法在中国使用情况(随机抽样)运筹学方法在中国使用情况(随机抽样)运筹学的推广应用前景运筹学的推广应用前景据美劳工局1992年统计预测: 运筹学应用分析人员需求从1990年到2005年的增长百分比预测为73%,增长速度排到各项职业的前三位. 结论: 运筹学在国内或国外的推广前景是非常广阔的 工商企业对运筹学应用和需求是很大的 在工商企业推广运筹学方面有大量的工作要做 §4如何学习运筹学§4如何学习运筹学MBA学员学习运筹学要把重点放在结合实际的应用上，不要被一些概念、理论的困难吓倒，要用好计算机这个强有力的工具。 MBA学员学习运筹学要充分发挥自己实践经验丰富和理论联系实际能力强的优势。 MBA学员学习运筹学要把注意力放在“入口”和“出口”两头，中间过程尽可能让计算机软件去完成： “入口”即结合实际问题建立运筹学模型； “出口”即解决问题的方案或模型的解。 本书附有运筹学教学软件，使用方法很简单。MBA学员必须尽快学会使用这个运筹学教学软件，并借助它来学好本课程。 第二章 线性规划的图解法第二章 线性规划的图解法在管理中一些典型的线性规划应用 合理利用线材问题：如何下料使用材最少 配料问题：在原料供应量的限制下如何获取最大利润 投资问题：从投资项目中选取方案，使投资回报最大 产品生产计划：合理利用人力、物力、财力等，使获利最大 劳动力安排：用最少的劳动力来满足工作的需要 运输问题：如何制定调运方案，使总运费最小 线性规划的组成： 目标函数 Max f 或 Min f 约束条件 s.t. (subject to) 满足于 决策变量 用符号来表示可控制的因素§1问题的提出§1问题的提出例1. 某工厂在计划期内要安排甲、乙两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的限制，如下表： 问题：工厂应分别生产多少单位甲、乙产品才能使工厂获利最多？线性规划模型： 目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 ≤ 300 2 x1 + x2 ≤ 400 x2 ≤ 250 x1 , x2 ≥ 0 线 性 规 划 模 型线 性 规 划 模 型一般形式 目标函数： 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 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 ≥ 0 §2 图 解 法§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 (E) 得到最优解： x1 = 50， x2 = 250 最优目标值 z = 27500 进 一 步 讨 论进 一 步 讨 论线性规划的标准化内容之一： —— 引入松驰变量（含义是资源的剩余量） 例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 =50 s3 = 0 说明：生产50单位甲产品和250单位乙产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。 解的性质： 1） 线性规划的最优解如果存在，则必定有一个顶点（极点）是最优解； 2） 有的线性规划问题存在无穷多个最优解的情况； 3） 有的线性规划问题存在无有限最优解的情况，也称无解； 4） 有的线性规划问题存在无可行解的情况。 作业：P24---1，2，3，4，5§3图解法的灵敏度分析§3图解法的灵敏度分析灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci , aij , bj 变化时，对最优解产生的影响。 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 （*） 时，原最优解仍是最优解 假设产品乙的利润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 。3.2 约束条件中右边系数 bj 的灵敏度分析3.2 约束条件中右边系数 bj 的灵敏度分析当约束条件中右边系数 bj 变化时，线性规划的可行域发生变化，可能引起最优解的变化。 考虑例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 和 x1 + x2 = 300 的交点 x1 = 50，x2 = 250 。 此变化对总利润无影响，该约束条件的对偶价格为 0 。 解释：原最优解没有把原料 A 用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。 在一定范围内，当约束条件右边常数增加1个单位时 1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）； 2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）； 3）若约束条件的对偶价格等于0，则其最优目标函数值不变。 作业：P24---6，7，8第三章 线性规划问题的计算机求解(1)第三章 线性规划问题的计算机求解(1)管理运筹学软件1.0版使用说明：（演示例1） 一、系统的进入与退出： 1、在WINDOWS环境下直接运行main.exe文件，或者在DOS下UCDOS中文平台环境下运行，也可直接运行各可执行程序。 2、退出系统的方法可以在主菜单中选退出项，也可按Ctrl+Break键直接退出。 3、在WINDOWS环境下直接运行软件，如果出现乱码，那是因为启用了全屏幕方式，解决办法是按ALT+ENTER键， 即可转换成非全屏的界面（一般就会消除乱码，如果还是乱码，可以点击菜单的“汉”选项）；若要每次启动程序都没有乱码，则需要修改屏幕设置的相应属性。具体方法是：在非全屏界面下点击菜单的“属性”选项，再选择“窗口”选项，然后选中其中的“窗口”项，并取消“启动时恢复设置”项，这样就可保证每次运行软件时以非全屏方式显示。 二、输入部分： 1、线性规划、整数规划的目标函数和约束的输入必须按由小到大的序号顺序输入，同时约束变量必须放在运算 符的左侧。如（x1+x2-x3=0，不能输为x2-x3+x1=0；x1-x2+x3=0，不能输为x1+x3=x2） 2、输入的约束中不包括">="或"<="，而是用">"或"<"代替，这不会影响求解。如 对于约束X1>=2,则输入 X1>2,而不是X1>=2。第三章 线性规划问题的计算机求解(2)第三章 线性规划问题的计算机求解(2)结果考察：（演示例1） 1、当目标函数的系数 ci 单一变化时，只要不超过其上、下限，最优解不变； 2、当约束条件中右边系数 bj 变化时，当其不超过上、下限，对偶价格不变（最优解仍是原来几个线性方程的解）； 3、当有多个系数变化时，需要进一步讨论。 百分之一百法则：对于所有变化的目标函数决策系数（约束条件右边常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过100%时，最优解不变（对偶价格不变，最优解仍是原来几个线性方程的解） * 允许增加量 = 上限 - 现在值 c1 的允许增加量为 100 - 50 = 50 b1 的允许增加量为 325 - 300 = 25 * 允许减少量 = 现在值 - 下限 c2 的允许减少量为 100 - 50 = 50 b3 的允许减少量为 250 - 200 = 50 * 允许增加的百分比 = 增加量 / 允许增加量 * 允许减少的百分比 = 减少量 / 允许减少量 第三章 线性规划问题的计算机求解(3)第三章 线性规划问题的计算机求解(3)例： c1 变为 74 , c2 变为 78, 则 (74 - 50) / 50 + (100 - 78 ) / 50 = 92%，故最优解不变。 b1 变为 315 , b3 变为 240, 则 (315 - 50) / 25 + (250 - 240 ) / 50 = 80%，故对偶价格不变（最优解仍是原来几个线性方程的解）。 在使用百分之一百法则进行灵敏度分析时，要注意： 1）当允许增加量（允许减少量）为无穷大时，则对任意增加量（减少量），其允许增加（减少）百分比均看作0； 2）百分之一百法则是充分条件，但非必要条件； 3）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化的情况。这种情况下，只有重新求解。第四章 线性规划在工商管理中的应用(1)第四章 线性规划在工商管理中的应用(1)一、人力资源分配的问题 例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员? 解：设 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,x5,x6 ≥ 0第四章 线性规划在工商管理中的应用(2)第四章 线性规划在工商管理中的应用(2)一、人力资源分配的问题 例2．福安商场是个中型的百货商场，它 对售货员的需求经过统计分析如右表： 为了保证售货人员充分休息，售货人员 每周工作 5天，休息两天，并要求休息的两 天是连续的。问应该如何安排售货人员的作 息，既满足工作需要，又使配备的售货人员 的人数最少？ 解：设 xi ( i = 1 - 7)表示星期一至日开始休息的人数,这样我们建立如下的 数学模型。 目标函数： Min x1 + x2 + x3 + x4 + 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 ≥ 0第四章 线性规划在工商管理中的应用(3)第四章 线性规划在工商管理中的应用(3)二、生产计划的问题 例3．明兴公司生产甲、乙、 丙三种产品，都需要经过铸造、 机加工和装配三个车间。甲、乙 两种产品的铸件可以外包协作， 亦可以自行生产，但产品丙必须 本厂铸造才能保证质量。数据如 右表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？ 解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数， x4,x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。 求 xi 的利润：利润 = 售价 - 各成本之和 可得到 xi （i = 1,2,3,4,5） 的利润分别为 15、10、7、13、9 元。 这样我们建立如下的数学模型。 目标函数： Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5 约束条件： s.t. 5x1 + 10x2 + 7x3 ≤ 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 ≤ 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000 x1,x2,x3,x4,x5 ≥ 0第四章 线性规划在工商管理中的应用(4)第四章 线性规划在工商管理中的应用(4)二、生产计划的问题 例4．永久机械厂生产Ⅰ、Ⅱ、 Ⅲ三种产品，均要经过A、B两道工 序加工。设有两种规格的设备A1、A2 能完成 A 工序；有三种规格的设备 B1、B2、B3能完成 B 工序。Ⅰ可在A、 B的任何规格的设备上加工；Ⅱ 可在 任意规格的A设备上加工，但对B工序， 只能在B1设备上加工；Ⅲ只能在A2与B2设备上加工；数据如右上表。问：为使该厂获得最大利润，应如何制定产品加工方案？ 解：设 xijk 表示第 i 种产品，在第 j 种工序上的第 k 种设备上加工的数量。 利润 = [（销售单价 - 原料单价）* 产品件数]之和 - （每台时的设备费用*设备实际使用的总台时数）之和。 这样我们建立如下的数学模型: Max 0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123 s.t. 5x111 + 10x211 ≤ 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; j = 1,2; k = 1,2,3第四章 线性规划在工商管理中的应用(5)第四章 线性规划在工商管理中的应用(5)三、套裁下料问题 例5．某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？ 解： 设计下列 5 种下料方案 设 x1,x2,x3,x4,x5 分别为上面前 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 ≥ 0 第四章 线性规划在工商管理中的应用(6)第四章 线性规划在工商管理中的应用(6)四、配料问题 例6．某工厂要用三种原料1、 2、3混合调配出三种不同规格的 产品甲、乙、丙，数据如右表。 问：该厂应如何安排生产，使利 润收入为最大？ 解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑： 对于甲： x11，x12，x13； 对于乙： x21，x22，x23； 对于丙： x31，x32，x33； 对于原料1： x11，x21，x31； 对于原料2： x12，x22，x32； 对于原料3： x13，x23，x33； 目标函数： 利润最大，利润 = 收入 - 原料支出 约束条件： 规格要求 4 个； 供应量限制 3 个。第四章 线性规划在工商管理中的应用(6续)第四章 线性规划在工商管理中的应用(6续)例6．（续） 目标函数：Max z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33 约束条件： 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 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)第四章 线性规划在工商管理中的应用(7)五、投资问题 例8．某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项 目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第 一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额 不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规 定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本 利155%，但规定最大投资额不能超过100万元； 据测定每万元每次投资的风险指数如右表： 问： a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？ b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？ 解： 1）确定决策变量：连续投资问题 设 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 x24第四章 线性规划在工商管理中的应用(7续)第四章 线性规划在工商管理中的应用(7续)2）约束条件： 第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是 x11+ x12 = 200； 第二年：B次当年末才可收回投资故第二年年初的资金为 x11，于是 x21 + x22+ x24 = 1.1x11； 第三年：年初的资金为 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）目标函数及模型： a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 s.t. x11+ x12 = 200 x21 + x22+ 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) 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 = 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）第七章 运 输 问 题（1）第七章 运 输 问 题（1）§1 运 输 模 型 例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解： 产销平衡问题： 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表： 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；j = 1、2、3）第七章 运 输 问 题（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 表示把物资为从产地Ai运往销地Bj的单位运价。变化： 1）有时目标函数求最大 如求利润最大或营业额最大等； 2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束； 3）产销不平衡时，可加入虚设的产地（销大于产时）或销地（产大于销时）。第七章 运 输 问 题（3）第七章 运 输 问 题（3）§2 运输问题的计算机求解 例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 解：增加一个 虚设的销地 运输费用为0例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 解：增加一个 虚设的产地 运输费用为0第七章 运输问题（4）§3 运输问题的应用第七章 运输问题（4）§3 运输问题的应用一、产销不平衡的运输问题 例4、石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为： 由于需大于供，经院研究决定一区供应量可减少0--200吨，二区必须满足需求量，三区供应量不少于1700吨，试求总费用为最低的调运方案。解： 根据题意，作出产销平衡与运价表： 这里 M 代表一个很大的正数，其作用是强迫相应的 x31、 x33、 x34取值为0。 第七章 运输问题（5）§3 运输问题的应用第七章 运输问题（5）§3 运输问题的应用一、产销不平衡的运输问题 例5、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表： 试求总费用为最低的化肥调拨方案。解： 根据题意，作出产销平衡与运价表： 最低要求必须满足，因此把相应的虚设产地运费取为 M ，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为 0 。对应 4”的销量 50 是考虑问题本身适当取的数据，根据产销平衡要求确定 D的产量为 50。 第七章 运输问题（6）§3 运输问题的应用第七章 运输问题（6）§3 运输问题的应用二、生产与储存问题 例6、某厂按合同规定须于当年每个季度末分 别提供10、15、25、20台同一规格的柴油机。 已知该厂各季度的生产能力及生产每台柴油机 的成本如右表。如果生产出来的柴油机当季不 交货，每台每积压一个季度需储存、维护等费 用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。解： 设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那末应满足： 交货：x11 = 10 生产：x11 + x12 + x13 + x14 ≤ 25 x12 + x22 = 15 x22 + x23 + x24 ≤ 35 x13 + x23 + x33 = 25 x33 + x34 ≤ 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 第七章 运输问题（7）§3 运输问题的应用第七章 运输问题（7）§3 运输问题的应用二、生产与储存问题 例7、光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表： 已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓储费、维护费为0.2万元。在7--8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1--6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？解： 这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地 1）1--6月份合计生产能力（包括上年末储存量）为743台，销量为707台。设一假想销地销量为36； 2）上年末库存103台，只有仓储费和运输费，把它列为的0行； 3）6月份的需求除70台销量外，还要80台库存，其需求应为70+80=150台； 4）1--6表示1--6月份正常生产情况， 1’--6’表示1--6月份加班生产情况。第七章 运输问题（8）§3 运输问题的应用第七章 运输问题（8）§3 运输问题的应用产销平衡与运价表：第七章 运 输 问 题（9）第七章 运 输 问 题（9）例8、腾飞电子仪器公司在大连和广州有两个分 厂生产同一种仪器，大连分厂每月生产450台， 广州分厂每月生产600台。该公司在上海和天津 有两个销售公司负责对南京、济南、南昌、青岛 四个城市的仪器供应。另外因为大连距离青岛较 近，公司同意大连分厂向青岛直接供货，运输费 用如下图，单位是百元。问应该如何调运仪器， 可使总运输费用最低？图中 1- 广州、2 - 大连、 3 - 上海、4 - 天津、5 - 南京、6 - 济南、7 - 南昌、8 - 青岛 三、转运问题： 在原运输问题上增加若干转运站。运输方式有：产地  转运站、转运站  销地、产地  产地、产地  销地、销地  转运站、销地  产地等。解：设 xij 为从 i 到 j 的运输量，可得到有下列特点的线性规划模型： 目标函数：Min f = 所有可能的运输费用（运输单价与运输量乘积之和） 约束条件： 对产地（发点） i ：输出量 - 输入量 = 产量 对转运站（中转点）：输入量 - 输出量 = 0 对销地（收点） j ：输入量 - 输出量 = 销量第七章 运 输 问 题（10）第七章 运 输 问 题（10）例8．（续） 目标函数： Min f = 2x13+ 3x14+ 3x23+ x24+ 4x28 + 2x35+ 6x36+ 3x37+ 6x38+ 4x45+ 4x46+ 6x47+ 5x48 约束条件： s.t. x13+ x14 ≤ 600 (广州分厂供应量限制） x23+ x24+ x28 ≤ 450 (大连分厂供应量限制） -x13- x23 + x35 + x36+ x37 + x38 = 0 （上海销售公司，转运站） -x14- x24 + x45 + x46+ x47 + x48 = 0 （天津销售公司，转运站） x35+ x45 = 200 （南京的销量） x36+ x46 = 150 （济南的销量） x37+ x47 = 350 （南昌的销量） x38+ x48 + x28 = 300 （青岛的销量） xij ≥ 0 , i,j = 1,2,3,4,5,6,7,8用“管理运筹学”软件求得结果： x13 = 550 x14 = 0 ； x23 = 0 x24 = 150 x28 = 300 ； x35 = 200 x36 = 0 x37 = 350 x38 = 0 ； x45 = 0 x46 = 150 x47 = 0 x48 = 0 。第七章 运输问题（11）第七章 运输问题（11）例9、某公司有A1、 A2、 A3三个分厂生产某种物质，分别供应B1、 B2、 B3、 B4四个地区的销售公司销售。假设质量相同，有关数 据如右表： 试求总费用为最少的调 运方案。 假设：1、每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运； 2、运往各销地的物资可以先运给其中几个销地，再转运给其他销地； 3、除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。 运价如下表：第七章 运输问题（12）第七章 运输问题（12）解：把此转运问题转化为一般运输问题： 1、把所有产地、销地、转运站都同时看作产地和销地； 2、运输表中不可能方案的运费取作M，自身对自身的运费为0； 3、产量及销量可定为：中转站 流量+20=20，产地 产量+20，销地 销量+20。20为各点可能变化的最大流量； 4、对于最优方案，其中 xi i 为自身对自身的运量，实际上不进行运作。 扩大的运输问题产销平衡表：