运筹学线性规划与目标函数.ppt
《运筹学线性规划与目标函数.ppt》由会员分享,可在线阅读,更多相关《运筹学线性规划与目标函数.ppt(168页珍藏版)》请在三一办公上搜索。
1、1,线性规划与目标规划,第1章 线性规划与单纯形法第2章 对偶理论与灵敏度分析第3章 运输问题第4章 目标规划,2,第1章 线性规划与单纯形法,第1节 线性规划问题及其数学模型第2节 线性规划问题的几何意义第3节 单纯形法第4节 单纯形法的计算步骤第5节 单纯形法的进一步讨论第6节 应用举例,3,第1节 线性规划问题及其数学模型,1.1 问题的提出1.2 图解法1.3 线性规划问题的标准形式1.4 线性规划问题的解的概念,4,第1节 线性规划问题及其数学模型,线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟,在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策
2、变量的线性规划问题之后,线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。解线性规划问题的方法有多种,以下仅介绍单纯形法。,5,1.1 问题的提出,1.1 问题的提出 例 1 某工厂在计划期内要安排生产、两种产品,已知生产单位产品所需的设备台时及A、B两种原材料的消耗,如表1-1所示。,每生产一件产品可获利2元,每生产一件产品可获利3元,问应如何安排计划使该工厂获利最多?,6,1.1 问题的提出,用数学关系式描述这个问题,7,1.1 问题的提出,得到本问题的数学模型为:,这就是
3、一个最简单的线性规划模型。,8,1.1 问题的提出,例 2 靠近某河流有两个化工厂(见图1-1),流经第一化工厂的河流流量为每天500万立方米,在两个工厂之间有一条流量为每天200万立方米的支流。,图1-1,化工厂1每天排放含有某种有害物质的工业污水2万立方米,化工厂2每天排放的工业污水为1.4万立方米。从化工厂1排出的污水流到化工厂2前,有20%可自然净化。根据环保要求,河流中工业污水的含量应不大于0.2%。因此两个工厂都需处理一部分工业污水。化工厂1处理污水的成本是1000元/万立方米,化工厂2处理污水的成本是800元/万立方米。问:在满足环保要求的条件下,每厂各应处理多少工业污水,使两个
4、工厂处理工业污水的总费用最小。,9,1.1 问题的提出,设:化工厂1每天处理的污水量为x1万立方米;化工厂2每天处理的污水量为x2万立方米,建模型之前的分析和计算,x11,0.8x1+x21.6,10,1.1 问题的提出,得到本问题的数学模型为:,11,1.1 问题的提出,每一个线性规划问题都用一组决策变量 表示某一方案,这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的;都有关于各种资源和资源使用情况的技术数据,创造新价值的数据;存在可以量化的约束条件,这些约束条件可以用一组线性等式或线性不等式来表示;都有一个达到某一目标的要求,可用决策变量的线性函数(称为目标函数)来表示。
5、按问题的要求不同,要求目标函数实现最大化或最小化。,上述两个问题具有的共同特征:,12,1.1 问题的提出,决策变量及各类系数之间的对应关系,13,1.1 问题的提出,线性规划模型的一般形式,14,1.2 图解法,1.2 图解法例1是一个二维线性规划问题,可用作图法直观地进行求解。,15,1.2 图解法,目标值在(4,2)点,达到最大值14,16,1.2 图解法,(1)无穷多最优解(多重最优解),见图1-4。(2)无界解,见图1-5-1。(3)无可行解,见图1-5-2。,通过图解法,可观察到线性规划的解可能出现的几种情况:,17,1.2 图解法,目标函数 max z=2x1+4x2,图1-4
6、无穷多最优解(多重最优解),18,1.2 图解法,图1-5-1 无界解,19,当存在相互矛盾的约束条件时,线性规划问题的可行域为空集。例如,如果在例1的数学模型中增加一个约束条件:则该问题的可行域即为空集,即无可行解,,无可行解的情形,1.2 图解法,20,图1-5-2 不存在可行域,1.2 图解法,21,1.3 线性规划问题的标准型式,1.3 线性规划问题的标准型式,22,1.3 线性规划问题的标准型式,用向量形式表示的标准形式线性规划,线性规划问题的几种表示形式,23,1.3 线性规划问题的标准型式,用矩阵形式表示的标准形式线性规划,24,1.3 线性规划问题的标准型式,(1)若要求目标函
7、数实现最小化,即min z=CX,则只需将目标函数最小化变换求目标函数最大化,即令z=z,于是得到max z=CX。(2)约束条件为不等式。分两种情况讨论:若约束条件为“”型不等式,则可在不等式左端加入非负松弛变量,把原“”型不等式变为等式约束;若约束条件为“”型不等式,则可在不等式左端减去一个非负剩余变量(也称松弛变量),把不等式约束条件变为等式约束。(3)若存在取值无约束的变量xk,可令,如何将一般线性规划转化为标准形式的线性规划,25,1.3 线性规划问题的标准型式,例3 将例1的数学模型化为标准形式的线性规划。例1的数学模型在加入了松驰变量后变为,26,1.3 线性规划问题的标准型式,
8、例4 将下述线性规划问题化为标准形式线性规划,(1)用x4x5替换x3,其中x4,x50;(2)在第一个约束不等式左端加入松弛变量x6;(3)在第二个约束不等式左端减去剩余变量x7;(4)令z=z,将求min z 改为求max z=max(-z)=-(-x1+2x2-3x3)即可得到该问题的标准型。,27,1.3 线性规划问题的标准型式,例4 例4的标准型,28,1.4 线性规划问题的解概念,1.可行解2.基3.基可行解4.可行基,29,1.4 线性规划问题的解的概念,定义满足约束条件(1-5)、(1-6)式的解X=(x1,x2,xn)T,称为线性规划问题的可行解,其中使目标函数达到最大值的可
9、行解称为最优解。,1.可行解,30,1.4 线性规划问题的解的概念,2.基,基向量,基变量,31,1.4 线性规划问题的解的概念,满足非负条件(1-6)的基解,称为基可行解.基可行解的非零分量的数目不大于m,并且都是非负的。,3 基可行解,32,1.4 线性规划问题的解的概念,对应于基可行解的基,称为可行基。约束方程组(1-5)具有的基解的数目最多是 个,一般基可行解的数目要小于基解的数目。以上提到了几种解的概念,它们之间的关系可用图1-6表明。说明:当基解中的非零分量的个数小于m时,该基解是退化解。在以下讨论时,假设不出现退化的情况。,4 可行基,33,1.4 线性规划问题的解的概念,不同解
10、之间的关系,34,第2节 线性规划问题的几何意义,2.1 基本概念2.2 几个定理,35,2.1 基本概念,凸集凸组合顶点,36,2.1 基本概念,定义设K是n维欧氏空间的一点集,若任意两点X(1)K,X(2)K的连线上的所有点X(1)+(1)X(2)K,(01),则称K为凸集。,图1-7,1.凸集,37,2.1 基本概念,实心圆,实心球体,实心立方体等都是凸集,圆环不是凸集。从直观上讲,凸集没有凹入部分,其内部没有空洞。图1-7中的(a)(b)是凸集,(c)不是凸集。图1-2中的阴影部分是凸集。任何两个凸集的交集是凸集,见图1-7(d),38,2.1 基本概念,设X(1),X(2),X(k)
11、是n维欧氏空间En中的k个点。若存在1,2,k,且0i1,i=1,2,,k 使 X=1X(1)+2X(2)+kX(k)则称X为X(1),X(2),X(k)的一个凸组合(当0i1时,称为严格凸组合)。,2.凸组合,39,2.1 基本概念,设K是凸集,XK;若X不能用不同的两点X(1)K和X(2)K的线性组合表示为 X=X(1)+(1)X(2),(01)则称X为K的一个顶点(或极点)。图中的0,Q1,2,3,4都是顶点。,3.顶点,40,2.2 几个定理,定理1 若线性规划问题存在可行域,则其可行域 是凸集。,41,2.2 几个定理,定理1的证明:只需证明D中任意两点连线上的点必然在D内即可。设
12、是D内的任意两点;且X(1)X(2)。,42,2.2 几个定理,43,2.2 几个定理,引理 1 线性规划问题的可行解X=(x1,x2,,xn)T为基可行解的充要条件是:X的正分量所对应的系数列向量是线性独立的。,44,2.2 几个定理,定理2 线性规划问题的基可行解X对应于可行域D的顶点。证:不失一般性,假设基可行解X的前m个分量为正。故 现分两步来讨论,分别用反证法。,45,2.2 几个定理,(1)若X不是基可行解,则它一定不是可行域D的顶点。根据引理1,若X不是基可行解,则其正分量所对应的系数列向量P1,P2,Pm线性相关,即存在一组不全为零的数i,i=1,2,m,使得 1P1+2P2+
13、mPm=0(1-9)用一个数0乘(1-9)式再分别与(1-8)式相加和相减,得(x11)P1+(x22)P2+(xm m)Pm=b(x1+1)P1+(x2+2)P2+(xm+m)Pm=b,46,2.2 几个定理,因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 设X是基可行解,对应的向量组P1Pm线性独立,故当jm时,有xj=xj(1)=xj(2)=0。由于X(1),X(2)是可行域的两点,因而满足,(2)若X不是可行域D的顶点,则它一定不是基可
14、行解。,将两式相减,得,因X(1)X(2),所以上式中的系数不全为零,故向量组P1,P2,,Pm线性相关,与假设矛盾,即X不是基可行解。,47,2.2 几个定理,引理2 若K是有界凸集,则任何一点XK可表示为K的顶点的凸组合。本引理的证明从略,用以下例子说明本引理的结论。例5 设X是三角形中任意一点,X(1),X(2)和X(3)是三角形的三个顶点,试用三个顶点的坐标表示X(见图1-8),图1-8,48,2.2 几个定理,解:任选一顶点X(2),做一条连线XX(2),并延长交于X(1)、X(3)连接线上一点X。因为X是X(1)、X(3)连线上一点,故可用X(1)、X(3)线性组合表示为X=X(1
15、)+(1)X(3)01 又因X是X与X(2)连线上的一个点,故X=X+(1)X(2)01 将X的表达式代入上式得到X=X(1)+(1)X(3)+(1)X(2)=X(1)+(1)X(3)+(1)X(2)令 1=,2=(1),3=(1),得到X=1X(1)+2X(2)+3X(3)ii=1,0i1,49,2.2 几个定理,定理 3 若可行域有界,则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。证:设X(1),X(2),X(k)是可行域的顶点,若X(0)不是顶点,且目标函数在X(0)处达到最优z*=CX(0)(标准型是z=max z)。因X(0)不是顶点,所以它可以用D的顶点线性表示为 代
16、入目标函数得,50,2.2 几个定理,在所有的顶点中必然能找到某一个顶点X(m),使CX(m)是所有CX(i)中最大者。并且将X(m)代替(1-10)式中的所有X(i),得到,由此得到 X(0)CX(m)根据假设CX(0)是最大值,所以只能有 CX(0)=CX(m)即目标函数在顶点X(m)处也达到最大值。,51,2.2 几个定理,有时,目标函数可能在多个顶点处达到最大,这时在这些顶点的凸组合上也达到最大值,这时线性规划问题有无限多个最优解。假设是目标函数达到最大值的顶点,则对这些顶点的凸组合,有,52,2.2 几个定理,设:于是:另外,若可行域为无界,则可能无最优解,也可能有最优解,若有最优解
17、,也必定在某顶点上得到。,53,基本结论,线性规划问题的所有可行解构成的集合是凸集,也可能为无界域,它们有有限个顶点,线性规划问题的每个基可行解对应可行域的一个顶点。若线性规划问题有最优解,必在某顶点上得到。虽然顶点数目是有限的,若采用“枚举法”找所有基可行解,然后一一比较,最终必然能找到最优解。但当n,m较大时,这种办法是行不通的,所以要继续讨论如何有效寻找最优解的方法。本课程将主要介绍单纯形法。,54,第3节 单纯形法,3.1 举例3.2 初始基可行解的确定3.3 最优性检验与解的判断3.4 基变换3.5 迭代(旋转运算),55,单纯形法求解线性规划的思路:,一般线性规划问题具有线性方程组
18、的变量数大于方程个数,这时有不定的解。但可以从线性方程组中找出一个个的单纯形,每一个单纯形可以求得一组解,然后再判断该解使目标函数值是增大还是变小,决定下一步选择的单纯形。这就是迭代,直到目标函数实现最大值或最小值为止。这样,问题就得到了最优解,先举一例来说明。,56,3.1 举例,例6 试以例1来讨论如何用单纯形法求解。解:已知本例的标准型为:,57,3.1 举例,约束条件(1-12)式的系数矩阵为从(1-12)式可看到x3,x4,x5的系数构成的列向量,58,3.1 举例,P3,P4,P5是线性独立的,这些向量构成一个基B。对应于B的变量x3,x4,x5为基变量.,从(1-12)式中可以得
19、到(1-13),59,3.1 举例,将(1-13)式代入目标函数(1-11):得到当令非基变量x1=x2=0,便得到z=0。这时得到一个基可行解X(0)X(0)=(0,0,8,16,12)T 本基可行解的经济含义是:工厂没有安排生产产品、,资源都没有被利用,所以工厂的利润为z=0。,60,3.1 举例,从分析目标函数的表达式(1-14)可以看到:非基变量x1,x2(即没有安排生产产品,)的系数都是正数,因此将非基变量变换为基变量,目标函数的值就可能增大。从经济意义上讲,安排生产产品或,就可以使工厂的利润指标增加。所以只要在目标函数(1-14)的表达式中还存在有正系数的非基变量,这表示目标函数值
20、还有增加的可能,就需要将非基变量与基变量进行对换。,61,3.1 举例,如何确定换入、换出变量?一般选择正系数最大的那个非基变量x2为换入变量,将它换到基变量中,同时还要确定基变量中哪一个换出来成为非基变量。可按以下方法来确定换出变量:分析(1-13)式,当将x2定为换入变量后,必须从x3,x4,x5中确定一个换出变量,并保证其余的变量仍然非负,即x3,x4,x50。,62,3.1 举例,如何确定换入、换出变量当x1=0时,由(1-13)式得到,63,3.1 举例,如何确定换入、换出变量当x2取何值时,才能满足非负要求呢?从(1-15)式可看出,只有选择 x2=min(8/2,-,12/4)=
21、3时,才能使(1-15)式成立。因当x2=3时,基变量x5=0,这就决定用x2去替换x5。以上数学描述说明,每生产一件产品,需要用掉的各种资源数为(2,0,4)。由这些资源中的薄弱环节,就确定了产品的产量。这里就是由原材料B的数量确定了产品的产量x2=12/4=3件。,64,3.1 举例,如何确定换入、换出变量为了求得以x3,x4,x2为基变量的一个基可行解和进一步分析问题,需将(1-13)中x2的位置与x5的位置对换,得到,65,3.1 举例,将(1-16)式中x2的系数列向量变换为单位列向量。其运算步骤是:=/4;=-2;=,并将结果仍按原顺序排列有:,高斯消去法,66,3.1 举例,再将
22、(1-17)式代入目标函数(1-11)式得到,67,3.1 举例,从目标函数的表达式(1-18)可看到,非基变量x1的系数是正的,说明目标函数值还可以增大,即X(1)还不是最优解。于是,再用上述方法确定换入、换出变量,继续迭代,得到另一个基可行解X(2)X(2)=(2,3,0,8,0)T 再经过一次迭代,又得到一个基可行解X(3)X(3)=(4,2,0,0,4)T 而这时得到目标函数的表达式是:z=141.5x3 0.125x4(1-19)再检查(1-19)式,可见所有非基变量x3,x4的系数都是负数,这说明若要用剩余资源x3,x4,就必须支付附加费用。所以当x3=x4=0时,即不再利用这些资
23、源时,目标函数达到最大值。所以X(3)是最优解。即当产品生产4件,产品生产2件时,工厂可以得到最大利润。,68,小结,通过上例,可将每步迭代得到的结果与图解法做一对比。例1的线性规划问题是二维的,即有两个变量x1,x2。当加入松弛变量x3,x4,x5后,变换为高维的。这时可以想象,满足所有约束条件的可行域是高维空间中的凸多面体(凸集)。该凸多面体上的顶点,就是基可行解。初始基可行解为 X(0)=(0,0,8,16,12)T,对应于图1-2中的原点(0,0);X(1)=(0,3,2,16,0)T对应于图中的Q4点(0,3);X(2)=(2,3,0,8,0)T对应于Q3点(2,3);最优解X(3)
24、=(4,2,0,0,4)T相当于图中的 Q2点(4,2)。,从初始基可行解X(0)开始迭代,依次得到X(1),X(2),X(3),相当于图中的目标函数平移时,从0点开始,首先碰到Q4,然后碰到Q3,最后达到Q2。,69,3.2 初始基可行解的确定,为了确定初始基可行解,要首先找出初始可行基,其方法如下。(1)直接观察(2)加松弛变量(3)加非负的人工变量,70,3.2 初始基可行解的确定,从线性规划问题的系数构成的列向量Pj(j=1,2,n)中,通过直接观察,找出一个初始可行基,(1)直接观察,71,3.2 初始基可行解的确定,对所有约束条件为“”形式的不等式,利用化标准型的方法,在每个约束条
25、件的左端加上一个松弛变量。经过整理,重新对xj及aij(i=1,2,m;j=1,2,n)进行编号,则可得下列方程组(x1,x2,xm 为松弛变量):,(2)加松弛变量,72,3.2 初始基可行解的确定,于是,(1-22)中含有一个mm阶单位矩阵,初始可行基B即可取该单位矩阵。将(1-22)式每个等式移项得,73,3.2 初始基可行解的确定,令xm+1=xm+2=xn=0,由(1-23)式可得xi=bi(i=1,2,m)得到一个初始基可行解。又因bi0(在1-3节中已做过规定),所以得到一个初始基可行解 X=(x1,x2,xm,0,0)T nm个=(b1,b2,bm,0,0)T nm个,74,3
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 线性规划 目标 函数
链接地址:https://www.31ppt.com/p-6028286.html