第3讲线性规划及单纯形

《第3讲线性规划及单纯形》由会员分享，可在线阅读，更多相关《第3讲线性规划及单纯形（18页珍藏版）》请在金锄头文库上搜索。

1、1线性规划及单纯形1 规划问题及模型1.1 问题提出与建模(1) 生产计划问题某工厂用三种原料生产三种产品，已知的条件如表所示，试制订总利润最大的生产计划。单位产品所需原料数量（吨） 产品 Q1 产品 Q2 原料可用量（吨/日）原料 P1 4 4 28原料 P2 4 2 20原料 P3 8 32原料 P4 2 4 24单位产品的利润（万元） 4 6问题分析可控因素：每天生产产品的数量，分别设为 x1，x 2目标：每天生产利润最大，利润函数 4x16x 2受制条件：每天原料的需求量限制原料 P1：4x 14x 2 28原料 P2：4x 12x 2 20原料 P3：8x 132原料 P4：2x 1

2、2x 2 24内蕴约束：产量非负性x1，x 2 0建立模型Max 4x16x 220,243848.21121xxts1.2 模型的标准化各种类型的规划问题的线性模型大体上是相同的，既在一组约束条件下寻找极值。规划的一般形式为： nxcxc. ZMax(in)210,. ),(. ,.)(.212 22212 11n mnmmnxbxaats为了讨论的方便，我们规定线性规划问题的标准形式为： nxcc.Ma Z210,.21222212 11nmnmnxbxaaxts可简写成： jjc1Ma Z0.1jinjixbts njmi,.21,.注：要求 ，否则两端都乘以“1” 。ib进一步简写成矩

3、阵形式：3CXMax Z0.bAts其中：为价值向量，),(21ncC为决策变量，xX为系数矩阵。为右端向量，),.(21mbb1.3 模型的转换(1) 目标转换如何处理 的问题？令 ,转求 即可。CXMin ZZ MinZax (2) 约束转换：左端加入非负松弛变量； ：左端减去非负松弛变量（又另称剩余变量）iniii bxaxa210,11niiii x或iniii baxa21 0,1121 niniii x(3) 变量转换若 无约束（即可正可负）如何处理？令 ，通过变成两个非jx )2()1(jjjx负变量的差便可解决。nnaaA 221142 代数解法我们以下面的标准型规划问题为例进

4、行代数分析：Max Z =4x16x 2系数矩阵为0,242388.65312512xxts 10428(1) 确定初始基变量易知 为基变量， 为非基变量。6543,x21,x21652144280xx TX)24,30,8()0 0621xZ(2) 更新基变量为使得变换后目标函数 增幅最大，因 系数较大故宜选 为216xZ2x2x入基变量。由 26524308xx可知道，随着 增加， 最先破坏非负要求（ ） ，6 6)42,08min(因此 最脆弱，被选为出基变量。从而 为基变量， 为非基变量。6x 2543,x1x61256143482xxx TX)0,3284,6()1 364361xZ

5、5(3) 第二次更新基变量为使得变换后目标函数 增幅最大，只能选 为入基变量。6143xZ1x由 125143682xx可知道，随着 增加， 最先破坏非负要求（ ） ，因3 2)16,83,24min(此 最脆弱，被选为出基变量。从而 为基变量， 为非基变量。3x 2541,x63,x632561431242xxx TX)0,162,5()2 38213863xZ此时目标函数表达式之系数皆为负，停止迭代计算。这种代数解法实际上就是单纯形算法。3 规划问题的解3.1 解的相关概念下面介绍线性规划问题解的基本概念。(1) 可行解（可行域）满足约束条件的变量的值，称为可行解。所有可行解之集合 D 为

6、可行域。(2) 最优解（最优值）使目标函数取得最优值的可行解，称为最优解，对应的目标函数值为最优值。6(3) 基本解（基变量与非基变量）设 r(A)=m,并且 B 是 A 的 m 阶非奇异的子矩阵（det(B )0),则称矩阵 B 为线性规划问题的一个基。矩阵 B=（P 1，P 2.Pm) ，其列向量 Pj 称为对应基 B 的基向量。与基向量 Pj 相对应的变量 xj 就称为基变量，其余的就称为 非基变量。对于某一特定的基 B，非基变量取 0 值的解，称为基本解。基本解的非零分量如果小于 m 则称为退化基本解。我们本章讨论都是假设不出现退化的情况。, )(NA1),(NBXbb 分 块BNB1

7、11 左 乘 00XN其中 B 是基，N 是非基；X B是基变量，X N是非基变量； X 是基本解。(4) 基本可行解（可行基）满足非负约束条件的基本解，称为基本可行解（即 ） 。此时对应的01bB基阵 B 为可行基。7以 max Z = 2x1 + 3x2 s.t. -2x1 + 3x2 6 3x1- 2x2 6 x1+x2 4 x1, x2 0 为例来说明本问题解的情况：可行解：由点（O，Q 1，Q 2，Q 3，Q 4）围成的区域。基本解：点（O，A，B，Q 1，Q 2，Q 3，Q 4）基本可行解：点（O，Q 1，Q 2，Q 3，Q 4）3.2 解的图解表示对于只有两个变量的线性规划问题可

8、以用图解法求解：变量用直角坐标系中的点表示；约束条件用坐标系中的半空间或直线的交表示；可行域是一个凸多面体；目标函数用一组等值线表示，沿着增加或减少的方向移动，与可行域最后的交点就是最优解。例如：求解问题 052.max11xtsz最优解（1，4） ，最优值 3821x21x521当目标函数改变后，等值线的方向会发生改变，如果等值线与某个约束对应的函数直线平行，则该函数值线上的所有可行解都是最优解，也就是说有无穷多个最优解。21x21x3.3 解的基本定理凸集概念：设 D 是 n 维线性空间 Rn 的一个点集，若 D 中的任意两点 x(1),x(2)的连线上的一切点 x 仍在 D 中，则称 D

9、 为凸集。即：若 D 中的任意两点 x(1),x(2) D，存在 01 使得x= x(1)+(1- )x(2) D,则称 D 为凸集凸组合：设 x(1),x(2) .x(k)是 n 维线性空间 Rn 中的 k 个点，若存在数u1,u2,.uk 且 0ui1 (i=1,2,k), ui =1,使得 x= u1 x(1)+ u2 x(2) +.+ uk x(k) 成立，则称 x 为 x(1),x(2) .x(k)的凸组合。顶点：设 D 是凸集, 若 D 中的点 x 不能成为 D 中任何线段上的内点，则称 x 为凸集 D 的顶点。即：若 D 中的任意两点 x(1),x(2) ，不存在数 （0 1）

10、使得 x= x(1)+(1- )x(2)成立，则称 x 为凸集 D 的一个顶点。定理 1 线性规划问题的可行解集是凸集。 （即连接线性规划问题任意两个可行解的线段上的点仍然是可行解。)定理 2 线性规划问题的可行解 x 为基础可行解的充分必要条件是：x 的非零分量所对应的系数矩阵 A 的列向量是线性无关。定理 3 线性规划问题的可行解 x 为基础可行解的充分必要条件是：x 是可最优解（1，4） ，最优值 3 521x9行域 D 中的顶点。推论：可行解集 D 中的顶点个数是有限的。推论：若可行域 D 是有界的凸集，则 D 中任意一点 x，都可表示成 D 的顶点的凸组合。定理 4 若可行域 D 有

11、界，则线性规划问题的最优解，必定在 D 的顶点上达到。以上定理证明在此略去，有兴趣的同学请查阅运筹学等相关书籍。3 单纯形思想规划理论：规划理论可以划分为两大部分。第一部分是研究在满足外部约束下规划的内部配合，即研究相互依赖的各项因素之间的配合。第二部分是讨论规划的最优性问题。数学规划：属于运筹学范畴，研究在现有人力、财力和物力等资源下，通过合理配置与使用达到最优目标的数学方法。线性规划（Linear Programming，简称 LP)：以线性假设为前提的数学规划。单纯形法：解法统一简单，解具有精确的全局最优性。这里，必须谈到两个著名的人物，康托洛维奇和丹齐克。1939 年著名数理经济学者康

12、托洛维奇发表了生产组织和计划中的数学方法这一运筹学的先驱性名著，其中已提到类似线性规划的模型和“解乘数求解法”。但是他的工作直到 1960 年的最佳资源利用的经济计算一书出版后，才得到重视。1975 年，康托洛维奇与 T . C . Koopmans 一起获得了诺贝尔经济学奖。1947 年 G . B. Dantzig 在研究美国空军军事规划时提出了线性规划的模型和单纯形解法，并很快引起美国著名经济学家 Koopmans 的注意。Koopmans 为此呼吁当时年轻的经济学家要关注线性规划。今天，单纯形法及其理论已成为了线性规划的一个重要的部分。103.1 线性规划发展历史线性规划创始人：G.B

13、.丹齐克（Dantzig）1947 年美国人 Dantzing 开始研究 LP1951 年 Dantzig 提出单纯形算法（Simpler）1963 年 Dantzig 写成“Linear Programming and Extension”1979 年原苏联的 Khachian 提出“椭球法”1984 年印度的 Karmarkar 提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。单纯形是美国数学家 G.B.丹齐克于 1947 年首先提出来的。它的理论根据是：线性规划问题的可行域是 n 维向量空间 Rn 中的多面凸集，其最优

14、值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形算法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。例 1、求解问题5,.21;03.2max241jxtszj解答：以 、 和 为基变量就可以得到初始基可行解 ，145 )2,10(其对应的单纯形表为（注意实际解题中可以简单类似如下列表）：1x23x45x z1 -2 0111 -2 1 1 -3 11 -1 1212由于 ，所以该基可行解不是最优解，同时系数矩阵该列有大于 0 的元012素，所以取 为入基变量。计算 ，所以取第二个约束对应的基x,min12变量 为出基变量，就可以得到一个新的基可行解，在上表中把 对应的列变4 2x成单位向量，系数矩阵第 2 行对应的元素为 1，则可以得到该基可行解的单纯形表1x23x45x z0 1 -1 -11 0 -5 21 -3 10 2 -1 1411由于 ，所以该基可行解不是最优解，同时系数矩阵该列有大于 0 的元13素，所以取 为入基变量。计算 ，所以取第 3 个约束对应的基变量 为x21 5x出基变量，就可以得到一个新的基可行解，在上表中把