《线性规划及单纯形法(最新新).ppt》由会员分享，可在线阅读，更多相关《线性规划及单纯形法(最新新).ppt（190页珍藏版）》请在三一办公上搜索。
1、1,运筹学,经济学院,2,课堂要求,1.要求同学们上课不迟到，不早退，不得旷课；2.上课认真听讲，要求每位同学都做笔记；3.上课不得讲话，看书，玩手机等与课堂无关的内容；4.课后要求独自完成作业，不得抄袭或不做课后作业。,3,参考资料,1.胡运权主编，运筹学教程（第三版），清华大学出版社；2.周华任主编，运筹学解题指导，清华大学出版社；3.运筹学习题集（修订版），清华大学出版社；4.熊伟编著，运筹学，机械工业出版社；5.运筹学数据、模型、决策，科学出版社。,4,教学计划 以线性规划和运输问题为讲授重点，其它部分作为选讲内容。教学方法 以授课为主，案例分析与上机演示为辅。而讲课中主要培养用最优化
2、方法解决实际问题的能力。,教学计划与方法,5,前言运筹学简介,运筹学是管理科学的重要理论基础和应用手段，是管理专业的重要专业基础课程之一。运筹学根据管理问题的环境条件和决策要求，建立相应的数学模型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的方案。,求解结果.,求解结果.,建立模型,求解模型,修改模型,求解结果.,修改模型,6,运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，搜索和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的
3、效果。当时英国把这些研究成为“作战研究”，英文是Operational Research，在美国称为Operations Research。,7,战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样，Operations Research就转义成为“作业研究”。我国把Operations Research译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义。运筹学的内容十分广泛，包括线性规划、整数规划、动态规划、非线性规划、图论与网络优化、排队论、决策理论、库存理论等。在本课程中，结合管理学科的特点，主要介绍线性规划和运输问题。,
4、8,线性规划,数学规划,非线性规划,整数规划,动态规划,学科内容,多目标规划,双层规划,组合优化,最优计数问题,网络优化,排序问题,统筹图,随机优化,对策论,排队论,库存论,决策分析,可靠性分析,运筹学的主要内容,9,目录：第一章线性规划及单纯形法第二章 对偶问题第三章灵敏度分析第四章线性规划的建模与应用第五章 运输问题,10,第一章 线性规划,线性规划问题线性规划模型线性规划的图解可行域的性质线性规划的基本概念基础解、基础可行解单纯形表,11,第1节线性规划问题及其数学模型,生产计划问题配料问题背包问题运输问题指派问题,1.1问题的提出,12,1.生产计划问题（Production Plan
5、ning）,某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,求使得总利润最大的生产计划。,13,设四种产品的产量分别为x1，x2，x3，x4，总利润为z，线性规划模型为：,max z=5.24x1+7.30 x2+8.34x3+4.18x4s.t.1.5x1+1.0 x2+2.4x3+1.0 x42000 1.0 x1+5.0 x2+1.0 x3+3.5x48000 1.5x1+3.0 x2+3.5x3+1.0 x45000 x1,x2,x3,x40,目标函数,约束条件,变量非负约
6、束,这个问题的最优解为：x1=294.12件，x2=1500件，x3=0，x4=58.82件最大利润为：z=12737.06元。,14,2.配料问题（Material Blending）,某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（）如下表：,要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。,15,min z=115x1+97x2+82x3+76x4s.t.3.21x1+4.53x2+2.19x3+1.76x
7、4320 Cr的含量下限约束 2.04x1+1.12x2+3.57x3+4.33x4210 Mn的含量下限约束 5.82x1+3.06x2+4.27x3+2.73x4430 Ni的含量下限约束 x1+x2+x3+x4=100 物料平衡约束 x1,x2,x3,x40,设四种原料分别选取x1，x2，x3，x4公斤，总成本为z。,这个问题的最优解为：x1=26.58,x2=31.57,x3=41.84，x4=0（公斤）,最低成本为z=9549.87元。问题：如果某一种成分的含量既有下限，又有上限怎么办？,16,3.背包问题（Knapsack Problem）,一只背包最大装载重量为50公斤。现有三种
8、物品，每种物品数量无限。每种物品每件的重量、价格如下表：,求背包中装入每种物品各多少件，使背包中物品总价值最高。,17,设三种物品的件数各为x1，x2，x3件，总价值为z。max z=17x1+72x2+35x3s.t.10 x1+41x2+20 x350 x1，x2，x30 x1，x2，x3为整数这是一个整数规划问题（Integer Programming）。这个问题的最优解为：x1=1件，x2=0件，x3=2件，最高价值z=87元,18,4.运输问题（Transportation）,某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地
9、到每个需求地每吨物资的运输价格如下表：,求总运费最低的运输方案。,19,35吨,25吨,10吨,30吨,20吨,20,设从两个供应地到三个需求地的运量（吨）如下表：,21,min z=2x11+3x12+5x13+4x21+7x22+8x23s.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,22,这个问题的最优解表示如下：,最小总运费为：z=330+55+410+815=275元,30吨,5吨,10吨,
10、15吨,23,5.指派问题（Assignment Problem）,有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个人完成j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。设：,24,张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。,25,设：,max z=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90 x32+
11、74x33+65x34+93x41+61x42+83x43+75x44s.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,26,最优解为：x14=1，x23=1，x32=1，x41=1，max z=336即张老师教化学，王老师教语文，李老师教数学，赵老师教语文。,四门课的总分可以达到336分。,27,线性规
12、划模型,min(max)z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn(,)b1 a21x1+a22x2+a2nxn(,)b2 am1x1+am2x2+amnxn(,)bm x1,x2,xn 0(,Free),线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：,28,1.2线性规划的标准形式,目标函数为极大化，约束条件全部为等号约束，右端常数项均为非负，所有变量全部是非负的，这样的线性规划模型称为标准形式maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a
13、22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0,29,线性规划模型用矩阵和向量表示,max z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0,30,线性规划模型用矩阵和向量表示（续）,因此，线性规划模型可以写成如下矩阵和向量的形式,MaxZ=CTXs.t.AX=b X0,31,线性规划模型总结,线性规划模型的结构目标函数：max，min约束条件：,=,变量符号：0,0,Free线性规划的标准形式目标函数：max约束
14、条件：=右端常数项：0变量符号：0,MaxZ=CTXs.t.AX=b X0,32,线性规划问题的标准化,极小化目标函数转化为极大化小于等于约束条件转化为等号约束大于等于约束条件转化为等号约束右端常数项小于等于0的标准化变量小于等于0的标准化变量没有符号限制（Free）的标准化,33,非标准形式如何化为标准,1)Min型化为Max型,加负号,因为，求一个函数的极小点，等价于求该函数的负函数的极大点。,注意：Min型化为Max型求解后，最优解不变，但最优值差负号。,34,min z=2x1-3x2+x3令 z=-z，z=-2x1+3x2-x3新的目标函数 max z=-2x1+3x2-x3取得极大
15、化的最优解时，这个最优解同时使原目标函数值取得最小化的最优解。但两个问题最优解的目标函数值相差一个负号。,极小化目标函数问题转化为极大化目标函数,35,例如，对于以下两个线性规划问题,min z=2x1+3x2s.t.x1+x23 x21(A)x1,x20,max z=-2x1-3x2s.t.x1+x23 x21(B)x1,x20,它们的最优解都是x1=2,x2=1，但(A)的最小化的目标函数值为min z=7，(B)的最大化的目标函数值为max z=-7,36,2)不等式约束化为等式约束,分析：以下面约束为例,之所以“不等”是因为左右两边有一个差额，称为“松弛量”，若在左边加上这个松弛量，则
16、化为等式。而这个松弛量也是变量，记为，则有,称为松弛变量。问题：它的实际意义是什么？,资源的“剩余”。,37,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,小于等于约束条件转化为等号约束
17、,38,将不等式约束变为等式约束。例如：2x1+3x2-4x35 3x1-2x2+5x38在两个约束的左边分别减去剩余变量x4，x50 2x1+3x2-4x3-x4=5 3x1-2x2+5x3-x5=8,大于等于约束条件转化为等号约束,39,练习：请将下列约束化为标准型,解：增加松弛变量,则约束化为,易见，增加的松弛变量的系数恰构成一个单位阵I。,40,一般地，记松弛变量的向量为 Xs，则,问题：松弛变量在目标中的系数为何？,0。,3)当模型中有某变量 xk 没有非负要求，称为自由变量,则可令,化为标准型。,41,没有符号限制的变量，用两个非负变量之差表示。例如：min z=x1+2x2-3x
18、3s.t.2x1+3x2-4x35 3x1-2x2+5x38 x10,x2:free,x30先将目标函数转化为极大化，并在约束中引进松弛变量，把不等式约束变为等式。Max z=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4=5 3x1-2x2+5x3-x5=8 x10,x2:free,x3,x4,x50,变量没有符号限制(Free)的标准化,42,Max z=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4=5 3x1-2x2+5x3-x5=8 x10,x2:free,x3,x4,x50然后，令x2=x2-x2”，其中x2,x2”0。代入模型，消去x2Max z=-x1-
19、2(x2-x”2)+3x3s.t.2x1+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+3x3s.t.2x1+3x2-3x”2-4x3+x4=5 3x1-2x2+2x”2+5x3-x5=8 x1,x2,x”2,x3,x4,x50,43,4）右端常数项小于等于0的标准化,当右端常数项为小于等于0时，如：2x1-3x2+4x3-4只需不等式两边同乘以-1，不等式改好就可以了-2x1+3x2-4x34,44,min z=x1+2x2-3x3s.t.2x1+3x2-4x3
20、5 3x1-2x2+5x38 x10,x20,x30max z=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4=5 3x1-2x2+5x3-x5=8 x10,x20,x3,x4,x50令 x2=-x2，x20,代入模型max z=-x1+2x2+3x3s.t.2x1-3x2-4x3+x4=5 3x1+2x2+5x3-x5=8 x10,x20,x3,x4,x50,5）变量小于等于0的的标准化,45,练习：min z=2x1-x2+4x3s.t.x1+x2-x33 3x1-x2+2x36 x1-3x2-4x3-4 x10,x30,46,1.3线性规划问题解的概念,设线性规划,47,举例
21、：1.maxZ=8x1+10 x2 2x1+x2 11 x1+2x2 10 x1,x20确定下列向量中哪些是解？可行解？求出可行域。,48,基本概念,（1）可行解与最优解,直观上，可行解是可行域中的点，是一个可行的方案；最优解是可行域的角点，是一个最优的方案。,49,1.4 图解法：对于模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法求解。一个线性规划问题有解，是指能找出一组xj(j=1,2,n)，满足约束条件，称这组xj为问题的可行解。通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域，可行域中使目标函数为最优的可行解为最优解。图解法的目的是判别线性规划问题的求解结局
22、和存在最优解的条件下求出最优解。,50,图解法的步骤,1.建立具有合适刻度单位的坐标系统；2.对每一约束条件建立直线，从而确定可行域；3.确定目标函数等值线的移动方向；4.求出最优解：最优解为等值线在移动过程中与可行域的最后交点。,51,线性规划的图解,max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20,可行域,目标函数等值线,最优解,z=6,z=3,z=9,z=12,问题：1、线性规划的最优解是否可能位于可行域的内部？2、线性规划的最优解是否可能位于可行域的边界上？,52,举例：1.maxZ=2x1+x2 5x215 6x1+2x2 24 x1+x2 5 x1,x2
23、0唯一最优解2.maxZ=x1+x2-2x1+x2 4 x1-x2 2 x1,x20 无界解,3.maxZ=3x1+9x2 x1+3x2 22-x1+x2 4 x1,x20无穷多最优解,4.maxZ=x1+x2 x1+x2 1 2x1+2x24 x1,x20无解,53,线性规划可行域和最优解的几种情况,1、可行域封闭 唯一最优解,2、可行域封闭 多个最优解,3、可行域开放 唯一最优解,4、可行域开放 多个最优解,5、可行域开放 目标函数无界,6、无可行解,54,标准化的线性规划问题，有n个变量，m个约束。maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a
24、21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0 如果m个变量的系数矩阵的行列式不等于0，这个mm的矩阵称为线性规划的一个基。其余的n-m个变量称为非基变量，m个变量称为基变量。,1.5线性规划的基本概念基、基解、基可行解、极点,55,求解mm的线性方程组，得到基变量的一组解，连同等于0的非基变量这n个变量的值称为线性规划的一个基解。如果一个基解中的所有变量都是非负的，这个基解称为基可行解。线性规划的基可行解就是可行域的极点。,56,基矩阵与基变量,基矩阵(简称基)：系数阵A中的m阶可逆子阵，记 为B；其余部分称为非基矩阵，记为N。,基向量
25、：基B中的列；其余称非基向量。,基变量：与基向量Pj对应的决策变量xj，记其组成的 向量为XB；与非基向量对应的变量称非基变 量，记其组成的向量为XN。,57,6个。,一般地，mn 阶矩阵A中基的个数最多有多少个？,问题：本例的A中一共有几个基？,58,基本解与基本可行解,可见：一个基本解是由一个基决定的。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。,称非负的基本解为基本可行解（简称基可行解）。,59,例4：在上例中,求相应于基B1和B2的基本解，它们是否基本可行解？,60,上二组概念间的联系：,几种解之间的关系：,问题：基本可行解是可行域中的哪些点？,61,1.找出下述线性
26、规划问题的全部基解，指出其中的基可行解，并确定最优解。maxZ=2x1+3x2 x1+x35 x1+2x2+x4 10 x2+x5 4 xi 0,62,解：,最优解为x1 2，x24，x3 3，Z19,63,1.6 解的可行性和松弛变量符号的关系,max z=2x1+3x2s.t.x1+x24(1)-x1+x21(2)x1,x20,max z=2x1+3x2s.t.x1+x2+x3=4-x1+x2-x4=1 x1,x2,x3,x40,引进松弛变量,A(1,2.5)满足所有约束条件，x3=0.5,x4=0.5B(2,1)满足(1)，不满足(2)，x3=1,x4=-2C(1.5,3)不满足(1),
27、满足(2)，x3=-0.5,x4=0.5D(3,2)不满足(1)和(2)，x3=-1,x4=-2结论：如果一个解满足一个约束条件，相应的松弛变量大于等于0。如果一个解不满足一个约束条件，相应的松弛变量小于0。,64,max z=x1+2x2s.t.x1+x23 x2 1 x1,x2 0,max z=x1+2x2s.t.x1+x2+x3=3 x2+x4=1 x1,x2,x3,x40,x1=0,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
28、=3,x4=-2是基解，但不是可行解,O,A,B,x3=0,x4=0,x2=0,x1=0,C,D,可行域,65,第2节 线性规划问题的几何意义,1.凸集 如果集合C中任意两点x1，x2，其连线上的所有点也都是集合C中的点，则称C为凸集，其中x1，x2的连线可以表示为：x1（1）x2(0 1)数学解析式为：x1 C，x2 C，有x1（1）x2C(0 1)，则C为凸集。,2.1基本概念,66,2.极点 如果集合C中任意两点x1，x2，使x为这两点连线上的一个点，对任何x1 C，x2 C，不存在 x=x1（1）x2(0 1)，则称x为凸集的顶点。,3.凸组合P16,67,2.2 几个基本定理,定理1
29、：若线性规划问题存在可行解，则问题的可行域是凸集引理：线性规划问题的可行解X(x1,x2,xn)为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的（所组成的矩阵是非奇异的）。定理2：线性规划问题的基可行解X对应线性规划问题可行域的顶点。定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解。,68,第3节 单纯形法,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=01
30、）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 即x4 0,最小,3.1举例,69,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=
31、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)Z225+2x2-3x4,70,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 为最优解,71,（1）线性规划模型为标准形式（2）约束条件系数矩阵中至少有一个单位子矩阵（3）目标函数中
32、不含基变量这样的线性规划模型称为规范型,72,线性规划基本概念练习（1）,0,3,6,x1,x2,O,A,B,C,E,F,G,H,I,4,6,-2,min z=-x1+2x2s.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,z=4,C,D,4,73
33、,1.确定初始基可行解,由于基可行解是由一个可行基决定的，因此，确定初始基可行解X0相当于确定一个初始可行基B0。,方法：若A中含I，则B0=I；若A中不含I，则可用人工变量法构 造一个I。,问题：若B0=I，则X0=？,3.2单纯形法的步骤,74,2.最优性检验,问题：用什么检验？,目标。,问题：非最优的特征为何？,75,3.寻找更好的基可行解,由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基B0变换为下一个新的基B1，因此，本步骤也称为基变换。,（基变换）,76,4.迭代,77,以下面模型为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。,（1）先将模型化为标准型,
34、(2)确定初始基可行解、检验,78,（3）换基、计算下一个基可行解、再检验，直至最优,问题：当模型规模较大时，计算量很大。,事实上，单纯形法的实现是在单纯形表上完成的。,79,第4节单纯形法的计算步骤单纯形表,单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。,回顾单纯形法步骤,80,单纯形表的主要结构：,问题：第一张表的B-1=？,单位阵I。,检验数的公式是什么？,81,单纯形表求解线性规划问题,maxZ=6x1+5x2 x1+3x290 2x1+x275 2x1+2x2 80 x1,x20,maxZ=6x1+5x2 x1+3x2+x390 2x1+x2+x4 75 2x1+
35、2x2+x580 xi0,82,83,84,所以把x4换出为非基变量，x1为换入变量即新的基变量。,85,86,87,88,89,所以把x5换出为非基变量，x2为换入变量即新的基变量。,90,91,92,93,此时所有的检验数都小于等于0，所以该解为最优解。,最优解为X（35，5，40，0，0）T，Z*235,94,练习：对于下面的线性规划,（1）用图解法求解；（2）将模型化为标准型；（3）用单纯形法步骤求出其最优解，并指出求 解过程中每一个基可行解相当于可行域的 哪一个角点。,95,Step 0 获得一个初始的单纯形表，确定基变量和非基变量Step 1 检查基变量在目标函数中的系数是否等于0
36、，在约束条件中的系数是否是一个单位矩阵。Step 2 如果表中非基变量在目标函数中的系数全为负数，则已得到最优解。停止。否则选择系数为正数且绝对值最大的变量进基，转step 3。Step 3 如果进基变量在约束条件中的系数全为负数或0，则可行域开放，目标函数无界。停止。否则选取右边常数和正的系数的最小比值，对应的基变量离基，转step 4。Step 4 确定进基变量的列和离基变量的行交叉的元素为“主元”，对单纯形表进行行变换，使主元变为1，主元所在列的其他元素变为0。将离基的基变量的位置用进基的非基变量代替。转Step 2。,单纯形表的算法描述,96,1.maxZ=3x1+9x2 x1+3x2
37、21-x1+x24 x1,x20,maxZ=3x1+9x2 x1+3x2+x321-x1+x2+x4 4 xi0,举例,97,所以把x4换出为非基变量，x2为换入变量即新的基变量。,98,99,100,101,所以把x3换出为非基变量，x1为换入变量即新的基变量。,102,103,104,此时所有的检验数都小于等于0，所以该解为最优解。,最优解为X（9/4，25/4，0，0）T，Z*63,由于非基变量x4的检验数0，所以我们可以把它作为换入基变量来考虑。,105,106,107,108,此时所有的检验数都小于等于0，所以该解为最优解。Z*=63,109,1.maxZ=x1+x2-2x1+x24
38、 x1-x22 x1,x20,maxZ=x1+x2-2x1+x2+x34 x1-x2+x4 2 xi0,举例,110,所以把x3换出为非基变量，x2为换入变量即新的基变量。,111,112,113,114,可以看出，的检验数为3，大于0，但是的系数列向量中的所有原数（-2,-1）T，都小于0，所以该题为无界解。,115,练习：用单纯形法求解,问题：标准模型的A中是否含I？,松弛变量系数恰好构成I。,116,中表示进基列与出基行的交叉元，下一张表将实行以它为主元的初等行变换（称高斯消去）。方法是：先将主元消成1，再用此1将其所在列的其余元消成0。,117,（请解释其实际意义）,118,第5节 单
39、纯形法的进一步讨论,5.1 人工变量法1.大M法约束条件：“”加一个剩余变量后，再加一个人工变量“”加一个人工变量目标函数：人工变量的系数为“M”，即罚因子若线性规划问题有最优解则人工变量必为0。,119,MaxZ=3x1-x2-x3 x1-2x2+x311-4x1+x2+2x33-2x1+x3=1 xi 0,MaxZ=3x1-x2-x3+0 x4+0 x5-Mx6-Mx7 x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1 xi 0,增加人工变量后，线性规划问题中就存在一个B为单位矩阵，后面可以根据我们前面所讲的单纯形法来进行求解。,120,121,
40、122,123,124,125,126,127,128,129,130,131,132,133,134,135,此时所有的检验数都小于等于0，所以该解为最优解。,最优解为X（4，1，9，0，0，0，0）T，Z*2,136,2.两阶段法第一阶段在不考虑原问题是否存在基可行解，给原问题加入人工变量，并构建一个仅含人工变量的目标函数（求极小化），人工变量的系数一般为1，约束条件和原问题的一样。当第一阶段中目标函数的最优值0，既人工变量0，则转入第二阶段；若第一阶段中目标函数的最优值不等于0，既人工变量不等于0，则判断原问题为无解。第二阶段：将第一阶段计算所得的单纯形表划去人工变量所在的列，并加目标函
41、数换为原问题的目标函数作为第二阶段的初始单纯形表，进行进一步的求解。,137,MaxZ=3x1-x2-x3 x1-2x2+x311-4x1+x2+2x33-2x1+x3=1 xi 0,MinZ=x6+x7 x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1 xi 0,增加人工变量后，线性规划问题中就存在一个B为单位矩阵，后面可以根据我们前面所讲的单纯形法来进行求解。,138,139,140,141,142,143,可以看到人工变量x6，x7均为0，所以构造的目标函数w=0，因此可以判断该线性规划问题有可行解，可以进行第二阶段的计算。,144,maxz=
42、3x1-x2-x3 s.t.x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1 xj0,145,此时所有的检验数都小于等于0，所以该解为最优解。,最优解为X（4，1，9，0，0，0，0）T，Z*2,可以看出该结果和大M法所得的结果是一样的。,146,第6节 用Excel“规划求解”工具求解线性规划问题,在Excel电子表格中建立线性规划模型用Excel“规划求解”工具求解线性规划问题使用单元格命名建好电子表格模型的几个原则,147,第6节 用Excel“规划求解”工具求解线性规划问题,在用电子表格建立数学模型（这里是一个线性规划模型）的过程中，有三个问题需要得到回
43、答：（1）要作出的决策是什么？（决策变量）（2）在作出这些决策时，有哪些约束条件？（约束条件）（3）这些决策的目标是什么？（目标函数）,148,例1.1 某工厂要生产两种新产品：门和窗。经测算，每生产一扇门需要在车间1加工1小时、在车间3加工3小时；每生产一扇窗需要在车间2和车间3各加工2小时。而车间1每周可用于生产这两种新产品的时间为4小时、车间2为12小时、车间3为18小时。已知每扇门的利润为300元，每扇窗的利润为500元。而且根据经市场调查得到的该两种新产品的市场需求状况可以确定，按当前的定价可确保所有新产品均能销售出去。问该工厂应如何安排这两种新产品的生产计划，可使总利润最大？,14
44、9,第6节 用Excel“规划求解”工具求解线性规划问题,150,第6节 用Excel“规划求解”工具求解线性规划问题,用Excel“规划求解”工具求解线性规划问题（如果“工具”菜单中没有“规划求解”选项，请参见SOLVER文件夹下的“Excel规划求解工具的安装说明.doc”）,151,第6节 用Excel“规划求解”工具求解线性规划问题,152,第6节 用Excel“规划求解”工具求解线性规划问题,在用Excel的“规划求解”工具求解线性规划问题，为单元格命名能使线性规划问题的电子表格模型更加容易理解。主要表现在两个方面：（1）在公式中使用名称使人们更容易理解公式的含义；（2）在“规划求解
45、参数”对话框中使用名称使人们更加容易理解线性规划模型的含义。所以，一般给跟公式和模型有关的四类单元格命名。例如：在例1.1电子表格模型中，单元格命名如下：（1）数据单元格：单位利润（C4:D4）、可用工时（G7:G9）；（2）可变单元格：每周产量（C12:D12）；（3）输出单元格：实际使用（E7:E9）；（4）目标单元格：总利润（G12）。,153,第6节 用Excel“规划求解”工具求解线性规划问题,154,例1.2 某公司有100万元的资金要投资(要求全部用完)。该公司有六个可选的投资项目，其各种数据如表1-2所示。,155,该公司想达到的目标为：投资风险最小，每年红利至少为6.5万元，
46、最低平均增长率为12%，最低平均信用度为7。请用线性规划方法求解该问题。,156,得到的线性规划数学模型为：,这是一个典型的成本（或风险）最小化问题。其中，“Min”是英文单词“Minimize”的缩写，含义为“最小化”。因此，上述模型的含义是：在给定的条件限制下，求使得目标函数z达到最小时的x1,x2,x3,x4,x5,x6取值,157,第6节 用Excel“规划求解”工具求解线性规划问题,158,第6节 用Excel“规划求解”工具求解线性规划问题,电子表格建模是一门艺术，建立一个好的电子表格模型应遵循以下几个原则：（1）首先输入数据；（2）清楚地标识数据；（3）每个数据输入到唯一的单元格
47、；（4）将数据与公式分离；（5）保持简单化（使用SUMPRODUCT函数、SUM函数、中间结果等）；（6）使用区域名称；（7）使用边框、底色来区分单元格类型（四类单元格）；（8）在电子表格中显示整个模型（包括符号和数据）。Excel提供许多有效的工具来帮助用户进行模型调试，其中一个工具是电子表格的输出单元格在数值和公式之间进行切换（“工具”“选项”“视图”“公式”）。Excel的“审核”工具栏也提供了几个有用的工具。,159,第7节 应用举例,7.1 资源分配问题7.2 成本收益平衡问题7.3 网络配送问题7.4 混合问题,160,7.1 资源分配问题,资源分配问题是将有限的资源分配到各种活动
48、（决策）中去的线性规划问题。这一类问题的共性是在线性规划模型中每一个函数约束均为资源约束,并且每一种资源都可以表现为如下的形式：使用的资源数量 可用的资源数量对任何资源分配问题，有三种数据必须收集：（1）每种资源的可供量；（2）每一种活动所需要的各种资源的数量,对于每一种资源与活动的组合,单位活动所消耗的资源量必须首先估计出来；（3）每一种活动对总的绩效测度（如总利润）的单位贡献（如单位利润）。,161,7.1 资源分配问题,例7.1 某公司是商务房地产开发项目的主要投资商。目前，该公司有机会在三个建设项目中投资：项目1：建造高层办公楼；项目2：建造宾馆；项目3：建造购物中心。每个项目都要求投
49、资者在四个不同的时期投资：在当前预付定金，以及一年、二年、三年后分别追加投资。表7-1显示了四个时期每个项目所需资金（百万元）。投资者可以按一定的比例进行投资和获得相应比例的收益。,公司目前有2500万元资金可供投资，预计一年后，又可获得2000万元，两年后获得另外的2000万元，三年后还有1500万元以供投资。那么，该公司要在每个项目中投资多少比例，才能使其投资组合获得最大的总净现值？,162,7.1 资源分配问题,解：这是一个资源分配问题。(1)决策变量 设：x1，x2，x3分别为在办公楼项目、宾馆项目、购物中心项目中的投资比例(2)目标函数 本问题的目标是总净现值最大,163,7.1 资
50、源分配问题,(3)约束条件 本题的约束条件是公司在各期可获得的资金限制（资源约束）。但要注意的是：前一期尚未使用的资金，可以在下一期使用（为了简化问题，不考虑资金可获得的利息）。因此，每一时点的资金限制就表现为累计的资金。表7-2显示了累计的资金数据。,164,7.1 资源分配问题,数学模型（线性规划模型）,165,7.1 资源分配问题,电子表格模型,166,补充：例7.1的解法2,例7.1还可用另外一种解法，引入剩余变量si。数学模型为：,167,补充：例7.1的解法2,例7.1还可用另外一种解法，引入剩余变量si。电子表格模型为：注意：在“规划求解”中，决策变量不连续时，用;隔开,168,
