第4章-确定性决策-线性规划初步1解析课件.ppt

1、线性规划问题n生产计划问题n配料问题n背包问题n运输问题n指派问题1.生产计划问题（Production Planning）产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.18某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：求使得总利润最大的生产计划。产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.

2、05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.18设四种产品的产量分别为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目标函数约束条件变量非负约束这个问题的最优解为：x1=294.12件，x2=1500件，x3=0，x4=58.82件最大利润为：z=

3、12737.06元。问题：三个约束条件可以改为等式吗？2.配料问题（Material Blending）某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（）如下表：T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30单价（元/公斤）115978276要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。T1T2T3T4GCr

4、3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30单价（元/公斤）115978276min z=115x1+97x2+82x3+76x4s.t.0.0321x1+0.0453x2+0.0219x3+0.0176x43.20 Cr的含量下限约束 0.0204x1+0.0112x2+0.0357x3+0.0433x42.10 Mn的含量下限约束 0.0582x1+0.0306x2+0.0427x3+0.0273x44.30 Ni的含量下限约束 x1+x2+x3+x4=100 物料平衡约束 x1,x2,x3,x40设四种原

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

6、 x1+41x2+20 x350 x1，x2，x30 x1，x2，x3为整数这是一个整数规划问题（Integer Programming）。这个问题的最优解为：x1=1件，x2=0件，x3=2件，最高价值z=87元物品1物品2物品3重量（公斤/件）104120价值（元/件）1772354.运输问题（Transportation）某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060求总运费最低的运输方案。运价（

7、元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060A1A2B3B2B135吨25吨10吨30吨20吨235478运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060设从两个供应地到三个需求地的运量（吨）如下表：B1B2B3A1x11x12x13A2x21x22x23运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060min z=2x11+3x12+5x13+4x21+7x22+8x23s.t.x11+x12+x13 =35 供应地A1 x21+x22+x23=25 供应地A

8、2 x11 +x21 =10 需求地B1 x12 +x22 =30 需求地B2 x13 +x23=20 需求地B3 x11,x12,x13,x21,x22,x230 运量（吨）B1B2B3供应量（吨）A130535A2101525需求量（吨）10302060这个问题的最优解表示如下：最小总运费为：z=330+55+410+815=275元A1A2B3B2B135吨25吨10吨30吨20吨23547830吨5吨10吨15吨5.指派问题（Assignment Problem）有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个人完成j项任务的成本（或效益）为cij。求使总成本最小（

9、或总效益最大）的分配方案。设：项任务个人被指派完成第第项任务个人不从事第第ji1ji0 xij1,0 xn,.,2,1i1xn,.,2,1j1x.t.sxczmax(min)ijn1jijn1iijn1in1jijij张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。语文数学物理化学张92688576王82917763李83907465赵93618375门课个老师教第第门课个老师不教第第ji1ji0 xij设：语文数学物理化

10、学张x11x12x13x14王x21x22x23x24李x31x32x33x34赵x41x42x43x44max z=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90 x32+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

11、=1 (7)x14+x24+x34+x44=1 (8)xij=0,1最优解为：x14=1，x23=1，x32=1，x41=1，max z=336即张老师教化学，王老师教语文，李老师教数学，赵老师教语文。语文数学物理化学张0001王0010李0100赵1000语文数学物理化学张92688576王82917763李83907465赵93618375四门课的总分可以达到336分。线性规划模型min(max)z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn (,)b1 a21x1+a22x2+a2nxn (,)b2 am1x1+am2x2+amnxn (,)bm x1,x2,

12、xn 0(,Free)线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：0 x,x,x9x4+x+x8xx+x+x2.t.sxx2+x3=zmin32132113212121线性规划的标准形式目标函数为极小化，约束条件全部为等号约束，所有变量全部是非负的，这样的线性规划模型称为标准形式min z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0 线性规划模型用矩阵和向量表示min z=c1x1+c2x

13、2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0 mn2m1mn22221n11211aaaaaaaaaAm21bbbbn21ccccn21xxxX线性规划模型用矩阵和向量表示（续）nn2211n21n21TxcxcxcxxxcccXCznmn22m11mnn2222121nn1212111n21mn2m1mn22221n11211xaxaxaxaxaxaxaxaxaxxxaaaaaaaaaAX因此，线性规划模型可以写成如下矩阵和向量的形式0Xb=AX.t.sXC=zminT线

14、性规划模型总结线性规划模型的结构n目标函数：max，minn约束条件：,=,n变量符号：0,0,Free线性规划的标准形式n目标函数：minn约束条件：=n变量符号：0Free0XbAXtsXCzT,)(),(.max(min)0XbAX.t.sXCzminT线性规划问题的标准化n极大化目标函数转化为极小化n小于等于约束条件转化为等号约束n大于等于约束条件转化为等号约束n变量没有符号限制（Free）的标准化n变量小于等于0的标准化 max z=2x1-3x2+x3令 z=-z，z=-2x1+3x2-x3新的目标函数 min z=-2x1+3x2-x3取得极小化的最优解时，这个最优解同时使原目标

15、函数值取得最大化的最优解。但两个问题最优解的目标函数值相差一个负号。极大化目标函数问题转化为极小化目标函数例如，对于以下两个线性规划问题max z=2x1+3x2s.t.x1+x23 x21 (A)x1,x20min z=-2x1-3x2s.t.x1+x23 x21 (B)x1,x20它们的最优解都是x1=2,x2=1，但(A)的最大化的目标函数值为max z=7，(B)的最小化的目标函数值为min z=-7 2x1+3x2-4x35引进松弛变量(Slack variable)x4=5-(2x1+3x2-4x3)，把松弛变量x4加在约束条件左边，就可以将小于等于约束变为等式。2x1+3x2-4

16、x3+x4=5由此可以知道，松弛变量x40。如果有一个以上小于等于约束，要对于每一个约束引进不同的松弛变量。例如：2x1+3x2-4x35 3x1-2x2+5x38在两个约束中分别引进松弛变量x4，x50 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 +x5=8小于等于约束条件转化为等号约束将不等式约束变为等式约束。例如：2x1+3x2-4x35 3x1-2x2+5x38在两个约束的左边分别减去松弛变量x4，x50 2x1+3x2-4x3-x4 =5 3x1-2x2+5x3 -x5=8大于等于约束条件转化为等号约束没有符号限制的变量，用两个非负变量之差表示。例如：max z=x1

17、+2x2-3x3s.t.2x1+3x2-4x35 3x1-2x2+5x38 x10,x2:free,x30先将目标函数转化为极小化，并在约束中引进松弛变量，把不等式约束变为等式。Min z=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10,x2:free,x3,x4,x50变量没有符号限制(Free)的标准化Min 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。代入模型，消去x2Min z

18、=-x1-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整理，得到标准形式：Min 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,x50max z=x1+2x2-3x3s.t.2x1+3x2-4x353x1-2x2+5x38x10,x20,x30min z=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4 =53x1-2x2+5x3 -x5=8x

19、10,x20,x3,x4,x50令 x2=-x2，x20,代入模型min z=-x1+2x2+3x3s.t.2x1-3x2-4x3+x4 =53x1+2x2+5x3 -x5=8x10,x20,x3,x4,x50变量小于等于0的的标准化可行域目标函数等值线最优解6543211 2 3 4 5 6-8 -7 -6 -5 -4 -3-2 -1 0 x1x2z=6z=3z=9z=12问题：1、线性规划的最优解是否可能位于可行域的内部？2、线性规划的最优解是否可能位于可行域的边界上？凸集凸集不是凸集线性规划可行域和最优解的几种情况1、可行域封闭 唯一最优解2、可行域封闭 多个最优解3、可行域开放 唯一最

20、优解4、可行域开放 多个最优解5、可行域开放 目标函数无界6、无可行解解的可行性和松弛变量符号的关系A(1,2.5)B(2,1)C(1.5,3)max z=2x1+3x2s.t.x1+x24 (1)-x1+x21 (2)x1,x20max z=2x1+3x2s.t.x1+x2+x3 =4 -x1+x2 -x4=1 x1,x2,x3,x40引进松弛变量约束条件(1)约束条件(2)D(3,2)A(1,2.5)满足所有约束条件，x3=0.5,x4=0.5B(2,1)满足(1)，不满足(2)，x3=1,x4=-2C(1.5,3)不满足(1),满足(2)，x3=-0.5,x4=0.5D(3,2)不满足(

21、1)和(2)，x3=-1,x4=-2结论：如果一个解满足一个约束条件，相应的松弛变量大于等于0。如果一个解不满足一个约束条件，相应的松弛变量小于0。0 1 2 3 4-14321x2x1x3=0 x4=0max z=x1+2x2s.t.x1+x23 x2 1 x1,x2 0max z=x1+2x2s.t.x1+x2+x3 =3 x2 +x4=1 x1,x2,x3,x40 x1=0,x2=0 x3=3,x4=1x1=0,x4=0 x2=1,x3=2x2=0,x3=0 x1=3,x4=1x3=0,x4=0 x1=2,x2=1x1=0,x3=0 x2=3,x4=-2x2=0 x1=0OABCD线性规

22、划的基本概念基、基础解、基础可行解、极点 标准化的线性规划问题，有n个变量，m个约束。p令其中n-m个变量等于零，如果剩下的m个变量的系数矩阵的行列式不等于0，这个mm的矩阵称为线性规划的一个基。等于0的n-m个变量称为非基变量，m个变量称为基变量。p求解mm的线性方程组，得到基变量的一组解，连同等于0的非基变量这n个变量的值称为线性规划的一个基础解。p如果一个基础解中的所有变量都是非负的，这个基础解称为基础可行解。p线性规划的基础可行解就是可行域的极点。线性规划的基本概念基、基础解、基础可行解、极点max z=x1+2x2s.t.x1+x23 x2 1 x1,x2 0max z=x1+2x2

23、s.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=3,x4=-2是基础解，但不是可行解OABx3=0 x4=0 x2=0 x1=0CD可行域几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基础解可行域的极点基础可行解目标函数等值：一组平行线 目标函数值等于一个常数的

24、解maxz=2x1+3x2+x3s.t.x1+3x2+x3152x1+3x2-x318x1-x2+x33x1,x2,x30minz=-2x1-3x2-x3stx1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1,x2,x3,x4,x5,x60通过搜索所有基础可行解求出最优解x1+3x2+x3=152x1+3x2-x3=18x1-x2+x3=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基础

25、可行解，表示可行域的一个极点。目标函数值为：z=20 x1+3x2+x4=152x1+3x2=18x1-x2=3基变量x1、x2、x4，非基变量x3、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1+3x2=152x1+3x2+x5=18x1-x2=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量x1、x2、x5，非基变量x3、x4、x6基础解为（

26、x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0）是基础解，但不是可行解，不是一个极点。x1+3x2=152x1+3x2=18x1-x2+x6=3基变量x1、x2、x6，非基变量x3、x4、x5基础解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基础可行解，表示可行域的一个极点。目标函数值为：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3+x4=153x2-x3=18-x2+x3=3基变量x2、x3、x4，非基变量x1、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，21/2，

27、27/2，-30，0，0）是基础解，但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3=153x2-x3+x5=18-x2+x3=3基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=15x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3=153x2-x3=18-x2+x3+x6=3基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，

28、x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基础解但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3可行域极点的数量如果线性规划有50个变量，20个约束条件，全部是等号约束。按照以上的算法，每计算一个基础解，要从50个变量中选择30个非基变量等于0，剩下20个变量，如果相应的2020行列式不等于0，则通过计算一个20 20的线性方程组得到基变量。要穷尽所有的基础解，最多可能要计算的线性方程组的个数为1320501074302050C.!假设每计算一个2020线性组需要1秒钟，计算以上所有方程组需要的时间为（年）6131051

29、3652436001074.由于极点的个数随着约束条件的增加而很快增加，用搜索所有极点来求出线性规划最优解，实际上并不是一个可行的方法。单纯形法原理示意图极点4，最优解初始极点1极点2极点3其实，不必搜索可行域的每一个极点，只要从一个极点出发，沿着使目标函数改善的方向，到达下一个相邻的极点。如果相邻的所有极点都不能改善目标函数，这个极点就是最优极点。用这样的搜索策略，可以大大减少搜索极点的个数。按照这样的搜索策略建立的算法，叫做单纯形法。单纯形法可以有效地减少搜索极点的个数。目标函数改善目标函数改善目标函数改善 单纯形法原理（1）松弛变量的表示max z=x1+2x2s.t.x1+x23 x2

30、 1 x1,x20max z=x1+2x2s.t.x1+x2+x3 =3 x2 +x4=1 x1,x2,x3,x40 x2=0 x1=0 x3=0 x4=0OABCD 引进松弛变量x2=0 x1=0 x3=0 x4=0OABCx1,x2=0为非基变量x3,x40为基变量当前基础可行解：(x1,x2,x3,x4)=(0,0,3,1)z=0 x2进基,从0开始增加，x3,x4随之减少第一次叠代：目标函数和基变量分别用非基变量表示：z=-x1-2x2选择x2进基 x3 =3-x1-x2 x4=1 -x2x2=1成为基变量，x4=0成为离基变量当前基础可行解：(x1,x2,x3,x4)=(0,1,2,

31、0)z=-2单纯形法原理(2)第一次叠代确定离基变量的进一步讨论设非基变量为x1、x2，基变量为x3、x4、x5，进基变量为x2x3 =5-x1-4x2 x4 =4-2x1-3x2 x5=2-3x1-x25/4=1.254/3=1.332/1=2min5/4,4/3,2/1=5/4当x2增加到1.25时x30离基x3 =5-x1+4x2 x4 =4-2x1-3x2 x5=2-3x1-x2x3增加4/3=1.332/1=2min4/3,2/1=4/3当x2增加到1.33时x40离基x3 =5-x1+4x2 x4 =4-2x1+3x2 x5=2-3x1-x2x3增加x4增加2/1=2min2/1=

32、2/1当x2增加到2时x50离基x3 =5-x1+4x2 x4 =4-2x1+3x2 x5=2-3x1+x2x3增加x4增加x5增加x2可以无限增加，可行域是开放区域，目标函数无界x2=0 x1=0 x3=0 x4=0OABC第二次叠代：目标函数和基变量分别用非基变量表示：z=-2-x1+2x4选择x1进基 x3 =2-x1+x4 x2=1 -x4当前基础可行解：(x1,x2,x3,x4)=(0,1,2,0)z=-2单纯形法原理（3）第二次叠代x1进基，从0开始增加，基变量x2保持不变，x3从2开始减少x1=2成为基变量，x3=0成为非基变量当前基础可行解：(x1,x2,x3,x4)=(2,1

33、,0,0)z=-4x2=0 x1=0 x3=0 x4=0OABC第三次叠代：目标函数和基变量分别用非基变量表示：z=-4+x3+x4 x1 =2-x3+x4 x2=1 -x4非基变量在目标函数中的系数全部大于0，已获得最优解。单纯形法原理（4）最优解的判定x1=2成为基变量，x3=0成为非基变量当前基础可行解：(x1,x2,x3,x4)=(2,1,0,0)z=-4x2=0 x1=0 x3=0 x4=0OABC单纯形法原理(5)叠代过程回顾max z=x1+2x2s.t.x1+x23 x2 1 x1,x20min z=-x1-2x2s.t.x1+x2+x3 =3 x2 +x4=1 x1,x2,x

34、3,x40引进松弛变量x3,x4单纯形法原理(6)叠代过程回顾x2=0 x1=0 x3=0 x4=0OABC(x1,x2,x3,x4)=(0,0,3,1),z=0min z=-x1-2x2s.t.x1+x2+x3 =3 x2 +x4=1 x1,x2,x3,x40min z=-x1-2x2s.t.x3 =3-x1-x2 x4=1 -x2 x1,x2,x3,x40根据目标函数中非基变量x1,x2的系数-1,-2，确定x2进基。根据 min3/1,1/1=1,确定x4离基。对应于C点第一次叠代x2进基，x4离基(x1,x2,x3,x4)=(0,1,2,0),z=-2目标函数z和基变量x3,x4用非基

35、变量x1,x2表示。x2=0 x1=0 x3=0 x4=0OABC第二次叠代x1进基，x3离基(x1,x2,x3,x4)=(0,1,2,0),z=-2(x1,x2,x3,x4)=(2,1,0,0),z=-4min z=-x1-2x2s.t.x1+x2+x3 =3 x2 +x4=1 x1,x2,x3,x40min z=-x1-2x2s.t.x2+x3=3-x1 x2 =1 -x4x1,x2,x3,x40单纯形法原理(7)叠代过程回顾基变量x2,x3用非基变量x1,x4表示。min z=-2-x1+2x4s.t.x3=2-x1+x4 x2 =1 -x4x1,x2,x3,x40目标函数用非基变量x1

36、,x4表示。根据目标函数中非基变量x1,x4的系数-1,2，确定x1进基。根据 min2/1,-=2,确定x3离基。对应于B点单纯形法原理(8)叠代过程回顾x2=0 x1=0 x3=0 x4=0OABC(x1,x2,x3,x4)=(2,1,0,0),z=-4min z=-x1-2x2s.t.x1+x2+x3 =3 x2 +x4=1 x1,x2,x3,x40min z=-x1-2x2s.t.x1+x2=3-x3 x2=1 -x4x1,x2,x3,x40基变量x1,x2用非基变量x3,x4表示。min z=-4+x3+x4s.t.x1=2-x3+x4 x2 =1 -x4x1,x2,x3,x40目标

37、函数用非基变量x1,x4表示。根据目标函数中非基变量x3,x4的系数+10,+10，x1=2,x2=1,x3=0,x4=0,z=-4为最优解，对应于B点x2=0 x1=0 x3=0 x4=0OABC第一次叠代x2进基，x4离基第二次叠代x1进基，x3离基(x1,x2,x3,x4)=(0,0,3,1),z=0(x1,x2,x3,x4)=(0,1,2,0),z=-2(x1,x2,x3,x4)=(2,1,0,0),z=-4,最优解单纯形法原理(9)叠代过程回顾单纯形法原理（6）单纯形法总结STEP 0 找到一个初始的基础可行解，确定基变量和非基变量。转STEP 1。STEP 1 将目标函数和基变量分

38、别用非基变量表示。转STEP 2。STEP 2 如果目标函数中所有非基变量的系数全部为正数，则已经获得最优解。运算终止。否则，选取系数为负数并且绝对值最大的非基变量进基。转STEP 3。STEP 3 如果进基变量增加时，基变量都不减少，则可行域开放，目标函数无界。运算终止。否则，随着进基变量的增加，最先下降到0的基变量离基。转STEP 1。线性规划基本概念练习（1）036x1x2OABCEFGHI46-2min z=-x1+2x2s.t.3x1+2x212(1)x1+2x2 6(2)-2x1+x2 4(3)x1,x2 01、约束条件（1）对应的直线是（），对应的半平面是 约束条件（2）对应的直

39、线是（），对应的半平面是 约束条件（3）对应的直线是（），对应的半平面是2、这个线性规划的可行域是（）。3、对于z=2和4,分别画出目标函数等值线。4、这个线性规划的最优解位于（）。ACEFBCDHEGHICDGEz=2z=4CD4036x1x2OABCEFGHI46-2D线性规划基本概念练习（2）5、x1等于0的直线是()，x2等于0的直线是()，x3等于0的直线是()，x4等于0的直线是()，x5等于0的直线是()。6、A点对应的基变量是()，非基变量是（）；D点对应的基变量是()，非基变量是（）。7、A点不是可行解,是由于()0 F点不是可行解,是由于()0 I 点不是可行解,是由于()0，则原问题没有可行解。STEP 4 转到第二阶段，从原问题的初始基础可行解出发，求出原问题的最优解。