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

《第4章确定性决策线性规划初步解析课件.ppt》由会员分享，可在线阅读，更多相关《第4章确定性决策线性规划初步解析课件.ppt（87页珍藏版）》请在三一办公上搜索。

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

2、x4s.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=12737.06元。问题：三个约束条件可以改为等式吗？,2. 配料问题（Material Blending）,某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量

3、（），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（）如下表：,要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。,min 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,

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

5、x1，x2，x30 x1，x2，x3为整数这是一个整数规划问题（Integer Programming）。这个问题的最优解为： x1=1件，x2=0件，x3=2件，最高价值z=87元,4. 运输问题（Transportation）,某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：,求总运费最低的运输方案。,35吨,25吨,10吨,30吨,20吨,设从两个供应地到三个需求地的运量（吨）如下表：,min z=2x11+3x12+5x13+4x21+7x22+8x23s.t. x11+x12+x13 =

6、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,这个问题的最优解表示如下：,最小总运费为：z=330+55+410+815=275元,30吨,5吨,10吨,15吨,5. 指派问题（Assignment Problem）,有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个人完成j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。设：,张、王、李、赵四位老师被分配教语文、

7、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。,设：,max 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

8、+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,最优解为：x14=1，x23=1，x32=1，x41=1，max z=336即张老师教化学，王老师教语文，李老师教数学，赵老师教语文。,四门课的总分可以达到336分。,线性规划模型,min(max) z=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn (, )b1 a21x1+a22x2+a2nxn (, )b2 am1x1+am2x2+amnxn (, )bm x1, x2, , xn 0

9、(, Free),线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：,线性规划的标准形式,目标函数为极小化，约束条件全部为等号约束，所有变量全部是非负的，这样的线性规划模型称为标准形式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+c2x2+cnxns.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a

10、2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0,线性规划模型用矩阵和向量表示（续）,因此，线性规划模型可以写成如下矩阵和向量的形式,线性规划模型总结,线性规划模型的结构目标函数 ：max，min约束条件：,=,变量符号：0, 0, Free线性规划的标准形式目标函数：min约束条件：=变量符号：0,线性规划问题的标准化,极大化目标函数转化为极小化小于等于约束条件转化为等号约束大于等于约束条件转化为等号约束变量没有符号限制（Free）的标准化变量小于等于0的标准化,max z=2x1-3x2+x3令 z=-z，z=-2x1+3x2-x3新的目标函数 min

11、 z=-2x1+3x2-x3取得极小化的最优解时，这个最优解同时使原目标函数值取得最大化的最优解。但两个问题最优解的目标函数值相差一个负号。,极大化目标函数问题转化为极小化目标函数,例如，对于以下两个线性规划问题,max z=2x1+3x2s.t. x1+x23 x21 (A) x1, x20,min 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+

12、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,小于等于约束条件转化为等号约束,将不等式约束变为等式约束。例如： 2x1+3x2-4x35 3x1-2x2+5x38在两个约束的左边分别减去松弛变量x4，x50 2x1+3x2-4x3-x4 =5 3x1-2x2+5x3

13、 -x5=8,大于等于约束条件转化为等号约束,没有符号限制的变量，用两个非负变量之差表示。例如：max z=x1+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+5

14、x3-x5=8 x10, x2:free, x3, x4, x50然后，令x2=x2-x2”，其中x2,x2”0。代入模型，消去x2Min z=-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,x50,max z=x1+2x2-3x3s.t. 2x1+3x2-

15、4x353x1-2x2+5x38x10, x20, x30min z=-x1-2x2+3x3s.t. 2x1+3x2-4x3+x4 =53x1-2x2+5x3 -x5=8x10, 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的的标准化,线性规划的图解,max z=x1+3x2s.t. x1+ x26-x1+2x28x1 0, x20,可行域,目标函数等值线,最优解,z=6,z=3,z=9,z=12,问题

16、：1、线性规划的最优解是否可能位于可行域的内部？ 2、线性规划的最优解是否可能位于可行域的边界上？,可行域的性质,线性规划的可行域是凸集线性规划如果有最优解，最优解至少在可行域的一个极点上,凸集,凸集,不是凸集,线性规划可行域和最优解的几种情况,1、可行域封闭 唯一最优解,2、可行域封闭 多个最优解,3、可行域开放 唯一最优解,4、可行域开放 多个最优解,5、可行域开放 目标函数无界,6、无可行解,解的可行性和松弛变量符号的关系,max z=2x1+3x2s.t. x1+x24 (1) -x1+x21 (2) x1, x20,max z=2x1+3x2s.t. x1+x2+x3 =4 -x1+

17、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),满足(2)，x3=-0.5, x4=0.5D(3,2)不满足(1)和(2)，x3=-1, x4=-2结论：如果一个解满足一个约束条件，相应的松弛变量大于等于0。如果一个解不满足一个约束条件，相应的松弛变量小于0。,x3=0,x4=0,max z=x1+2x2s.t. x1+x23 x2 1 x1, x2 0,max z=x1+2x2s.t. x1+x2+ x3 =3 x2 +x4=1

18、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,x2=0,x1=0,O,A,B,C,D,线性规划的基本概念基、基础解、基础可行解、极点,标准化的线性规划问题，有n个变量，m个约束。令其中n-m个变量等于零，如果剩下的m个变量的系数矩阵的行列式不等于0，这个mm的矩阵称为线性规划的一个基。等于0的n-m个变量称为非基变量，m个变量称为基变量。求解mm的线性方程组，得到基变量的一组解，连同等于0

19、的非基变量这n个变量的值称为线性规划的一个基础解。如果一个基础解中的所有变量都是非负的，这个基础解称为基础可行解。线性规划的基础可行解就是可行域的极点。,线性规划的基本概念基、基础解、基础可行解、极点,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基础可行

20、解,x1=0, x3=0 x2=3, x4=-2是基础解，但不是可行解,O,A,B,x3=0,x4=0,x2=0,x1=0,C,D,可行域,几何概念,代数概念,约束直线,满足一个等式约束的解,约束半平面,满足一个不等式约束的解,约束半平面的交集：凸多边形,满足一组不等式约束的解,约束直线的交点,基础解,可行域的极点,基础可行解,目标函数等值：一组平行线,目标函数值等于一个常数的解,通过搜索所有基础可行解求出最优解,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=20

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

22、,基础解为（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0）是基础解，但不是可行解。,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=15,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基础解但不是可行解。,可行域极点的数量,如果线性规划有50个变量，20个约束条件，全部是等号约束。按照以上的算法，每计算一个基础解，要从50个变量中选择30

23、个非基变量等于0，剩下20个变量，如果相应的2020行列式不等于0，则通过计算一个20 20的线性方程组得到基变量。要穷尽所有的基础解，最多可能要计算的线性方程组的个数为,假设每计算一个2020线性组需要1秒钟，计算以上所有方程组需要的时间为,由于极点的个数随着约束条件的增加而很快增加，用搜索所有极点来求出线性规划最优解，实际上并不是一个可行的方法。,单纯形法原理示意图,极点4，最优解,初始极点1,极点2,极点3,其实，不必搜索可行域的每一个极点，只要从一个极点出发，沿着使目标函数改善的方向，到达下一个相邻的极点。如果相邻的所有极点都不能改善目标函数，这个极点就是最优极点。用这样的搜索策略，可

24、以大大减少搜索极点的个数。按照这样的搜索策略建立的算法，叫做单纯形法。单纯形法可以有效地减少搜索极点的个数。,目标函数改善,目标函数改善,目标函数改善, ,单纯形法原理（1）松弛变量的表示,max z=x1+2x2s.t. x1+x23 x2 1 x1, x20,max z=x1+2x2s.t. x1+x2+x3 =3 x2 +x4=1 x1, x2, x3, x40,x2=0,x1=0,x3=0,x4=0,O,A,B,C,D, ,x2=0,x1=0,x3=0,x4=0,O,A,B,C,第一次叠代：目标函数和基变量分别用非基变量表示： z=-x1-2x2选择x2进基 x3 =3-x1-x2 x

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

26、,x3增加x4增加2/1=2,min2/1=2/1当x2增加到2时x50离基,x3 =5- x1+4x2 x4 =4-2x1+3x2 x5 =2-3x1+ x2,x3增加x4增加x5增加,x2可以无限增加，可行域是开放区域，目标函数无界,x2=0,x1=0,x3=0,x4=0,O,A,B,C,第二次叠代：目标函数和基变量分别用非基变量表示： z=-2-x1+2x4选择x1进基 x3 =2-x1+x4 x2=1 -x4,单纯形法原理（3）第二次叠代,x2=0,x1=0,x3=0,x4=0,O,A,B,C,第三次叠代：目标函数和基变量分别用非基变量表示： z=-4+x3+x4 x1 =2-x3+x

27、4 x2=1 -x4非基变量在目标函数中的系数全部大于0，已获得最优解。,单纯形法原理（4）最优解的判定,x2=0,x1=0,x3=0,x4=0,O,A,B,C,单纯形法原理(5)叠代过程回顾,max z=x1+2x2s.t. x1+x23 x2 1 x1, x20,min z=-x1-2x2s.t. x1+x2+x3 =3 x2 +x4=1 x1, x2, x3, x40,引进松弛变量x3,x4,单纯形法原理(6)叠代过程回顾,x2=0,x1=0,x3=0,x4=0,O,A,B,C,(x1,x2,x3,x4)=(0,0,3,1), z=0,min z=-x1-2x2s.t. x1+x2+x3

28、 =3 x2 +x4=1 x1, x2, x3, x40,min 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,x2=0,x1=0,x3=0,x4=0,O,A,B,C,第二次叠代x1进基，x3离基,(x1,x2,x3,x4)=(0,1,2,0), z=-2,(x1,x2,x3,x4)=(2,1,0,0), z=-4,min z

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

30、0), z=-4,min z=-x1-2x2s.t.x1+x2+x3 =3 x2 +x4=1 x1, x2, x3, x40,min z=-x1-2x2s.t. x1+x2=3-x3 x2=1 -x4x1, x2, x3, x40,min z=-4+x3+x4s.t. x1=2-x3+x4 x2 =1 -x4x1, x2, x3, x40,根据目标函数中非基变量x3,x4的系数 +10,+10，x1=2,x2=1,x3=0,x4=0,z=-4为最优解，对应于B点,x2=0,x1=0,x3=0,x4=0,O,A,B,C,第一次叠代x2进基，x4离基,第二次叠代x1进基，x3离基,(x1,x2,x

31、3,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 将目标函数和基变量分别用非基变量表示。转STEP 2。STEP 2 如果目标函数中所有非基变量的系数全部为正数，则已经获得最优解。运算终止。否则，选取系数为负数并且绝对值最大的非基变量进基。转STEP 3。STEP 3 如果进基变量增加时，基变量都不减少，则可行域开放，目标

32、函数无界。运算终止。否则，随着进基变量的增加，最先下降到0的基变量离基。转STEP 1。,线性规划基本概念练习（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、这个线性规划的最优解位于（ ）。,ACE

33、F,BCDH,EGHI,CDGE,z=2,z=4,C,D,4,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,

34、EGHI,8、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,线性规划基本概念练习（3）,0,3,6,x1,x2,O,A,B,C,E,F,G,H,I,4,6,-2,D,4,x1=0,x2=0,x3=0,x4=0,x5=0,9、从O到D的单纯形迭代， 进基变量是（ ），离基变量是（ ）。 从D到C的单纯形迭代，进基变量是（ ），离

35、基变量是（ ）。 从C到E的单纯形迭代，进基变量是（ ），离基变量是（ ）。,x2,x4,x1,x3,x4,x5,单纯形表,min z=-x1-2x2s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40,max z=x1+2x2s.t. x1+x23 x2 1 x1, x2 0,z+x1+2x2 =0 x1+x2+ x3 =3 x2 +x4=1,z=-x1-2x2x3 =3-x1-x2 x4=1 -x2,z=-2-x1+2x4 x3=2-x1+x4x2 =1 -x4,z=-4+x3+x4x1 =2-x3+x4 x2=1 -x4,单纯形法原理,单纯形表,用单纯形表

36、求解线性规划问题,写成标准化形式,写出单纯形表,25/1,36/2,0,-3,-2,0,-2,-72,0,1,1/2,0,1,-1/2,7/1/2,1,x5,1/2,1,0,1/2,18/1/2,0,7,18,1,1/2,1/2,x2,0,x6离基，为主元，进行行变换，将变为1，4和1变为0,x2进基，计算RHS和x2在约束条件中的系数的比值，比值小的基变量离基,x5离基，,x1进基，,0,-4,-2,-2,-1,-86,0,1,1,0,2,-1,1,x1,0,1,-1,1,0,14,11,0,1,0,x2,0,得到最优解，最优解为：,（x1，x2，x3，x4，x5，x6）=（14，11，0，

37、0，0，0）min z=-86，max z=86,标准化。引进松弛变量x4，x5,单纯形表求解线性规划的例子,写出单纯形表,写成线性规划形式min z+3x1+2x2+x3 =0s.t. 2x1+x2+2x3+x4 =24 -x1+2x2-x3 +x5=18 x1, x2, x3, x4, x50,将非基变量移到右边min z= -3x1-2x2-x3s.t. x4 =24-2x1-x2-2x3 x5=18 +x1-2x2+x3 x1, x2, x3, x4, x50,根据目标函数系数，选择x1进基；根据约束条件，确定x4离基。,x1进基，x4离基。第二行除以2,行变换。将主元变成1，主元所在

38、列的其他元素变为0,12/1/2=24,30/5/2=12,行变换。将主元变成1，主元所在列的其他元素变为0,写成线性规划形式min z+1/2x2-2x3-3/2x4 =-36s.t. x1+1/2x2+x3+1/2x4 =12 5/2x2 +1/2x4+x5=30 x1, x2, x3, x4, x50,将非基变量移到右边min z=-36-1/2x2+2x3+3/2x4s.t. x1 =12-1/2x2-x3-1/2x4 x5=30-5/2x2 -1/2x4 x1, x2, x3, x4, x50,根据目标函数系数，选择x2进基；根据约束条件，确定x5离基。,x2进基，x5离基。第三行除

39、以5,行变换，将主元变为1，主元所在列其他元素变为0变为,检验数全部为负数或0，获得最优解。最优解为：（x1，x2，x3，x4，x5）（6，12，0，0，0）min z=-42，max z=42,写成线性规划形式min z-2x3-8/5x4-1/5x5 =-42s.t. x1 +x3+2/5x4-1/5x5 =6 x2 +1/5x4+2/5x5=12 x1, x2, x3, x4, x50,将非基变量移到右边min z=-42+2x3+8/5x4+1/5x5s.t. x1 =6-x3-2/5x4+1/5x5 x2=12 -1/5x4 -2/5x5 x1, x2, x3, x4, x50,单纯

40、形表的结构,基变量,基变量,基变量在目标函数中的系数等于0，基变量在约束条件中的系数是一个单位矩阵。,Step 0 获得一个初始的单纯形表，确定基变量和非基变量Step 1 检查基变量在目标函数中的系数是否等于0，在约束条件中的系数是否是一个单位矩阵。Step 2 如果表中非基变量在目标函数中的系数全为负数，则已得到最优解。停止。否则选择系数为正数且绝对值最大的变量进基，转step 3。Step 3 如果进基变量在约束条件中的系数全为负数或0，则可行域开放，目标函数无界。停止。否则选取右边常数和正的系数的最小比值，对应的基变量离基，转step 4。Step 4 确定进基变量的列和离基变量的行交

41、叉的元素为“主元”，对单纯形表进行行变换，使主元变为1，主元所在列的其他元素变为0。将离基的基变量的位置用进基的非基变量代替。转Step 2。,单纯形表的算法描述,初始基础可行解两阶段法,约束条件全部是，右边常数全部是非负的线性规划问题，引进松弛变量后，可以直接得到一个初始基础可行解。在这个解中，原来的变量为非基变量，松弛变量为基变量。例如：,min z=x1+x2-2x3s.t. 3x1+2x2- x335 x1- x2+2x328 x1, x2, x30,min z=x1+x2-2x3s.t. 3x1+2x2- x3+x4 =35 x1- x2+2x3 +x5=28 x1, x2, x3,

42、 x4, x50,x1=x2=x30为非基变量，x4=35，x5=28为基变量，得到初始的基础可行解。,引进松弛变量,约束条件中有约束，右边常数全部是非负的线性规划问题，引进松弛变量（Slack Variables）后，无法直接得到一个初始基础可行解。例如：,min z=x1+x2s.t. 3x1+2x235 x1- x228 x1, x20,min z=x1+x2s.t. 3x1+2x2 -x3 =35 x1- x2 -x4=28 (A) x1, x2, x3, x40,x1=x20为非基变量，x3=-35，x4=-28为基变量，不是可行解。为了得到(A)的基础可行解，在(A)的约束条件中再

43、引进两个变量x5，x60，这两个变量称为人工变量（Artificial Variables）。,min z=x1+x2s.t. 3x1+2x2 -x3 +x5 =35 x1- x2 -x4 +x6=28 (B) x1, x2, x3, x4, x5, x60,（B）有一个初始的基础可行解： (x1, x2, x3, x4, x5, x6) = (0, 0, 0, 0, 35, 28)，但它不是（A）的可行解。只有当x5=x6=0时，（B）的可行解才同时也是（A）的可行解。这样的解中x5，x6一定是非基变量。因此，可以这样来求得（A）的一个初始基础可行解：从（B）以人工变量x5，x6为基变量的初

44、始基础可行解出发，用单纯形法对（B）进行进基离基变换，如果x5，x6都离基，成为非基变量，则（B）的这个基础可行解就是（A）的一个可行解。为了迫使人工变量尽快离基，构造一个新的极小化目标函数，这个目标函数等于所有人工变量之和。,min z=x1+x2s.t. 3x1+2x2 -x3 =35 x1- x2 -x4=28 (A) x1, x2, x3, x40,min z=x1+x2s.t. 3x1+2x2 -x3 +x5 =35 x1- x2 -x4 +x6=28 (B) x1, x2, x3, x4, x5, x60,min z=x5+x6s.t. 3x1+2x2 -x3 +x5 =35 x1

45、- x2 -x4 +x6=28 x1, x2, x3, x4, x5, x60,min z=x1+x2s.t. 3x1+2x2 -x3 =35 x1- x2 -x4=28 x1, x2, x3, x40,求解辅助问题，得到辅助问题的最优解,引进人工变量x5，x6，构造辅助问题，辅助问题的目标函数为所有人工变量之和,min z=0?,人工变量不能离基，原问题没有可行解。,把辅助问题的最优解作为原问题的初始基础可行解,用单纯形法求解原问题，得到原问题的最优解,否,是,两阶段法的算法流程图,两阶段法的算法的例子,min z=x1-2x2s.t. x1+x22 -x1+x21 x23 x1, x20,

46、引进松弛变量x3，x4，x5min z=x1-2x2s.t. x1+x2-x3 =2 -x1+x2 -x4 =1 x2 +x5 =3 x1, x2, x3, x4, x50,0,1,2,1,2,3,x1,x2,x3=0,x4=0,x5=0,x2=0,x1=0,引进人工变量x6，x7，构造辅助问题min z=x6+x7s.t. x1+x2-x3 +x6 =2 -x1+x2 -x4 +x7=1 x2 +x5 =3 x1, x2, x3, x4, x5, x6, x70,写出辅助问题的系数矩阵（不是单纯形表！）,行变换，消去基变量x5，x6，x7在目标函数中的系数,x2进基，x7离基，确定主元，进行

47、行变换,x1进基，x6离基，确定主元，进行行变换,已获得第一阶段最优解。z=0，人工变量x6，x7都已离基。去掉人工变量x6，x7，换入原问题的目标函数min z=x1-2x2，列出第二阶段系数矩阵。,消去基变量x1，x2，x5在目标函数中的系数,x4进基，x1离基，确定主元，进行行变换,x3进基，x5离基，确定主元，进行行变换,得到原问题 min z=x1-2x2 s.t. x1+x22 -x1+x21 x23 x1, x20的最优解(x1, x2, x3, x4, x5)=(0, 3, 1, 2, 0)，min z=-6,O,A,B,C,D,0,1,2,1,2,3,x1,x2,x3=0,x

48、4=0,x5=0,x2=0,x1=0,两阶段法叠代的路线如下图。前两次叠代OA，AB是第一阶段辅助问题的叠代；BC，CD是第二阶段的叠代。,运用两阶段法，就可以求解任何形式的线性规划问题，可以判断线性规划问题是否有可行解，如果有可行解，可以进一步求得最优解或者判断目标函数无界。,两阶段法的算法描述,STEP 0 引进松弛变量，成为标准形式。STEP 1 如果约束条件的系数矩阵中没有一个单位矩阵，引进人工变量，构造辅助问题。STEP 2 求解辅助问题。得到辅助问题的最优解。如果辅助问题的最优解中人工变量都离基成为非基变量，即辅助问题最优解的目标函数值min z=0，则辅助问题的最优解就是原问题的一个初始基础可行解。如果辅助问题最优解中仍有人工变量没有离基，即辅助问题最优解的目标函数值min z0，则原问题没有可行解。STEP 4 转到第二阶段，从原问题的初始基础可行解出发，求出原问题的最优解。,