线性规划与单纯形法（宣城）

1、1,第二章 线性规划与单纯形法,本章重点内容 线性规划模型与解的主要概念 线性规划的单纯形法，线性规划多解分析 线性规划的应用建模,2,Linear Programming , LP 1939年 苏 康托洛维奇和1941年 美 Hichook 在生产组织管理和制定交通运输方案方面研究和应用线性规划，求解方法解乘数法 1947年 G. B. Dantzig 单纯形法 1979年 苏 哈奇安多项式算法（椭球算法） 1984年 Karmarkar算法 多项式时间算法每次迭代不是从一个顶点出发求改进的顶点，而是使迭代点保持在某个单纯形的内部，因此是一种内点算法。,第一节 线性规划问题及其数学模型,3,

2、LP是数学规划的一个重要分支，数学规划着重解决资源的优化配置，一般可以表达成以下两个问题中的一个： （1）当资源给定时，要求完成的任务最多； （2）当任务给定时，要求为完成任务所消耗的资源最少。 若上述问题的目标约束都能表达成变量的线性关系，则这类优化问题称LP问题。 LP是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。,4,一、实例,例1 生产计划问题 (书P15，典型示例),Step 1:明确问题，设定决策变量 设I、II两种产品的产量分别为x1, x2 。,Step 2: 确定约束条件,5,说明：OBJ 表示Objective; s.t. 表示Subject to,Step

3、 3: 给出目标函数,Step 4: 整理数学模型,6,例2 污水处理问题 (书P16),设x1x2为工厂12 的日污水处理量。建立该问题的数学模型为：,7,二、总结,目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。,线性规划问题（LP问题）的共同特征：,每一个问题变量都用一组决策变量（x1, x2, , xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的且在某范围内连续取值。,存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。,8,三、线性规划问题的一般形式,9,四、两变量线性规划问题的图解法,1.线性不等式的几何意义

4、 半平面,作出LP问题的可行域 作出目标函数的等值线 移动等值线到可行域边界得到最优点,2.图解法步骤,例1 （典型示例）：,10,4x1=16,4x2=12,x1+2x2=8,x1,x2,Q6(0,4),Q7(8,0),Q4(0,3),O(0,0),Q2(4,2),Z=2x1+3x2,做目标函数2x1+3x2的等值线，与阴影部分的边界相交于Q(4,2)点，表明最优生产计划为：生产I产品4件，生产II产品2件。,Q1(4,0),Q3(2,3),Q5(4,3),图解法意义不大，但可直观揭示有关概念。,11,3.LP解的类型,有4类： （1）唯一最优解 如例1的Q2点。 （2）无穷多最优解（多重解

5、） （3）无界解 （4）无可行解,12,0 4 8 12 x1,9 6 3,可行域,Z=36,此线段上的点 均为最优点,x2,当例1 的目标函数变为 max Z =2x1+4x2,多重解示例,13,x2,可行域不闭合,Z增大方向,x1,无界解示例,14,产生原因：缺少约束条件 注 意：可行域不闭合不一定就会出现无界解，这要看目标函数的性质。若目标函数是min，则有最优解。无论有无最优解，一定有可行解。,15,无可行解示例,无公共区域(可行域) 产生原因： 有相互矛盾的约束条件。,x2,x1,16,4. 图解法的作用,LP问题,有可行解,有最优解,唯一解 无穷多解,无最优解（可行域为无界）,无可

6、行解（无解）,（1）规律：,揭示了线性规划问题有关规律和结论。,（2）结论：若LP问题有最优解，则要么最优解唯一（对应其中一个顶点），要么有无穷多最优解（对应其中两个顶点连线上的所有点）。,17,五、线性规划问题的标准型,1. 标准型的构成要素,（1）目标函数：max,（2）约束条件：等式,（3）变量约束：非负 xj0,（4）资源限量：非负bi 0,18,2. 标准型的表示方法,（1）解析式,19,简写的解析式,20,亦可写成：,其中：,（2）矩阵式,21,X决策变量列向量。 b约束条件右端常数（资源）列向量。 C目标函数价值系数行向量。 Amn约束条件左端系数矩阵。,22,（3）向量和矩阵符

7、号式,23,3. 非标准型的标准化,（1）最小转换成最大,24,（2）不等式约束条件转换成等式约束条件,（3）变量约束转换,25,（4）把bi0,26,例3 (P20),可化为,27,例4 (P21) 化下列LP为标准型,28,29,六、标准型LP问题的解,1. 基本概念,30,31,32,33,34,4x1=16,4x2=12,x1+2x2=8,x1,x2,Q6(0,4),Q7(8,0),Q4(0,3),O(0,0),Q2(4,2),Q1(4,0),Q3(2,3),Q5(4,3),K,2. 可行解、基解和基可行解举例,典型示例标准化后有3个约束条件、5个决策变量，基的最大个数可达C53=10

8、个，但实际上只有8个。,35,约束方程的 解空间,基解,可行解,非可行解,基可 行解,3. LP标准型问题解的关系,36,4. LP标准型问题解的结论,根据LP的图解法及解的基本概念可知： 基解对应约束条件的交点； 基可行解对应可行域的顶点 某个基可行解一定是最优解，即一定在可行域的顶点上得到最优解。,37,第二节 单纯形法 Simplex Method,由线性代数知，对LP标准型问题，理论上可以求出所有基解（枚举法），再通过观察找出其中基可行解，进而找出最优解。但如果变量和方程较多，比如m=50，n=100，所有基解有可能达1029个，即使计算机每秒能求解1亿个这样的方程组，也需要30万亿年

9、！因此，必须寻求有效的算法。 为加快计算速度，算法必须具有两个功能，一是每得到一个基可行解，就能检验是否已经最优，若是，停止。二是若不是最优，要保证下一步得到的基可行解不劣于当前解。基于线性代数原理，并将上述功能贯穿于算法过程，这就是线性规划的单纯形法。,一、基本思想,38,化LP问题为标准型， 确定一个初始基可行解,结束,Y,旋转运算（枢轴运算） 确定另一个基可行解,N,基本思路：化LP问题为标准型，从可行域的某个基可行解（一个顶点）开始，转换到另一个基可行解（另一个顶点），并使目标函数值得到改善，如此反复，从而求得问题的最优解。 其实质是逐步迭代（逼近）法。,39,二、基本原理举例,1.

10、初始基可行解的确定,要得到一个初始基可行解，必须找到一个初始可行基。由于典型示例标准化后，x3、x4、x5的系数列向量构成单位矩阵，该矩阵B0是一个基，并且是一个可行基（可以证明，标准化后的单位矩阵一定是可行基）。,例5 (P28,例6),40,令非基变量x10、x2 0，得到基可行解及相应的目标函数值，X(0) (0,0,8,16,12)T， Z(0) 0。 结论： （1）在标准化的LP问题的约束系数矩阵中，只要存在单位矩阵，就可求得初始基可行解； （2）基变量确定后，目标函数和基变量均可表示成非基变量的线性表达式（如(6)和(5)），从而便于求出基可行解及相应的目标函数值。,41,2. 最

11、优性检验,考察变换后的目标函数(6)式，非基变量x1、x2的系数都为正数，若让x1、x2取正值，则目标函数值会增大。因此，应将非基变量x1、x2变换成基变量。 结论： 在非基变量的线性表达式表示的目标函数中，若非基变量的系数（称为检验数）为正，则目标函数值还有增加的可能，表明当前的基可行解不是最优解。,42,3. 确定新的基可行解（基变换）,单纯形法在寻找新的可行基时，是以当前的可行基为基础的，即把当前的可行基中某一列用非基向量替换，从而形成新的可行基。 换入变量：一般选择正系数最大的非基变量为换入变量。 本例为非基变量x2。 换出变量：其依据是 （a）保证换出的变量取值为0，变成非基量； （

12、b）其它的变量取值为非负。,43,当确定x2为换入变量后， x1还是非基变量，故 x10。现在要保证x3、x4、x50，即(5),当 x2 min（8/2，12/4） =3 （最小比值规则） 可保证 x5 =0 则x5为换出变量。 新的基变量为x3、x4、x2 ，新的可行基为B1(P3, P4 , P2),44,4. 旋转迭代,基变量确定后，旋转迭代就是把目标函数和基变量均表示成非基变量x1、x5的线性表达式。可用高斯消去法实现。,令非基变量x10、x5 0，得到新的基可行解及相应的目标函数值，X(1) (0,3,2,16,0)T， Z(1) 9。返回至第二步，直至求出最优解。 将上述方程组求

13、解过程，用列表形式表达，即为线性规划单纯形表。,45,三、最优性检验及解的判别,1. 检验数公式,补充作业2-1 请给出公式（2）的推导过程。,46,47,2. 最优性检验与解的判别,设X(0)=(b1, b2, ,bm,0, ,0)T为对应于基B的一个基可行解。对于最大化问题，最优性检验与解的判别如下： （1）唯一最优解 对于一切 j=m+1, ,n，有sj0，且对i=1, ,m，有ai,m+k0，则该LP问题具有无界解。,48,四、基变换,1. 换入变量的确定,2. 换出变量的确定,则第l个约束方程对应的基变量xl为换出变量。,49,五、迭代运算,例6 迭代运算示例,50,第三节 单纯形表

14、,1. 化LP问题为标准型,建立初始单纯形表;,一、步骤,51,化为标准型,二、实例,52,单纯形表算法,X(0) (0,0,8,16,12)T O点,以1为主元素进行旋转运算，x1为换入变量， x3为换出变量,x1,cj,x2,x3,x4,x5,1,4,0,2,0,4,1,0,0,0,1,0,0,0,1,2,3,0,0,0,b,8,16,12,XB,x3,x4,x5,CB,0,0,0,以4为主元素进行旋转运算，x2为换入变量，x5为换出变量,sj,2,3,0,0,0,qi,8/2,12/4,4,x2,3,主元列,主元行,0,0,0,1/4,3,1,0,1,1,0,-1/2,2,X(1) (0

15、,3,2,16,0)T Q4点,16/4,2/1,1,53,此时达到最优解。X*=(4,2), max Z=14。,x1,2,2,0,-4,1,2,8,0,8/2,12,x5,0,X(3) (4,2,0,0,4)T Q2点,X(2) (2,3,0,8,0)T Q3点,以2为主元素进行旋转运算，x5为换入变量，x4为换出变量,54,一、最小化问题最优解判别,第四节 LP问题的进一步讨论,前面讨论的LP问题都是以最大化目标函数作为标准型的，但也有用最小化目标函数作为LP问题标准型的构成要素的情况。二者的区别如下：,55,二、人工变量法,化为标准型,化标准型时，若找不到单位矩阵，可人为添加非负变量（

16、人工变量）凑成单位矩阵。 因人工变量是虚拟的变量，无任何物理意义，它们的取值最终必须为零，才能保证约束方程不发生变化。 为此，必须把人工变量从基变量中替换出去而变成非基变量，则LP问题有解；若最优解中含有人工变量，则LP问题无可行解。这是LP问题无解的判别条件。,56,加入松弛变量x4;剩余变量x5;人工变量x6,x7,例7 人工变量示例,57,（1） 基本思路,（2）目标函数的处理,（3） 计算,1. 大M法(M为任意大的正数),例8 (P42,例8),58,59,结果得: X*=(4,1,9,0,0) T Z*=-2,（接上表）,60,将LP问题分成两个阶段来考虑,第I 阶段: 不考虑原问

17、题是否存在可行解，给原LP问题加入人工变量，并构造仅含人工变量的目标函数和要求最小化；然后用单纯形法求解，若得W=0，则进行第二阶段计算，否则无可行解。,第II 阶段：将第一阶段得到的最终表除去人工变量，将目标函数行的系数换为原问题的系数，作为第二阶段的初始表。,2. 两阶段法,61,加入松弛变量x4;剩余变量x5;人工变量x6,x7,用单纯形法求解第一阶段的结果得：,例9 (P43,例9) 两阶段法示例,62,此时，达到第一阶段的最优解，W=0,63,由于人工变量x6 =x7=0,所以（0,1,1,12,0）T 是该线性规划问题的基可行解。于是转入第二阶段运算：,此时达到该LP问题的最优解：

18、 X*=(4,1,9,0,0) T; 目标函数值Z*=-2。,64,三、单纯形法中存在的问题,1. 存在两个以上的最大正检验数。选择任何变量（对应最大正检验数）作为换入变量。,2. 最小比值相同。LP问题出现退化现象，即基变量取值为0,65,选取x1为换入变量；按Bland算法，选取下标最小的x5为换出变量。,66,此时换出变量为x1，换入变量为x4，迭代后目标函数值不变，继而出现了循环现象，达不到最优解。,67,解决退化的方法有： “摄动法”、“辞典序法”、 Bland规则等,1974年Bland提出Bland算法规则：,68,3. 最小比值原则失效,经过一次迭代后可得右表,69,70,4.

19、 在最优表中出现某非基变量检验数为0,71,72,结论：若线性规划问题存在某非基变量检验数为0,而其对应列向量Pk0,仍可判断线性规划问题有无穷多最优解。,式中的X* 是否能由单纯形法求得？为什么？,补充作业2-2,若X (1)* 和X (2)*是单纯形法求得的2个最优解，则：,73,第五节 应用举例,应用1：下料问题（书P47 例10） 现要做100套钢架，每套需2.9米、2.1米和1.5米的圆钢各一根。已知原料长7.4米，问如何下料，使用的原料最少（余料最少或根数最少）？,分析： 最简单的做法是：每根7.4米长的原材料各截取三种规格的元钢一根，则料头为0.9米，100套则浪费材料90米。关

20、键是要设计套裁方案，不能有遗漏。,74,解：设 x1, x2 , x3, x4 , x5分别代表五种不同套裁方案的原料用量。,余料最少的LP模型：,75,根数最少的LP模型：,76,应用2：配料问题（书P48 例11） 某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D。已知产品的规格要求、单价和原材料的供应量、单价。该厂应如何安排生产使利润最大？,77,解：根据题意，可将问题简化成如下表格形式：,78,用单纯型法计算得结果：每天只生产A产品200kg。分别需要原料：C为100kg；P为50kg；H为50kg。 总利润收入Z=500元/天.,79,某企业拟用m种资源(i=1,

21、2,m)生产n种产品(j=1,2,n) 。已知第i种资源的数量为bi，其单价为Pi；第j种单位产品的产值为Vj，消耗第i种资源的数量为aij，合同量为ej，最高需求为dj。问企业应如何拟定生产计划？,解：根据题意，设xj (j=1,2,n)为第j种产品的生产量。,应用3：生产计划问题,80,应用4：生产组织问题（书P51 例12）,某快递公司下设的快件分拣部每天负责分拣到达和寄出的快件。每天各时段到达的快件数量如下表：,81,快件由机器自动分拣，共11台，每台500件/h，每台机器需1名操作员。 操作员分为2类。全日制操作员，上班时间点分别为10、11和12点，连续工作8h，工资150元/d。

22、非全日制操作员，上班时间点分别为13、14和15点，连续工作5h，工资80元/d 。 快件处理规则：每个整点可分拣该整点前到达的快件。特殊时限要求是14点需分拣出12点之前到达的所有快件，17点需分拣出15点之前到达的所有快件，20点需分拣出当天到达的所有快件。 问分拣部应设多少名全日制和非全日制操作员，在完成任务的同时，总工资支出最少？,应用4：生产组织问题（书P51 例12）,82,解：根据题意，设x1, x2, x3分别为10,11,12点上班的操作员数量； y1, y2, y3分别为13,14,15点上班的操作员数量。,83,LP模型如下:,最优解:,84,应用5：连续投资问题（书P5

23、3 例13）,某部门在今后5年内连续给以下项目投资： 项目A，第一年至第四年每年年初投资，次年末回收本利 115%； 项目B，第三年初投资，第五年末回收本利 125%，最大投资额不超过4万元； 项目C，第二年初投资，第五年末回收本利 140%，最大投资额不超过3万元； 项目D，五年内每年初可购买公债，当年末归还，并加利息6% 。 该部门现有资金 10万元，问该如何确定投资方案，使第五年末拥有的资金本利和最大？,85,86,应用6：食谱问题,有n种食品(j=1,2,n)，每种食品中含有m种营养成分(i=1,2,m) 。已知第j种食品单价为cj，每天最大供应量为dj，每单位第j种食品中含第i种营养成分的数量为aij。设某种生物每天对第i种营养成分的需求量至少为bi，而每天的进食数量限定在h1, h2之间。问该生物的食谱，使总成本为最小？,解：根据题意，设xj (j=1,2,n)表示每天食用第j种食品的数量。,87,88,应用7：产品配套问题,某厂生产一种产品，由两个B1 零件和三个B2零件配置组装而成。该厂有A1、A2、A3三种机床可加工上述两种零件，每种机床的台数以及每台机床每个工