《运筹学线性规划与目标函数》由会员分享，可在线阅读，更多相关《运筹学线性规划与目标函数（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 图解法,目标函数
6、 max z=2x1+4x2,图1-4 无穷多最优解（多重最优解）,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
7、线性规划问题的标准型式,(1) 若要求目标函数实现最小化，即min z =CX，则只需将目标函数最小化变换求目标函数最大化，即令z= z，于是得到max z= CX。 (2) 约束条件为不等式。分两种情况讨论： 若约束条件为“”型不等式，则可在不等式左端加入非负松弛变量，把原“”型不等式变为等式约束； 若约束条件为“”型不等式，则可在不等式左端减去一个非负剩余变量(也称松弛变量)，把不等式约束条件变为等式约束。 (3) 若存在取值无约束的变量xk,可令,如何将一般线性规划转化为标准形式的线性规划,25,1.3 线性规划问题的标准型式,例3 将例1的数学模型化为标准形式的线性规划。 例1的数学模
8、型在加入了松驰变量后变为,26,1.3 线性规划问题的标准型式,例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
9、)式的解X=(x1,x2，xn)T，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。,1. 可行解,30,1.4 线性规划问题的解的概念,2. 基，基向量，基变量,31,1.4 线性规划问题的解的概念,满足非负条件（1-6）的基解，称为基可行解. 基可行解的非零分量的数目不大于m，并且都是非负的。,3 基可行解,32,1.4 线性规划问题的解的概念,对应于基可行解的基，称为可行基。 约束方程组(1-5)具有的基解的数目最多是 个，一般基可行解的数目要小于基解的数目。 以上提到了几种解的概念，它们之间的关系可用图1-6表明。 说明：当基解中的非零分量的个数小于m时，该基解是
10、退化解。在以下讨论时，假设不出现退化的情况。,4 可行基,33,1.4 线性规划问题的解的概念,不同解之间的关系,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中的阴
11、影部分是凸集。 任何两个凸集的交集是凸集，见图1-7(d),38,2.1 基本概念,设X(1)，X(2)，X(k)是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 若线性规划问题存在
12、可行域，则其可行域是凸集。,41,2.2 几个定理,定理1的证明：只需证明D中任意两点连线上的点必然在D内即可。设是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不是基可行解，则
13、其正分量所对应的系数列向量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+(x2+2)P2+(xm+m)Pm=b,46,2.2 几个定理,因X 不是可行域D的顶点，故在可行域D中可找到不同的两点 X(1)=(x1(1),x2(1),xn(1)TX(2)=(x1(2),x2(2),xn(2)T使得 X=X(1)+(1) X(2) ， 01设X是基可行解，对应的向量组P1Pm线性独立，故当jm时，有xj=
14、xj(1)=xj(2)=0。由于X(1)，X(2)是可行域的两点，因而满足,（2）若X不是可行域D的顶点，则它一定不是基可行解。,将两式相减，得,因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)，并延
15、长交于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的表达式代入上式得到 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的顶点线性表示为代入目标函数得,
