1、第 三 章,线 性 规 划,3.1 线性规划模型,例:某工厂拥有A、B、C 三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,问题：工厂应如何安排生产可获得最大的总利润？ 解：设变量xi为第i种（甲、乙）产品的生产件数（i1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1 + 2 x2 65； 对设备B，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2 x1 + x2 40；,3.1 线性规
2、划模型,对设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2 75 ；另外，产品数不可能为负，即 x1 ,x2 0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500x1+2500x2 。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：,3.1 线性规划模型,目标函数 Max z =1500x1+2500x2约束条件 s.t. 3x1+2x2 65 2x1+x2 40 3x2 75 x1 ,x2 0,3.1 线性规划模型,这是一个典型的利
3、润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1 ,x2 的取值。,3.1 线性规划模型,一般形式 目标函数：Max(Min)z = c1x1 + c2x2 + + cnxn,约束条件： a11x1+a12x2+a1nxn( =, )b1a21x1+a22x2+a2nxn( =, )b2 . . . am1x1+am2x2 +amnxn( =, )bm x1 ，x2 ， ，xn 0,3.1 线性规划模型,标准形式目标
4、函数：Max z = c1x1 + c2x2 + + cnxn,约束条件：a11x1 + a12x2 + + a1nxn = b1a21x1 + a22x2 + + a2nxn = b2 . . .am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0,3.1 线性规划模型,可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。 对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:,3.1 线性规划模型,1.极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + + c
5、nxn 则可以令z -f ，该极小化问 题与下面的极大化问题有相同的最优 解，即 Max z = -c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f - Max z,3.1 线性规划模型,2、约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量s ，使它等于约束右边与左边之差 s=bi(ai1 x1 + ai2 x2 + + ain xn ) 显然，s 也具有非负约束，即s0， 这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+
6、s = bi,3.1 线性规划模型,当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时，类似地令 s=(ai1 x1+ai2 x2+ +ain xn)- bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi,3.1 线性规划模型,为了使约束由不等式成为等式而引进的变量s称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。,3.1 线性规划模型,例2.2：将以下线性规划问题转化为标准形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s
7、. t. 2.3 x1 + 5.2 x2 - 6.1 x3 15.7 4.1 x1 + 3.3 x3 8.9 x1 + x2 + x3 = 38 x1 , x2 , x3 0,3.1 线性规划模型,解：首先,将目标函数转换成极大化：令 z= -f = -3.6x1+5.2x2-1.8x3,其次考虑约束，有2个不等式约束，引进松弛变量x4，x5 0。于是，我们可以得到以下标准形式的线性规划问题： Max z = - 3.6 x1 + 5.2 x2 - 1.8 x3s.t. 2.3x1+5.2x2-6.1x3+x4= 15.7 4.1x1+3.3x3-x5= 8.9 x1+x2+x3= 38 x1
8、 ,x2 ,x3 ,x4 ,x5 0,3.1 线性规划模型,3. 变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj = xj- xj”其中 xj0，xj”0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。,3.1 线性规划模型,4.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi 0, 且 B-1pj0, 则 (LP) 无有界解 .,3.2 线性规划的单纯形法,表格单纯形法1、原理及算法过程 Max cTx(LP) s.t. Ax = b x0其
9、中, c , x Rn b Rm A mn 矩阵，秩（A）= m,3.2 线性规划的单纯形法单纯形法原理及算法过程,算法过程 (考虑一般步, k = 0,1,2, )设 x(k) 为极点, 对应分解 A = B , N ，使 xT = xBT, xNT , 这里 xB = B-1b0, xN =0， 相应 cT = cBT, cNT 。那么， 1）若 cNT- cBT B-1N0, 则 x(k) opt，停； 2）否则，存在 cj- cBT B-1pj 0, a）若 B-1pj0, 则 (LP) 无有界解，停； b）若存在 (B-1pj)i 0, 取 = min(B-1b)i / (B-1pj
10、)i | (B-1pj)i 0 = (B-1b)r /(B-1pj)r 0,3.2 线性规划的单纯形法单纯形法原理及算法过程,(续) 得到 x(k+1) = x(k) + d 是极点其中, dT = dBT, dNT , 这里 j dB = -B-1pj , dN = (0, . , 1, ,0)T有, cTx(k+1) = cTx(k) + cTd = cTx(k) + (cj - cBTB-1pj) cTx(k) 所以，x(k+1) 比 x(k) 好 重复这个过程，直到停机。,3.2 线性规划的单纯形法 表格单纯形法,2、单纯形表：设 x 为初始极点, 相应分解 A = B , N ,作变
11、换，使前m+1列对应的m+1阶矩阵变为单位矩阵。相当于该表左乘 1 cBT -1 1 - cBT B-1 0 B 0 B-1,=,3.2 线性规划的单纯形法表格单纯形法,得到： 检验数,为了计算方便，我们对规范形式建立如下单纯形表：（注：引入了m个松弛变量）,3.2 线性规划的单纯形法,表格单纯形法考虑： bi 0 i = 1 , , m Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn b1 a21 x1 + a22 x2 + + a2n xn b2 am1 x1 + am2 x2 + + amn xn bm x1
12、 ，x2 ， ，xn 0,3.2 线性规划的单纯形法,加入松弛变量： Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn+ xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0,显然，xj = 0 j = 1, , n ; xn+i = bi i = 1 , , m 是基本可行解 对应的基是单位矩阵。以下是初始单纯形表： m m其中：f =
13、- cn+i bi j = cj - cn+i aij 为检验数 cn+i = 0 i= 1,m i = 1 i = 1 an+i,i = 1 , an+i,j = 0 ( ji ) i , j = 1, , m,建立实用单纯形表,利用求解线性规划问题基本可行解（极点）的方法来求解较大规模的问题是不可行的。单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。,3.2 线性规划的单纯形法,单 纯 形 法,单纯形法的基本过程,例：用单纯形法的基本思路解前例的线性规划问题 Max z = 1500 x1
14、 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0,3.2 线性规划的单纯形法,3.2 线性规划的单纯形法,最优解 x1 = 5 x2 = 25 x4 = 5（松弛标量，表示B设备有5个机时的剩余） 最优值 z* = 70000,注意：单纯形法中， 1、每一步运算只能用矩阵初等行变换； 2、表中第3列的数总应保持非负（ 0）； 3、当所有检验数均非正（ 0）时，得到最优单纯形表。,3.2 线性规划的单纯形法,一般情况的处理及注意事项的强调：主要是讨论初
15、始基本可行解不明显时，常用的方法。要弄清它的原理，并通过例题掌握这些方法，同时进一步熟悉用单纯形法解题。 考虑一般问题： bi 0 i = 1 , , m,3.2 线性规划的单纯形法,Max z = c1x1 + c2x2 + + cnxn s.t. a11x1+a12x2 +a1nxn = b1 a21x1+a22x2 +a2nxn = b2 . . . am1x1+am2x2+amnxn = bm x1 ，x2 ， ，xn 0,3.2 线性规划的单纯形法,大M法： 引入人工变量 xn+i 0 （i = 1 , , m）及充分大正数 M 。得到：Max z = c1x1 +c2x2 +cnx
16、n -Mxn+1 -Mxn+m s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 . . . am1 x1 + am2 x2 + + amn xn + xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0,3.2 线性规划的单纯形法,显然，xj = 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解。对应的基是单位矩阵。 结论：若得到的最优解满足 xn+i = 0 i = 1 , , m 则是原问题的最优解；否则，原问题无可行
17、解。,单 纯 形 法,两阶段法： 引入人工变量 xn+i 0，i = 1 , m； 构造: Max z = - xn+1 - xn+2 - - xn+m s.t. a11x1+a12x2+ +a1nxn+xn+1 = b1 a21x1+a22x2+ +a2nxn+xn+2 = b2 . . . am1x1+am2x2+ +amnxn+xn+m = bm x1,x2 . xn ,xn+1,xn+m 0,单 纯 形 法,第一阶段求解上述问题： 显然，xj = 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解,它对应的基 是单位矩阵。,结论：若得到的最优解满足 xn+
18、i=0 i=1 , , m 则是原问题的基本可行解;否则，原问题无可行解。 得到原问题的基本可行解后，第二阶段求解原问题。,单 纯 形 法,例（LP）Max z = 5x1 + 2x2 + 3x3 - x4 s.t. x1 + 2x2 + 3x3 = 15 2x1 + x2 + 5x3 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 0,3.2 线性规划的单纯形法,Max z = 5x1+2x2+3x3-x4-Mx5-Mx6 s.t. x1+2x2+3x3+x5 =15 2x1+x2+5x3+x6 =20 x1+2x2+4x3+x4 =26 x1
19、 ,x2 ,x3 ,x4 ,x5 ,x6 0,大M法问题(LP-M）,3.2 线性规划的单纯形法,大M法 （LP - M）,得到最优解：(25/3，10/3，0，11)T 最优目标值：112/3,3.2 线性规划的单纯形法,第一阶段问题（LP - 1） Max z = - x5 - x6 s.t. x1 + 2x2 + 3x3 + x5 = 15 2x1 + x2 + 5x3 + x6 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 0,两阶段法 ：,3.2 线性规划的单纯形法,第一阶段 (LP - 1）,得到原问题的基本可行
20、解: (0，15/7，25/7，52/7)T,3.2 线性规划的单纯形法,第二阶段 把基本可行解填入表中,得到原问题的最优解:(25/3，10/3，0，11)T 最优目标值：112/3,3.2 线性规划的单纯形法,3.3 线性规划的对偶,对偶原理 对偶问题定义 线性规划问题写出其对偶问题，要掌握在对称形式和非对称情况下由原问题写出对偶问题的方法。 对偶定理 只需了解原问题与对偶问题解的关系，证明从略。,1.对偶问题： 若3.1中的例题的设备都用于外协加工，工厂收取加工费。试问：设备 A、B、C 每工时各如何收费才最有竞争力？ 设 y1 ，y2 ，y3 分别为每工时设备 A、B、C 的收取费用。
21、,3.3 线性规划的对偶,线性规划原问题,例:某工厂拥有A、B、C 三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。,Max z = 1500x1 + 2500x2 s.t. 3x1 + 2x2 65 2x1 + x2 40 原问题 3x2 75 x1 ,x2 0 Min f = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 1500 （不少于甲产品的利润） 2y1+y2+3y3 2500 对偶问题 （不少于乙产品的利润） y1, y2 , y3 0,3.3 线性规划的对偶,
22、2、对偶定义 对称形式： 互为对偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax b s.t. AT y c x 0 y 0 “Max - ” “Min- ”,3.3 线性规划的对偶,一对对称形式的对偶规划之间具有下面的对应关系。 (1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“min，”相对应。,3.3 线性规划的对偶,(2)从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。 (3)从数据b
23、、C的位置看：在两个规划模型中，b和C的位置对换。 (4)两个规划模型中的变量皆非负。,3.3 线性规划的对偶,非对称形式的对偶规划 一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。 对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。 （1）将模型统一为“max，”或“min，” 的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；,3.3 线性规划的对偶,（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制； （3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。,3.3 线性规划的对偶,
24、3.3 线性规划的对偶,例 写出下面线性规划的对偶规划模型,解 先将约束条件变形为“”形式,3.3 线性规划的对偶,再根据非对称形式的对应关系，直接写出对偶规划,3.3 线性规划的对偶,对偶定理(原问题与对偶问题解的关系）考虑（LP）和（DP）,定理3-1 (弱对偶定理） 若 x, y 分别为（LP) 和（DP）的可行解，那么cTx bTy。,推论 若（LP）可行，那么（LP）无有限最优解的充分必要条件是（LD）无可行解。,3.3 线性规划的对偶,定理3-2 (最优性准则定理) 若x,y分别(LP),(DP)的可行解,且cTx=bTy ，那么x,y分别为(LP)和(DP)的最优解。,定理3-3
25、 (主对偶定理) 若(LP)和(DP)均可行 那么(LP)和(DP)均有最优解,且最优值相等。,以上定理、推论对任意形式的相应性规划的对偶均有效,3.3 线性规划的对偶,影子价格 是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。 若x*,y* 分别为（LP）和（DP）的最优解， 那么， cT x* = bT y* 。 根据 f = bTy*=b1y1*+b2y2*+bmym* 可知 f / bi = yi* yi* 表示 bi 变化1个单位对目标 f 产生的影响，称 yi* 为 bi的影子价格。 注意：若 B 是最优基， y* = (BT)-1 cB 为影子价格向量。,3.3 线
26、性规划的对偶,影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。,3.3 线性规划的对偶,需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格的经济含义（2），是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。,3.3 线性规划的对偶,由最优单纯形表求对偶问题最优解 标准形式： Max z = 50
27、 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 2x1 + x2 + x4 = 400 x2 + x5 = 250 x1 ,x2 ,x3 ,x4 ,x5 0,3.3 线性规划的对偶,-cBTB-1,I,B=(p1, p4,p2 ),oT,B-1,最优解 x1 = 50 x2 = 250 x4 = 50影子价格 y1 = 50 y2 = 0 y3 = 50 , B-1对应的检验数 T = cBTB-1 。,3.3 线性规划的对偶,对偶单纯形法的基本思想 对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也
28、可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。,对偶单纯形法,如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原 规划的最优解。,对偶单纯形法,对偶单纯形法在什么情况下使用 ： 应用前提：有一个基，其对应的基满足: 单纯形表的检验数行全部非正（对偶可行）； 变量取值可有负数（非可行解）。 注：通过矩阵行变换运算，使
29、所有相应变量取值均为非负数即得到最优单纯形表。,对偶单纯形法,1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2； 2.若b0,则得到最优解,停止;否则,若有bk0则选k行的基变量为出基变量,转3 3.若所有akj0( j = 1,2,n )，则原问题无可行解,停止;否则,若有akj0 则选 =minj / akjakj0=r/akr那么 xr为进基变量,转4； 4.以akr为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。,对偶单纯形法求解线性规划问题过程：,对偶单纯形法,例：求解线性规划问题：,对偶单纯形法,表格对偶单纯形法,单纯形法和对偶单纯形法步骤,单纯形表的理解
30、（例题）,上表中6个常数 a1 , a2 , a3 , b , 1 , 2 取值在什么范围可使1、现可行解最优，且唯一？何时不唯一？2、现基本解不可行；3、问题无可行解；4、无有限最优解；5、现基本解可行，由 x1 取代 x6 目标函数可改善。,进一步理解最优单纯性表中各元素的含义考虑问题 Max z = c1 x1 + c2 x2 + + cn xn s.t. a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 . . . am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0,3.4 灵敏度分析
31、,3.4 灵敏度分析,无防设，xj = 0 j = m+1, , n ; xi = bi i = 1 , , m 是基本可行解, 对应的目标函数典式为：z = -f + m+1xm+1+ nxn以下是初始单纯形表： m m其中：f = - ci bi j = cj - ci aij 为检验数。 向量 b = B-1 b i = 1 i = 1 A= p1, p2, , pn , pj = B-1 pj, pj = ( a1j , a2j , , amj )T ， j = m+1, , n,内容： ci , bj发生变化 增加一约束或变量,对于表格单纯形法，通过计算得到最优单纯形表。 应能够找到
32、最优基 B 的逆矩阵 B-1 ， B-1b 以及 B-1N，检验数 j 等。,3.4 灵敏度分析,价值系数c发生变化： m 考虑检验数 j = cj - cri arij j =1,2,n i = 1,1. 若ck是非基变量的系数： 设ck变化为 ck + ck k= ck + ck -cri arik = k+ ck 只要 k 0 ,即 ck - k ，则 最优解不变；否则，将最优单纯形表 中的检验数 k 用 k取代，继续单 纯形法的表格计算。,3.4 灵敏度分析,例: Max z = -2x1 - 3x2 - 4x3 S.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 0,3.4 灵敏度分析,例：最优单纯形表,从表中看到3= c3+c3-(c2a13+c1a23 ) 可得到c3 9/5 时，原最优解不变。,3.4 灵敏度分析,2、若 cs 是基变量的系数： 设 cs 变化为 cs + cs ，那么 j= cj -cri arij - ( cs + cs ) asj = j - cs asj ， i s,
