《管理运筹学》讲稿(第1-2章)概述课件

《管理运筹学》

第1章李存芳博士/副教授/硕士生导师研究领域：战略管理、组织行为、运营管理讲授课程：管理运筹学、管理系统工程、运营管理经济学单位：江苏师范大学管理学院物流管理系

E-mail：licf66@163.com1教材与参考书籍教材：魏晓平等编.管理运筹学，中国矿业大学出版社，2011参考书：钱颂迪,甘应爱等.运筹学,清华大学出版社，2001宁宣熙.运筹学实用教程,科学出版社，2007徐辉,张延飞.管理运筹学,同济大学出版社,2011郭耀煌等.运筹学.西南交通大学出版社,19952讲授提纲第一章绪论第二章线性规划的基本问题第三章线性规划的对偶问题第四章线性规划的灵敏度分析第五章运输问题分析第六章目标规划第七章整数规划第八章图与网络第九章网络计划技术3考核方式结课考试：笔试（

闭卷）

70%作业与案例研究：结合企业实际进行应用30%4管理运筹学的称谓管理运筹学是一门研究如何最优安排的学科。

OperationsResearch日本译作“运用学”香港、台湾译为“作业研究”我国译作“运筹学”源于《史记》中刘邦赞誉张良“运筹帷幄中,决胜千里外”。取“运筹”二字，体现运心筹谋、策略取胜司马迁5第一章绪

论一、发展历史二、学科作用三、学科性质四、工作程序五、学科体系六、学习要求6§1-1发展历史

1.早期的运筹思想

(1)齐王赛马

孙膑(约公元前380-432),孙武的后世子孙,战国中期著名军事家,担任齐国将领田忌的军师.

齐将田忌与齐王赛马,孙膑献策:以下马对齐王上马,以上马对齐王中马,以中马对齐王下马.结果田忌以一负两胜而获胜.7

(2)渭修皇宫宋真宗年间(公元1008一1017年),都城开封里的皇宫失火,需要重建.丁渭受命负责限期重新营造.丁渭将挖土、运送物材、处理废弃瓦砾等三件工程一蹴而成,节省的工费数以亿万计.

8(3)沈括运粮沈括(1031-1095年),北宋时期大科学家、军事家.在率兵抗击西夏侵扰的征途中,曾经从行军中各类人员可以背负粮食的基本数据出发,分析计算了后勤人员与作战士兵在不同行军天数中的不同比例关系；同时也分析计算了用各种牲畜运粮与人力运粮之间的利弊,最后做出了从敌国就地征粮,保障前方供应的重要决策.从而减少了后勤人员的比例,增强了前方作战的兵力.9

2.军事运筹学阶段

20世纪40年代（二战期间）诞生于英美。问题与对策：1940年，英国为对付德国空军的空袭，使用了雷达，但没有科学布局，效果不好。——拟建立空防预警系统。为对付德国海军的潜艇——拟以深水炸弹代替飞机射击。解决方案：成立运筹学小组，称OperationalResearch，意为作战研究。著名的“Blackett马戏团”：由3位生理学家、2位数学物理学家、1位天体物理学家、1位陆军军官、1位测量员、1位普通物理学家、2位数学家组成。10成效：英美等国蠃得英伦三岛空战、太平洋岛战、北大西洋战争的胜利。

3.管理运筹学阶段战后许多从事运筹学研究的科学家转向了民用问题的研究，使运筹学在企业管理方面的应用得到了长足进展。——1947年美国数学家乔治·伯纳德·丹兹格（G.B.Dant-zig）提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法，为这门学科奠定了基础。被称为“线性规划之父”。如“配餐问题”。11——1951年美国经济学家库普曼斯（J.C.Koopmans）把线性规划应用到经济领域，为此与利奥尼德·康托罗维奇(L.V.Kantorovich，苏联数学家)，一起因“最优资源配置理论的贡献”获1975年诺贝尔经济学奖。——20世纪50年代中期钱学森、许国志等将管理运筹学引入中国，取得了很大成就。12§1-2学科作用

1.量化管理的重要性

管理科学是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策的一门学科。目的：用科学方法分析管理问题，为管理者决策提供依据目标：在企业经营内外环境的限制下，实现资源效用最大组织中存在的问题定量分析定性分析评价与评估决策量化管理是第一步,它导致控制,并最终实现改进如果不能量化某些事情，那么就不能理解它如果不能理解它，那么就不能控制它如果不能控制它，那么就不能改进它

——H.JamesHarrington定性到定量分析，数量界限的重要性：量变引起质变13听一场音乐会：情况1：网络订票的票价500元，不去可退票。在你马上要出发的时候，发现你把最近的价值500元的电话卡弄丢了。你是否还会去听这场音乐会？情况2：假设昨天花500元钱买一张今晚的音乐会取票单。在你出发时，发现把票单丢了。如果去听音乐会，就必须再花500元钱买张票，去还会不去？

2.量化思考使人理性

——实验表明，大部分的回答者仍旧会去听——结果却是，大部分人回答说不去了14§1-3学科性质

1.研究对象美国运筹学会给出定义：“运筹学是一门在紧缺资源的情况下，如何设计与运行一个人——机系统的决策科学。”一般定义：“运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。”研究对象：经济和管理活动中能用“数量关系”描述的如运营、规划与组织管理问题。2.学科特点强调科学性和定量化强调应用性和实践性强调整体性和系统性15§1-4工作程序管理者制定决策：管理运筹学的步骤：明确问题环境分析确定目标制定准则收集资料数量关系结构分析数学模型制定决策方案选择算法求解方案优选否是方案实施持续改进识别问题量化分析建立模型软件求解结果分析确定方案实施方案控制管理者解的分析16§1-5学科体系

1.管理问题

需求预测产品的市场需求量有多大，需求类别如何，对企业盈利有何影响?生产计划在有限资源约束下，生产什么，生产多少，获利最大？资源配置需要哪些资源，如何进行最优配置，资源紧缺性如何，以什么代价获取?作业排序作业的重要次序如何，作业的顺序安排如何?市场营销广告预算、媒介选择、产品定价、销售计划等如何安排？运输问题最佳运输线路是哪条？物流配送集载如何优化？物流设施布局如何设置？设施选址运营点如何选择，需要哪些运作设施，设施如何布局?库存控制应保持多大库存量，何时应进行订货，订货批量多少为宜?项目规划项目完工工期多长为宜，哪些作业起关键性作用，资源如何分配?设备更新设备运转状况如何演进，运行可靠性如何，何时和如何更新或改造?人力资源人员需求预测，技能要求，编制与任务指派，绩效测评，留用多长时间?财务资金资金投放的数量，从何处进行融资，资金成本是多少?172.学科内容

模型类型解决的典型办法线性规划在线性目标和约束条件间取得最优化结果整数规划在线性目标和约束条件间寻求整数决策最优目标规划在相对立的目标间寻得多目标妥协的满意解动态规划寻求多阶段动态系统的整体决策优化问题网络分析寻求网络路径、流量分布、网络瓶颈及其改进网络计划用各种作业和结点的网络排列来说明项目实施计划管理决策依据决策准则权衡比较备选方案的决策结果库存模型寻求订货、存储和缺货等库存成本降至最低的经济批量183.学科应用管理既是科学又是艺术低层管理的科学成分较多，高层管理的艺术成分较多运营管理需较多管理科学，人力资源管理需较多管理艺术例行管理需要较多管理科学，例外管理需要较多管理艺术M:管理决策问题MC:定量解决方法方案选择依据问题导向技术支持战略决策营销决策生产安排物流运营资本运作人力资源方案优选应用统计线性规划整数规划目标规划网络计划网络分析决策分析动态规划……管理科学：运用合理的分析来改善决策的制定管理者:制定决策19§1-6学习要求

如何学习重点在结合实际的应用发挥自己理论联系实际的能力强化结合实际问题建立管理优化模型的能力强化对于解决问题的方案或模型的解的分析与应用能力20第2章线性规划的基本问题Subtitle内容提要第一节线性规划问题及其数学模型第二节线性规划问题的解第三节线性规划的单纯形解法第四节确定初始基本可行解的大M法21§2-1线性规划问题及其数学模型线性规划研究两类问题：一类，给定了一定数量的人力、物力、财力等资源，研究如何运用这些资源使完成的任务最多；另一类，给定了一项任务，研究如何统筹安排，才能以最少的人力、物力、财力等资源来完成该项任务。——本质上就是寻求某个整体指标的最优化问题。22——生产计划问题例1某企业生产甲、乙两种产品，生产工艺路线为：各自的零部件分别在设备A、B加工，最后都需在设备C上装配。经测算得到相关数据如表所示。问题：应如何制定生产计划，使总利润为最大。

据市场分析，单位甲、乙产品的销售收益分别为3和5元，试确定获利最大的产品生产计划。

产品设备工时消耗甲乙工时成本元/h加工能力hABC

2002342015101610322.1.1线性规划问题

典型问题23(1)设x1为甲产品的产量，x2为乙产品的产量。（决策变量）(2)产量会受设备加工能力制约。（约束条件）设备A的加工能力约束条件表达为：

2x1≤16同理，设备B的加工能力约束条件表达为：

2x2≤10设备C的装配能力也有限，其约束条件为

3x1+4x2≤32(3)目标是企业利润最大化。（目标函数）

maxZ=

3x1+5x2

(4)另外，甲乙产品的产量为非负

x1≥0，x2≥0综上，问题的LP模型：求一组变量x1

、x2

24——物资调运问题例2某产品商有3个工厂（产地）A1、A2、A3，其经销商有4个需求市场（销地）B1、B2、B3、B4。已知各厂的日产量、各经销商的日销售量及从Ai到Bj

的单位运费为Cij。为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。

销地产地B1B2B3B4日产量A1632550A2758420A3329730日销量2030104025(1)设从Ai（i=1,2,3）到Bj(j=1,2,3,4)的调运量为xij（决策变量）(2)目标是运费最小（目标函数）MinZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34

(3)实现供需平衡：产量之和等于销量之和（约束条件）供应平衡条件（当日产量全部运走）x11+x12+x13+x14=50x21+x22+x23+x24=20x31+x32+x33+x34=30销售平衡条件（当日送货全部售完）x11+x21+x31=20x12+x22+x32=30x13+x23+x33=10x14+x24+x34=40非负性约束

xij≥0(i=1,2,3；j=1,2,3,4)

26归纳起来，此问题的LP模型为：

求一组变量xij（i=1,2,3；j=1,2,3,4)，满足下列约束条件x11+x12+x13+x14=50x21+x22+x23+x24=20x31+x32+x33+x34=30x11+x21+x31=20x12+x22+x32=30x13+x23+x33=10x14+x24+x34=40

xij≥0(i=1,2,3；j=1,2,3,4)

使目标函数

Z（x）=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34达到最小27——混合问题

例3某合金产品由A、B两种金属混合制成，按合金性能要求，金属A不能超过6%，金属B不能少于92%（其它杂质不计）。若金属A、B的价格分别为2元/千克和5元/千克。那么，本合金应该按怎样的比例混合配料才能使其原料成本最低？

（1）设1千克合金产品中A、B两种金属含量分别为x1、x2(决策变量)

（2）为满足合金对金属A、B含量的限制，应有：（约束条件）

x1≦0.06

x2≧0.92

而金属A、B构成合金的含量总平衡关系式为（平衡条件）

x1+x2=1

当然，金属A、B的含量均不能为负值，即有

x1

≥0，x2

≥028（3）目标是使原料成本

Z（x）=2x1+5x2达到最低。

于是，得此问题的LP模型为：求一组变量x1、x2，满足下列约束条件

x1≦0.06x2≧0.92x1+x2=1

x1

，x2≥0使目标函数

Z（x）=2x1+5x2达到最小。29

问题特征

上述三个案例，尽管其实际问题的背景有所不同，但讨论的都是资源的最优配置问题。它们的共同特征：——目标明确。决策者寻求某个整体目标最优。如最大收益、最小成本等。——多种方案。决策者可从多种可供选择的方案中选取最佳方案。如不同产品的生产方案和物资调运方案等。——资源有限。决策者的行为必须受到限制。如产品的生产数量受到资源供应量的限制；物资调运既要满足各销地的销售量，又不能超过各产地的生产量。——线性关系。约束条件及目标函数均保持线性关系。

具有以上特征的决策问题，被称为线性规划问题。30

——用一组非负决策变量（x1,x2,…,xn

）表示的一个决策问题；决策变量是决策问题待定的量值。

——存在一组等式或不等式的线性约束条件；任何管理决策问题都是限定在一定的条件下求解；约束条件是决策方案可行的保障。

——有一个希望达到的目标，可表示成决策变量的极值线性函数。目标函数是衡量决策优劣的准则，如时间最省、利润最大、成本最低；有的目标要实现极大，有的则要求极小。2.1.2线性规划的数学模型

数学模型的共同特征31

数学模型的一般形式式中：cj（j=1,2,…,n）

——价值系数；bi（i=1,2,…,m）

——限定系数；aij（i=1,2,…,m;j=1,2,…,n）

——技术系数.xj（j=1,2,…,n）——决策变量；S.t——“Subjectto”（在----条件下）的缩写。每一个约束条件只持有一种符号（≤或=或≥）。32由于线性规划模型有多种形式，为了讨论和求解的方便，需要在这多种形式中规定一种形式（标准形式）。

线性规划模型的标准型为

2.1.3线性规划模型的标准形式

MaxZ（x）=c1x1+c2x2+…+cn

xn

s.t.a11x1+a12x2+…+a1J

xJ+…+a1n

xn=b1

a21x1+a22x2+…+a2J

xJ

+…+a2n

xn=b2…………

am1x1+am2x2+…+amJ

xJ+…+amn

xn

=bm

x1，x2

，…，xn≥033

线性规划模型标准形式的特点

（1）目标函数是求极大值的(Max)；（2）所有决策变量都是非负的(xJ≥0

)；（3）所有约束条件都是“=”型的(方程)；（4）所有常数项都是非负的(bi

≥0

).

线性规划模型标准形式的简缩形式

(1)代数式

(2)向量式

34

(3)矩阵式

A：技术系数矩阵，简称系数矩阵（m×n）；一般m＜n，m、n为正整数b：可用的资源量，称资源向量；C：决策变量对目标的贡献，称价值向量；X：决策向量。35(1)对于极小化原问题minZ=CX，则令Z'=-Z，转为求maxZ'=-CX(2)若某个bi<0，则以－1乘该约束两端，使之满足非负性的要求。(3)对于≤型约束，则在左端加上一个非负松弛变量，使其为等式。(4)对于≥型约束，则在左端减去一个非负剩余变量，使其为等式。(5)若某决策变量xk无非负约束（自由变量），则令xk=x'k

-x"k

，(x'k≥0,x"k≥0)。2.1.4线性规划标准型转换方法36举例例4把例1的模型化为标准型

例1的数学模型为解：在各个不等式的左边分别加上松驰骋变量，使之变成等式，从而化为标准型：37解：通过以下四个步骤：例5把下列线性规划的模型化为标准型38（1）目标函数两边乘上-1化为求最大值；（2）以

代入目标函数和所有的约束条件中，其中；（3）在第一个约束条件的左边加上松驰变量x4；（4）在第二个约束条件的左边减去剩余变量x5。可得标准型392.2.1线性规划问题解的概念

由上节分析可知线性规划模型的标准型为§2-2线性规划问题的解

MaxZ（x）=c1x1+c2x2+…+cn

xn

（2-1）

s.t.a11x1+a12x2+…+a1J

xJ+…+a1n

xn=b1

a21x1+a22x2+…+a2J

xJ

+…+a2n

xn=b2（2-2）

…………

am1x1+am2x2+…+amJ

xJ+…+amn

xn

=bm

x1，x2

，…，xn≥0（2-3）40（1）可行解

满足约束条件AX=b和X≥0的解X=(x1,x2,…,xn)T称为线性规划问题的可行解，而所有可行解的集合称为可行域。（2）最优解

使目标函数最优的可行解，称为最优解。（3）基本解

设A是约束方程组（2-2）的m×n阶系数矩阵，其秩为m，则A中任意m个线性无关的列向量组成的m×m阶子矩阵称为线性规划的一个基矩阵（简称为一个基，最多有个），记为B。显然，B为非奇异矩阵，即︱B︱≠0。41

组成基矩阵的m个列向量称为基向量，其余n-m个向量称为非基向量；与m个基向量对应的m个变量称为基变量，其余的n-m个变量则被称为非基变量。显然，基变量随着基的变化而改变，当基被确定以后，基变量和非基变量也随之确定。

若令约束方程组（2-2）中的n-m个非基变量为0，再对余下的m个基变量求解，所得到的约束方程组的解称为基本解。

问题的实质：一个基矩阵（m×m）→对应一组基向量（P1,P2,…,Pm）→对应一组基变量（x1,x2,…,xm）→令相应一组非基变量为0（0,0,…,0）→由克莱姆法则求出唯一解→再加上非基变量（0,0,…,0）→便得一个基本解。42引例：设B=（P1,P2,…,Pm）为线性规划的一个基，于是xi(i=1,2,…,m)为一组基变量，xj

(j=m+1,m+2,…,n)就为相应的非基变量。现令非基变量xm+1=xm+2=…=xn=0，方程组（2-2）就变为

a11x1+a12x2+…+a1J

xJ+…+a1mxm=b1

a21x1+a22x2+…+a2J

xJ

+…+a2m

xm=b2…………

am1x1+am2x2+…+amJ

xJ+…+amm

xm

=bm

此时方程组有m个方程、m个未知数，可唯一地解出(克莱姆法则)：

x1,x2,…xm43则向量

X=(x1,x2,…,xm,0,…,0)T(其中含有n-m个0)就是对应于基B的基本解。（4）基本可行解

满足非负条件（2-3）的基本解称为基本可行解；对应于基本可行解的的基，称为可行基。

显然，基本可行解既是基本解，又是可行解。由于约束方程组（2-2）的基的数目最多为，而且基本解与基一一对应，故基本解的数目也不多于。一般，基本可行解的数目要小于基本解的数目，最多两者相等。44其相互关系图示如下：非可行解可行解基本解基本可行解45解：将已知模型化为标准型：例6求下列线性规划问题的所有基本解，并指出哪些是基本可行解。46显然，m=2；秩=2

由于其中任意两个列向量都是线性无关的，故有个不同的基，对应着6个不同的基本解（表2-4）。

由于满足非负条件（2-3），所以为基本可行解；而两个基本解不满足非负条件，因此为非可行解。

其系数矩阵为47表2-4482.2.2线性规划问题的图解法

仍以例1为例分析：（1）确定线性规划的可行域可行域：满足所有约束条件的解的集合，即所有约束条件共同围成的区域。

maxZ(x)=

3x1+5x22x1≤162x2≤103x1+4x2≤32x1≥0,x2≥0

图中阴影区域上任何一点的坐标（x1,x2）都同时满足所有约束条件。S.t.3x1+4x2=322x1=162x2=10x1x248102580ABCD49(2)寻找线性规划的最优解点目标函数Z=

3x1+5x2

代表以Z为参数的一族平行线。2x1=162x2=10x1x248103583x1+4x2

=320ABCDZ=30Z=37Z=15目标函数线,通过原点时Z=0;距离原点越远Z值越大;即将脱离可行域的最后一点Z值最大,图中的C点就是最优解点.50通过求解方程组:便得C点坐标:x1=4;x2=5代入目标函数得:z=37结论:安排甲产品生产4件、乙产品生产5件，可使总利润达到最大为37。512.2.3线性规划解的几种特殊情况

1、唯一最优解：只有一个最优点(上节的案例)2、多重最优解：无穷多个最优解在例1中,当乙产品市场收益下降到4元，其数学模型变为

2x1=162x2=103x1+4x2

=32x1x248103580ABCDZ=24Z=32Z=1252在一批等值线中,离原点最远又与可行域有交点的直线恰与BC重合,这表明以BC为端点的线段上的任意点都使目标函数取得相同的最大值----该线性规划有多重最优解.3、无界解：可行域无界，目标值无限增大

(缺乏必要约束)53其最优解为：X1=0，X2=0，目标函数值Z=0（有下界）

-----因此，要根据具体模型来分析无界可行域与无界解间的关系。

可行域的拓展方向与目标函数的拓展方向一致----目标函数无上界，Z（x）→∞。问题的原因可能是遗漏了约束条件。需要指出的是，无界可行域并不一定意味着目标函数无界。如将本例的目标函数改为544、没有可行解：线性规划问题的可行域是空集

(约束条件相互矛盾)由上图可知：没有能同时满足所有约束条件的点，可行域是空集------没有可行解。

552.2.4线性规划解的基本性质(1)由线性不等式组成的可行域是凸多边形(凸多边形是凸集);凸集定义：集合内部任意两点连线上的点都属于这个集合abcd(2)凸多边形的顶点与基本可行解一一对应;(3)如有可行解,一定有基本可行解(凸多边形必有顶点);(4)基本可行解的个数是有限的(凸多边形的顶点个数有限);(5)线性规划问题若有最优解,一定会在凸多边形某个顶点上取得(可以在基本可行解中找到).56------因此,求解线性规划问题,只需在基本可行解(凸多边形的顶点)中寻找即可.57§2-3线性规划问题的单纯形解法

2.3.1线性规划解题思路先找到一个初始基可行解，也就是找到一个初始可行基，设法判断这个基可行解是不是最优解。如果是最优解，就得到这个线性规划问题的最优解；如果判断出不是最优解，就设法由这个可行基按一定规则变化到下一个可行基，然后再判断新得到的基可行解是不是最优解；如果还不是，再接着进行下一个可行基变化，直到得到最优解。58仍以例1来讨论,该问题的数学模型为2.3.2单纯形法的基本求解思路

maxZ(x)=

3x1+5x22x1≤162x2≤103x1+4x2≤32x1≥0,x2≥0分析:首先将约束条件中加入松驰变量,化成标准型:

maxZ(x)=

3x1+5x2+0x3+0x4+0x5（2-4）

2x1+x3

=16（2-5）

2x2

+x4=10（2-6）

3x1+4x2

+x5

=32（2-7）

x1,x2,x3,x4

,x5≥059（1）找出一个基本可行解作为初始解

在约束条件中，x3,x4,x5的系数向量构成单位矩阵，成为线性规划的一个基。x3,x4,x5就是基变量，x1,x2为非基变量。若令非基变量x1=0,x2=0，可得x3=16,x4=10,x5=32。显然，这就是一个基本可行解：

X（0）=（0,0,16,10,32）

（2）检验判断是否为最优解

将X（0）=（0,0,16,10,32）代入目标函数,可知x1=0,x2=0，Z(X（0）)=0,即为图中的原点.----两种产品产量为0,收益也为0.显然不会是最优解.

需要考虑寻求一个新的基本可行解,且使目标函数值增加.60（3）选择进基变量

从目标函数可以看出,

由于x1,x2前面的系数均为正，当x1或x2由现在的0变成非0时，均可使目标函数值增加.

由于x2的系数比x1的系数大（收益增长率高）。

----故选择x2为进基变量。(大进)那么，为了保证新解仍为基本可行解，在x3,x4,x5中让谁作为出基变量呢？为此，可把约束条件中的原基变量x3,x4,x5用非基变量表示出来，即有61

x3=16-2x1x4=10-2x2

x5=32-3x1-4x2

因为x1仍为非基变量（因为x2要进基），可令x1=0，于是有

x3=16x4=10-2x2

x5=32-4x2若取x4=0，则x2=10/2；若取x5=0，则x2=32/4。为了保证新解中的x3,x4

,x5≥0，一定有

x2=min﹛10/2,32/4﹜=562

因此，选择x4

为出基变量----最小比值法。换言之，出基变量应选择随着进基变量增大而最先变为0者。（小出）为了简便地得到一个新的基本可行解，可对约束方程组进行变换，即将（2-6）式中的x2

的系数变成1，（2-5）和（2-7）两式中的x2的系数变成0。其变换过程为：以1/2乘（2-6）式，得（2-9）；以-2乘（2-6）式加到（2-7），得（2-10）。于是，新的约束方程组为：

2x1+x3

=16（2-8）

1x2

+（1/2）x4=5（2-9）

3x1

-2x4

+x5

=12（2-10）

63（4）推出新的基本可行解若令此时的非基变量x1=0,x4=0；基变量x3,x2,x5的值可以从右边常数项直接得到.所以推出新的基本可行解:

X（1）=（0,5,16,0,12）该解对应于图示可行域的顶点D.

相应地将目标函数用非基变量表示,变成:

Z(X（1）)=25+3x1–(5/2)x4（2-11）

而当x1=0,x4=0时，Z(X（1）)=25。显然，

Z(X（1）)＞Z(X（0）)

结果表明：生产产品乙5个单位，可获得的收益为25。64（5）选择新的进基变量

从（2-11）式可以看出，当非基变量x1的值增加（由0变成非0）时，仍可使目标函数值增加。因此，还没有得到最优解。（当且仅当非基变量的系数均为负，目标函数才能达到最优）进而，将x1作为新的进基变量，分析约束方程组（2-8）、（2-9）、（2-10）式可知，

x1=min﹛16/2,12/3﹜=4，故选择x5作为新的出基变量。

重复上述变换过程，得：

+x3+（4/3）x4-

（2/3）x5

=8（2-12）

x2

+（1/2）x4=5（2-13）

1x1

-（2/3）x4

+（1/3）x5

=4（2-14）

65

令此时的非基变量x4=0,x5=0；基变量x3,x2,x1的值可以从右边常数项直接得到.所以推出新的基本可行解:

X（2）=（4,5,8,0,0）

------该解对应于图示可行域的顶点C.（6）检验判断是否为最优解（返回（2）继续检验）

将目标函数用非基变量表示,（2-11）式变成:Z(X（2）)=37-（1/2）x4–x5

（2-15）由于目标函数（2-15）的所有非基变量的系数均为负，故当x4

或x5增加时，目标函数值只会减少，而无法再使目标函数值增大。因此X（2）=（4,5,8,0,0）就是最优解，目标函数的最大值为37。662.3.3单纯形表

从前面代数解法中可以看出，求最优解的过程是一种迭代选优的过程，即从一个基本可行解迭代到另一个基本可行解，且使目标函数值一次比一次好。而在几何上则是从可行域的一个顶点迭代到另一个相邻的顶点。

为了方便运算，可以将代数运算表格化。

分析结果表明，企业应安排计划甲生产4个单位、乙生产5个单位，可获取最大收益为37个单位。67仍以例1来讨论,该问题的数学模型为

maxZ=3x1+5x2+0x3+0x4+0x52x1+x3=162x2+x4=103x1+4x2+x5=32

cj比值(θi)CBXBb/检验数λjx1x2x3x4x535000162010010020103234001x3x4x5000035000-10/2=532/4=8可以推导后选：小出先选：大进68单纯形表内涵说明：

——cj行的数字是目标凼数中各变量的系数，下面一行是与之相对应的变量；

——XB列填入的是基变量，

——CB列填入的是与基变量相对应的目标凼数中的系数，它们随着基变量的改变而变化；

——b/列填入的是约束方程组右端的常数，即非基变量为0时，基变量的取值；

——中间为约束条件中的变量系数；

——比值θi列是在确定出基变量时，用于最小比值法计算的数字。

69

——最后一行称为检验数（λj）行，它是把目标函数用非基变量表示时的非基变量的系数。利用检验数便可以判断此表所对应的基本可行解是否为最优解。

当所有的检验数均不大于0时，表明目标凼数值不可能再增加，即得到最优解。70162010050101/2012300-21x3x2x5050300-5/205-4cj比值CBXBb/检验数λjx1x2x3x4x535000检验数λj80014/3-2/350101/204100-2/31/3x3x2x1053000-1/2-1最优解:X*=(4,5,8,0,0)T，Z*=37后选：小出先选：大进712.3.4单纯形法的计算步骤（1）确定初始基本可行解，建立初始单纯形表。

（2）进行最优性检验。若所有的检验数λj≤0，则已得到最优解，停止运算。否则，转下一步。

（3）确定进基变量Xk

。在所有的正检验数中选择最大的检验数所对应的非基变量为进基变量(大进)。如果进基变量Xk所在列的所有系数都≤0，则该问题为无界解，停止运算；否则，进行下一步。

（4）确定出基变量Xs

。按最小比值法则求出

故Xs为出基变量（小出）。转下一步。

72（5）以ask为主元素，进行变换，得到新的单纯形表。将主元素变成1，同列的其它元素变成0，可得一组新的基本可行解，返回第二步，重新进行判别运算，直到取得最优解或判定无解。一般说来，凡是在最优单纯形表中出现检验数为0的非基变量，就存在多个最优解——多重最优解；凡是进基变量所在列的所有系数均小于0，此线性规划问题为无界解。732.3.5单纯形的管理启示2x1=162x2=103x1+4x2

=32x1x24812590ABC(4,5)DX0=(0,0,16,10,32)TX1=(0,5,16,0,12)TX1=(4,5,8,0,0)T企业管理过程也是如此，把现有方案作