《第一章线性规划与单纯形法教学教案》由会员分享，可在线阅读，更多相关《第一章线性规划与单纯形法教学教案（253页珍藏版）》请在金锄头文库上搜索。
1、1,第一章 线性规划与单纯形法,第一节 线性规划问题及其数学模型 第二节 线性规划问题的几何意义 第三节 单纯形法 第四节 单纯形法的计算步骤 第五节 单纯形法的进一步讨论 第六节 应用举例,2,第一节 线性规划问题及其数学模型,一、 问题的提出 二、 图解法 三、 线性规划问题的标准形式 四、 线性规划问题的解的概念,3,线性规划是运筹学的一个重要分支。 线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。 从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决
2、策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。 解线性规划问题的方法有多种，以下仅介绍单纯形法 。,5,利润 z=2x1+3x2,6,本问题的数学模型为:,这就是一个最简单的线性规划模型。,7,例2 建立LP数学模型,某家电厂家利用现有资源生产两种 产品，有关数据如下表：,如何安排生产，使获利最多？,8,如何安排生产， 使获利最多？,厂 家,设 产量 产量,9,每一个线性规划问题都用一组决策变量 表示某一方案，这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的； 都有关于各种资源和资源使用情况的技术数据，创造新价值的数据； 存在可以量化的约束条件，这些约束条件可以用
3、一组线性等式或线性不等式来表示; 都有一个达到某一目标的要求，可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同，要求目标函数实现最大化或最小化。,上述两个问题具有的共同特征：,10,线性规划模型的一般形式,目标函数,满足约束条件,价值系数,技术（工艺）系数,限额系数（资源）,非负约束条件,11,二、图解法,例1是一个二维线性规划问题，因而可用作图法直观地进行求解。,12,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,4,3,0,13,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,4,3,0,Q1,可行域,14,目标值在（4，2）点，达到最大
4、值14,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,4,3,0,Q2(4,2),Q1,可行域,x1+2x2=8 4x1=16,15,图解法求解步骤,由全部约束条件作图求出可行域； 作目标函数等值线，确定使目标函数最优的移动方向； 平移目标函数的等值线，找出最优点，算出最优值。,16,练习：用图解法求解,目标函数 Max Z = 2x1 + x2 约束条件 5x2 15 6x1 +2x2 24 x1 + x2 5 x1、 x2 0,17,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,x2,x1 + x2 =5,目标函数 Max Z = 2x1 + x
5、2 约束条件 5x2 15 6x1 +2x2 24 x1 + x2 5 x1、 x2 0,5 x2 = 15,图解法,12 11 10 ,18,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,x2,x1 + x2 = 5,目标函数 Max Z = 2x1 + x2 约束条件 5x2 15 6x1 +2x2 24 x1 + x2 5 x1、 x2 0,5 x2 = 15,图解法,12 11 10 ,可行域,19,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,x2,x1 + x2 = 5,目标函数 Max Z = 2x1 + x2 约束条件 5x2 1
6、5 6x1 +2x2 24 x1 + x2 5 x1、 x2 0,5 x2 = 15,12 11 10 ,x2 = -2x1,6x1+ 2x2=24 x1+ x2=5,最优解 (3.5,1.5),目标值在（3.5，1.5）点，达到最大值8.5,20,（1）无穷多最优解(多重最优解) （2）无界解 （3）无可行解,上例中求解得到问题的最优解是惟一的,通过图解法，可观察到一般线性规划的解还可能出现一下几种情况：,21,无穷多最优解（多重最优解）,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,4,3,0,可行域,Q2,Q3,Max Z = 2x1 + 4x2,22,4x1=16,
7、x1,x2,4,0,无界解（a）,可行域,23,无界解（b）,24,当存在相互矛盾的约束条件时，线性规划问题的可行域为空集，即无可行解，也不存在最优解。,无可行解,4x1=16,4x2=12,x1+2x2=8,x1,x2,3,0,原可行域,8,增加一个新的约束条件,25,可行域和解有以下几种情况,(a)可行域有界 有唯一最优解,(b)可行域有界 有无穷多最优解,26,(c)可行域无界 有唯一最优解,(d)可行域无界 有无穷多最优解,(e)可行域无界 无最优解 (无界解),27,(f)可行域为空集 无可行解,28,LP问题,有可行解,有最优解,唯一解 无穷多解,无最优解（可行域为无界,无界解）,
8、无可行解（无解，可行域为空集）,若LP问题有最优解，则要么最优解唯一，要么有无穷多最优解,29,图解法的几点结论:（由图解法得到的启示）,可行域是有界或无界的凸多边形，凸多边形的顶点个数是有限的。 若线性规划问题存在最优解，它一定可以在可行域的顶点得到。 若两个顶点同时得到最优解，则其连线上的所有点都是最优解。 解题思路：找出凸集的顶点，计算其目标函数值，比较即得。,30,三、线性规划问题的标准形式,在标准形式中规定约束条件的右端项bi0,31,32,用向量形式表示的标准形式线性规划,线性规划问题的几种表示形式,33,用矩阵形式表示的标准形式线性规划,34,(1) 若要求目标函数实现最小化，即
9、min z =CX，则只需将目标函数最小化变换求目标函数最大化，即令z= z，于是得到max z= CX。 (2) 约束条件为不等式。分两种情况讨论： 若约束条件为“”型不等式，则可在不等式左端加入非负松弛变量，把原“”型不等式变为等式约束； 若约束条件为“”型不等式，则可在不等式左端减去一个非负剩余变量(也称松弛变量)，把不等式约束条件变为等式约束。 (3) 若存在取值无约束的变量xk,可令,如何将一般线性规划转化为标准形式的线性规划,35,例3 将例1的数学模型化为标准形式的线性规划。 例1的数学模型在加入了松驰变量后变为,36,例4 将下述线性规划问题化为标准形式线性规划,(1) 用x4
10、x5替换x3，其中x4，x50； (2) 在第一个约束不等式左端加入松弛变量x6； (3) 在第二个约束不等式左端减去剩余变量x7； (4) 令z= z，将求min z 改为求max z,37,例4的标准型,38,补充： 当某个变量xj0时,令xj=xj. 当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束,将其化为两个不等式,再加入松驰变量化为等式。,39,四、线性规划问题解的概念,1.可行解 2.基 3.基可行解 4.可行基,40,（1-4）,（1-5）,（1-6）,一般线性规划问题的标准型：,41,定义 满足约束条件(1-5)、(1-6)式的解X=(x1,x2
11、，xn)T，称为线性规划问题的可行解； 其中使目标函数（1-4）达到最大值的可行解称为最优解。,1、可行解,42,2、基,A是约束方程组的mn维 系数矩阵，其秩为m,43,B是矩阵A中mm阶非奇异子矩阵（| B | 0） ，则称B是线性规划问题的一个基。 令B = =( P1 , P2 , , Pm ) Pj (j=1,2,m) 为基向量。 与基向量Pj对应的变量xj称为基变量 记为XB = ( x1 , x2 , , xm )T，其余的变量称为非基变量，记为 XN = ( xm+1 , xm+2 , , xn ) T 。,44,令非基变量xm+1 = xm+2 = =xn =0 线性规划问题
12、变量的个数等于线性方程的个数（m个） 利用高斯消去法，求出一个解 X = ( x1 , x2 , , xm,0,0 )T 称X为基解（或称为基本解）,45,4x1=16,4x2=12,x1+ 2x2=8,x1,x2,4,3,0,Q1,Q2,Q3,Q4,Q6,Q7,Q8,46,满足非负条件（1-6）的基解，称为基可行解(或称为基本可行解)。 基可行解的非零分量的数目不大于m，并且都是非负的。,3、基可行解,4x1=16,4x2=12,x1+ 2x2=8,x1,x2,4,3,0,Q1,Q2,Q3,Q4,Q6,Q7,Q8,基可行解为可行域的顶点,47,对应于基可行解的基，称为可行基。 约束方程组(1
13、-5)具有的基解的数目最多是 个。 一般基可行解的数目要小于基解的数目。 以上提到了几种解的概念，它们之间的关系可用图1-6表明。 说明：当基解中的非零分量的个数小于m时，该基解是退化解。在以下讨论时，假设不出现退化的情况。,4、可行基,48,非可行解,可行解,基可行解,基解,图1-6 线性规划标准型问题不同解之间的关系,49,例：求基解、基可行解、最优解。,50,系数矩阵,列向量,51,1,基：,52,令非基变量,得基解,X1 不是基可行解,53,2,基：,54,令非基变量,得基解,X2 是基可行解,55,3,基：,56,令非基变量,得基解,X3 是基可行解,57,4,基：,58,令非基变量
14、,得基解,X4 是基可行解,59,5,基：,60,令非基变量,得基解,X5 不是基可行解,61,6,基：,62,令非基变量,得基解,X6 是基可行解,63,7,基：,64,令非基变量,得基解,X7 不是基可行解,65,8,基：,66,令非基变量,得基解,X8 是基可行解,67,问1：,是否是一个基?,否,因为此矩阵不可逆,或者说列向量组线性相关,68,问2：,是否是一个基?,否,因为此矩阵不可逆,或者说列向量组线性相关,69,最优解,全部基解：,70,上例中指出了一种求解线性规划问题的可能途径，就是先确定线性规划问题的基以及基解，如果是基可行解，则计算相应的解的目标函数值。由于基的个数是有限的
15、（最多 个），因此必定可以从有限个基本可行解中找到最优解。,71,4x1=16,4x2=12,x1+ 2x2=8,x1,x2,4,8,4,3,0,Q1,约束直线的交点基解 可行域的顶点基可行解,Q2,Q3,Q4,Q5,Q6,Q7,Q8,1 4 3 -2 0 0 N Q7 2 2 3 0 8 0 Y Q3 3 4 2 0 0 4 Y Q2 4 4 0 4 0 12 Y Q1 5 8 0 0 -16 12 N Q6 6 0 3 2 16 0 Y Q4 7 0 4 0 16 -4 N Q8 8 0 0 8 16 12 Y Q5,是否基 可行解,对应的点解,72,第二节 线性规划问题的几何意义,一、基本概念 二、几个定理,73,一、 基本概念,凸集 凸组合 顶点,74,定义 设K是n维欧氏空间的一点集，若任意两点X(1)K，X(2)K的连线上的所有点X(1)+(1)X(2)K，(01)，则称K为凸集。,1.凸集,凸,非凸,(a),(b),(d),(c),75,实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。 从直观上讲，凸集没有凹入部分，其内部没有空洞。 任何两个凸集的交集是凸集，见下图所示：,
