matlab4线性规划.ppt

第四章 线性规划,引言,什么是线性规划如果最优化问题三要素中的目标函数和约束条件都是线性的，则该最优化问题称为线性规划问题 线性规划的应用和发展线性规划（Linear Programming，简写成LP）是最优化理论和方法中的重要领域之一。其理论上的完整性、方法上的有效性以及应用上的广泛性，较其他分支都成熟的多，同时很多实际问题都可以转化为线性规划来解决线性规划的要点就是在满足线性约束条件的前提下，使预定的线性目标函数达到最优。现在线性规划已不仅仅是一种数学方法，在理论上，它启发了诸如对偶、凸性等最优化理论的核心概念，在实际中更是大量被运用于经济学和管理学领域，成为科学决策的一个有效手段乔治丹齐格（G.B.Dantzig）被认为是线性规划之父。自从1947年他提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在应用上也日益深入，成为科学与工程领域广泛应用的数学模型。特别是在计算机能处理海量约束条件和设计变量的线性规划问题之后，线性规划就更加受到青睐,线性规划的典型实例,运输问题 设有两个建材厂C1和C2，每年沙石的产量分别为35万吨和55万吨，这些沙石需要供应到W1、W2和W3三个建筑工地，每个建筑工地对沙石的需求量分别为26万吨、38万吨和26万吨，各建材厂到建筑工地之间的运费（万元/万吨）如表所示，问题是应当怎么调运才能使得总运费最少？,线性规划的典型实例,运输问题问题分析假设xij代表建材厂Ci运往建筑工地Wj的数量（万吨），则各建材厂和工地之间的运量可以用下表来表示目标函数即为总运费建材厂C1、C2的输出量应分别为建材厂C1、C2的产量各工地的沙石需求量应当为从各建材厂接收到沙石的总量运输量xij为一非负值,线性规划的典型实例,运输问题数学模型线性规划问题的特征均可以用一组设计变量来表示一种实施方案每个问题都有一定的约束条件，这些条件可以用一组线性等式或者线性不等式表达在上述前提下，一般都有一个目标函数，该函数用于衡量方案的优劣，可以表达为设计变量的一个线性函数，我们的目的一般为使得目标函数达到最大值或者最小值,线性规划问题的标准型,线性规划问题的一般标准型 根据线性规划的定义，线性规划问题即求取设计变量x=x1,x2,xnT的值，在线性约束条件下使得线性目标函数达到最大，线性规划问题的一般标准型为：其中，ci、aij、bi 为给定的常数线性规划问题的标准型的特点 目标函数为设计变量的线性函数，且需要极大化；约束条件为设计变量的一组线性等式，也称为约束方程组；设计变量x1,x2,xn都有非负限制。,线性规划问题的标准型,线性规划问题的矩阵标准型 利用向量或矩阵符号，线性规划问题的标准型还可以用矩阵形式表达：其中 为n维行向量 为mn维矩阵 为m维列向量 为n维列向量 是指其各分量,线性规划问题的标准型,不同类型的非标准型化为标准型的方法问题为极小化目标函数 设原有线性规划问题为极小化目标函数 则可设 将极小化目标函数问题转化为极大化目标函数问题约束条件为不等式 如果原有线性规划问题的约束条件为不等式，则可增加一个或减去一个非负变量，使约束条件变为等式，增加或减去的这个非负变量称为松弛变量。例如，假如约束为 则可以在不等式的左边增加一个非负变量xn+1，使不等式变为等式 如果约束为 则可在不等式的左边减去一个非负变量xn+1，使不等式变为等式模型中的某些变量没有非负限制 若对某个变量xj并无限制，取值可正可负，这时可设两个非负变量 和，令 注意到，因为对原设计变量进行了代换，还需要将代换式代入目标函数和其他约束条件做相应的代换，这样就可以满足线性规划标准型对变量非负的要求,线性规划问题的标准型,例子将线性规划模型标准化将目标函数两边乘上-1转化为求极大值 原问题的约束条件中的前两个条件均为不等式，在第一个不等式的左边加上一个松弛变量x4，在第二个不等式的左边减去一个松弛变量x5，将两者转化为等式约束原问题对设计变量x3没有非负限制，故在此引入非负变量 和，令经过上述步骤整理后的标准型为,线性规划问题中解的概念,概述为了帮助分析线性规划求解过程，先介绍线性规划解的概念。仍然考虑式(4-2)中的线性规划的矩阵标准型：求解上述线性规划问题实际上就是要求出向量x=x1,x2,xnT使其满足Ax=b和x0，且目标函数f达到最大值，这个向量称为线性规划问题的解。当求解Ax=b时，假设独立方程的个数为m个，设计变量的维数为n，根据线性代数的知识，如果m=n，则方程有唯一解，无优化的自由度；如果mn，方程个数大于未知数的个数，则有些约束可能不能被满足，上述两类问题不在我们探讨的范围之列，也就是我们仅讨论mn的情况，在这个前提下，方程将有无穷多组解，如果需要直接从这无穷多组解中找出一个非负解使得目标函数取得最大值是很难的下面将分步骤详细分析如何获得这个线性规划问题的解，同时介绍在这类问题中的几个概念,线性规划问题中解的概念,基本解 如果线性规划问题的解存在，则它必定是满足Ax=b的有限多个“基本解”中选出的，那么我们的第一个任务就是找出满足方程Ax=b的基本解假设独立方程的个数为m个，故Ax=b的系数矩阵A的秩为m，于是A中必有m个列向量是线性无关的，不妨假设A中的前m个列向量线性无关，则这m个列向量可以构成矩阵A的m阶非奇异子矩阵，用矩阵B表示：B是一个m阶的满秩方阵，称B为线性规划问题的基，其每一个列向量Pj称为基向量，基向量所对应的设计变量称为基变量，记为A中其余n-m个列向量则构成非基矩阵，用矩阵N表示：非基矩阵N的每一个列向量称为非基向量，非基向量所对应的设计变量称为非基变量，记为,线性规划问题中解的概念,基本解根据上述分析，可以将方程组Ax=b转化为于是有上式称为约束方程组Ax=b的一个基本解，一般来说，如果线性规划问题中有n个设计变量，在Ax=b中有m个约束方程(nm)，则基本解的数量小于或等于 基本解不是线性规划问题的解，而是仅满足约束方程组的解,线性规划问题中解的概念,可行解、可行域 上面的分析仅考虑了约束方程组Ax=b，下面进一步考虑线性规划问题的非负约束。我们称既满足约束方程组Ax=b，又满足非负约束x0的解为线性规划问题的可行解，即可行解满足线性规划问题的所有约束。可行解的集合称为可行域，记作：基本可行解特别的，若线性规划问题的基本解能够满足线性规划问题中的非负约束，即：则称该解xB为基本可行解，简称基可行解，称B为可行基。基可行解的数量不会超过 个。显然，基本可行解一定是可行解，基可行解是可行域中一种特殊的解 最优解 能使得线性规划问题的目标函数值达到最大的可行解称为最优解。线性规划问题中的最优解，一定可以在基可行解中找到，而基可行解的数量是有限的，因而这就在理论上保证了可以在有限的步骤之内求出线性规划问题的最优解。,线性规划问题中解的概念,实例线性规划标准型为 于是取矩阵A的线性无关列P1和P2构成2阶非奇异子矩阵，B1是线性规划问题的一个 基矩阵，与其对应的基变量为x1和x2，即，相应的非基矩阵和非基变量分别为 令非基变量x3=0，可以求出对应基矩阵B1的基本解为，基矩阵B1解向量的各分量均为非负，故是线性规划问题的基本可行解。如果这个解可以使得目标函数取得最大值则该解为最优解。是否最优解的判断方法将在后续的章节中探讨。若取矩阵A的后两个线性无关列P2和P3，构成线性规划的另一个基矩阵 用相同的方法进行分析，可知，此时的基变量为x2和x3，非基变量为x1，于是令x1=0，可以得到对应基矩阵B2的一组基本解为：，由于对应基矩阵B2解向量的第二个分量即x3为负，故该解不是线性规划问题的基本可行解由理论分析可知，该线性规划问题基本解的个数为3个，也就是还可以选取P1和P3构成基矩阵B3，求取该问题的第三个基本解，只要有一个基矩阵，就可以求出一个对应的基本解，至于该基本解是否基本可行解和最优解则需要进一步判断。,线性规划问题的图解法,用图解法求解如下二维线性规划问题分析可行域引入平面直角坐标系，以x1作为横轴，以x2作为纵轴，由于线性规划问题满足非负条件x1,x20，故问题的探讨局限在平面直角坐标系的第一象限分析x1-2x24，取直线x1-2x2=4，则直线上的点和直线以上的区域满足该不等式分析x1+2x28，取直线x1+2x2=8，则直线上的点和直线以下的区域满足不等式于是可行域为四边形ACBO内的区域（包括边界上的点），在图中用阴影表示 分析最优解分析目标函数f=x1+x2，可以将其改写成为x2=-x1+f 可以发现改写后的方程是以f为参量，以-1为斜率的一 族平行的直线，这些平行线越向右上方移动，离原点 越远，对应的目标函数值就越大。当直线运动到经过 点C时，即不能再继续向上移动，否则将脱离线性规 划问题的可行域，故线性规划问题在点C达到最大值,线性规划问题求解的单纯形法,理论基础称T(B)为对应于基B的单纯形表，b0j(j=1,2n)称为检验数线性规划问题最优解的判定若T(B)中所有检验数b0j 0(j=1,2n)，则xB=B-1b-B-1NxN是最优解。若T(B)中有某一个检验数b0,m+s 0，且在该列中的bi,m+s0(i=1,2,m)，则线性规划问题无最优解,线性规划问题求解的单纯形法,单纯形迭代(步骤1)建立初始单纯形表T(B)，确定T(B)中的枢点（Pivot）项确定进基变量 在所有b0j0的检验数中，选出最小的一个b0s，对应的非基变量为xs,此时，即已确定xs为进基变量，即下一次的迭代中将以xs作为进基变量 确定出基变量 取（若有几个相同的最小者，则取基变量下标最小者）记 此时，即已确定出基变量为xr 确定枢点项 由确定出基变量时所得的结论，可知，brs即被称为枢点项，此时，需要对枢点项brs进行标注，例如右上角加*号或者用括号括起来等方式，以便于后面的讨论和分析,线性规划问题求解的单纯形法,单纯形迭代(步骤2)调换基变量，构造新基，构造新的单纯形表确定新基对单纯形表进行变换 目的是使得下一步对基 的单纯形表 进行适当的变换，使得向量 变为单位向量，即使得分量brs取1，其它分量取0，在这个过程中运用的是Gauss-Jordan消元法，Gauss-Jordan消元法实际上就是下述两次变换 第一次变换，使brs=1 为了使brs=1，只需将原表数用brs去除第r行各数，得新表第r行各数，即 第二次变换，使bis=0(0ir m)为使新表中bis=0(0ir m)，需将原表中第i行减去第r行相应数的 倍，得新表第i行的数，即 换基后，新基 仍是一个可行基，且目标函数值增加,线性规划问题求解的单纯形法,单纯形迭代(重复上述1,2过程)按照上面步骤(1)(2)进行重复迭代，循环操作，以求得最优解特别注意需要特别注意的是，如果基B对应的单纯形表T(B)中检验数有负数b0s0，且对应的如下列向量非正，即：那么，目标函数无上界，即无最优解。,线性规划问题求解的单纯形法,用单纯形法求解线性规划问题将上述问题转化为线性规划标准型确定A和Pi确定xB1初始基、初始基矩阵B1、非基变量等确定一个基本解,线性规划问题求解的单纯形法,确定初始单纯形表构建初识单纯形表如表所示，从行的角度说，表中的每一行代表一个约束方程（把目标函数也看做是约束方程放在第一行）。从列的角度讲，对于约束方程而言，表中的第一列即为约束方程右边的值，而对于目标函数f则是填写根据当前基计算出来的目标函数值。而其他的每一列则对应于一个变量。例如例题中的目标函数为f=4x1+3x2，则改写成f-4x1-3x2=0，故表的第一行右端系数为0，Value处填0，x1和x2处分别填-4和-3。而对于约束方程3x1+4x2+x3=12，其方程右端的值为12，故在Value处填12，在对应变量的位置填3、4和1。由例题求初始基可行解的过程可知，如果线性规划标准型的向量b的每一个分量均为正的话，当令所有的松弛变量为基时，总是可以找到一组基本可行解。这时每个基本变量的值等于其方程右端的常数。由于此时目标函数的系数全都为零，所以对应的目标函数值也为零。我们的目的就是要使用单纯形法，通过变换运算，在每次迭代的最后，使得当前基本变量对应的矩阵B形成一个单位阵，并且目标函数中对应于基本变量的系数变为零。具有这种性质的表称之为规范型,初始单纯形表,线性规划问题求解的单纯形法,单纯形迭代对单纯形表进行判别 在单纯形表4-3的检验数存在负数，即b01=-4、b03=-3，则可知基B1对应的解不满足最优解条件，又b01、b03对应的列向量中的分量有非负数，所以需要进行换基迭代。确定进基变量、出基变量和枢点项 在两个非负检验数中，取最小者b01=-4，b01对应设计变量x1所在列，故x1为进基变 量，标记进基变量所在列的符号s=1；设计变量x1对应的列向量为，3个分量b11=3、b21=3、b31=4均为正数，需要分别计算表单纯形表中 的值，有 即选择的是，于是r=3，枢点项为b31，枢点项所在行对应的变量为x5，故出基变量为x5。我们把枢点项用括号括起来如表所示,标记枢点项,线性规划问题求解的单纯形法,调换基变量，构造新的基矩阵B2和单纯形表出基变量为x5，进基变量为x1，于是新的基矩阵使得当前基变量对应的矩阵B2形成一个单位阵，并且目标函数中对应于基本变量的系数变为零，结果如表所示在得到新的单纯形表之后，一次迭代完成。我们需要进行判断是否进行再次迭代，采用的方法和上一次的迭代完全相同。,Gauss-Jordan消元,线性规划问题求解的单纯形法,二次迭代经过与一次迭代完全相同的步骤，得到单纯形表在该单纯形表中，检验数已没有负数，故最新的基矩阵所对应的基本可行解即是线性规划问题的最优解了。此时线性规划问题的最优解为：对应的目标函数的极值为,二次迭代单纯形表,一般情况下线性规划问题求解的思路,何时使用大M法我们可以看到在上面的例子中，不等式约束均有“”的形式，这样才可以通过将非负松弛变量加到（而不是减去）每个不等式的左端，将不等式转化为等式，这时，我们将所加的松弛变量作为初始基变量，所得到的基矩阵为一单位阵，可以很容易的获得一个初始基本可行解进行单纯形法的迭代。但是在一般情况下，线性规划问题的约束条件存在等式和不等式，同时不等式也存在“”和“”，注意到当约束方程组中含有“=”约束时，我们不需要加入非负松弛变量，当约束方程组中含有“”约束时，我们需要减去一个非负松弛变量，在这两种情况下就无法形成单位阵作为初始的基矩阵进行求解，即不能顺利得到一个初始基本可行解，从而造成了迭代的困难。于是我们需要找到一种系统处理方法，能够比较方便的在各种约束条件下都能找到线性规划问题的初始可行基本解使得单纯形算法在任何约束下均有效。此时，我们需要用到人工变量，而将人工变量用于单纯形求解中的算法主要有大M法和两阶段方法,线性规划问题求解的大M法,大M法的求解原理大M法的原理是，先将线性规划问题变换成标准型，然后将新的非负变量加到具有“=”或者“”类型约束的方程的左端，于是用这些新的变量作为基变量就可以构成一个初始可行基。我们人为加入的这些非负变量就称为人工变量。人工变量与松弛变量不同，它没有明确的物理意义，只是为了获得一个初始可行基而设置的。但是对任何一个约束增加非负变量之后与原约束就是矛盾的，为了解决这个矛盾，使得新增加的变量对任一可行解无影响，我们在目标函数中给新增加的变量赋以一个很大的负系数（因为线性规划的标准型为目标函数求极大），这个系数通常用M来表示，因而这个方法又叫大M法。在目标函数中使用一个大的“-M”是迫使新的变量为零，否则目标函数将远不能达到极大值。,线性规划问题求解的大M法,使用大M法求解线性规划问题引入人工变量x4和x5到约束等式的左边 单纯形法求解 首先取x4和x5作为初始基变量 令非基变量x1=x2=x3=0，得到一个基本解 解的各分量均为非负，故该基本解为线性规划的一个基本可行解。故可用单纯形法开始迭代。,线性规划问题求解的大M法,单纯形迭代按照单纯形法，构造初始单纯形表，注意其中含有M项，但这并不影响求解过程上表并非单纯形表的规范性，因为目标函数对应于基变量x4和x5的系数不为零，故我们采用矩阵的行变换将上表转化为规范型 然后和单纯形法一致，经过迭代得到最终单纯形表为上表3中，检验数已没有负数，故已经求出线性规划问题的的最优解,线性规划问题求解的两阶段法,两阶段法的原理两阶段也是用以解决具有“=”或者“”类型约束的线性规划问题的初始可行解问题。顾名思义，该方法分为两个阶段进行：第一阶段 先引入松弛变量和人工变量，而目标函数则由人工变量的和组成。这一步的工作是用单纯形法把目标函数对应的所有的人工变量的值变为零。若第一阶段最优解对应的目标函数的最优值为零，则所有人工变量一定都取零值，说明原问题存在基可行解，可以进行第二阶段的计算；否则，原问题无可行解，停止计算。第二阶段 用原问题的的目标函数代替人工目标函数，用第一阶段获得的基本可行解作为该阶段迭代的初始点进行单纯形的换基迭代。,线性规划问题求解的两阶段法,用二阶段法求解线性规划问题化为标准型 在原问题的不等式约束中分别加入松弛变量x4和x5，将上述问题化为标准型 在上述标准型问题中，由于不存在单位阵基矩阵，故我们需要引入人工变量人为的构造出单位阵基矩阵，故我们采用两阶段法。,线性规划问题求解的两阶段法,第一阶段 构造辅助问题，加入人工变量x6和x7，并将目标函数表示称为人工变量的和，目的就是为了构造单位阵，辅助问题的形式如下：我们用单纯形法对该问题进行求解，可见，由于加入了人工变量，使得现在的辅助问题的约束方程组中形成了单位阵，即我们选取x4、x6和x7为基变量的话，基矩阵即是一个单位阵，然后在辅助问题的初始单纯形表的基础上将其转换成为规范型如下 于是在上述表的基础上进行单纯形迭代，以求出辅助问题的最优解,线性规划问题求解的两阶段法,第一阶段 单纯形迭代 一次迭代后的单纯形表为 二次迭代后的单纯形表为 检验数均非负，故辅助问题最优解 此时，目标函数最优值，且人工变量已全部出基。故第一阶段结束，转入第二阶段,线性规划问题求解的两阶段法,第二阶段 求解原线性规划问题。这时以在第一阶段筛选出来的基变量构成基矩阵作为原线性规划 问题的初始可行基，并将辅助问题的最优解删去人工变量的两列，作为原线性规划问题 的初始可行解，然后进行单纯形算法的换基迭代 在这个问题中，初始可行基为：初始可行解为：在单纯形表中删去人工变量x6和x7这两列，把第1行换成原问题的目标函数（消去基变量以后）的系数得到下表 可以看出，基变量x4，x2和x3没有构成单位阵，此时先要进行线性变化，例如在本例中就需要将f所在行减去x2所在行和x3所在行的和，之后得到新表就可以继续换基迭代,线性规划问题求解的两阶段法,第二阶段 换基迭代，由上页新表可知检验数b01为唯一的负数，故进基变量为x1，而在进基变量x1所在列中只有b11元素为正，进而确定枢点元素为b11，故出基变量为x4，然后使用Gauss-Jordan消元法结果如表所示，此时检验数已经全部非负，故已找到该问题的最优解 根据表上的数据可知，目标函数的最大值在最优解x*处取得：,线性规划问题的MATLAB求解,MATLAB标准型MATLAB标准型和前面理论知识讲解中有所不同，在上述模型中，有一个需要极小化的目标函数f，以及需要满足的约束条件假设x为n维设计变量，且线性规划问题具有不等式约束m1个，等式约束m2个，那么：c、x、lb 和ub 均为n维列向量，b为m1维列向量，beq为m2维列向量，A为m1n维矩阵，Aeq为m2n维矩阵注意事项MATLAB标准型是对目标函数求极小，如果遇到是对目标函数求极大的问题，在使用MATLAB求解时，需要在函数前面加一个负号转化为对目标函数求极小的问题；MATLAB标准型中的不等式约束形式为“”，如果在线性规划问题中出现“”形式的不等式约束，则我们需要在两边乘以(-1)使其转化为MATLAB中的“”形式。如果在线性规划问题中出现了“”的约束形式，则我们需要通过添加松弛变量使得不等式约束变为等式约束之后，我们只需要将所有的约束（包括不等式约束和等式约束）转化为矩阵形式的即可,线性规划问题的MATLAB求解,将问题转化为MATLAB标准型原问题是对目标函数求极大，故添加负号使目标变为：min f=-4x1+2x2-x3原问题中存在“”的约束条件，故添加负号使其变为8x1-2x2+2x3-8将约束整理为矩阵形式用MATLAB表达则为,c=-4;2;-1;%将目标函数转化为求极小A=2-1 1;8-2 2;b=12;-8;%不等式约束系数矩阵Aeq=-2 0 1;1 1 0;beq=3;7;%等式约束系数矩阵lb=0;0;0;ub=Inf;Inf;Inf%对设计变量的边界约束,线性规划问题的MATLAB求解,函数调用格式MATLAB优化工具箱中求解线性规划问题的命令为linprog，其函数调用方法有多种形式如下所示 x=linprog(c,A,b)x=linprog(c,A,b,Aeq,beq)x=linprog(c,A,b,Aeq,beq,lb,ub)x=linprog(c,A,b,Aeq,beq,lb,ub,x0)x=linprog(c,A,b,Aeq,beq,lb,ub,x0,options)x=linprog(problem)x,fval=linprog(.)x,fval,exitflag=linprog(.)x,fval,exitflag,output=linprog(.)x,fval,exitflag,output,lambda=linprog(.),线性规划问题的MATLAB求解,输入参数MATLAB工具箱中的linprog函数在求解线性规划问题时，提供的参数为：模型参数、初始解参数和算法控制参数。模型参数x、c、lb、ub、b、beq、A和Aeq在MATLAB标准型中已经介绍了其具体物理意义和获得方法x0为线性规划问题的初始解，该设置仅在中型规模算法中有效，而在默认的大型规模算法和单纯形算法中，MATLAB将忽略一切初始解。options为包含算法控制参数的结构变量，我们可以通过optimset命令对这些具体的控制参数进行设置，例如下述格式 options=optimset(param1,value1,param2,value2,.)该命令格式创建一组控制参数结构变量options，将参数的具体值赋给单引号之间的参数，任何未被指定的参数将被赋值为，参数值为的具体的含义是将该组控制参数传递给优化函数时将使用MATLAB提供的默认值 在线性规划问题中可以用到的设置参数如下一页的表所示,线性规划问题的MATLAB求解,线性规划问题的MATLAB求解,输出参数 linprog函数返回的输出参数有x、fval、exitflag、lambda和output。输出参数x为线性规划问题的最优解输出参数fval为线性规划问题在最优解x处的函数值输出参数exitflag返回的是优化函数计算终止时的状态指示，说明算法终止的原因，其取值和其代表的具体原因如表所示,线性规划问题的MATLAB求解,输出参数输出参数output是一个返回优化过程中相关信息的结构变量，其属性如表所示输出参数lambda是返回线性规划问题最优解x处的拉格朗日乘子的一个结构变量,其总维数等于约束条件的个数，其非零分量对应于起作用的约束条件，其属性如表所示。,线性规划问题的MATLAB求解,命令详解x=linprog(c,A,b)该函数调用格式求解线性规划问题 x=linprog(c,A,b,Aeq,beq)该函数调用格式求解线性规划问题 即该函数调用格式解决的是既含有线性等式约束，又含有线性不等式约束的线性规划问题，如果在线性规划问题中无线性不等式约束，则可以设A=以及b=x=linprog(c,A,b,Aeq,beq,lb,ub)该函数调用格式求解线性规划问题 即在线性规划问题的求解过程中进一步考虑了对设计变量的约束，其中lb和ub均是和设计变量维数相同的列向量，如果对设计变量没有上界约束，可以设置ub(i)=Inf，如果没有下界约束则可以设置lb(i)=-Inf，和(2)类似，如果问题中没有等式约束，则可以设Aeq=以及beq=,线性规划问题的MATLAB求解,命令详解x=linprog(c,A,b,Aeq,beq,lb,ub,x0)在前面调用方法的基础上设置线性规划问题求解的初始解为x0，该参数仅在使用有效集算法时生效，否则当使用默认的内点算法时，将忽略任何初始点，即参数无效。x=linprog(c,A,b,Aeq,beq,lb,ub,x0,options)用options指定的优化参数进行最小化。可以使用optimset来设置这些参数x,fval=linprog(.)在优化计算结束之时返回线性规划问题在解x处的目标函数值fval。x,fval,exitflag=linprog(.)在优化计算结束之时返回exitflag值，描述函数计算的退出条件。x,fval,exitflag,output=linprog(.)在优化计算结束之时返回返回结构变量outputx,fval,exitflag,output,lambda=linprog(.)在优化计算结束之时返回线性规划问题最优解x处的拉格朗日乘子lambda,线性规划问题的MATLAB求解,用MATLAB求解线性规划问题,c=-1;-1;%目标函数，为转化为极小，故取目标函数中设计变量的相反数A=1-2;1 2;%线性不等式约束b=4;8;lb=0;0;%设计变量的边界约束，由于无上界，故设置ub=Inf;Inf;ub=Inf;Inf;x,fval=linprog(c,A,b,lb,ub)Optimization terminated.x=6.0000 1.0000fval=-7.0000,线性规划问题的MATLAB求解,用MATLAB求解线性规划问题,c=-4;-3;%目标函数，为转化为极小，故取目标函数中设计变量的相反数A=3 4;3 3;4 2;%线性不等式约束b=12;10;8;lb=0;0;%设计变量的边界约束，由于无上界，故设置ub=Inf;Infub=Inf;Inf;x,fval,exitflag=linprog(c,A,b,lb,ub)x=0.8000 2.4000fval=-10.4000exitflag=1,线性规划问题的MATLAB求解,用MATLAB求解线性规划问题,c=-1;-3;1;%目标函数，为转化为极小，故取目标函数中设计变量的相反数Aeq=1 1 2;-1 2 1;%线性等式约束beq=4;4;lb=0;0;0;%设计变量的边界约束，由于无上界，故设置ub=Inf;Inf;Infub=Inf;Inf;Inf;x,fval,exitflag=linprog(c,Aeq,beq,lb,ub)Optimization terminated.x=1.3333 2.6667 0.0000fval=-9.3333exitflag=1,线性规划问题的MATLAB求解,用MATLAB求解线性规划问题,c=-3;1;1;%目标函数，为转化为极小，故取目标函数中设计变量的相反数A=1-2 1;4-1-2;%线性不等式约束b=11;-3;Aeq=-2 0 1;%线性等式约束beq=1;lb=0;0;0;%设计变量的边界约束，由于无上界，故设置ub=Inf;Inf;Infub=Inf;Inf;Inf;x,fval,exitflag,output,lambda=linprog(c,A,b,Aeq,beq,lb,ub)Optimization terminated.x=4.0000 1.0000 9.0000fval=-2.0000exitflag=1,线性规划问题的MATLAB求解,生产计划问题问题的提出 某工厂需要生产A、B两种产品以满足市场的需求。这两种产品的生产均需要经过两道工艺流程。每生产1kg的A产品在第一道工艺流程耗时4小时，在第二道工艺流程耗时6小时；每生产1kg的B产品在第一道工艺流程耗时6小时，在第二道工艺流程耗时8小时，由于生产计划的要求，可供用的第一道工艺流程工时为240小时，第二道工艺流程工时为480小时。在化学品生产的过程中一般会伴随着副产品的生产，该工厂在生产B产品的同时，会产出副产品C，每生产1kg的B产品会产生2kg的副产品C，而不需外加任何费用，由于副产品C的利用率问题，使得产品C中的一部分可盈利，其他部分只能报废。根据核算，出售1kg的A产品可盈利600元，出售1kg的B产品可以盈利1000元，出售1kg的C产品可以盈利300元，而报废1kg的C产品需要亏损200元。经市场预测，在计划期内，产品C最大销售量为50kg，此时，应当如何安排A、B两种产品的产量，使该工厂的预计总盈利可以达到最大。,线性规划问题的MATLAB求解,生产计划问题问题分析 在本例中，重点是设计变量的选取方法。因为副产品C的出现和限制销售量使得问题显得稍复杂。如果我们用x1和x2分别代表产品A和产品B的产量，作为该问题的设计变量，由于产品C的产量为2x2，且如果2x2大于50的话，其小于50的部分会产生盈利，但其超出的部分会产生亏损，即产品C的单位利润会在300和-200之间变化，在这个前提下，总利润和产量之间就产生了非线性关系，我们会发现在确定目标函数和约束条件时比较困难。于是，我们需要另辟蹊径，寻求设计变量的选择方法，解决这个问题。由于MATLAB为线性规划的求解打开了方便之门，于是我们的选择设计变量的余地就很大，在两个设计变量难以解决的前提下，我们可以设置多个设计变量，使得目标函数和约束条件均为线性。,线性规划问题的MATLAB求解,生产计划问题问题解答 从产品C的约束出发，既然C产品可能产生盈利，也可能产生亏损，则设置相应的设计变量来表示其产生盈利的部分和产生亏损的部分，即产品C的销售量和报废量，故在这个原则下，我们得到问题的设计变量为：产品A的产量：x1 产品B的产量：x2 产品C的销售量：x3 产品C的报废量：x4 于是产品C的产量即为其销售量和报废量之和，即x3+x4 将预计总盈利作为该问题的目标函数 C是伴随产品B出现的，其数量之间满足的约束关系 C的最大销量为50kg 每道工艺流程的总工时是确定的，例如第一道工艺，生产x1kg的A耗时4x1小时，生产x2kg的B要6x2小时，其总和必须小于240小时；对第二道工艺流程的分 析也一样,线性规划问题的MATLAB求解,生产计划问题线性规划数学模型 由上述结果可知，当A产品的产量为22.5kg，B产品的产量为25kg时，该工厂预计盈利的最大值为5.35万元，其中伴随B产品产生的C产品恰好为50kg，为可销售的最大值。,c=-600;-1000;-300;200;A=2 3 0 0;3 4 0 0;0 0 1 0;b=120;240;50;Aeq=0-2 1 1;beq=0;lb=0;0;0;0;ub=Inf;Inf;Inf;Inf;x,fval=linprog(c,A,b,Aeq,beq,lb,ub)Optimization terminated.x=22.5000 25.0000 50.0000 0.0000fval=-5.3500e+004,线性规划问题的MATLAB求解,连续投资问题 问题的提出 某机构现在拥有资本200万元，为了获取更大的收益，该机构决定将这200万元进行投资，以期最大回报，现在共有四个方案可供选择，投资的方式为每年初将机构持有的所有资本都用于投资。方案1：从第1年到第4年的每年年初都需要投资，次年末回收本利1.15 方案2：第3年初投资，到第5年末收回本利1.25，最大投资额为80万元 方案3：第2年初投资，到第5年末收回本利1.40，最大投资额为60万元 方案4：每年初投资，每年末收回本利1.06 那么应该采用何种投资组合策略，使得该机构5年末的总资本最大,线性规划问题的MATLAB求解,连续投资问题问题分析 由于方案有4种可选，且每种开始投资的期限一般也不相同，故选择设计变量时需要考虑这两个因素，最直观的选法是令xij为第i年初投资方案j的资金数，此时，设计变量可以用下表来表示：,线性规划问题的MATLAB求解,连续投资问题问题解答 在第1年时，将所有的100万元用于投资，可选方案1和方案2 由于在第1年年末投资方案4的资金在第1年年末即收回本利1.06，故该部分资金即1.06x14可用于第2年的投资，即 方案3的最大投资额为60万元 可用于第3年投资的资本数来源于第1年投资方案1收回的本利1.15x11和第2年投资方案4收回的本利1.11x24，故 方案2的最大投资额为80万元 可用于第4年投资的资本数来源于第2年投资方案1收回的本利1.15x21和第3年投资方案4收回的本利1.11x34，故 可用于第5年投资的资本数来源于第3年投资方案1收回的本利1.15x31和第4年投资方案4收回的本利1.11x44，故,线性规划问题的MATLAB求解,连续投资问题问题解答 通过上述连续投资方式，在第5年末可以获得的本利资本总和为：我们的目的就是选择最佳的投资策略，极大化目标函数f的值 线性规划数学模型,线性规划问题的MATLAB求解,连续投资问题由运行结果可知，采取上述最佳投资方案之后，在第5年末所得到的总资本数为287.5万元。,c=0;0;0;-1.40;0;0;-1.25;0;-1.15;0;-1.06;Aeq=1 1 0 0 0 0 0 0 0 0 0;0 1.06-1-1-1 0 0 0 0 0 0;1.15 0 0 0 1.06-1-1-1 0 0 0;0 0 1.15 0 0 0 0 1.06-1-1 0 0 0 0 0 0 1.15 0 0 0 1.06-1;beq=200;0;0;0;0;lb=0;0;0;0;0;0;0;0;0;0;0;ub=Inf;Inf;Inf;60;Inf;Inf;80;Inf;Inf;Inf;Inf;x,fval=linprog(c,Aeq,beq,lb,ub)Optimization terminated.x=123.5459 76.4541 21.0414 60.0000 0.0000 34.5138 80.0000 27.5639 53.4154 0.0000 39.6909fval=-287.5000,线性规划问题的MATLAB求解,饲养场的配料问题 某饲养场有5种饲料已知各种饲料的单位价格和每百公斤饲料的蛋白质、矿物质、维生素含量如表所示，又知该场每日至少需蛋白质70单位、矿物质3单位、维生素10毫单位间如何混合调配这5种饲料才能使总成本最低?,线性规划问题的MATLAB求解,饲养场的配料问题,线性规划问题的MATLAB求解,c=2;7;4;3;5;A=-0.3-2.2-1-0.6-1.8-0.1-0.05-0.02-0.2-0.05-0.05-0.1-0.02-0.2-0.08;b=-70;-3;-10;lb=0;0;0;0;0;ub=Inf;Inf;Inf;Inf;Inf;x,fval=linprog(c,A,b,lb,ub)Optimization terminated.x=0.0000 0.0000 0.0000 39.7436 25.6410 fval=247.4359 由运行结果可知，只需要后两种饲料即可，其中饲料4需要3974.36公斤，饲料52564.1公斤，且此时的最低成本为247.4。,饲养场的配料问题,线性规划问题的MATLAB求解,运输问题,线性规划问题的MATLAB求解,c=10;12;9;8;11;13;Aeq=1 1 1 0 0 0;0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;beq=35;55;26;38;26;lb=0;0;0;0;0;0;ub=Inf;Inf;Inf;Inf;Inf;Inf;x,fval=linprog(c,Aeq,beq,lb,ub)Optimization terminated.x=0.0000 9.00