管理运筹学全套课件

管管 理理 运运 筹筹 学学数学的魅力与实质数学的魅力与实质n数学的本质是处理抽象对象，是比语言更精炼、更严谨的符号系统。是人类理性的集中体现。n数学的方法是建立一个牢不可破的公理体系，并以演绎推理的方法去构建和扩展整个学科体系。n数学数学分支分支n数学数学分支分支n数学数学分支分支n应用应用 n演绎方法演绎方法 n公理体系公理体系数学大厦数学大厦数学的魅力与实质数学的魅力与实质n数学方法在自然科学体系中无处不在，并取得了光辉的成就。n19世纪以后，数学被广泛深入地应用于社会科学领域。n经济学、管理学领域的许多大师具有高超的数学技能。数学的魅力与实质数学的魅力与实质n本门课程不仅要学习一门课程，一套方法，更重要的是要学会理性分析问题的方法。n培养逻辑思维能力和抽象思维能力。n数学在发展的过程中遇到过许多问题，而且也并非确切无疑，大家要敢于质疑，敢于提问题。数学的魅力与实质数学的魅力与实质n一个例子：S=1-1+1-1+1n请问S等于多少？数学的魅力与实质数学的魅力与实质n至少有三种解法：1、S=（1-1）+（1-1）+（1-1）2、S=1+（-1+1）+（-1+1）3、1-S=1-(1-1+1-1)=1-1+1-1+1-1=S 得到2S=1，从而S=1/2。数学的魅力与实质数学的魅力与实质n事实上，这是一个争论未定的题目，反映了人类对自然认识的不足。n无穷的概念存在许多不足之处，而且并非绝对精确。不同的学派对无穷有着不同的认识。考核方法考核方法n平时成绩占20%，每位同学的初始成绩都是60分（按100分为满分计算）。n每次作业交上加1分，不交不加不减，拷贝别人作业一次扣2分。n上课主动回答问题每次加2分。n提出有价值问题或发现老师错误每次加5分。运筹学的体系和发展历史运筹学的体系和发展历史n定义定义n运筹学是一门应用于管理有组织系统的科学运筹学是一门应用于管理有组织系统的科学n它为掌管这类系统的人提供决策目标和数量分析的它为掌管这类系统的人提供决策目标和数量分析的工具工具n运筹学应用分析、实验、量化的方法，对经济管理运筹学应用分析、实验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理策者提供有依据的最优方案，以实现最有效的管理n正式起源与二次世界大战，被称为正式起源与二次世界大战，被称为Operations Operations research,research,日本人翻译为运做学，台湾人翻译为作业研日本人翻译为运做学，台湾人翻译为作业研究究运筹学的体系和发展历史运筹学的体系和发展历史n田忌赛马田忌赛马n萌芽在萌芽在20世纪初，世纪初，Lanchester战斗方战斗方程。丹麦工程师爱尔朗研究电话通讯系程。丹麦工程师爱尔朗研究电话通讯系统时提出了一些排队论的公式。统时提出了一些排队论的公式。n30年代，数学家列温逊运用运筹思想分年代，数学家列温逊运用运筹思想分析商业广告、顾客心理。析商业广告、顾客心理。运筹学的体系和发展历史运筹学的体系和发展历史n二次世界大战中，英美科学家研究如何有效运用雷达，研究船队遇到袭击如何减少损失，以及如何使用深水炸弹等紧迫问题。n应用：德国潜艇被摧毁数增加到400%，船只中弹数由47%减少到29%。n结果：打赢了空战和海战，保证了二次世界大战的最终胜利。运筹学在现实生活中的例子运筹学在现实生活中的例子n企业安排生产计划n库存管理n公交系统优化n食堂窗口设置n电脑游戏，帝国时代、魔兽争霸等。运筹学的学科体系运筹学的学科体系n规划论：包括线性规划、非线性规划、整数规划等。1947年，Danzig提出单纯形法，随后规划方法得到了广泛的应用。n图论与网络分析：图是研究离散事物之间关系的一种分析模型。例：有甲、乙、丙、丁、戊、己6名同学参加ABCDEF六个项目的比赛，下表是各运动员报名参赛的项目，问6个项目顺序如何安排，作到每名运动员不连续参加两项比赛。运筹学的学科体系运筹学的学科体系A AB BC CD DEF F甲*乙*丙*丁*戊*己*运筹学的学科体系运筹学的学科体系n排队论：研究公共服务系统的运行与优化的数学理论方法。n决策论：研究不确定情况以及风险情况下的决策。n存储论：研究企业的库存计划，进货周期等。n博弈论：研究竞争环境下决策者行为的数学方法。运筹学的工作步骤运筹学的工作步骤n提出和形成问题：弄清问题的目标，可能的约束，问题的可控变量，相关参数等。n建立模型：把问题中的可控变量、参数、目标、约束之间的关系用一定的模型表示出来。n求解：用计算或实验方法求出问题的解。n解的检验：检查求解过程，检查解能否反映现实问题。n解的实施：将解运用到实际问题中。第一章第一章 线性规划线性规划本章内容本章内容n线性规划模型线性规划模型n线性规划问题的图解法线性规划问题的图解法n单纯形法单纯形法n非标准形线性规划的解法非标准形线性规划的解法线性规划模型线性规划模型n规划问题：就是否合理利用有限资源的问题。n线性规划：线性的规划问题。两个意思：1、目标函数是线性的 2、约束条件是线性的 线性规划模型线性规划模型n生产决策问题n某汽车工厂生产大轿车和载重汽车两种型号的汽车,已知每辆汽车所用的钢材都是2吨/辆，该工厂每年供应的钢材为1600吨；工厂的生产能力是每2.5小时可生产一辆载重汽车，每5小时可生产一辆大轿车，工厂全年的有效工时为2500小时；已知供应给该厂大轿车用的座椅每年可装配400辆。据市场调查，出售一辆大轿车可获利4000元，出售一辆载重汽车可获利3000元。如何安排生产才能使工厂获利最大？线性规划模型线性规划模型n建模型如下：设大轿车数量为x1,载重汽车数量为x2。0,40025005.25160022.34max211212121xxxxxxxtsxxzs.t.是subject to 的简写，表示受限制于。线性规划模型线性规划模型n某工厂在计划期间内生产某工厂在计划期间内生产 、两种产品，已知生两种产品，已知生产单位产品所需的设备台时及产单位产品所需的设备台时及A A、B B两种原材料的消两种原材料的消耗，如下表所示：耗，如下表所示：设备设备1 11 1300300台时台时原料原料A A2 21 1400400KgKg原料原料B B0 01 1250250KgKg已知已知 、两种产品每单位分别可以获利两种产品每单位分别可以获利5050元、元、100100元，问工厂应该如何安排生产才能使工厂获利最多。元，问工厂应该如何安排生产才能使工厂获利最多。线性规划模型线性规划模型n设置变量：生产 产品x1个，产品x2个n目标函数是利润最大化：n资源是有限的，第一个限制是设备台时的限制：2110050maxxxz30021 xx线性规划模型线性规划模型n第二个限制是原材料A的限制：n第三个限制是原材料B的限制：n显然，产量不可能为负数：400221 xx2502x0,21xx线性规划模型线性规划模型n建模型如下：设生产 产品x1件,产品x2件。)2(0,2504002300.)1(10050max212212121xxxxxxxtsxxz线性规划模型线性规划模型n（1），（2）分别被称为目标函数和约束条件。目标函数中变量的系数被称为价值系数，约束条件不等号右端称为资源向量或限定系数，约束条件左端变量的系数被称为技术系数。n目标函数和约束条件都是一次幂函数，或称线性函数，因此这类规划问题被称为线性规划问题。线性规划模型线性规划模型n例3：生产卷烟的主要原材料包括烟叶和烟梗。国家规定每千克焦油含量不超过15mg，烟气烟碱含量不超过1.4mg，现在知道每千克烟叶含焦油12mg，烟气烟碱1.5mg，烟梗含焦油18mg，烟气烟碱0.3mg，烟叶每千克50元，烟梗每千克20元，问如何搭配使生产成本最小。线性规划模型线性规划模型n设每千克卷烟用烟叶设每千克卷烟用烟叶x1x1千克，烟梗千克，烟梗x2x2千克，模千克，模型如下：型如下：)2(0,14.13.05.1151812.2050min2121212121xxxxxxxxtsxxf这是目标函数一个求最小化的问题。线性规划的标准形线性规划的标准形n为求解方便，一般线性规划都可以转化成如下标准形式：),2,1(0.max221122222121112121112211njxbxaxaxabxaxaxabxaxaxatsxcxcxczjmnmnmmnnnnnn要求).2,1(0mibi线性规划的标准形线性规划的标准形n目标函数为求最小化时，等式两端同乘以-1，变为求最大化。n约束条件为=时，减一个剩余变量。n资源变量为负数时，等式两端同乘以-1。n变量为0b0即可。n如果bk的变化使得B-1 b+b+B-1 b0b0，这时最优解的基就要发生变化，这种情况下用对偶单纯形法继续求出新的最优解。资源向量的灵敏度分析资源向量的灵敏度分析n例：课本P6例1-1中，如果钢材的供应数量发生变化，请问n1、钢材供应量在什么范围内变化时，最优基不会发生改变？n2、当钢材的供应量增加到2200吨时，应当如何安排生产计划？资源向量的灵敏度分析资源向量的灵敏度分析n如果例1-1中的钢材供应数量变为1600+b1，最终解将变为：x xB B=B-1 b=b=B-1(b+bb+b）=004002500160004.05.004.0114.05.01b15.015.0200600200b资源向量的灵敏度分析资源向量的灵敏度分析n要保证最优基不改变，要求b中所有向量大于等于0，即：n从（1）式中可得：b1-400，从（2）式中可得：b1-600，从（3）式中可得：b1400，得到-400 b1400，也就是说，钢材供应量在1200到2000之间时，最优基不发生变化。)3(05.0200)2(0600)1(05.0200111bbb资源向量的灵敏度分析资源向量的灵敏度分析n资源向量在一定范围内变化时，最优基虽然不会发生变化，但最优解则会发生变化。n最优基不变时，可以直接将发生变化的资源向量代入B-1 bb中，得到新的最优解的值。n例如，当钢材供应量变为2000时，新的最优解的求解如下：资源向量的灵敏度分析资源向量的灵敏度分析千元。为套，利润辆，剩余座椅载重汽车产大轿车，生产最优生产方案为：不生3000400100030001000*3)400,0,0,1000,0(010004004002500200004.05.004.0114.05.0ZXxB资源向量的灵敏度分析资源向量的灵敏度分析n当钢材的供应量增加到2200吨时：n资源向量出现负数，不再是可行解，需要继续迭代，用对偶单纯形法。10010005004002500220004.05.004.0114.05.0Bx资源向量的灵敏度分析资源向量的灵敏度分析n最终单纯形表变为：x1 x2 x3 x4 x5x Cj430125xxx1001200500 zj 0 0 1 0.4 0 zj-cj 4 3 1 0.4 0 4 3 0 0 0 0 0 0.5 -0.4 1 0 1 1 -0.4 0 1 0 -0.5 0.4 0b3200资源向量的灵敏度分析资源向量的灵敏度分析n以主元素为中心进行迭代运算：x1 x2 x3 x4 x5x Cj030325xxx2001000400 zj 2 0 0 1.2 0 zj-cj 6 3 2 1.2 0 4 3 0 0 0 1 0 0 0 1 2 1 0 0.4 0-2 0 1 -0.8 0b3000趣味数学趣味数学n一个富有的律师拥有11辆古董汽车，每辆值5000美元。律师死时留下了一个奇怪的遗嘱。他说他的11辆古董汽车分给他的三个儿子。把其中的一半分给长子，1/4分给次子，1/6分给小儿子。同时规定不能把车卖掉。n律师去世后，儿子为了这个遗嘱争论不休，这时一个数学家开了一辆汽车来悼念老朋友。n三个儿子把他们的难题告诉了数学家，数学家沉思片刻后说，我有办法了。请问，他该怎么分配这些汽车？约束方程系数矩阵的灵敏度分析约束方程系数矩阵的灵敏度分析n从前边的分析中，我们知道，单纯形法的实质是找到一个能得到最优解的基x xB B，在约束条件中用其系数矩阵左乘一个B-1，同时令非基变量为0，得到最优解向量x xB B=B-1 b b。n从而我们可以得到如下结论，最终单纯形表中x xi i的系数列向量p pi i 事实上就是其初始系数列向量p pi i左乘以B-1，既p pi i=B-1 p pi i。n根据以上分析，我们可以得到约束方程技术系数变化时灵敏度分析的方法。约束方程系数矩阵的灵敏度分析约束方程系数矩阵的灵敏度分析n例如，在例1-1中，列向量x x4 4的系数列向量(用p p4 4表示）在最终单纯形表中为（用p p4 4表示）：4.04.04.001004.05.004.0114.05.0414pBp约束方程系数矩阵的灵敏度分析约束方程系数矩阵的灵敏度分析n根据以上分析我们可以得到系数矩阵灵敏度分析的思路。n当基变量系数列向量改变时，用初始系数列向量左乘以B-1 后代入原最终单纯形表，在新的单纯形表中继续进行运算，得到最优解。n当新加入决策变量时，意味着约束方程组中增加了列向量，将这个列向量左乘以B-1 后添加到原最终单纯形表中，继续运算得到最优解。约束方程系数矩阵的灵敏度分析约束方程系数矩阵的灵敏度分析n在例1-1，为了增加安全性，当每辆大轿车使用钢材由2吨变为3吨时，求最优解有什么变化？n工厂具备了生产旅行车的技术，每辆旅行车用钢材1.5吨，工时1.25小时，座椅0.25套，利润为每辆3千元，问该不该投产，如果投产有利可图，应该如何安排新的生产计划？约束方程系数矩阵的灵敏度分析约束方程系数矩阵的灵敏度分析n当大轿车使用钢材变为3吨时，x1在最终单纯形表中的系数列向量变为：5.015.015304.05.004.0114.05.0111pBp约束方程系数矩阵的灵敏度分析约束方程系数矩阵的灵敏度分析n最终单纯形表变为：x1 x2 x3 x4 x5x Cj430125xxx200600200 zj zj-cj 4 3 0 0 0 0.5 0 0.5 -0.4 1 1 1 1 -0.4 00.5 0 -0.5 0.4 0b约束方程系数矩阵的灵敏度分析约束方程系数矩阵的灵敏度分析n由于x1对应的列向量尚未化为单位向量，先进行迭代运算：x1 x2 x3 x4 x5x Cj430125xxx4002000 zj 0 0 2 -0.4 0 zj-cj 4 3 0 0 0 0 0 1 -0.8 1 0 1 2 -1.2 0 1 0 -1 0.8 0b 4 3 2 -0.4 05001800约束方程系数矩阵的灵敏度分析约束方程系数矩阵的灵敏度分析n检验数仍然有负数，继续迭代：x1 x2 x3 x4 x5x Cj030425xxx500800400 zj 0.5 0 1.5 0 0 zj-cj 4 3 0 0 0 1 0 1 0 1 1.5 1 0.5 0 0 1.25 0 -1.25 1 0b 4.5 3 1.5 0 02400约束方程系数矩阵的灵敏度分析约束方程系数矩阵的灵敏度分析n第二问，新增加一种产品，模型中增加了一个新列，设新产品产量为x6，增加的系数列向量在最终单纯形表中变为：25.015.025.025.15.104.05.004.0114.05.0616pBp约束方程系数矩阵的灵敏度分析约束方程系数矩阵的灵敏度分析n最终单纯形表变为：x1 x2 x3 x4 x5 x6 x Cj430125xxx200600200 zj 0 0 1 0.4 0 -1 zj-cj 4 3 0 0 0 3 0 0 1 -0.4 1 0.5 0 1 0.5 -0.4 0 1 1 0 -0.5 0.4 0 -0.25b 4 3 1 0.4 0 26004002600约束方程系数矩阵的灵敏度分析约束方程系数矩阵的灵敏度分析n检验数中存在负数，继续迭代：x1 x2 x3 x4 x5 x6 x Cj433126xxx300200400 zj 0 0 2 -0.4 2 0 zj-cj 4 3 0 0 0 3 0 0 1 -0.8 2 1 0 1 0 0.4 -2 0 1 0 -0.25 0.2 0.5 0b 4 3 2 -0.4 2 315005003000约束方程系数矩阵的灵敏度分析约束方程系数矩阵的灵敏度分析n仍不是最优解，继续运算：x1 x2 x3 x4 x5 x6 x Cj403146xxx200500800 zj 0 1 2 0 0 0 zj-cj 4 3 0 0 0 3 0 2 1 0 -2 1 0 2.5 0 1 -5 0 1 -0.5 -0.25 0 1.5 0b 4 4 2 0 0 33200约束方程系数矩阵的灵敏度分析约束方程系数矩阵的灵敏度分析n求得最优解为：x1=200，x2=0，x3=0，x4=500，x5=0，x6=800，Z=3200。n可见，生产旅行车是有利可图的，新的生产方案为：生产大轿车200辆，生产旅行车800辆，剩余工时500小时，利润为3200千元。灵敏度分析小结灵敏度分析小结n价值系数发生变化时：1、如果是非基变量的系数发生变化，则只要该变量对应的检验数z zj j-c-cj j在c cj j变化后仍然大于等于0，则最优解不发生任何变化。2、如果是基变量的价值系数发生变化，则需要重新计算所有检验数，如果所有检验数仍然保持大于等于0，则最优基不变，但最优解一般会发生变化。如果有检验数变为负数，则在原最终单纯形表中继续迭代，求出最优解。灵敏度分析小结灵敏度分析小结n当资源向量发生改变时，用公式x xB B=B-1 b+b+B-1 b=b=x xB B +B-1 bb（其中bb=(0,0,bk,0)T）计算新的b列的值，如果新的b列的值仍然全部大于等于0，则最优基不变，但最优解的值一般会发生变化。n如果计算出来的新的b列的值出现负数，则说明该解是不可行解，用对偶单纯形法继续进行迭代运算，求出新的最优解。灵敏度分析小结灵敏度分析小结n当基变量技术系数发生变化时，求出用公式p pi i=B-1 p pi i求出发生变化的系数所在列的数值，代替最终单纯形表中原来的列。然后用高斯消元法将该列化为单位向量，计算新的检验数。1、如果检验数不为负数，则最优基不变。2、如果新的检验数变为负数，则最优基将发生变化，用单纯形法继续迭代，求出新的最优解。趣味数学趣味数学n你作为幸运观众参加了一个节目，节目中你面对三个门，其中一个门后一辆汽车，另外两个门后各有一只羊。主持人请你选择一扇门，门后的物品将做为你的奖品。当你选择后，主持人先不打开门，而是打开一扇门后有羊的门，然后问你改变不改变你的选择，请问，你该不该改变你的选择？作业作业n某公司制作三种产品A、B、C，需要劳动力和原材料两种资源，要求制订生产计划使总利润最大化。三种产品所需的资源和产生的利润如下表所示：ABC资源劳动力63545原材料34530利润315作业作业n1、请建立模型，解决最优生产计划问题。n2、求出使得最优解不变的产品A的单位利润变动范围，问A产品的利润变为2时最优解变不变？n3、假定原材料的市场价格是10元每单位，可以购买15个单位，问以10元的价格采购15单位原材料是否合算？n4、请问原材料的供应在什么范围内变化时，不必改变生产计划？作业作业n5、厂家研制出了一种新产品D，生产一单位D需要劳动力4单位，原材料3单位，而每单位的新产品D的利润为3元。请问：生产计划是否需要修改？为什么？该如何修改？第三章第三章 运运 输输 问问 题题主要内容主要内容n运输问题的背景运输问题的背景n运输问题的模型运输问题的模型n运输问题的表上作业法运输问题的表上作业法n运输问题的应用运输问题的应用运输问题的背景运输问题的背景n在经济建设中，经常碰到大宗物资调运问题，如煤炭、钢铁、粮食等等。n主产区和主销区往往不同，需要大规模的调运，将物资从产地供应到销地。n大型企业有多个生产基地，销售遍及全国乃至全世界，如何分配供应计划使经济效益最好。运输问题模型运输问题模型n运输问题运输问题 解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，且各地运输单价已知的前提下，如何确定一个使总的运输费用最小的方案。运输问题模型运输问题模型例例1.某公司从两个产地某公司从两个产地A A1 1 ,A A2 2 ,将货物运往三个销地将货物运往三个销地B B1 1 ,B B2 2 ,B,B3 3 ,各产地的产量、各各产地的产量、各销地的销量和各产地运往各销地的销量和各产地运往各销地的每件货物的运费如下销地的每件货物的运费如下表。问题：应如何调运，才表。问题：应如何调运，才能使得总运输费用最小？能使得总运输费用最小？运输问题模型运输问题模型n这是一个产销平衡的运输问题这是一个产销平衡的运输问题n把把A A1 1，A A2 2的产量全部分配给的产量全部分配给B B1 1，B B2 2，B B3 3，销地销地运费单价运费单价产地产地A A1 1 6 4 6 200 6 4 6 200A A2 2 6 5 5 300 6 5 5 300销销 量量 150 150 200 150 150 200 B B1 1 B B2 2 B B3 3 产量（件产量（件）单单 位位 运运 价价 表表运输问题模型运输问题模型n设决策变量设决策变量x xijij:产地产地A Ai i调运到调运到B Bj j的运输量的运输量（i=1,2;j=1,2,3)i=1,2;j=1,2,3)销地销地运费量运费量产地产地A A1 1 x x1111 x x1212 x x1313 200 200A A2 2 x x2121 x x2222 x x2323 300 300销销 量量 150 150 200 500 150 150 200 500 B B1 1 B B2 2 B B3 3 产量（件产量（件）产销平衡表产销平衡表运输问题模型运输问题模型n线性规划模型线性规划模型)3,2,1;2,1(0200150150300200.556646min231322122111232221131211232221131211jixxxxxxxxxxxxxtsxxxxxxfij运输问题模型运输问题模型n一般线性规划模型一般线性规划模型nA Ai i表示某种物资的第表示某种物资的第i i个产地个产地nB Bj j表示某种物资的第表示某种物资的第j j个销地个销地ns si i表示产地表示产地A Ai i的产量的产量nd dj j表示销地表示销地B Bj j的销量的销量nc cijij表示把物资从产地表示把物资从产地A Ai i运到销地运到销地B Bj j的单位运价的单位运价n决策变量决策变量x xijij表示产地表示产地A Ai i调运到销地调运到销地B Bj j的运输量的运输量运输问题模型运输问题模型njijijmixcf11mininjijsx1jmiijdx1x xj j 0,(i=1,2,0,(i=1,2,m;j=1,2,m;j=1,2,n)n)miinjjsd11运输问题模型运输问题模型n其他的运输问题模型其他的运输问题模型n产销平衡的运输问题产销平衡的运输问题:当当 时时n求目标函数最大的运输问题求目标函数最大的运输问题n考虑利润最大、营业额最大考虑利润最大、营业额最大n具有能力限制的运输问题具有能力限制的运输问题n运输线路的能力限制运输线路的能力限制n产销不平衡的运输问题产销不平衡的运输问题n产大于销：假设销地产大于销：假设销地n销大于产：假设产地销大于产：假设产地miinjjsd11运输问题模型运输问题模型n从模型中看，运输问题属于线性规划问题的一种。n其特殊之处在于：约束条件系数矩阵全部为0-1元素，而且结构比较松散。n系数矩阵中对应x xijij的系数向量，其分量中除第i个和第m+j个为1以外，其余的都为0。n以例1的模型为例，考察其约束条件系数矩阵：运输问题模型运输问题模型100100010010001001111000000111232221131211xxxxxx表上作业法表上作业法分分 析析 实实 际际 问题问题列出产销平衡表列出产销平衡表确定初始调运方案确定初始调运方案 西西 北北 角角 法法最小元素法最小元素法求检验数（闭回求检验数（闭回路法或位势法）路法或位势法）所有检验数所有检验数 0 0得到最优方案得到最优方案算出总的运价算出总的运价 找找 出出 绝对值最大的负检验数绝对值最大的负检验数 用闭回路调整得出新的调运方案用闭回路调整得出新的调运方案是是否否表上作业法表上作业法n表上作业法表上作业法n解决运输问题的单纯形法解决运输问题的单纯形法n针对运输问题变量多，结构独特的特点，简化了针对运输问题变量多，结构独特的特点，简化了运算运算n假设问题为产销平衡的运输问题假设问题为产销平衡的运输问题n求解步骤求解步骤1.找出初始的基可行解找出初始的基可行解运输问题有运输问题有m+n-1个基变量个基变量在（在（m n）产销平衡表上给出产销平衡表上给出m+n-1个数字格个数字格其相应的调运量就是基变量，格子中填写的值为基变量的值其相应的调运量就是基变量，格子中填写的值为基变量的值表上作业法表上作业法2.求各非基变量的检验数求各非基变量的检验数 在表上计算除了在表上计算除了m+n-1个数字格以外的空格的检验数个数字格以外的空格的检验数判别是否达到最优解判别是否达到最优解如已是最优解如已是最优解,则停止计算则停止计算,否则转下步否则转下步3.确定进基变量和出基变量确定进基变量和出基变量找出新的基可行解找出新的基可行解在表上用闭回路法调整在表上用闭回路法调整4.重复第重复第2、3步骤，直至得到最优解步骤，直至得到最优解表上作业法表上作业法 产销平衡表产销平衡表B B1 1 B B2 2 B Bj j B Bn n 产量限制产量限制c c1n1n销地销地产地产地A A1 1 A A2 2 A Am m c c1111销量限制销量限制c c1212c c1j1jx x1111s s1 1 s s2 2 s si i A Ai i s sm m c c2121c c2222c c2323c c2424c ci1i1c ci2i2c cijijc cininc cm1m1c cm2m2c cmjmjc cmnmnd d1 1 d d2 2 d dj j d dn n x x1212x x1n1nx x2121x x2222x x2n2nx xm1m1x xm2m2x xmnmnmiinjjsd11表上作业法表上作业法n确定初始基可行解确定初始基可行解n西北角法西北角法n最小元素法最小元素法n西北角法西北角法n从左上角的变量从左上角的变量x x11 11 开始分配运输量，并使开始分配运输量，并使x x1111的取的取值尽可能大值尽可能大n依次类推，直至给出全部方案为止依次类推，直至给出全部方案为止n例例2.2.喜庆食品公司有三个生产面包的分厂喜庆食品公司有三个生产面包的分厂A A1 1,A,A2 2,A A3 3,有四个销售公司有四个销售公司B B1 1,B,B2 2,B,B3 3,B,B4 4,其各分厂每日的其各分厂每日的产量、各销售公司每日的销量以及各分厂到各产量、各销售公司每日的销量以及各分厂到各表上作业法表上作业法销地销地运费单价运费单价产地产地A A1 1 3 11 3 10 7 3 11 3 10 7A A2 2 1 9 2 8 4 1 9 2 8 4销量销量(吨吨)3 6 5 6)3 6 5 6B B1 1 B B2 2 B B3 3 B B4 4 产量（吨产量（吨）2020A A3 3 7 4 10 5 9 7 4 10 5 9销售公司的单位运价如下表。产量与销量的单位为销售公司的单位运价如下表。产量与销量的单位为吨，运价的单位为百元吨，运价的单位为百元/吨。问该公司应如何调运产吨。问该公司应如何调运产品在满足各销点需求量的前提下，使总运费最少？品在满足各销点需求量的前提下，使总运费最少？表上作业法表上作业法可行方案为可行方案为:x x11 11=3,=3,x x12 12=4,x=4,x22 22=2,x=2,x23 23=2,x=2,x33 33=3,=3,x x34 34=6,=6,minfminf=135=135 3 3 销地销地产地产地A A1 1 A A2 2 B B1 1 B B2 2 B B3 3 B B4 4 产量（吨产量（吨）A A3 3 311310192874105销量销量(吨吨)3 6 5 6)3 6 5 67 74 49 9 0 0 4 4 4 4 0 0 2 2 2 2 0 0 2 2 2 2 3 3 0 0 3 3 0 0 6 6 6 6 0 0 0 0 表上作业法表上作业法n最小元素法最小元素法n西北角法是对西北角的变量分配运输量西北角法是对西北角的变量分配运输量n最小元素法是就近供应最小元素法是就近供应,对单位运价最小的变量分对单位运价最小的变量分配运输量配运输量n用最小元素法求的初始基可行解比西北角法的总运用最小元素法求的初始基可行解比西北角法的总运费要小费要小n通常迭代的次数可能会少通常迭代的次数可能会少表上作业法表上作业法可行方案为可行方案为:x x13 13=4,=4,x x14 14=3,x=3,x21 21=3,x=3,x23 23=1,x=1,x32 32=6,=6,x x34 34=3,=3,minfminf=86=86销地销地产地产地A A1 1 A A2 2 B B1 1 B B2 2 B B3 3 B B4 4 产量（吨产量（吨）A A3 3 311310192874105销量销量(吨吨)3 6 5 6)3 6 5 67 74 49 9 3 3 0 0 1 1 1 1 4 4 0 0 4 4 0 0 6 6 3 3 0 0 3 3 3 3 0 0 3 3 3 3 0 0 0 0 表上作业法表上作业法n注意注意n当取定当取定x xijij 的值之后的值之后,会出现会出现A Ai i 的产量与的产量与 B Bj j 的销量都为零的情况的销量都为零的情况,只能划去只能划去A Ai i 行或行或 B Bj j列列,不能同时划去不能同时划去n用最小元素法时用最小元素法时,可能会出现只剩一行或一可能会出现只剩一行或一列的所有格均未填数或未划掉的情况列的所有格均未填数或未划掉的情况,此时此时在这一行或这一列中除去已填上的数外均填在这一行或这一列中除去已填上的数外均填上零上零,不能将空格划掉不能将空格划掉n这样可保证填过数或行的格为这样可保证填过数或行的格为m+n-1m+n-1个个,即基即基变量的个数为变量的个数为m+n-1m+n-1个个表上作业法表上作业法n最优解的判定最优解的判定n检验已得到的运输方案是否为最优方案检验已得到的运输方案是否为最优方案n闭回路法闭回路法n位势法位势法n闭回路法闭回路法n闭回路的构成闭回路的构成n在已给出的调运方案的运输表上，从代表非基变量的一个在已给出的调运方案的运输表上，从代表非基变量的一个空格出发空格出发n沿水平或垂直方向前进，只有碰到代表基变量的有数字的沿水平或垂直方向前进，只有碰到代表基变量的有数字的格才能向左或右转格才能向左或右转n直到回到出发的空格直到回到出发的空格表上作业法表上作业法销地销地产地产地A A1 1 A A2 2 B B1 1 B B2 2 B B3 3 B B4 4 产量（吨产量（吨）A A3 3 311310192874105销量销量(吨吨)3 6 5 6)3 6 5 67 74 49 9 3 3 4 4 1 1 6 6 3 3 3 3 1 x x11 11 为非基变量的闭回路为非基变量的闭回路表上作业法表上作业法n检验数的计算：从（A1，B1）出发，增加一单位调运量（从A1运到B1），为保持产销平衡，依次做调整：在（A1，B3）处减少1吨，（A2，B3）处增加1吨，（A2，B1）处减少1吨。n调整方案使运费增加：1*3+（-1）*3+1*2+（-1）*1=1，可见这样调整将每单位增加运费1，将1填入（A1，B1）。所有非基变量的闭回路及检验数所有非基变量的闭回路及检验数表上作业法表上作业法空空 格格闭闭 回回 路路检检 验验 数数x x11 11 x x11-11-x x13-13-x x23-23-x x21-21-x x11 11 x x12-12-x x14-14-x x34-34-x x32-32-x x12 12 x x12 12 x x22 22 x x24 24 x x31 31 x x33 33 x x22-22-x x23-23-x x13-13-x x14-14-x x34-34-x x32-32-x x22 22 x x24-24-x x23-23-x x33-33-x x14-14-x x24 24 x x31-31-x x34-34-x x14-14-x x13-13-x x23-23-x x21-21-x x31 31 x x33-33-x x34-34-x x14-14-x x13-13-x x33 33 121-11012表上作业法表上作业法n闭回路法闭回路法n在以空格为始点和终点，其他顶点均为数字点的闭回路上在以空格为始点和终点，其他顶点均为数字点的闭回路上n将该空格的运输量调整为将该空格的运输量调整为1，则其他顶点在保持供销平衡，则其他顶点在保持供销平衡的基础上，运输量增加或减少的基础上，运输量增加或减少1n计算出该回路的总费用的变化值计算出该回路的总费用的变化值n该变化值作为该非基变量的检验数该变化值作为该非基变量的检验数n若所有检验数都大于零，则原基可行解为最优解若所有检验数都大于零，则原基可行解为最优解n否则进一步迭代找出最优解否则进一步迭代找出最优解n用闭回路法求检验数用闭回路法求检验数n要对每一个空格找一条闭回路要对每一个空格找一条闭回路n当产销点多时，较繁杂当产销点多时，较繁杂表上作业法表上作业法n位势法位势法n将运输表上的每一行赋予值将运输表上的每一行赋予值u ui i ,每一列赋予值每一列赋予值v vj j nx xijij为基变量，则满足为基变量，则满足c cijij -u ui i -v vj j =0=0 令令u u1 1=0=0，可先计算出，可先计算出u ui i 和和v vj j 的值的值nx xijij为非基变量，则利用为非基变量，则利用u ui i 和和v vj j 的值，计算出其检的值，计算出其检验数验数 ijij =c cijij -u ui i -v vj j n若所有检验数若所有检验数 ijij 均大于零，则均大于零，则原基可行解为最优原基可行解为最优解解n否则进一步迭代找出最优解否则进一步迭代找出最优解表上作业法表上作业法n例1中检验数的计算：n令u1=0，将基变量的检验数列出：n由基变量x14，有c14(u1+v4)=0n由基变量x13，有c13(u1+v3)=0n由基变量x21，有c21(u2+v1)=0n由基变量x23，有c23(u2+v3)=0n由基变量x32，有c32(u3+v2)=0n由基变量x34，有c34(u3+v4)=0表上作业法表上作业法n即：8(u1+v4)=0，5(u1+v3)=0 1(u2+v1)=0，4(u2+v3)=0 3(u3+v2)=0，10(u3+v4)=0n又知u1=0，所以得到：u1=0，u2=-1，u3=-5，v1=2,v2=9,v3=3,v4=10。n因非基变量的检验数ij=cij-ui-vj ，已知所有ui、vj的值，可以在表格中计算所有非基变量的检验数。销地销地产地产地A A1 1 (1)(1)(2)(2)4 3 0 4 3 0 A A2 2 3 3 (1)(1)1 1 (-1)(-1)-1 -12 9 3 10 2 9 3 10 B B1 1 B B2 2 B B3 3 B B4 4 u ui i A A3 3 (10)(10)6 6 (12)(12)3 -5 3 -5311310192874105v vj j表上作业法表上作业法表上作业法表上作业法n改进运输方案的方法改进运输方案的方法闭回路调整法闭回路调整法n选最小的负检验数，以它对应的非基变量为进基变选最小的负检验数，以它对应的非基变量为进基变量量n找出以该非基变量空格找出以该非基变量空格x xijij 为出发点的闭回路为出发点的闭回路n尽量增加尽量增加x xijij 的运输量的运输量n将该回路中的偶数顶点调运量的最小值取为将该回路中的偶数顶点调运量的最小值取为x xijij 的的运输量运输量n将所有回路中的偶数顶点的调运量减去该值，而奇将所有回路中的偶数顶点的调运量减去该值，而奇数顶点加上该值，得到新的调运方案数顶点加上该值，得到新的调运方案销地销地产地产地A A1 1 (1)(1)(2)(2)4 3 0 4 3 0 A A2 2 3 3 (1)(1)1 1 (-1)(-1)-1 -12 9 3 10 2 9 3 10 B B1 1 B B2 2 B B3 3 B B4 4 u ui i A A3 3 (10)(10)6 6 (12)(12)3 -5 3 -5311310192874105v vj j表上作业法表上作业法表上作业法表上作业法销地销地产地产地A A1 1 4 4（+1+1）3 3（-1-1）7 7A A2 2 3 1 3 1（-1-1）（+1+1）4 4销销 量量 3 6 5 6 3 6 5 6B B1 1 B B2 2 B B3 3 B B4 4 产产 量量A A3 3 6 3 9 6 3 9表上作业法表上作业法调整后的运输方案如下调整后的运输方案如下销地销地产地产地A A1 1 5 2 7 5 2 7A A2 2 3 1 4 3 1 4销销 量量 3 6 5 6 3 6 5 6B B1 1 B B2 2 B B3 3 B B4 4 产产 量量A A3 3 6 3 9 6 3 9运输量运输量表上作业法表上作业法n用位势法再计算出检验数如下表：所有检验数用位势法再计算出检验数如下表：所有检验数都大于零，最小费用为都大于零，最小费用为8585元元销地销地产地产地A A1 1 (0)(0)(2)(2)5 2 0 5 2 0 A A2 2 3 3 (2)(2)（1 1）1 -2 1 -23 9 3 10 3 9 3 10 B B1 1 B B2 2 B B3 3 B B4 4 u ui i A A3 3 (9)(9)6 6 (12)(12)3 -5 3 -5311310192874105v vj j表上作业法表上作业法n如何找多个最优方案如何找多个最优方案n识别是否有最优方案的方法与单纯形法一样识别是否有最优方案的方法与单纯形法一样n只需检查最优方案中是否存在非基变量的检验数为只需检查最优方案中是否存在非基变量的检验数为零零n将检验数为零的非基变量进入基，对运输方案进行将检验数为零的非基变量进入基，对运输方案进行调整，就可得到另一个最优方案调整，就可得到另一个最优方案n见下例见下例表上作业法表上作业法n由前面的表中可知：由前面的表中可知：x x1111的检验数的检验数 11 11=0=0n令令x x1111进入基，调整的运输方案为另一个最优方案进入基，调整的运输方案为另一个最优方案 销地销地产地产地A A1 1 （+2+2）5 2 5 2（-2-2）7 7 A A2 2 3 3（-2-2）1 1（+2+2）4 4 B B1 1 B B2 2 B B3 3 B B4 4 产产 量量 A A3 3 6 3 9 6 3 9 销销 量量 3 6 5 6 3 6 5 6表上作业法表上作业法n此时的最小运费仍为此时的最小运费仍为85销地销地产地产地A A1 1 2 5 7 2 5 7 A A2 2 1 3 4 1 3 4 B B1 1 B B2 2 B B3 3 B B4 4 产产 量量 A A3 3 6 3 9 6 3 9 销销 量量 3 6 5 6 3 6 5 6产销不平衡的运输问题产销不平衡的运输问题n对于产大于销的运输问题，可以用增加一个虚拟销地的方法转化为产销平衡的运输问题，任何一个产地运往虚拟销地的运费均设为0。n对于销大于产的运输问题，可以用增加一个虚拟产地的方法转化为产销平衡的运输问题，虚拟产地运往任何一个销地的运费均设为0。产销不平衡的运输问题产销不平衡的运输问题n例2：某产品的供求表如下，请给出最佳调运方案。销地销地运费单价运费单价产地产地A A1 1 3 11 3 10 7 3 11 3 10 7A A2 2 1 9 2 8 7 1 9 2 8 7销量销量(吨吨)3 6 5 6)3 6 5 6B B1 1 B B2 2 B B3 3 B B4 4 产量（吨产量（吨）2320A A3 3 7 4 10 5 9 7 4 10 5 9产销不平衡的运输问题产销不平衡的运输问题n首先转化为产销平衡的运输问题：B B1 1 B B2 2 B B3 3 B B4 4 B B5 5 产量产量销地销地运费单价运费单价产地产地A A1 1 3 11 3 10 0 7 3 11 3 10 0 7A A2 2 1 9 2 8 0 7 1 9 2 8 0 7销量销量(吨吨)3 6 5 6 3)3 6 5 6 32323A A3 3 7 4 10 5 0 9 7 4 10 5 0 9产销不平衡的运输问题产销不平衡的运输问题n用最小元素法求出初始可行解：B B1 1 B B2 2 B B3 3 B B4 4 B B5 5 产量产量销地销地运费单价运费单价产地产地A A1 1 1 3 3 7 1 3 3 7A A2 2 3 4 7 3 4 7销量销量(吨吨)3 6 5 6 3)3 6 5 6 32323A A3 3 6 3 9 6 3 9产销不平衡的运输问题产销不平衡的运输问题n用位势法求出非基变量的检验数得：B B1 1 B B2 2 B B3 3 B B4 4 B B5 5 产量产量销地销地运费单价运费单价产地产地A A1 1 （1 1）（2 2）1 3 3 7 1 3 3 7A A2 2 3 3 （1 1）4 4 （-1-1）（0 0）7 7销量销量(吨吨)3 6 5 6 3)3 6 5 6 32323A A3 3 （1010）6 6 （1212）3 3 （5 5）9 9产销不平衡的运输问题产销不平衡的运输问题n检验数存在负数，用闭回路法调整：B B1 1 B B2 2 B B3 3 B B4 4 B B5 5 产量产量销地销地运费单价运费单价产地产地A A1 1 1 1（+3+3）3 3（-3-3）3 7 3 7A A2 2 3 4 3 4（-3-3）（+3+3）7 7销量销量(吨吨)3 6 5 6 3)3 6 5 6 32323A A3 3 6 3 9 6 3 9产销不平衡的运输问题产销不平衡的运输问题n调整后的运输方案为：B B1 1 B B2 2 B B3 3 B B4 4 B B5 5 产量产量销地销地运费单价运费单价产地产地A A1 1 （1 1）（3 3）4 4 （1 1）3 7 3 7A A2 2 3 3 （2 2）1 3 1 3 （1 1）7 7销量销量(吨吨)3 6 5 6 3)3 6 5 6 32323A A3 3 （9 9）6 6 （1111）3 3 （4 4）9 9产销不平衡的运输问题产销不平衡的运输问题n运输费用为：80n最优方案为:x13=4,x15=3,x21=3,x23=1,x24=3，x32=6,x34=3。产销不平衡的运输问题产销不平衡的运输问题n思考题：产销不平衡的运输问题转化为产销平衡的运输问题后，虚拟产地运出的产品或运往虚拟销地的产品的单位运输费用均设为0，为什么？如果设为M行不行？设为任意数值行不行？为什么？运输问题作业运输问题作业n1、求解运输问题：B B1 1 B B2 2 B B3 3 产量（吨产量（吨）销地销地运费单价运费单价产地产地A A1 1 20 16 24 300 20 16 24 300A A2 2 10 10 8 500 10 10 8 500销量销量(吨吨)200 400 300 )200 400 300 900900A A3 3 80 18 10 100 80 18 10 100运输问题作业运输问题作业n1、求解运输问题：B B1 1 B B2 2 B B3 3 产量产量销地销地运费单价运费单价产地产地A A1 1 10 16 32 15 10 16 32 15A A2 2 14 22 40 7 14 22 40 7销量销量 12 8 20 12 8 20 A A3 3 22 24 34 16 22 24 34 16第四章第四章 整数规划整数规划主要内容主要内容n整数规划的特点整数规划的特点n整数规划的图解法整数规划的图解法n整数规划的计算机解法整数规划的计算机解法n整数规划的分枝定界法整数规划的分枝定界法n整数规划的应用整数规划的应用整数规划的特点整数规划的特点n问题的提出问题的提出n在一般的线性规划中，最优解往往是分数或小数在一般的线性规划中，最优解往往是分数或小数n在许多实际问题中，要求全部或部分变量的取值必在许多实际问题中，要求全部或部分变量的取值必须是整数须是整数n安排上班的人数安排上班的人数n裁剪钢材的根数裁剪钢材的根数n生产机器的台数生产机器的台数n分类分类n纯整数规划：所有变量为非负整数纯整数规划：所有变量为非负整数n01 规划：所有变量取值为规划：所有变量取值为0、1n混合整数规划：部分变量为非负整数混合整数规划：部分变量为非负整数整数规划的特点整数规划的特点n求解方法求解方法n四舍五入法或凑整法四舍五入法或凑整法n变量取值很大时，此方法得到的解与最优变量取值很大时，此方法得到的解与最优解差别不大解差别不大n但当问题规模较大时，计算工作量很大但当问题规模较大时，计算工作量很大n如如,最优解为最优解为(4.6,5.5)；n10个变量要比较个变量要比较 次，最优次，最优解不一定在这些组合中解不一定在这些组合中1024210整数规划的特点整数规划的特点且为整数,0,5.45.0143223max21212121xxxxxxxxzn比较比较(4,3),(4,2),(3,3)(4,3),(4,2),(3,3)不是可行解不是可行解n(3,2)(3,2)是可行解是可行解,不是最不是最优解优解z=13z=13n最优解最优解(4,1),(4,1),z=14z=14123 x x1 11230 02x2x1 1+3 x+3 x2 2 =14=14 x x2 24x x1 1+0.5x+0.5x2 2 =4.5=4.5456756789(3.25,2.5)(3.25,2.5)整数规划的特点整数规划的特点n常用方法常用方法n二变量的图解法二变量的图解法n分枝定界方法分枝定界方法n割平面法割平面法n分配问题的匈牙利方法分配问题的匈牙利方法n0-1型整数规划的隐枚举法型整数规划的隐枚举法整数规划的特点整数规划的特点n例例1.1.有一份说明书有一份说明书,要分别翻译成英、日、德、俄四要分别翻译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各个的种文字，交甲、乙、丙、丁四个人去完成。因各个的专长不同，所需时间如表所示。问应如何分配，使这专长不同，所需时间如表所示。问应如何分配，使这四个人分别完成这四项任务总的时间最小？四个人分别完成这四项任务总的时间最小？人人工作工作英文英文日文日文德文德文俄文俄文甲甲 乙乙 丙丙 丁丁2 10 9 715 4 14 813 14 16 11 4 15 13 9整数规划的特点整数规划的特点n引入引入0-1逻辑变量逻辑变量ijx1 1，分配第分配第i i个人完成第个人完成第j j项任务项任务0 0，不分配第不分配第i i个人完成第个人完成第j j项任务项任务4141minjijijixcz)4,3,2,1;4,3,2,1(10)4,3,2,1(1)4,3,2,1(14141jixjxixijiijjij或整数规划的图解法整数规划的图解法n基本思