第一章线性规划与单纯形法ppt课件.ppt
《第一章线性规划与单纯形法ppt课件.ppt》由会员分享,可在线阅读,更多相关《第一章线性规划与单纯形法ppt课件.ppt(253页珍藏版)》请在三一办公上搜索。
1、1,第一章 线性规划与单纯形法,第一节 线性规划问题及其数学模型第二节 线性规划问题的几何意义第三节 单纯形法第四节 单纯形法的计算步骤第五节 单纯形法的进一步讨论第六节 应用举例,2,第一节 线性规划问题及其数学模型,一、 问题的提出二、 图解法三、 线性规划问题的标准形式四、 线性规划问题的解的概念,3,线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟,在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后,线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作
2、用。它已是现代科学管理的重要手段之一。解线性规划问题的方法有多种,以下仅介绍单纯形法 。,4,一、问题的提出,例 1 某工厂在计划期内要安排生产、两种产品,已知生产单位产品所需的设备台时及A、B两种原材料的消耗,如下表所示。,每生产一件产品可获利2元,每生产一件产品可获利3元,问应如何安排计划使该工厂获利最多?,5,利润 z=2x1+3x2,6,本问题的数学模型为:,这就是一个最简单的线性规划模型。,7,例2 建立LP数学模型,某家电厂家利用现有资源生产两种 产品,有关数据如下表:,如何安排生产,使获利最多?,8,如何安排生产,使获利最多?,厂家,设 产量 产量,9,每一个线性规划问题都用一组
3、决策变量 表示某一方案,这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的;都有关于各种资源和资源使用情况的技术数据,创造新价值的数据;存在可以量化的约束条件,这些约束条件可以用一组线性等式或线性不等式来表示;都有一个达到某一目标的要求,可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同,要求目标函数实现最大化或最小化。,上述两个问题具有的共同特征:,10,线性规划模型的一般形式,目标函数,满足约束条件,价值系数,技术(工艺)系数,限额系数(资源),非负约束条件,11,二、图解法,例1是一个二维线性规划问题,因而可用作图法直观地进行求解。,12,4x1=16,4x2
4、=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)点,达到最大值14,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,4,3,0,Q2(4,2),Q1,可行域,x1+2x2=84x1=16,15,图解法求解步骤,由全部约束条件作图求出可行域;作目标函数等值线,确定使目标函数最优的移动方向;平移目标函数的等值线,找出最优点,算出最优值。,16,练习:用图解法求解,目标函数 Max Z = 2x1 + x2 约束条件 5x2 15 6x1 +2x2 2
5、4 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 + x2 约束条件 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
6、 ,可行域,19,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 ,x2 = -2x1,6x1+ 2x2=24 x1+ x2=5,最优解 (3.5,1.5),目标值在(3.5,1.5)点,达到最大值8.5,20,(1)无穷多最优解(多重最优解)(2)无界解(3)无可行解,上例中求解得到问题的最优解是惟一的,通过图解法,可观察到一般线性规划的解还可能出现一下几种情况:,21,无穷多
7、最优解(多重最优解),4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,4,3,0,可行域,Q2,Q3,Max Z = 2x1 + 4x2,22,4x1=16,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)可行域无界 有无
8、穷多最优解,(e)可行域无界 无最优解 (无界解),27,(f)可行域为空集 无可行解,28,LP问题,有可行解,有最优解,唯一解无穷多解,无最优解(可行域为无界,无界解),无可行解(无解,可行域为空集),若LP问题有最优解,则要么最优解唯一,要么有无穷多最优解,29,图解法的几点结论:(由图解法得到的启示),可行域是有界或无界的凸多边形,凸多边形的顶点个数是有限的。若线性规划问题存在最优解,它一定可以在可行域的顶点得到。若两个顶点同时得到最优解,则其连线上的所有点都是最优解。解题思路:找出凸集的顶点,计算其目标函数值,比较即得。,30,三、线性规划问题的标准形式,在标准形式中规定约束条件的右
9、端项bi0,31,32,用向量形式表示的标准形式线性规划,线性规划问题的几种表示形式,33,用矩阵形式表示的标准形式线性规划,34,(1) 若要求目标函数实现最小化,即min z =CX,则只需将目标函数最小化变换求目标函数最大化,即令z= z,于是得到max z= CX。(2) 约束条件为不等式。分两种情况讨论:若约束条件为“”型不等式,则可在不等式左端加入非负松弛变量,把原“”型不等式变为等式约束;若约束条件为“”型不等式,则可在不等式左端减去一个非负剩余变量(也称松弛变量),把不等式约束条件变为等式约束。(3) 若存在取值无约束的变量xk,可令,如何将一般线性规划转化为标准形式的线性规划
10、,35,例3 将例1的数学模型化为标准形式的线性规划。例1的数学模型在加入了松驰变量后变为,36,例4 将下述线性规划问题化为标准形式线性规划,(1) 用x4x5替换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.
11、可行基,40,(1-4),(1-5),(1-6),一般线性规划问题的标准型:,41,定义满足约束条件(1-5)、(1-6)式的解X=(x1,x2,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,其余的变量称为非基变量,记为 X
12、N = ( xm+1 , xm+2 , , xn ) T 。,44,令非基变量xm+1 = xm+2 = =xn =0 线性规划问题变量的个数等于线性方程的个数(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,
13、4,3,0,Q1,Q2,Q3,Q4,Q6,Q7,Q8,基可行解为可行域的顶点,47,对应于基可行解的基,称为可行基。约束方程组(1-5)具有的基解的数目最多是 个。一般基可行解的数目要小于基解的数目。以上提到了几种解的概念,它们之间的关系可用图1-6表明。说明:当基解中的非零分量的个数小于m时,该基解是退化解。在以下讨论时,假设不出现退化的情况。,4、可行基,48,非可行解,可行解,基可行解,基解,图1-6 线性规划标准型问题不同解之间的关系,49,例:求基解、基可行解、最优解。,50,系数矩阵,列向量,51,1,基:,52,令非基变量,得基解,X1 不是基可行解,53,2,基:,54,令非基
14、变量,得基解,X2 是基可行解,55,3,基:,56,令非基变量,得基解,X3 是基可行解,57,4,基:,58,令非基变量,得基解,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 Q72 2 3 0 8 0 Y Q3 3 4 2 0 0 4 Y Q2 4 4 0 4 0 12 Y Q15 8 0 0 -16 12 N Q66 0 3 2 16 0 Y Q47 0 4 0 16 -4 N
16、Q88 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,实心圆,实心球体,实心立方体等都是凸集,圆环不是凸集。从直观上讲,凸集没有凹入部分,其内部没有空洞。任何两个凸集的交集是凸集,见下图所示:,76,设X(1),X(2),X(k)是n维欧氏空间En中的k个点。若存在1,2,k,且0i1
17、, i=1,2,,k 使 X=1X(1)+2X(2)+kX(k),成立 则称X为X(1),X(2),X(k)的一个凸组合(当0i1时,称为严格凸组合)。,2. 凸组合,77,设K是凸集,XK;若X不能用不同的两点X(1)K和X(2)K的线性组合表示为: X=X(1)+(1)X(2),(01) 则称X为K的一个顶点(或极点)。,3. 顶点,凸集,凸集,78,二、几个定理,定理1 若线性规划问题存在可行域,则其可行域 是凸集。,79,定理1的证明:只需证明D中任意两点连线上的点必然在D内即可。 设X(1)、X(2) 是D内的任意两点;且X(1)X(2)。 AX(1)=A X(2)=b,AX=AX(
18、1)+(1- )X(2),AX= AX(1)+A X(2) - AX(2),AX= b+b - b=b,XD,令X为X(1),X(2)连线上的任意一点,即 X=X(1)+(1-)X(2) (01)将它代入约束条件,得到,D是凸集,80,引理 1 线性规划问题的可行解X=(x1,x2,,xn)T为基可行解的充要条件是:X的正分量所对应的系数列向量是线性独立的。,证: (1) 必要性 由基可行解的定义可知。 (2) 充分性 若向量P1,P2,Pk线性独立, 则必有km; 当k=m时,它们恰构成一个基,从而 X=(x1,x2,xk,00)为相应的基可行解。 当km时,则一定可以从其余的列向量中取出m
19、-k个与P1,P2,Pk构成最大的线性独立向量组,其对应的解恰为X,所以根据定义它是基可行解。,81,定理2 线性规划的可行解X是基可行解的充分必要条件是X是可行域D的顶点。,(1)充分性 : X是可行域D的顶点 X是基可行解。 逆否命题 若X不是基可行解,则它一定不是可行域D的顶点。,82,根据引理1,若X不是基可行解,则其正分量所对应的系数列向量P1,P2,Pm线性相关,即存在一组不全为零的数i,i=1,2,m,使得 1P1+2P2+mPm=0 (1-9) 用一个数0乘(1-9)式再分别与(1-8)式相减和相加,得: (x11)P1+(x22)P2+(xm m)Pm=b (x1+1)P1+
20、(x2+2)P2+(xm+m)Pm=b,不妨设X的前m个分量为正,则有,P1 x1 + Pm x m = b (1-8),83,现构造两个点X(1) ,X(2) 如下:,另一方面,当充分小时,可保证,则X(1) ,X(2) D, 且X1/2 X(1) + 1/2 X(2),所以 X 不是D的顶点.,X是 X(1) , X(2)的中点,若X不是基可行解,则它一定不是可行域D的顶点。,84,因X不是可行域D的顶点,故在可行域D中可找到不同的两点 X(1)=(x1(1),x2(1),xn(1)T X(2)=(x1(2),x2(2),xn(2)T 使得 X=X(1)+(1) X(2) , 01,(2)
21、必要性 : X是基可行解 X是可行域D的顶点。逆否命题 若X不是可行域D的顶点,则它一定不是基可行解。,85,假设X是基可行解, X的前m个分量为正,对应的向量组P1Pm线性独立,故当jm时,有xj=xj(1)=xj(2)=0。 由于X(1),X(2)是可行域的两点,因而满足,将两式相减,得,因X(1)X(2),所以上式中的系数不全为零,故向量组P1,P2,,Pm线性相关,与假设矛盾,即X不是基可行解。,若X不是可行域D的顶点,则它一定不是基可行解。,86,引理2 若K是有界凸集,则任何一点XK可表示为K的顶点的凸组合。 本引理的证明从略,用以下例子说明本引理的结论。例5 设X是三角形中任意一
22、点,X(1),X(2)和X(3)是三角形的三个顶点,试用三个顶点的坐标表示X(见图1-8),87,解:任选一顶点X(2),做一条连线XX(2),并延长交于X(1)、X(3)连接线上一点X。 因为X是X(1)、X(3)连线上一点,故可用X(1)、X(3)线性组合表示为:X=X(1)+(1)X(3) 01 又因X是X与X(2)连线上的一个点,故X=X+(1 )X(2) 01,X,88,将X的表达式X=X(1)+(1)X(3)代入式X=X+(1 )X(2) 得到X=X(1)+(1)X(3)+(1)X(2)=X(1)+(1 )X(3)+(1)X(2) 令 1=,2=(1 ),3=(1 ),得到X=1X
23、(1)+2X(2)+3X(3)ii=1, 0i1,89,定理 3 若可行域有界,则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。 证: 设X(1),X(2),X(k)是可行域的顶点,若X(0)不是顶点,且目标函数在X(0)处达到最优 z*=CX(0)(标准型是z*=max z)。 因X(0)不是顶点,所以它可以用D的顶点的凸组合表示。 代入目标函数得:,90,在所有的顶点中必然能找到某一个顶点X(m),使CX(m)是所有CX(i)中最大者。并且将X(m)代替 中的所有X(i),得到,由此得到 CX(0)CX(m)根据假设CX(0)是最大值,所以只能有 CX(0)=CX(m)即目标函
24、数在顶点X(m)处也达到最大值。,91,定理4 :目标函数可能在多个顶点处达到最大,这时在这些顶点的凸组合上也达到最大值,这时线性规划问题有无限多个最优解。证明:假设 是目标函数达到最大值的顶点,则对这些顶点的凸组合,有,92,设:于是:另外,若可行域为无界,则可能无最优解,也可能有最优解,若有最优解,也必定在某顶点上得到。,93,练习,证明:若X(1)、X(2)是线性规划的最优解,则X(1)、X(2)连接线段上的点也都是最优解。,则XX(1)+(1)X(2),(01),CXCX(1)+(1)CX(2),,CX(1)+ CX(2) CX(2),设 CX(1) CX(2)m,m为最优值,m+ m
25、 mm,X(1)、X(2)是线性规划的最优解,设X为X(1)、X(2)连接线段上的点,X是线性规划的最优解,证:,94,基本结论,线性规划问题的可行域是凸集(定理1)。可行域的每个顶点对应着一个基可行解,基可行解的个数是有限的,因此可行域的顶点个数也是有限的(定理2) 。若线性规划问题有最优解,必在某顶点上得到(定理3) 。顶点数目是有限的,若采用“枚举法”找所有基可行解,然后一一比较,最终必然能找到最优解。但当n,m较大时,这种办法是行不通的,所以要继续讨论如何有效寻找最优解的方法。,95,第三节 单纯形法,一、 初始基可行解的确定二、最优性检验与解的判断三、基变换四、迭代(旋转运算),96
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第一章 线性规划 单纯 ppt 课件

链接地址:https://www.31ppt.com/p-1354748.html