线性规划及单纯形法课件.ppt

《线性规划及单纯形法课件.ppt》由会员分享，可在线阅读，更多相关《线性规划及单纯形法课件.ppt（62页珍藏版）》请在三一办公上搜索。

1、1,1 线性规划问题及其数学模型,e.g. 1 资源的合理利用问题,问：如何安排生产计划，使工厂获总利润最大？,表 1 产品 资源 甲 乙 库存量 A 1 3 60 B 1 1 40 单件利润 15 25,某工厂在下一个生产周期内生产甲、乙两种产品，要消耗A、B两种资源，已知每件产品对这两种资源的消耗，这两种资源的现有数量和每件产品可获得的利润如表 1。,2,第二章 线性规划及单纯形法,max z = 15x1 +25x2s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0,解 ：,设 x1，x2 为下一个生产周期产品甲和乙的产量；,约束条件：,Subject to,x1 +

2、 3x2 60,x1 + x2 40,x1，x2 0,目标函数：,z = 15 x1 +25 x2,表 1 产品 资源 甲 乙 库存量 A 1 3 60 B 1 1 40 单件利润 15 25,决策变量,3,1 线性规划问题及其数学模型,e.g. 2 营养问题,假定在市场上可买到 B1,B2,Bn n 种食品，第 i 种食品的单价是 ci , 另外有 m 种营养 A1,A2,Am。设 Bj内含有 Ai 种营养数量为 aij (i=1m,j=1n)，又知人们每天对 Ai 营养的最少需要量为 bi。见表2：,表 2 食品 最少 营养 B1 B2 Bn 需要量 A1 a11 a12 a1n b1 A

3、2 a21 a22 a2n b2 Am am1 am2 amn bm 单 价 c1 c2 cn,试在满足营养要求的前提下，确定食品的购买量，使食品的总价格最低。,4,第二章 线性规划及单纯形法,表 2 食品 最少 营养 B1 B2 Bn 需要量 A1 a11 a12 a1n b1 A2 a21 a22 a2n b2 Am am1 am2 amn bm 单 价 c1 c2 cn,解 ：,设 xj 为购买食品 Bj 的数量 ( j=1,2,n ),（i = 1,2,m）,xj0 （j = 1,2,n）,0 xj lj,5,1 线性规划问题及其数学模型,三个基本要素：,Note：,1、善于抓住关键因

4、素，忽略对系统影响不大的因素；,2、可以把一个大系统合理地分解成 n 个子系统处理。,1、决策变量 xj0,2、约束条件 一组决策变量的线性等式或不等式,3、目标函数 决策变量的线性函数,6,第二章 线性规划及单纯形法,max（min）z = c1x1 + c2x2 + + cnxns.t. a11x1 + a12x2 + + a1nxn （或=，）b1 a21x1 + a22x2 + + a2nxn （或=，）b2 am1x1 + am2x2 + + amnxn （或=，）bm xj 0 （j = 1,2,n）,其中aij、bi、cj（i = 1,2,m；j = 1,2,n）为已知常数,7,

5、1 线性规划问题及其数学模型,线性规划问题的标准形式：,max z = c1x1 + c2x2 + + cnxns.t. a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn = bm xj 0 （j = 1,2,n） bi 0 （i = 1,2,m）,特点：,1、目标函数为极大化；,2、除决策变量的非负约束外，所有的约束条件都是等式，且右端常数均为非负；,3、所有决策变量均非负。,8,第二章 线性规划及单纯形法,如何转化为标准形式？,1、目标函数为求极小值，即为： 。,因为求 min

6、 z 等价于求 max (-z)，令 z = - z，即化为：,2、约束条件为不等式，,xn+1 0松弛变量,如何处理？,9,1 线性规划问题及其数学模型,、右端项bi 0时，只需将等式两端同乘（-1）则右端项必大于零,4、决策变量无非负约束,设 xj 没有非负约束，若 xj 0，可令 xj = - xj ，则 xj 0；,又若 xj 为自由变量，即 xj 可为任意实数，可令 xj = xj - xj，且 xj , xj 0,10,第二章 线性规划及单纯形法,e.g. 3,试将 LP 问题,min z = -x1+2x2-3x3 s.t. x1+x2+x3 7 x1-x2+x3 2 -3x1+

7、x2+2x3 = -5 x1,x2 0 化为标准形式。,解：,令 x3= x4 - x5 其中x4、x5 0；,对第一个约束条件加上松弛变量 x6 ；,对第二个约束条件减去松弛变量 x7 ；,对第三个约束条件两边乘以“-1” ；,令 z=-z 把求 min z 改为求 max z,max z= x1-2x2+3x4- 3x5 s.t. x1+x2+x4-x5+x6=7 x1-x2+x4-x5-x7=2 3x1-x2-2x4+2x5=5 x1,x2,x4,x5,x6,x70,11,1 线性规划问题及其数学模型,LP的几种表示形式：,12,2 线性规划问题的图解法,定义1 在LP 问题中，凡满足约

8、束条件(2)、(3)的 解 x = (x1,x2,xn)T 称为LP 问题的可行解， 所有可行解的集合称为可行解集（或可行域）。 记作 D= x | Ax = b ,x0 。,定义2 设LP问题的可行域为D，若存在x*D，使得 对任意的xD 都有c x*c x，则称x*为LP 问题 的最优解，相应的目标函数值称为最优值， 记作 z*=c x*。,13,2 线性规划问题的图解法,max z = 15x1 +25x2s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0,(40,0),(0,0),B,C,(30,10),O,L1,L2,Z=250,目标函数变形：,x2=-3/5 x

9、1+z/25,x2,x1,最优解： x1=30 x2 =10最优值：zmax=700,B点是使z达到最大的唯一可行点,14,第二章 线性规划及单纯形法,LP问题图解法的基本步骤：,1、在平面上建立直角坐标系；,2、图示约束条件，确定可行域和顶点坐标；,3、图示目标函数（等值线）和移动方向；,4、寻找最优解。,15,2 线性规划问题的图解法,max z =3x1 + 5.7x2 s.t. x1 + 1.9x2 3.8 x1 - 1.9x2 3.8 x1 + 1.9x2 11.4 x1 - 1.9x2 -3.8 x1 ，x2 0,x1,x2,o,x1 - 1.9 x2 = 3.8,x1 + 1.9

10、 x2= 3.8,x1 + 1.9 x2 = 11.4,（7.6,2）,D,0=3 x1 +5.7 x2,max Z,min Z,（3.8,4）,34.2 = 3 x1 +5.7 x2,可行域,x1 - 1.9 x2 = -3.8,(0,2),(3.8,0),绿色线段上的所有点都是最优解,即有无穷多最优解。Zman=34.2,16,第二章 线性规划及单纯形法,max z = 2x1 + 2x2 s.t. 2x1 x2 2 -x1 + 4x2 4 x1，x2 0,O,x1,x2,Note:可行域为无界区域，目标函数值可无限增大，即解无界。称为无最优解。,可行域为无界区域一定无最优解吗？,17,2

11、 线性规划问题的图解法,由以上两例分析可得如下重要结论：,1、LP 问题从解的角度可分为：, 有可行解, 无可行解,a.有唯一最优解b.有无穷多最优解c.无最优解,2、LP 问题若有最优解，必在可行域的某个顶点上取 到；若有两个顶点上同时取到，则这两点的连线上 任一点都是最优解。,18,2 线性规划问题的图解法,图解法优点：,直观、易掌握。有助于了解解的结构。,图解法缺点：,只能解决低维问题，对高维无能为力。,19,3 线性规划问题解的基本性质,讨论如下 LP 问题：,其中,系数矩阵,决策向量,假设 A 的秩为 m ,且只讨论 m n 的情形。,什么意思？为什么？,20,第二章 线性规划及单纯

12、形法,定义 3 在上述 LP 问题中，约束方程组（2）的系数矩阵 A 的任意一个 mm 阶的非奇异的子方阵 B （即 |B|0），称为 LP 问题的一个基阵或基。,称 pi (i=1,2,m) 为基向量;,xi (i=1,2,m) 为基变量；,xj (j= m+1,n) 为非基变量,j (j= m+1,n) 为非基向量;,记：,则 A = ( B, N ),21,3 线性规划问题解的基本性质,A = ( B, N ),xB= (x1,xm)T , xN =(xm+1,xn)T,则,代入约束方程（2），得,自由变量（独立变量）,令,称（4）为相应于基 B 的基本解,22,第二章 线性规划及单纯形

13、法,是可行解吗？,max z= x1-2x2+3x4- 3x5 s.t. x1+x2+x4-x5+x6=7 x1-x2+x4-x5-x7=2 3x1-x2-2x4+2x5=5 x1,x2,x4,x5,x6,x70,令 x1=x2=x4=0,如果 B-1b 0，则称（4）为相应于基 B 的基可行解，此时的基 B 称为可行基。,23,3 线性规划问题解的基本性质,基本解唯一吗？ 最多有多少？,称它是非退化的解；反之，如果有一个基变量也取零值，则称它是退化的解。一个LP问题，如果它的所有基可行解都是非退化的就称该是非退化的，否则就称它是退化的。,24,第二章 线性规划及单纯形法,LP 问题解的基本性

14、质,Ax=0,定理 2、定理 3 称为 LP 问题的基本定理,定理2 证明,向前,定理3 证明,LP 问题是一个组合优化问题,25,3 线性规划问题解的基本性质,定理 2 证明,设x = (x1, x2, xn)T 是LP 问题的一个可行解，如果 x = 0，则由定理 1知，它是LP 问题的一个基可行解，定理成立。,如果x0，不妨设 x 的前 k 个分量为非零分量。则有 x1p1 + x2p2 +xkpk = b，及 x10, x20, xk 0，,分两种情况讨论：,如果 p1, p2, pk 线性无关，即 x 的非零分量对应的列向量线性无关，则由定理1知，它是LP 的一个基本可行解，定理成立

15、。,(2) 如果p1,p2,pk线性相关，则必存在一组不全为零的数 1,2, ,k 使得,26,第二章 线性规划及单纯形法,假定有i0，,取,作,其中,由（6）式知，必有,即,又因为由（5）式知,故有，,，即,也是LP的两个可行解。,27,3 线性规划问题解的基本性质,再由 的取法知，在式 (7) 的诸式中，至少有一个等于零，于是所作的可行解 中，它的非零分量的个数至少比 x 的减少1，如果这些非零分量所对应的列向量线性无关，则 为基可行解，定理成立。,否则，可以从 出发，重复上述步骤，再构造一个新的可行解 ，使它的非零分量的个数继续减少。这样经过有限次重复之后，必可找到一个可行解使它的非零分

16、量对应的列向量线性无关，故可行解必为基可行解。证毕。,返回,28,3 线性规划问题解的基本性质,定理 3 证明,设,是 LP 的一个最优解。,如果 x* 是基本解，则定理成立；,如果 x* 不是基本解，则由定理2的证明过程可构造两个可行解,它的非零分量的个数比 x* 的减少，且有,，,又因为 x* 是最优解，故有,由式（8）和（9）知，必有,即x(1),x(2) 仍为最优解。,如果 x(1)或 x(2) 是基可行解，则定理成立。,否则，按定理2证明过程，可得基可行解 x(s)或x(s+1),使得,即得基可行解 x(s)或x(s+1)为最优解。,返回,29,第二章 线性规划及单纯形法,LP 问题

17、解的几何意义,定义 5 设集合 是 n 维欧氏空间中的一个点集，如果 及实数,则称 S 是一个凸集。,几何意义：如果集合中任意两点连线上的一切点都在 该集合中，则称该集合为凸集。,Note: 空集和单点集也是凸集。,30,3 线性规划问题解的基本性质,定义 6 设 则称,为点 的一个凸组合。,31,第二章 线性规划及单纯形法,定理 5 设 D 为 LP 问题的可行解集， ，则 x 是 D的极点的充分必要条件是 x 为 LP 问题的基可行解。,prove,（此时，该LP 问题有无穷多最优解）,32,3 线性规划问题解的基本性质,Note:,1、如何判断 LP 问题有最优解；,2、计算复杂性问题。

18、,设有一个50个变量、20个约束等式的 LP 问题，则 最多可能有 个基。,即约150万年,33,4 单纯形法的基本原理,单纯形法（Simplex Method）是1947年由 G.B.Dantzig 提出，是解 LP 问题最有效的算法之一，且已成为整数规划和非线性规划某些算法的基础。,基本思路： 基于 LP 问题的标准形式，先设法找到一个基可行解，判断它是否是最优解，如果是则停止计算；否则，则转换到相邻的目标函数值不减的一个基可行解.（两个基可行解相邻是指它们之间仅有一个基变量不相同）。,34,第二章 线性规划及单纯形法,单纯形法引例,首先，化原问题为标准形式：,x3, x4 是基变量.,基

19、变量用非基变量表示：,x3 = 60 -x1 - 3x2 x4 = 40 -x1 - x2,代入目标函数：,z =15 x1+25 x2,令非基变量 x1= x2=0,z=0 基可行解 x(0)=(0,0,60,40)T,是最优解吗？,max z = 15x1 +25x2s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0,max z = 15x1 + 25x2 + 0 x3 + 0 x4 s.t. x1 + 3x2 + x3 = 60 x1 + x2 + x4=40 x1，x2 , x3, x4 0,35,4 单纯形法的基本原理,z =15 x1+25 x2x3 = 60

20、-x1 - 3x2 x4 = 40 -x1 - x2,因为x2 的系数大，所以x2 换入基变量。,x3 = 60 - 3x2 0 x4 = 40 - x2 0,谁换出？,如果 x4 换出，则x2 = 40， x3 = -60，不可行。,如果是“+”会怎样？,如果 x3 换出，则x2 = 20， x4 = 20。,最小比值法则,所以 x3 换出。,基变量用非基变量表示：,代入目标函数：,z =500+20/3 x1- 25/3 x3,令非基变量 x1= x3=0,z=500 基可行解 x(1)=(0,20,0,20)T,大于零！,36,第二章 线性规划及单纯形法,因为x1 的系数大，所以x1 换

21、入基变量。,所以 x4 换出。,基变量用非基变量表示：,代入目标函数：,z =700 5 x3 10 x4,令非基变量 x3= x4=0,z=700 基可行解 x(2)=(30,10,0,0)T,因为非基变量的系数都小于零， 所以 x(2)=(30,10,0,0)T 是最优解 zmax=700,37,4 单纯形法的基本原理,目标函数用非基变量表示时，非基变量的系数 称为检验数,(40,0),(0,0),(0,20),A,B,C,(30,10),O,L1,L2,Z=250,x2,x1,x(0)=(0,0,60,40)T z=0,x(1)=(0,20,0,20)T z=500,x(2)=(30,1

22、0,0,0)T z=700,38,第二章 线性规划及单纯形法,单纯形法的基本原理,称(1a)(2a)(3a)为LP问题对应于基 B 的典则形式（典式）.,Ax = b,基变量用非基变量表示：,代入目标函数：,39,4 单纯形法的基本原理,如果记,则典式(1a)(2a)(3a) 可写成,40,第二章 线性规划及单纯形法,定理 7 在 LP 问题 的典式 (1b) (3b)中，如果有,则对应于基 B 的基可行解,是 LP 问题的最优解，记为,相应的目标函数最优值 z*=z(0),此时，基B称为最优基,41,4 单纯形法的基本原理,定理 8 在 LP 问题 的典式 (1b) (3b)中，,是对应于基

23、 B 的一个基可行解，如果满足下列条件：,(1)有某个非基变量 xk 的检验数 k 0 (m+1 k n);,(2)aik(i=1,2,m) 不全小于或等于零，即至少有一个 aik0 (i=1,2,m) ;,(3) 0 (i=1,2,m) ,即x(0) 为非退化的基可行解。,则从 x(0)出发，一定能找到一个新的基可行解,42,第二章 线性规划及单纯形法,定理 9 在 LP 问题的典式 (1b) (3b)中，如果检验数满足最优准则 j 0 ( j = m+1 ,n )，且其中有一个 k = 0 ( m+1 k n )，则该 LP 问题有无穷多个最优解。,这在应用中很有价值,则该 LP 问题解无

24、界（无最优解）。,43,5 单纯形法的计算步骤,单纯形表,44,第二章 线性规划及单纯形法,如何得到单纯形表？,B-1b,- cB B-1b,检验数,B N,cB cN,I B-1N,0 cN-cB B-1N,45,5 单纯形法的计算步骤,e.g.4 列出如下 LP 问题的初始单纯形表。,max z = 4x1 + 3x2 + 2x3 + 5x4 s.t. x1 + 3x2 + x3 + 2x4 = 5 4x1+ 2x2+3x3 +7x4 = 17 x1，x2 ，x3 ，x4 0,不妨已知x3 、x4 为可行基变量,1,-7,0,1,2,6,-31,0,5,-2,-1,17,1,0,1,1,4

25、,0,-12,x(0)=(0,0,1,2 )T,z0 = 12,46,第二章 线性规划及单纯形法,单纯形法求解 LP 问题的计算步骤：,Step 1 找出初始可行基，列初始单纯形表,确定初始基可行解；,Step 2 检验各非基变量 xj 的检验数 j , 如果所有 的 j 0（j = 1,2, n），则已求得最优解，停 止计算。否则转入下一步；,Step 3 在所有的 j 0 中，如果有某个k 0，所对 应的 xk 的系数列向量pk0（即 aik0，i =1,2, m），则此问题解无界，停止计算。否则转入下一 步;,47,5 单纯形法的计算步骤,Step 4 根据 ,确定 xk为换入基变量，又

26、根据最小比值法则计算:确定xr为换出基变量。转入下一步;,Step 5 以 为主元进行换基变换，用初等行变换将 xk 所对应的列向量变换成单位列向量，即,同时将检验数行中的第k个元素也变换为零，得到新的单纯形表。返回Step 2 。,48,第二章 线性规划及单纯形法,max z = 15x1 +25x2s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0,max z = 15x1 +25x2+ 0 x3 + 0 x4s.t. x1 + 3x2 + x3 = 60 x1 + x2 + + x4 = 40 x1，x2 ， x3 ， x4 0,0,0,x2,1/3,-500,x1,

27、0,-700,1/2,检验数都小于等于零,x(2)为最优解 zmax = 700,60/3,40/1,25,3,1/3,1,20,0,0,-1/3,1,20,20/3,-25/3,0,20/1/3,20/2/3,15,2/3,2/3,1,0,-1/2,3/2,30,0,-1/2,10,0,-5,-10,49,5 单纯形法的计算步骤,思考：,在单纯形法中根据,确定 xk为进基变量，是否在这次变换中，使目标函数值提高最大？,如果不是，应选择哪个变量进基，保证这次变换使得目标函数值提高最大？,目标函数值能提高多少？,50,6 单纯形法的进一步讨论,一、初始可行基的求法,max z = c1x1 +

28、c2x2 + cnxn (1c) s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 . (2c) am1x1 + am2x2 + amnxn = bm xj0 （j = 1,2, n） (3c),a11x1 + a12x2 + a1nxn + xn+1 = b1 a21x1 + a22x2 + a2nxn + xn+2 = b2 am1x1 + am2x2 + amnxn + xn+m = bm xj0 （j = 1,2, n, n+1, n+m）,人工变量,1、试算法,人造基本解： x0 = (0,0,0,b1,bm)T,2

29、、人工变 量法,51,6 单纯形法的进一步讨论,(1)大 M 法,惩罚法,max w = c1x1 + c2x2 + cnxn M ( xn+1 +xn+m ) s.t. a11x1 + a12x2 + a1nxn + xn+1 = b1 a21x1 + a22x2 + a2nxn + xn+2 = b2 am1x1 + am2x2 + amnxn + xn+m = bm xj0 （j = 1,2, n, n+1, n+m）,M 是一个充分大的正数,结论：,设,为上述问题的最优解,则,为原问题的最优解，这时的目标函数值为最优值；,则原问题无可行解。,不全为零，,52,第二章 线性规划及单纯形法

30、,e.g.5,用大 M 法求解,max z = 3x1 - x2 x3s.t. x1 - 2x2 + x3 11 -4x1 + x2 +2 x3 3 -2x1 + x3 = 1 x1，x2 ， x3 0,max z = 3x1 - x2 x3 + 0 x4+ 0 x5 -M x6 -M x7s.t. x1 - 2x2 + x3 + x4 = 11 -4x1 + x2 +2 x3 - x5 + x6 = 3 -2x1 + x3 + x7 = 1 xj 0 ( j = 1,2,7),解：,引入松弛变量 x4， x5 和人工变量 x6， x7 得,3-4M,M-1,2M-1,0,-M,0,-M,3M

31、,3-6M,M-1,3M-1,0,-M,0,0,4M,11/1,3/2,1/1,x3,-1,1,3,-2,0,1,1,0,0,-1,10,0,1,0,0,-1,1,-2,1,1,M-1,0,0,-M,1-3M,M+1,1/1,1,x2,-1,3,0,0,1,-2,2,-5,12,1,0,0,0,-1,-1-M,2,1,12/3,x1,3,0,0,1/3,-2/3,2/3,-5/3,4,0,0,1,2/3,-4/3,4/3,-7/3,9,0,0,0,-1/3,-1/3,2/3-M,-2,3,1,0,1-M,1/3-M,200-0.2M 0 ?,由于人工变量 x6 = x7 = 0, 所以,得原问

32、题的最优解 x*=(4,1,9,0,0)T 目标函数最优值 zmax = 2,Note: 在计算过程中,某个人工变量一旦变为非基变量,则该列可被删去,53,6 单纯形法的进一步讨论,(2)两阶段法,第一阶段：,max z = c1x1 + c2x2 + cnxn (1c) s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 . (2c) am1x1 + am2x2 + amnxn = bm xj0 （j = 1,2, n） (3c),max w = xn+1 xn+2 xn+m (1d) s.t. a11x1 + a12x2 +

33、 a1nxn + xn+1 = b1 a21x1 + a22x2 + a2nxn + xn+2 = b2 (2d) am1x1 + am2x2 + amnxn + xn+m = bm xj0 （j = 1,2, n, n+1, n+m） (3d),判断原LP 问题,（1c） （3c）是否存在可行解，如果存在就找出一个初始基可行解；,解之可得：,（a）如果 wmax 0, 则原问题无可行解，停止计算；,（b）如果 wmax = 0, 且人工变量都不是基变量，则转入 第二阶段；,54,第二章 线性规划及单纯形法,（c）如果 wmax = 0, 但仍有取零的人工变量为基变量；,x1 x2 xn xn

34、+1 xn+k xn+m bal1 al2 aln aln+1 1 an+m 0,如 x n+k =0 是基变量，在最终单纯形表中：,al1 al2 aln 不可能全为零，必有某个 alj 0，这时 xj 不是基变量，与 x n+k 交换即可。,第二阶段：,从第一阶段所求得的初始可行基出发，求解原问题,55,6 单纯形法的进一步讨论,二、关于退化和循环,1955 年 Beale 给出如下例子：,最优解：,B0=(P1,P2,P3)作为初始可行基，经6次迭代又得B0,56,第二章 线性规划及单纯形法,Bland 法则：,（对极大值问题而言）,则选择 xk 作为进基变量。,57,7 线性规划应用举

35、例,e.g.6 生产计划问题,某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表，若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费0.2万元. 现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低.试建立线性规划模型.,58,第二章 线性规划及单纯形法,解：,方法一,设工厂第 j 季度生产产品 xj 吨,需求约束：,第一季度末需交货 20 吨， x1 20,第二季度末需交货 20 吨， x1-20+x2 20,这是上季末交货后积余,第三季度末需交货 30 吨， x1+x2 -40+x3 30,第四季度末需交货 10 吨， x1+x2 +x

36、3 -70 +x4 = 10,生产能力约束：,0 xj aj j =1,2,3,4,生产、存储费用：,第一季度：15x1第二季度: 14x2+0.2(x1-20)第三季度: 15.3x3+0.2(x1+x2 -40)第四季度: 14.8x4 +0.2(x1+x2 +x3 -70 ),min z =15.6x1 +14.4x2 +15.5x3 + 14.8x4 -26 s.t. x1+x2 40 , x1+x2 +x3 70 x1+x2 +x3 + x4 =80, 20 x130,0 x240,0 x320,0 x410.,59,7 线性规划应用举例,方法二,设第 i 季度生产而用于第 j 季度

37、末交货的产品数量为 xij 吨.,需求约束：,x11=20 x12+x22=20,x13+x23+x33=30 x14+x24+x34+x44=10,生产能力约束：,x11 + x12 + x13+ x14 30,x22 +x23 +x24 40, x33 +x34 20, x44 10,xij 的费用 cij= di+0.2( j-i ),min z =15 x11 + 15.2x12 + 15.4x13 + 15.6x14 +14x22 +14.2x23 +14.4x24 +15.3x33 +15.5x34 +14.8x44 s.t. x11=20 x11 + x12 + x13+ x14

38、 30 x12+x22=20 x22 +x23 +x24 40 x13+x23+x33=30 x33 +x34 20 x14+x24+x34+x44=10 x44 10 xij 0 i =1,4; j=1,4, j i,60,第二章 线性规划及单纯形法,e.g.7 合理下料问题,某工厂要制作100套专用钢架，每套钢架需要用长为2.9m、2.1m和1.5m的圆钢各一根。已知原料每根长7.4m，现考虑应如何下料，可使所用原料最省？,解：,一根原料做一套，料头0.9m.,下料方案表,去掉料头0.9的方案可以吗？,61,7 线性规划应用举例,解：设 xj ( j=1,8)分别按8种方案下料的原材料根数

39、,约束条件：,2.9m: 2x1+x2+x3 +x4 100,2.1m: 2x2+x3 +3x5 + 2x6 +x7 100,1.5m: x1 +x3+3x4 +2x6 +3x7+4x8 100,xj 0 ( j=1,8),62,第二章 线性规划及单纯形法,目标函数分别为：1、材料根数最少；,min z= x1 +x2 +x3+x4 +x5 +x6 +x7+x8 s.t. 2x1+x2+x3 +x4 100 2x2+x3 +3x5 + 2x6 +x7 100 x1 +x3+3x4 +2x6 +3x7+4x8 100 xj 0 ( j=1,8),用单纯形法求解可得： x*=（10，50，0，30，0，0，0，0）T，最少使用的材料为90根，各种圆钢数均正好100个.,