管理运筹学 全套课件

管理运筹学数学的魅力与实质数学的本质是处理抽象对象，是比语言更精炼、更严谨的符号系统。是人类理性的集中体现。数学的方法是建立一个牢不可破的公理体系，并以演绎推理的方法去构建和扩展整个学科体系。数学分支数学分支数学分支应用演绎方法公理体系数学大厦数学的魅力与实质数学方法在自然科学体系中无处不在，并取得了光辉的成就。19世纪以后，数学被广泛深入地应用于社会科学领域。经济学、管理学领域的许多大师具有高超的数学技能。数学的魅力与实质本门课程不仅要学习一门课程，一套方法，更重要的是要学会理性 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的方法。培养逻辑思维能力和抽象思维能力。数学在发展的过程中遇到过许多问题，而且也并非确切无疑，大家要敢于质疑，敢于提问题。数学的魅力与实质一个例子：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分。运筹学的体系和发展历史定义运筹学是一门应用于管理有组织系统的科学它为掌管这类系统的人提供决策目标和数量分析的工具运筹学应用分析、实验、量化的方法，对经济 管理系统 工资管理系统慧云智能化管理系统免费考勤管理系统员工工资计算excel病人信息管理系统 中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，以实现最有效的管理正式起源与二次世界大战，被称为Operationsresearch,日本人翻译为运做学，台湾人翻译为作业研究运筹学的体系和发展历史田忌赛马萌芽在20世纪初，Lanchester战斗方程。丹麦工程师爱尔朗研究电话通讯系统时提出了一些排队论的公式。30年代，数学家列温逊运用运筹思想分析商业广告、顾客心理。运筹学的体系和发展历史二次世界大战中，英美科学家研究如何有效运用雷达，研究船队遇到袭击如何减少损失，以及如何使用深水炸弹等紧迫问题。应用：德国潜艇被摧毁数增加到400%，船只中弹数由47%减少到29%。结果：打赢了空战和海战，保证了二次世界大战的最终胜利。运筹学在现实生活中的例子企业安排生产计划库存管理公交系统优化食堂窗口设置电脑游戏，帝国时代、魔兽争霸等。运筹学的学科体系规划论：包括线性规划、非线性规划、整数规划等。1947年，Danzig提出单纯形法，随后规划方法得到了广泛的应用。图论与网络分析：图是研究离散事物之间关系的一种分析模型。例：有甲、乙、丙、丁、戊、己6名同学参加ABCDEF六个项目的比赛，下表是各运动员报名参赛的项目，问6个项目顺序如何安排，作到每名运动员不连续参加两项比赛。运筹学的学科体系**己**戊**丁**丙***乙**甲FEDCBA运筹学的学科体系排队论：研究公共服务系统的运行与优化的数学理论方法。决策论：研究不确定情况以及风险情况下的决策。存储论：研究企业的库存计划，进货周期等。博弈论：研究竞争环境下决策者行为的数学方法。运筹学的工作步骤提出和形成问题：弄清问题的目标，可能的约束，问题的可控变量，相关参数等。建立模型：把问题中的可控变量、参数、目标、约束之间的关系用一定的模型表示出来。求解：用计算或实验方法求出问题的解。解的检验：检查求解过程，检查解能否反映现实问题。解的实施：将解运用到实际问题中。第一章线性规划本章内容线性规划模型线性规划问题的图解法单纯形法非标准形线性规划的解法线性规划模型规划问题：就是否合理利用有限资源的问题。线性规划：线性的规划问题。两个意思：1、目标函数是线性的2、约束条件是线性的线性规划模型生产决策问题某汽车工厂生产大轿车和载重汽车两种型号的汽车,已知每辆汽车所用的钢材都是2吨/辆，该工厂每年供应的钢材为1600吨；工厂的生产能力是每2.5小时可生产一辆载重汽车，每5小时可生产一辆大轿车，工厂全年的有效工时为2500小时；已知供应给该厂大轿车用的座椅每年可装配400辆。据市场调查，出售一辆大轿车可获利4000元，出售一辆载重汽车可获利3000元。如何安排生产才能使工厂获利最大？线性规划模型建模型如下：设大轿车数量为x1,载重汽车数量为x2。s.t.是subjectto的简写，表示受限制于。线性规划模型某工厂在计划期间内生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示：111Ⅱ250Kg0原料B400Kg2原料A300台时1设备Ⅰ已知Ⅰ、Ⅱ两种产品每单位分别可以获利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为例：线性规划的图解法x2800400400800x1线性规划的图解法从图中可以得到：x1=200,x2=600,z=2600最优解为：生产200辆大轿车，生产600辆载重汽车，可获利润2600千元。钢材和工时全部用完，座椅剩余200套。几个概念凸集：设k是n维欧氏空间中的一个点集，在集合中任意取两点x1,x2∈k。如果这两点连线上的一切点都落在k中，则称k为凸集。角顶：设k为凸集，x∈k，如果不能用不同的两点x1,x2∈k线性表出x，则称x为k的一个角顶。角顶可行解和角顶不可行解：既是角顶解又是可行解的解称为角顶可行解，是角顶解而不是可行解的解称为角顶不可行解。图解法的几点启示线性规划的可行域必定为凸集。线性规划的最优解必定在顶点取得。如果有多个最优解，那么至少有两个相邻的角顶可行解是最优解。角顶可行解的数目是有限的。如果一个角顶可行解的目标函数值比相邻的所有角顶解好，它就是最优解。解决线性规划问题的思路基本思路是在满足约束条件的前提下，从一个初始顶点开始，不断寻找改进目标函数的顶点，直到无法改进为止。步骤1：从一个角顶可行解出发，判断相邻的角顶可行解是否比目前的点更好。如果相邻的角顶可行解都劣与这个顶点，则说明这个点已经是最优解，算法结束。步骤2：如果相邻的角顶可行解更好，就向这个点移动。重复步骤1。线性规划问题解的基本概念可行解：满足约束条件解称为可行解，对应图解法的阴影部分。基：约束条件中任意一个m阶非奇异子矩阵确定一个线性规划问题的基。对应图解法中的顶点。基可行解：既是可行解又是基解称为基可行解。最优解：满足目标函数和约束条件的解称为最优解。单纯形法求解单纯形法的步骤单纯形表法单纯形表法中的一些特殊情况求解单纯形法的步骤步骤1：将模型转化为标准形。步骤2：找到一个初始可行基，列出初始单纯形表。步骤3：判断初始可行基是否最优。如果是最优解则结束，否则转步骤4。步骤4：如果不是最优，则通过一定的规则将一个变量换出，另一个变量换入，构成一个新的基解。转步骤3。求解单纯形法的步骤x2800400400800x1求解单纯形法的步骤图形解法只能解决2维的线性规划问题（仅有两个变量）。对超过3维的情况，既无法在平面上画出图形，也无法进行直观的想象。根据图形解法的启示，提出单纯形法解决线性规划问题的基本思路。单纯形表法以例一为例：单纯形表法步骤1：首先转化为标准形式：添加松弛变量。单纯形表法步骤2：找到一个初始可行基。即寻找一个m阶的非奇异子矩阵。从标准形的线性规划问题中可以看出，x3,x4,x5构成了一个3阶的单位矩阵，把这三个变量作为初始可行基。列出初始单纯形表。单纯形表法列出初始单纯形表：x1x2x3x4x5xCjzjzj-cj430002210052.501010001bθ单纯形表法步骤3：确定换入换出变量。方法：先确定换入变量，计算检验数zj-cj，计算方法：，cj为对应xj的系数。以最负的检验数对应的系数列作为主列元素。随后确定换出变量，计算检验数θ，计算方法：，选择θ值最小的行对应的主列元素作为换出变量。单纯形表法确定换入换出变量：x1x2x3x4x5xCjzj-4-3000zj-cj00000430002210052.5010[1]0001bθ0单纯形表法步骤4：以主元素为中心，进行迭代运算。x1x2x3x4x5xCjzj0-3004zj-cj40004430000210-202.501-510001bθ1600单纯形表法检验数仍然有负数，继续确定换出换入变量x1x2x3x4x5xCjzj0-3004zj-cj40004430000210-202.501-510001bθ1600单纯形表法迭代运算x1x2x3x4x5xCjzj0001.2-2zj-cj4301.2-243000001-0.8[4]0100.4-210001bθ2200单纯形表法继续迭代：x1x2x3x4x5xCjzj0010.40zj-cj43000000.5-0.41010-0.4010-0.50.40b4310.402600单纯形表法从表中可以看出，检验数全部为正数或零，说明已达到最优。求得最优解为：x1=200，x2=600，x3=0，x4=0，x5=200，Z=2600。生产方案为：生产大轿车200辆，生产载重汽车600辆，剩余座椅200套，利润为2600千元。单纯形表法思考题1、用单纯形法求解线性规划问题时为什么要首先转化为标准形？2、为什么要选择松弛变量作为初始可行基，能不能任意选择几个变量作为初始可行基？作业求解线性规划问题：作业某工厂在计划期内要生产A、B两种产品，已知生产单位产品所需的设备台时及甲、乙两种原材料的消耗如下表所示：12公斤40原材料乙16公斤04原材料甲8台时21设备BA作业该工厂每生产一件产品A可以获利2元，每生产一件产品B可以获利3元，问应该如何安排计划使该工厂获利最多？要求：建立线性规划模型并用单纯形法求解。单纯形表法例2：用单纯形表法求解线性规划问题：单纯形表法步骤1：首先转化为标准形式：添加松弛变量。单纯形表法步骤2：找到一个初始可行基。从标准形的线性规划问题中可以看出，x3,x4,x5构成了一个3阶的单位矩阵，把这三个变量作为初始可行基。列出初始单纯形表。单纯形表法列出初始单纯形表：x1x2x3x4x5xCjzjzj-cj50100000111002101001001bθ单纯形表法步骤3：确定换入换出变量。确定换入变量，计算检验数zj-cj，计算方法：，cj为对应xj的系数。以最负的检验数对应的系数列作为主列元素。随后确定换出变量，计算检验数θ，计算方法：，选择θ值最小的行对应的主列元素作为换出变量。单纯形表法确定换入换出变量：x1x2x3x4x5xCjzj-50-100000zj-cj000005010000011100210100[1]001bθ0单纯形表法步骤4：以主元素为中心，进行迭代运算。x1x2x3x4x5xCjzj-500000zj-cj0100000501000001010-12001-101001bθ25000单纯形表法检验数仍然有负数，继续确定换出换入变量x1x2x3x4x5xCjzj-500000zj-cj010000050100000[1]010-12001-101001bθ25000单纯形表法迭代运算x1x2x3x4x5xCjzj0050050zj-cj5010050050501000001010-100-21101001bθ27500单纯形表法检验数全部大于等于0，已经求得最优解。最优解为：x1=50,x2=250,x3=0,x4=50,x5=0;Z=27500单纯形表法例3：某工厂在计划期内要生产A、B两种产品，已知生产单位产品所需的设备台时及甲、乙两种原材料的消耗如下表所示：12公斤40原材料乙16公斤04原材料甲8台时21设备BA单纯形表法该工厂每生产一件产品A可以获利2元，每生产一件产品B可以获利3元，问应该如何安排计划使该工厂获利最多？要求：建立线性规划模型并用单纯形法求解。单纯形表法A产品的产量设为x1，B产品的产量设为x2，建立模型如下：单纯形表法最终单纯形表为：x1x2x3x4x5xCjzj001.50.1250zj-cj231.50.1250230001000.25000-20.51010.5-0.1250bθ14单纯形表法中一些问题如果两个θ相同，有可能产生退化现象（死循环），可以用摄动法求解，就是选下标最小的变量作为换出变量。有一个以上的非基变量为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法列出初始单纯形表：x1x2x3x4x5xCjzj-3M-3–2M-5000zj-cj-3M-2M00-M3500-M[1]01000201032001bθ-18M大M法迭代计算-6M+12x1x2x3x4x5xCjzj0–2M-53M+300zj-cj3-2M3M+30-M3500-M10100020100[2]-301bθ大M法迭代运算x1x2x3x4x5xCjzj00-4.502.5+Mzj-cj35-4.502.53500-M101000031-101-1.500.5bθ27大M法迭代计算x1x2x3x4x5xCjzj0001.5M+1zj-cj3501.513500-M100-1/31/30011/3-1/30101/20bθ36大M法大于等于约束条件当出现大于等于约束条件时，首先添加一个剩余变量，使约束条件变为等式约束，然后再添加一个人工变量，用大M法求解。常数项为负数时，先在等式两边同乘-1，使资源变量变为正数，然后再根据相应情况进行处理。趣味数学这是基诺未能想出来的又一个悖论。一条蠕虫在橡皮绳的一端。橡皮绳长一公里。蠕虫以每秒1厘米的稳定速度沿橡皮绳爬行。在1秒钟之后，橡皮绳就像橡皮筋一样拉长为2公里。再过一秒钟后，它又拉长为3公里，如此下去。蠕虫最后究竟会不会达到终点呢？作业将本问题转化为标准形，并列出初始单纯形表。作业求解线性规划问题：第二章对偶理论和灵敏度分析本章内容对偶问题的提出原问题与对偶问题原问题与对偶问题的转化影子价格对偶问题的求解灵敏度分析对偶问题的提出对偶现象无论是从理论还是实践，对偶问题是线性规划最重要和最有趣的概念和理论刻划四边形面积与周长之间的关系周长一定的四边形中，面积为最大面积一定的四边形中，周长为最小一种现象的两种提法线性规划问题原问题：求目标最大对偶问题：求目标最小对偶问题的提出例1美佳公司计划制造Ⅰ、Ⅱ两种家电产品的生产，已知生产单位产品所需的设备A、B、C台时如下。该公司每生产一单位产品Ⅰ、Ⅱ可获利50元、100元。问：如何达到利润最大？ⅠⅡ资源限制设备A设备B设备C120111300台时400台时250台时对偶问题的提出例1的决策问题：生产多少个Ⅰ产品和Ⅱ产品才能使利润达到最大设决策变量x1为生产Ⅰ产品的数量，x2为生产Ⅱ产品的数量最大利润：maxz=50x1+100x2约束条件：x1+x2≤3002x1+x2≤400x2≤250x1，x2≥0对偶问题的提出生产产品，创造最大利润？出赁设备，确定合理租金？出赁设备总租金不应低于原利润全部设备的总租金越低越好对偶问题的提出设决策变量y1,y2,y3为设备A、B、C每台时的租金最小租金：minf=300y1+400y2+250y3原问题与对偶问题原问题某企业有m种资源，生产n种产品各种资源的拥有量为bi,xj为产量,aij为生产第j种产品所消耗第i种资源的数量，cj为产值原问题与对偶问题对偶问题出让资源，获取回报，付出代价条件：同等数量资源出让的代价应不低于组织生产的产值yi出让第i种资源付出的代价原问题与对偶问题两者的关系原问题对偶问题目标函数求最大约束条件的右端目标函数系数约束条件“≤”约束条件的行约束条件的列约束条件的个数原问题变量的个数目标函数求最小目标函数系数约束条件的右端约束条件“≥”约束条件的列约束条件的行对偶变量的个数约束条件的个数原问题与对偶问题的转化例2.写出下列问题的对偶问题及对偶的对偶问题原问题与对偶问题的转化对偶问题对偶的对偶问题原问题与对偶问题的转化原问题非对称形式原问题对称形式对偶问题目标函数求最小等式约束xj≤0xj取值无约束原问题与对偶问题的转化例3写出下述线性规划的对偶问题原问题与对偶问题的转化对偶问题影子价格原问题与对偶问题的重要性质Yi对一个第i种资源的估价，不是资源的市场价格是企业根据资源在生产中作出的贡献的估价影子价格：对资源在生产中作出的贡献的估价对偶变量Yi单位资源在最优利用条件下所产生的经济效果特征影子价格依赖于资源利用情况，是未知量。随生产任务、产品结构情况变化。影子价格一种边际价格：yi的值相当于在给定的生产条件下，bi每增加一个单位时，目标函数z的增加量一种机会成本当市场价格低于影子价格时，购进资源，增加生产，提高利润当市场价格高于影子价格时，出售资源，提高利润随着影子价格的买进和卖出，影子价格随之变动，直到影子价格与市场价格保持同等水平，才处于平衡影子价格线性规划的原问题是确定资源的最优分配方案，而对偶问题是确定对资源的恰当评估大公司借助资源的影子价格确定一些内部结算价格，以控制资源的使用和考核下属企业的经营状况在社会资源的有效配置中，可借助影子价格规定使用最紧缺资源一个单位必须上缴的利润额，以控制一些效益低的企业自觉节约使用紧缺资源对偶问题的求解利用原问题单纯形法确定初始基可行解转换为新基可行解建立最优解判断准则例4.求对偶问题的解对偶问题的求解对偶问题的求解用单纯形法解，添加两个剩余变量，两个人工变量，用大M法求解。非常麻烦，运算量比较大。当约束条件个数很多时，计算量成倍增加。对偶问题的性质弱对偶性，如果X，Y分别是原问题和对偶问题的可行解，则存在：CX≤YB对偶定理：若原问题有最优解，则对偶问题也有最优解，且目标函数值相等。解的互补松弛性：原问题的基变量对应于对偶问题的松弛变量的检验数，原问题的松弛变量对应于对偶问题的基变量的检验数。对偶单纯形法基本思想:在保持对偶问题为可行解的基础上,逐步迭代,减小目标值,当原问题也达到可行解时,得到了目标函数的最小值对偶问题的求解cjc1…cm…cj…cn基CBx1…xm…xj…xnb………………j=zj-cj0…0……对偶问题的求解步骤1：根据线性规划问题，列出初始单纯形表，检查b列数字，若都为非负，检验数也均为非负，则已经得到最优解。否则转步骤2。步骤2：确定换出变量，选择最负的基变量为换出变量。步骤3：确定换入变量，如果换出变量对应的行系数全部非负，则无可行解。否则，用换出变量那一行具有负值的系数分别去除同列的检验数，取绝对值最小者对应的变量为换入变量。对偶问题的求解步骤4：以换入变量对应的行和换出变量对应的列交点对应的元素做为主元素，进行迭代运算，得到新的单纯形表。步骤5：最优性检验，如果b列元素和检验数全部为非负，则已得到最优解，否则转步骤2。对偶单纯形法步骤1：转换并列出初始单纯形表对偶单纯形法:初始单纯形表by1y2y3y4y5YCjzj30040025000zj-cj000000-300-400-25000-1-2010-1-1-101b列系数为负，检验数为正，说明原问题为可行解，而对偶问题为不可行解。转步骤2。对偶单纯形法:确定换入换出变量y1y2y3y4y5YCjzj30040025000zj-cj000000-300-400-25000-1-2010-1-1[-1]01选b列系数最负的值为换出变量，用换出变量那一行具有负值的系数分别去除同列的检验数，取绝对值最小者对应的变量为换入变量，转步骤4。b对偶单纯形法:迭代运算y1y2y3y4y5YCjzj5015000250zj-cj-250-250-2500250-25000-300-400-25000-1-20101110-1以换入变量对应的行和换出变量对应的列交点对应的元素做为主元素，进行迭代运算，得到新的单纯形表。b列系数仍存在负数，转步骤2。b对偶单纯形法:确定换入换出变量y1y2y3y4y5YCjzj5015000250zj-cj-250-250-2500250-25000-300-400-25000[-1]-20101110-1以换入变量对应的行和换出变量对应的列交点对应的元素做为主元素，进行迭代运算，得到新的单纯形表。b列系数仍存在负数，转步骤2。b对偶单纯形法:迭代运算y1y2y3y4y5YCjzj050050250zj-cj-300-350-25050250-27500-300-400-25000120-100-111-1以第一行和第一列交点对应的元素做为主元素，进行迭代运算，得到新的单纯形表。b列系数全部非负，检验数也全部非负，已求得最优解。b对偶单纯形法：解的说明Y=（50,0,50,0,0），-f=-27500即f=27500。与原问题比较可以看到，y1,y3恰好是原问题第一、第三个约束条件的松弛变量。检验数恰好是原问题的解。这就是所谓的互补松弛性。原问题与对偶问题的最优解相同。对偶单纯形法例5.求对偶问题的解对偶单纯形法例5的最终单纯形表如下：y1y2y3y4y5YCjzj001.81.60.2zj-cj-2-3-2.21.60.2-5.6-2-3-40001-0.2-0.40.2101.4-0.2-0.4b对偶单纯形法初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，可以简化计算。当变量多于约束条件时，用对偶单纯形法可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先转化为对偶问题，然后用对偶单纯形法求解。在灵敏度分析中，有时需要用对偶单纯形法，这样可以使问题简化。对偶单纯形法：作业1、什么是资源的影子价格，同相应的市场价格之间有何区别，研究影子价格的意义何在。2、试述对偶单纯形法的计算步骤，它的优点及应用上的局限性。3、写出线性规划问题的对偶问题：对偶单纯形法：作业用对偶单纯形法求解以下问题：灵敏度分析由于市场条件、工艺条件以及企业规模的变化，价值系数、资源向量、技术系数等都会发生变化。提出两个问题：一、当这些系数有一个或几个发生变化时，最优解会发生变化；二、这些系数在什么范围内变化时，线性规划问题的最优解不变。如果每有参数发生变化就重新构建模型计算，太麻烦，也没有必要。可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，进行分析。灵敏度分析价值系数的灵敏度分析资源向量的灵敏度分析约束方程系数矩阵的灵敏度分析决策变量增减的灵敏度分析约束条件增减的灵敏度分析价值系数的灵敏度分析某工厂在计划期间内生产1、2、3三种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示：402212Kg00原料B16Kg84原料A8台时21设备311、2、3每单位产品分别可以获利2元，3元，a元，求如何安排生产可以使工厂利润最大。价值系数的灵敏度分析线性规划问题：问，当a=1，2，3，5时，最优解分别为多少，最优基分别为那些变量。价值系数的灵敏度分析当a=1时，最终单纯形表如下：x1x2x3x4x5x6xCjzj0031.50.1250zj-cj2341.50.125023100010200.250000-20.510100.5-0.1250bθ14价值系数的灵敏度分析当a=2时，最终单纯形表如下：x1x2x3x4x5x6xCjzj0021.50.1250zj-cj2341.50.125023200010200.250000-20.510100.5-0.1250bθ14价值系数的灵敏度分析当a=3时，最终单纯形表如下：x1x2x3x4x5x6xCjzj0011.50.1250zj-cj2341.50.125023300010200.250000-20.510100.5-0.1250bθ14价值系数的灵敏度分析当a=5时，最终单纯形表如下：x1x2x3x4x5x6xCjzj0.5001.50.250zj-cj2.5351.50.2502350000100.5-0.12500.50100.1250000-20.51bθ16价值系数的灵敏度分析当a=1，2，3时，zj-cj≥0，最终单纯形表基本没有改变，最优解没有改变，仅有x3的检验数有所不同。当a=5时，zj-cj≤0，最优基改变，最终单纯形表也发生改变。当最优基发生变化时，事实上我们不必重新进行全部计算，只需要在原来最终单纯形表的基础上继续迭代就可以得到最优解。价值系数的灵敏度分析当a由3变为5时：x1x2x3x4x5x6xCjzj00-11.50.1250zj-cj2341.50.125023500010[2]00.250000-20.510100.5-0.1250bθ14价值系数的灵敏度分析从上图中看到，检验数仍存在负数，继续迭代。x1x2x3x4x5x6xCjzj0.5001.50.250zj-cj2.5351.50.2502350000.50100.1250000-20.510100.5-0.1250bθ16价值系数的灵敏度分析非基变量价值系数变化价值系数不在基变量中，zj保持不变，所以检验数zj-cj变化Δcj（为正数），要保持最优解不变，只要Δcj≤zj-cj。基变量价值系数变化基变量价值系数发生变化时，只需将新的价值系数代入最终单纯形表中，检查检验数，如果检验数仍保持为正，则最优基不变，但最优解的值会发生变化。如果检验数出现负数，则以原最终单纯形表为基础，继续进行迭代运算。资源向量的灵敏度分析单纯形法的实质是找到一个能得到最优解的基xB，在约束条件中用其系数矩阵左乘一个B-1，令非基变量为0，得到最优解向量xB=B-1b。事实上迭代过程也是用矩阵初等变换求B的逆矩阵B-1的过程。最终单纯形表中的b列其实就是B-1b，当第k个资源向量bk变为bk+Δbk时，也就是原来单纯形表中的b向量变成了b’向量。资源向量的灵敏度分析令Δb=(0,0,…Δbk,…0)T，则有b’=b+Δb，这样最终单纯形表中基变量xB的解就变成了xB’=B-1(b+Δb）=B-1b+B-1Δb。要使xB仍然为最优解，只要B-1b+B-1Δb>0即可。如果bk的变化使得B-1b+B-1Δb<0，这时最优解的基就要发生变化，这种情况下用对偶单纯形法继续求出新的最优解。资源向量的灵敏度分析例：课本P6例1-1中，如果钢材的供应数量发生变化，请问1、钢材供应量在什么范围内变化时，最优基不会发生改变？2、当钢材的供应量增加到2200吨时，应当如何安排生产计划？资源向量的灵敏度分析如果例1-1中的钢材供应数量变为1600+Δb1，最终解将变为：xB’=B-1b’=B-1(b+Δb）==资源向量的灵敏度分析要保证最优基不改变，要求b’中所有向量大于等于0，即：从（1）式中可得：Δb1≥-400，从（2）式中可得：Δb1≥-600，从（3）式中可得：Δb1≤400，得到-400≤Δb1≤400，也就是说，钢材供应量在1200到2000之间时，最优基不发生变化。资源向量的灵敏度分析资源向量在一定范围内变化时，最优基虽然不会发生变化，但最优解则会发生变化。最优基不变时，可以直接将发生变化的资源向量代入B-1b’中，得到新的最优解的值。例如，当钢材供应量变为2000时，新的最优解的求解如下：资源向量的灵敏度分析资源向量的灵敏度分析当钢材的供应量增加到2200吨时：资源向量出现负数，不再是可行解，需要继续迭代，用对偶单纯形法。资源向量的灵敏度分析最终单纯形表变为：x1x2x3x4x5xCjzj0010.40zj-cj4310.4043000000.5-0.41011-0.4010[-0.5]0.40b3200资源向量的灵敏度分析以主元素为中心进行迭代运算：x1x2x3x4x5xCjzj2001.20zj-cj6321.2043000100012100.40-201-0.80b3000趣味数学一个富有的律师拥有11辆古董汽车，每辆值5000美元。律师死时留下了一个奇怪的遗嘱。他说他的11辆古董汽车分给他的三个儿子。把其中的一半分给长子，1/4分给次子，1/6分给小儿子。同时规定不能把车卖掉。律师去世后，儿子为了这个遗嘱争论不休，这时一个数学家开了一辆汽车来悼念老朋友。三个儿子把他们的难题告诉了数学家，数学家沉思片刻后说，我有 办法 鲁班奖评选办法下载鲁班奖评选办法下载鲁班奖评选办法下载企业年金办法下载企业年金办法下载 了。请问，他该怎么分配这些汽车？约束方程系数矩阵的灵敏度分析从前边的分析中，我们知道，单纯形法的实质是找到一个能得到最优解的基xB，在约束条件中用其系数矩阵左乘一个B-1，同时令非基变量为0，得到最优解向量xB=B-1b。从而我们可以得到如下结论，最终单纯形表中xi的系数列向量pi’事实上就是其初始系数列向量pi左乘以B-1，既pi’=B-1pi。根据以上分析，我们可以得到约束方程技术系数变化时灵敏度分析的方法。约束方程系数矩阵的灵敏度分析例如，在例1-1中，列向量x4的系数列向量(用p4表示）在最终单纯形表中为（用p4’表示）：约束方程系数矩阵的灵敏度分析根据以上分析我们可以得到系数矩阵灵敏度分析的思路。当基变量系数列向量改变时，用初始系数列向量左乘以B-1后代入原最终单纯形表，在新的单纯形表中继续进行运算，得到最优解。当新加入决策变量时，意味着约束方程组中增加了列向量，将这个列向量左乘以B-1后添加到原最终单纯形表中，继续运算得到最优解。约束方程系数矩阵的灵敏度分析在例1-1，为了增加安全性，当每辆大轿车使用钢材由2吨变为3吨时，求最优解有什么变化？工厂具备了生产旅行车的技术，每辆旅行车用钢材1.5吨，工时1.25小时，座椅0.25套，利润为每辆3千元，问该不该投产，如果投产有利可图，应该如何安排新的生产计划？约束方程系数矩阵的灵敏度分析当大轿车使用钢材变为3吨时，x1在最终单纯形表中的系数列向量变为：约束方程系数矩阵的灵敏度分析最终单纯形表变为：x1x2x3x4x5xCjzjzj-cj430000.500.5-0.41111-0.400.50-0.50.40b约束方程系数矩阵的灵敏度分析由于x1对应的列向量尚未化为单位向量，先进行迭代运算：x1x2x3x4x5xCjzj002-0.40zj-cj43000001-0.81012-1.2010-1[0.8]0b432-0.40θ1800约束方程系数矩阵的灵敏度分析检验数仍然有负数，继续迭代：x1x2x3x4x5xCjzj0.501.500zj-cj43000101011.510.5001.250-1.2510b4.531.500θ2400约束方程系数矩阵的灵敏度分析第二问，新增加一种产品，模型中增加了一个新列，设新产品产量为x6，增加的系数列向量在最终单纯形表中变为：约束方程系数矩阵的灵敏度分析最终单纯形表变为：x1x2x3x4x5x6xCjzj0010.40-1zj-cj430003001-0.41[0.5]010.5-0.40110-0.50.40-0.25b4310.402θ2600约束方程系数矩阵的灵敏度分析检验数中存在负数，继续迭代：x1x2x3x4x5x6xCjzj002-0.420zj-cj430003001-0.821010[0.4]-2010-0.250.20.50b432-0.423θ3000约束方程系数矩阵的灵敏度分析仍不是最优解，继续运算：x1x2x3x4x5x6xCjzj012000zj-cj4300030210-2102.501-501-0.5-0.2501.50b442003θ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-1b+B-1Δb=xB+B-1Δb（其中Δb=(0,0,…Δbk,…0)T）计算新的b列的值，如果新的b列的值仍然全部大于等于0，则最优基不变，但最优解的值一般会发生变化。如果计算出来的新的b列的值出现负数，则说明该解是不可行解，用对偶单纯形法继续进行迭代运算，求出新的最优解。灵敏度分析小结当基变量技术系数发生变化时，求出用公式pi’=B-1pi求出发生变化的系数所在列的数值，代替最终单纯形表中原来的列。然后用高斯消元法将该列化为单位向量，计算新的检验数。1、如果检验数不为负数，则最优基不变。2、如果新的检验数变为负数，则最优基将发生变化，用单纯形法继续迭代，求出新的最优解。趣味数学你作为幸运观众参加了一个节目，节目中你面对三个门，其中一个门后一辆汽车，另外两个门后各有一只羊。主持人请你选择一扇门，门后的物品将做为你的奖品。当你选择后，主持人先不打开门，而是打开一扇门后有羊的门，然后问你改变不改变你的选择，请问，你该不该改变你的选择？作业某公司制作三种产品A、B、C，需要劳动力和原材料两种资源，要求制订生产计划使总利润最大化。三种产品所需的资源和产生的利润如下表所示：513利润30543原材料45536劳动力资源CBA作业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，销地运费单价产地A1646200A2655300销量150150200B1B2B3产量（件）单位运价表运输问题模型设决策变量xij:产地Ai调运到Bj的运输量（i=1,2;j=1,2,3)销地运费量产地A1x11x12x13200A2x21x22x23300销量150150200500B1B2B3产量（件）产销平衡表运输问题模型线性规划模型运输问题模型一般线性规划模型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的模型为例，考察其约束条件系数矩阵：运输问题模型表上作业法分析实际问题列出产销平衡表确定初始调运方案西北角法最小元素法求检验数（闭回路法或位势法）所有检验数0得到最优方案算出总的运价找出绝对值最大的负检验数用闭回路调整得出新的调运方案是否表上作业法表上作业法解决运输问题的单纯形法针对运输问题变量多，结构独特的特点，简化了运算假设问题为产销平衡的运输问题求解步骤1.找出初始的基可行解运输问题有m+n-1个基变量在（mn）产销平衡表上给出m+n-1个数字格其相应的调运量就是基变量，格子中填写的值为基变量的值表上作业法2.求各非基变量的检验数在表上计算除了m+n-1个数字格以外的空格的检验数判别是否达到最优解如已是最优解,则停止计算,否则转下步3.确定进基变量和出基变量找出新的基可行解在表上用闭回路法调整4.重复第2、3步骤，直至得到最优解表上作业法产销平衡表B1B2BjBn产量限制c1n销地产地A1A2Amc11销量限制c12c1jx11s1s2siAismc21c22c23c24ci1ci2cijcincm1cm2cmjcmnd1d2djdnx12x1nx21x22x2nxm1xm2xmn表上作业法确定初始基可行解西北角法最小元素法西北角法从左上角的变量x11开始分配运输量，并使x11的取值尽可能大依次类推，直至给出全部方案为止例2.喜庆食品公司有三个生产面包的分厂A1,A2,A3,有四个销售公司B1,B2,B3,B4,其各分厂每日的产量、各销售公司每日的销量以及各分厂到各表上作业法销地运费单价产地A13113107A219284销量(吨)3656B1B2B3B4产量（吨）2020A3741059销售公司的单位运价如下表。产量与销量的单位为吨，运价的单位为百元/吨。问该公司应如何调运产品在满足各销点需求量的前提下，使总运费最少？表上作业法可行方案为:x11=3,x12=4,,x22=2,x23=2,x33=3,x34=6,minf=1353销地产地A1A2B1B2B3B4产量（吨）A3311310192874105销量(吨)365674904402202230306600表上作业法最小元素法西北角法是对西北角的变量分配运输量最小元素法是就近供应,对单位运价最小的变量分配运输量用最小元素法求的初始基可行解比西北角法的总运费要小通常迭代的次数可能会少表上作业法可行方案为:x13=4,x14=3,,x21=3,x23=1,x32=6,x34=3,minf=86销地产地A1A2B1B2B3B4产量（吨）A3311310192874105销量(吨)3656749301140406303303300表上作业法注意当取定xij的值之后,会出现Ai的产量与Bj的销量都为零的情况,只能划去Ai行或Bj列,不能同时划去用最小元素法时,可能会出现只剩一行或一列的所有格均未填数或未划掉的情况,此时在这一行或这一列中除去已填上的数外均填上零,不能将空格划掉这样可保证填过数或行的格为m+n-1个,即基变量的个数为m+n-1个表上作业法最优解的判定检验已得到的运输方案是否为最优方案闭回路法位势法闭回路法闭回路的构成在已给出的调运方案的运输表上，从代表非基变量的一个空格出发沿水平或垂直方向前进，只有碰到代表基变量的有数字的格才能向左或右转直到回到出发的空格表上作业法销地产地A1A2B1B2B3B4产量（吨）A3311310192874105销量(吨)36567493416331x11为非基变量的闭回路表上作业法检验数的计算：从（A1，B1）出发，增加一单位调运量（从A1运到B1），为保持产销平衡，依次做调整：在（A1，B3）处减少1吨，（A2，B3）处增加1吨，（A2，B1）处减少1吨。调整方案使运费增加：1*3+（-1）*3+1*2+（-1）*1=1，可见这样调整将每单位增加运费1，将1填入（A1，B1）。所有非基变量的闭回路及检验数表上作业法空格闭回路检验数x11x11-----x13-----x23-----x21-----x11x12-----x14-----x34-----x32-----x12x12x22x24x31x33x22---x23---x13---x14---x34---x32---x22x24-----x23-----x33-----x14-----x24x31---x34---x14---x13---x23---x21---x31x33-----x34-----x14-----x13-----x33121-11012表上作业法闭回路法在以空格为始点和终点，其他顶点均为数字点的闭回路上将该空格的运输量调整为1，则其他顶点在保持供销平衡的基础上，运输量增加或减少1计算出该回路的总费用的变化值该变化值作为该非基变量的检验数若所有检验数都大于零，则原基可行解为最优解否则进一步迭代找出最优解用闭回路法求检验数要对每一个空格找一条闭回路当产销点多时，较繁杂表上作业法位势法将运输表上的每一行赋予值ui,每一列赋予值vjxij为基变量，则满足cij-ui-vj=0令u1=0，可先计算出ui和vj的值xij为非基变量，则利用ui和vj的值，计算出其检验数ij=cij-ui-vj若所有检验数ij均大于零，则原基可行解为最优解否则进一步迭代找出最优解表上作业法例1中检验数的计算：令u1=0，将基变量的检验数列出：由基变量x14，有c14–(u1+v4)=0由基变量x13，有c13–(u1+v3)=0由基变量x21，有c21–(u2+v1)=0由基变量x23，有c23–(u2+v3)=0由基变量x32，有c32–(u3+v2)=0由基变量x34，有c34–(u3+v4)=0表上作业法即：8–(u1+v4)=0，5–(u1+v3)=01–(u2+v1)=0，4–(u2+v3)=03–(u3+v2)=0，10–(u3+v4)=0又知u1=0，所以得到：u1=0，u2=-1，u3=-5，v1=2,v2=9,v3=3,v4=10。因非基变量的检验数ij=cij-ui-vj，已知所有ui、vj的值，可以在表格中计算所有非基变量的检验数。销地产地A1(1)(2)430A23(1)1(-1)-129310B1B2B3B4uiA3(10)6(12)3-5311310192874105vj表上作业法表上作业法改进运输方案的方法—闭回路调整法选最小的负检验数，以它对应的非基变量为进基变量找出以该非基变量空格xij为出发点的闭回路尽量增加xij的运输量将该回路中的偶数顶点调运量的最小值取为xij的运输量将所有回路中的偶数顶点的调运量减去该值，而奇数顶点加上该值，得到新的调运方案销地产地A1(1)(2)430A23(1)1(-1)-129310B1B2B3B4uiA3(10)6(12)3-5311310192874105vj表上作业法表上作业法销地产地A14（+1）3（-1）7A231（-1）（+1）4销量3656B1B2B3B4产量A3639表上作业法调整后的运输方案如下销地产地A1527A2314销量3656B1B2B3B4产量A3639运输量表上作业法用位势法再计算出检验数如下表：所有检验数都大于零，最小费用为85元销地产地A1(0)(2)520A23(2)（1）1-239310B1B2B3B4uiA3(9)6(12)3-5311310192874105vj表上作业法如何找多个最优方案识别是否有最优方案的方法与单纯形法一样只需检查最优方案中是否存在非基变量的检验数为零将检验数为零的非基变量进入基，对运输方案进行调整，就可得到另一个最优方案见下例表上作业法由前面的表中可知：x11的检验数11=0令x11进入基，调整的运输方案为另一个最优方案销地产地A1（+2）52（-2）7A23（-2）1（+2）4B1B2B3B4产量A3639销量3656表上作业法此时的最小运费仍为85销地产地A1257A2134B1B2B3B4产量A3639销量3656产销不平衡的运输问题对于产大于销的运输问题，可以用增加一个虚拟销地的方法转化为产销平衡的运输问题，任何一个产地运往虚拟销地的运费均设为0。对于销大于产的运输问题，可以用增加一个虚拟产地的方法转化为产销平衡的运输问题，虚拟产地运往任何一个销地的运费均设为0。产销不平衡的运输问题例2：某产品的供求表如下，请给出最佳调运方案。销地运费单价产地A13113107A219287销量(吨)3656B1B2B3B4产量（吨）2320A3741059产销不平衡的运输问题首先转化为产销平衡的运输问题：B1B2B3B4B5产量销地运费单价产地A131131007A2192807销量(吨)365632323A37410509产销不平衡的运输问题用最小元素法求出初始可行解：B1B2B3B4B5产量销地运费单价产地A11337A2347销量(吨)365632323A3639产销不平衡的运输问题用位势法求出非基变量的检验数得：B1B2B3B4B5产量销地运费单价产地A1（1）（2）1337A23（1）4（-1）（0）7销量(吨)365632323A3（10）6（12）3（5）9产销不平衡的运输问题检验数存在负数，用闭回路