第01章线性规划及单纯形法(胡运权)

第一章线性规划及单纯形法,线性规划及单纯形法,线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论数据包络分析其他应用例子,1线性规划问题,问题的提出线性规划问题的数学模型线性规划概念和模型,问题的提出,例1美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。表1-1,数学模型,例1中先用变量x1和x2分别表示美佳公司制造家电和的数量。这时该公司可获取的利润为(2x1+x2)元，令z=2x1+x2，因问题中要求获取的利润为最大，即maxz。z是该公司能获取的利润的目标值，它是变量x1，x2的函数，称为目标函数。x1，x2的取值受到设备A、B和调试工序能力的限制，用于描述限制条件的数学表达式称为约束条件。由此例1的数学模型可表为：,数学模型,max:maximize的缩写，“最大化”，s.t.subjectto的缩写，“受限制于”,问题的提出,例2捷运公司在下一年度的14月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。,数学模型,例2中若用变量xij表示捷运公司在第i(i=1,4)个月初签订的租借期为j(j=1,4)个月的仓库面积的合同。因5月份起该公司不需要租借仓库，故x24，x33，x34，x42，x43，x44均为零。该公司希望总的租借费用为最小，故有如下数学模型：,min：minimize，“最小化”,概念和模型,定义：对于求取一组变量xj(j=1,2,.,n)，使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。,max（或min）,概念和模型,一般形式：,max（或min）,目标函数,约束条件,非负约束,称为决策变量,称为价值系数或目标函数系数,称为资源常数或约束右端常数,称为技术系数或约束系数,概念和模型,紧缩形式：,max（或min）,概念和模型,矩阵形式：,max（或min）,称为决策变量向量,称为价值系数向量或目标函数系数向量,称为资源常数向量或约束右端常数向量,称为技术系数或约束系数矩阵,标准形式,标准型的主要特征：目标最大；约束等式；变量非负；右端非负。,标准型,标准型的紧缩形式：,标准型的矩阵形式：,标准型,标准型的向量形式：,其中：,标准化,把一般的LP化成标准型的过程称为线性规划问题的标准化方法：1目标标准化minZ等价于max(-Z)maxZ=-cjxj2化约束为等式加松弛变量、减剩余变量3变量非负化做变换或4右端非负,标准化,标准化举例（例3）：,线性规划及单纯形法,线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论数据包络分析其他应用例子,2图解法,1什麽是图解法？线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。求解的思路是：先将约束条件加以图解，求得满足约束条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。,图解法,2.图解法(例1),运用图解法，以求出最优生产计划（最优解）。,图解法,由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可以进行图解了。,1.建立平面直角坐标系，标出坐标原点,坐标轴的指向和单位长度。2.对约束条件加以图解，找出可行域。3.画出目标函数等值线。4.结合目标函数的要求求出最优解。,图解法,图解法,(a)可行域有界(b)可行域有界(c)可行域无界唯一最优解多个最优解唯一最优解,(d)可行域无界(e)可行域无界(f)可行域为空集多个最优解目标函数无界无可行解,线性规划及单纯形法,线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论数据包络分析其他应用例子,3单纯形法原理,线性规划问题的解的概念凸集及其顶点几个基本定理,解的概念,可行解：变量满足所有约束条件的一组值可行解集：所有可行解构成的集合可行域：可行解集构成n维空间的区域,线性规划问题,解的概念,最优解：使得目标函数达到最优的可行解最优值：最优解对应的目标函数值目的：求最优解和最优值求解方法：单纯形法,解的概念,先研究AX=b设系数矩阵A是mn矩阵，秩为m，B是A中mm阶非奇异子矩阵（即|B|0），则称B是线性规划问题的一个基。B是由m个线性独立的列向量组成,基向量,基变量,非基变量：其余变量,解的概念,AX=BXB+NXN=b令非基变量XN=0得BXB=b和特解XB=B-1b结合XN=0称为对应于B的基本解；基本解个数=基的个数Cnm基可行解可行的基本解XB0XN=0可行基：对应于基可行解的基,A=（B|N）,解的概念,最优基：对应的基本可行解也是最优基本可行解个数基的个数Cnm基本可行解的非零分量均为正分量，其正分量个数m。退化的基本可行解：基本可行解的非零分量个数小于m时，也就是在基本可行解中一个或多于一个的基变量取零值时,凸集及其顶点,1、基本概念：凸集设K是n维欧氏空间的一个点集，若任意两点X（1）K，X（2）K的连线上的一切点：X（1）+（1-）X（2）K（01），则称K为凸集。,凸集的概念,顶点设K是凸集，XK；若K中不存在两个不同的点X（1）K，X（2）K使X=X（1）+（1-）X（2）（027/4=Z(0)此时非基变量检验数均为负，解最优,单纯形法一般步骤,1.初始基本可行解的确定（观察法）；,单纯形法一般步骤,1.初始基本可行解的确定（观察法）；,基,基本可行解,单纯形法一般步骤,2.从约束中解出基变量；,单纯形法一般步骤,3.代入目标消去基变量，得到非基变量xj的检验数j；,单纯形法一般步骤,3.代入目标消去基变量，得到非基变量xj的检验数j；,单纯形法一般步骤,4.判断最优；最优性判别定理：若是对应于B的基本可行解，j是用非基变量表示目标函数的表达式中非基变量xj的检验数，若对于一切非基变量的角指数j均有j0则当前基本可行解为最优解。,对于任意可行解X，,对于基本可行解X0，,单纯形法一般步骤,5.没有有限最优解的判断；无最优解判别定理：若是对应于B的基本可行解，非基变量xk的检验数k0,且对于i=1,2,m均有aik0,则问题没有有限最优解。,单纯形法一般步骤,6.改进目标若k0，则选xk进基;用最小比值法确定xk的最大值，使基变量xl取0值，其它基变量非负；,即xl出基，目标改善k，换基过程若不存在,则Z，没有有限最优解。,单纯形法一般步骤,7.主元变换（枢变换或旋转变换）xk进基，xl出基，解出新的基变量,5表格单纯形法,标准型：,表格单纯形法,标准型：,表格单纯形法,表格单纯形法,基变量,检验数,最小比值列,基变量系数,右端常数,解：,表1-7,表1-9中所有j=0,且基变量中不含人工变量，最优解X=(7/2,3/2,15/2,0,0);最优值Z=17/2.,练习1：求解线性规划,表格单纯形法,向右迭代一步,练习2：求解线性规划,表格单纯形法,没有有限最优解,算法思路,求一个初始基本可行解是判断基本可行解是否最优结束不是求使目标得到改善的基本可行解,是否存在？如何得到？,是否唯一？,如何判断？,如何改善？如何判断没有有限最优解？,5单纯形法进一步讨论,处理方法一大法,人造基添加人工变量造成基去掉人工变量,5单纯形法进一步讨论,原问题的可行解新问题的可行解目标值,结论：新问题的最优解中，如果人工变量均为零，则得到的解也是原问题的最优解，否则原问题无可行解,例6大M法,最优解:X=(0,5/2,3/2,0,0,0,0)最优值：Z=3/2,大M法举例,所有检验数0已经是最优解x5=2人工变量不为零,表示原问题无可行解参照图解法结果,5单纯形法进一步讨论,处理方法二两阶段法,人造基添加人工变量造成基去掉人工变量,两阶段法,如果线性规划问题中的aij、bi或cj等参数值与这个代表M的数相对比较接近，或远远小于这个数字，由于计算机计算时取值上的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。,5单纯形法进一步讨论,第一阶段,第一阶段最优解中:如果Z0,则原问题没有基本可行解;如果Z=0,则若人工变量全为非基变量,则得到原问题的基本可行解.否则基本可行解退化,继续迭代就可以得到基本可行解.,5单纯形法进一步讨论,第二阶段,以第一阶段最优基作为初始基本可行解,继续迭代.,第一阶段,例6两阶段法,第一阶段：,请注意:第一阶段的最优解不是唯一的,第二阶段,单纯形法矩阵描述,单纯形法矩阵描述,单纯形法矩阵描述,几点注意事项,检验数的计算；进基变量的选取；若有不止一个变量可以进基时,只取一个；最小比值；若有不止一个最小比值时，只能选取其中之一行对应的基变量出基；没有有限最优解的情况；最优解是否唯一；最优表中非基变量检验数等于零时,可能最优解不唯一。,线性规划及单纯形法,线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论数据包络分析其他应用例子,数据包络分析(DataEnvelopmentAnalysis,DEA),6数据包络分析,根据多项投入指标和多项产出指标,利用线性规划的方法,对具有可比性的同类型单位进行相对有效性评价的一种数量分析方法。,生产前沿面,DEA有效,在DEA中通常称被衡量绩效的组织为决策单元（decisionmakingunit,DMU)。,数学模型,当求解结果有E1时，则j0决策单元非DEA有效，否则j0决策单元DEA有效。,例8振华银行的4个分理处的投入产出情况如表1-16所示。要求分别确定各分理处的运行是否DEA有效。,解先确定分理处1的运行是否DEA有效。线性规划模型如下：,求解结果为E=1，说明分理处1的运行为DEA有效。,同理计算其他三个分理处的E值，结果为分理处3和分理处4，E=1；,此时1=028,3=0.72,2=4=0,即分理处2运行非DEA有效。理由为：若将28%的分理处1同72%分理处3组合，其各项产出不低于分理处2的各项产出，但其投入只有分理处2的96.6%。,对于分理处2，有E=0.966；,线性规划及单纯形法,线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论数据包络分析其他应用例子,例9混合配料问题某糖果厂用原料A，B，C加工成三种不同牌号