运筹学线性规划PPT演示文稿

《运筹学线性规划PPT演示文稿》由会员分享，可在线阅读，更多相关《运筹学线性规划PPT演示文稿（154页珍藏版）》请在金锄头文库上搜索。

1、1,赵立强,管理运筹学教程,2,第一章 线性规划 线性规划是运筹学的一个重要分枝。自1947年美国数学家丹捷格（G.B.Dantzig）提出了求解线性规划问题的方法单纯形法之后，线性规划在理论上趋于成熟，在实际中的应用日益广泛与深入。特别是在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后，它的适用领域更加广泛。从解决技术问题中的最优化设计到工业、农业、商业、交通运输业、军事、经济计划与管理、决策等各个领域均可发挥重要作用；从范围来看，小到一个小组的日常工作和计划安排，大至整个部门以致国民经济计划的最优方案的提出，都有用武之地。它具有适应性强、应用广泛、计算技术比较简单的特点，

2、是现代管理科学的重要基础和手段之一。,3,第 一 节 线性规划问题及其数学模型 一、线性规划问题的数学模型 线性规划问题主要解决以下两类问题： 1、任务确定后，如何统筹安排，做到应用尽量少的人力和物力资源来完成任务； 2、在一定量的人力、物力资源的条件下，如何安排、使用他们，使完成的任务最多。 在生产管理和经济活动中，经常会遇到线性规划问题，如何利用线性规划的方法来进行分析，下面举例来加以说明。,4,例11：（计划安排问题）某工厂在计划期内安排生产、两种产品，已知生产单位产品所占用的设备A、B的台时、原材料的消耗及两种产品每件可获利润见表所示：,问如何安排计划使该工厂获利最多？,5,解: 假设

3、 x1、x2分别表示在计划期内生产 产品I、II的件数。该问题可用如下 数学模型表示为： 目标函数： Max Z = 2x1 +3x2 约束条件：,6,例12 (成本问题)某炼油厂根据每季度需供应给合同单位汽油15万吨、煤油12万吨、重油12万吨。该厂计划从A，B两处运回原油提炼，已知两处的原油成分含量见表12；又已知从A处采购的原油价格为每吨（包括运费）200元，B处采购的原油价格为每吨（包括运费）290元, 问：该炼油厂该如何从A，B两处采购原油，在满足供应合同的条件下，使购买成本最小。 表12,产品来源,成分,7,分析：很明显，该厂可以有多种不同的方案从A，B两处采购原油，但最优方案应是

4、使购买成本最小的一个，即在满足供应合同单位的前提下，使成本最小的一个采购方案。 解：设分别表示从A，B两处采购的原油量（单位：万吨），建立的数学模型为：,8,以上两个例子，从数学上来讲，我们会发现此数学模型具有如下特点： (1)有一组非负的决策变量(decision or control variable)； (2)有一组约束条件：含有决策变量的线性不等式(或等式)组(linear function constraints)； (3)有一个含有决策变量的线性目标函数(objective linear function)，按研究问题的不同，要求目标函数实现最大化或最小化。 我们把满足上述三个条件

5、的数学模型称为线性规划的数学模型。其一般形式如下：,9,在该数学模型中，方程(1.1)称为目标函数；(1.2)称为约束条件；(1.3)称为变量的非负约束条件。,10,二、线性规划问题的标准型 由前面所举的例子可知，线性规划问题可能有各种不同的形式。目标函数有实现最大化也有实现最小化的；约束条件可以是“”形式、“”形式的不等式，也可以是等式。决策变量有时有非负限制，有时没有。这种多样性给讨论问题带来了不便。为了便于今后讨论，我们规定线性规划问题的标准型为：,11,标准型具有如下特点： （1）目标函数求最大值； （2）所求的变量都要求是非负的； （3）所有的约束条件都是等式； （4）常数项非负。

6、综合以上的讨论可以说明任何形式的线性规划问题都可以通过上述手段把非标准型的线性规划问题化成标准型。现举例如下：,12,例14 试将如下线性规划问题化成标准型,解：令 x3 = x4 - x5 , x4 , x5 0 , (1)式左端加上非负松弛变量 x6 ；(2)式左端减去非负剩余变量 x7 , 则可将上述线性规划问题化成如下的标准型：,13,第二节 线性规划问题的图解法及几何意义,一、线性规划问题的解的概念 在讨论线性规划问题的求解之前，先要了解线性规划问题的解的概念。由前面讨论可知线性规划问题的标准型为 (1.6)、(1.7)、(1.8)式所示：,14,1. 可行解: 满足约束条件(1.7

7、)，(1.8)的解 X = ( x1, x2, , xn) 称为线性规划问题的可行解；所有可行解的集合称为可行解集或可行域。 2. 最优解: 满足约束条件及目标函数(1.6)的可行解称为线性规划问题的最优解。 3. 基: 假设 A 是约束方程组的系数矩阵，其秩数为 m ，B是矩阵 A 中由 m 列构成的非奇异子矩阵(B的行列式的值不为0)，则称 B 是线性规划问题的一个基。基B的第j列 Pj ( j = 1,2,m )称为基向量，与基向量 Pj 相对应的变量xj ( j = 1,2,m )称为基变量，否则称为非基变量。,T,15,为了进一步讨论线性规划问题的解，下面研究约束方程组(1.7)的求

8、解问题。假设该方程组系数矩阵 A 的秩为 m，因 m n，所以它有无穷多个解。假设前 m 个变量的系数列向量是线性无关的，这时(1.7)式可改写为： 现若令(1.9)式中的非基变量xm+1= =xn=0，并用高斯消去法求出一个解X =(x1,x2, ,xm,0, , 0 ) ，这个解的非0分量的数目不大于方程的个数m，这时称X为基本解。,T,16,4. 基本可行解 : 满足非负条件(1.8)的基本解称为基本可行解。由此可见，基本可行解的非0分量的数目不大于m，并且都是非负的。 5. 可行基: 对应于基本可行解的基称为可行基。由此可见，满足约束方程组(1.7)的基本解的数目至多是 Cnm 个。一

9、般地讲，基本可行解的数目要小于基本解的数目，至多相等。 以上提到的几种解的概念，可用图14来表示：,17,二、线性规划问题的图解法 对于简单的线性规划问题(只有两个决策变量的线性规划问题)，我们可以通过图解法对它进行求解。我们以例11具体给出求解的方法。 例15 用图解法求解线性规划问题 max Z = 2x1 +3x2,18,解：对于上述具有两个变量的线性规划问题，图1-2中的OABCD部分描述了满足约束条件的区域；虚线为目标函数Z=2x1+3x2的等值线。沿箭头方向移动目标函数的等值线，平移等值线直至与可行域OABCD相切或融合为一条直线，此时就得到最优解为B点，其坐标可通过解方程组得到：

10、 2x1+2x2=14 3x2=15 解得：x1=2 x2=5 这就是本线性规划问题的最优解。 此时相应的目标函数的最大值为： Z=22+35=19,19,例17 maxZ=2x1+ 4x2 s.t. 2x1+x2 8 -2 x1+ x2 2 x1，x2 0 解：由于可行域无界，作目标函数等值线，如图14中虚线所示，并用箭头标出其函数值增加的方向，由此可以看出，该问题无有限最优解。 若目标函数由 max Z = 2x1 + 4x2 改为 min Z =2 x1 +4 x2 , 则可行解所在的范围虽然无界，但有最优解 x1 = 4，x2 = 0 ，即 (4,0)点。,20,通过以上各题图解法所得

11、结论可以看出： （1）线性规划的所有可行解构成的可行域一般是凸多边形，有些可行域可能是无界的； （2）若存在最优解，则一定在可行域的某顶点得到； （3）若在两个顶点上同时得到最优解，则在这两点的连线上的任一点都是最优解。 （4）若可行域无界，则可能发生最优解无界的情况； （5）若可行域是空集，此时无最优解。 上述理论具有普遍意义，对于两个以上变量的线性规划问题都是成立。 图解法虽然具有直观、简便等优点，但在变量多的情况下，即在多维的情况下，它就无能为力了。因此，需要介绍一种代数方法单纯型法，为了以后介绍方便，需要研究一下线性规划问题解的概念。,21,三、基本定理 1. 凸集：假设K是n维欧氏空

12、间的一个点集，若对于K中的任意两点X1、X2，其连线上的所有点X1+(1-)X2，( 0 1)都在集合K中，即：X1+(1-)X2 K ( 0 1) 则称K为凸集。 从直观上讲，凸集无凹入部分，其内部没有洞。 2. 凸组合：设X1，X2，Xk是n维欧氏空间En中的k个点，若存在1，2，k，且0 i 1，i = 1,2, , k， i = 1，使X = 1X1 + 2X2 + + kXk，则称X为由X1，X2，Xk所构成的凸组合。 3. 顶点： 假设K是凸集，X K；X若不能用不同的两个点X1、X2 K的线性组合表示为： X = X1+(1-)X2 ， ( 0 1) 则称X为凸集K的一个顶点（或

13、称为极点）。 顶点不位于凸集K中的任意不同两点的连线内。,22,定理1.1 若线性规划问题存在可行域，则其可行域： D = X | AX = b , X 0 ，是凸集。 引理1.1 线性规划问题的可行解X为基本可行解的充要条件是X的正分量所对应的系数列向量是线性无关的。 定理1.2 线性规划问题的基本可行解对应于可行域的顶点。 定理1.3 若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优解。 定理1.4 若线性规划问题在k个顶点上达到最优解 （k2），则在这些顶点的凸组合上也达到最优解。,23,第 三 节 单纯形算法 单纯形算法的基本思路是：根据问题的标准型，从可行域中

14、某个基本可行解(顶点)开始，转换到另一个基本可行解(顶点)，并使得每次的转换，目标函数值均有所改善，最终达到最大值时就得到最优解。 现在需要解决的问题是： (1) 为了使目标函数逐步变优，应如何从可行域的一个顶点转移到可行域的另一个顶点？ （2）目标函数何时达到最优值？判断标准是什么？,24,1确定初始基可行解 从中一般可以直接观察到存在一个初始可行基 B = ( P1, P2, Pm ) （1.10） 当线性规划的约束条件均为“”形式的不等式时，可以利用标准型的方法，在每个约束条件的左端加上一个松弛变量，其松弛变量的系数矩阵即为单位矩阵；对于约束条件为“”形式的不等式或等式时，若不存在单位矩

15、阵，就采用构造人造基的办法，关于这个方法将在本章第四节讨论。,25,（1.10）式中的P1,P2, Pm称为基向量，在约束条件中把非基变量项移到等式的右边得：,（1.11）,令所有非基变量 ，得 X = ( b1,b2, , bm, 0, , 0 ) 又由于，故X满足约束条件，所以它是一个基可行解。,T,26,2最优性检验 假定已求得(LP)的一个基本可行解 X(0) ，假设： 目标函数用非基变量表示的形式。,（1.14）,其中,称为各非基变量 的检验数。,27,定理1.5 最优解判别定理: 若 为对应于基 B 的基本可行解，且对于一切 ，有 j 0，则 X 为线性规划问题的最优解。 定理1.6 无穷多最优解判别定理:若 为对应于基 B 的基本可行解，且对于一切 ，有 j 0，又存在某个非基变量的检验数 ，则线性规划问题有无穷多最优解。 定理1.7 无有限最优解判别定理： 若 为对应于基 B 的基本可行解，有一个 ，而对于 有 ，则线性规划问题无有限最优解(也称为无最优解)。,（0）,28,3. 基变换 若上面所求的基可行解还不是最优解，下面我们将介绍，如何通过基变换，求一个新的可行解？ （1）换入变量的确定 当某些非基变量的检验数j 0时，如果xj增加