线性规划方法课件

第五章 线性规划方法线性规划及其单纯形求解方法 线性规划的对偶理论 运输问题的求解方法表上作业法 第五章线性规划方法线性规划及其单纯形求解方法1线性规划是运筹学中发展较快、应用较广和比较成熟的一个分支。它在实际应用中日益广泛与深入,已经被广泛地应用到工业、农业、商业与交通运输规划，工程技术的优化设计，以及企业管理等各个领域。在地理学领域，线性规划，作为传统的计量地理学方法之一，是解决有关规划、决策和系统优化问题的重要手段。线性规划是运筹学中发展较快、应用较广和比较成熟的一个分支。它2线性规划的数学模型线性规划的标准形式线性规划的解及其性质线性规划问题的求解方法单纯形法应用实例:农场种植计划模型 第一节 线性规划及其单纯形求解方法线性规划的数学模型第一节线性规划及其单纯形求解方法3（一）线性规划模型之实例（一）线性规划模型之实例线性规划研究的两类问题：某项任务确定后，如何统筹安排，以最少的人力、物力和财力去完成该项任务；面对一定数量的人力、物力和财力资源，如何安排使用，使得完成的任务最多。它们都属于最优规划的范畴。以下为一些实例。一、线性规划的数学模型一、线性规划的数学模型（一）线性规划模型之实例一、线性规划的数学模型4运输问题运输问题假设某种物资（譬如煤炭、钢铁、石油等）有m个产地，n个销地。第i产地的产量为ai（i=1，2，m），第j销地的需求量为bj(j=1,2，n)，它们满足产销平衡条件。如果产地i到销地j的单位物资的运费为Cij，要使总运费达到最小，可这样安排物资的调运计划：运输问题5设xij表示由产地i供给销地j 的物资数量，则上述问题可以表述为：求一组实值变量xij(i=1，2，m；j=1，2，n)，使其满足：而且使：设xij表示由产地i供给销地j的物资数量，则上述问题可以表6资源利用问题资源利用问题假设某地区拥有m种资源，其中，第i种资源在规划期内的限额为bi(i=1，2，m)。这m种资源可用来生产n种产品，其中，生产单位数量的第j种产品需要消耗的第i种资源的数量为aij(i=1，2，m；j=1,2,n)，第j种产品的单价为cj(j=1，2，n)。试问如何安排这几种产品的生产计划，才能使规划期内资源利用的总产值达到最大?资源利用问题假设某地区拥有m种资源，其中7设第j种产品的生产数量为xj(j=1，2，n)，则上述资源问题就是：求一组实数变量xj(j=1，2，n)，使其满足设第j种产品的生产数量为xj(j=1，2，n)，则上述资8合理下料问题合理下料问题用某种原材料切割零件A1，A2,Am的毛坯，现已设计出在一块原材料上有B1，B2，Bn种不同的下料方式，如用Bj下料方式可得Ai种零件aij个，设Ai种零件的需要量为bi个。试问应该怎样组织下料活动，才能使得既满足需要，又节约原材料？合理下料问题用某种原材料切割零件A1，A2,9设采用Bj方式下料的原材料数为xj，则上述问题可表示为：求一组整数变量xj(j=1，2，n)，使得设采用Bj方式下料的原材料数为xj，则上述问题可表示为：求一10（二）线性规划的数学模型（二）线性规划的数学模型 以上例子表明，线性规划问题具有以下特征：每一个问题都用一组未知变量（x1，x2，xn）表示某一规划方案，其一组定值代表一个具体的方案，而且通常要求这些未知变量的取值是非负的。每一个问题的组成部分：一是目标函数，按照研究问题的不同，常常要求目标函数取最大或最小值；二是约束条件，它定义了一种求解范围，使问题的解必须在这一范围之内。每一个问题的目标函数和约束条件都是线性的。（二）线性规划的数学模型以上例子表明，线性规划问题具有以下11由此可以抽象出线性规划问题的数学模型，一般形式为：在线性约束条件以及非负约束条件xj0（j=1，2，n）下，求一组未知变量xj(j=1，2，n)的值，使由此可以抽象出线性规划问题的数学模型，一般形式为：以及非负约12采用矩阵形式可描述为：在约束条件 AX(，)b X0下，求未知向量，使得Z=CXmax(min)其中采用矩阵形式可描述为：13二、线性规划的标准形式二、线性规划的标准形式（一）线性规划的标准形式（一）线性规划的标准形式 在讨论与计算时，需要将线性规划问题的数学模型转化为标准形式，即在约束条件：xj0（j=1，2，n）下，求一组未知变量xj（j=1，2，n）的值，使二、线性规划的标准形式（一）线性规划的标准形式xj0（14其缩写形式为：在约束条件x0（j=1，2，n）下，求一组未知变量（j=1，2，n）的值，使得：常记为如下更为紧凑的形式：或其缩写形式为：在约束条件x0（j=1，2，n）15（二）化为标准形式的方法（二）化为标准形式的方法 具体的线性规划问题，需要对目标函数或约束条件进行转换，化为标准形式。1.目标函数化为标准形式的方法目标函数化为标准形式的方法 如果其线性规划问题的目标函数为：minZ=CX显然有：minZ=max(-Z)=max Z则目标函数的标准形式为：max Z=-CX（二）化为标准形式的方法具体的线性规划问题，需要对目标函数162.2.约束方程化为标准形式的方法约束方程化为标准形式的方法 若第k个约束方程为不等式，即引入松弛变量,K个方程改写为：则目标函数标准形式为：2.约束方程化为标准形式的方法17三、线性规划的解及其性质三、线性规划的解及其性质 （一）线性规划的解（一）线性规划的解 可行解与最优解可行解与最优解满足约束条件（即满足线性约束和非负约束）的一组变量为可行解。所有可行解组成的集合称为可行域。使目标函数最大或最小化的可行解称为最优解。三、线性规划的解及其性质（一）线性规划的解18基本解与基本可行解基本解与基本可行解 在线性规划问题中，将约束方程组的mn阶矩阵A写成由n个列向量组成的分块矩阵基本解与基本可行解19如果B是A中的一个m阶的非奇异子阵，则称B为该线性规划问题的一个基。不失一般性，不妨设：则称 为基向量，与基向量相对应的向量 为基变量，而其余的变量 为非基变量。如果B是A中的一个m阶的非奇异子阵，则称B为该线性规划问题20如果是方程组的解，则就是方程组式的一个解，它称之为对应于基B的基本解，简称基解。满足非负约束条件的基本解，称为基本可行解。对应于基本可行解的基，称为可行基。如果21线性规划问题的以上几个解的关系，可用下图来描述：线性规划问题的以上几个解的关系，可用下图来描述：22(二二)线性规划解的性质线性规划解的性质 凸集和顶点凸集和顶点凸集凸集：若连接n维点集S中的任意两点X(1)和X(2)之间的线段仍在S中，则S为凸集。顶点顶点：若凸集S中的点X(0)不能成为S中任何线段的内点，则称X(0)为S的顶点或极点。(二)线性规划解的性质凸集和顶点23线性规划解的性质线性规划解的性质线性规划问题的可行解集（可行域）为凸集。可行解集S中的点X是顶点的充要条件是基本可行解。若可行解集有界，则线性规划问题的最优值一定可以在其顶点上达到。因此线性规划的最优解只需从其可行解集的有限个顶点中去寻找。线性规划解的性质24四、线性规划问题的求解方法四、线性规划问题的求解方法 四、线性规划问题的求解方法25线性规划方法课件26线性规划方法课件27四、线性规划问题的求解方法四、线性规划问题的求解方法 单纯形法单纯形法 （一）单纯形表（一）单纯形表 根据以上讨论，令则基变量，非基变量，则有：变形得：四、线性规划问题的求解方法（一）单纯形表28相应地，记：目标函数记为：则对应于基B的基本解为：相应地，记：29最优解的判定：当时，则由目标函数式可看出：对应于B的基本可行解为最优解，这时，B也被称为最优基。由于与等价，故可得最优解的判定定理最优解的判定定理：对于基B，若，且则对应于基B的基本解为最优解，B为最优基。最优解的判定：30在上式中，称系数矩阵为对应于基B的单纯形表，记为T(B).或对目标函数与约束不等式运用矩阵变形得：在上式中，称系数矩阵为对应于基B的单纯形表，记为T(B).31如果记：以及则如果记：以及则32(二二)单纯形法的计算步骤单纯形法的计算步骤 第一步第一步，找出初始可行基，建立初始单纯形表。第二步第二步，判别检验所有的检验系数（1）如果所有的检验系数 ，则由最优性判定定理知，已获最优解，即此时的基本可行解就是最优解。（2）若检验系数中，有些为正数，但其中某一正的检验系数所对应的列向量的各分量均非正，则线性规划问题无解。（3）若检验系数中，有些为正数，且它们所对应的列向量中有正的分量，则需要换基、进行迭代运算。(二)单纯形法的计算步骤第一步，找出初始可行基，建立初始33第第三三步步，选主元。在所有大于零的检验数中选取最大的一个b0s，对应的非基变量为xs,对应的列向量为若则确定brs为主元项。第第四四步步，在基B中调进Ps，换出Pjr，得到一个新的基第第五五步步，在单纯形表上进行初等行变换，使第s列向量变为单位向量，又得一张新的单纯形表。第六步第六步，转入上述第二步。第三步，选主元。在所有大于零的检验数中选取最大的一个b0s34例例1：用单纯形方法求解线性规划问题解解：首先引入松弛变量 ，把原问题化为标准形式：例1：用单纯形方法求解线性规划问题解：首先引入松弛变量35具体步骤如下：第一步，确定初始单纯形表如下：x1x2x3x4-z02300 x3121310 x492101第二步，判别。在初始单纯形表中b01=2,b02=3，所以B1不是最优基，进行换基迭代。第三步，选主元。根据选主元法则，确定主元项。第四步，换基，得一新基。具体步骤如下：x1x2x3x4-z02300 x312131036第五步，进行初等行变换，得B2下的新单纯形表x1x2x3x4-z-1210-10 x241/311/30 x455/30-1/31第六步，因检验系数有正数b01=1，重复以上步骤可得对应于B3=p2,p3的单纯形表，检验各检验数可知得最优解X1=3,X2=3,X3=0,X4=0:目标函数最大值为Z=15。x1x2x3x4-z-1500-4/5-3/5x23012/5-1/5x1310-1/53/5第五步，进行初等行变换，得B2下的新单纯形表x1x2x3x37五、应用实例五、应用实例:农场种植计划模型农场种植计划模型 某农场I、II、III等耕地的面积分别为100hm2、300hm2和200hm2，计划种植水稻、大豆和玉米，要求三种作物的最低收获量分别为190000kg、130000kg和350000kg。I、II、III等耕地种植三种作物的单产如表5.1.4所示。若三种作物的售价分别为水稻1.20元/kg，大豆1.50元/kg，玉米0.80元/kg。那么，（1）如何制订种植计划，才能使总产量最大？（2）如何制订种植计划，才能使总产值最大？五、应用实例:农场种植计划模型某农场I、II、III等耕38表5.1.4不同等级耕地种植不同作物的单产(单位:kg/hm2)I等耕地II等耕地III等耕地水稻1100095009000大豆800068006000玉米140001200010000表5.1.4不同等级耕地种植不同作物的单产(单位:kg/39对于上面的农场种植计划问题，我们可以用线性规划方法建立模型。根据题意，决策变量设置如表5.1.5所示,表中Xij表示在第j等级的耕地上种植第i种作物的面积。三种作物的产量可以用表5.1.6表示。对于上面的农场种植计划问题，我们可以用线性规划方法建立模型。40表5.1.5作物计划种植面积（单位:hm2)表5.1.6三种作物的总产量（单位:kg）I等耕地II等耕地III等耕地水稻大豆玉米作物种类总产量水稻大豆玉米表5.1.5作物计划种植面积（单位:hm2)I等耕41根据题意，约束方程如下,耕地面积约束：最低收获量约束：非负约束：根据题意，约束方程如下,耕地面积约束：42（1）追求最大总产量的目标函数为：调用Matlab软件系统优化工具箱中的linprog函数，进行求解运算，可以得到一个最优解（如表5.1.7所示）。在该方案下，最优值，即最大总产量为6892200kg。从表中可以看出，如果以追求总产量最大为种植计划目标，那么，玉米的种植面积在I、II、III等耕地上都占绝对优势。（1）追求最大总产量的目标函数为：43表5.1.7追求总产量最大的计划方案（单位：hm2）I等耕地II等耕地III等耕地水稻0021.1111大豆0021.6667玉米100300157.2222表5.1.7追求总产量最大的计划方案（单位：hm2）44(2)追求最大总产值的目标函数为：进行求解运算，可以得到一个最优解（如表5.1.8所示）。在该方案下，最优值，即最大总产值为6830500元。从表中可以看出，如果以追求总产值最大为种植计划目标，那么，水稻的种植面积在I、II、III等耕地上都占绝对优势。(2)追求最大总产值的目标函数为：45表5.1.8追求总产值最大的计划方案（单位：hm2）I等耕地II等耕地III等耕地水稻58.75 300 200大豆16.25 00玉米2500表5.1.8追求总产值最大的计划方案（单位：hm2）46第二节第二节 线性规划的对偶理论线性规划的对偶理论对偶问题的提出对偶问题的提出原问题与对偶问题的关系原问题与对偶问题的关系对偶单纯形法对偶单纯形法第二节线性规划的对偶理论对偶问题的提出47一、对偶问题的提出一、对偶问题的提出 对于上节中所介绍的资源利用问题考虑：资源拥有者为了实现一定的收入目标，将其所拥有的资源出售，则需给每一种资源定价。一、对偶问题的提出对于上节中所介绍的资源利用问题48表示出售单位数量的第i种资源的价格，若将所有资源出售，则得到的总收入为 在做出决策时，考虑出售资源的收入不应该低于生产所获得的收入，则：表示49资源拥有者出售每一种资源的最低估价，可通过求解线性规划问题而得到。这表明，从不同角度考虑同一问题可得到相互联系的线性规划模型，这就是线性规划的对偶问题。资源拥有者出售每一种资源的最低估价，可通过求解线性规划问题而50一般地，称线性规划问题（I)和()互为对偶问题的标准形式。（I)()一般地，称线性规划问题（I)和()互为对偶问题的标准形式51对偶问题的变换关系为对称关系时，根据原问题的系数矩阵就能容易地写出对偶问题。如下表：表表5.2.1yjx1 x2 xn，原关系minW对偶关系maxZ对偶问题的变换关系为对称关系时，根据原问题的系数矩阵就能容52当原问题的约束条件中含有等式约束方程时，即变换关系为非对称形式，可按以下步骤求对偶问题：首先将每一个等式约束方程都用两个不等式约束方程代替，所有约束方程都变为同号不等式约束。按对称形式变换关系（表5.2.1）写出它的对偶问题。当原问题的约束条件中含有等式约束方程时，即变换关系为非对称53例例：对于线性规划问题可以按下述步骤求出其对偶问题：第一步：将等式约束分解为不等式约束，变为：例：对于线性规划问题54第二步，设和分别代表对应的对偶变量，按对称形式变换关系写出它的对偶问题第二步，设和55上述线性规划问题的各式，经过整理后得到：令，由于，可见不受正、负限制，将代入，可得到原线性规划问题的对偶问题。上述线性规划问题的各式，经过整理后得到：令56二、原问题与对偶问题的关系二、原问题与对偶问题的关系 线性规划原问题与对偶问题之间的形式变换关系可以由表5.2.2予以概述。原问题（或对偶问题）对偶问题（或原问题）目标函数目标函数变量个数n00无约束约束方程个数n=约束方程个数m=变量个数m00无约束约束方程右端项目标函数中变量的系数目标函数中变量的系数约束方程右端项二、原问题与对偶问题的关系线性规划原问题与对偶问题之间的57利用表5.2.2所描述的变换关系，可写出任何一个线性规划问题的对偶问题。譬如，对于线性规划问题利用表5.2.2所描述的变换关系，可写出任何一个线性规划问题58其对偶问题为其对偶问题为59对偶问题的基本性质：对称性：即对偶问题的对偶是原问题。弱对偶性：即若 是原问题的可行解，是对偶问题的可行解，则存在关系：。无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。对偶定理：若原问题有最优解，那么对偶问题也有最优解，而且它们的最优目标值相等。对偶问题的基本性质：60松紧定理：若 和 分别为原问题与对偶问题的可行解，则它们为最优解的充要条件为：设原问题是其对偶问题是：松紧定理：若和分别为原问题与对偶问题的可行解，61则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如下表。表表5.2.30互补松弛性：若 和 分别是原问题和对偶问题的可行解。那么，和，当且仅当和为最优解。则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关62三、对偶单纯形法三、对偶单纯形法 基本思想：若保持对偶问题的解是基可行解，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也就得到了最优解。这种方法的优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。基本原理：对于原问题三、对偶单纯形法基本思想：若保持对偶问题的解是基可行解，而63设B是一个基，不失一般性，令，它对应的基变量为。当非基变量都为零时，可以得到。若在中至少有一个负分量，设，并且在单纯形表的检验数行中的检验数都非正，即对偶问题保持可行解，它的各分量是对应基变量的检验数是对应非基变量的检验数是设B是一个基，不失一般性，令64每次迭代是将基变量中的负分量取出，去替换非基变量中的，经过基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近，当原问题得到可行解时，便得到了最优解。每次迭代是将基变量中的负分量取出，去替换非基变65计算步骤：（1)列出初始单纯形表，检查b列中的各分量，若都为非负，且检验数都为非正，则已得到最优解：若b列中至少有一个负分量，检验数保持非正，进行以下计算。（2）确定换出变量。按照法则确定对应的基变量为换出变量。计算步骤：66（3）确定换入变量。若xj所在行有负系数，计算所对应的非基变量xk为换入变量（4）以 为主元素，按原单纯形法迭代运算，得新单纯形表（5）重复（1）（4）的步骤，直至求得最优解。（3）确定换入变量。若xj所在行有负系数，计算67例例1：试用对偶单纯形法求解如下线性规划问题首先将该问题化为：例1：试用对偶单纯形法求解如下线性规划问题首先将该问题化为68-2-3-400CBXBbX1X2X3X4X500X4X5-3-4-1-2-21-131001-2-3-400初始单纯形表，如表5.2.4所示表表5.2.4b列各行为负，进行迭代计算，确定换出变量。故X3为换出变量。-2-3-400CBXBbX1X2X3X4X50X4-3-169故X1为换入变量。换入、换出变量所在列、行的交叉处“2”为主元项。进行迭代运算，得表5.2.5。表表5.2.5-2-3-400CBXBbX1X2X3X4X50-2X4X1-1201-5/2-1/21/23/210-1/2-1/20-4-10-1故X1为换入变量。换入、换出变量所在列、行的交叉处“2”为主70从上表可看出，b列中仍有负分量，继续迭代计算，重复上述步骤，得表5.2.6。表表5.2.6-2-3-400CBXBbX1X2X3X4X5-3-2X2X1-2/511/50110-1/57/5-2/5-1/51/5-2/500-3/5-8/5-1/5在上表中，b列各分量全为非负，检验数全为非正，故问题的最优解为，其对偶问题的最优解为从上表可看出，b列中仍有负分量，继续迭代计算，重复上述步骤，71线性规划方法课件72线性规划方法课件73线性规划方法课件74