matlab4线性规划PPT课件

1、第四章第四章 线性规划线性规划 引言 v 什么是线性规划 如果最优化问题三要素中的目标函数和约束条件都是线性的，则该最优化问题 称为线性规划问题 v 线性规划的应用和发展 线性规划（Linear Programming，简写成LP）是最优化理论和方法中的重 要领域之一。其理论上的完整性、方法上的有效性以及应用上的广泛性，较其 他分支都成熟的多，同时很多实际问题都可以转化为线性规划来解决 线性规划的要点就是在满足线性约束条件的前提下，使预定的线性目标函数达 到最优。现在线性规划已不仅仅是一种数学方法，在理论上，它启发了诸如对 偶、凸性等最优化理论的核心概念，在实际中更是大量被运用于经济学和管理

2、学领域，成为科学决策的一个有效手段 乔治丹齐格（G. B. Dantzig）被认为是线性规划之父。自从1947年他提出 求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在应用上也日 益深入，成为科学与工程领域广泛应用的数学模型。特别是在计算机能处理海 量约束条件和设计变量的线性规划问题之后，线性规划就更加受到青睐 线性规划的典型实例 v 运输问题 设有两个建材厂C1和C2，每年沙石的产量分别为35万吨和55万吨，这些沙石 需要供应到W1、W2和W3三个建筑工地，每个建筑工地对沙石的需求量分别 为26万吨、38万吨和26万吨，各建材厂到建筑工地之间的运费（万元/万吨） 如表所示，问题是应

3、当怎么调运才能使得总运费最少？ 运费 工地 建材厂 W1W2W3 C110129 C281113 线性规划的典型实例 v 运输问题 问题分析 假设xij代表建材厂Ci运往建筑工地Wj的数量（万吨），则各建材厂和工地之间的运 量可以用下表来表示 目标函数即为总运费 建材厂C1、 C2的输出量应分别为建材厂C1、 C2的产量 各工地的沙石需求量应当为从各建材厂接收到沙石的总量 运输量xij为一非负值 分配量 工地 （万吨） 建材厂 W1W2W3 输出总 量 C1x11x12x1335 C2x21x22x2355 接收总量26382690 111213212223 1012981113fxxxxxx

4、=+ 111213 212223 35 55 xxx xxx += += 1121 1222 1323 26 38 26 xx xx xx += += += 0 ij x蕹 线性规划的典型实例 v 运输问题 数学模型 v 线性规划问题的特征 均可以用一组设计变量来表示一种实施方案 每个问题都有一定的约束条件，这些条件可以用一组线性等式或者线性不等式 表达 在上述前提下，一般都有一个目标函数，该函数用于衡量方案的优劣，可以表 达为设计变量的一个线性函数，我们的目的一般为使得目标函数达到最大值或 者最小值 111213212223 111213 212223 1121 1222 1323 1012

5、981113 m i n 35 s. t. 55 26 38 26 0 (1,2;1,2,3) ij fxxxxxx xxx xxx xx xx xx xij =+ += += += += += = 线性规划问题的标准型 v 线性规划问题的一般标准型 根据线性规划的定义，线性规划问题即求取设计变量x=x1, x2, xnT的值， 在线性约束条件下使得线性目标函数达到最大，线性规划问题的一般标准型为： 其中，ci 、aij 、bi 为给定的常数 v 线性规划问题的标准型的特点 目标函数为设计变量的线性函数，且需要极大化； 约束条件为设计变量的一组线性等式，也称为约束方程组； 设计变量x1, x2

6、, xn都有非负限制。 () 1 12 2 11 112 211 21 122 222 1 12 2 m ax s. t. 01,2, nn nn nn mmm nnm j fc xc xc x a xa xa xb a xa xaxb axaxaxb xjn =+ += += += = L L L L L L L L 线性规划问题的标准型 v 线性规划问题的矩阵标准型 利用向量或矩阵符号，线性规划问题的标准型还可以用矩阵形式表达： 其中 为n维行向量 为mn维矩阵 为m维列向量 为n维列向量 是指其各分量 m ax s. t. 0 f = = c cx x A A x xb b x x 12

7、n cccc 11121 21222 12 n n mmm n aaa aaa aaa 骣 = 桫 A A L L LLLL L 12 T n bbbb 12 T n xxxx x0 12 , ,0 n x xxL 线性规划问题的标准型 v 不同类型的非标准型化为标准型的方法 问题为极小化目标函数 设原有线性规划问题为极小化目标函数 则可设 将极小化目标函数问题转化为极大化目标函数问题 约束条件为不等式 如果原有线性规划问题的约束条件为不等式，则可增加一个或减去一个非负变量，使约 束条件变为等式，增加或减去的这个非负变量称为松弛变量。例如，假如约束为 则可以在不等式的左边增加一个非负变量xn+

8、1，使不等式变为等式 如果约束为 则可在不等式的左边减去一个非负变量 xn+1， 使不等式变为等式 模型中的某些变量没有非负限制 若对某个变量xj并无限制，取值可正可负，这时可设两个非负变量 和 ，令 注意到，因为对原设计变量进行了代换，还需要将代换式代入目标函数和其他约束条件 做相应的代换，这样就可以满足线性规划标准型对变量非负的要求 1 12 2 m i n nn fc xc xc x=+Lff = - 1 12 2 m ax nn fc xc xc x = - -L 1 12 2iiinni a xa xa xb+L 1 12 21iiinnni a xa xa xxb + +=L 1

9、12 2iiinni a xa xa xb+L 1 12 21iiinnni a xa xa xxb + +-=L j x j x jjj xxx=- 线性规划问题的标准型 v 例子 将线性规划模型标准化 将目标函数两边乘上-1转化为求极大值 原问题的约束条件中的前两个条件均为不等式，在第一个不等式的左边加上一个松 弛变量x4，在第二个不等式的左边减去一个松弛变量x5，将两者转化为等式约束 原问题对设计变量x3没有非负限制，故在此引入非负变量 和 ，令 经过上述步骤整理后的标准型为 123 123 123 123 1 2 2 m i n 3 s. t. 21 234 0 0 fxxx xxx

10、xxx xxx x x =-+ + +- -+= 123 m ax2fxxx= -+- 1234 1235 3 21 xxxx xxxx += +-= 1 3 x 2 3 x 12 333 xxx=- 12 1233 12 12334 12 12335 12 1233 12 123345 2 m ax 3 s. t. 221 2334 , ,0 fxxxx xxxxx xxxxx xxxx x x xxxx = -+-+ +-+= +-+-= -+-= 线性规划问题中解的概念 v 概述 为了帮助分析线性规划求解过程，先介绍线性规划解的概念。仍然考虑式(4- 2)中的线性规划的矩阵标准型： 求解

11、上述线性规划问题实际上就是要求出向量x=x1,x2,xnT使其满足Ax=b 和x0，且目标函数f达到最大值，这个向量称为线性规划问题的解线性规划问题的解。 当求解Ax=b时，假设独立方程的个数为m个，设计变量的维数为n，根据线性 代数的知识，如果m=n，则方程有唯一解，无优化的自由度；如果mn，方 程个数大于未知数的个数，则有些约束可能不能被满足，上述两类问题不在我 们探讨的范围之列，也就是我们仅讨论仅讨论mm)，则基本解的数量小于或等于 基本解不是线性规划问题的解不是线性规划问题的解，而是仅满足约束方程组的解 B N 轾 轾 犏= 犏 臌 犏 臌 x x B BN Nb b x x 1 0

12、B N - 轾 轾 犏 犏= 犏 犏 臌犏 臌 x x B Bb b x x x x m n C 线性规划问题中解的概念 v 可行解、可行域 上面的分析仅考虑了约束方程组Ax=b，下面进一步考虑线性规划问题的非负 约束。我们称既满足约束方程组Ax=b，又满足非负约束x0的解为线性规划问 题的可行解，即可行解满足线性规划问题的所有约束。可行解的集合称为可行 域，记作： v 基本可行解 特别的，若线性规划问题的基本解能够满足线性规划问题中的非负约束，即： 则称该解xB为基本可行解，简称基可行解，称B为可行基。基可行解的数量不 会超过 个。显然，基本可行解一定是可行解，基可行解是可行域中一种特 殊的

13、解 v 最优解 能使得线性规划问题的目标函数值达到最大的可行解称为最优解。线性规划问 题中的最优解，一定可以在基可行解中找到，而基可行解的数量是有限的，因 而这就在理论上保证了可以在有限的步骤之内求出线性规划问题的最优解。 |,0D=x xA A x xb b x x 1 0 B - =x xB Bb b m n C 线性规划问题中解的概念 v 实例 线性规划标准型为 于是 取矩阵A的线性无关列P1和P2构成2阶非奇异子矩阵 ，B1是线性规划问题的 一个 基矩阵，与其对应的基变量为x1和x2，即 ，相应的非基矩阵和非基变量分别为 令非基变量x3=0，可以求出对应基矩阵B1的基本解为 ，基矩阵B

14、1解向量的各分 量均为非负，故是线性规划问题的基本可行解。如果这个解可以使得目标函数取得最大值则该解为最 优解。是否最优解的判断方法将在后续的章节中探讨。 若取矩阵A的后两个线性无关列P2和P3，构成线性规划的另一个基矩阵 用相同的方法进行分析，可知，此时的基变量为x2和x3，非基变量为x1，于是令x1=0，可以得到对 应基矩阵B2的一组基本解为： ，由于对应基矩阵B2解向量的第二个分量 即x3为负，故该解不是线性规划问题的基本可行解 由理论分析可知，该线性规划问题基本解的个数为3个，也就是还可以选取P1和P3构成基矩阵B3， 求取该问题的第三个基本解，只要有一个基矩阵，就可以求出一个对应的基

15、本解，至于该基本解是否 基本可行解和最优解则需要进一步判断。 123 123 123 123 2 m ax 3 s. t. 21 , ,0 fxxx xxx xxx x x x = -+- += -= 123 111 112 轾 轾 犏= 犏 臌 犏 - APPPAPPP 112 11 11 轾 轾犏 = 犏 犏臌 - 犏 臌 BPPBPP 1 12 T B xx 轾 = 犏 臌 x x 13 1 2 轾 犏 = 犏 - 犏 臌 NPNP 1 3N x=x x 1 210 轾 = 犏 臌 B B x x 223 11 12 轾 轾犏 = 犏 犏臌 - 犏 臌 B BP PP P 2 074 轾

16、 =- 犏 臌 B B x x 线性规划问题的图解法 v 用图解法求解如下二维线性规划问题 分析可行域 引入平面直角坐标系，以x1作为横轴，以x2作为纵轴，由于线性规划问题满足非负 条件x1, x20，故问题的探讨局限在平面直角坐标系的第一象限 分析x1-2x24，取直线x1-2x2=4，则直线上的点和直线以上的区域满足该不等式 分析x1+2x28，取直线x1+2x2=8，则直线上的点和直线以下的区域满足不等式 于是可行域为四边形ACBO内的区域（包括边界上的点），在图中用阴影表示 分析最优解 分析目标函数f =x1+x2，可以将其改写成为x2=-x1+ f 可以发现改写后的方程是以f为参量，

17、以-1为斜率的一 族平行的直线，这些平行线越向右上方移动，离原点 越远，对应的目标函数值就越大。当直线运动到经过 点C时，即不能再继续向上移动，否则将脱离线性规 划问题的可行域，故线性规划问题在点C达到最大值 12 12 12 12 m ax 24 s. t. 28 ,0 fxx xx xx x x =+ - + 线性规划问题求解的单纯形法 v 理论基础 称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

18、 ，且在该列中的bi,m+s0 (i=1,2,m)， 则线性规划问题无最优解 ( ) 0001020 1011121 11 20212222 11 012 n n BB mmmm n bbbb bbbb bbbbT bbbb - - 骣 骣 - = 桫 桫 c c B Bb bc c B BA Ac c B B B Bb bB BA A L L L LLLLL L 线性规划问题求解的单纯形法 v 单纯形迭代(步骤1) 建立初始单纯形表T(B)，确定T(B)中的枢点（Pivot）项 确定进基变量 在所有b0j0的检验数中，选出最小的一个b0s，对应的非基变量为xs , 此时，即已确定xs为进基变

19、量为进基变量，即下一次的迭代中将以xs作为进基变量 确定出基变量 取 （若有几个相同的最小者，则取基变量下标最小者）记 此时， 即已确定出基变量为出基变量为xr 确定枢点项 由确定出基变量时所得的结论，可知，brs即被称为枢点项即被称为枢点项，此时，需要对枢点项brs 进行标注，例如右上角加*号或者用括号括起来等方式，以便于后面的讨论和分析 0 m i n i is b b 00 m i n ir isrs bb bb = 1 ss - = P PB BP P 线性规划问题求解的单纯形法 v 单纯形迭代(步骤2) 调换基变量，构造新基，构造新的单纯形表 确定新基 对单纯形表进行变换 目的是使得

20、下一步对基 的单纯形表 进行适当的变换，使得向量 变为 单位向量，即使得分量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行的数，即 换基后，新基 仍是一个可行基，且目标函数值增加 () 1211 , , rsrm-+ = B BP P P PP PP

21、 P P PP PLL ()T B B B()TB B s P P ()0 rj rj rs b bjn b = is rs b b () 0,0 is ijijrj rs b bbbijmjn b = -祝梗 B 线性规划问题求解的单纯形法 v 单纯形迭代(重复上述1,2过程) 按照上面步骤(1)(2)进行重复迭代，循环操作，以求得最优解 特别注意 需要特别注意的是，如果基B对应的单纯形表T(B)中检验数有负数b0s0 ，且对应 的如下列向量非正，即： 那么，目标函数无上界，即无最优解。 1 2 1 0 s s ss m s b b b - 骣 = = 桫 PBPPBP M 线性规划问题求解

22、的单纯形法 v 用单纯形法求解线性规划问题 将上述问题转化为线性规划标准型 确定A和Pi 确定xB1初始基、初始基矩阵B1、非基变量等 确定一个基本解 12 12 12 12 12 43 m ax 3412 3310 428 ,0 fxx xx xx xx x x =+ + + + 12 123 124 125 43 m ax 3412 s. t. 3310 428 0 (1,2,. . . 5) i fxx xxx xxx xxx xi =+ += += += = 12345 34010 3 ,3 ,0 ,1 ,0 00421 轾轾轾轾轾 犏犏犏犏犏 犏犏犏犏犏 = 犏犏犏犏犏 犏犏犏犏犏

23、犏犏犏犏犏 臌臌臌臌臌 P PP PP PP PP P 34100 33010 42001 轾 犏 犏 = 犏 犏 犏 臌 A A 345B xxx 轾 = 犏 臌 x x 1345 100 010 001 轾 犏 犏 轾 = 犏 犏 臌 犏 犏 臌 B BP PP PP P 12N xx 轾 = 犏 臌 x x 1 1 12 10 8 B - 轾 犏 犏 = 犏 犏 犏 臌 xBbbxBbb 线性规划问题求解的单纯形法 确定初始单纯形表 构建初识单纯形表如表所示，从行的角度说，表中的每一行代表一个约束方程（把目标函数也每一行代表一个约束方程（把目标函数也 看做是约束方程放在第一行）看做是约束

24、方程放在第一行）。从列的角度讲，对于约束方程而言，表中的第一列即为约束对于约束方程而言，表中的第一列即为约束 方程右边的值，而对于目标函数方程右边的值，而对于目标函数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。 由例题求初始基可行解的过程可知，如果线性规划

25、标准型的向量b的每一个分量均为正的话， 当令所有的松弛变量为基时，总是可以找到一组基本可行解。这时每个基本变量的值等于其方 程右端的常数。由于此时目标函数的系数全都为零，所以对应的目标函数值也为零。我们的目 的就是要使用单纯形法，通过变换运算，在每次迭代的最后，使得当前基本变量对应的矩阵B 形成一个单位阵，并且目标函数中对应于基本变量的系数变为零目标函数中对应于基本变量的系数变为零。具有这种性质的表称之为规规 范型范型 Valuex1x2x3x4x5 f0-4-3000 x31234100 x41033010 x5842001 初始单纯形表 线性规划问题求解的单纯形法 单纯形迭代 对单纯形表进

26、行判别 在单纯形表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。我们把枢点项用括号括起来如表所示 1 334

27、 T 轾 = 犏 臌 p p 01 /(1,2,3) ii bbi= ()() 102030 112131 12 10 810 m i n,m i n,m i n 4,22 3343 bbb bbb 骣 = 桫 3031 /bb 标记枢点项 Valuex1x2x3x4x5 f0-4-3000 x31234100 x41033010 x58(4)2001 线性规划问题求解的单纯形法 调换基变量，构造新的基矩阵B2和单纯形表 出基变量为x5，进基变量为x1，于是新的基矩阵 使得当前基变量对应的矩阵B2形成一个单位阵，并且目标函数中对应于基本变量的 系数变为零，结果如表所示 在得到新的单纯形表之后，

28、一次迭代完成一次迭代完成。 我们需要进行判断是否进行再次迭代，采用的方法和上一次的迭代完全相同。 2341 103 013 004 轾 犏 犏 轾 = 犏 犏 臌 犏 犏 臌 B BP PP PP P Gauss-Jordan消元 Valuex1x2x3x4x5 f80-1001 x3605/210-3/4 x4403/201-3/4 x1211/2001/4 线性规划问题求解的单纯形法 二次迭代 经过与一次迭代完全相同的步骤，得到单纯形表 在该单纯形表中，检验数已没有负数检验数已没有负数，故最新的基矩阵所对应的基本可行解即是线 性规划问题的最优解了。此时线性规划问题的最优解为： 对应的目标函

29、数的极值为 二次迭代单纯形表 Valuex1x2x3x4x5 f52/5002/507/10 x212/5012/50-3/10 x42/500-3/51-3/10 x14/510-1/502/5 241 1224 * 555 T T xxx 轾 轾 = 犏 犏 臌 臌 x x * 52 5 f= 一般情况下线性规划问题求解的思路 v 何时使用大M法 我们可以看到在上面的例子中，不等式约束均有不等式约束均有“”的形式的形式，这样才可以通 过将非负松弛变量加到（而不是减去）每个不等式的左端，将不等式转化为等 式，这时，我们将所加的松弛变量作为初始基变量，所得到的基矩阵为一单位基矩阵为一单位 阵阵

30、，可以很容易的获得一个初始基本可行解进行单纯形法的迭代。 但是在一般情况下，线性规划问题的约束条件存在等式和不等式，同时不等式 也存在“”和“”，注意到当约束方程组中含有含有“=”约束约束时，我们不需要加 入非负松弛变量，当约束方程组中含有含有“”约束约束时，我们需要减去一个非负 松弛变量，在这两种情况下就无法形成单位阵无法形成单位阵作为初始的基矩阵进行求解，即 不能顺利得到一个初始基本可行解，从而造成了迭代的困难。 于是我们需要找到一种系统处理方法，能够比较方便的在各种约束条件下都能 找到线性规划问题的初始可行基本解使得单纯形算法在任何约束下均有效。此 时，我们需要用到人工变量人工变量，而将

31、人工变量用于单纯形求解中的算法主要有大大 M法和两阶段方法法和两阶段方法 线性规划问题求解的大M法 v 大M法的求解原理 大M法的原理是，先将线性规划问题变换成标准型，然后将新的非负变量加到 具有“=”或者“”类型约束的方程的左端，于是用这些新的变量作为基变量 就可以构成一个初始可行基。我们人为加入的这些非负变量就称为人工变量。 人工变量与松弛变量不同人工变量与松弛变量不同，它没有明确的物理意义，只是为了获得一个初始可 行基而设置的。 但是对任何一个约束增加非负变量之后与原约束就是矛盾的，为了解决这个矛 盾，使得新增加的变量对任一可行解无影响，我们在目标函数中给新增加的变在目标函数中给新增加的

32、变 量赋以一个很大的负系数量赋以一个很大的负系数（因为线性规划的标准型为目标函数求极大），这个 系数通常用M来表示，因而这个方法又叫大M法。在目标函数中使用一个大的 “-M”是迫使新的变量为零，否则目标函数将远不能达到极大值。 线性规划问题求解的大M法 v 使用大M法求解线性规划问题 引入人工变量x4和x5到约束等式的左边 单纯形法求解 首先取x4和x5作为初始基变量 令非基变量x1=x2= x3=0，得到一个基本解 解的各分量均为非负，故该基本解为线性规划的一个基本可行解。故可用单纯 形法开始迭代。 123 123 123 m ax3 s. t.24 24 0 (1,2,3) j fxxx

33、xxx xxx xj =+- += -+= = 12345 1234 1235 m ax3 s. t.24 24 0 (1,2,. . . ,5) j fxxxM xM x xxxx xxxx xj =+- += -+= = 11210 12101 轾 犏 = 犏 - 犏 臌 A A 12345 01121 , 01121 轾轾轾轾轾 犏犏犏犏犏 = 犏犏犏犏犏 - 犏犏犏犏犏 臌臌臌臌臌 P PP PP PP PP P 145 10 01 轾 轾犏 = 犏 犏臌 犏 臌 BPPBPP 1 1 4 4 B - 轾 犏 = 犏 犏 臌 xBbbxBbb 线性规划问题求解的大M法 单纯形迭代 按照

34、单纯形法，构造初始单纯形表，注意其中含有M项，但这并不影响求解过程并不影响求解过程 上表并非单纯形表的规范性，因为目标函数对应于基变量x4和x5的系数不为零，故我们采用矩 阵的行变换将上表转化为规范型 然后和单纯形法一致，经过迭代得到最终单纯形表为 上表3中，检验数已没有负数，故已经求出线性规划问题的的最优解 Valuex1x2x3x4x5 f0-1-31MM x4411210 x54-12101 Valuex1x2x3x4x5 f-8M-1-3M -3-3M +100 x4411210 x54-1(2)101 Valuex1x2x3x4x5 f28/3005M+5/3M+2/3 x14/31

35、012/3-1/3 x28/30111/31/3 12 48 * 33 T T xx 轾 轾 = 犏 犏 臌 臌 x x * 28 3 f= 线性规划问题求解的两阶段法 v 两阶段法的原理 两阶段也是用以解决具有“=”或者“”类型约束的线性规划问题的初始可行 解问题。顾名思义，该方法分为两个阶段进行： 第一阶段 先引入松弛变量和人工变量，而目标函数则由人工变量的和组成。这一步的工作是 用单纯形法把目标函数对应的所有的人工变量的值变为零。若第一阶段最优解对应 的目标函数的最优值为零，则所有人工变量一定都取零值，说明原问题存在基可行 解，可以进行第二阶段的计算；否则，原问题无可行解，停止计算。 第

36、二阶段 用原问题的的目标函数代替人工目标函数，用第一阶段获得的基本可行解作为该阶 段迭代的初始点进行单纯形的换基迭代。 线性规划问题求解的两阶段法 v 用二阶段法求解线性规划问题 化为标准型 在原问题的不等式约束中分别加入松弛变量x4和x5，将上述问题化为标准型 在上述标准型问题中，由于不存在单位阵基矩阵，故我们需要引入人工变量人 为的构造出单位阵基矩阵构造出单位阵基矩阵，故我们采用两阶段法。 123 123 123 13 m ax3 s. t.211 423 21 0 (1,2,3) j fxxx xxx xxx xx xj =- -+ -+ -+= = 123 1234 1235 13 m

37、 ax3 s. t.211 423 21 0 (1,2,. . . ,5) j fxxx xxxx xxxx xx xj =- -+= -+-= -+= = 线性规划问题求解的两阶段法 第一阶段第一阶段 构造辅助问题构造辅助问题，加入人工变量x6和x7，并将目标函数表示称为人工变量的和，目的就是为 了构造单位阵，辅助问题的形式如下： 我们用单纯形法对该问题进行求解，可见，由于加入了人工变量，使得现在的辅助问题的 约束方程组中形成了单位阵，即我们选取x4、x6和x7为基变量的话，基矩阵即是一个单位 阵，然后在辅助问题的初始单纯形表的基础上将其转换成为规范型如下 于是在上述表的基础上进行单纯形迭代

38、，以求出辅助问题的最优解 67 1234 12356 137 m ax s. t.211 423 21 0 (1,2,. . . ,7) j fxx xxxx xxxxx xxx xj = - -+= -+-+= -+= = Valuex1x2x3x4x5x6x7 f-46-1-30100 x4111-211000 x63-4120-110 x71-20(1)0001 线性规划问题求解的两阶段法 第一阶段第一阶段 单纯形迭代单纯形迭代 一次迭代后的单纯形表为 二次迭代后的单纯形表为 检验数均非负，故辅助问题最优解 此时，目标函数最优值 ，且人工变量已全部出基。故第一阶段结束，转入 第二阶段 V

39、aluex1x2x3x4x5x6x7 f-10-100103 x4103-20100-1 x610(1)00-11-2 x31-2010001 Valuex1x2x3x4x5x6x7 f00000011 x4123001-22-5 x210100-11-2 x31-2010001 * 0127 01112000 T xxx 轾轾 = 犏犏 臌臌 x xL * 0f = 线性规划问题求解的两阶段法 第二阶段第二阶段 求解原线性规划问题。这时以在第一阶段筛选出来的基变量构成基矩阵作为原线性规划 问题的初始可行基，并将辅助问题的最优解删去人工变量的两列，作为原线性规划问题 的初始可行解，然后进行单纯

40、形算法的换基迭代 在这个问题中，初始可行基为： 初始可行解为： 在单纯形表中删去人工变量删去人工变量x6和和x7这两列，把第这两列，把第1行换成原问题的目标函数行换成原问题的目标函数（消去基变量 以后）的系数得到下表 可以看出，基变量x4，x2和x3没有构成单位阵，此时先要进行线性变化，例如在本例中就 需要将f所在行减去x2所在行和x3所在行的和，之后得到新表就可以继续换基迭代 Valuex1x2x3x4x5 f0-31100 x4123001-2 x210100-1 x31-20100 1423 轾 = 犏 臌 B BP PP PP P 1 125 011120 T xxx 轾轾 = 犏犏

41、臌臌 B B x xL Valuex1x2x3x4x5 f-2-10001 x412(3)001-2 x210100-1 x31-20100 线性规划问题求解的两阶段法 第二阶段第二阶段 换基迭代，换基迭代，由上页新表可知检验数b01为唯一的负数，故进基变量为x1，而在进基变量x1 所在列中只有b11元素为正，进而确定枢点元素为b11，故出基变量为x4，然后使用Gauss- Jordan消元法结果如表所示，此时检验数已经全部非负，故已找到该问题的最优解 根据表上的数据可知，目标函数的最大值在最优解x*处取得： Valuex1x2x3x4x5 f20001/31/3 x141001/3-2/3

42、x210100-1 x390012/3-4/3 * 41900 T x 轾 = 犏 臌 * 2f= 线性规划问题的MATLAB求解 v MATLAB标准型 MATLAB标准型和前面理论知识讲解中有所不同， 在上述模型中，有一个需要极小化的目标函数f，以及需要满足的约束条件 假设x为n维设计变量，且线性规划问题具有不等式约束m1个，等式约束m2个，那 么：c、x、lb 和ub 均为n维列向量，b为m1维列向量，beq为m2维列向量，A为 m1n维矩阵，Aeq为m2n维矩阵 注意事项 MATLAB标准型是对目标函数求极小求极小，如果遇到是对目标函数求极大的问题，在使 用MATLAB求解时，需要在函

43、数前面加一个负号转化为对目标函数求极小的问题； MATLAB标准型中的不等式约束形式为不等式约束形式为“”，如果在线性规划问题中出现“” 形式的不等式约束，则我们需要在两边乘以(-1)使其转化为MATLAB中的“”形 式。如果在线性规划问题中出现了“”的约束形式，则我们需要通过添加 松弛变量使得不等式约束变为等式约束 之后，我们只需要将所有的约束（包括不等式约束和等式约束）转化为矩阵形式的 即可 m i n s. t. T eqeq f = = c c x x A A x xb b A Ax xb b l l b bx xu ub b 线性规划问题的MATLAB求解 v 将问题转化为MATLA

44、B标准型 原问题是对目标函数求极大，故添加负号使目标变为：min f=-4x1+2x2-x3 原问题中存在“”的约束条件，故添加负号使其变为8x1-2x2+2x3-8 将约束整理为矩阵形式 用MATLAB表达则为 123 123 123 13 12 123 42 m ax 212 s. t. 8228 23 7 , ,0 fxxx xxx xxx xx xx x x x =-+ -+ -+- -+= += 1 2 3 12 211 8 822 x x x 轾 犏 轾 轾 - 犏 犏 犏 犏 犏 犏- -犏犏 臌 犏 臌 1 2 3 3 201 7 110 x x x 轾 犏 轾 轾 - 犏 犏

45、 犏= 犏 犏 犏 臌犏犏 臌 犏 臌 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求解 v 函数调用格式 MATLAB优化工具箱中求解线性规划问题的命令为linprog，其函数调用方法 有多种形式如下所示 x = linprog(c,A,b) x = lin

46、prog(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求解 v

47、输入参数 MATLAB工具箱中的linprog函数在求解线性规划问题时，提供的参数为：模 型参数、初始解参数和算法控制参数。 模型参数x、c、lb、ub、b、beq、A和Aeq在MATLAB标准型中已经介绍了其具体 物理意义和获得方法 x0为线性规划问题的初始解，该设置仅在中型规模算法中有效，而在默认的大型规 模算法和单纯形算法中，MATLAB将忽略一切初始解。 options为包含算法控制参数的结构变量，我们可以通过optimset命令对这些具体 的控制参数进行设置，例如下述格式 options = optimset(param1,value1,param2,value2,.) 该命令格式创

48、建一组控制参数结构变量options，将参数的具体值赋给单引号之间的 参数，任何未被指定的参数将被赋值为，参数值为的具体的含义是将该组控制参 数传递给优化函数时将使用MATLAB提供的默认值 在线性规划问题中可以用到的设置参数如下一页的表所示 线性规划问题的MATLAB求解 参数名称参数设置 Diagnostics设置是否显示函数优化中的诊断信息，可以选择on或者off（默认值），该功能主要 显示一些退出信息，即linprog函数运算终止的原因 Display设置显示信息的级别，当该参数值为off时 ，不显示任何输出信息；当参数值为iter 时，将显示每一步迭代的输出信息，iter参数值仅对大

49、型规模算法和中型规模的单 纯形算法有效；当参数值为final时，仅显示最终的输出信息 Simplex当该参数值为on时，函数采用单纯形算法 LargeScale设置是否采用大型规模算法，当参数值为on（默认值）时，使用大型规模算法；当 参数值为off时，使用中型规模算法 MaxIter算法运行中的最大迭代次数，对于大型规模算法，默认值为85，对于单纯形算法， 其默认值为10*设计变量的个数，对于中型有效集算法为10*max(设计变量的个数， 不等式约束的个数+边界约束的个数) TolFun函数计算终止的误差限，对于大型规模算法其默认值为1e-8，该控制参数对于中型 规模的有效集算法无效。 线性

50、规划问题的MATLAB求解 v 输出参数 linprog函数返回的输出参数有x、fval、exitflag、lambda和output。 输出参数x为线性规划问题的最优解 输出参数fval为线性规划问题在最优解x处的函数值 输出参数exitflag返回的是优化函数计算终止时的状态指示，说明算法终止的 原因，其取值和其代表的具体原因如表所示 值物理意义 1已经收敛到解x 0已经达到最大迭代次数限制options.MaxIter -2没有找到问题的可行点 -3问题无有限最优解 -4在算法执行过程中遇到了NaN值 -5原线性规划问题和其对偶问题均不可行 -7搜索方向变化太小，无法进一步获得更优解，说

51、明原线性 规划问题或者约束条件是病态的 线性规划问题的MATLAB求解 v 输出参数 输出参数output是一个返回优化过程中相关信息的结构变量，其属性如表所 示 输出参数lambda是返回线性规划问题最优解x处的拉格朗日乘子的一个结构 变量,其总维数等于约束条件的个数，其非零分量对应于起作用的约束条件， 其属性如表所示。 属性名称属性含义 output.iterations优化过程的实际迭代次数 output.algorithm优化过程中所采用的具体算法 output.cgiterations0（仅用于大型规模算法，为了后向兼容性而设置的参数） output.message退出信息 属性名称

52、属性含义 ineqlin线性不等式约束的拉格朗日乘子 eqlin线性等式约束的拉格朗日乘子 upper上界约束的拉格朗日乘子 lower下界约束的拉格朗日乘子 线性规划问题的MATLAB求解 v 命令详解 x = linprog(c,A,b) 该函数调用格式求解线性规划问题 x = linprog(c,A,b,Aeq,beq) 该函数调用格式求解线性规划问题 即该函数调用格式解决的是既含有线性等式约束，又含有线性不等式约束的线性规划问 题，如果在线性规划问题中无线性不等式约束，则可以设A=以及b= x = linprog(c,A,b,Aeq,beq,lb,ub) 该函数调用格式求解线性规划问题

53、 即在线性规划问题的求解过程中进一步考虑了对设计变量的约束，其中lb和ub均是和设 计变量维数相同的列向量，如果对设计变量没有上界约束，可以设置ub(i) = Inf，如果 没有下界约束则可以设置lb(i) = -Inf，和(2)类似，如果问题中没有等式约束，则可以 设Aeq=以及beq= m i n s. t. T f = c c x x A A x xb b m i n s. t. T eqeq f = = c xc x A xbA xb AxbAxb m i n s. t. T eqeq f = = c xc x A xbA xb AxbAxb l bxubl bxub 线性规划问题的M

54、ATLAB求解 v 命令详解 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(.) 在优化计算结

55、束之时返回exitflag值，描述函数计算的退出条件。 x,fval,exitflag,output = linprog(.) 在优化计算结束之时返回返回结构变量output x,fval,exitflag,output,lambda = linprog(.) 在优化计算结束之时返回线性规划问题最优解x处的拉格朗日乘子lambda 线性规划问题的MATLAB求解 v 用MATLAB求解线性规划问题 c=-1;-1;%目标函数，为转化为极小，故取目标函数中设计变量的相反数目标函数，为转化为极小，故取目标函数中设计变量的相反数 A=1 -2;1 2;%线性不等式约束线性不等式约束 b=4;8; l

56、b=0;0;%设计变量的边界约束，由于无上界，故设置设计变量的边界约束，由于无上界，故设置ub=Inf;Inf; ub=Inf;Inf; x,fval=linprog(c,A,b,lb,ub) Optimization terminated. x = 6.0000 1.0000 fval = -7.0000 12 12 12 12 m ax 24 s. t. 28 ,0 fxx xx xx x x =+ - + 线性规划问题的MATLAB求解 v 用MATLAB求解线性规划问题 c=-4;-3; %目标函数，为转化为极小，故取目标函数中设计变量的相反数目标函数，为转化为极小，故取目标函数中设计

57、变量的相反数 A=3 4;3 3;4 2; %线性不等式约束线性不等式约束 b=12;10;8; lb=0;0; %设计变量的边界约束，由于无上界，故设置设计变量的边界约束，由于无上界，故设置ub=Inf;Inf ub=Inf;Inf; x,fval,exitflag=linprog(c,A,b,lb,ub) x = 0.8000 2.4000 fval = -10.4000 exitflag = 1 12 12 12 12 12 43 m ax 3412 3310 428 ,0 fxx xx xx xx x x =+ + + + 线性规划问题的MATLAB求解 v 用MATLAB求解线性规划

58、问题 123 123 123 m ax3 s. t.24 24 0 (1,2,3) j fxxx xxx xxx xj =+- += -+= = c=-1;-3;1; %目标函数，为转化为极小，故取目标函数中设计变量的相反数目标函数，为转化为极小，故取目标函数中设计变量的相反数 Aeq=1 1 2;-1 2 1;%线性等式约束线性等式约束 beq=4;4; lb=0;0;0;%设计变量的边界约束，由于无上界，故设置设计变量的边界约束，由于无上界，故设置ub=Inf;Inf;Inf ub=Inf;Inf;Inf; x,fval,exitflag=linprog(c,Aeq,beq,lb,ub)

59、Optimization terminated. x = 1.3333 2.6667 0.0000 fval = -9.3333 exitflag = 1 线性规划问题的MATLAB求解 v 用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;%设计变量的边界约束，由于无上界，故设置设计变量的边界约束，由于无上界，故设置u

60、b=Inf;Inf;Inf ub=Inf;Inf;Inf; x,fval,exitflag,output,lambda=linprog(c,A,b,Aeq,beq,lb,ub) Optimization terminated. x = 4.0000 1.0000 9.0000 fval = -2.0000 exitflag = 1 123 123 123 13 m ax3 s. t.211 423 21 0 (1,2,3) j fxxx xxx xxx xx xj =- -+ -+ -+= = 线性规划问题的MATLAB求解 v 生产计划问题 问题的提出 某工厂需要生产A、B两种产品以满足市场