第二讲线性规划基础课件.ppt
1,2023年4月3日,第二讲 线性规划基础,一.线性规划的提出与模型 二.线性规划的图解 三.线性规划标准型与解的概念四.线性规划的基本理论,2,2023年4月3日,一、线性规划的提出与模型,1、问题的提出,第二讲 线性规划基础,例1-1：某工厂在计划期内要安排生产甲、乙两种产品，按照工艺要求，产品甲、乙在设备A、B上所需的加工台时及原材料的消耗如表1-1所示。,表1-1 例1-1数据资料,3,2023年4月3日,第二讲 线性规划基础,一、线性规划的提出与模型,1、问题的提出,续例1-1：问：应如何安排生产计划才能到最大利润？,用数学关系式描述这个问题,假设，分别表示在计划期内产品甲、乙的产量；,生产，的数量多少，受到各种条件限制；,生产的产品数量不能为负值，即；,问：如何安排生产，使利润最大？,决策变量,约束条件,目标函数,4,2023年4月3日,第二讲 线性规划基础,一、线性规划的提出与模型,1、问题的提出,得到本问题的数学模型为:,这就是一个最简单的线性规划模型。,5,2023年4月3日,第二讲 线性规划基础,一、线性规划的提出与模型,练习题,练习题1 靠近某河流有两个化工厂(见图1-1)，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。,化工厂1每天排放含有某种有害物质的工业污水2万立方米，化工厂2每天排放的工业污水为1.4万立方米。从化工厂1排出的污水流到化工厂2前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。因此两个工厂都需处理一部分工业污水。化工厂1处理污水的成本是1000元/万立方米,化工厂2处理污水的成本是800元/万立方米。问:在满足环保要求的条件下，每厂各应处理多少工业污水，使两个工厂处理工业污水的总费用最小。,图1-1,6,2023年4月3日,第二讲 线性规划基础,一、线性规划的提出与模型,练习题1,建模型之前的分析和计算,设：化工厂1每天处理的污水量为x1万立方米；化工厂2每天处理的污水量为x2万立方米,7,2023年4月3日,第二讲 线性规划基础,一、线性规划的提出与模型,练习题1,得到本问题的数学模型为：,8,2023年4月3日,第二讲 线性规划基础,一、线性规划的提出与模型,练习题2,练习题2 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如表1-2所示。设司乘人员在各时间段一开始时上班，并连续工作8小时，问该公交线路怎样安排司乘人员，既能满足工作需要，又配备最少的司机和乘务人员？试列出该问题的线性规划模型。,表1-2 练习题2数据资料,9,2023年4月3日,第二讲 线性规划基础,一、线性规划的提出与模型,2、线性规划的一般数学模型,一般线性规划数学模型有三个要素：,（1）决策变量集合：，通常要求非负；,（2）约束条件集合，决策变量集的一组线性等式或不等式；,（3）目标函数：，通常求最大值或最小值。,10,2023年4月3日,第二讲 线性规划基础,一、线性规划的提出与模型,2、线性规划的一般数学模型,线性规划模型的一般形式为：,11,2023年4月3日,第二讲 线性规划基础,一、线性规划的提出与模型,2、线性规划的一般数学模型,决策变量及各类系数之间的对应关系：,12,2023年4月3日,第二讲 线性规划基础,一、线性规划的提出与模型,总结：,线性规划是求一个线性函数在满足一组线性等式或不等式方程条件下极值的数学问题的统称。,其组成部分：1、一个反映决策目标的目标函数；2、一组线性等式或不等式的约束方程；3、限制决策变量取值范围的非负约束。,13,2023年4月3日,第二讲 线性规划基础,二、线性规划的图解法,例1是一个二维线性规划问题，因而可用作图法直观地进行求解。,14,2023年4月3日,第二讲 线性规划基础,二、线性规划的图解法,目标值在（4，2）点，达到最大值14,15,2023年4月3日,第二讲 线性规划基础,二、线性规划的图解法,几种特殊情况：,（1）无穷多最优解：,将目标函数改为：max z=2x1+4x2,当目标方程直线与某一约束直线平行时，最优值不唯一！,16,2023年4月3日,第二讲 线性规划基础,二、线性规划的图解法,几种特殊情况：,（2）无界解：有可行域，但无最优解；,17,2023年4月3日,第二讲 线性规划基础,二、线性规划的图解法,几种特殊情况：,（3）无可行解：无可行域；,当存在相互矛盾的约束条件时，线性规划问题的可行域为空集。,例如，如果在例1的数学模型中增加一个约束条件:,思考：会出现什么结果？,18,2023年4月3日,第二讲 线性规划基础,二、线性规划的图解法,（3）无可行解：无可行域；,结论：该问题的可行域为空集，即无可行解，,19,2023年4月3日,第二讲 线性规划基础,二、线性规划的图解法,结论：,1、当线性规划问题的可行域非空时，它是有界或无界凸多边形；,2、若线性规划问题存在最优解，它一定在有界可行域的某个顶点得到。,推广：无穷多最优解的情况？,思考：图解法给人们的启示是什么？,20,2023年4月3日,第二讲 线性规划基础,三、线性规划标准型与解的概念,1、线性规划的标准型,21,2023年4月3日,第二讲 线性规划基础,三、线性规划标准型与解的概念,1、线性规划的标准型,用向量形式表示的标准形式线性规划：,22,2023年4月3日,第二讲 线性规划基础,三、线性规划标准型与解的概念,1、线性规划的标准型,用矩阵形式表示的标准形式线性规划：,23,2023年4月3日,第二讲 线性规划基础,三、线性规划标准型与解的概念,2、化一般模型为标准模型,(1)若要求目标函数实现最小化，即min z=CX，则只需将目标函数最小化变换求目标函数最大化，即令z=z，于是得到max z=CX。,(2)约束条件为不等式。分两种情况讨论：,若约束条件为“”型不等式，则可在不等式左端加入非负松弛变量，把原“”型不等式变为等式约束；,(3)若存在取值无约束的变量xk,可令:,若约束条件为“”型不等式，则可在不等式左端减去一个非负剩余变量(也称松弛变量)，把不等式约束条件变为等式约束。,24,2023年4月3日,第二讲 线性规划基础,三、线性规划标准型与解的概念,2、化一般模型为标准模型,练习题：,例3 将例1的数学模型化为标准形式的线性规划。,25,2023年4月3日,第二讲 线性规划基础,三、线性规划标准型与解的概念,2、化一般模型为标准模型,练习题：,(1)用x4x5替换x3，其中x4，x50；,(2)在第一个约束不等式左端加入松弛变量x6；,(3)在第二个约束不等式左端减去剩余变量x7；,(4)令z=z，将求min z 改为求max z,26,2023年4月3日,第二讲 线性规划基础,三、线性规划标准型与解的概念,2、化一般模型为标准模型,27,2023年4月3日,第二讲 线性规划基础,三、线性规划标准型与解的概念,3、线性规划问题解的概念,满足约束条件(1-5)、(1-6)式的解X=(x1,x2，xn)T，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。,28,2023年4月3日,第二讲 线性规划基础,三、线性规划标准型与解的概念,3、线性规划问题解的概念,29,2023年4月3日,第二讲 线性规划基础,三、线性规划标准型与解的概念,3、线性规划问题解的概念,30,2023年4月3日,满足非负条件的基解，称为基可行解.基可行解的非零分量的数目不大于m，并且都是非负的。,第二讲 线性规划基础,三、线性规划标准型与解的概念,3、线性规划问题解的概念,对应于基可行解的基，称为可行基。,约束方程组(1-5)具有的基解的数目最多是 个，一般基可行解的数目要小于基解的数目。,思考：例中基解可以有多少个？,31,2023年4月3日,第二讲 线性规划基础,线性规划问题各种解之间的关系,三、线性规划标准型与解的概念,32,2023年4月3日,第二讲 线性规划基础,四、线性规划的基本理论,1、凸集、凸组合与顶点,设S是n维欧氏空间的一点集，若任意两点X(1)S，X(2)S的连线上的所有点X(1)+(1)X(2)S，(01)，则称K为凸集。,33,2023年4月3日,第二讲 线性规划基础,四、线性规划的基本理论,1、凸集、凸组合与顶点,从直观上讲，凸集没有凹入部分，其内部没有空洞。任何两个凸集的交集是凸集。,34,2023年4月3日,第二讲 线性规划基础,四、线性规划的基本理论,1、凸集、凸组合与顶点,设X(1)，X(2)，X(k)是n维欧氏空间Rn中的k个点。若存在1，2，k，且0i1,（i=1,2,，k）且 使 X=1X(1)+2X(2)+kX(k)则称X为X(1)，X(2)，X(k)的一个凸组合（当0i1时，称为严格凸组合）。,35,2023年4月3日,设K是凸集，XK；若X不能用不同的两点X(1)K和X(2)K的线性组合表示为 X=X(1)+(1)X(2)，(01)则称X为K的一个顶点(或极点)。,第二讲 线性规划基础,四、线性规划的基本理论,1、凸集、凸组合与顶点,思考：圆有没有顶点，如果有，有多少个？,36,2023年4月3日,第二讲 线性规划基础,四、线性规划的基本理论,2、线性规划基本定理,定理1 若线性规划问题存在可行域，则其可行域 是凸集。,37,2023年4月3日,第二讲 线性规划基础,四、线性规划的基本理论,2、线性规划基本定理,引理 1 线性规划问题的可行解X=(x1,x2,，xn)T为基可行解的充要条件是：X的正分量所对应的系数列向量是线性独立的。,38,2023年4月3日,定理2 线性规划问题的基可行解X对应于可行域D的顶点。证：不失一般性，假设基可行解X的前m个分量为正。故 现分两步来讨论，分别用反证法。,第二讲 线性规划基础,四、线性规划的基本理论,2、线性规划基本定理,39,2023年4月3日,(1)若X不是基可行解，则它一定不是可行域D的顶点。根据引理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+(x2+2)P2+(xm+m)Pm=b,第二讲 线性规划基础,四、线性规划的基本理论,定理2 线性规划问题的基可行解X对应于可行域D的顶点。,40,2023年4月3日,第二讲 线性规划基础,四、线性规划的基本理论,定理2 线性规划问题的基可行解X对应于可行域D的顶点。,(1)若X不是基可行解，则它一定不是可行域D的顶点。,41,2023年4月3日,第二讲 线性规划基础,四、线性规划的基本理论,定理2 线性规划问题的基可行解X对应于可行域D的顶点。,（2）若X不是可行域D的顶点，则它一定不是基可行解。,因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。,42,2023年4月3日,由于X(1)，X(2)是可行域的两点，因而满足：,第二讲 线性规划基础,四、线性规划的基本理论,定理2 线性规划问题的基可行解X对应于可行域D的顶点。,（2）若X不是可行域D的顶点，则它一定不是基可行解。,将两式相减，得：,因X(1)X(2)，所以上式中的系数不全为零，故向量组P1,P2,，Pm线性相关，与假设矛盾，即X不是基可行解。,43,2023年4月3日,第二讲 线性规划基础,四、线性规划的基本理论,定理 3 若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。,证：设X(1),X(2)，X(k)是可行域的顶点，若X(0)不是顶点，且目标函数在X(0)处达到最优z*=CX(0)(标准型是z=max z)。因X(0)不是顶点，所以它可以用D的顶点线性表示为,2、线性规划基本定理,44,2023年4月3日,第二讲 线性规划基础,四、线性规划的基本理论,2、线性规划基本定理,定理 3 若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。,代入目标函数得：,在所有的顶点中必然能找到某一个顶点X(m)，使CX(m)是所有CX(i)中最大者。并且将X(m)代替(1-10)式中的所有X(i)，得到：,45,2023年4月3日,第二讲 线性规划基础,四、线性规划的基本理论,2、线性规划基本定理,定理 3 若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。,由此得到 CX(0)CX(m)根据假设CX(0)是最大值，所以只能有 CX(0)=CX(m)即目标函数在顶点X(m)处也达到最大值。,结论：有时，目标函数可能在多个顶点处达到最大，这时在这些顶点的凸组合上也达到最大值，这时线性规划问题有无限多个最优解。并且，线性规划不排斥在非顶点处取得最优解。,46,2023年4月3日,精品课件！,47,2023年4月3日,精品课件！,48,2023年4月3日,第二讲 线性规划基础,四、线性规划的基本理论,结论,1、线性规划问题的可行域是凸集（定理1）；2、凸集的每个顶点对应一个基可行解（定理2）；3、若线性规划问题有最优解，必在某顶点上得到。,
