管理运筹学教学课件

绪论运筹学是一门解决实际问题的新兴学科，它在国民经济和科学技术的各个领域有着广泛的应用。它以人类对各种资源的分配和使用为研究对象，目的在于探索人类对各种资分配和使用活动的基本规律，以便发挥有限资源的最大效益，来达到全局最优的目标。它的基本特点是强调研究过程的完整性，强调理论与实践的紧密结合，强调数学模型的构造。美国实验心理学家威廉.詹姆士说过：播下一种思想，收获一种行为；播下一种行为，收获一种习惯；播下一种习惯，收获一种性格；播下一种性格，收获一种命运。

我们希望在当代大学生的思维模式中播下运筹学的思想

威廉.詹姆士美国实验心理学家1842.1.11日—1910.8.26开设运筹学的必要性

在多年从事运筹学课程教学的实践中发现，许多大学生以及从事规划、投资、决策、管理等领域工作的各级行政管理干部和公司企业管理者，对运筹学既爱又怕，他们很多人从千古名句“运筹帷帐中，决胜千里外”知道运筹学的名称，喜爱运筹学的巧妙思路，希望自己具有运筹帷幄、决胜千里的能力，但又畏惧运筹学复杂的数学计算，这导致他们无缘接受运筹学的学习.

开设运筹学的必要性

为了帮助学生掌握好运筹学的思想和方法，提高分析、解决实际问题的能力，本课程以运筹学的思想、方法为主，表述通俗易懂，讲清方法思路，使读者理解、掌握运筹学的思想、方法的实质.

开设运筹学的必要性教学中突出三个方面：一是如何将一个实际问题提炼成一个运筹学问题；二是如何借助软件求解，最后落实到一个“用”字上，在讲清楚概念、原理的基础上，借助计算机技术，解决复杂的数学推理过程；三是在授课过程中提供大量实际应用案例，充分调动学生的学习积极性。教会学生运用运筹学的思维方法看问题、想问题、做出科学决策。开设运筹学的必要性课程理念学习运筹学的关键是掌握使用运筹学思想方法解决实际问题的能力，善于优化利用资源.运筹学的本质，具体说就是在做决策时：首先要考虑做的事情是否有价值？其次要考虑自己是否有资源和能力完成这个计划？如果资源或能力不足，从哪里可以获得支持？善于发现资源和找到支持去完成有价值的决策，同时又能优化利用资源，才能形成竞争力.运筹学（OperationalResearch）诞生于第二次世界大战期间，由于反法西斯战争的需要发展起来的一门新兴学科.研究对象：人类对各种资源的运用及筹划活动.研究目的:了解和发现这种运用及筹划活动的基本规律，以便发挥有限资源的最大效益，来达到全局最优的目标.运筹学研究的重要特点:强调研究过程的完整性、强调理论与实践的结合，构造数学模型是运筹学中最重要的方法.应用范围:遍及工农业生产、经济管理、科学技术、国防事业等各方面.运筹学的起源1.运筹学的军事起源

军事是运筹学的第一个起源.运筹学思想方法的起源可追溯到古代.人们发现,在我国先秦时期的诸子著作中,就存在许多朴素的运筹思想.被后世称为兵圣的我国春秋时期（公元前770年—公元前476年）军事家孙武,在他的著作《孙子兵法》一书中,体现了丰富的运筹思想,孙武首先将度、量、数等概念引人军事领域,通过必要的计算来预测战争的胜负并指导战争中的有关行为.运筹学的起源在国外，运筹学思想方法也可追溯到很早以前.阿基米德、达芬奇、伽利略都研究过作战问题.阿基米德(约公元前287～212是古希腊物理学家、数学家

达·芬奇(1452-1519)意大利文艺复兴时期最负盛名的美术家、雕塑家、建筑家、工程师、机械师、科学巨匠和发明家伽利略(1564～1642)意大利文艺复兴后期伟大的天文学家、力学家、哲学家、物理学家，被誉为近代科学之父运筹学的起源现代进行的运筹学工作最早是以希尔(A.V.Hill)为首的英国国防部防空试验小组在第一次世界大战期间进行的高射炮系统利用研究.英国人莫尔斯建立的分析美国海军横跨大西洋护航队损失的数学模型，也是运筹学的早期工作，这一工作在第二次世界大战中有了深入而全面的发展.运筹学的起源1916年，英国的兰彻斯特(F.W.Lanchester，1868～1946)指出了军队的数量优势、火力和胜负的动态关系，这种动态关系后来被人们称为兰彻斯特方程.美国人爱迪生用数学中的博弈论和统计分析方法研究出了商船避免德国潜艇袭击的航行策略，虽未被采用，但却对以后运筹学的发展有所影响.运筹学的起源1935年，英国科学家沃森·瓦特（R.WatsonWart）发明了雷达.当时任英国海军大臣的丘吉尔敏锐地认识到雷达的重要意义，下令在英国东海岸的鲍得西（Bawdsey）建立了一个秘密的雷达站.Watson-Watt(1892～1973)英国物理学家和雷达技术专家。1935年2月，他提出《采用无线电方法探测飞机》的秘密备忘录，并在当年研制成功探测距离达到80公里的米波防空雷达。1938年在沃森－瓦特主持下在英国东海岸建成防空雷达网，以后又建立了第二个雷达网。雷达网在1940年击败纳粹德国的空袭中起了重要的作用。运筹学的起源1939年，由英国曼彻斯特大学物理学家、英国战斗机司令部科学顾问、战后获得诺贝尔奖的布莱凯特（P.M.S.Blackett，1897～1974）为首，组建了一个代号为“Blackett马戏团”的研究小组,专门就改进防空系统进行研究.运筹学的起源第二次世界大战中，运筹学被广泛应用于军事系统工程中去，除英国外，美国、加拿大等国也相继成立了军事运筹研究小组，解决战争中提出的运筹学课题，其中最著名的工作之一是改进深水炸弹的起爆深度.当时德国的潜水艇严重威胁盟军的运输船，于是研究如何用飞机投掷深水炸弹，有效摧毁敌军潜艇就成为当务之急.1942年，美国大西洋舰队主持反潜战的官员贝克（W.D.Baker）请求成立反潜战运筹组，麻省理工学院的物理学家莫尔斯（P.W.Morse）被请来担任计划与监督.莫尔斯最出色的工作之一是协助英国打破了德国对英吉利海峡的海上封锁.

运筹学的起源莫尔斯领导的小组经过多方实地调查，提出两条重要建议：（1）将反潜攻击由反潜舰艇投掷水雷改为由飞机投掷深水炸弹；仅当潜艇浮出水面或刚下潜时，方投掷深水炸弹；深水炸弹的定深（指起爆深度）由100-200英尺，修正为20-50英尺.（2）改进运送物资的船队及护航舰艇编队的方式，由小规模多批次，改进为加大规模、减少批次，可使损失减少.

运筹学的起源军方采用了上述建议，重创德国潜艇舰队，最终成功地打破了德国的海上封锁.此外，在对潜艇的有效搜索、合理安排飞机维修、提高飞机的利用率等许多问题的解决，运筹学发挥了重要作用.这些运筹学成果对盟军大西洋海战的胜利起了十分重要的作用，对许多战斗的胜利也起了积极的作用.

运筹学的起源战争结束时，英美及加拿大军队中工作的运筹学工作者已超过了700人.正是由于战争需要的促进，以及大批著名科学家的参与，运筹学得到迅速发展.第二次世界大战期间的军事运筹问题及其解决方法，具有如下的特点：（1）数据是实践中的真实数据；（2）解决问题的人员组成是多学科的；（3）处理问题的方法渗透着物理学的思想.运筹学的起源第二次世界大战结束后，英国军方的一份《总结报告》曾说：“这种有资深科学家进行的，改善海军技术和物质运作的科学方法，被称为运筹学”，“和以往的历次战争相比，这次战争更是新的技术策略和反策略的较量……我们在几次关键战役中加快了反应速度，运筹学使我们赢得了胜利.”运筹学的起源第二次世界大战后，运筹学从单纯军事和战争中的应用研究，扩展到经济和管理领域，并形成了自己的理论与方法.1948年，美国麻省理工学院率先开设了运筹学课程，许多大学群起效法，内容也日益丰富.1950年，美国出版了第一份运筹学杂志；运筹学的起源1951年，莫尔斯（PhilipM.Morse,1903-1985）和金博尔(GeorgeE.Kimball,1906-1967)出版了（1946年内部出版，1951年公开出版）第一本运筹学专著：《运筹学的方法》（TheMethodsofOperationsResearch）。书中总结了第二次世界大战中运筹学的军事应用，并且给出了运筹学的一个著名定义：运筹学是为执行部门对它们控制下的“业务”活动采取决策提供定量依据的科学方法。运筹学的起源2.运筹学的管理起源运筹学的第二个起源是管理.第一次世界大战前就已经发展成熟的古典管理学派，对运筹学的产生和发展影响很大.1911年，泰勒(F.W.Taylor，美国人，科学管理之父)出版了著名的《科学管理原理》一书.在这本书中，泰勒的管理思想和理论，概括起来主要有以下三个观点：运筹学的起源（1）科学管理的根本目的是谋求最高工作效率.（2）达到最高工作效率的重要手段是科学的管理方法.（3）实施科学管理要求精神上的彻底变革.运筹学的起源（1）最佳动作原理.（2）合理的日工作量或恰当的工作定额原理.（3）第一流工人制.（4）刺激性付酬制度.（5）职能管理原理或职能工长制.（6）例外原理.根据以上观点泰勒提出以下管理制度：

运筹学的起源与泰勒同时代的，对管理改革作出贡献的还有一些学者，其中具有代表性的人物有：

亨利·L·甘特(Henry·L·Gantt，1861-1919)

弗兰克·杰尔布雷斯(FrankGilbreth，1868-1924)夫妇.运筹学的起源甘特曾是泰勒的亲密合作者，科学管理运动的先驱之一.1902年至1919年期间，他作为一个独立开业的咨询师进行工作，并在哈佛大学、耶鲁大学、哥伦比亚大学等著名高校任教.甘特的贡献主要有以下几点：1．提出了一种“工资任务加奖金”的工资制度.2．1903年，发明了“甘特图”（也称黑道图）.至今还在实践中使用，并发展为统筹方法.3．强调管理民主和重视人的领导方式.运筹学的起源弗兰克·杰尔布雷斯夫妇，他们以进行动作研究而著称，比较有影响的著作有：《动作研究》（1911年）、《科学管理入门》（1912年）以及《疲劳研究》（1916年）等.他们的研究比泰勒的研究更为细致和广泛，其重要贡献在以下几方面：1．提出动作研究和动作经济原理.2．疲劳研究.3．注意到了工作、工人和环境之间的相互影响.运筹学的起源美国的亨利·福特(HenryFord，1863-1947)在泰勒的单工序动作研究的基础上，为了提高企业的竞争能力，对如何提高整个生产过程的生产效率进行了研究.他充分考虑了大量生产的优点，规定了各个工序的标准时间，使整个生产过程在时间上协调起来，创造了第一条流水生产线——汽车流水线，从而提高了整个企业的生产效率，使成本明显降低.运筹学的起源福特为了利于企业向大量生产发展，进行了多方面的标准化工作，包括：产品系列化，零件规格化，工厂专业化，机器及工具专用化，作业专门化.运筹学的起源泰勒及其他同期先行者的理论和实践构成了泰勒制.泰勒制的核心是用科学的方法提高生产现场的生产效率.所以,人们把以泰勒为代表的这些学者所形成的学派称为科学管理学派.管理实践和管理科学的许多问题,至今仍然是运筹学家关注的课题.运筹学的起源

3.运筹学的经济学起源

运筹学的第三个来源是经济学的研究.经济学理论对运筹学的影响是和数理经济学学派紧密联系的.数理经济学对运筹学，特别是对线性规划的影响可以从魁奈（Qusnay）1758年发表的《经济表》算起，当时最著名的经济学家沃尔拉斯（Walras）研究了经济平衡问题，后来的经济学家对其数学形式继续研究并得到深入发展.运筹学的起源1928年，冯.诺伊曼（vonNeumann,John,1903-1957）以研究二人零和对策的一系列论文为“对策论”奠基，1932年，又提出了广义经济平衡模型.1939年，苏联的康托洛维奇发表《生产组织和计划中的数学方法》.这些工作都可以看作是运筹学的先驱工作.运筹学的起源教学计划与方法教学计划数学规划以线性规划和整数规划为教授重点，组合优化部分主要讲网络优化，而随机优化讲授排队论和对策论，其它部分作为选讲内容。教学方法

以授课为主，与案例分析相结合。而讲课中主要培养用最优化方法解决实际问题的能力。考试与要求考核内容

卷面成绩70%平时成绩30%其中平时成绩包含：1）考勤15分2）作业10分3）课堂表现5分参考资料韩伯棠，管理运筹学，高等教育出版社，北京，2000年。徐光辉等，运筹学手册，科学出版社，北京，1999年。胡运权等，运筹学教程，清华出版社，北京，1998年。刘家壮，王建方，网络最优化，华中工学院出版社，武汉，1987年管梅谷，郑汉鼎，线性规划，山东科学技术出版社，济南，1983年。第一章线性规划及单纯形法

LinearProgramming(LP)管理运筹学教学课件2012年1月第一节线性规划问题的数学模型第二节两变量线性规划问题的图解法第三节线性规划的基本定理第四节单纯形法第五节单纯形法的进一步讨论第六节线性规划应用举例本章内容第一节线性规划问题的数学模型线性规划是运筹学中研究较早、发展较快、应用较广、比较成熟的一个分支，它是一种合理利用和调配有限资源的数学方法。线性规划研究的问题：极大化问题：面对一定的资源，要求充分利用，以获得最大的经济效益。极小化问题：给定一项任务，要求统筹安排，尽量做到用最少的人力、物力资源去完成这一任务。一、实例：生产安排问题原料配比问题运输问题二、线性规划问题的结构特征线性规划问题的特征线性规划问题的一般形式线性规划问题的标准形式一般形式向标准形式的转化本节内容安排一、实例例1-1[生产安排问题]某企业使用A、B、C三台机器生产甲、乙两种产品。已知未来两周内A、B、C三台机器的使用时间分别不得超过80，60，45小时，生产每单位产品所需要各台机器的加工时间及每单位产品的利润如表1—1所示，问企业如何安排未来两周的生产，才能使总利润达到最大？产品机器甲乙可利用的机时（小时）A2480B3260C3045单位产品的利润（元）5060设甲乙两种产品的产量分别为x1，x2单位，未来两周的总利润为。于是上述问题归结为，寻求一组的值，在满足条件目标函数约束条件设生产甲乙两种产品的数量分别为x1,x2件，总利润为z.例1—2[原料配比问题]某企业使用三种原料B1,B2,B3配置某种食品，要求食品中蛋白质、脂肪、糖、维生素的含量分别不低于15、20、25、30单位。以上三种原料的单价以及每单位原料所含各种成分的数量下表1所示，问应如何配置食品，才能使成本最低？原料营养成分B1B2B3食品中营养成分的需要量蛋白质56815脂肪34620糖85425维生素1012830原料单价（元）202530设x1,x2,x3分别表示原料B1,B2,B3的用量，z表示食品成本。该问题的数学模型为：

例1—3[运输问题]

设要从甲地调出物资2000吨，从乙地调出物资600吨，从丙地调出物资500吨，分别供应给A地1700吨、B地1100吨、C地200吨、D地100吨。已知每吨运费如下表所示。假定运费与运量成正比，问如何安排调运才能使总运费最省？销地产地ABCD甲2125715乙51513715丙43382617用（i=1,2,3;j=1,2,3,4）分别表示从甲乙丙三个产地运往A,B,C,D四个销地的物资数量。则该问题的数学模型为简化表达式二、线性规划问题的结构特征：1.线性规划问题的特征；（1）都有一组决策变量。（2）都有一组线性的约束条件，它们是线性等式或不等式。（3）都有一个确定的目标，这个目标可以表示成决策变量的线性函数，根据问题不同，有的要求实现极大化，有的要求实现极小化。线性规划问题的本质：研究在一组线性约束下，一个线性函数的极值问题。所以称为线性规划linearprogramming(LP)2.线性规划问题的一般形式s.t（1）（2）（3）一般形式的简化表达规范形式极大化问题极小化问题3.线性规划的标准形式s.t.s.t（1）（2）（3）标准形式的简化表达标准形式的矩阵表达标准形式的向量表达标准形式的特点：(1).目标函数极大化(2).约束条件全部是等式(3).所有的变量都是非负的(4).约束条件右端常数为非负的4.一般形式向标准形式的转化：(1)目标函数极大化对于极小化的目标函数可以等价地转化成求的极大化。(2)不等式约束化等式约束对于形的不等式，可以在不等式的左边加上（减去）一个非负的变量使不等式化成等式。这样的变量称为松弛（剩余）变量。例如：(3)自由变量化非负变量的差自由变量可以用两个非负变量的差代替，例如对于一个符号无限制的变量，可以引进两个非负变量

并设(4)约束条件右端的负常数化为正常数对于右端常数为负数的约束，可以两端同时乘以-1。取值小于等于0的变量，可以用一个非负变量的相反数表示。例1-4将下列LP问题化成标准形式第二节两变量线性规划问题的图解法

一、几个概念二、两变量LP问题的图解法可行解：任何一组满足所有约束条件的决策变量值称为LP问题的一个可行解。最优解：使目标函数达到最大（小）值的可行解。最优值：最优解对应的目标函数值。可行域：所有可行解的集合称为可行域。一、几个概念：二、两变量LP问题的图解法图解法是根据平面直角坐标系和二元一次方程（不等式）的特点设计的。1.图解法的一般步骤：（1）建立直角坐标系，以为横轴，为纵轴。（2）将约束条件在直角坐标系中表示，并找出可行域。（3）作出目标函数的等值线簇，找出目标函数值的增加（或减小）方向，用箭头表示。（4）确定出问题的最优解。若为极大（小）化问题，目标函数沿增加（减小）方向平移，与可行域的最后一个交点即为最优解。例1-5用图解法解下列线性规划问题最优解

x*=(10,15)T,最优值

z*=5010+6015=1400.可行域有界,有唯一最优解例1-6用图解法求解下列LP问题无穷多最优解例1-7、用图解法求解下列线性规划问题：

⑴⑵无有限最优解x1x2

⑴⑵可行域无界,有唯一最优解x1x2

例1-8改换一下例1—7中线性规划的目标函数，得到一个新的规划

例1-9用图解法求解下列线性规划问题可行域为空,无可行解可行域是空集。可行域存在，则一定是一个凸多边形.无有限最优解（可行域一定无界）。最优解存在且唯一，则一定在顶点上达到。最优解存在且不唯一，一定存在一个顶点是最优解。2.图解法求解两变量LP问题时可能出现的情况：3.两变量线性规划问题解的性质

1.两变量线性规划问题的可行域是若干个半平面的交集，它是一个有界或无界的凸多边形，并且有有限个顶点。2.对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域的某个顶点上达到。第三节线性规划的基本定理一、一般线性规划问题可行区域的几何结构二、基可行解及线性规划的基本定理

一、一般线性规划问题可行区域的几何结构1.

基本假设2.

凸集及其性质3.

可行域的凸性4.

问题1.基本假设凸集：设S是n维欧氏空间的一个点集，若任意两点X(1)S,X(2)S的连线上的一切点

X(1)+(1-)X(2)S,(01);则称S为一个凸集。性质：任意多个凸集的交集仍然是凸集。2.凸集及性质顶点：设S是凸集，XS；若对任何X(1)S和X(2)S，X(1)

X(2)，以及任何0<

<1，都有X

X(1)+(1-

)X(2)

则称X为凸集S的一个顶点（或极点）。根据顶点的定义，长方形的四个角点就是长方形区域的全部顶点，而圆周上的点则是圆形区域的全部顶点。在平面区域中，每个顶点至少是两条直线的交点。3.可行域的凸性定理1-1：线性规划问题的可行域D={xRn|AX=b,X0}是凸集。4.问题可行域顶点的个数是否有限？最优解是否一定在可行域顶点上达到？如何找到顶点？

如何从一个顶点转移到另一个顶点？二、基可行解及线性规划的基本定理基可行解的定义线性规划的基本定理问题1.基可行解的定义考虑标准形式的线性规划问题基：A是约束方程组的系数矩阵(设n>m)，其秩为m，B是A中的一个m阶满秩子方阵，称B是线性规划问题的一个基。B中每一个列向量称为一个基向量，与基向量对应的变量称为基变量。其余变量称为非基变量。不失一般性，设则Pj（j=1，2…m）是基向量，xj（j=1，2…m）是基变量。xj（j=m+1，…，n）是非基变量。基解：在约束方程组中令所有的非基变量xm+1=xm+2=xn=0，得此方程组有唯一解XB=(x1，x2，…xm)T，将这个解加上非基变量取0的值有X=(x1，x2，…xm,0,…,0)T,称X为线性规划问题的基解。显然，基解中取非零值的变量个数不超过m，基解的总数不超过Cnm个。基可行解：满足非负约束的基解称为基可行解。可行基：对应于基可行解的基。可行解基解基可行解用矩阵形式表示的基解考虑标准形式的线性规划问题：例如LP问题是它的两个基，对应的基解分别为可见X1是基可行解，故B1是可行基。而X2不是基可行解，故B2不是可行基。根据以上定义2.线性规划的基本定理引理：LP问题的可行解X是基可行解的充要条件是它的正分量所对应的A中的列向量线性无关。定理1-2：若线性规划问题有非零可行解，则其必有基可行解

定理1-3：X是线性规划问题的基可行解的充要条件是X是可行域的顶点定理1-4

一个线性规划问题，若有有限最优解，则一定存在一个基可行解是最优解。3.问题如何得到第一个基可行解？如何判别一个基可行解是否最优？如果当前的基可行解不是最优，如何从一个基可行解转化到另一个基可行解？第四节单纯形法单纯形法（SimplexMethod）是G.B.Dantzing在1947年提出的。确定初始基可行解最优性检验和解的判别基可行解的改进单纯形法的基本步骤情况1约束条件全部是“”型不等式且右端常数非负（化成标准形后，约束条件系数矩阵含有单位子矩阵）加上松弛变量，化为标准形式：

1.

确定初始基可行解其约束条件系数矩阵为令其中的单位矩阵作为基，可得初始基可行解考虑标准形式的LP问题假设可行域非空，A为一mn实矩阵，r(A)=m<n

。

情况2化成标准形式后，约束条件系数矩阵不含单位子矩阵关键：找一个可行基，将约束条件化成系数矩阵含有单位矩阵的形式。假设B是一个可行基，不妨设B是由A的前m个列向量组成的，即A=(B,N)，则线性规划问题的等式约束AX=b可以化成：目标函数Z=CX可以化成线性规划问题的典式（典则形式）典式的特点（1）约束条件系数矩阵中含有一个单位矩阵；（2）目标函数中不含有基变量。此时：有了典式，就很容易写出线性规划问题的基解其中如果基B是可行基，则

0

即X0是基可行解，对应的目标函数值为z0。问题：如何判断一个基可行解是否为最优解呢？在典式中，目标函数中非基变量的系数称为检验数，检验数是用来判断相应基可行解是否最优的标志。2.最优性检验和解的判别当所有检验数

j≤0时，当前的基可行解为最优解；如果某个非基变量的检验数j>0，而ij≤0，则原问题无界；如果某个非基变量的检验数j>0，且至少存在一个i，使得ij>0，则可以找到一个新的基可行解X1，使得CX1>CX。3.基可行解的改进1)基的修改：进基变量、出基变量的选取准则。2)迭代：得到新基对应的典式。基的修改准则：新基与原有基有m-1

个相同的基变量，只有一个基变量不同。进基变量：从非基变量变为基变量的变量。出基变量：由基变量变为非基变量的变量。1)进基变量的选取原则：最优性原则：若

k>0,则与

k相对应的变量xk是非基变量，当xk变为基变量时，它的值由0变为正数，比如说xk=>0，其余的非基变量仍取值为零。由(3.4)式知，对应新解的目标函数值为z=z0+

K>z0，显然

越大目标函数值越大。可行性原则（最小比值原则）：

的取值应保证新解仍然是基可行解。2)

出基变量的选取原则进基变量和出基变量的选取准则当xk=>0成为基变量以后，其余非基变量仍然取值为0。设新基对应的基可行解为X1=(x11,…,xn1)T,则X1应满足约束条件，即由于xi1必须是非负的，即如果

ik0，显然只要>0，就有xi1=i-

ik0，对于

ik>0，就要求所以

应满足假定至少有一个aik>0，i=1,2,…m，并且所有的

i

>0,则

0>0，从最优性原则出发，让

取值尽量大，即取然后把xt从原有的基中取出来，得到一组新的基可行解X1

使目标函数取值z1=z0+

k

0

>z0.迭代（新的基可行解对应的典式的确定）利用线性方程组的等价变换将约束条件和目标函数化成新基对应的典式，从而求出新的基可行解及相应的检验数例1-10:用单纯形法求解线性规划问题添加松弛变量，化成标准形式第一个基可行解X0=(0,0,80,60,45)T目标函数值为0对应可行域顶点O(0，0).让x2进基，不妨假设x2

＝，x2仍为非基变量。目标函数值为60。从最优性角度看，

越大越好为了保持解的可行性，原先的基变量取值必须满足综上得到X3出基，新的基变量为X2

，X4，X5对应的典式可以由方程组的初等变换得到新的基可行解：X1=(0,20,0,20,45)T,对应的目标函数值为1200。对应可行域A点。由于仍然有正的检验数，因此当前的解不是左右，取x1为进基变量，按照最小比值原则确定出基变量为x4，经过初等变换得到新基对应的典式为：新的基可行解：X1=(10,15,0,0,15)T,对应的目标函数值为1400。对应可行域B点。由于检验数均非正，所以已得到最优解。4单纯形法的计算步骤、单纯形表Step1

将线性规划问题化成典式,求出各个非基变量的检验数.Step2

判断所有非基变量的检验数是否非正,若是,则结束;否则转step3.Step3

选取一个检验数大于零的非基变量为进基变量;Step4

若进基变量所对应的约束条件系数全为非正数,则原问题无界,结束;否则,按最小比值原则确定出基变量;Step5

进行迭代(用方程组的初等变换法确定新的基对应的典式及检验数),转step2.单纯形表=-∑cn+ibi

j=cj-∑cn+i

CBXBbc1c2cmcm+1cnx1x2…xmxm+1…xnc1x1b11…0

1m+1…

1n:::cmxmbm0…1

mm+1…

mn检验数z00…0

m+1…

n例1-11用单纯形表求解例1-1的线型规划问题解：先化成标准形式cj5060000

CBXBbx1x2x3x4x50x3802[4]10020（1）0x4603201030（2）0x54530001---（3）05060000cj5060000

CBXBbx1x2x3x4x560x2201/211/40040（1’）0x420[2]0-1/21010（2’）0x5453000115（3’）-1200200-1500cj5060000

CBXBbx1x2x3x4x560x215013/8-1/40（1”）50x11010-1/41/20（2”）0x515003/4-3/21（3”）-140000-10-100注意：1.在选取进基变量时，若有几个非基变量的检验数都是正数，则可以任意选取一个正检验数对应的非基变量作为进基变量，一般选取最大正检验数对应的非基变量。但实际情况表明这种策略不一定最好。2.在选取出基变量时，若有几个比值同时达到最小，可以任意选择一个，但在新的基本可行解中这些对应分量均为零。从而新的基本可行解是一个退化的基本可行解。假若问题是非退化的，则不会出现这种情况。例1-12：利用单纯形法求下列线性规划问题将该问题化成标准形式（也是典式）基变量是：x3，x4，x5，非基变量是x1x2填入单纯形表求解cj11000

CBXBbx1x2x3x4x50x34-1[1]10040x441-1010---0x561100160110001x24-11100---0x4800110---0x52[2]0-1011-420-1001x25011/201/2100x4800[1]1081x1110-1/201/2----6000011x21010-1/21/20x38001101x151001/21/2-600001最优解X1=(1,5,0,8,0)T，最优值6。最优解X2=(5,1,8,0,0)T，最优值6。实际上X1与X2的连线上的任意点都是最优解.(5,1)(1,5)例1-13：用单纯形法求解线性规划问题（无有限最优解的情况）解：化成标准形（典式）（5，0）（0，5）2100CBXBbx1x2x3x40x35-11100x4102-501

j021000x3100-3/211/22x151-5/201/2

j-10060-1

5X2的检验数为正，但约束条件中x2的系数全为负，因此该问题无有限最优解。第五节单纯形法的进一步讨论1.大M法2.两阶段法3.单纯形法的矩阵描述4.单纯形法小结考虑标准形式的线性规划问题1.大M法原问题辅助问题人工变量X是原问题的基可行解是辅助问题的基可行解。为了得到原问题的一个基可行解，只要将辅助问题的基可行解中的人工变量全部变为非基变量即可。为此，将人工变量加到辅助问题的目标函数中并赋予系数-M。（M可以看成惩罚系数）添加M以后，直接求解辅助问题，可能有两种情况：1.辅助问题的最优解中人工变量全部是非基变量，此时去掉人工变量直接得到原问题的最优解。2.在辅助问题的最优解中某些人工变量是基变量且取值非零，此时原问题无可行解。例1-14：用大M法求解下列线性规划问题化标准型添加人工变量得辅助问题cj-30100-M-MCBXBbx1x2x3x4x5x6x70x441111000-Mx61-2[1]-10-110-Mx79031000110M-2M-34M10-M000x4330211-100x21-21-10-110-Mx76[6]0403-316M6M-304M+103M-4M00x400001-1/21/2-1/20x23011/30001/3-3x1110[2/3]01/2-1/21/6300303/2-M-3/2-M+1/20x400001-1/21/2-1/20x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4-3/2-9/2000-3/4-M+3/4-M-1/4例1-15：用大M法求解下列线性规划问题添加人工变量，化成典式cj2300-MCBXBbx1x2x3x4x50x3122[2]100-Mx514120-1114M2+M3+2M0-M03x26111/200-Mx52-10-1-112M-18-1-M0-3/2-M-M0所有的检验数都不大于零，人工变量X5仍留在基变量中且不为零，故原问题无可行解。2.两阶段法第一阶段：寻找原问题的一个基可行解

第二阶段：求原问题的最优解通过求解一个目标函数只含有人工变量的辅助问题实现。原问题辅助问题第一阶段解的情况1.第一阶段人工变量取值为0，目标函数值也为0。此时得到原问题的第一个基可行解。结束第一阶段，去掉人工变量，进入第二阶段求原问题的最优解。2.第一阶段最优解的基变量中含有人工变量，表明原问题无可行解。例1-16：用两阶段法求解下列线性规划问题化标准形第一阶段的线性规划问题为cj00000-1-1CBXBbx1x2x3x4x5x6x70x441111000-1x61-2[1]-10-110-1x79031000110-2400-1000x4330211-100x21-21-10-110-1x76[6400x400001-1/21/2-1/20x23011/30001/30x1110[2/3]01/2-1/21/6000000-1-1第一阶段：用单纯形法求解辅助问题得原问题的基可行解X=(1,3,0,0,0)T。cj-30100CBXBbx1x2x3x4x50x400001-1/20x23011/3000x1110[2/3]01/2300303/20x400001-1/2

0x25/2-1/210

0-1/41x33/23/20103/4-3/2-9/2000-3/4第二阶段：将上表中的人工变量去除，目标函数换成原问题的目标函数，从上表的最后一个单纯形表出发，继续计算。得原问题的最优解X=（0，5/2，3/2，0，0）T，最优值是3/2。3.单纯形法的矩阵描述添加松弛变量化成标准形式初始解非基变量基变量bBNE00,0,…,0假设可行基为B,不妨假设B是由A中的部分列构成的满秩方阵，把A中的列分块。其中N是A中的非基向量构成的块。则

初始单纯形表为单纯形法的迭代计算实际上就是对约束方程组增广矩阵实施初等行变换。由线性代数知识知道，对矩阵实施行的初等变换，当B变为单位矩阵E的时候，单位矩阵E将变为B-1。由此上述矩阵将变为，变换后的单纯形表为基可行解基变量非基变量B-1bEB-1NB-1-z0,…,0-y1,-y2,…,-ym其中单纯形法计算小结第六节线性规划应用举例例1-17[混合配料问题]

某糖果厂用原料A,B,C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A,B,C的含量，原料成本，各种原料的每月限制用量，三种糖果的单位加工费如下表所示．问该厂每月生产这三种牌号的糖果各多少千克，才能获利最大？甲乙丙原料成本（元/kg）每月限制用量（kg)A

60%

30%2.002000B1.502500C≤20%≤50%≤60%1.001200加工费(元/kg)0.500.400.30售价(元/kg)3.402.852.25解:用i=1，2，3代表A,B,C三种原料，用j=1,2,3分别代表甲，乙，丙三种糖果，设xij为生产第j种糖果使用的第i种原料的质量，则问题的数学模型为：用单纯形法解得：例1-18［投资项目的组合问题］兴安公司有一笔30万元的资金，考虑今后3年内用于下列项目的投资：［项目一］三年内的每年年初可投资，每年获利为投资额的20%，其本利可一起用于下一年的投资；［项目二］只允许第一年初投资，于第二年末收回，本利合计为投资额的150%，但此类投资限额不超过15万元；［项目三］允许于第二年初投资，于第三年末收回，本利合计为投资额的160%，但限额投资为20万元；［项目四］允许于第三年初投资，年末收回，可获利40%，但限额为10万元。试为该公司确定一个使第三年末本利和为最大的投资组合方案。解：用xij表示第i年初投资到第j项目的资金数，则可得下列线性规划模型求解得例1-19[下料问题]

工厂要制作100套专用钢架，每套钢架需要用长为2.9m、2.1m和1.5m的圆钢各一根。已知原料每根长7.4米，现考虑应如何下料，可使所用原料最省？方案1方案2方案3方案4方案5方案6方案7方案82.9m211100002.1m021032101.5m10130234合计7.37.16.57.46.37.26.66.0剩料0.10.30.901.10.20.81.4解：设x1,x2,x3,x4,x5,x6,x7,x8

分别表示按上述8种方案下料的原料根数。则：用单纯形法求的最优解例1-20[人员安排问题]某个中型百货商场对售货人员（周工资200元）的需求经统计如下表星期一二三四五六七人数12151214161819为了保证销售人员充分休息，销售人员每周工作5天，连续休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？解：设第

i天开始工作的人员数为xi

,

i=1,2,…7.求解得：例1—21[生产与库存的优化安排问题]

yij≤dij(i=1,…,5;j=1,…,6)

第二章线性规划的对偶理论2012年1月管理运筹学教学课件本章主要内容第一节、原问题和对偶问题第二节、对偶问题的基本性质第三节、对偶问题的经济解释——影子价格第四节、对偶单纯形法第五节、灵敏度分析第六节、线性规划的软件求解方法第七节、线性规划应用案例分析第一节、原问题和对偶问题一、引例二、对称形式的对偶规划三、非对称形式的对偶规划四、一般形式的对偶规划一、引例ABCD原料拥有量（单位）含量（单位/公斤）糖524260蛋白质321440脂肪312535单价（元/公斤）157912建立其数学模型。例2-1甲食品厂用糖、蛋白质和脂肪三种原料生产四种复合食品A、B、C、D，复合食品中含有各种原料的数量、复合食品的单价、三种原料的拥有量分别如下表所示，问甲厂如何安排生产才能使总产值达到最大？x1x2x3x4解：设甲厂安排A、B、C、D的产量分别为x1、x2、x3、x4公斤，总产值为z元。于是，例2-1的数学模型为：例2-2.假设乙食品厂欲将甲厂的原料收买过来，问乙厂至少应付出多少代价，才能使甲厂放弃生产活动，出让原料？建立该问题的数学模型。ABCD原料拥有量（单位）含量（单位/公斤）糖524260蛋白质321440脂肪312535单价（元/公斤）157912y1y2y3解：设y1,y2和y3（元/单位）分别代表乙厂收购糖、蛋白质和脂肪的单价，乙厂收购原料付出的总费用为w元，于是例2-2的数学模型为：例2-1和例2-2的数学模型比较令以上两个线性规划分别称为线性规划的原问题和对偶问题。若两个线性规划分别是和则称它们是一对对称的对偶规划。二、对称形式的对偶规划对称对偶规划还可以写成表格形式，称为对偶表MaxzMinw原问题（求极大）c1

x1c2x2……cnxn右端项对偶问题求极小b1y1a11a12…a1n

b1b2y2a21a22…a2n

b2………………bmymam1am2…amn

bm右端项

c1

c2…

cn对偶规划中的两个问题分别称为原问题和对偶问题（互为对偶）。

一对对称形式的对偶规划之间具有下面的对应关系。(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，≤”和“min，≥”相对应。

(2)一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。

(3)原问题目标函数系数是对偶问题的约束条件右端项；原问题的约束条件右端项是对偶问题的目标函数系数。(4)两个规划模型中的变量皆非负。例2-3：写出下列线性规划的对偶规划解：原规划的对偶规划为y1y2三、非对称形式的对偶规划叫做非对称的对偶规划。非对称的对偶规划可以由对称对偶规划推出。例2-4：写出下列线性规划问题的对偶规划。解：将上述线性规划化成对称对偶规划的形式写出它的对偶规划y1'y1

y2'y2

(D)四、一般形式的对偶规划(P)一般形式对偶规划的特点（1）原问题是“max，=,≤”形式，对偶问题是“min，=,≥”形式（2）原问题的每个等式约束，对应对偶问题一个自由变量，原问题的每个不等式约束，对应对偶问题的一个非负变量；反之亦然，即原问题中的每个非负变量对应的是对偶问题中的一个不等式约束，而原始问题中的每个自由变量对应对偶问题中的一个等式约束。（3）原问题目标函数中的系数c就是对偶问题约束条件的右端常数项，而原问题约束的右端常数项就是对偶问题目标函数中的系数。（4）如果用矩阵和向量形式写出问题(P)和(D)的约束，可以看出这两个问题的约束系数矩阵互为转置。线性规划原问题与对偶问题的对应关系原问题（对偶问题）对偶问题（原问题）目标函数max目标函数minn个

变量0

0无限制n个

约束条件

=目标函数中变量的系数约束条件右端常数m个约束条件

=m个0变量

0无限制约束条件右端常数目标函数中变量的系数例2-5．写出下列线性规划问题的对偶规划解：设对应于原问题的三个约束条件的对偶变量分别为y1,y2,y3；则根据一般对偶规划的对应关系，可以直接写出上述规划的对偶规划第二节、对偶问题的基本性质考虑如下的对偶规划定理2-1(对称性)

对偶问题的对偶是原问题定理2-2(弱对偶定理)

设X0和Y0分别是原问题和对偶问题的可行解，则CX0Y0b；特别当CX0=Y0b

时，X0和Y0分别是原问题和对偶问题的最优解。定理2-3

（强对偶定理）若原问题有最优解，则其对偶问题也一定有最优解，并且此时目标函数的最优值相等。证明：将原问题加上松弛变量化成标准形式：用单纯形方法求解得最优解X，设其最优基为B，则XB=B-1b,检验数为令则Y是对偶问题的可行解又因为由定理2-2知Y是对偶问题的最优解。即即原问题和对偶问题的解的情况如下对偶原始有最优解问题无界无可行解有最优解①

问题无界

③无可行解

③②定理2-4

给定一个线性规划的原问题和它的对偶问题，则上表中的三种情况恰有一种出现。证明：由定理2-2容易证明，如果原问题或它的对偶中有一个是无界的，那么另一个不可能有可行解。（用反证法）下面举例说明剩下的情况（2）和（3）是可能出现的。考虑下列对偶规划显然两个问题均无可行解，情况（2）出现。原问题无可行解，对偶问题无界，情况（3）出现。考虑下列对偶规划：例2-6已知线性规划问题试用对偶理论证明该问题无界证：首先看到该问题有可行解，如X=(0,0,0)T,容易写出其对偶问题为

由对偶问题的第一个约束条件可知，对偶问题无可行解。由于原问题有可行解，因此，由定理2—4可知，原问题无界。(P)(D)定理2-5

（互补松弛定理）设X和Y分别是原问题和对偶问题的可行解，则它们分别是原问题和对偶问题的最优解的充要条件是对一切的i=1,2,…,m，和一切j=1,2,…n

有证明：由对偶的定义知证明：由对偶的定义知因此定义由定理2-2知，X和Y分别是原问题和对偶问题最优解的充要条件是即也即例2-7已知线性规划问题其对偶问题的最优解为试用对偶理论找出原问题的最优解。解：先写出对偶规划定理2-6：线性规划原问题单纯形表的检验数行对应对偶问题的基解，其中原问题的变量的检验数相反数对应对偶问题的剩余变量，原问题的松弛变量检验数的相反数对应对偶问题的变量。这对互补的基解分别代入原问题和对偶问题的目标函数有z=w。证：设线性规划的原问题和对偶问题分别为将原问题和对偶问题分别化成标准形式设B是原问题的一个可行基,于是原问题可以改写成例2-8.考虑考虑第一章例1—1的生产安排问题线性规划模型及对偶线性规划

将其分别化为标准形式：其标准形式的变量对应关系表第三节、对偶问题的经济解释—影子价格：一、影子价格的概念考虑下面一对互为对偶的线性规划设Y*=（y1*，y2*，…,ym*)是对偶问题的最优解,则称yi*是原规划的第i个约束对应的影子价格。如本章例2—1和2—2的对应的对偶线性规划模型分别为：

经过计算可以得到原规划及对偶规划的最优解分别为：，。即最优生产计划是生产A食品10公斤，B食品5公斤，不生产C,D食品。乙厂欲收购甲厂的原料，应该分别为糖、蛋白质、脂肪付出的价格为：1.833，1.389，0.556，此即三种原料的影子价格。影子价格是对第i种资源的一种估价，这个价格不是市场价格，而是针对企业在一定时期内存在的一种特殊价格，它蕴含在求最大利润的生产计划模型中。（1）第i种资源的影子价格yi*

是一个边际价格。它表示在第i种资源数量bi

附近的某个闭区间内，该资源的数量增加一个单位（此时其它资源数量不变），生产计划的最大利润z*将增加yi*个单位。

z*=CBB-1b=Y*b二、影子价格的经济含义（2）影子价格是对现有资源实现最大效益的一种估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价。（3）影子价格是一种机会成本，对市场有调节作用。当某种资源的市场价格低于影子价格时，企业应当买进该种资源用于扩大生产；当某种资源的市场价格高于影子价格时，企业的决策者应当把已有资源卖掉。随着资源的买进卖出，影子价格也将随着变化，直到影子价格和市场价格保持同等水平时，才处于平衡状态。（4）由对偶问题的互补松弛性质可知，当某种资源未被充分利用时，影子价格为0；当某种资源的影子价格不为0时，说明该资源在生产中已经消耗完毕。（5）从影子价格的含义上来考察单纯形法的计算。当产品的产值大于隐含成本时，表明生产该项产品有利，可在计划中安排生产，否则这些资源生产别的产品更为有利，就不在生产计划中安排。这就是单纯形法中检验数的经济意义。第四节、对偶单纯形方法对偶单纯形方法的基本原理对偶单纯形方法求解原规划的主要步骤对偶单纯形方法的适用范围1.对偶单纯形方法的基本原理对偶单纯形方法：从原规划的一个基解出发，此基解不一定是原规划的基可行解，但它对应着对偶问题的基可行解（检验数非正），逐步调整，使所有变量取值变成非负，即得到原问题的基可行解。单纯形方法：从原规划的一个基可行解（此基解不一定对应对偶问题的可行解，即检验数不一定非正）出发，逐步调整，使检验数变成非正（对应对偶问题的可行解）。原问题的基可行解对偶问题的基可行解单纯形方法对偶单纯形方法2.对偶单纯形法的求解步骤

1.根据线性规划问题的典式，建立初始对偶单纯形表,对应原问题的一个基解,所有检验数均非正,转2；

2.若b≥0,则得到最优解,停止;否则,若有bk<0,则选k行的基变量为出基变量(若有多个bk<0,则选最小的一个所在的行中的基变量出基),转3;

3.若所有akj≥0(j=1,2,…,n)，则原问题无可行解,停止;否则,若有akj<0,则计算

=min{j/akj┃akj<0}=r/akr

并选xr为进基变量,转4；

4.以akr为主元素,作矩阵行初等变换使其变为1,该列其他元变为0,转2。例2-9：用对偶单纯形法求解下述线性规划问题：化成标准形若用单纯形方法求解，需再引进两个非负的人工变量，然后用大M法或两阶段法求解。由本例的特点，我们只要将等式两端同乘以-1，就可以得到原问题的一个基解（不可行）和对偶问题的一个可行解（检验数非正）-2-3-400CBXBbx1x2x3x4x50x4-3-1-2-1100x5-4-21-301

j0-2-3-4000x4-10-5/21/21-1/2-2x121-1/23/20-1/2

j40-4-10-1-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5

j28/500-9/5-8/5-1/5得原问题的最优解X=（11/5，2/5，0，0，0）T，最优值是-28/5。3.对偶单纯形法的适用范围1.如下形式的问题2.灵敏度分析第五节：灵敏度分析

当参数发生变化时，如果重新建立模型，从头计算求解，当然是一种办法，但是这样做不仅麻烦、没有必要，而且也得不到更多有用的信息。灵敏度分析采用的办法，是从已得到的最优解出发，通过对变化数据进行一些简单的计算，便可迅速得到所需要的结果以及变化后的最优解。因此，灵敏度分析也称优化后分析。研究最优解受数据变化的影响情况主要考虑两个方面：一是解的最优性，即检验数是否仍然非正；二是解的可行性，即基解的各个分量是否仍然非负。一、目标函数系数的变化目标函数中系数c的变化仅仅影响到检验数cj-zj的变化，所以可以直接在最终的单纯形表中计算例1:试分析下列线性规划问题的目标函数中x3的系数在多大范围内变化时最优解保持不变。

解：最优单纯形表从表中看到σ3=-9/5+Δc3当-9/5+Δc3≤0,即Δc3≤9/5

时，原最优解不变。例２：在第一章例1-1中，试分析（1）产品甲的单位利润在多大范围内变化时，最优生产方案保持不变？（2）如果产品甲的单位利润由50元增加到100元，最优生产方案如何变化？二、约束条件右端常数的变化b的变化在实际问题中表明资源的数量发生变化，反映到最终单纯形表上只引起基变量列数字的变化。根据前面的讨论，最优解的基变量XB=B-1b=b*，设b变化为b+b，那么只要保持B-1(b+b)≥0，则最优基不变，所以关键是求出B-1。例2-13对于线性规划问题(1)分析第二个约束右端常数在什么范围内变化时,问题的最优基保持不变.(2)若第二个约束右端常数由60分别增加到70和80，问最优解如何变化？设第二个约束右端常数变为

，为保持最优基不变，应使下式成立（2）若第二个约束右端常数由60增加到70，则基解变为若第二个约束右端常数变80，则基解变为三、增加新变量的分析

增加一个变量相当于增加一种新产品，分析的步骤是首先计算这种新产品对应的检验数，如果检验数小于等于零，则最优解保持不变，如果检验数大于零，说明投产新产品有利，继续按单纯形法迭代可以求出新的最优解。例2—14

在例1—1中假设企业考虑投产一种新的产品丙，丙产品每单位需要在A,B,C三台设备上的加工时间分别为2、1、3小时，利润是40元，试分析企业投产丙产品是否有利。解：设丙产品的产量为x6单位由于检验数为正，说明投产丙产品有利。将以上结果填入原问题的最后一张单纯形表中，得表2—19.

表2—19cj506000040CBXBbx1x2x3x4x5x660x215013/8-1/401/250x11010-1/41/2000x515003/4-3/21[3]

j-140000-10-10010选x6为进基变量，迭代一步得表2—20.

表2—20cj506000040CBXBbx1x2x3x4x5x660x212.5011/40-1/6050x11010-1/41/20040x65001/4-1/21/31

j-145000-12.4-5-10/30故企业应该投产丙产品，新的生产方案是甲、乙、丙的产量分别为10、12.5、5单位，总利润1450元。四、增加一个约束的分析增加一个约束，在实际中相当于增加一道工序，分析的方法是先将原来的最优解代入这个新增加的约束中，若满足，则说明新增加的约束未起到限制作用，原最优解不变。否则，将新的约束反映到最终的单纯形表中，再进一步分析。表2—21cj50600000CBXBBx1x2x3x4x5x660x215013/8-1/40050x11010-1/41/2000x515003/4-3/2100x660240001

j-140000-10-1000为了使P2,P1,P5,P6

列组成单位矩阵，对表2—21进行行的初等变换得到表2—22表2—22cj50600000CBXBBx1x2x3x4x5x660x215013/8-1/40050x11010-1/41/2000x515003/4-3/2100x6-2000[-1]001

j-140000-10-1000用对偶单纯形法迭代得表2—23

表2—23cj50600000CBXBbx1x2x3x4x5x660x215/2010-1/403/850x1151001/20-1/40x50000-3/213/40x32000100-1

j-1200000-100-10因此，增加约束后，新的最优解是第六节：线性规划的软件求解方法第七节线性规划应用案例分析

例2—16（城市更新问题）某城市由于面临严重的预算不足问题，为了寻求一种长期的解决方案，决定征用内城的一块住宅区域，进行一项现代化的项目开发，以增加税收来源。改造工程包括两个阶段：（一）拆除不符合标准的住宅，为新的开发提供土地；（二）建造新的建筑。大体情况是这样的：(1)拆除大约300套不符合标准的住宅。每套住宅占地0.25英亩，拆除一套征地住宅的成本是2000美元。(2)新的单、双、三和四户住宅（单元）的土地面积分别是0.18、0.28、0.4和0.5英亩。街道、开阔地和公共设施占可利用面积总量的15%。(3)在新的开发项目中，三户与四户的住宅单元数的总和至少占总住宅单元的25%。单户住宅单元数至少应占总单元数的20%。双户住宅单元数至少占总单元数的10%。(4)对于单、双、三和四户住宅，每单元征税额分别是1000美元、1900美元、2700美元和3400美元。(5)对于单、双、三和四户住宅，每单元的建筑成本分别是50000美元、70000美元、130000美元和160000美元。通过当地银行筹措资金总计最高达到1500万美元。问各种类型的住宅分别应建多少单元才能使得税收总额达到最大？

最优方案是，应该拆旧住宅245套，建立单户、双户、三户住宅分别为36、98、45套，不建立四户住宅。总税收额343700美元。

表2—25最优货车租赁方案新合同一月二月三月四月五月六月3月期23000240004月期002100005月期000000总车数430430440450450450表2—30购入的组件数量组件名称轮子棒材保险杠底盘驾驶室车门窗购买数量120060060030030006000组件名称风挡蓝色集装箱红色油罐蓝色发动机红色发动机车头灯购买数量3000300030003000300012000表2