2.线性规划与单纯形法(宣城)

第二章线性规划与单纯形法本章重点内容线性规划模型与解的主要概念线性规划的单纯形法，线性规划多解分析线性规划的应用——建模1LinearProgramming,LP1939年苏康托洛维奇和1941年美Hichook在生产组织管理和制定交通运输方案方面研究和应用线性规划，求解方法——解乘数法1947年G.B.Dantzig单纯形法1979年苏哈奇安多项式算法（椭球算法）1984年Karmarkar算法多项式时间算法每次迭代不是从一个顶点出发求改进的顶点，而是使迭代点保持在某个单纯形的内部，因此是一种内点算法。第一节线性规划问题及其数学模型2LP是数学规划的一个重要分支，数学规划着重解决资源的优化配置，一般可以表达成以下两个问题中的一个：（1）当资源给定时，要求完成的任务最多；（2）当任务给定时，要求为完成任务所消耗的资源最少。若上述问题的目标﹑约束都能表达成变量的线性关系，则这类优化问题称LP问题。LP是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。3一、实例例1生产计划问题(书P15，典型示例)Step1:明确问题，设定决策变量设I、II两种产品的产量分别为x1,x2。Step2:确定约束条件32利润12公斤40原料B16公斤04原料A8台时21设备资源限量III产品4说明：OBJ表示Objective;s.t.表示SubjecttoStep3:给出目标函数Step4:整理数学模型5例2污水处理问题(书P16)设x1﹑x2为工厂1﹑2的日污水处理量。建立该问题的数学模型为：500万m3200万m31.4万m3，800元/万m3o工厂22万m3，1000元/万m3o工厂16二、总结目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。线性规划问题（LP问题）的共同特征：每一个问题变量都用一组决策变量（x1,x2,…,xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的且在某范围内连续取值。存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。7三、线性规划问题的一般形式8四、两变量线性规划问题的图解法1.线性不等式的几何意义—半平面作出LP问题的可行域作出目标函数的等值线移动等值线到可行域边界得到最优点2.图解法步骤例1（典型示例）：94x1=164x2=12x1+2x2=8x1x2Q6(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)图解法意义不大，但可直观揭示有关概念。103.LP解的类型有4类：（1）唯一最优解如例1的Q2点。（2）无穷多最优解（多重解）（3）无界解（4）无可行解1104812x1963①③②可行域Z=364,6此线段上的点均为最优点x2当例1的目标函数变为maxZ=2x1+4x2多重解示例8,312x2可行域不闭合②Z增大方向①x1无界解示例13产生原因：缺少约束条件注意：可行域不闭合不一定就会出现无界解，这要看目标函数的性质。若目标函数是min，则有最优解。无论有无最优解，一定有可行解。14无可行解示例①③④无公共区域(可行域)产生原因：有相互矛盾的约束条件。②x2x1154.图解法的作用LP问题有可行解有最优解唯一解无穷多解无最优解（可行域为无界）无可行解（无解）（1）规律：揭示了线性规划问题有关规律和结论。（2）结论：若LP问题有最优解，则要么最优解唯一（对应其中一个顶点），要么有无穷多最优解（对应其中两个顶点连线上的所有点）。16五、线性规划问题的标准型1.标准型的构成要素（1）目标函数：max（2）约束条件：等式（3）变量约束：非负xj0（4）资源限量：非负bi0172.标准型的表示方法（1）解析式18简写的解析式19亦可写成：其中：（2）矩阵式20X—决策变量列向量。b—约束条件右端常数（资源）列向量。C—目标函数价值系数行向量。Am´n—约束条件左端系数矩阵。21（3）向量和矩阵符号式223.非标准型的标准化（1）最小转换成最大y1=f(x)y2=-f(x)xyx*y1*y2*23（2）不等式约束条件转换成等式约束条件（3）变量约束转换24。，即方程两边同乘以－－－则，，即若1000ijijijijibxabxab（4）把bi0转换成bi025例3(P20)可化为26例4(P21)化下列LP为标准型2728六、标准型LP问题的解1.基本概念29303132334x1=164x2=12x1+2x2=8x1x2Q6(0,4)Q7(8,0)Q4(0,3)O(0,0)Q2(4,2)Q1(4,0)Q3(2,3)Q5(4,3)Q7基解x2，x3x5=12x4=－16x1=8Q6基解x1，x3x5=－4x4=16x2=4Q5基解x4，x5x3=－2x2=3x1=4Q4基可行解x1，x5x4=16x3=2x2=3Q3基可行解x3，x5x4=8x2=3x1=2Q2基可行解最优解x3，x4x5=5x2=2x1=4Q1基可行解x2，x4x5=12x3=4x1=4K可行解x1=2,x2=2,x3=2,x4=8,x5=4O基可行解x1，x2x5=12x4=16x3=8图中的点及对应的解非基变量基变量K•2.可行解、基解和基可行解举例典型示例标准化后有3个约束条件、5个决策变量，基的最大个数可达C53=10个，但实际上只有8个。34约束方程的解空间基解可行解非可行解基可行解3.LP标准型问题解的关系354.LP标准型问题解的结论根据LP的图解法及解的基本概念可知：基解对应约束条件的交点；基可行解对应可行域的顶点某个基可行解一定是最优解，即一定在可行域的顶点上得到最优解。36第二节单纯形法SimplexMethod由线性代数知，对LP标准型问题，理论上可以求出所有基解（枚举法），再通过观察找出其中基可行解，进而找出最优解。但如果变量和方程较多，比如m=50，n=100，所有基解有可能达1029个，即使计算机每秒能求解1亿个这样的方程组，也需要30万亿年！因此，必须寻求有效的算法。为加快计算速度，算法必须具有两个功能，一是每得到一个基可行解，就能检验是否已经最优，若是，停止。二是若不是最优，要保证下一步得到的基可行解不劣于当前解。基于线性代数原理，并将上述功能贯穿于算法过程，这就是线性规划的单纯形法。一、基本思想37化LP问题为标准型，确定一个初始基可行解检验解的最优性结束Y旋转运算（枢轴运算）确定另一个基可行解N基本思路：化LP问题为标准型，从可行域的某个基可行解（一个顶点）开始，转换到另一个基可行解（另一个顶点），并使目标函数值得到改善，如此反复，从而求得问题的最优解。其实质是逐步迭代（逼近）法。38二、基本原理举例1.初始基可行解的确定要得到一个初始基可行解，必须找到一个初始可行基。由于典型示例标准化后，x3、x4、x5的系数列向量构成单位矩阵，该矩阵B0是一个基，并且是一个可行基（可以证明，标准化后的单位矩阵一定是可行基）。例5(P28,例6)39令非基变量x1＝0、x2＝0，得到基可行解及相应的目标函数值，X(0)＝(0,0,8,16,12)T，Z(0)＝0。结论：（1）在标准化的LP问题的约束系数矩阵中，只要存在单位矩阵，就可求得初始基可行解；（2）基变量确定后，目标函数和基变量均可表示成非基变量的线性表达式（如(6)和(5)），从而便于求出基可行解及相应的目标函数值。402.最优性检验考察变换后的目标函数(6)式，非基变量x1、x2的系数都为正数，若让x1、x2取正值，则目标函数值会增大。因此，应将非基变量x1、x2变换成基变量。结论：在非基变量的线性表达式表示的目标函数中，若非基变量的系数（称为检验数）为正，则目标函数值还有增加的可能，表明当前的基可行解不是最优解。413.确定新的基可行解（基变换）单纯形法在寻找新的可行基时，是以当前的可行基为基础的，即把当前的可行基中某一列用非基向量替换，从而形成新的可行基。换入变量：一般选择正系数最大的非基变量为换入变量。本例为非基变量x2。换出变量：其依据是（a）保证换出的变量取值为0，变成非基量；（b）其它的变量取值为非负。42当确定x2为换入变量后，x1还是非基变量，故x1＝0。现在要保证x3、x4、x50，即(5)当x2＝min（8/2，—，12/4）=3（最小比值规则）可保证x5=0则x5为换出变量。新的基变量为x3、x4、x2，新的可行基为B1＝(P3,P4,P2)434.旋转迭代基变量确定后，旋转迭代就是把目标函数和基变量均表示成非基变量x1、x5的线性表达式。可用高斯消去法实现。令非基变量x1＝0、x5＝0，得到新的基可行解及相应的目标函数值，X(1)＝(0,3,2,16,0)T，Z(1)＝9。返回至第二步，直至求出最优解。将上述方程组求解过程，用列表形式表达，即为线性规划单纯形表。44三、最优性检验及解的判别1.检验数公式补充作业2-1请给出公式（2）的推导过程。45462.最优性检验与解的判别设X(0)=(b1,b2,…,bm,0,…,0)T为对应于基B的一个基可行解。对于最大化问题，最优性检验与解的判别如下：（1）唯一最优解对于一切j=m+1,…,n，有sj0，则X(0)为唯一最优解。（2）无穷多最优解对于一切j=m+1,…,n，有sj0，且至少有一个sm+k=0，则该LP问题有无穷多最优解，X(0)为其中之一。（3）无界解在j=m+1,…,n中，至少有一个sm+k0，且对i=1,…,m，有ai,m+k0，则该LP问题具有无界解。47四、基变换1.换入变量的确定2.换出变量的确定则第l个约束方程对应的基变量xl为换出变量。48五、迭代运算例6迭代运算示例49第三节单纯形表1.化LP问题为标准型,建立初始单纯形表;一、步骤50化为标准型二、实例51单纯形表算法X(0)＝(0,0,8,16,12)TO点以[1]为主元素进行旋转运算，x1为换入变量，x3为换出变量0qi300x5x2x3x40x4x3XBbsj0x1CB2cjx1cjx2x3x4x514020410001000123000b81612XBx3x4x5CB000以[4]为主元素进行旋转运算，x2为换入变量，x5为换出变量sj23000qi8/2—12/4[4]x23主元列主元行0001/43140101600110-1/22X(1)＝(0,3,2,16,0)TQ4点200-3/4016/42/1—[1]52此时达到最优解。X*=(4,2),maxZ=14。0qi300x5x2x3x40x4x23XBbsjx1CB2cj0qi300x5x2x3x4x23x1XBbsj2x1CB2cj0001/4310-201/40x120110-1/22[2]0-412808/212—x500-21/2140101/40401/2-1/800210-3/2-1/800X(3)＝(4,2,0,0,4)TQ2点X(2)＝(2,3,0,8,0)TQ3点以[2]为主元素进行旋转运算，x5为换入变量，x4为换出变量53一、最小化问题最优解判别第四节LP问题的进一步讨论前面讨论的LP问题都是以最大化目标函数作为标准型的，但也有用最小化目标函数作为LP问题标准型的构成要素的情况。二者的区别如下：按最小比值规则maxZ=CXAX=b，X0minZ=CXAX=b，X000min{sj|sj0}max{sj|sj0}换入变量xk换出变量xl最优解的sj标准型比较条目54二、人工变量法化为标准型化标准型时，若找不到单位矩阵，可人为添加非负变量（人工变量）凑成单位矩阵。因人工变量是虚拟的变量，无任何物理意义，它们的取值最终必须为零，才能保证约束方程不发生变化。为此，必须把人工变量从基变量中替换出去而变成非基变量，则LP问题有解；若最优解中含有人工变量，则LP