运筹学第1章教材课件学习资料

第1章线性规划1.1线性规划问题与模型1.2图解法1.3普通单纯形法1.4大M法和两阶段法1.1线性规划问题与模型线性规划((LinearProgramming,LP)是运筹学的重要分支之一，应用非常广泛。由于线性规划是学习其他运筹学分支内容的重要基础，其方法也较为成熟，因此在各类教材中都是最先学习的内容。线性规划通常研究资源的最优利用、设备最佳运行以及费用最低等问题，一般可以解决两大类问题:①已知资源求利润最大化;②已知任务求成本最小化。1.1.1问题举例(1)生产计划问题。生产计划问题是典型的已知资源求利润最大化的问题，对于此类问题通常有三个假设:①在某一计划期内对生产做出的安排;②生产过程的损失忽略不计;③市场需求无限制，即假设生产的产品全部卖出。下一页返回例1用一块连长为a的正方形铁皮做一个容器，应如何裁剪，使做成的窗口的容积为最大？要使容积最大，就是要确定X的值，使V达到最大。1.一般线性规划问题的数学模型例2生产计划问题产品1产品2资源限量原材料A/kg4016原材料B/kg0412设备/台128单位产品利润2元3元练习：某煤油厂每季度需供应给合同单位汽油15万吨、煤油12万吨、重油12万吨.该厂计划从A，B两处运回原油提炼，已知两处的原油成分含量见下表，又已知从A处采购的原油价格（包括运费）为每吨200元，B处采购的原油价格（包括运费）为每吨290元，问：该炼油厂该如何从A,B两处采购原油，在满足供应合同的条件下，使购买成本最小？AB汽油15%50%煤油20%30%重油50%15%其他15%5%解：设分别表示从A,B两处采购的原油量（单位：吨），则所有的采购方案的最优方案为：1.1线性规划问题与模型1.1.2一般模型(1)模型要素。线性规划问题的数学模型包括三大要素:①一组决策变量(x1，x2，…xn)，即模型中需要确定的未知量。②一组约束条件，即资源限制条件以及决策变量受到的约束限制，包括两个部分:不等式组或方程组;决策变量的取值范围。③一个目标函数，是关于决策变量的最优函数，求max或min。(2)模型的一般形式。假设模型有n个决策变量，m个约束条件，则线性规划问题模型的一般形式为下一页返回上一页1.1线性规划问题与模型max(min)Z=c1x1+c2x2+…+cnxn下一页返回上一页1.1线性规划问题与模型可简写为下一页返回上一页1.1线性规划问题与模型进一步化简为线性规划模型也经常写成矩阵或向量形式:下一页返回上一页1.1线性规划问题与模型其中，X=(x1，x2，…xn)T;C=(c1，c2，…cn)为价值向量,Cj为价值系数;A为技术矩阵，aij为技术系数(或工艺系数)。价值向量b=(x1，x2，…xn)T。A也可写成A=(P1，P2，…Pn)，其中P1=(a11，a21，…am1)T,P2=(a12，a22，…am2)T,…Pn=(a1n，a2n，…amn)T。下一页返回上一页1.1线性规划问题与模型在实际问题中决策变量的取值范围通常为非负，但对于模型本身来说，可以是xj≤0。或xj无符号限制(取值无约束)。模型(1-2)之所以是线性规划问题模型，是因为它具有以下特征:①解决的问题是规划问题;②目标函数是关于决策变量的线性表达式(求最大值或最小值);③约束条件是关于决策变量的线性不等式或等式。返回上一页1.2图解法图解法就是利用几何图形求解两个变量线性规划问题的方法，具有简单、直观的特点，但只适用于两个变量的线性规划((LP)问题，这是图解法的局限性。图解法虽然不能解决三个以上变量的线性规划问题，但通过学习图解法，可以帮助我们掌握求解线性规划问题的思路以及线性规划问题解的类型(可能性)。下一页返回图解法步骤：（1）建立坐标系；（2）将约束条件在图上表示；（3）确立满足约束条件的解的范围；（4）绘制出目标函数的图形（5）确定最优解用图解法求解下列线性规划问题图1一1返回图1一2返回图1-3返回1.2图解法1.2.2线性规划解的特性学习图解法的主要目的之一就是掌握线性规划问题解的特性，主要包括以下三点:①线性规划问题若有可行域，则可行域必是一个凸多边形，对应于凸集(集合内部任意两点连线上的点都属于这个集合)。例如，在图1-4中，只有图(a)可以用来表示凸集。凸集的数学定义:设K为n维欧氏空间的一个点集，若K中任意两个点X1和X2连线上的所有点都属于K，即“X=αX1+(1-α)X2

∈K(0≤a≤1)”，则称K为凸集。设X(x1，x2，…，xn)，X1(u1，u2，...，un)，X2(v1，v2，…，vn)，如图1一5所示，“X=αX1+(1-α)X2

∈K(0≤a≤1)”的证明思路如下:下一页返回上一页1.2图解法(vi-xi)=α(vi-ui)＝＞xi=αui+(1-α)vi＝＞X=αX1+(1-α)X2(i=1，2，…，n)②凸多边形(可行域)的顶点是有限的，每个顶点对应的解为基本可行解。③对于某一线性规划问题，如果有最优解，则最优解一定在可行域的某个顶点获得。下一页返回上一页1.2图解法为此，可以得到线性规划问题求解的思路:找出并比较凸多边形(可行域)的顶点，目标函数值最大(或最小)的顶点对应于最优解。可见，在求解线性规划问题的时候只需要考虑凸多边形的顶点，并比较这些顶点对应的目标函数值，就能获得最优解。1.2.3线性规划解的可能性线性规划问题解的可能性有四种，即唯一最优解(如图1-3所示)、无穷多最优解(又称多重最优解)、无界解和无可行解，如图1-6、图1-7、图1-8和图1-9。下一页返回上一页1.2图解法图解法的解题思路和几何上的直观表示，对求解线性规划问题具有重要启示:①线性规划问题的解有唯一最优解、无穷多最优解、无界解和无可行解四种情况。②线性规划问题的可行域一般为无界或有界凸多边形(无可行解除外)。③若线性规划问题的最优解存在，即有唯一最优解或无穷多最优解，则必在可行域的某个顶点上获得。④若可行域中有两个点对应于最优解，则该两点连线上的任意一点都对应于最优解。返回上一页1.3普通单纯形法1.3.1线性规划模型的标准形式在使用单纯形法求解时，第一步就是寻找基本可行解，前提是先将原模型标准化。(1)标准型的表达方式。线性规划模型的标准形式定义为下一页返回1.3普通单纯形法也可以写成模型(1-6)和模型(1-7)的形式，其中模型(1-7)较为常用。线性规划模型的标准形式有如下特征:①目标函数求最大值，即maxZ。下一页返回上一页1.3普通单纯形法②资源限量非负，即b≥0。③决策变量非负，表示所有决策变量取值均大于或等于零，即X≥0。④约束条件为等式，即AX=b。(2)一般形式与标准形式的转换方法。①“决策变量非负”。若某决策变量xk为“取值无约束”(无符号限制)，令xk=x′k-x″k(x′k≥0，x″k≥0)；若xk≤0，令xk=-x′k，则x′k≥0②“目标函数求最大值”。对于极小化原问题minZ=CX，则令Z′=-Z，原问题则转为求maxZ′=-CX，即当Z′达到最大值时，Z达到最小值，求解后应注意还原，即Z=-Z′。下一页返回上一页1.3普通单纯形法③“约束条件为等式”。对于“≤”型约束，则在“≤”左端加上一个非负松弛变量(SlackVariable)，使其变为等式。对于“≥”型约束，则在“≥”左端减去一个非负剩余变量(SurplusVariable)，使其变为等式。。④“资源限量非负”。若某个bi＜0，则将该约束两端同乘“-1”，以满足非负性的要求。1.3.2几个重要概念(1)基。下一页返回上一页1.3普通单纯形法假设线性规划问题模型的系数矩阵为m行n列，则系数矩阵中秩为m的m行和m列子矩阵称为基矩阵，简称为基，一般用B来表示。已知线性规划标准化模型(1-8)的系数矩阵A为2行4列，见矩阵(1-9)，其中2行2列的子矩阵有6(C21)个，如表1一9所示。容易判断，B4中两个行(或列)向量线性相关，即对应元素成比例，其余子矩阵均为满秩矩阵，因此该线性规划模型存在5个基:B1

，B2，B3，B5和B6。下一页返回上一页1.3普通单纯形法(2)基变量和非基变量。基中的列向量对应的变量称为基变量，决策变量中除基变量以外的变量称为非基变量。如B1中的两个列向量分别对应于决策变量x1和x2，则x1和x2为基变量，x3和x4为非基变量，其他情况见表1-9。(3)基本解。对于某一确定的基，令所有非基变量为0，通过约束方程组AX=b可解出m个基变量的唯一解，称之为基本解。基矩阵B1，B2，B3，B5和B6。对应的基本解如表1-10所示。下一页返回上一页1.3普通单纯形法(4)基本可行解。变量取值满足非负条件的基本解称为基本可行解，基本可行解对应于凸多边形(凸集)的顶点。如表1-10所示，X1，X2，X5和X6。为基本可行解，分别对应于该问题可行域(凸多边形)的四个顶点。1.3.3求解步骤(1)普通单纯形法求解思路。掌握了上述概念以后，根据图解法带来的启示，可以确定线性规划问题的解题思路，如图1一10所示。下一页返回上一页1.3普通单纯形法首先，确定一个初始基可行解，即找到一个初始可行基；想办法判断这个基可行解是不是最优解，如果是最优解，就得到这个线性规划问题的最优解;如果判断出这个可行解不是最优解，就将这个可行基按一定规则变化到下一个可行基，然后再判断新得到的基可行解是不是最优解；如果还不是，再接着进行下一个可行基变化，直至找到最优解。(2)单纯形法原理。对于公式(1-7)，可令A=(P1，P2，…，Pm，Pm+1，…，Pn)，其中P1，P2，…，Pm为基变量对应的列向量;Pm+1，Pm+2，…，Pn

为非基变量对应的列向量，因此，A可写成A=(B,N)，相应地，X=(XB，XN)T，C=(CB，CN)。下一页返回上一页1.3普通单纯形法对于约束条件AX=(B,N)(XB，XN)T=BXB+NXN=b，在等式两端左乘B-1，有XB+B-1NXN=B-1b，即XB=B-1b-B-1NXN。若令XN=0,XB=B-1b。对于目标函数Z=CX=(CB，CN)(XB，XN)T=CBXB+CNXN，将“B-1b-B-1NXN”代人后，有Z=CB(B-1b-B-1NXN)+CNXN=CBB-1b+(CN一CBB-1N)XN，令XN=0,Z=CBB-1b。其中“CN-CBB-1N”为非基变量检验数，通常用“σN=CN-CBB-1N”表示。对于某一非基变量的检验数，也可表示为“σj=cj-Zj。同理，基变量检验数为“σB=CB-CBB-1B”，因此基变量的检验数为零。所有检验数可表示为“σ=C-CBB-1A”。上述推导过程可用表1一11和表1一12表示(其中，E为单位矩阵，即B-1B=E)，称为单纯形表。下一页返回上一页1.3普通单纯形法(3)单纯形法求解步骤。①求出初始基本可行解。先将模型标准化，找到单位基，令非基变量为零，确定初始基本可行解。②最优性检验。利用公式“σn=CN-CBB-1N”求出非基变量检验数，若所有非基变量检验数小于或等于零，说明已得到最优解，否则进人步骤③。③换基和迭代。(a)确定入基变量σk=max{σj|σj>0}(入基变量确定法则)；下一页返回上一页1.3普通单纯形法(b)确定出基变量θl=min{bi/aik|aik＞0}(出基变量确定法则或最小比值法则);(c)确定主元素，考查入基变量对应的列向量和出基变量对应的行向量，交叉元素即为“主元素”；(d)先将主元素变为“1”，再利用初等变换方法求出新的基本可行解。④重复步骤②和③，直到求出最优解。(4)退化解与Bland法则。一般称基变量取值为零的解为退化解。在确定出基变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现了退化解，当出现退化时，进行多次迭代，而基从B1,B2,…又返回到B1，计算过程陷人循环，无法得到最优解。下一页返回上一页1.3普通单纯形法Bland法则:①在确定入基变量时，若存在两个或两个以上的最大检验数(大于零)，选择下标号最小的变量入基。②在确定出基变量时，若存在两个或两个以上的最小比值，同样选择比值对应下标号小的变量出基。1.3.4最优解判定定理判定定理1:在单纯形表中，若所有非基变量的检验数小于零，且B-1b均为非负，则线性规划问题具有唯一最优解。见表1-17或表1-18，非基变量x3和x5的检验数(-1/8和-3/2)均小于零，则线性规划问题只有一个最优解，通常称作“唯一最优解”。下一页返回上一页1.3普通单纯形法判别定理2:在单纯形表中，若所有非基变量的检验数小于或等于零，且B-1b均为非负，其中某个检验数等于零，则线性规划问题具有无穷多个最优解(多重最优解)。判定定理