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

《第一章线性规划及单纯形法.ppt》由会员分享，可在线阅读，更多相关《第一章线性规划及单纯形法.ppt（129页珍藏版）》请在三一文库上搜索。

1、2019/2/18,1,运筹学,经济学院,2019/2/18,2,课堂要求,1.要求同学们上课不迟到，不早退，不得旷课； 2.上课认真听讲，要求每位同学都做笔记； 3.上课不得讲话，看书，玩手机等与课堂无关的内容； 4.课后要求独自完成作业，不得抄袭或不做课后作业。,2019/2/18,3,参考资料,1.胡运权主编，运筹学教程（第三版），清华大学出版社； 2.周华任主编，运筹学解题指导，清华大学出版社； 3.运筹学习题集（修订版），清华大学出版社； 4.熊伟编著，运筹学，机械工业出版社； 5.运筹学数据、模型、决策，科学出版社。,2019/2/18,4,教学计划 以线性规划和运输问题为讲授重点

2、，其它部分作为选讲内容。 教学方法 以授课为主，案例分析与上机演示为辅。而讲课中主要培养用最优化方法解决实际问题的能力。,教学计划与方法,2019/2/18,5,前言运筹学简介,运筹学是管理科学的重要理论基础和应用手段，是管理专业的重要专业基础课程之一。 运筹学根据管理问题的环境条件和决策要求，建立相应的数学模型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的方案。,求解结果 .,求解结果 .,建立模型,求解模型,修改 模型,求解结果 .,修改 模型,2019/2/18,6,运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和

3、工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，搜索和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战研究”，英文是Operational Research，在美国称为Operations Research。,2019/2/18,7,战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样，Operations Research就转义成为“作业研究”。我国把Operations Research译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义。 运筹学

4、的内容十分广泛，包括线性规划、整数规划、动态规划、非线性规划、图论与网络优化、排队论、决策理论、库存理论等。在本课程中，结合管理学科的特点，主要介绍线性规划和运输问题。,2019/2/18,8,线性规划,数 学 规 划,非线性规划,整数规划,动态规划,学 科 内 容,多目标规划,双层规划,组 合 优 化,最优计数问题,网络优化,排序问题,统筹图,随 机 优 化,对策论,排队论,库存论,决策分析,可靠性分析,运筹学的主要内容,2019/2/18,9,目录： 第一章 线性规划及单纯形法 第二章 对偶问题 第三章 灵敏度分析 第四章 线性规划的建模与应用 第五章 运输问题,2019/2/18,10,

5、第一章 线性规划,线性规划问题 线性规划模型 线性规划的图解 可行域的性质 线性规划的基本概念 基础解、基础可行解 单纯形表,2019/2/18,11,线性规划问题,生产计划问题 配料问题 背包问题 运输问题 指派问题,2019/2/18,12,1. 生产计划问题（Production Planning）,某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,求使得总利润最大的生产计划。,2019/2/18,13,设四种产品的产量分别为x1，x2，x3，x4，总利润为z，线性规划模型为：

6、,max z=5.24x1+7.30x2+8.34x3+4.18x4 s.t. 1.5x1+1.0x2+2.4x3+1.0x42000 1.0x1+5.0x2+1.0x3+3.5x48000 1.5x1+3.0x2+3.5x3+1.0x45000 x1, x2, x3, x40,目标函数,约束条件,变量非负约束,这个问题的最优解为：x1=294.12件，x2=1500件，x3=0，x4=58.82件 最大利润为：z=12737.06元。,2019/2/18,14,2. 配料问题（Material Blending）,某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种

7、原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（）如下表：,要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。,2019/2/18,15,min z=115x1+97x2+82x3+76x4 s.t. 3.21x1+4.53x2+2.19x3+1.76x4320 Cr的含量下限约束 2.04x1+1.12x2+3.57x3+4.33x4210 Mn的含量下限约束 5.82x1+3.06x2+4.27x3+2.73x4430 Ni的含量下限约束 x1+x2+x3+x4=100 物料平衡约束 x

8、1, x2, x3, x40,设四种原料分别选取x1，x2，x3，x4公斤，总成本为z。,这个问题的最优解为：x1=26.58, x2=31.57, x3=41.84，x4=0（公斤）, 最低成本为z=9549.87元。 问题：如果某一种成分的含量既有下限，又有上限怎么办？,2019/2/18,16,3. 背包问题（Knapsack Problem）,一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：,求背包中装入每种物品各多少件，使背包中物品总价值最高。,2019/2/18,17,设三种物品的件数各为x1，x2，x3件，总价值为z。 max z=

9、17x1+72x2+35x3 s.t. 10x1+41x2+20x350 x1，x2，x30 x1，x2，x3为整数 这是一个整数规划问题（Integer Programming）。这个问题的最优解为： x1=1件，x2=0件，x3=2件，最高价值z=87元,2019/2/18,18,4. 运输问题（Transportation）,某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：,求总运费最低的运输方案。,2019/2/18,19,35吨,25吨,10吨,30吨,20吨,2019/2/18,20,

10、设从两个供应地到三个需求地的运量（吨）如下表：,2019/2/18,21,min z=2x11+3x12+5x13+4x21+7x22+8x23 s.t. x11+x12+x13 =35 供应地A1 x21+x22+x23 =25 供应地A2 x11 +x21 =10 需求地B1 x12 +x22 =30 需求地B2 x13 +x23 =20 需求地B3 x11, x12, x13, x21, x22, x230,2019/2/18,22,这个问题的最优解表示如下：,最小总运费为：z=330+55+410+815=275元,30吨,5吨,10吨,15吨,2019/2/18,23,5. 指派问题

11、（Assignment Problem）,有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个人完成j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。 设：,2019/2/18,24,张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。,2019/2/18,25,设：,max z=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+ 83x3

12、1+90x32+74x33+65x34+93x41+61x42+83x43+75x44 s.t. x11+x12+x13+x14=1 (1) x21+x22+x23+x24=1 (2) x31+x32+x33+x34=1 (3) x41+x42+x43+x44=1 (4) x11+x21+x31+x41=1 (5) x12+x22+x32+x42=1 (6) x13+x23+x33+x43=1 (7) x14+x24+x34+x44=1 (8) xij=0,1,2019/2/18,26,最优解为：x14=1，x23=1，x32=1，x41=1，max z=336 即张老师教化学，王老师教语文，

13、李老师教数学，赵老师教语文。,四门课的总分可以达到336分。,2019/2/18,27,线性规划模型,min(max) z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn (, )b1 a21x1+a22x2+a2nxn (, )b2 am1x1+am2x2+amnxn (, )bm x1, x2, , xn 0 (, Free),线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：,2019/2/18,28,线性规划的标准形式,目标函数为极大化，约束条件全部为等号约束，右端常数项均为非负，所有变量全部是非

14、负的，这样的线性规划模型称为标准形式 maxz=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0,2019/2/18,29,线性规划模型用矩阵和向量表示,max z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0,2019/2/18,30,线性规划模型用矩阵和向量表示（续）,因此，线性规划模型可以写成如下

15、矩阵和向量的形式,MaxZ =CTX s.t. AX=b X0,2019/2/18,31,线性规划模型总结,线性规划模型的结构 目标函数 ：max，min 约束条件：,=, 变量符号：0, 0, Free 线性规划的标准形式 目标函数：max 约束条件 ：= 右端常数项： 0 变量符号 ：0,MaxZ =CTX s.t. AX=b X0,2019/2/18,32,线性规划解的概念,设线性规划,2019/2/18,33,举例： 1.maxZ=8x1+10 x2 2x1+x2 11 x1+ 2x2 10 x1, x20 确定下列向量中哪些是解？可行解？ 求出可行域。,2019/2/18,34,图解

16、法： 对于模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法求解。 一个线性规划问题有解，是指能找出一组xj(j=1,2,n)，满足约束条件，称这组xj为问题的可行解。 通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域，可行域中使目标函数为最优的可行解为最优解。 图解法的目的是判别线性规划问题的求解结局和存在最优解的条件下求出最优解。,2019/2/18,35,图解法的步骤,1.建立具有合适刻度单位的坐标系统； 2.对每一约束条件建立直线，从而确定可行域； 3.确定目标函数等值线的移动方向； 4.求出最优解：最优解为等值线在移动过程中与可行域的最后交点。,2019/2/

17、18,36,线性规划的图解,max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域,目标函数等值线,最优解,z=6,z=3,z=9,z=12,问题：1、线性规划的最优解是否可能位于可行域的内部？ 2、线性规划的最优解是否可能位于可行域的边界上？,2019/2/18,37,举例： 1.maxZ=2x1+ x2 5x215 6x1+2x2 24 x1+ x2 5 x1, x20 唯一最优解 2. maxZ=x1+ x2 -2x1+x2 4 x1- x2 2 x1, x20 无界解,3.maxZ=3x1+9x2 x1+3x2 22 -x1+x2 4 x1,

18、x20 无穷多最优解,4.maxZ=x1+ x2 x1+x2 1 2x1+2x24 x1, x20 无解,2019/2/18,38,线性规划可行域和最优解的几种情况,1、可行域封闭 唯一最优解,2、可行域封闭 多个最优解,3、可行域开放 唯一最优解,4、可行域开放 多个最优解,5、可行域开放 目标函数无界,6、无可行解,2019/2/18,39,标 准 形 式,2019/2/18,40,线性规划问题的标准化,极小化目标函数转化为极大化 小于等于约束条件转化为等号约束 大于等于约束条件转化为等号约束 右端常数项小于等于0的标准化 变量小于等于0的标准化 变量没有符号限制（Free）的标准化,20

19、19/2/18,41,min z=2x1-3x2+x3 令 z=-z，z=-2x1+3x2-x3 新的目标函数 max z=-2x1+3x2-x3 取得极大化的最优解时，这个最优解同时使原目标函数值取得最小化的最优解。但两个问题最优解的目标函数值相差一个负号。,极小化目标函数问题转化为极大化目标函数,2019/2/18,42,例如，对于以下两个线性规划问题,min z=2x1+3x2 s.t. x1+x23 x21 (A) x1, x20,max z=-2x1-3x2 s.t. x1+x23 x21 (B) x1, x20,它们的最优解都是x1=2, x2=1，但(A)的最小化的目标函数值为m

20、in z=7，(B)的最大化的目标函数值为max z=-7,2019/2/18,43,2x1+3x2-4x35 引进松弛变量(Slack variable) x4=5-(2x1+3x2-4x3)，把松弛变量x4加在约束条件左边，就可以将小于等于约束变为等式。 2x1+3x2-4x3+x4=5 由此可以知道，松弛变量x40。如果有一个以上小于等于约束，要对于每一个约束引进不同的松弛变量。例如： 2x1+3x2-4x35 3x1-2x2+5x38 在两个约束中分别引进松弛变量x4，x50 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 +x5=8,小于等于约束条件转化为等号约束,201

21、9/2/18,44,将不等式约束变为等式约束。例如： 2x1+3x2-4x35 3x1-2x2+5x38 在两个约束的左边分别减去剩余变量x4，x50 2x1+3x2-4x3-x4 =5 3x1-2x2+5x3 -x5=8,大于等于约束条件转化为等号约束,2019/2/18,45,右端常数项小于等于0的标准化,当右端常数项为小于等于0时，如： 2x1-3x2+4x3-4 只需不等式两边同乘以-1，不等式改好就可以了 -2x1+3x2-4x34,2019/2/18,46,min z=x1+2x2-3x3 s.t. 2x1+3x2-4x35 3x1-2x2+5x38 x10, x20, x30 m

22、ax z=-x1-2x2+3x3 s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10, x20, x3, x4, x50 令 x2=-x2，x20, 代入模型 max z=-x1+2x2+3x3 s.t. 2x1-3x2-4x3+x4 =5 3x1+2x2+5x3 -x5=8 x10, x20, x3, x4, x50,变量小于等于0的的标准化,2019/2/18,47,没有符号限制的变量，用两个非负变量之差表示。例如： min z=x1+2x2-3x3 s.t. 2x1+3x2-4x35 3x1-2x2+5x38 x10, x2:free, x30 先将

23、目标函数转化为极大化，并在约束中引进松弛变量，把不等式约束变为等式。 Max z=-x1-2x2+3x3 s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10, x2:free, x3, x4, x50,变量没有符号限制(Free)的标准化,2019/2/18,48,Max z=-x1-2x2+3x3 s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3-x5=8 x10, x2:free, x3, x4, x50 然后，令x2=x2-x2”，其中x2,x2”0。代入模型，消去x2 Max z=-x1-2(x2-x”2)+3x3 s.t. 2

24、x1+3(x2-x”2)-4x3+x4 =5 3x1-2(x2-x”2)+5x3 -x5=8 x1, x2, x”2, x3, x4,x50 整理，得到标准形式： Max z=-x1-2x2+x”2+3x3 s.t. 2x1+3x2-3x”2-4x3+x4 =5 3x1-2x2+2x”2+5x3 -x5=8 x1, x2, x”2, x3, x4,x50,2019/2/18,49,练习： min z=2x1-x2+4x3 s.t. x1+x2-x33 3x1-x2+2x36 x1-3x2-4x3-4 x10, x30,2019/2/18,50,标准化的线性规划问题，有n个变量，m个约束。 ma

25、xz=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0 令其中n-m个变量等于零，如果剩下的m个变量的系数矩阵的行列式不等于0，这个mm的矩阵称为线性规划的一个基。等于0的n-m个变量称为非基变量，m个变量称为基变量。,线性规划的基本概念基、基解、基可行解、极点,2019/2/18,51,求解mm的线性方程组，得到基变量的一组解，连同等于0的非基变量这n个变量的值称为线性规划的一个基解。 如果一个基解中的所有变量都是非负的，这个基解称为基可行解。 线

26、性规划的基可行解就是可行域的极点。,2019/2/18,52,解的可行性和松弛变量符号的关系,max z=2x1+3x2 s.t. x1+x24 (1) -x1+x21 (2) x1, x20,max z=2x1+3x2 s.t. x1+x2+x3 =4 -x1+x2 -x4=1 x1, x2,x3,x40,引进松 弛变量,A(1,2.5)满足所有约束条件，x3=0.5, x4=0.5 B(2,1)满足(1)，不满足(2)，x3=1, x4=-2 C(1.5,3)不满足(1),满足(2)，x3=-0.5, x4=0.5 D(3,2)不满足(1)和(2)，x3=-1, x4=-2 结论：如果一个

27、解满足一个约束条件，相应的松弛变量大于等于0。如果一个解不满足一个约束条件，相应的松弛变量小于0。,2019/2/18,53,1.找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解。 maxZ=2x1+3x2 x1 +x35 x1+2x2 +x4 10 x2 + x5 4 xi 0,2019/2/18,54,解：,最优解为x1 2，x24， x3 3，Z19,2019/2/18,55,max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0,max z=x1+2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40,x1=0

28、, x2=0 x3=3, x4=1 基可行解,x1=0, x4=0 x2=1, x3=2 基可行解,x2=0, x3=0 x1=3, x4=1 基可行解,x3=0, x4=0 x1=2, x2=1 基可行解,x1=0, x3=0 x2=3, x4=-2 是基解，但不是可行解,O,A,B,x3=0,x4=0,x2=0,x1=0,C,D,可行域,2019/2/18,56,凸集和极点,1.凸集 如果集合C中任意两点x1，x2，其连线上的所有点也都是集合C中的点，则称C为凸集，其中x1，x2的连线可以表示为： x1 （1）x2(0 1) 数学解析式为： x1 C， x2 C， 有x1 （1）x2C (

29、0 1) ，则C为凸集。,2019/2/18,57,2.极点 如果集合C中任意两点x1，x2，使x为这两点连线上的一个点，对任何x1 C， x2 C，不存在 x=x1 （1）x2(0 1)，则称x为凸集的顶点。,2019/2/18,58,几个基本定理,定理1：若线性规划问题存在可行解，则问题的可行域是凸集 引理：线性规划问题的可行解X(x1,x2,xn)为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的（所组成的矩阵是非奇异的）。 定理2：线性规划问题的基可行解X对应线性规划问题可行域的顶点。 定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解。,2019/2/18,59

30、,线性规划的代数解法,maxZ=6x1+5x2 x1+3x290 2x1+x275 2x1+2x2 80 x1, x20,maxZ=6x1+5x2 x1+3x2+x390 2x1+ x2 +x4 75 2x1+2x2 +x580 xi0,找一个基可行解，X（0，0，90，75，80），Z=0 1）Z6x1+5x2，x1的系数C16大于C2=5；选择x1为新的基变量。 X3=90-(x1+3x2) 当x3=0，X2=0时，x1=90 选择x4为 X4=75-(2x1+x2) 当x4=0，X2=0时，x1=37.5 换出变量， X5=80-(2x1+2x2) 当x5=0，X2=0时，x1=40 即

31、x4 0,最小,2019/2/18,60,3）Z225+2x2-3x4，x2的系数C22大于0；选择x2为新的基变量。 X3=52.5-(2.5x2-0.5x4) 当x3=0，x4=0时，x2=21 X1=75/2-(0.5x2+0.5x4) 当x1=0，x4=0时，x2=75 X5=5-(x2-x4) 当x5=0，x4=0时，x2=5 所以选择x5为换出变量, x2为换入变量,最小,则X（37.5，0，52.5，0，5）T，Z2252X2-3X4,2）仍然用非基变量表示基变量 X3=52.5-(2.5x2-0.5x4) X1=75/2-(0.5x2+0.5x4) X5=5-(x2-x4) Z

32、225+2x2-3x4,2019/2/18,61,4)用非基变量表示基变量 X3=40-(1.5x4-2.5x5) X1=35-(x4-0.5x5) X2=5-(x5-x4) Z235-x4-2x5,则X（35，5，40，0，0）T，Z235-x4-2x5 为最优解,2019/2/18,62,可行域极点的数量,如果线性规划有50个变量，20个约束条件，全部是等号约束。按照以上的算法，每计算一个基础解，要从50个变量中选择30个非基变量等于0，剩下20个变量，如果相应的2020行列式不等于0，则通过计算一个20 20的线性方程组得到基变量。要穷尽所有的基础解，最多可能要计算的线性方程组的个数为,

33、假设每计算一个2020线性组需要1秒钟，计算以上所有方程组需要的时间为,由于极点的个数随着约束条件的增加而很快增加，用搜索所有极点来求出线性规划最优解，实际上并不是一个可行的方法。,2019/2/18,63,单纯形法原理示意图,极点4，最优解,初始极点1,极点2,极点3,其实，不必搜索可行域的每一个极点，只要从一个极点出发，沿着使目标函数改善的方向，到达下一个相邻的极点。如果相邻的所有极点都不能改善目标函数，这个极点就是最优极点。用这样的搜索策略，可以大大减少搜索极点的个数。 按照这样的搜索策略建立的算法，叫做单纯形法。 单纯形法可以有效地减少搜索极点的个数。,目标函数改善,目标函数改善,目标

34、函数改善,2019/2/18,64,线性规划基本概念练习（1）,0,3,6,x1,x2,O,A,B,C,E,F,G,H,I,4,6,-2,min z=-x1+2x2 s.t. 3x1+2x212 (1) x1+2x2 6 (2) -2x1+ x2 4 (3) x1, x2 0,1、约束条件（1）对应的直线是（ ），对应的半平面是 约束条件（2）对应的直线是（ ），对应的半平面是 约束条件（3）对应的直线是（ ），对应的半平面是,2、这个线性规划的可行域是（ ）。 3、对于z=2和4,分别画出目标函数等值线。 4、这个线性规划的最优解位于（ ）。,ACEF,BCDH,EGHI,CDGE,z=2,

35、z=4,C,D,4,2019/2/18,65,0,3,6,x1,x2,O,A,B,C,E,F,G,H,I,4,6,-2,D,线性规划基本概念练习（2）,5、x1等于0的直线是( )， x2等于0的直线是( )， x3等于0的直线是( )， x4等于0的直线是( )， x5等于0的直线是( )。 6、A点对应的基变量是( )，非基变量是（ ）； D点对应的基变量是( )，非基变量是（ ）。 7、A点不是可行解,是由于( )0 F点不是可行解,是由于( )0 I 点不是可行解,是由于( )0,4,x1=0,x2=0,x3=0,x4=0,x5=0,ODGF,IOAB,ACEF,BCDH,EGHI,8

36、、x1,x2,x50, x3,x40的区域是( ) x1,x2,x3,x50, x40的区域是( ) x2,x3,x4,x50, x10的区域是( ) x1,x2,x3,x40, x50的区域是( ),x1,x4,x5,x3,x2,x2,x3,x5,x1,x4,x4,x5,x1,x4,ABC,OACD,DGH,EFG,2019/2/18,66,单纯形法计算步骤,1.将非标准型线性规划化为标准型 2.确定初始基可行解：一般设松弛变量为初时基可行解 3.判断 若所有的某一非基变量的检验数j0，则此解为线性规划问题的最优解，若存在某一非基变量的检验数j0，则问题还没有达到最优解，需要进行改进。 4.

37、改进迭代 选择换入变量max cj- zj/ cj- zj0假设选取xk为换入变量 选择换出变量minbi/aik，aik0则假设选取cl为换出变量 迭代，使得alk1，其余aik为0,2019/2/18,67,2019/2/18,68,单纯形表求解线性规划问题,maxZ=6x1+5x2 x1+3x290 2x1+x275 2x1+2x2 80 x1, x20,maxZ=6x1+5x2 x1+3x2+x390 2x1+ x2 +x4 75 2x1+2x2 +x580 xi0,2019/2/18,69,2019/2/18,70,2019/2/18,71,所以把x4换出为非基变量，x1为换入变量即

38、新的基变量。,2019/2/18,72,2019/2/18,73,2019/2/18,74,2019/2/18,75,2019/2/18,76,所以把x5换出为非基变量，x2为换入变量即新的基变量。,2019/2/18,77,2019/2/18,78,2019/2/18,79,2019/2/18,80,此时所有的检验数都小于等于0，所以该解为最优解。,最优解为X（35，5，40，0，0）T，Z*235,2019/2/18,81,Step 0 获得一个初始的单纯形表，确定基变量和非基变量 Step 1 检查基变量在目标函数中的系数是否等于0，在约束条件中的系数是否是一个单位矩阵。 Step 2

39、如果表中非基变量在目标函数中的系数全为负数，则已得到最优解。停止。否则选择系数为正数且绝对值最大的变量进基，转step 3。 Step 3 如果进基变量在约束条件中的系数全为负数或0，则可行域开放，目标函数无界。停止。否则选取右边常数和正的系数的最小比值，对应的基变量离基，转step 4。 Step 4 确定进基变量的列和离基变量的行交叉的元素为“主元”，对单纯形表进行行变换，使主元变为1，主元所在列的其他元素变为0。将离基的基变量的位置用进基的非基变量代替。转Step 2。,单纯形表的算法描述,2019/2/18,82,1.maxZ=3x1+9x2 x1+3x221 -x1+x24 x1,

40、x20,maxZ=3x1+9x2 x1+3x2+x321 -x1+ x2 +x4 4 xi0,举例,2019/2/18,83,所以把x4换出为非基变量，x2为换入变量即新的基变量。,2019/2/18,84,2019/2/18,85,2019/2/18,86,2019/2/18,87,所以把x3换出为非基变量，x1为换入变量即新的基变量。,2019/2/18,88,2019/2/18,89,2019/2/18,90,此时所有的检验数都小于等于0，所以该解为最优解。,最优解为X（9/4，25/4，0，0）T，Z*63,由于非基变量x4的检验数0，所以我们可以把它作为换入 基变量来考虑。,2019

41、/2/18,91,2019/2/18,92,2019/2/18,93,2019/2/18,94,此时所有的检验数都小于等于0，所以该解为最优解。Z*=63,2019/2/18,95,1.maxZ=x1+x2 -2x1+x24 x1-x22 x1, x20,maxZ=x1+x2 -2x1+x2+x34 x1- x2 +x4 2 xi0,举例,2019/2/18,96,所以把x3换出为非基变量，x2为换入变量即新的基变量。,2019/2/18,97,2019/2/18,98,2019/2/18,99,2019/2/18,100,可以看出，的检验数为3，大于0，但是的系数列向量中的所 有原数（-2,

42、-1）T，都小于0，所以该题为无界解。,2019/2/18,101,单纯形法的进一步讨论,一、人工变量法（大M法） 约束条件： “” 加一个剩余变量后，在加一个人工变量 “” 加一个人工变量 目标函数： 人工变量的系数为“M”，即罚因子 若线性规划问题有最优解则人工变量必为0。,2019/2/18,102,MaxZ=3x1- x2-x3 x1-2x2+ x311 -4x1+ x2+2x33 -2x1 +x3=1 xi 0,MaxZ=3x1- x2-x3+0x4+0x5-Mx6-Mx7 x1-2x2+ x3+ x4=11 -4x1+ x2+2x3 -x5+x6=3 -2x1 +x3 +x7=1

43、xi 0,增加人工变量后，线性规划问题中就存在一个B为单位矩阵， 后面可以根据我们前面所讲的单纯形法来进行求解。,2019/2/18,103,2019/2/18,104,2019/2/18,105,2019/2/18,106,2019/2/18,107,2019/2/18,108,2019/2/18,109,2019/2/18,110,2019/2/18,111,2019/2/18,112,2019/2/18,113,2019/2/18,114,2019/2/18,115,2019/2/18,116,2019/2/18,117,2019/2/18,118,此时所有的检验数都小于等于0，所以该解

44、为最优解。,最优解为X（4，1，9，0，0，0，0）T，Z*2,2019/2/18,119,2.两阶段法 第一阶段在不考虑原问题是否存在基可行解，给原问题加入人工变量，并构建一个仅含人工变量的目标函数（求极小化），人工变量的系数一般为1，约束条件和原问题的一样。 当第一阶段中目标函数的最优值0，既人工变量0，则转入第二阶段；若第一阶段中目标函数的最优值不等于0，既人工变量不等于0，则判断原问题为无解。 第二阶段：将第一阶段计算所得的单纯形表划去人工变量所在的列，并加目标函数换为原问题的目标函数作为第二阶段的初始单纯形表，进行进一步的求解。,2019/2/18,120,2019/2/18,121

45、,2019/2/18,122,2019/2/18,123,2019/2/18,124,2019/2/18,125,可以看到人工变量x6，x7均为0，所以构造的目标函数w=0，因此 可以判断该线性规划问题有可行解，可以进行第二阶段的计算。,2019/2/18,126,maxz=3x1 -x2-x3 s.t. x1-2x2 +x3+x4=11 -4x1+ x2+2x3-x5=3 -2x1 +x3=1 xj0,2019/2/18,127,此时所有的检验数都小于等于0，所以该解为最优解。,最优解为X（4，1，9，0，0，0，0）T，Z*2,可以看出该结果和大M法所得的结果是一样的。,2019/2/18

46、,128,建模题,1.一贸易公司专门经营某种杂粮的批发业务。公司现有库容5000担的仓库。一月一日，公司拥有1000担杂粮，并有资金20000元。估计第一季度杂粮价格如表所示。如买进的杂粮当月到货，但需要下月才能卖出，且规定货到付款。公司希望本季末库存为2000担，问应采取什么样的买进和卖出策略使三个月的总获利为最大。,2019/2/18,129,2.某厂生产I,II两种食品，现有50名熟练工人，已知一名熟练工人每小时可生产10千克食品I或6千克食品II。根据合同预定，该两种食品每周的需求量将急剧上升，见表所示。为此厂方决定到第8周末培训出50名新的工人两班生产。已知一名工人每周的工作时间为40小时，一名数量工人每两周时间可培训出不多于3名新工人（培训期间熟练工人和培训人员均不参加生产）。熟练工人每周工资为360元，新工人培训期间每周工资为120元，培训结束后为240元/周，生产效率同熟练工人。在培训过渡期间，很多熟练工人愿意加班工作，工厂决定安排部分工人每周工作60小时，工资为540元/周。如果预定食品不能按期交货，每推迟交货一周的赔偿费为食品I为0.5元，食品II为0.6元，在上述各种条件下，工厂应如何作出全