1、第 一 章 线性规划,Linear Programming,2019年7月17日,-第 1 章 线性规划-,-1-,1.1 线性规划概述（1）,线性规划的广泛应用是计算机时代的产物。1902年，Julius Farkas 发表论文，阐述有关线性规划问题。1938年，英国人康德进行较详细研究。1947年，美国学者George Dantzig（丹茨格）发明了求解线性规划的单纯形法（1951年发表），从而为线性规划的推广奠定了基础。有人认为，求解线性规划的单纯形算法可与求解线性方程组的高斯消元法相媲美。,2019年7月17日,-第 1 章 线性规划-,-2-,1.1 线性规划概述（2）,线性规划的数
2、学模型有三要素，从实际问题提炼成数学模型时，首先寻找需求解的未知量xj (j=1,n)，然后列举三要素： 列写与自变量（未知量）有关的若干个线性约束条件（等式或不等式）。列写自变量xj取值限制（xj0，xj0或不限）。列写关于自变量的线性目标函数值（极大值或极小值）。其中，前两条称为可行条件，最后一条称为优化条件。符合这三个条件的数学模型通常称为线性规划的一般型（general）。,2019年7月17日,-第 1 章 线性规划-,-3-,1.1.1问题的提出 例1：某企业计划生产甲、乙两种产品，该两种产品均需经A、B、C、D四种不同设备上加工，按工艺资料规定，在各种不同设备上的加工时间及设备加
3、工能力、单位产品利润如表中所示。问:如何安排产品的生产计划,才能使企业获利最大?,1.1 一般线性规划问题及数学模型（3）,2019年7月17日,-第 1 章 线性规划-,-4-,建立模型：,设 产品的产量 甲x1件 ，乙 x2件，则,Maxz=2 x1+3 x2,2 x1+2 x2 12,x1+2 x2 8,4 x1 16 4 x2 12,x10， x2 0,目标(object) ：,限制条件(subject to )：,2019年7月17日,-第 1 章 线性规划-,-5-,例2、多产品生产问题（Max, ）,生产甲乙电缆，1方案需铜每米2个单位铅每米1个单位，售价6元每米，2方案需铜每米
4、1个单位铅每米1个单位，售价6元每米，现有铜10个单位，铅8个单位，且第二种最多生产7米，问如何生产获利最大设x1, x2 分别代表甲、乙两种电缆的生产量，,2019年7月17日,-第 1 章 线性规划-,-6-,1.1.2线性规划问题的一般数学模型,1.相关概念 （1）决策变量：指模型中要求解的未知量，简称变量。,（2）目标函数：指模型中要达到的目标的数学表达式。,（3）约束条件：指模型中的变量取值所需要满足的一切限制条件。,此三项内容称为模型结构的三要素。,2019年7月17日,-第 1 章 线性规划-,-7-,2.线性规划模型的一般要求,（1）变量：取值为连续的、可控的量； （2）目标函
5、数：线性表达式； （3）约束条件：线性的等式或者不等式。,2019年7月17日,-第 1 章 线性规划-,-8-,3 . 线性规划问题的一般表示方法,（1）一般式： max z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 am1x1+am2x2+amnxnbm x1 ,x2, ,xn0 s.t.-subject to,2019年7月17日,-第 1 章 线性规划-,-9-,n (2) 和式： max z= cjxj j=1 n s.t. aijxjbi （i=1,2,m) j=1 xj 0 （j=1,2,n) 其中：c
6、j-表示目标函数系数 aij-表示约束条件系数 bi -表示约束右端项,2019年7月17日,-第 1 章 线性规划-,-10-,n （4） 向量: max z=cjxj n j=1 s.t pjxjb （i=1,2,m） j=1 xj0 （j=1,2,n),（3） 矩阵: max z=CX s.t. AXb X0,2019年7月17日,-第 1 章 线性规划-,-11-,4. 线性规划模型的标准形式,（1）变量：所有变量均xj0 （2）目标函数：为取“max”形式（3）约束条件：全部约束方程均为“=”连接（4）约束右端项：bi 0 非标准形式情况有变量： xj0 ,或xj无约束目标函数：mi
7、n 约束条件：“”或“”约束右端项： bi0,2019年7月17日,-第 1 章 线性规划-,-12-,LP的标准化：,（1）变量：若 xj0，令 xj=-xj，xj0 若 xj无约束，则令 xj= xjxj，xj0，xj0,x,z,z,zmin,z = - z,z max,（3）约束方程：当 “”时，引进松弛（slack）变量+xs；如 x1+x23 x1+x2+ x3=3 当 “”时，引进剩余（surplus）变量 - xs；如 x1+2x2 4 x1+2x2x4=4,（2）目标函数：若求 min z，则 令 z = -z，等价于求 max （z ）即有 min z= - max （- z
8、）,（4）约束右端项：当 bi 0，则不等式两端同乘（- 1）,2019年7月17日,-第 1 章 线性规划-,-13-,例：将下述LP模型标准化：,obj. Min z=2x1- x2+3x3st. x1+2 x2+4x3 6 3x1- 2x2+ x3 = 4 2x1- x2 - 3x3 5 x1 0, x2无符号限制, x3 0,解：设 z= - z, x2= x2 - x2 , x2 0 , x2 0, x3= - x3 , x3 0 ，x40, x50, 则有obj. Max z= -2x1 + (x2 - x2 ) + 3x3 st. x1+2(x2 - x2 ) - 4x3 +x4
9、=6 3x1 - 2(x2 - x2 ) - x3 =42x1 - (x2 - x2 ) + 3x3 -x5=5 x1 0, x2 0, x2 0, x3 0, x4 0, x5 0,2019年7月17日,-第 1 章 线性规划-,-14-,复习思考题：,1. 什么是模型结构的三要素？2. 什么是线性规划模型？能举出线性规划模型的例子吗？3. LP模型中目标函数系数、约束条件系数、约束右端项的含义指的是什么？通常以什么符号表示？4. LP模型的一般表示方法有几种形式？能否写出这些形式？5. 什么是线性规划模型的标准形式？为何提出标准形式？你能否把一个线性规划模型的非标准形式转化为标准形式？,2
10、019年7月17日,-第 1 章 线性规划-,-15-,1.1.3 简单线性规划模型的建立,步骤：,（2）具体构造模型：选择合适的决策变量、确定目标函数的表达式、约束条件的表达式，分析各变量取值的符号限制。,（1）分析问题：确定决策内容、要实现的目标以及所受到的限制条件。,2019年7月17日,-第 1 章 线性规划-,-16-,例1：某工厂在生产过程中需要使用浓度为80%的硫酸100 吨，而市面上只有浓度为30%，45%，73%，85%，92%的硫酸出售， 每吨的价格分别为400、700、1400、1900和2500元。 问：采用怎样的购买方案，才能使所需总费用最小？,2019年7月17日,
11、-第 1 章 线性规划-,-17-,模型：,设 第j 种硫酸需购买 xj 吨，则,Minz=400x1+700x2+1400x3+1900x4+2500x5st. x1+x2+x3+x4+x5=100 30x1+45x2+73x3+85 x4+92x5=10080 x10, x20, x30, x40, x50,2019年7月17日,-第 1 章 线性规划-,-18-,例2：设有下面四个投资机会： 甲：在三年内，投资人应在每年年初投资，每年每元投资可获利0.2元，每年取息后可重新将本息用于投资。 乙：在三年内，投资人应在第一年年初投资，每两年每元投资可获利0.5元，两年后取息，取息后可重新将本
12、息用于投资。这种投资最多不得超过20,000元。 丙：在三年内，投资人应在第二年年初投资，两年后每元投资可获利0.6元。这种投资最多不得超过15,000元。 丁：在三年内，投资人应在第三年年初投资，一年后每元投资可获利0.4元。这种投资最多不得超过10,000元。 假定在这三年为一期的投资中，每期的开始有30,000元资金可供使用，问：采取怎样的投资计划，才能在第三年年底获得最大收益？,2019年7月17日,-第 1 章 线性规划-,-19-,模型：,设 xij第 i 年投资于第 j 项目上的资金量，则,Maxz=0.2 (x11+x21+ x31) + 0.5 x12 + 0.6 x2 3+
13、 0.4 x34st. x11+ x1230,000 x21+ x2330,000 x12+ 0.2 x11 x31+ x3430,000 x23 +0.2(x11+ x21)+0.5x12 x12 20,000 x23 15,000 x3410,000 xij0, (i=1,2,3; j=1,2,3,4),x11,x12,x21,x23,x31,x34,1,2,3,4,30,000,2019年7月17日,-第 1 章 线性规划-,-20-,例3：合理下料问题： 要制作100套钢筋架子，每套含2.9米、2.1米、1.5米的钢筋各一根。已知原料长7.4米，问：如何下料，使用料最省？,方案,下料数
14、,长度,2.9米2.1米1.5米,121221 3123,合计(米),7.47.37.27.16.6,料头(米),00.10.20.30.8,2019年7月17日,-第 1 章 线性规划-,-21-,模型:,设 xj 为第j种方案用料的数量,则,Min z=0x1+0.1x2+0.2x3+0.3x4+0.8x5st. x1+2x2 + x4 =100 2x3+2x4+ x5=100 3x1+ x2+2x3 +3x5=100 xj0, (j=1,2,-,5),思考题：目标函数是否可以选取为 min z=x1+x2+x3+x4+x5 ，为什 么？,2019年7月17日,-第 1 章 线性规划-,-
15、22-,例4：有A、B两种产品，都需要经过前、后两到化学反应过程。每种产品需要的反应时间及其可供使用的总时间如表示。 每生产一个单位产品B的同时，会产生2个单位的副产品C，且不需外加任何费用。副产品C的一部分可以出售盈利，其余的只能加以销毁。 副产品C每卖出一个单位可获利3元，但是如果卖不出去，则每单位需销毁费用2元。预测表明，最多可售出5个单位的副产品C。 要求确定使利润最大的生产计划。,2019年7月17日,-第 1 章 线性规划-,-23-,模型：,设 产品的产量为 Ax1单位，B x2单位，已售出的产品C x3 单 位，销毁的产品C x4单位，则,Max z=4x1+10x2+3x32
16、x4st. 2x1+3x216 3x1+4x224 2x2=x3+x4 x3 5 xj0, (j=1,2,3,4),2019年7月17日,-第 1 章 线性规划-,-24-,例5：一家昼夜服务的饭店，24小时中需要的服务员数如下表所示。每个服务员每天连续工作8小时，且在时段开始时上班。问：最少需要多少名服务员？试建立该问题的线性规划模型。,2019年7月17日,-第 1 章 线性规划-,-25-,模型：,设 xj第j时段开始上班工作的服务员数，则,Min z=x1+x2+x3+x4+x5+x6st. x6+x14 x1+x28 x2+x310 x3+x47 x4+x512 x5+x64 xj0
17、, (j=1,2,-,6),2019年7月17日,-第 1 章 线性规划-,-26-,建立线性规划模型要求：（1）要求决策的量是连续的、可控的量，或者是可以简化为连续取值的变量；（2）要求所解决的问题的目标可用数值指标描述，并且能表示成线性函数；（3）存在着多种决策方案可供选择；（4）决策所受到的限制条件可用线性的等式或者不等式表示。,2019年7月17日,-第 1 章 线性规划-,-27-,1.1.4线性规划问题解的有关概念,设模型 n max z=cjxj j=1 n s.t. aijxj=bi （i=1,2,m) j=1 xj0 （j=1,2,n),（1）可行解：满足所有约束方程和变量符
18、号限制条件的一组变量的取值。,（2）可行域：全部可行解的集合称为可行域。,（3）最优解：使目标函数达到最优值的可行解。,2019年7月17日,-第 1 章 线性规划-,-28-,（4）基：设A为线性规划模型约束条件系数矩阵（m n，mn），而B为其mm子矩阵，若|B|0，则称B为该线性规划模型的一个基。,（5）基变量：基中每个向量所对应的变量称为基变量。,（6）非基变量：模型中基变量之外的变量称为非基变量。,（7）基本解（基解）：令模型中所有非基变量X非基=0后，由模型约束方程组 n aijxj =bi (i=1,2,m)得到的一组解。 j=1,（8）基本可行解（基可行解）：在基本解中，同时又
19、是可行解的解称为基本可行解。,（9）可行基：对应于基本可行解的基称为可行基。,2019年7月17日,-第 1 章 线性规划-,-29-,Max z=2x1+3x2 st. x1+x23 x1+2x24 x1,x20,Max z=2x1+3x2 +0x3 +0x4 st. x1+x2+x3=3 x1+2x2+x4=4 x1, x2, x3 , x40,A=,x1 x2 x3 x4,1 1 1 01 2 0 1,可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T 等。,设,B=,1 0 0 1,，令,，则,| B |=10,令 x1=x2 =0，则 x3 =3, x4=4，X=(
20、0,0,3,4)T,例：,x3 x4,基变量,令,B=,1 1 1 0,x1 x3,，则,令 x2=x4 =0，则 x3 =-1, x1=4，X=(4,0,-1,0)T,| B |=-10,非基本可行解,基本可行解,标准化,2019年7月17日,-第 1 章 线性规划-,-30-,复习思考题： 1. 可行解和可行域有怎样的关系？ 2. 一个标准化LP模型，最多可有多少个基？ 3. 基本解是如何定义的？怎样才能得到基本解？ 4. 可行解、基本解、基本可行解三者之间有什么关系？在LP模型中是否一定存在？ 5. 什么是可行基？,2019年7月17日,-第 1 章 线性规划-,-31-,1.2线性规划
21、问题的图解方法,* 利用作图方法求解。 例：max z=2x1+3x2 s.t 2x1+2x212 - x1+2x2 8 - 4x116 - 4x2 12 - x10, x20,2019年7月17日,-第 1 章 线性规划-,-32-,x1,x2,2,2,4,6,8,4,6,0,Z=6,Z=0,(4,2),Zmax,2019年7月17日,-第 1 章 线性规划-,-33-,A,A,B,唯一解,无穷多解,无界解,无可行解,2019年7月17日,-第 1 章 线性规划-,-34-,步骤：（1）作平面直角坐标系，标上刻度；（2）做出约束方程所在直线，确定可行域；（3）做出一条目标函数等值线，判定优化
22、方向；（4）沿优化方向移动，确定与可行域相切的点，确定最优解，并计算最优值。,讨论一：模型求解时，可得到如下几种解的状况：（1）唯一最优解：只有一点为最优解点，简称唯一解；（2）无穷多最优解：有许多点为最优解点，简称无穷多解；（3）无界最优解：最优解取值无界，简称无界解；（4）无可行解：无可行域，模型约束条件矛盾。,讨论二：LP模型求解思路：（1）若LP模型可行域存在，则为一凸形集合；（2）若LP模型最优解存在，则其应在其可行域顶点上找到；（3）顶点与基本解、基本可行解的关系：,2019年7月17日,-第 1 章 线性规划-,-35-,复习思考题：1. LP模型的可行域是否一定存在?2. 图解
23、中如何去判断模型有唯一解、无穷多解、无界解和无可行解？3. LP模型的可行域的顶点与什么解具有对应关系？4.你认为把所有的顶点都找出来，再通过比较目标函数值大小的方式找出最优解，是否是最好的算法？为什么？,2019年7月17日,-第 1 章 线性规划-,-36-,1.3单纯形法的基本原理（Simplex Method）,1.3.1 两个概念：（1）凸集：对于集合C中任意两点连线上的点，若也在C内，则称 C为凸集。,或者，任给X1C，X2 C，X=X1+ (1-)X2 C (01)，则C为凸集。,凸集,非凸集,2019年7月17日,-第 1 章 线性规划-,-37-,（2）顶点：凸集中不成为任意
24、两点连线上的点，称为凸集顶点。,或者， 设C为凸集，对于XC，不存在任何X1C，X2 C， 且X1X2，使得X=X1+(1-)X2C， (01)，则X为凸集顶点。,X,X,X,X,X,2019年7月17日,-第 1 章 线性规划-,-38-,定理1：若线性LP模型存在可行解，则可行域为凸集。,证明：设 max z=CX st.AX=b X0,并设其可行域为C，若X1、X2为其可行解，且X1X2 ，则 X1C，X2 C， 即AX1=b，AX2=b，X10，X20，,又 X为X1、X2连线上一点，即 X=X1+(1-)X2C， (01)， AX=AX1+ (1-)AX2 = b+ (1-)b =b
25、 , (01)，且 X 0， X C， C为凸集。,1.3.2 三个基本定理：,2019年7月17日,-第 1 章 线性规划-,-39-,引理：线性规划问题的可行解X=(x1, x2,xn)T 为基本可行解的充要条件是X的正分量所对应的系数列向量线性独立。,证：（1）必要性：X基本可行解X的正分量所对应的系数列向量线性独立 可设X=(x1,x2,xk,0,0,0)T，若X为基本可行解，显然，由基本可行解定义可知x1, x2,xk所对应的系数列向量P1,P2,Pk应该线性独立。,（2）充分性： X的正分量所对应的系数列向量线性独立 X为基本可行解若A的秩为m，则X的正分量的个数km； 当k=m时
26、，则x1,x2,xk的系数列向量P1,P2,Pk恰好构成基， X为基本可行解。 当km时，则必定可再找出m-k个列向量与P1,P2,Pk一起构成基， X为基本可行解。,2019年7月17日,-第 1 章 线性规划-,-40-,证：用反证法 X非基本可行解X非凸集顶点（1）必要性：X非基本可行解 X非凸集顶点 不失一般性，设X=(x1,x2,xm,0,0,0)T，为非基本可行解， X为可行解，, pjxj=b，,j=1,n,即 pjxj=b (1),j=1,m,又 X是非基本可行解， P1,P2,Pm线性相关，即有1P1+2P2+mPm=0， 其中1，2，m不全为0，两端同乘0，得1P1+2P2
27、+mPm=0，（2）,定理2：线性规划模型的基本可行解对应其可行域的顶点。,2019年7月17日,-第 1 章 线性规划-,-41-,由 (1)+(2)得 (x1+ 1)P1+ (x2+ 2)P2+ (xm+ m)Pm=b由 (1)-(2)得 (x1 -1)P1+ (x2 - 2)P2+ (xm -m)Pm=b,令X1=(x1+ 1，x2+ 2，xm+ m，0， ，0)T X2=(x1- 1，x2- 2，xm- m ，0，0)T取充分小,使得 xj j0， 则 X1、X2均为可行解，但 X=0.5X1+(1-0.5)X2， X是X1、X2连线上的点， X非凸集顶点。,2019年7月17日,-第
28、 1 章 线性规划-,-42-,（2）充分性： X非凸集顶点 X非基本可行解,设X=(x1,x2,xr,0,0,0)T为非凸集顶点，则必存在Y、Z两点，使得,X=Y+(1-)Z，(01)，且Y、Z为可行解或者 xj=yj+(1-)zj (00, 1-0 ，当xj=0， 必有yj=zj=0, pjyj =,j=1,n, pjyj=b (1),j=1,r, pjzj =,j=1,n, pjzj=b (2),j=1,r, (yj-zj)pj=0,j=1,r,(1)-(2),得,即,(y1 - z1)P1+ (y2 - z2)P2+ (yr -zr)Pr=0,2019年7月17日,-第 1 章 线性规
29、划-,-43-, Y、Z为不同两点， yj-zj不全为0， P1,P2,Pr线性相关， X非基本可行解。,2019年7月17日,-第 1 章 线性规划-,-44-,3,4,O,(3,3),C (4,2),6,6,2X1+2X2+X3=12,4X2+X5=12,4X1+X4=16,XA=(0,3,6,16,0)T,XO=(0,0,12,16,12)T,XB=(3,3,0,4,0)T,XC=(4,2,0,0,4)T,XD=(4,0,4,0,12)T,A,D,B,X1,X2,2019年7月17日,-第 1 章 线性规划-,-45-,z1=CX1=CX0-C=zmax-C ，z2=CX2=CX0+C
30、=zmax+C z0 = zmax z1 ， z0 = zmax z2 ， z1 = z2 = z0 ，即 X1 、 X2也为最优解，若X1、X2仍不是顶点，可如此递推，直至找出一个顶点为最优解。 从而，必然会找到一个基本可行解为最优解。,定理3：若线性规划模型有最优解，则一定存在一个基本可行解为最优解。,证：设 X0=(x10, x20,xn0)T 是线性规划模型的一个最优解，z0=zmax=CX0若X0非基本可行解，即非顶点，只要取充分小，则必能找出X1= X0-0 ，X2 = X0 +0 ，即X1 、 X2为可行解，,2019年7月17日,-第 1 章 线性规划-,-46-,单纯形法的计
31、算步骤：,初始基本可行解,新的基本可行解,最优否？,STOP,Y,N,2019年7月17日,-第 1 章 线性规划-,-47-,1初始基本可行解的确定：,设模型 n max z=cjxj j=1 n s.t. aijxjbi （i=1,2,m) j=1 xj0 （j=1,2,n),n m max z=cjxj + 0xsi j=1 I=1 n s.t. aijxj+xsi=bi （i=1,2,m) j=1 xj0， xsi0 （j=1,2,n; i=1,2, ,m),化标准形,初始基本可行解 X=(0,0,0, b1,b2,bm)T，,n-m个0,2019年7月17日,-第 1 章 线性规划-
32、,-48-,2从一个基本可行解向另一个基本可行解转换,不失一般性，设基本可行解X0=(x10, x20,xm0,0,0)T ，前m个分量为正值，秩为m，其系数矩阵为,P1 P2 Pm Pm+1 Pj Pn b 1 0 0a 1,m+1 a1j a 1n b1 0 1 0 a 2,m+1 a2j a 2nb2 0 0 1a m,m+1 amj a mn bm, pjxj0 =,j=1,n, pixi0=b (1),i=1,m,2019年7月17日,-第 1 章 线性规划-,-49-,又P1 P2 Pm为一个基，任意一个非基向量Pj可以以该组向量线性组合表示，即Pj = a1j P1 + a2j
33、P2 + amj Pm ，即 Pj = aij pi ， 移项，两端同乘0 ，有 (Pj- aij pi )=0 (2),i=1,m,i=1,m,(1)+(2)： (xi 0- aij)Pi + Pj =b，取充分小，使所有xi 0 - aij 0，从而,i=1,m,X1 = (x1 0- a1j ,x2 0- a2j ,xm 0- amj ,0,0)T,也是可行解。,当取 = min aij 0 = ，则X1的前m个分量至少有一个xL1为0。,xi 0,aij,alj,xL 0,i, P1 , P2,PL-1, PL+1, Pm, Pj 线性无关。,2019年7月17日,-第 1 章 线性规
34、划-,-50-, X1 也为基本可行解。,3.最优解的判别,依题义,z0 = cjxj0 =ci xi0,i=1,m,j=1,n,z1 = cjxj1 =ci(xi 0- aij) + cj ,i=1,m,j=1,n,=cixi 0+ (cj - ciaij)= z0 + j,i=1,m,i=1,m,2019年7月17日,-第 1 章 线性规划-,-51-,因0，所以有如下结论：,(1) 对所有j，当 j0 ，有z1 z0 ，即z0为最优值，X0为最优解；(2) 对所有j，当j0 ，但存在某个非基变量k=0，则对此Pk作 为新基向量得出的解X1 ，应有z1 = z0 ，故z1 也为最优值， 从
35、而 X1为最优解，且为基本可行解， X0、X1 连线上所有的点均为最优解，因此该线性规划模型 具有无穷多解；(3) 若存在某个j 0，但对应aij0，则因当 时，有z1 ， 该线性规划模型具有无界解。,2019年7月17日,-第 1 章 线性规划-,-52-,1.4单纯形法的计算及示例,1.4.1 单纯形法几何解释-顶点寻优 例： max z=2x1+3x2 max z=2x1+3x2+0x3 +0x4 s.t x1+x23 标准化 s.t x1+x2+x3=3 x1+2x2 4 x1+2x2+x4=4 x10, x20 xj0, (j=1,2,3,4),（1）初始基本可行解的选择：-坐标原点处,令 x1 =x2 =0,由 x1+x2+x3=3 x1+2x2+x4=4,（2）是否为最优解的判定:-计算检验数,若 x11, 则 x31, x41, 1= 2-（01+0 1）=2 j =z=cj-zj = cj-ciaij ，称 j为检验数。,x3=3 -(x1+x2) x4=4 -(x1+2x2),解得 X=( 0,0,3,4 )T,
