《【7A文】生产运筹学--线性规划及单纯形法》由会员分享，可在线阅读，更多相关《【7A文】生产运筹学--线性规划及单纯形法（66页珍藏版）》请在金锄头文库上搜索。
1、运 筹 学,Operations Research,第一章 线性规划及单纯形法,第一章 线性规划及单纯形法,线性规划（Linear Programming，简称LP） 运筹学的一个重要分支，是运筹学中研究较早、发展较 快、理论上较成熟和应用上极为广泛的一个分支。,1947年G.B. Dantying提出了一般线性规划问题求解 的方法单纯形法之后，线性规划的理论与应用都得 到了极大的发展。,60年来，随着计算机的发展，线性规划已广泛应用 于工业、农业、商业、交通运输、经济管理和国防等各 个领域，成为现代化管理的有力工具之一。,1 线性规划问题及其数学模型,e.g. 1 资源的合理利用问题,问：如
2、何安排生产计划， 使得既能充分利用现有资 源又使总利润最大？,表 1 产品 资源 甲 乙 库存量 A 1 3 60 B 1 1 40 单件利润 15 25,某工厂在下一个生产周期内生产甲、乙两种产品， 要消耗A、B 两种资源，已知每件产品对这两种资源的 消耗，这两种资源的现有数量和每件产品可获得的利 润如表 1。,第一章 线性规划及单纯形法,max z = 15x1 +25x2 s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0,解 ：,设 x1，x2 为下一个生 产周期产品甲和乙的产量；,约束条件：,Subject to,x1 + 3x2 60,x1 + x2 40,x1
3、，x2 0,目标函数：,z = 15 x1 +25 x2,表 1 产品 资源 甲 乙 库存量 A 1 3 60 B 1 1 40 单件利润 15 25,决策变量,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 A2 a21 a22 a2n b2 Am
4、 am1 am2 amn bm 单 价 c1 c2 cn,试在满足营养要 求的前提下，确定食 品的购买量，使食品 的总价格最低。,第一章 线性规划及单纯形法,表 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,1 线性规划问题及其数学模型,三个基本要素：,Note：,1、善于抓住关键因素，忽略对系统影响不大的因素；,2
5、、可以把一个大系统合理地分解成 n 个子系统处理。,1、决策变量 xj0,2、约束条件 一组决策变量的线性等式或不等式,3、目标函数 决策变量的线性函数,第一章 线性规划及单纯形法,max（min）z = c1x1 + c2x2 + + cnxn s.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）为已知 常数,1 线性规划问题及其数学模型,线性规划
6、问题的标准形式：,max z = c1x1 + c2x2 + + cnxn s.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、所有决策变量 均非负。,第一章 线性规划及单纯形法,如何转化为标准形式？,1、目标函数为求极小值，即为： 。,因为求 min z 等价于求 max (-
7、z)，令 z = - z， 即化为：,2、约束条件为不等式，,xn+1 0 松弛变量,如何处理？,1 线性规划问题及其数学模型,、右端项bi 0时，只需将等式两端同乘（-1） 则右端项必大于零,4、决策变量无非负约束,设 xj 没有非负约束，若 xj 0，可令 xj = - xj ， 则 xj 0；,又若 xj 为自由变量，即 xj 可为任意实数， 可令 xj = xj - xj，且 xj , xj 0,第一章 线性规划及单纯形法,e.g. 3,试将 LP 问题,min z = -x1+2x2-3x3 s.t. x1+x2+x3 7 x1-x2+x3 2 -3x1+x2+2x3 = -5 x1
8、,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,1 线性规划问题及其数学模型,LP的几种表示形式：,2 线性规划问题的图解法,定义1 在LP 问题中，凡满足约束条件(2)、(3)的 解 x = (x
9、1,x2,xn)T 称为LP 问题的可行解， 所有可行解的集合称为可行解集（或可行域）。 记作 D= x | Ax = b ,x0 。,定义2 设LP问题的可行域为D，若存在x*D，使得 对任意的xD 都有c x*c x，则称x*为LP 问题 的最优解，相应的目标函数值称为最优值， 记作 z*=c x*。,2 线性规划问题的图解法,max z = 15x1 +25x2 s.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 x1+z/25,x2,x1,最优解： x1=3
10、0 x2 =10 最优值：zmax=700,B点是使z达到最大的唯一可行点,第一章 线性规划及单纯形法,LP问题图解法的基本步骤：,1、在平面上建立直角坐标系；,2、图示约束条件，确定可行域和顶点坐标；,3、图示目标函数（等值线）和移动方向；,4、寻找最优解。,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 x2= 3.8,x1 + 1.9 x2 = 11.4
11、,（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,第一章 线性规划及单纯形法,max z = 2x1 + 2x2 s.t. 2x1 x2 2 -x1 + 4x2 4 x1，x2 0,O,x1,x2,Note: 可行域为无界区域， 目标函数值可无限 增大，即解无界。 称为无最优解。,可行域为无界区域一定无最优解吗？,2 线性规划问题的图解法,由以上两例分析可得如下重要结论：
12、,1、LP 问题从解的角度可分为：, 有可行解, 无可行解,有唯一最优解 b. 有无穷多最优解 C. 无最优解,2、LP 问题若有最优解，必在可行域的某个顶点上取 到；若有两个顶点上同时取到，则这两点的连线上 任一点都是最优解。,2 线性规划问题的图解法,图解法优点：,直观、易掌握。有助于了解解的结构。,图解法缺点：,只能解决低维问题，对高维无能为力。,3 线性规划问题解的基本性质,讨论如下 LP 问题：,其中,系数矩阵,决策向量,假设 A 的秩为 m , 且只讨论 m n 的情 形。,什么意思？ 为什么？,第一章 线性规划及单纯形法,定义 3 在上述 LP 问题中，约束方程组（2）的系数 矩
13、阵 A 的任意一个 mm 阶的非奇异的子方阵 B （即 |B|0），称为 LP 问题的一个基阵或基。,称 pi (i=1,2,m) 为基向量;,xi (i=1,2,m) 为基变量；,xj (j= m+1,n) 为非基变量,pj (j= m+1,n) 为非基向量;,记：,则 A = ( B, N ),3 线性规划问题解的基本性质,A = ( B, N ),xB= (x1,xm)T , xN =(xm+1,xn)T,则,代入约束方程（2），得,自由变量 （独立变量）,令,称（4）为相应于基 B 的基本解,第一章 线性规划及单纯形法,是可行解吗？,max z= x1-2x2+3x4- 3x5 s.t
14、. 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 称为可行基。,3 线性规划问题解的基本性质,基本解唯一吗？ 最多有多少？,称它是非退化的解；反之，如果有一个基变量也取 零值，则称它是退化的解。一个LP问题，如果它的 所有基可行解都是非退化的就称该是非退化的，否 则就称它是退化的。,第一章 线性规划及单纯形法,LP 问题解的基本性质,Ax=0,定理 2、定理 3 称为 LP 问题的基本定理,定理2 证明,向前,定理3 证明,LP 问题是一个组合优化问题,3 线性规划问题解的基本性质,定理 2 证明,设x = (x1, x2, xn)T 是LP 问题的一个可行解，如果 x = 0， 则由定理 1知，它是LP 问题的一个基可行解，定理成立。,如果x0，不妨设 x 的前 k 个分量为非零分量。 则有 x1p1 +
