线性规划与单纯形方法

1、1,第一章 线性规划与单纯形法,本章重点内容 线性规划模型与解的主要概念 线性规划的单纯形法，线性规划多解分析 线性规划的应用建模,2,第一节 线性规划问题及数学模型,1939年，（苏） 康托洛维奇 1947年，G. B. Dantzig 单纯形法 1979年，（苏） 哈奇安算法 1984年，Karmarkar算法,3,设I、II两种产品的产量分别为x1, x2 。建立该问题的数学模型为:,例2 现要做100套钢架，每套需2.9米、2.1米和1.5米的元钢各一根。已知原料长7.4米，问如何下料，使余料最少？,一、实例,4,解：设I, II, III, IV, V分别代表五种不同的原料用量方案,

2、 x1, x2 , x3, x4 , x5分别代表采用各方案下料的元钢的根数。,5,6,目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。,每一个问题变量都用一组决策变量（x1, x2, , xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的。,存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。,结论：线性规划是研究在一组线性不等式或线性等式约束下，使得某一线性目标函数取最大或最小的极值问题。,二、线性规划问题（LP问题）的共同特征,7,Max(Min) Z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn

3、 ( =, ) b1 a21x1+a22x2+a2nxn ( =, ) b2 s.t. am1x1+am2x2+amnxn ( =, ) bm xj0, j=1,2, ，n n变量个数； m约束行数； cj价值系数； bi右端项； aij技术系数,线性规划模型的一般形式为：,8,1.线性不等式的几何意义 半平面,作出LP问题的可行域 作出目标函数的等值线 移动等值线到可行域边界得到最优点,2.图解法步骤,三、两变量线性规划问题的图解法,9,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,4,3,0,例3（书P8）：,Q(4,2),Z=2x1+3x2,做目标函数2x1+3x2的

4、等值线，与阴影部分的边界相交于点Q(4,2) ，表明最优生产计划为：生产I产品4件，生产II产品2件。,10,例4,Z=36,11,3.图解法的作用,能解决少量问题,LP问题,有可行解,有最优解,唯一解 无穷多解,无最优解（可行域为无界）,无可行解（无解）,规律1：,揭示了线性规划问题的若干规律,12,规律2：,线性规划问题的可行域为一凸集 线性规划问题凸集的顶点个数是有限的 最优解可在凸集的某顶点处达到,13,四、线性规划问题的标准型,1.标准型,特点：目标最大化、约束为等式、 决策变量非负、右端项非负。,14,2.线性规划标准型的向量和矩阵表达式,矩阵式: Max Z=CTX s.t. A

5、X=b X0,n 向量式: Max Z= cjxj j=1 n s.t. Pjxj=b j=1 xj 0, j=1,2, . ,n,其中：C = (c1 , c2 , . , cn)T b = (b1 , b2 , . , bm)T X = (x1 , x2 , . , xn)T a11 a12 . a1n A= a21 a22 . a2n . . am1 am2 . amn = ( P1 , P2 , . , Pn ),15,3.所有LP问题均可化为标准型,16,例5 化标准型,可化为,17,例6 化标准型,Max Z =x1+2x2+3x4-3x5+0 x6+0 x7 s.t. x1 -

6、x2 + x4 - x5+x6 = 7 x1+x2 + x4 - x5 - x7 = 2 -3x1 -x2+3x4 -3x5 = 5 x20 , xj0, j=1,4,5,6,7,18,课堂练习,19,五、标准型LP问题解的概念,20,21,令B = =( P1 , P2 , , Pm ) 且| B | 0 ，则称Pj (j=1,2,m) 为基向量。 与基向量Pj对应的变量xj称为基变量， 记为XB = ( x1 , x2 , , xm )T，其余的变量称为非基变量，记为 XN = ( xm+1 , xm+2 , , xm+n ) T 。,基变量：,22,基解 令非基变量XN = 0， 求得的

7、一组基变量XB的值称为基解。,基可行解 既是基本解，又是可行解。,结论：基可行解的个数基解的个数Cnm,23,线性规划标准型问题解的关系,约束方程的 解空间,基解,可行解,非可行解,基可 行解,24,例1（书P8）： Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1, x2 0,六、可行解、基解和基可行解举例,x1+2x2=8,x1,标准型,25,例2,26,第二节 LP问题的基本理论,一、基本概念,27,28,定理1 LP问题的可行域为一凸集。,二、基本定理,29,引理 线性规划问题的可行解X=(x1, x2, , xn)T是基可行解的充要条件为X的

8、正分量所对应的系数列向量是线性独立的。,30,定理2 线性规划问题的基可行解对应于可行域的顶点。,（即：设X是LP问题的可行解，则X不是LP问题的基可行解当且仅当X不是可行域顶点）,31,32,33,定理3 若可行域有界，则LP问题的目标函数一定可以在其可行域的顶点上达到最优。,34,总结 线性规划问题的可行域是凸集(定理1)；凸集的顶点对应于基可行解(定理2)，基可行解(顶点)的个数是有限的（不超过Cnm个）；若线性规划有最优解，必在可行域某顶点上达到(定理3)。因此,我们可以在有限个基可行解中寻找最优解。,35,这就提供了寻求线性规划问题最优解的途径：在有限个基可行解中寻求最优解, 但穷举

9、法仍然低效率的。针对线性规划问题的特点，有效地求解方法是单纯形方法。 单纯形方法的基本思想是：开始于某一个可行基及其对应的基可行解，从一个基可行解迭代到另一个基可行解，并且使目标函数值不断增大，经过有限步必能求得线性规划问题的最优解或者判定线性规划问题无有界的最优解。,36,第三节 单纯形法,一、基本思想,化LP问题为标准型， 确定一个初始基可行解,检验解的 最优性,结束,是,枢轴运算（旋转运算） 确定另一个基可行解,否,37,二、举例,例（书P8）： Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1, x2 0,标准型,保证单位矩阵，如果找不到，后面

10、会介绍人工变量法。 对上述约束等式变形得：,38,39,40,41,42,问题： (1) 为何最后目标函数表达式无正系数时，得到最优解；何时出现无穷多解以及无界解？ (2) 每次如何选取进基变量和出基变量？,43,三、进基变量的选择,44,45,结论：每次进基变量选择当前检验数最大的 非基变量，这样能使目标函数值尽快 增大。,46,四、最优性检验与解的判别,47,三、检验数的意义,结论：如果LP问题通过单纯形法迭代到某步时，所有检验数0,则该LP问题已得到最优解。,Max Z=CTX s.t. AX=b X0,若cj-CBB-1Pj=j0, 则ZZ0, Z0即为最优解. (基变量的检验数必为0

11、),令A=(B,N), X= XB ,CT=(CBT,CNT) XN,48,一、步骤,Step 1. 化LP问题为标准型,建立初始单纯形表; Step 2. 若所有检验数0,则最优解已达到。 否则,计算 , 选取k 所对应的变量xk 为进基变量; Step 3. 计算 ,选取l 所对应的变量xl 为出基变量; Step 4. 以alk为主元素进行旋转运算,转Step 2;,第四节 单纯形法的步骤,49,基可行解： x1=b1, x2=b2, , xm=bm , xm+1=xm+2= =xn= 0,1.初始单纯形表,c1 c2 cm cm+1 cn,c1 x1 c2 x2 cm xm,b1 b2

12、 bm,1 0 0 a1, m+1 a1n 0 1 0 a2, m+1 a2n 0 0 1 am, m+1 amn,0 0 0 m+1 n,-CBTB-1b,50,2.进基变量的选择,选取 所对应的变量xk 为进基变量。,51,3.出基变量的选择,选取 所对应的变量xl 为出基变量。,52,4.旋转运算,ck xk,bl /alk,0 1/alk 0 al, m+1/alk1 aln/alk,b1,1 -a1k/alk 0 a1, m+1 0 a1n,bm,0 -amk/alk1 am, m+1 0 amn,53,二、实例,化为标准型,54,单纯形表算法,以4为枢轴元素进行旋转运算，x2为换入

13、变量，x5为换出变量,以1为枢轴元素进行运算，x1为换入变量， x3为换出变量,0 x3 0 x4 0 x5,2 3 0 0 0,8 16 12,1 2 1 0 0 4 0 0 1 0 0 4 0 0 1,2 3 0 0 0,0,4 - 3,55,以2为枢轴元素进行运算，x5为换入变量， x4为换出变量,此时达到最优解：X*=(4, 2)T, Max Z=14。,56,1 D. Goldfarb and J.K. Reid, A practicable steepest-edge simplex algorithm, Mathematical Programming,12,361-371,(1

14、977).,2 J.J.Forrest and D. Goldfarb, Steepest-edge simplex algorithms for linear programming, Mathematical Programming,57,341-374,(1992).,参考文献：,最陡边下降法,57,一、人工变量法,第五节 LP问题的进一步讨论,58,1.大M法（M为任意大的正数）,加入松弛变量x4;剩余变量x5;人工变量x6, x7,59,1) 人工变量的识别,2) 目标函数的处理,3) 计算(单纯形法),60,注意：本例是求最小值，所以用所有 来判别目标函数是否实现了最小化。因而换入

15、变量xk的选取标准为,61,结果得: X*=(4,1,9,0,0,0,0) Z*=-2,（接上表）,62,两阶段法 (将LP问题分成两个阶段来考虑),第I 阶段: 不考虑原问题是否存在可行解，给原LP问题加入人工变量，并构造仅含人工变量的目标函数和要求最小化；然后用单纯形法求解，若得W=0，则进行第二阶段计算，否则无可行解。,第II 阶段：将第一阶段得到的最终表除去人工变量，将目标函数行的系数换为原问题的系数，作为第二阶段的初始表。,63,加入松弛变量x4;剩余变量x5;人工变量x6,x7,用单纯形法求解第一阶段的结果得：,64,此时，达到第一阶段的最优解，W=0,65,由于人工变量x6 =x

16、7=0,所以(0, 1, 1, 12, 0)T 是该线性规划问题的基可行解。于是转入第二阶段运算：,此时达到该LP问题的最优解：x1=4, x2=1, x3=9; 目标函数值Z= -2。,66,1.存在两个以上的最大正检验数。选择任何变量（对应最大正检验数）作为进基变量。,2.最小比值相同。此时LP问题出现退化现象。,二、单纯形法中存在的问题,如果在一个基本可行解的基变量中至少有一个分量为0，则称此基本可行解是退化的基本可行解。,67,68,选取 x1 为换入变量；选取下标最小的 x5 为换出变量，得下表：,此时换出变量为x1，换入变量为x4，迭代后目标函数值不变。,69,解决退化的方法有：

17、“摄动法”、“辞典序法”、 Bland规则等,1974年Bland提出Bland算法规则：,70,3.最小比值原则失效,经过一次迭代后可得右表,当用单纯形法求解LP问题迭代到某步时,存在某k0, 而k对应列向量Pk0, 则此LP问题有无界解.,71,4.在最优表中出现某非基变量检验数为0,72,73,例1 某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、C。已知产品的规格要求、单价和原材料的供应量、单价。该厂应如何安排生产使利润最大？,第六节 应用举例,74,用单纯型法计算得结果：每天生产A产品200kg,分别需要原料:C为100kg;P为50kg;H为50kg. 总利润收入Z=500元/天.,75,先考虑一月份的线性规划模型:,例2,76,以一月份内各种设备的生产能力总和为分母,生产产品所需要的各类设备的总台时数为分子,可计算出一月份的平均设备利用系数Z,将Z作为目标函数,可得下面的模型:,77,考虑二月份线性规划模型时:(1)从全年计划中减去一月份已生产的数量;(2)对批量小的产品,如一月份已经安排较大产量的,二月份将剩余部分安排生产;(3)保证第4号产品在月底前交货.,这样,我们可以依次对12个月列出线性规划模型并求解,再根据具体情况对计算结果进行必要调整。,78,例3 某部门在今后5年内连续给以下项目投资：,项目