运筹学-线性规划

第一章线性规划(LinearProgramming),线性规划问题及数学模型单纯形法的原理单纯型法的步骤LP问题的进一步讨论应用举例,第一节线性规划问题及数学模型LinearProgramming,LP1939年苏康托洛维奇1941年美Hichook1947年丹捷格（G.B.Dantzig）单纯形法1979年苏哈奇安算法1984年Karmarkar算法,LP是数学规划的一个重要分支，数学规划着重解决资源的优化配置，一般可以表达成以下两个问题中的一个：（1）当资源给定时，要求完成的任务最多；（2）当任务给定时，要求为完成任务所消耗的资源最少。若上述问题的目标约束都能表达成变量的线性关系，则这类优化问题称LP问题。LP是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。,一、实例,例1生产计划问题(书P8，典型示例),Step1:明确问题，设定决策变量设I、II两种产品的产量分别为x1,x2。,Step2:确定约束条件,说明：OBJ表示Objective;s.t.表示Subjectto,Step3:给出目标函数,Step4:整理数学模型,例2污水处理问题(书P9),设x1x2为工厂12的日污水处理量。建立该问题的数学模型为：,练习：捷运公司在下一年度的14月份的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于下表1。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表2。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租用期限不同的合同。试确定该公司签订租借合同的最优决策，目的是使所租借费用最少。,表1各月份所需仓库面积,表2,单位：100m2,单位：元/100m2,解：设表示捷运公司在第i(i=1,2,3,4)月初签订的租期为j(j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。,15,10,20,12,经过上面的讨论，得到下面的LP模型：,OBJ目标函数,约束条件,二、总结,目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。,线性规划问题（LP问题）的共同特征：,每一个问题变量都用一组决策变量（x1,x2,xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的且在某范围内连续取值。,存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。,三、线性规划问题的一般形式,四、两变量线性规划问题的图解法,1.线性不等式的几何意义半平面,作出LP问题的可行域作出目标函数的等值线移动等值线到可行域边界得到最优点,2.图解法步骤,例1（典型示例）：,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),图解法意义不大，但可直观揭示有关概念。,3.LP解的类型,有4类：（1）唯一最优解如例1的Q2点。（2）无穷多最优解（多重解）（3）无界解（4）无可行解,04812x1,963,可行域,Z=36,4,6,此线段上的点均为最优点,x2,当例1的目标函数变为maxZ=2x1+4x2,无穷多最优解示例,8,3,x2,可行域不闭合,Z增大方向,x1,无界解示例,产生原因：缺少约束条件注意：可行域不闭合不一定就会出现无界解，这要看目标函数的性质。若目标函数是min，则有最优解。无论有无最优解，一定有可行解。,无可行解示例,无公共区域(可行域)产生原因：有相互矛盾的约束条件。,x2,x1,4.图解法的作用,LP问题,有可行解,有最优解,唯一解无穷多解,无最优解（可行域为无界）,无可行解（无解）,（1）规律：,揭示了线性规划问题有关规律和结论。,（2）结论：若LP问题有最优解，则要么最优解唯一（对应其中一个顶点），要么有无穷多最优解（对应其中两个顶点连线上的所有点）。,0,12345678,123456,最优解：x1=4x2=2,有唯一最优解，Z=14,x2,x1,(42),练习：用图解法求解,例2,例3,无穷多最优解,无界解,x1,x1,x2,x2,x1,x2,无可行解,例4,五、线性规划问题的标准型,1.标准型的构成要素,（1）目标函数：max,（2）约束条件：等式,（3）变量约束：非负xj0,（4）资源限量：非负bi0,2.标准型的表示方法,（1）解析式,简写的解析式,亦可写成：,其中：,（2）矩阵式,X决策变量列向量。b约束条件右端常数（资源）列向量。C目标函数价值系数行向量。Amn约束条件左端系数矩阵。,（3）向量和矩阵符号式,3.非标准型的标准化,（1）最小转换成最大,（2）不等式约束条件转换成等式约束条件,（3）变量约束转换,（4）把bi0转换成bi0,例1,可化为,例2化标准型,课堂作业1,六、标准型LP问题的解,1.基本概念,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个。,约束方程的解空间,基解,可行解,非可行解,基可行解,3.LP标准型问题解的关系,4.LP标准型问题解的结论,根据LP的图解法及解的基本概念可知：基解对应约束条件的交点；基可行解对应可行域的顶点最优解一定是基可行解，一定在可行域的顶点上得到。,第二节单纯形法SimplexMethod,由线性代数知，对LP标准型问题，理论上可以求出所有基解（枚举法），再通过观察找出其中基可行解，进而找出最优解。但如果变量和方程较多，比如m=50，n=100，所有基解有可能达1029个，即使计算机每秒能求解1亿个这样的方程组，也需要30万亿年！因此，必须寻求有效的算法。为加快计算速度，算法必须具有两个功能，一是每得到一个基可行解，就能检验是否已经最优，若是，停止。二是若不是最优，要保证下一步得到的基可行解不劣于当前解。基于线性代数原理，并将上述功能贯穿于算法过程，这就是线性规划的单纯形法。,一、基本思想,化LP问题为标准型，确定一个初始基可行解,检验解的最优性,结束,Y,旋转运算（枢轴运算）确定另一个基可行解,N,基本思路：化LP问题为标准型，从可行域的某个基可行解（一个顶点）开始，转换到另一个基可行解（另一个顶点），并使目标函数值得到改善，如此反复，从而求得问题的最优解。其实质是逐步迭代（逼近）法。,二、基本原理举例,1.初始基可行解的确定,要得到一个初始基可行解，必须找到一个初始可行基。由于典型示例标准化后，x3、x4、x5的系数列向量构成单位矩阵，该矩阵B0是一个基，并且是一个可行基（可以证明，标准化后的单位矩阵一定是可行基）。,令非基变量x10、x20，得到基可行解及相应的目标函数值，X(0)(0,0,8,16,12)T，Z(0)0。结论：（1）在标准化的LP问题的约束系数矩阵中，只要存在单位矩阵，就可求得初始基可行解；（2）基变量确定后，目标函数和基变量均可表示成非基变量的代数和形式（如(6)和(5)），从而便于求出基可行解及相应的目标函数值。,2.最优性检验,考察变换后的目标函数(6)式，非基变量x1、x2的系数都为正数，若让x1、x2取正值，则目标函数值会增大。因此，应将非基变量x1、x2变换成基变量。结论：在非基变量的代数和形式表示的目标函数中，若非基变量的系数（称为检验数）为正，则目标函数值还有增加的可能，表明当前的基可行解不是最优解。,3.确定新的基可行解（基变换）,单纯形法在寻找新的可行基时，是以当前的可行基为基础的，即把当前的可行基中某一列用非基向量替换，从而形成新的可行基。确定换入变量：一般选择正系数最大的非基变量为换入变量。本例为非基变量x2。确定换出变量：其依据是（a）保证换出的变量取值为0，变成非基量；（b）其它的变量取值为非负。,当确定x2为换入变量后，x1还是非基变量，故x10。现在要保证x3、x4、x50，即(5),当x2min（8/2，12/4）=3（最小比值规则）可保证x5=0则x5为换出变量。新的基变量为x3、x4、x2，新的可行基为B1(P3,P4,P2),4.旋转迭代,基变量确定后，旋转迭代就是把目标函数和基变量均表示成非基变量x1、x5的代数和形式。可用高斯消去法实现。,令非基变量x10、x50，得到新的基可行解及相应的目标函数值，X(1)(0,3,2,16,0)T，Z(1)9。返回至第二步，直至求出最优解。将上述方程组求解过程，用列表形式表达，即为线性规划单纯形法。,三、最优性检验及解的判别,1.检验数公式,课堂作业2：请给出教科书p23公式（1-25）的推导过程。,2.最优性检验与解的判别,设X(0)=(b1,b2,bm,0,0)T为对应于基B的一个基可行解。对于最大化问题，最优性检验与解的判别如下：（1）唯一最优解对于一切j=m+1,n，有j0，则X(0)为唯一最优解。（2）无穷多最优解对于一切j=m+1,n，有j0，且至少有一个m+k=0，则该LP问题有无穷多最优解，X(0)为其中之一。（3）无界解在j=m+1,n中，至少有一个m+k0，且对i=1,m，有ai,m+k0，则该LP问题具有无界解。,四、基变换,1.换入变量的确定,2.换出变量的确定,则第l个约方程对应的基变量xl为换出变量。,五、迭代运算,第三节单纯型法的步骤,1.化LP问题为标准型,建立初始单纯型表;,一、步骤,化为标准型,二、实例,单纯型表算法,X(0)(0,0,8,16,12)TO点,以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为换出变量,j,2,3,0,0,0,i,8/2,12/4,4,x2,3,主元列,主元行,0,0,0,1/4,3,1,0,1,1,0,-1/2,2,X(1)(0,3,2,16,0)TQ4点,16/4,2/1,1,此时达到最优解。X*=(4,2),maxZ=14。,x1,2,2,0,-4,1,2,8,0,8/2,12,x5,0,X(3)(4,2,0,0,4)TQ2点,X(2)(2,3,0,8,0)TQ3点,以2为主元素进行旋转运算，x5为换入变量，x4为换出变量,一、最小化问题最优界判别,第四节LP问题的进一步讨论,前面讨论的LP问题都是以最大化目标函数作为标准型的，但也有用最小化目标函数作为LP问题标准型的构成要素的情况。二者的区别如下：,二、人工变量法,化为标准型,化标准型时，若找不到单位矩阵，可人为添加非负变量（人工变量）凑成单位矩阵。因人工变量是虚拟的变量，无任何物理意义，它们的取值最终必须为零，才能保证约束方程不发生变化。为此，必须把人工变量从基变量中替换出去而变成非基变量，则LP问题有解；若最优解中含有人工变量，则LP问题无可行解。这是LP问题无解的判别条件。,加入松弛变量x4;剩余变量x5;人工变量x6,x7,（1）基本思路,（2）目标函数的处理,（3）计算,1.大M法(M为任意大的正数),结果得:X*=(4,1,9,0,0)TZ*=-2,（接上表）,将LP问题分成两个阶段来考虑,第I阶段:不考虑原问题是否存在可行解，给原LP问题加入人工变量，并构造仅含人工变量的目标函数和要求最小化；然后用单纯型法求解，若得W=0，则进行第二阶段计算，否则无可行解。,第II阶段：将第一阶段得到的最终表除去人工变量，将目标函数行的系数换为原问题的系数，作为第二阶段的初始表。,2.两阶段法,加入松弛变量x4;剩余变量x5;人工变量x6,x7,用单纯形法求解第一阶段的结果得：,此时，达到第一阶段的最优解，W=0,由于人工变量x6=x7=0,所以（0,1,1,12,0）T是该线性规划问题的基可行解。于是转入第二阶段运算：,此时达到该LP问题的最优解：X*=(4,1,9,0,0)T;目标函数值Z*=-2。,三、单纯型法中存在的问题,1.存在两个以上的最大正检验数。选择任何变量（对应最大正检验数）作为换入变量。,2.最小比值相同。LP问题出现退化现象，即基变量取值为0,选取x1为换入变量；按Bland算法，选取下标最小的x5为换出变量，得下表：,此时换出变量为x1，换入变量为x4，迭代后目标函数值不变，继而出现了循环现象，达不到最优解。,解决退化的方法有：“摄动法”、“辞典序法”、Bland规则等,1974年Bland提出Bland算法规则：,3.最小比值原则失效,经过一次迭代后可得右表,4.在最优表中出现某非基变量检验数为0,结论：若线性规划问题存在某非基变量检验数为0,而其对应列向量Pk0,仍可判断线性规划问题有无穷多最优解。,式中的X*是否能全部由单纯形法求得？,课堂作业3,第五节应用举例,应用1：下料问题（书P38例10）现要做100套钢架，每套需2.9米、2.1米和1.5米的圆钢各一根。已知原料长7.4米，问如何下料，使用的原料最少（余料最少或根数最少）？,分析：最简单的做法是：每根7.4米长的原材料各截取三种规格的元钢一根，则料头为0.9米，100套则浪费材料90米。关键是要设计套裁方案，不能有遗漏。,解：设x1,x2,x3,x4,x5分别代表五种不同的原料用量方案。,余料最少的LP模型：,根数最少的LP模型：,应用2：配料问题（书P38例11）某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、C。已知产品的规格要求、单价和原材料的供应量、单价。该厂应如何安排生产使利润最大？,解：根据题意，可将问题简化成如下表格形式：,用单纯型法计算得结果：每天只生产A产品200kg。分别需要原料：C为100kg；P为50kg；H为50kg。总利润收入Z=500元/天.,例1：某企业拟用m种资源(i=1,2,m)生产n种产品(j=1,2,n)。已知第i种资源的数量为bi，其单价为Pi；第j种单位产品的产值为Vj，消耗第i种资源的数量为aij，合同量为ej，最高需求为dj。问企业应如何拟定生产计划？,解：根据题意，设xj(j=1,2,n)为第j种产品的生产量。,应用3：生产计划问题,例2（书P41例12）市场要求：1)产品数量和品种；2)产品交货期不同。生产要求：1)设备均衡且满负荷生产；2)生产技术准备需要时间。,以一月份内各种设备的生产能力总和为分母,生产产品所需要的各类设备的总台时数为分子,可计算出一月份的平均设备利用系数Z,将Z作为目标函数,可得下面的模型:,先考虑一月份的线性规划模型:,考虑二月份线性规划模型时:(1)从全年计划中减去一月份已生产的数量;(2)对批量小的产品,如一月份已经安排较大产量的,二月份将剩余部分安排生产;(3)保证第4种产品在月底前交货。,这样,我们可以依次对12个月列出线性规划模型并求解,再根据具体情况对计算结果进行必要调整。,应用4：连续投资问题（书P42例13）,某部门在今后5年内连续给以下项目投资：项目A，第一年至第四年每年年初投资，次年末回收本利115%；项目B，第三年初投资，第五年末回收本利125%，最大投资额不超过4万元；项目C，第二年初投资，第五年末回收本利140%，最大投资额不超过3万元；项目D，五年内每年初可购买公债，当年末归还，并加利息6%。该部门现有资金10万元，问该如何确定投资方案，使第五年末拥有的资金本利和最大？,应用5：食谱问题,有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种食品的数量。,应用6：产品配套问题,某厂生产一种产品，由两个B1零件和三个B2零件配置组装而成。该厂有A1、A2、A3三种机床可加工上述两种零件，每种机床的台数以及每台机床每个工作日全部用于加工某一种零件的最大产量（即生产率：件/日）见下表。试求该产品产量最大的生产方案。,难点：1)同一台机床加工零件B1和B2的时间分配；2)零件B1和B2的配套问题，2:3构成一件产品。,解：（1）决策变量根据题意，设每台Ai(i=1,2,3)机床每个工作日加工Bj(j=1,2)零件的时间为xij(工作日)；Z为零件B1和B2按2:3比例配套的产品数量（套/日）。（2）约束条件工时约束：机床A1：x11+x