及求解线性规划模型的应用运输问题指派问题排队问题课件.ppt

1、l管理运筹学管理科学Operations Research Management science教学日历l概述l线性规划模型及求解l线性规划模型的应用l运输问题l指派问题l排队问题某工厂拥有有3个车间生产门、窗两种产品。每件产品在生产中需要占有的车间加工时数以及每件产品可以获得的利润以及3个车间每周可供加工时数如下表所示：求使得总利润最大的生产计划。1.确定决策变量：设门、窗2种产品每周的产量分别为x1，x22.确定限制条件： 车间1时间限制： 1x1+0 x24 车间2时间限制： 0 x1+2x212 车间3时间限制： 3x1+2x218 决策变量限制： x1, x203.确定决策目标：设总

2、利润为z ，即： Max z =300 x1+500 x2目标函数约束条件变量非负约束张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。门课个老师教第第门课个老师不教第第ji1ji0 xij设：max z=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+ 83x31+90 x32+74x33+65x34+93x41+61x42+83x43+75x44s.t. x11+x12+x

3、13+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最优解为：x14=1，x23=1，x32=1，x41=1，max z=336即张老师教化学，王老师教语文，李老师教数学，赵老师教语文。四门课的总分可以达到336分。线性规划问题n生产计划问题产品组合优化问题n配料问题n背包问题n运输问题n指派问题1.

4、生产计划问题1（Production Planning）某工厂拥有原料A、B以及生产设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：求使得总利润最大的生产计划。1.确定决策变量：设甲乙丙三种产品的产量分别为x1，x2，x32.确定限制条件： 台时限制： 1x1+2x2+3x33000 限制： 6x1+5x2+4x34000 限制： 0 x1+7x2+8x32500 决策变量限制： x1, x2, x303.确定决策目标：设总利润为z ，即： Max z =500 x1+800 x2+1000 x3设三种产品的产量

5、分别为x1，x2，x3，总利润为z，线性规划模型为：max z=500 x1+800 x2+1000 x3s.t. 1x1+2x2+3x33000 6x1+5x2+4x34000 0 x1+7x2+8x32500 x1, x2, x30目标函数约束条件变量非负约束这个问题的最优解为：x1=458.3件，x2=0单位，x3=312.5单位最大利润为：z=541666.7元。问题：三个约束条件可以改为等式吗？1. 生产计划问题2（Production Planning）某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三

6、种设备可利用的时数如下表所示：求使得总利润最大的生产计划。设四种产品的产量分别为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=12737.06元。问题：三个约束条件可以改为

7、等式吗？2. 配料问题（Material Blending）某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（），这四种原料的单价以及新的不锈钢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的含

8、量下限约束 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.84，x4=0（公斤）, 最低成本为z=9549.87元。问题：如果某一种成分的含量既有下限，又有上限怎么办？3. 背包问题（Knapsack Problem）一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：求背包中装入每种物品各多少

9、件，使背包中物品总价值最高。设三种物品的件数各为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元4. 运输问题（Transportation）某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：求总运费最低的运输方案。A1A2B3B2B135吨25吨1

10、0吨30吨20吨235478设从两个供应地到三个需求地的运量（吨）如下表：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 这个问题的最优解表示如下：最小总运费为：z=330+55+410+815=275元A1A2B3B2B135吨25吨10吨30吨20吨23547830吨5吨10吨15吨5. 指派问题（A

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

12、的平均总成绩最高。门课个老师教第第门课个老师不教第第ji1ji0 xij设：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+x31+x41=1 (5) x12+x22+x32+x42=1 (6) x13+x23+x33+x43=1 (7)

13、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 (, Free)线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题

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

15、2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0 mn2m1mn22221n11211aaaaaaaaaAm21bbbbn21ccccn21xxxX线性规划模型用矩阵和向量表示（续）nn2211n21n21TxcxcxcxxxcccXCznmn22m11mnn2222121nn1212111n21mn2m1mn22221n11211xaxaxaxaxaxaxaxaxaxxxaaaaaaaaaAX因此，线性规划模型可以写成如下矩阵和向量的形式0. .min(max)XbAXtsXCzT线性规划模型总结线性规划模型的结构n目标函数 ：max，minn约束条件：

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

17、问题最优解的目标函数值相差一个负号。极大化目标函数问题转化为极小化目标函数例如，对于以下两个线性规划问题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-4x3+x4=5

18、由此可以知道，松弛变量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+2x2-

19、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。代入模型，消

20、去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,x50max z=x1+2x2-3x3s.t. 2x1+3x2-4x353x1-2x2+5x38x10, x20, x30min z=-x1-2x2+3x3s.t. 2x1+3x2-4x3+x

21、4 =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的的标准化简单线性规划问题的图解法某小家电制造企业提出两种新型的小家电D3210与H4211，两种产品均要经过5道工序，两件产品在生产中各工序的时间、每件产品可以获得的利润以及5道工序可利用的时数如下表所示：求使得总利润最大的生产计划。设两种产品的产量分别为x1，x2，总利润为z，线性规划模型为：max z=7

22、0 x1+110 x2s.t. 1.0 x1+1.2x240 0.7x1+0.8x234 0.5x1+0.5x227 0.2x1+0.3x215 1.5x1+1.4x254 x1, x20目标函数约束条件变量非负约束可行域目标函数等值线最优解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、可行域开放 唯一最优解4、可行域

23、开放 多个最优解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)不满

24、足(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, x

25、4=-2x2=0 x1=0OABCD线性规划的基本概念基、基础解、基础可行解、极点 标准化的线性规划问题，有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

26、 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=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可行域几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基

27、础解可行域的极点基础可行解目标函数等值：一组平行线 目标函数值等于一个常数的解可行域极点的数量如果线性规划有50个变量，20个约束条件，全部是等号约束。按照以上的算法，每计算一个基础解，要从50个变量中选择30个非基变量等于0，剩下20个变量，如果相应的2020行列式不等于0，则通过计算一个20 20的线性方程组得到基变量。要穷尽所有的基础解，最多可能要计算的线性方程组的个数为1320501074302050C.!假设每计算一个2020线性组需要1秒钟，计算以上所有方程组需要的时间为（年）61310513652436001074.由于极点的个数随着约束条件的增加而很快增加，用搜索所有极点来求出线性规划最优解，实际上并不是一个可行的方法。单纯形法原理示意图极点4，最优解初始极点1极点2极点3其实，不必搜索可行域的每一个极点，只要从一个极点出发，沿着使目标函数改善的方向，到达下一个相邻的极点。如果相邻的所有极点都不能改善目标函数，这个极点就是最优极点。用这样的搜索策略，可以大大减少搜索极点的个数。按照这样的搜索策略建立的算法，叫做单纯形法。单纯形法可以有效地减少搜索极点的个数。目标函数改善目标函数改善目标函数改善