管理运筹学第一章改

1、线性规划问题,生产计划问题 配料问题 背包问题 运输问题,1. 生产计划问题（Production Planning）,某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,求使得总利润最大的生产计划。,设四种产品的产量分别为x1，x2，x3，x4，总利润为z，线性规划模型为：,max z=5.24x1+7.30 x2+8.34x3+4.18x4 s.t. 1.5x1+1.0 x2+2.4x3+1.0 x42000 1.0 x1+5.0 x2+1.0 x3+3.5x48000 1.5x1

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

3、使得总成本最低的配料方案。,min z=115x1+97x2+82x3+76x4 s.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,设四种原料分别选取x1，x2，x3，x4公斤，总成本为z。,这个问题的最优解为：x1=26.58, x2=31.57, x3=41

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

5、=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+8x23 s.t. x11+x12+x13 =35 供应地A1 x21+x22+x23 =25 供应地A2 x11 +x21 =10 需求地B1 x12 +x22 =30 需求

6、地B2 x13 +x23 =20 需求地B3 x11, x12, x13, x21, x22, x230,这个问题的最优解表示如下：,最小总运费为：z=330+55+410+815=275元,30吨,5吨,10吨,15吨,线性规划的标准形式,目标函数为极大化，约束条件全部为等号约束，所有变量全部是非负的，这样的线性规划模型称为标准形式 MAX z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0,线性规划模型用矩阵和向量表示,MAX z=c1x1+c

7、2x2+cnxn s.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0,线性规划模型用矩阵和向量表示（续）,因此，线性规划模型可以写成如下矩阵和向量的形式,线性规划模型总结,线性规划模型的结构 目标函数 ：max，min 约束条件：,=, 变量符号：0, 0, Free 线性规划的标准形式 目标函数：max 约束条件：= 变量符号：0,线性规划问题的标准化,极小化目标函数转化为极大化 小于等于约束条件转化为等号约束 大于等于约束条件转化为等号约束 变量没有符号限制（Free）的标准化

8、 变量小于等于0的标准化,min z=2x1-3x2+x3 令 z=-z，z=-2x1+3x2-x3 新的目标函数 max z=-2x1+3x2-x3 取得极小化的最优解时，这个最优解同时使原目标函数值取得最大化的最优解。但两个问题最优解的目标函数值相差一个负号。,极大化目标函数问题转化为极小化目标函数,例如，对于以下两个线性规划问题,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)的最小化的目标函数值为min z=7，(B)的

9、最小化的目标函数值为max z=-7,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,小于等于约束条件转化为等号约束,将不等式约束变为等式约束。例如： 2x1+3x2-4x

10、35 3x1-2x2+5x38 在两个约束的左边分别减去松弛变量x4，x50 2x1+3x2-4x3-x4 =5 3x1-2x2+5x3 -x5=8,大于等于约束条件转化为等号约束,没有符号限制的变量，用两个非负变量之差表示。例如： min z=x1+2x2-3x3 s.t. 2x1+3x2-4x35 3x1-2x2+5x38 x10, x2:free, x30 先将目标函数转化为极小化，并在约束中引进松弛变量，把不等式约束变为等式。 Max z=-x1-2x2+3x3 s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10, x2:free, x3, x4,

11、 x50,变量没有符号限制(Free)的标准化,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. 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+3x3 s.t. 2x1+3x2-3x”2-4x3+x4

12、 =5 3x1-2x2+2x”2+5x3 -x5=8 x1, x2, x”2, x3, x4,x50,min z=x1+2x2-3x3 s.t. 2x1+3x2-4x35 3x1-2x2+5x38 x10, x20, x30 max 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,变量小于等于

13、0的的标准化,线性规划的图解,max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域,目标函数等值线,最优解,z=6,z=3,z=9,z=12,问题：1、线性规划的最优解是否可能位于可行域的内部？ 2、线性规划的最优解是否可能位于可行域的边界上？,可行域的性质,线性规划的可行域是凸集 线性规划如果有最优解，最优解至少在可行域的一个极点上,凸集,凸集,不是凸集,线性规划可行域和最优解的几种情况,1、可行域封闭 唯一最优解,2、可行域封闭 多个最优解,3、可行域开放 唯一最优解,4、可行域开放 多个最优解,5、可行域开放 目标函数无界,6、无可行解,解的可

14、行性和松弛变量符号的关系,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 结论：如果一个解满足一个约束条件，相应的松弛变量大于等于0。如果一个解不满足一个约

15、束条件，相应的松弛变量小于0。,x3=0,x4=0,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, 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个约束。 令

16、其中n-m个变量等于零，如果剩下的m个变量的系数矩阵的行列式不等于0，这个mm的矩阵称为线性规划的一个基。等于0的n-m个变量称为非基变量，m个变量称为基变量。 求解mm的线性方程组，得到基变量的一组解，连同等于0的非基变量这n个变量的值称为线性规划的一个基础解。 如果一个基础解中的所有变量都是非负的，这个基础解称为基础可行解。 线性规划的基础可行解就是可行域的极点。,线性规划的基本概念基、基础解、基础可行解、极点,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,

17、 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 是基础解，但不是可行解,O,A,B,x3=0,x4=0,x2=0,x1=0,C,D,可行域,几何概念,代数概念,约束直线,满足一个等式约束的解,约束半平面,满足一个不等式约束的解,约束半平面的交集：凸多边形,满足一组不等式约束的解,约束直线的交点,基础解,可行域的极点,基础可行解,目标函数等值： 一组平行线,目标函数值

18、等于一个常数的解,通过搜索所有基础可行解求出最优解,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=20,基变量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） 是基础解，但不是可行解，不

19、是一个极点。,基变量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,基础解为 （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、

20、x5、x6,基础解为 （x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10） 是基础解但不是可行解。,可行域极点的数量,如果线性规划有50个变量，20个约束条件，全部是等号约束。按照以上的算法，每计算一个基础解，要从50个变量中选择30个非基变量等于0，剩下20个变量，如果相应的2020行列式不等于0，则通过计算一个20 20的线性方程组得到基变量。要穷尽所有的基础解，最多可能要计算的线性方程组的个数为,假设每计算一个2020线性组需要1秒钟，计算以上所有方程组需要的时间为,由于极点的个数随着约束条件的增加而很快增加，用搜索所有极点来求出线性规划最优解，实际上并不是一

21、个可行的方法。,单纯形法原理示意图,极点4，最优解,初始极点1,极点2,极点3,其实，不必搜索可行域的每一个极点，只要从一个极点出发，沿着使目标函数改善的方向，到达下一个相邻的极点。如果相邻的所有极点都不能改善目标函数，这个极点就是最优极点。用这样的搜索策略，可以大大减少搜索极点的个数。 按照这样的搜索策略建立的算法，叫做单纯形法。 单纯形法可以有效地减少搜索极点的个数。,目标函数改善,目标函数改善,目标函数改善, , ,单纯形法原理（1）松弛变量的表示,max z=x1+2x2 s.t. x1+x23 x2 1 x1, x20,max z=x1+2x2 s.t. x1+x2+x3 =3 x2

22、 +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 x4=1 -x2,单纯形法原理(2)第一次叠代,确定离基变量的进一步讨论,设非基变量为x1、x2，基变量为x3、x4、x5，进基变量为x2,x3 =5- x1-4x2 x4 =4-2x1-3x2 x5 =2-3x1- x2,5/4=1.25 4/3=1.33 2/1=2,min5/4,4/3,2/1=5/4 当x2增加到

23、1.25时 x30离基,x3 =5- x1+4x2 x4 =4-2x1-3x2 x5 =2-3x1- x2,x3增加 4/3=1.33 2/1=2,min4/3,2/1=4/3 当x2增加到1.33时 x40离基,x3 =5- x1+4x2 x4 =4-2x1+3x2 x5 =2-3x1- x2,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

24、,第二次叠代： 目标函数和基变量分别用非基变量表示： z=2+x1+x4 选择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+x4 x2=1 -x4 非基变量在目标函数中的系数全部大于0，已获得最优解。,单纯形法原理（4）最优解的判定,x2=0,x1=0,x3=0,x4=0,O,A,B,C,单纯形法原理(5)叠代过程回顾,max z=x1+2x2 s.t. x1+x23 x2 1 x1, x20,min z=-x1-

25、2x2 s.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-2x2 s.t. x1+x2+x3 =3 x2 +x4=1 x1, x2, x3, x40,min z=-x1-2x2 s.t. x3 =3-x1-x2 x4=1 -x2 x1, x2, x3, x40,根据目标函数中非基变量x1,x2的系数 -1,-2，确定x2进基。 根据 min3/1,1/1=1, 确定x4离

26、基。对应于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=-x1-2x2 s.t.x1+x2+x3 =3 x2 +x4=1 x1, x2, x3, x40,min z=-x1-2x2 s.t. x2+x3=3-x1 x2 =1 -x4 x1, x2, x3, x40,单纯形法原理(7)叠代过程回顾,min z=-2-x1+

27、2x4 s.t. x3=2-x1+x4 x2 =1 -x4 x1, 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,0), z=-4,min z=-x1-2x2 s.t.x1+x2+x3 =3 x2 +x4=1 x1, x2, x3, x40,min z=-x1-2x2 s.t. x1+x2=3-x3 x2=1 -x4 x1, x2, x3, x40,min z=-4

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