管理运筹学 全套ppt课件.ppt

,管 理 运 筹 学,数学的魅力与实质,数学的本质是处理抽象对象，是比语言更精炼、更严谨的符号系统。是人类理性的集中体现。数学的方法是建立一个牢不可破的公理体系，并以演绎推理的方法去构建和扩展整个学科体系。,应用,演绎方法,公理体系,数学大厦,数学的魅力与实质,数学方法在自然科学体系中无处不在，并取得了光辉的成就。19世纪以后，数学被广泛深入地应用于社会科学领域。经济学、管理学领域的许多大师具有高超的数学技能。,数学的魅力与实质,本门课程不仅要学习一门课程，一套方法，更重要的是要学会理性分析问题的方法。培养逻辑思维能力和抽象思维能力。数学在发展的过程中遇到过许多问题，而且也并非确切无疑，大家要敢于质疑，敢于提问题。,数学的魅力与实质,一个例子： S=1-1+1-1+1请问S等于多少？,数学的魅力与实质,至少有三种解法： 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。,数学的魅力与实质,事实上，这是一个争论未定的题目，反映了人类对自然认识的不足。无穷的概念存在许多不足之处，而且并非绝对精确。不同的学派对无穷有着不同的认识。,考核方法,平时成绩占20%，每位同学的初始成绩都是60分（按100分为满分计算）。每次作业交上加1分，不交不加不减，拷贝别人作业一次扣2分。上课主动回答问题每次加2分。提出有价值问题或发现老师错误每次加5分。,运筹学的体系和发展历史,定义运筹学是一门应用于管理有组织系统的科学它为掌管这类系统的人提供决策目标和数量分析的工具运筹学应用分析、实验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理正式起源与二次世界大战，被称为Operations research,日本人翻译为运做学，台湾人翻译为作业研究,运筹学的体系和发展历史,田忌赛马萌芽在20世纪初，Lanchester战斗方程。丹麦工程师爱尔朗研究电话通讯系统时提出了一些排队论的公式。30年代，数学家列温逊运用运筹思想分析商业广告、顾客心理。,运筹学的体系和发展历史,二次世界大战中，英美科学家研究如何有效运用雷达，研究船队遇到袭击如何减少损失，以及如何使用深水炸弹等紧迫问题。应用：德国潜艇被摧毁数增加到400%，船只中弹数由47%减少到29%。结果：打赢了空战和海战，保证了二次世界大战的最终胜利。,运筹学在现实生活中的例子,企业安排生产计划库存管理公交系统优化食堂窗口设置电脑游戏，帝国时代、魔兽争霸等。,运筹学的学科体系,规划论：包括线性规划、非线性规划、整数规划等。1947年，Danzig提出单纯形法，随后规划方法得到了广泛的应用。图论与网络分析：图是研究离散事物之间关系的一种分析模型。例：有甲、乙、丙、丁、戊、己6名同学参加ABCDEF六个项目的比赛，下表是各运动员报名参赛的项目，问6个项目顺序如何安排，作到每名运动员不连续参加两项比赛。,运筹学的学科体系,运筹学的学科体系,排队论：研究公共服务系统的运行与优化的数学理论方法。决策论：研究不确定情况以及风险情况下的决策。存储论：研究企业的库存计划，进货周期等。博弈论：研究竞争环境下决策者行为的数学方法。,运筹学的工作步骤,提出和形成问题：弄清问题的目标，可能的约束，问题的可控变量，相关参数等。建立模型：把问题中的可控变量、参数、目标、约束之间的关系用一定的模型表示出来。求解：用计算或实验方法求出问题的解。解的检验：检查求解过程，检查解能否反映现实问题。解的实施：将解运用到实际问题中。,第一章 线性规划,本章内容,线性规划模型线性规划问题的图解法单纯形法非标准形线性规划的解法,线性规划模型,规划问题：就是否合理利用有限资源的问题。线性规划：线性的规划问题。两个意思： 1、目标函数是线性的 2、约束条件是线性的,线性规划模型,生产决策问题某汽车工厂生产大轿车和载重汽车两种型号的汽车,已知每辆汽车所用的钢材都是2吨/辆，该工厂每年供应的钢材为1600吨；工厂的生产能力是每2.5小时可生产一辆载重汽车，每5小时可生产一辆大轿车，工厂全年的有效工时为2500小时；已知供应给该厂大轿车用的座椅每年可装配400辆。据市场调查，出售一辆大轿车可获利4000元，出售一辆载重汽车可获利3000元。如何安排生产才能使工厂获利最大？,线性规划模型,建模型如下：设大轿车数量为x1,载重汽车数量为x2。,s.t.是subject to 的简写，表示受限制于。,线性规划模型,某工厂在计划期间内生产 、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示：,已知 、两种产品每单位分别可以获利50元、100元，问工厂应该如何安排生产才能使工厂获利最多。,线性规划模型,设置变量：生产 产品x1个， 产品x2个目标函数是利润最大化：资源是有限的，第一个限制是设备台时的限制：,线性规划模型,第二个限制是原材料A的限制：第三个限制是原材料B的限制：显然，产量不可能为负数：,线性规划模型,建模型如下：设生产 产品x1件, 产品x2件。,线性规划模型,（1），（2）分别被称为目标函数和约束条件。目标函数中变量的系数被称为价值系数，约束条件不等号右端称为资源向量或限定系数，约束条件左端变量的系数被称为技术系数。目标函数和约束条件都是一次幂函数，或称线性函数，因此这类规划问题被称为线性规划问题。,线性规划模型,例3：生产卷烟的主要原材料包括烟叶和烟梗。国家规定每千克焦油含量不超过15mg，烟气烟碱含量不超过1.4mg，现在知道每千克烟叶含焦油12mg，烟气烟碱1.5mg，烟梗含焦油18mg，烟气烟碱0.3mg，烟叶每千克50元，烟梗每千克20元，问如何搭配使生产成本最小。,线性规划模型,设每千克卷烟用烟叶x1千克，烟梗x2千克，模型如下：,这是目标函数一个求最小化的问题。,线性规划的标准形,为求解方便，一般线性规划都可以转化成如下标准形式：,要求,线性规划的标准形,目标函数为求最小化时，等式两端同乘以-1，变为求最大化。约束条件为=时，减一个剩余变量。资源变量为负数时，等式两端同乘以-1。变量为=0时，令变量无约束时，令,线性规划的图解法,以例1为例：,线性规划的图解法,x2,800,400,400,800,x1,线性规划的图解法,从图中可以得到： x1=200,x2=600,z=2600最优解为：生产200辆大轿车，生产600辆载重汽车，可获利润2600千元。钢材和工时全部用完，座椅剩余200套。,几个概念,凸集：设k是n维欧氏空间中的一个点集，在集合中任意取两点x1,x2k。如果这两点连线上的一切点都落在k中，则称k为凸集。角顶：设k为凸集，xk，如果不能用不同的两点x1,x2k线性表出x，则称x为k的一个角顶。角顶可行解和角顶不可行解：既是角顶解又是可行解的解称为角顶可行解，是角顶解而不是可行解的解称为角顶不可行解。,图解法的几点启示,线性规划的可行域必定为凸集。线性规划的最优解必定在顶点取得。如果有多个最优解，那么至少有两个相邻的角顶可行解是最优解。角顶可行解的数目是有限的。如果一个角顶可行解的目标函数值比相邻的所有角顶解好，它就是最优解。,解决线性规划问题的思路,基本思路是在满足约束条件的前提下，从一个初始顶点开始，不断寻找改进目标函数的顶点，直到无法改进为止。步骤1：从一个角顶可行解出发，判断相邻的角顶可行解是否比目前的点更好。如果相邻的角顶可行解都劣与这个顶点，则说明这个点已经是最优解，算法结束。步骤2：如果相邻的角顶可行解更好，就向这个点移动。重复步骤1。,线性规划问题解的基本概念,可行解：满足约束条件解称为可行解，对应图解法的阴影部分。基：约束条件中任意一个m阶非奇异子矩阵确定一个线性规划问题的基。对应图解法中的顶点。基可行解：既是可行解又是基解称为基可行解。最优解：满足目标函数和约束条件的解称为最优解。,单纯形法,求解单纯形法的步骤单纯形表法单纯形表法中的一些特殊情况,求解单纯形法的步骤,步骤1：将模型转化为标准形。步骤2：找到一个初始可行基，列出初始单纯形表。步骤3：判断初始可行基是否最优。如果是最优解则结束，否则转步骤4。步骤4：如果不是最优，则通过一定的规则将一个变量换出，另一个变量换入，构成一个新的基解。转步骤3。,求解单纯形法的步骤,x2,800,400,400,800,x1,求解单纯形法的步骤,图形解法只能解决2维的线性规划问题（仅有两个变量）。对超过3维的情况，既无法在平面上画出图形，也无法进行直观的想象。根据图形解法的启示，提出单纯形法解决线性规划问题的基本思路。,单纯形表法,以例一为例：,单纯形表法,步骤1：首先转化为标准形式：添加松弛变量。,单纯形表法,步骤2：找到一个初始可行基。即寻找一个m阶的非奇异子矩阵。从标准形的线性规划问题中可以看出，x3,x4,x5构成了一个3阶的单位矩阵，把这三个变量作为初始可行基。列出初始单纯形表。,单纯形表法,列出初始单纯形表：,单纯形表法,步骤3：确定换入换出变量。方法：先确定换入变量，计算检验数zj -cj ，计算方法： ，cj为对应xj的系数。以最负的检验数对应的系数列作为主列元素。随后确定换出变量，计算检验数，计算方法： ，选择值最小的行对应的主列元素作为换出变量。,单纯形表法,确定换入换出变量：,单纯形表法,步骤4：以主元素为中心，进行迭代运算。,单纯形表法,检验数仍然有负数，继续确定换出换入变量,单纯形表法,迭代运算,单纯形表法,继续迭代：,单纯形表法,从表中可以看出，检验数全部为正数或零，说明已达到最优。求得最优解为： x1=200，x2=600，x3=0，x4=0，x5=200，Z=2600。生产方案为：生产大轿车200辆，生产载重汽车600辆，剩余座椅200套，利润为2600千元。,单纯形表法,思考题1、用单纯形法求解线性规划问题时为什么要首先转化为标准形？2、为什么要选择松弛变量作为初始可行基，能不能任意选择几个变量作为初始可行基？,作业,求解线性规划问题：,作业,某工厂在计划期内要生产A、B两种产品，已知生产单位产品所需的设备台时及甲、乙两种原材料的消耗如下表所示：,作业,该工厂每生产一件产品A可以获利2元，每生产一件产品B可以获利3元，问应该如何安排计划使该工厂获利最多？要求：建立线性规划模型并用单纯形法求解。,单纯形表法,例2：用单纯形表法求解线性规划问题：,单纯形表法,步骤1：首先转化为标准形式：添加松弛变量。,单纯形表法,步骤2：找到一个初始可行基。从标准形的线性规划问题中可以看出，x3,x4,x5构成了一个3阶的单位矩阵，把这三个变量作为初始可行基。列出初始单纯形表。,单纯形表法,列出初始单纯形表：,x1 x2 x3 x4 x5,x Cj,zj,zj -cj,50 100 0 0 0,1 1 1 0 0 2 1 0 1 0 0 1 0 0 1,b,单纯形表法,步骤3：确定换入换出变量。确定换入变量，计算检验数zj -cj ，计算方法： ，cj为对应xj的系数。以最负的检验数对应的系数列作为主列元素。随后确定换出变量，计算检验数，计算方法： ，选择值最小的行对应的主列元素作为换出变量。,单纯形表法,确定换入换出变量：,单纯形表法,步骤4：以主元素为中心，进行迭代运算。,单纯形表法,检验数仍然有负数，继续确定换出换入变量,x1 x2 x3 x4 x5,x Cj,zj,-50 0 0 0 0,zj -cj,0 100 0 0 0,50 100 0 0 0,1 0 1 0 -1 2 0 0 1 -1 0 1 0 0 1,b,25000,单纯形表法,迭代运算,x1 x2 x3 x4 x5,x Cj,zj,0 0 50 0 50,zj -cj,50 100 50 0 50,50 100 0 0 0,1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 1,b,27500,单纯形表法,检验数全部大于等于0，已经求得最优解。最优解为：x1=50,x2=250,x3=0,x4=50,x5=0;Z=27500,单纯形表法,例3：某工厂在计划期内要生产A、B两种产品，已知生产单位产品所需的设备台时及甲、乙两种原材料的消耗如下表所示：,单纯形表法,该工厂每生产一件产品A可以获利2元，每生产一件产品B可以获利3元，问应该如何安排计划使该工厂获利最多？要求：建立线性规划模型并用单纯形法求解。,单纯形表法,A产品的产量设为x1，B产品的产量设为x2，建立模型如下：,单纯形表法,最终单纯形表为：,单纯形表法中一些问题,如果两个相同，有可能产生退化现象（死循环），可以用摄动法求解，就是选下标最小的变量作为换出变量。有一个以上的非基变量为0时，说明有无穷多解，这时换入换出变量做完之后Z值不变，这时两个点连线上的任何一点都是最优解。主列元素全部为负数或0时，这时值无法计算，也无法确定换出变量，则此时说明有无界解，此时检查你的计算过程看前面计算是否出现错误，或检查建模是否有错误。,思考题,当变量无约束时，需要做变换：请问， 会同时出现在最终单纯形表中吗？为什么？,单纯形法的进一步讨论,目标函数求最小化时，有两种解决方法： 1、目标函数左右同乘以-1，变成求最大化的问题。 2、直接用单纯形法计算，但是检验规则改变，以正的检验数对应的变量作为换入变量，当全部检验数为负数时迭代结束。,单纯形法的进一步讨论,当约束条件出现等号约束时，无法通过增加松弛变量的方法产生初始可行解，这时要使用增加人工变量的方法来产生初始可行基。由于人工变量在最终解中必须为0，否则无法满足约束条件，如何使人工变量在最优解中为0？用大M法。,大M法,当目标函数是求极大值时，令人工变量在目标函数中的系数为-M，其中M是一个非常大的正数。这样，如果人工变量不为0，则目标函数就无法取到最优。当目标函数是求最小时，令人工变量在目标函数中的系数为M（为什么？）。,大M法,例4：,大M法,化为标准形，约束条件变为：,大M法,系数行列式为：这时无法直接在系数矩阵中找到一个初始可行解。把第三个约束条件添加一个人工变量。,大M法,约束条件：变为：由这两个式子可以看出x5必定等于0。,大M法,系数行列式变为：出现了一个三维的单位矩阵，可以用单纯形法求解了，但还要保证x5=0，所以目标函数变形为：,大M法,列出初始单纯形表：,大M法,迭代计算,大M法,迭代运算,x1 x2 x3 x4 x5,x Cj,zj,0 0 -4.5 0 2.5+M,zj -cj,3 5 -4.5 0 2.5,3 5 0 0 -M,1 0 1 0 0 0 0 3 1 -1 0 1 -1.5 0 0.5,b,27,大M法,迭代计算,x1 x2 x3 x4 x5,x Cj,zj,0 0 0 1.5 M+1,zj -cj,3 5 0 1.5 1,3 5 0 0 -M,1 0 0 -1/3 1/3 0 0 1 1/3 -1/3 0 1 0 1/2 0,b,36,大M法,大于等于约束条件 当出现大于等于约束条件时，首先添加一个剩余变量，使约束条件变为等式约束，然后再添加一个人工变量，用大M法求解。常数项为负数时，先在等式两边同乘-1，使资源变量变为正数，然后再根据相应情况进行处理。,趣味数学,这是基诺未能想出来的又一个悖论。一条蠕虫在橡皮绳的一端。橡皮绳长一公里。 蠕虫以每秒1厘米的稳定速度沿橡皮绳爬行。在1秒钟之后，橡皮绳就像橡皮筋一样拉长为2公里。再过一秒钟后，它又拉长为3公里，如此下去。蠕虫最后究竟会不会达到终点呢？,作业,将本问题转化为标准形，并列出初始单纯形表。,作业,求解线性规划问题：,第二章 对偶理论和灵敏度分析,本章内容,对偶问题的提出原问题与对偶问题原问题与对偶问题的转化影子价格对偶问题的求解灵敏度分析,对偶问题的提出,对偶现象无论是从理论还是实践，对偶问题是线性规划最重要和最有趣的概念和理论刻划四边形面积与周长之间的关系周长一定的四边形中，面积为最大面积一定的四边形中，周长为最小一种现象的两种提法线性规划问题原问题：求目标最大对偶问题：求目标最小,对偶问题的提出,例1 美佳公司计划制造、两种家电产品的生产，已知生产单位产品所需的设备A、B、C台时如下。该公司每生产一单位产品、 可获利50元、100元。问：如何达到利润最大？,对偶问题的提出,例1的决策问题：生产多少个产品和产品才能使利润达到最大设决策变量 x1 为生产产品的数量， x2为生产产品的数量 最大利润：max z = 50 x1 + 100 x2 约束条件： x1 + x2 300 2x1 + x2 400 x2 250 x1 ， x2 0,对偶问题的提出,生产产品，创造最大利润？,出赁设备，确定合理租金？,出赁设备总租金不应低于原利润,全部设备的总租金越低越好,对偶问题的提出,设决策变量 y1 , y2, y3为设备A、B、C每台时的租金最小租金：min f = 300y1+400y2+250y3,原问题与对偶问题,原问题某企业有m种资源，生产n种产品各种资源的拥有量为bi,xj为产量, aij 为生产第j种产品所消耗第i种资源的数量， cj为产值,原问题与对偶问题,对偶问题出让资源，获取回报，付出代价条件：同等数量资源出让的代价应不低于组织生产的产值yi出让第i种资源付出的代价,原问题与对偶问题,两者的关系,原问题与对偶问题的转化,例2. 写出下列问题的对偶问题及对偶的对偶问题,原问题与对偶问题的转化,对偶问题,对偶的对偶问题,原问题与对偶问题的转化,目标函数求最小等式约束xj 0 xj 取值无约束,原问题与对偶问题的转化,例3 写出下述线性规划的对偶问题,原问题与对偶问题的转化,对偶问题,影子价格,原问题与对偶问题的重要性质Yi对一个第i种资源的估价，不是资源的市场价格是企业根据资源在生产中作出的贡献的估价影子价格：对资源在生产中作出的贡献的估价对偶变量Yi单位资源在最优利用条件下所产生的经济效果特征影子价格依赖于资源利用情况，是未知量。随生产任务、产品结构情况变化。,影子价格,一种边际价格： yi的值相当于在给定的生产条件下， bi每增加一个单位时，目标函数z的增加量一种机会成本当市场价格低于影子价格时，购进资源，增加生产，提高利润当市场价格高于影子价格时，出售资源，提高利润随着影子价格的买进和卖出，影子价格随之变动，直到影子价格与市场价格保持同等水平，才处于平衡,影子价格,线性规划的原问题是确定资源的最优分配方案，而对偶问题是确定对资源的恰当评估大公司借助资源的影子价格确定一些内部结算价格，以控制资源的使用和考核下属企业的经营状况在社会资源的有效配置中，可借助影子价格规定使用最紧缺资源一个单位必须上缴的利润额，以控制一些效益低的企业自觉节约使用紧缺资源,对偶问题的求解,利用原问题单纯形法,确定初始基可行解,转换为新基可行解,建立最优解判断准则,例4. 求对偶问题的解,对偶问题的求解,对偶问题的求解,用单纯形法解，添加两个剩余变量，两个人工变量，用大M法求解。非常麻烦，运算量比较大。当约束条件个数很多时，计算量成倍增加。,对偶问题的性质,弱对偶性，如果X，Y分别是原问题和对偶问题的可行解，则存在：CXYB对偶定理：若原问题有最优解，则对偶问题也有最优解，且目标函数值相等。解的互补松弛性：原问题的基变量对应于对偶问题的松弛变量的检验数，原问题的松弛变量对应于对偶问题的基变量的检验数。,对偶单纯形法基本思想:在保持对偶问题为可行解的基础上,逐步迭代,减小目标值,当原问题也达到可行解时,得到了目标函数的最小值,对偶问题的求解,对偶问题的求解,步骤1：根据线性规划问题，列出初始单纯形表，检查b列数字，若都为非负，检验数也均为非负，则已经得到最优解。否则转步骤2。步骤2：确定换出变量，选择最负的基变量为换出变量。步骤3：确定换入变量，如果换出变量对应的行系数全部非负，则无可行解。否则，用换出变量那一行具有负值的系数分别去除同列的检验数，取绝对值最小者对应的变量为换入变量。,对偶问题的求解,步骤4：以换入变量对应的行和换出变量对应的列交点对应的元素做为主元素，进行迭代运算，得到新的单纯形表。步骤5：最优性检验，如果b列元素和检验数全部为非负，则已得到最优解，否则转步骤2。,对偶单纯形法,步骤1：转换并列出初始单纯形表,对偶单纯形法:初始单纯形表,b,b列系数为负，检验数为正，说明原问题为可行解，而对偶问题为不可行解。转步骤2。,对偶单纯形法:确定换入换出变量,选b列系数最负的值为换出变量，用换出变量那一行具有负值的系数分别去除同列的检验数，取绝对值最小者对应的变量为换入变量，转步骤4。,b,对偶单纯形法:迭代运算,y1 y2 y3 y4 y5,以换入变量对应的行和换出变量对应的列交点对应的元素做为主元素，进行迭代运算，得到新的单纯形表。 b列系数仍存在负数，转步骤2。,b,对偶单纯形法:确定换入换出变量,以换入变量对应的行和换出变量对应的列交点对应的元素做为主元素，进行迭代运算，得到新的单纯形表。 b列系数仍存在负数，转步骤2。,b,对偶单纯形法:迭代运算,以第一行和第一列交点对应的元素做为主元素，进行迭代运算，得到新的单纯形表。 b列系数全部非负，检验数也全部非负，已求得最优解。,b,对偶单纯形法：解的说明,Y=（50,0,50,0,0），-f=-27500即f=27500 。与原问题比较可以看到，y1,y3恰好是原问题第一、第三个约束条件的松弛变量。检验数恰好是原问题的解。这就是所谓的互补松弛性。原问题与对偶问题的最优解相同。,对偶单纯形法,例5. 求对偶问题的解,对偶单纯形法,例5的最终单纯形表如下：,y1 y2 y3 y4 y5,Y Cj,zj,0 0 1.8 1.6 0.2,zj -cj,-2 -3 -2.2 1.6 0.2,-5.6,-2 -3 -4 0 0,0 1 -0.2 -0.4 0.2 1 0 1.4 -0.2 -0.4,b,对偶单纯形法,初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，可以简化计算。当变量多于约束条件时，用对偶单纯形法可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先转化为对偶问题，然后用对偶单纯形法求解。在灵敏度分析中，有时需要用对偶单纯形法，这样可以使问题简化。,对偶单纯形法：作业,1、什么是资源的影子价格，同相应的市场价格之间有何区别，研究影子价格的意义何在。2、试述对偶单纯形法的计算步骤，它的优点及应用上的局限性。3、写出线性规划问题的对偶问题：,对偶单纯形法：作业,用对偶单纯形法求解以下问题：,灵敏度分析,由于市场条件、工艺条件以及企业规模的变化，价值系数、资源向量、技术系数等都会发生变化。提出两个问题：一、当这些系数有一个或几个发生变化时，最优解会发生变化；二、这些系数在什么范围内变化时，线性规划问题的最优解不变。如果每有参数发生变化就重新构建模型计算，太麻烦，也没有必要。可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，进行分析。,灵敏度分析,价值系数的灵敏度分析资源向量的灵敏度分析约束方程系数矩阵的灵敏度分析决策变量增减的灵敏度分析约束条件增减的灵敏度分析,价值系数的灵敏度分析,某工厂在计划期间内生产1、2、3三种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示：,1、2、3每单位产品分别可以获利2元，3元，a元，求如何安排生产可以使工厂利润最大。,价值系数的灵敏度分析,线性规划问题：,问，当a=1，2，3，5时，最优解分别为多少，最优基分别为那些变量。,价值系数的灵敏度分析,当a=1时，最终单纯形表如下：,价值系数的灵敏度分析,当a=2时，最终单纯形表如下：,价值系数的灵敏度分析,当a=3时，最终单纯形表如下：,价值系数的灵敏度分析,当a=5时，最终单纯形表如下：,x1 x2 x3 x4 x5 x6,x Cj,zj,0.5 0 0 1.5 0.25 0,zj -cj,2.5 3 5 1.5 0.25 0,2 3 5 0 0 0,0 1 0 0.5 -0.125 00.5 0 1 0 0.125 0 0 0 0 -2 0.5 1,b,16,价值系数的灵敏度分析,当a=1，2，3时，zj - cj 0，最终单纯形表基本没有改变，最优解没有改变，仅有x3的检验数有所不同。当a=5时， zj - cj 0，最优基改变，最终单纯形表也发生改变。当最优基发生变化时，事实上我们不必重新进行全部计算，只需要在原来最终单纯形表的基础上继续迭代就可以得到最优解。,价值系数的灵敏度分析,当a由3变为5时：,价值系数的灵敏度分析,从上图中看到，检验数仍存在负数，继续迭代。,x1 x2 x3 x4 x5 x6,x Cj,zj,0.5 0 0 1.5 0.25 0,zj -cj,2.5 3 5 1.5 0. 25 0,2 3 5 0 0 0,0.5 0 1 0 0.125 0 0 0 0 -2 0.5 1 0 1 0 0.5 -0.125 0,b,16,价值系数的灵敏度分析,非基变量价值系数变化 价值系数不在基变量中，zj保持不变，所以检验数zj - cj变化cj （为正数） ，要保持最优解不变，只要cj zj - cj 。基变量价值系数变化 基变量价值系数发生变化时，只需将新的价值系数代入最终单纯形表中，检查检验数，如果检验数仍保持为正，则最优基不变，但最优解的值会发生变化。如果检验数出现负数，则以原最终单纯形表为基础，继续进行迭代运算。,资源向量的灵敏度分析,单纯形法的实质是找到一个能得到最优解的基xB ，在约束条件中用其系数矩阵左乘一个B-1 ，令非基变量为0，得到最优解向量xB = B-1 b。事实上迭代过程也是用矩阵初等变换求B的逆矩阵B-1的过程。最终单纯形表中的b列其实就是B-1 b，当第k个资源向量bk变为bk+bk时，也就是原来单纯形表中的b向量变成了b向量。,资源向量的灵敏度分析,令b=(0,0, bk,0)T ，则有b= b+ b，这样最终单纯形表中基变量xB的解就变成了xB= B-1 (b + b）= B-1 b + B-1 b。要使xB仍然为最优解，只要B-1 b + B-1 b0即可。如果bk的变化使得B-1 b + B-1 b0，这时最优解的基就要发生变化，这种情况下用对偶单纯形法继续求出新的最优解。,资源向量的灵敏度分析,例：课本P6例1-1中，如果钢材的供应数量发生变化，请问1、钢材供应量在什么范围内变化时，最优基不会发生改变？2、当钢材的供应量增加到2200吨时，应当如何安排生产计划？,资源向量的灵敏度分析,如果例1-1中的钢材供应数量变为1600+ b1，最终解将变为： xB= B-1 b= B-1 (b + b） = =,资源向量的灵敏度分析,要保证最优基不改变，要求b中所有向量大于等于0，即：从（1）式中可得： b1-400，从（2）式中可得： b1-600，从（3）式中可得： b1400，得到-400 b1400，也就是说，钢材供应量在1200到2000之间时，最优基不发生变化。,资源向量的灵敏度分析,资源向量在一定范围内变化时，最优基虽然不会发生变化，但最优解则会发生变化。最优基不变时，可以直接将发生变化的资源向量代入B-1 b中，得到新的最优解的值。例如，当钢材供应量变为2000时，新的最优解的求解如下：,资源向量的灵敏度分析,资源向量的灵敏度分析,当钢材的供应量增加到2200吨时：资源向量出现负数，不再是可行解，需要继续迭代，用对偶单纯形法。,资源向量的灵敏度分析,最终单纯形表变为：,资源向量的灵敏度分析,以主元素为中心进行迭代运算：,趣味数学,一个富有的律师拥有11辆古董汽车，每辆值5000美元。律师死时留下了一个奇怪的遗嘱。他说他的11辆古董汽车分给他的三个儿子。把其中的一半分给长子，1/4分给次子，1/6分给小儿子。同时规定不能把车卖掉。律师去世后，儿子为了这个遗嘱争论不休，这时一个数学家开了一辆汽车来悼念老朋友。三个儿子把他们的难题告诉了数学家，数学家沉思片刻后说，我有办法了。请问，他该怎么分配这些汽车？,约束方程系数矩阵的灵敏度分析,从前边的分析中，我们知道，单纯形法的实质是找到一个能得到最优解的基xB ，在约束条件中用其系数矩阵左乘一个B-1 ，同时令非基变量为0，得到最优解向量xB = B-1 b。从而我们可以得到如下结论，最终单纯形表中xi的系数列向量pi 事实上就是其初始系数列向量pi左乘以B-1 ，既pi = B-1 pi 。根据以上分析，我们可以得到约束方程技术系数变化时灵敏度分析的方法。,约束方程系数矩阵的灵敏度分析,例如，在例1-1中，列向量x4的系数列向量(用p4表示）在最终单纯形表中为（用p4表示）：,约束方程系数矩阵的灵敏度分析,根据以上分析我们可以得到系数矩阵灵敏度分析的思路。当基变量系数列向量改变时，用初始系数列向量左乘以B-1 后代入原最终单纯形表，在新的单纯形表中继续进行运算，得到最优解。当新加入决策变量时，意味着约束方程组中增加了列向量，将这个列向量左乘以B-1 后添加到原最终单纯形表中，继续运算得到最优解。,约束方程系数矩阵的灵敏度分析,在例1-1，为了增加安全性，当每辆大轿车使用钢材由2吨变为3吨时，求最优解有什么变化？工厂具备了生产旅行车的技术，每辆旅行车用钢材1.5吨，工时1.25小时，座椅0.25套，利润为每辆3千元，问该不该投产，如果投产有利可图，应该如何安排新的生产计划？,约束方程系数矩阵的灵敏度分析,当大轿车使用钢材变为3吨时，x1在最终单纯形表中的系数列向量变为：,约束方程系数矩阵的灵敏度分析,最终单纯形表变为：,约束方程系数矩阵的灵敏度分析,由于x1对应的列向量尚未化为单位向量，先进行迭代运算：,1800,约束方程系数矩阵的灵敏度分析,检验数仍然有负数，继续迭代：,约束方程系数矩阵的灵敏度分析,第二问，新增加一种产品，模型中增加了一个新列，设新产品产量为x6，增加的系数列向量在最终单纯形表中变为：,约束方程系数矩阵的灵敏度分析,最终单纯形表变为：,约束方程系数矩阵的灵敏度分析,检验数中存在负数，继续迭代：,约束方程系数矩阵的灵敏度分析,仍不是最优解，继续运算：,x1 x2 x3 x4 x5 x6,x Cj,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 0,b,4 4 2 0 0 3,3200,约束方程系数矩阵的灵敏度分析,求得最优解为： x1=200，x2=0，x3=0，x4=500，x5=0，x6=800，Z=3200。可见，生产旅行车是有利可图的，新的生产方案为：生产大轿车200辆，生产旅行车800辆，剩余工时500小时，利润为3200千元。,灵敏度分析小结,价值系数发生变化时： 1、如果是非基变量的系数发生变化，则只要该变量对应的检验数zj-cj在cj变化后仍然大于等于0，则最优解不发生任何变化。 2、如果是基变量的价值系数发生变化，则需要重新计算所有检验数，如果所有检验数仍然保持大于等于0，则最优基不变，但最优解一般会发生变化。如果有检验数变为负数，则在原最终单纯形表中继续迭代，求出最优解。,灵敏度分析小结,当资源向量发生改变时，用公式xB = B-1 b + B-1 b= xB + B-1 b（其中b=(0, 0, bk,0)T ）计算新的b列的值，如果新的b列的值仍然全部大于等于0，则最优基不变，但最优解的值一般会发生变化。如果计算出来的新的b列的值出现负数，则说明该解是不可行解，用对偶单纯形法继续进行迭代运算，求出新的最优解。,灵敏度分析小结,当基变量技术系数发生变化时，求出用公式pi = B-1 pi求出发生变化的系数所在列的数值，代替最终单纯形表中原来的列。然后用高斯消元法将该列化为单位向量，计算新的检验数。 1、如果检验数不为负数，则最优基不变。 2、如果新的检验数变为负数，则最优基将发生变化，用单纯形法继续迭代，求出新的最优解。,趣味数学,你作为幸运观众参加了一个节目，节目中你面对三个门，其中一个门后一辆汽车，另外两个门后各有一只羊。主持人请你选择一扇门，门后的物品将做为你的奖品。当你选择后，主持人先不打开门，而是打开一扇门后有羊的门，然后问你改变不改变你的选择，请问，你该不该改变你的选择？,作业,某公司制作三种产品A、B、C，需要劳动力和原材料两种资源，要求制订生产计划使总利润最大化。三种产品所需的资源和产生的利润如下表所示：,作业,1、请建立模型，解决最优生产计划问题。2、求出使得最优解不变的产品A的单位利润变动范围，问A产品的利润变为2时最优解变不变？3、假定原材料的市场价格是10元每单位，可以购买15个单位，问以10元的价格采购15单位原材料是否合算？4、请问原材料的供应在什么范围内变化时，不必改变生产计划？,作业,5、厂家研制出了一种新产品D，生产一单位D需要劳动力4单位，原材料3单位，而每单位的新产品D的利润为3元。请问：生产计划是否需要修改？为什么？该如何修改？,第三章 运 输 问 题,主要内容,运输问题的背景运输问题的模型运输问题的表上作业法运输问题的应用,运输问题的背景,在经济建设中，经常碰到大宗物资调运问题，如煤炭、钢铁、粮食等等。主产区和主销区往往不同，需要大规模的调运，将物资从产地供应到销地。大型企业有多个生产基地，销售遍及全国乃至全世界，如何分配供应计划使经济效益最好。,运输问题模型,运输问题 解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，且各地运输单价已知的前提下，如何确定一个使总的运输费用最小的方案。,运输问题模型,例1. 某公司从两个产地A1 , A2 ,将货物运往三个销地B1 , B2 , B3 ,各产地的产量、各销地的销量和各产地运往各销地的每件货物的运费如下表。问题：应如何调运，才能使得总运输费用最小？,运输问题模型,这是一个产销平衡的运输问题把A1， A2的产量全部分配给B1， B2， B3，,单 位 运 价 表,运输问题模型,设决策变量xij: 产地Ai调运到Bj的运输量（i=1,2;j=1,2,3),产销平衡表,运输问题模型,线性规划模型,运输问题模型,一般线性规划模型Ai表示某种物资的第i个产地Bj表示某种物资的第j个销地si表示产地Ai的产量dj表示销地Bj的销量cij表示把物资从产地Ai运到销地Bj的单位运价决策变量xij表示产地Ai调运到销地Bj的运输量,运输问题模型,xj 0, (i=1,2,m; j=1,2,n),运输问题模型,其他的运输问题模型产销平衡的运输问题: 当 时求目标函数最大的运输问题考虑利润最大、营业额最大具有能力限制的运输问题运输线路的能力限制产销不平衡的运输问题产大于销：假设销地销大于产：假设产地,运输问题模型,从模型中看，运输问题属于线性规划问题的一种。其特殊之处在于：约束条件系数矩阵全部为0-1元素，而且结构比较松散。系数矩阵中对应xij的系数向量，其分量中除第i个和第m+j个为1以外，其余的都为0。以例1的模型为例，考察其约束条件系数矩阵：,运输问题模型,表上作业法,表上作业法,表上作业法解决运输问题的单纯形法针对运输问题变量多，结构独特的特点，简化了运算假设问题为产销平衡的运输问题求解步骤1. 找出初始的基可行解运输问题有m+n-1个基变量在（mn）产销平衡表上给出m+n-1个数字格其相应的调运量就是基变量，格子中填写的值为基变量的值,表上作业法,2. 求各非基变量的检验数 在表上计算除了m+n-1个数字格以外的空格的检验数判别是否达到最优解如已是最优解, 则停止计算, 否则转下步3. 确定进基变量和出基变量找出新的基可行解在表上用闭回路法调整4. 重复第2、3步骤，直至得到最优解,表上作业法,产销平衡表,B1 B2 Bj Bn 产量限制,表上作业法,确定初始基可行解西北角法最小元素法西北角法从左上角的变量x11 开始分配运输量，并使x11的取值尽可能大依次类推，直至给出全部方案为止例2. 喜