第一章线性规划及单纯形法14课件.ppt

1、 管理运筹学管理运筹学 牧云志牧云志 13858057439 WELCOME TO Management Operations Research 管理运筹学管理运筹学 绪论“夫运筹帷幄之中，决胜千里之外夫运筹帷幄之中，决胜千里之外”史记.高祖本纪运筹学起源之一 军事 古代军事运筹学思想古代军事运筹学思想“孙子兵法”（1981年美国军事运筹学会出版了一本书，书中第一句话就是说孙武子是世界上第一个军事运筹学的实践家）；中国古代运筹学思想的例子还有：田忌赛马、围魏救赵等等。国外历史上的阿基米德、伽利略研究过作战问题；第一次世界大战时，英国的兰彻斯特（Lanchester）提出了战斗方程，指出了数量优

2、势、火力和胜负的动态关系；美国的爱迪生为美国海军咨询委员会研究了潜艇攻击和潜艇回避攻击的问题。鲍德西（鲍德西（Bawdsey）雷达站的研究）雷达站的研究1939年，以Blackett为首的一个研究小组（代号“Blackett 马戏团”），研究的问题是：设计将雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调，作了系统的研究，并获得成功。“Blackett马戏团”在秘密报告中使用了“Operational Research”，即“运筹学”。(OR)大西洋反潜战大西洋反潜战 研究如何打破德国对英吉利海峡的海上封锁运筹学的正式产生：第二次

3、世界大战运筹学起源之二 管理 泰勒泰勒的时间动作研究、甘特的用于生产计划与控制的“甘特图”、吉尔布雷思夫妇的动作研究等 爱尔朗爱尔朗（Erlong）的排队论公式19091920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式。尤其是1909年的论文“概率与电话通话理论”，开创了运筹学的重要分支排队论。运筹学起源之三 经济（数理经济学）Von Neumann（冯（冯诺依曼诺依曼）与对策论）与对策论 1932年，Von Neumann提出一个广义经济平衡模型；1939年，提出了一个属于宏观经济优化的控制论模型；1944年，与Morgenstern（摩根斯顿）共

4、著的对策论与经济行为开创了对策论分支。康托洛维奇与康托洛维奇与“生产组织与计划中的数学方法生产组织与计划中的数学方法”30年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得了很多重要成果。1939年，出版了堪称运筹学的先驱著作生产组织与计划中的数学方法，其思想和模型被归入线性规划范畴。诺贝尔经济学奖从1969年首发至今的获奖者中就有多位是运筹学家。1975年诺贝尔经济学奖授给了库普曼和康脱罗维奇，以表彰首先将线性规划与经济问题相联系而做出的贡献；1994年诺贝尔经济学奖授给了三位博弈论专家：纳什、泽尔腾、海萨尼。博弈论已经成为当代经济学的基石。2005年以色列经济学家罗

5、伯特-奥曼和美国经济学家托马斯-斯切林，因“通过博弈论分析加强了我们对冲突和合作的理解”所作出的贡献而获奖。我国运筹学的发展 50年代中期由钱学森等由西方引入，1957年正式定名为运筹学。1970年后，在华罗庚教授的直接指导下，在全国范围内推广统筹法和优选法，并取得了卓著成效，同时也使运筹学的研究队伍迅速壮大。随后，中国运筹学会于1980年成立，1982年作为正式成员加入了国际运筹学联合会（IFORS）。运筹学在科学技术体系中的地位运筹学的主要分支排队论（Queuing Theory）决策论（Decision Theory）对策论（Game Theory）存贮论（Inventory Theor

6、y）线性规划（Linear Programming）非线性规划（Nonlinear Programming）动态规划（Dynamic Programming）图论与网络分析（Graph Theory and Network Analysis）生产结构优化投资组合优化资源分配优化工程计划优化服务系统优化军事活动机会选择订货库存管理运筹学研究的运筹学研究的基本步骤基本步骤分析和分析和表述问题表述问题建立模型建立模型求解模型求解模型优化方案优化方案解的检验解的检验模型修正模型修正解的实施解的实施解的控制解的控制引例：在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到 最大的效益最大

7、的效益。第一章第一章 线性规划及单纯形法线性规划及单纯形法线性规划（Linear Programming，LP）解决有限资源的最佳分配问题求解方法：图解法 单纯形法 第一章第一章 线性规划及单纯形法线性规划及单纯形法 1 线性规划问题及其数学模型 2 线性规划问题的图解法 3 线性规划问题解的基本性质 4 单纯形法的基本原理 5 单纯形法的计算步骤 6 单纯形法的进一步讨论 7 线性规划应用举例 第一章 习题本章学习要求 1了解一般线性规划问题的数学模型。2掌握线性规划问题的图解法。3理解单纯形法基本原理。4掌握单纯形法的计算步骤。5能够将实际问题抽象为数学模型。重点和难点重点和难点：图解法、

8、单纯形法、单纯形法的原理及计算步骤1 1 线性规划问题及其数学模型线性规划问题及其数学模型一、线性规划问题的提出一、线性规划问题的提出例例1.1 资源合理利用问题资源合理利用问题 某厂生产甲、乙两种产品，要消耗A、B、C三种资源，已知每件产品对三种资源的消耗、这三种资源的现有数量和每件产品可获得的利润见下表：如何安排生产计划，使总利如何安排生产计划，使总利润最大（列出数学模型）润最大（列出数学模型）产品资源甲乙资源限制A3265B2140C0375单件利润15002500线性规划模型的三要素线性规划模型的三要素1.决策变量：需决策的量，即待求的未知数；决策变量的取值要求非负。2.约束条件：为实

9、现优化目标需受到的限制，用决策变量的等式或不等式表示。LP的约束条件，都是决策变量的线性函数。3.目标函数：需优化的量，即欲达的目标，用决策变量的线性表达式表示；有的目标要实现极大，有的则要求极小。(1)决策变量决策变量 要决策的问题是甲、乙两种产品的产量，因此有两个决策变量：设x1为甲产品产量，x2为乙产品产量。(2)约束条件约束条件 生产这两种产品受到现有资源的制约。123265xx 例1.1 解：解：12240 xx23275x 12,0 x x 资源A的限制：资源B的限制：资源C的限制：非负约束：(3)目标函数目标函数 目标是利润最大化，用z表示利润，即求 的最大值。121500250

10、0zxx121212212max150025003265240.3275,0zxxxxxxstxx x综上所述，该问题的数学模型可表示为：20 模仿例1.1的解题步骤：引例（列出数学模型）引例的数学模型：1212121212max7129436045200.310300,0zxxxxxxstxxx x1 1 线性规划问题及其数学模型线性规划问题及其数学模型一、线性规划问题的提出一、线性规划问题的提出 原料化学成分甲乙产品成分最低含量A1234B232C3155单位成本32例例1.2 配料问题（配料问题（P.2）121212121212min3212342323155.1,0zxxxxxxxxs

11、txxx x231 1 线性规划问题及其数学模型线性规划问题及其数学模型一、线性规划问题的提出一、线性规划问题的提出例例1.3 运输问题运输问题(P.2)(P.2)销地产地 B1B2B3B4产量（t）A121257152000A2515137151100需求量（t）17001100200100总产量总产量=总需求量（产销平衡）总需求量（产销平衡）111213142122232411121314212223241121122213231424min2125715515137152000110017001100.2001000(1,2;1,4)ijzxxxxxxxxxxxxxxxxxxxxstxx

12、xxxij练习1 1 线性规划问题及其数学模型线性规划问题及其数学模型二、线性规划问题的数学模型二、线性规划问题的数学模型线性规划模型的一个基本特点基本特点：目标和约束均为变量的线性表达式线性表达式如果模型中出现如的非线性表达式，则不属于线性规划。线性规划问题的线性规划问题的一般形式：一般形式：11 11221121 1222221 122,0(1,2,)nnnnmmmnnmja xa xa xba xa xa xba xaxaxbxjn （或）（或）（或）s.t.nnxcxcxcz2211minmax）（或目标函数约束条件其中：为已知常数ijaibjc(1,2,;1,2,)im jn11 1

13、1221121 1222221 122.0(1,2,)nnnnmmmnnmja xa xa xba xa xa xbsta xa xa xbxjn1 122maxnnzc xc xc x线性规划问题的线性规划问题的标准形式：标准形式：其中：为非负值ib(1,2,)im11max 1.0 1njjjnijjijjzc xa xbimstxjn（，）（，）简记形式：简记形式：max.0zcxAxbstx矩阵形式：矩阵形式：其中：其中：12,ncc cc12,Tnxx xx12,Tmbb bb111212122212nnmmmnaaaaaaAaaa系数矩阵价值向量决策向量资源向量（右端向量）标准形式

14、：标准形式：），（），（njxmibxaxczjinjjijnjjj1 01 max11LP模型标准形式特点：模型标准形式特点：4.决策变量取值决策变量取值非负非负。1.目标函数为目标函数为求极大值求极大值；2.约束条件全为约束条件全为等式等式；3.约束条件右端常数项全为约束条件右端常数项全为非负值非负值；一般线性规划问题如何化为标准型：一般线性规划问题如何化为标准型：1.目标函数求极小值：目标函数求极小值：njjjxcz1min令：令：，即化为：，即化为：zznjjjnjjjxcxczzz11min)max(max2.约束条件为不等式：约束条件为不等式：（1）当约束条件为）当约束条件为“”时

15、时如：如：122221 xx可令：可令：，显然显然1222321xxx03x（2）当约束条件为）当约束条件为“”时时如：如：18121021xx可令：可令：，显然显然04x181210421xxx 称为称为松弛变量。松弛变量。3x 称为称为剩余变量剩余变量。4x松弛变量和剩余变量统称为松弛变量。松弛变量和剩余变量统称为松弛变量。（3）目标函数中松弛变量的系数）目标函数中松弛变量的系数 由于松弛变量和剩余变量分别表示未被充分利由于松弛变量和剩余变量分别表示未被充分利用的资源以及超用的资源，都没有转化为价值和利用的资源以及超用的资源，都没有转化为价值和利润，因此润，因此在目标函数中系数为零在目标函

16、数中系数为零。12max712zxx原目标函数：1234max71200zxxxx3.约束条件右端常数项约束条件右端常数项bi0，则它是基可行解的充要条件是它的正分量所对应的列向量线性无关。如果LP问题有可行解，则它必有基可行解。如果LP问题有最优解，则必存在一个基可行解是它的最优解。二、线性规划问题解的基本性质二、线性规划问题解的基本性质 练习：P.37 7（2）3 3 线性规划解的基本性质线性规划解的基本性质三、线性规划问题解的几何意义三、线性规划问题解的几何意义 凸集凸集：设集合 是n维欧式空间的一个点集，如果对任何 及实数 都有 则称S是一个凸集。直观上，集合中任意两点连线上的一切点都

17、在该集合中，则称该集合为凸集。(1)(2),xxSnSR0,1(1)(2)(1)xxS70()()11,0,1,1,kkiniiiiiixRikxx设则称 (1)(2)(1)(2)SR,S,S,(1),01,S().nxxxxxxxx设凸集如果 不能用 中不同的两点表示为 则称 为 的一个极点 顶点(1)(2)(),.kxxx为点的一个凸组合凸组合：凸组合：极点（顶点）：极点（顶点）：71凸集凸集凸集凸集不是凸集不是凸集顶顶 点点.4 若LP问题存在可行域，则其可行域一定是凸集。LP问题的基可行解对应可行域的顶点。推论1.1 若LP问题的可行解集非空，则顶点集合是非空有限集。推论1.2 若可行

18、域有界，则LP问题的目标函数一定可以在可行域的顶点上达到最优。（证明）若LP问题在多个顶点处达到最优，则这些顶点的凸组合也是最优解。此时，该LP问题有无穷多最优解。线性规划的解题思路线性规划的解题思路 线性规划问题可以有无数个可行解，最优解只可能在顶点上达到，而有限个顶点对应的是基可行解，故只要在有限个基可行解中寻求最优解即可。从一个顶点出发找到一个可行基，得到一组基可行解，拿目标函数做尺度衡量一下是否最优。如若不是，则向邻近的顶点转移，换一个基再求解、检验，如此迭代循环目标值逐步改善，直至求得最优解。3 3 线性规划解的基本性质线性规划解的基本性质 单纯形法(Simplex Method)是

19、美国人丹捷格(G.Dantzig)1947年提出的。这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。4 4 单纯形法的基本原理单纯形法的基本原理4 4 单纯形法的基本原理单纯形法的基本原理一、单纯形法的引入一、单纯形法的引入 例1.7121212212max150025003265240.375,0zxxxxxxstxx x1234512312425max150025000003265240.3750,1,2,5jzxxxxxxxxxxxstxxxj标准化34512:,:,x x xx x相应的基变量非基变量为Step1：求初始基可行解0345100010001BPPPA的一个

20、3阶可逆子阵B0作为初始基：12345321002101003001APPPPP系数矩阵：将目标函数和基变量用非基变量表示：1231241252150025006532402753zxxxxxxxxxx120:0Nxxx 令(65,40,75)TBx 则(0)(0):(0,0,65,40,75):0Txz得到初始基可行解相应的目标函数值7712 15002500zxx分析34215:,:,x x xx x新的基变量非基变量为13242520(),65204007530 xxxxxxx仍为非基变量 又要满足变量的非负要求Step2：判断是否得到最优解22max1500,25002500()xx是

21、非基变量 的系数,确定 进基确定进基（换入）变量确定出基（换出）变量25565 40 75min,25 2130()xxx此时由基变量变成非基变量作为出基变量7834215:,:,x x xx x新的基变量非基变量为Step3：求新的基可行解1342102011003BPPPB1作为新的基：如何将目标函数和基变量用非基变量表示？1531541525250062500150032153311523125 3zxxxxxxxxxx2201031P初等行变换133232332100 65321006530102/3 1521010 40210104020011/3 1503001 7501001/3

22、 2501001/3 25A150:0Nxxx 令342(,)(15,15,25)TTBxx xx则(1)(1):(0,25,15,15,0):62500Txz得到新的基可行解相应的目标函数值79152500 62500 15003zxx分析14235:,:,x x xx x新的基变量非基变量为5314120(),15301520250 xxxxxx仍为非基变量 又要满足变量的非负要求判断是否得到最优解111500()xx是非基变量 的系数,确定 进基确定进基（换入）变量确定出基（换出）变量13315 15min,5 320()xxx 此时由基变量变成非基变量作为出基变量80求新的基可行解如何

23、将目标函数和基变量用非基变量表示？3513543525700005005001253921539125 3zxxxxxxxxxx21123330102/3 15101/302/9 520011/3 15002/311/9501001/3 2501001/3 25A350:0Nxxx 令142(,)(5,5,25)TTBxx x x则(2)(2):(5,25,0,5,0):70000Txz得到新的基可行解相应的目标函数值14235:,:,x x xx x新的基变量非基变量为(2)70000 xxz2142B P P PB2作为新的基：2142BPPP81(0)(0):(0,0,65,40,75)

24、:0Txz初始基可行解目标函数值(2)=(5,25,0,5,0)70000Txxzx2102030 x1102030O40ABCD(1)(1)(0,25,15,15,0)62500Txz82例1.7的过程分析标准化初始基可行解确定进基（换入）变量确定出基（换出）变量新的基可行解判断是否最优否进基变量、出基变量的选择规则（1）选进基变量max|0,1,kjjkmjn k对应的非基变量x 作为进基变量（2）选出基变量（最小比值准则）min|0,10irikikrkrbbaimaax 此时 为出基变量84练习二、单纯形法的基本原理二、单纯形法的基本原理 1、LP的典式 max.0zcxAxbstx标

25、准形式：1111max().0,0 BNBNBNBNzc B bcc B N xxB NxB bstxx对应于基B的典式：（）（）861NB N1N12():(,)NBmmncc B N非基变量的系数检验数(0)1Bzc B b1bB b1111122112211222221122.0(1,2,)mmmmnnmmmmnnmmmmmmmmnnmjxaxaxa xbxaxaxa xbstxaxaxa xbxjn(0)1122maxmmmmnnzzxxx（）(0)11max 1.0 1njjj mniijjij mjzzxxa xbimstxjn（，2,，）（，2,，）（）可以简化为：）可以简化为：

26、（）87二、单纯形法的基本原理二、单纯形法的基本原理 2、最优性检验和基可行解的改进 定理1.7（最优解判定定理）LP的典式（），如果有0(1,2,)jjmmn则对应于基B的基可行解(0)12(,0,0)Tmxb bb12(,0,0)Tmxb bb是线性规划的最优解，记为(0)zz相应的目标函数最优值特别 则 是唯一最优解(0)x0(1,2,)jjmmn88 定理1.9（无穷多最优解判定定理）0(1,2,)jjmmn如果检验数满足最优准则而且其中有一个0(1)kmkn 则该LP问题有无穷多最优解90 定理1.10（无界解判定定理）0(1)kmkn 如果某个非基变量的检验数且则该LP问题解无界0(1,2,)ikaim 91 定理1.8(0)12(,0,0)Tmxb bbLP的典式（），是对应于基B的一个基可行解，如果满足以下条件：（1）某个非基变量xk的检验数（2）至少有一个（3）这样一定能找到一个新的基可行解0(1)kmkn(1)(1)(2)(n)(1)(0)12n(,)Txxxxcxcx使得0(1)ikaim 0(1,2,)ibim(0)x即非退化确保可用最小比值准则换基92作业：P.37 第一章习题：8