线性规划-课件

线性规划线性规划1数学建模线性规划数学建模线性规划2第二讲线性规划线性规划第二讲线性规划3§2.1引言

线性规划是运筹学的重要分枝，也是运筹学最基本的部分。

20

世纪

30

年代末，前苏联学者康托洛维奇首先研究了线性规划问题。1939

年，他撰写的《生产组织与计划中的数学方法》一书，是线性规划应用于工业生产问题的经典著作。

然而这项工作长期不为人们所知。线性规划§2.1引言线性规划4

第二次世界大战期间，由于战争的需要，柯勃门(T.C.Koopmans)重行、独立地研究了运输问题。

后来丹西格(G.B.Dantzig)于

1947

年发现了单纯形方法，并将其应用于与国防有关的诸如人员的轮训、任务的分派等问题。此后，线性规划的理论和方法日渐趋于成熟。线性规划第二次世界大战期间，由于战争的需要，柯勃门(5

线性规划所研究的对象属于最优化的范畴，本质上是一个极值问题。和其它最优化问题一样，在建立线性规划问题的数学模型时，应首先明确三个基本要素：

决策变量(decisionvariables)：它们是决策者(你)所控制的那些数量，它们取什么数值需要决策者来决策，问题的求解就是找出决策变量的最优值。线性规划线性规划所研究的对象属于最优化的范畴，本质上6

约束条件(constraints)：它们是决策者在现实世界中所受到的限制，或者说决策变量在这些限制范围之内才有意义。

目标函数(objectivefunction)：它代表决策者希望对其进行优化的那个指标。目标函数是决策变量的函数。线性规划问题的特征是目标函数和约束条件中的函数都是决策变量的线性函数，并且约束是必不可少的(否则不存在有实际意义的解)。线性规划约束条件(constraints)：它们是决7§2.2引例：食用油加工计划

加工一种食用油需要精炼若干种原油并把它们混合起来。原油来源有两类共5种：植物油：VEG1，VEG2非植物油：OIL1，OIL2，OIL3购买每种原油的价格(镑/吨)见表2.2.1：线性规划§2.2引例：食用油加工计划线性规划8VEG1VEG2OIL1OIL2OIL3110120130110115表2.2.1：

最终产品以150镑/吨价格出售。

植物油和非植物油需要在不同的生产线上进行精炼。每月能够精炼的植物油不超过

200吨，非植物油不超过

250

吨；在精炼过程中，重量没有损失，精炼费用可忽略不计。线性规划VEG1VEG2OIL1OIL2OIL311012013019VEG1VEG2OIL1OIL2OIL38.86.12.04.25.0最终产品要符合硬度的技术条件。按照硬度计量单位，它必须在

3~6

之间。假定硬度的混合是线性的，而原油的硬度见表2.2.2：表2.2.2问：为使利润最大，应该怎样制定它的月采购和加工计划？线性规划VEG1VEG2OIL1OIL2OIL38.86.12.0410要建立表述这个问题的数学模型，首先需要确定它的三个要素。1．确定决策变量设x1,…,x5分别代表需要采购的

5

种原油的吨数，y代表需要加工的成品油的吨数。线性规划要建立表述这个问题的数学模型，首先需要确定它112．确定约束条件生产能力限定：x1+x2

200(植物油200吨)x3+x4+x5

250(非植物油250吨)技术指标(硬度)限定：8.8x1+6.1x2+2x3+4.2x4+5x5

6y8.8x1+6.1x2+2x3+4.2x4+5x5

3y连续性(均衡性)：x1+x2+x3+x4+x5=y非负性：xi

0(i=1,…,5)，y

0线性规划2．确定约束条件线性规划123．确定目标函数目标是使利润最大，即出售产品的收入扣除原油成本之后所得最大：150y

110x1

120x2

130x3

110x4

115x5

最大线性规划3．确定目标函数线性规划13显然这是一个线性规划问题，可以用下面的数学模型来表述这个问题：线性规划显然这是一个线性规划问题，可以用下面的数学模型来表述14§2.3线性规划模型§2.3.1线性规划模型的一般形式线性规划问题有各种不同形式，其目标函数可以是实现最大化，也可以是实现最小化；约束条件可以是“

”，也可以是“

”，还可以是“=”的形式；决策变量可以非负，也可以是无符号限制。线性规划§2.3线性规划模型线性规划15归纳起来，线性规划问题的数学模型的一般形式为：线性规划归纳起来，线性规划问题的数学模型的一般形式为：线性16或者：这里“s.t.”是“subjectto”的缩写，即“满足于”的意思。线性规划或者：这里“s.t.”是“subjectto”的线性规划17如果我们设

线性规划一般形式也可用矩阵形式描述为：线性规划如果我们设线性规划一般形式也可用矩阵形式描述为：线性规划18§2.3.2线性规划模型的标准形式为理论研究之便，人们规定线性规划模型的标准形式为：线性规划§2.3.2线性规划模型的标准形式线性规划19若给定问题的目标函数是求

min

Z

=

CTX，则可化为求maxZ'=

CTX；若给定问题的约束条件中含有不等式：ai1x1

ai2x2

…

ainxn

(或

)bi，则可等价地化为：ai1x1

ai2x2

…

ainxn

xn+1=bi，xn+1

0或ai1x1

ai2x2

…

ainxn

xn+1=bi，xn+1

0我们称新增加的变量xn+1为松弛变量。线性规划若给定问题的目标函数是求minZ=C20§2.3.3线性规划问题解的概念

对于线性规划问题，我们定义：可行解：满足全部约束条件的决策向量。可行域：全部可行解构成的集合(它是

n

维欧氏空间

Rn

中的点集，而且是一个“凸多面体”)。最优解：使目标函数达到最优值(最大值或最小值，并且有界)的可行解。无界解：若求极大化则目标函数在可行域中无上界；若求极小化则目标函数在可行域中无下界。

线性规划§2.3.3线性规划问题解的概念线性规划21线性规划问题的最优解有下列几种情况：(1)有最优解时，可能有唯一最优解，也可能有无穷多个最优解。如果最优解不唯一，最优解一定有无穷多个，不可能为有限个。最优解的目标函数值均相等。(2)没有最优解时，也有两种情形。一是可行域为空集，二是目标函数值无界(求最大时无上界，求最小时无下界)。线性规划线性规划问题的最优解有下列几种情况：线性规划22

定理：当线性规划问题有最优解时，一定可以在可行域的某个顶点上取到。当有唯一解时，最优解就是可行域的某个顶点。当有无穷多个最优解时，其中至少一个是可行域的一个顶点。线性规划定理：当线性规划问题有最优解时，一定可以在可23§2.3.4几何解释在这部分，我们给出一种求解两个变量的线性规划问题的几何方法，目的是阐明线性规划问题的基本原理及其直观的几何意义。线性规划§2.3.4几何解释线性规划24例2.3.1求解线性规划问题maxZ=x1

x2s.t.2x1

3x2

63x1

2x2

6

xi

0(i=1,2)我们把

x1,

x2

看成坐标平面上的坐标，则满足约束条件的点集，即可行域，如图

2.3.1

阴影部分所示。线性规划例2.3.1求解线性规划问题线性规划25图2.3.1可行域线性规划图2.3.1可行域线性规划26目标函数x1+x2=c在坐标平面上是一簇平行线，称为目标函数的等值线，在同一等值线上目标值相等。箭头表示目标函数值增大的方向，其方向与目标函数的梯度方向

(1,1)T

相同。

线性规划目标函数x1+x2=c在坐标平面27由于是求最大值问题，目标函数的等值线应沿梯度方向移动，到临界状态，即可行域的顶点(6/5,6/5)处，目标函数取得最大值12/5。继续沿梯度方向上升，目标函数值会更大，但与可行域无交点，即找不到满足所有约束条件的点使得目标值比12/5大。线性规划由于是求最大值问题，目标函数的等值线应沿梯度28图2.3.1线性规划图2.3.1线性规划29因此，线性规划问题的最优解为临界等值线与可行域的交点：x*=(6/5,6/5)，最优值为12/5。

线性规划因此，线性规划问题的最优解为临界等值线与可行30例2.3.2求解线性规划问题maxZ=2x1

3x2s.t.2x1

3x2

63x1

2x1

6

xi

0(i=1,2)线性规划问题的可行域仍如图2.3.1所示；目标函数的等值线为

2x1

3x2

=

c；目标函数的梯度方向为

(2,3)T。线性规划例2.3.2求解线性规划问题31图2.3.1线性规划图2.3.1线性规划32由于是求最大值问题，目标函数的等值线应沿梯度方向推进，临界等值线为2x1

3x2=6与可行域交于一线段

PQ，其中

P(0,

2)，Q(6/5,6/5)，最优解为PQ上任一点，最优值为6。线性规划由于是求最大值问题，目标函数的等值线应沿梯度33图2.3.1线性规划图2.3.1线性规划34例2.3.3求解线性规划问题minZ=

2x1

x2，s.t.

x1

x2

2

x1

4x2

2

xi

0(i=1,2)线性规划问题的可行域如图

2.3.2

所示，目标函数的梯度方向为

(

2,

1)T。由于是求最小值问题，目标函数的等值线应沿负梯度方向推进，可一直进行下去，得不到临界等值线，此问题目标值无下界，无最优解。线性规划例2.3.3求解线性规划问题35线性规划线性规划36例2.3.4求解线性规划问题minZ=

2x1

5x2，s.t.

x1

x2

2

x1

x2

3

xi

0(i=1,2)线性规划问题的可行域如图2.3.3所示，是一空集。此问题无最优解。线性规划例2.3.4求解线性规划问题37线性规划线性规划38§2.4用Matlab解线性规划在

Matlab

软件的优化工具箱中，求解线性规划的函数为：linprog。其调用格式为x=linprog(c,A,b,Aeq,beq,xLB,xUB)线性规划§2.4用Matlab解线性规划线性规划39适用模型为：其中Aeq、beq表示约束条件中的等式约束部分AeqX=beq的系数矩阵和常数向量。

使用Matlab求解线性规划问题，必须是这样的“标准形式”。线性规划适用模型为：其中Aeq、beq表示约束条件中的等式约束部40

例2.4.1在§2.2的引例中，我们对食用油加工计划问题建立了如下的线性规划模型：线性规划例2.4.1在§2.2的引例中，我们41将上述模型改写成Matlab适用的模型，其形式为：线性规划将上述模型改写成Matlab适用的模型，42建立M文件，编写Matlab程序：c=[110;120;130;110;115;-150]A=[1,1,0,0,0,0;0,0,1,1,1,0;8.8,6.1,2,4.2,5,-6;-8.8,-6.1,-2,-4.2,-5,3];b=[200;250;0;0];Aeq=[1,1,1,1,1,-1];beq=0;xLB=zeros(6,1);xUB=inf*ones(6,1);x=linprog(c,A,b,Aeq,beq,xLB,xUB);x，Profit=c'*x线性规划建立M文件，编写Matlab程序：线性规划43运行上述Matlab程序，计算得：x=159.259340.74070.0000250.00000450.0000Profit=-1.7593e+004线性规划运行上述Matlab程序，计算得：x=线性规划44于是月采购与生产计划为：原油VEG1VEG2OIL1OIL2OIL3采购量159.259340.740702500生产量：450总利润：1.7593

104线性规划于是月采购与生产计划为：原油VEG1VEG2OIL1OIL45§2.5灵敏度分析与参数线性规划§2.5.1线性规划问题的灵敏度分析灵敏度分析是指对系统因周围条件变化显示出来的敏感程度的分析。

线性规划§2.5灵敏度分析与参数线性规划§2.5.1线性规划46在前面讨论线性规划问题时，我们都设定aij,bi,cj是常数。但在许多实际问题中，包括大型线性规划问题，这些系数往往是估计值或预测值，经常有少许的变动。例如在§2.2的引例中，如果市场条件发生变化，cj

值就会随之变化；生产工艺条件发生改变，会引起

bi

变化，aij也会由于种种原因产生改变。线性规划在前面讨论线性规划问题时，我们都设定aij,47因此提出这样两个问题：当线性规划模型中的参数有一个或几个发生不大的变化时，已求得的线性规划问题的最优解会有什么变化；或者这些参数在什么范围内变化时，线性规划问题的最优解不变。这涉及解的稳定性问题。线性规划因此提出这样两个问题：线性规划48当然，有一套理论方法可以进行灵敏度分析(参见[1],[2])，这里就不讨论了。但在实际应用中，对于不同的参数值重复求解线性规划问题，不失为一种可用的方法，特别是使用计算机求解时。线性规划当然，有一套理论方法可以进行灵敏度分析(参见49§2.5.2参数线性规划参数线性规划是研究

aij,

bi,

cj

这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量，而目标函数在某区间内是这参变量的线性函数，含这参变量的约束条件是线性等式或不等式。当然，在实际应用中，给定参变量一个步长重复求解线性规划问题，以观察最优解变化情况，也是一种可用的数值方法。线性规划§2.5.2参数线性规划线性规划50§2.6范例

载货问题：有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如下面表2.6.1所示。前舱中舱后舱最大允许载重量(t)200030001500容积(m3)400054001500线性规划§2.6范例前舱中舱后舱最大允许载重量(t)2000351现有三种货物待运，已知有关数据列于下面表2.6.2。商品数量(件)每件体积(m3/件)每件重量(t/件)运价(元/件)A6001081000B100056700C80075600线性规划现有三种货物待运，已知有关数据列于下面表252又为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求前、后舱分别与中舱之间载重量比例上偏差不超过

15%，前、后舱之间不超过10%。问该货轮应装载A、B、C各多少件，运费收入为最大？线性规划又为了航运安全，要求前、中、后舱在实际载重量53

解：(1)确定决策变量

因为A、B、C三种商品在货轮的前、中、后舱均可装载，令i=1,2,3分别代表商品A、B、C，用j=1,2,3分别代表前、中、后舱。设决策变量

xij

为装于

j

舱位的第

i

种商品的数量(件)。线性规划解：(1)确定决策变量线性规划54

(2)确定目标函数

商品A的件数为：x11+x12+x13，即装于货轮前、中、后舱商品A的件数之和；

商品B的件数为：x21+x22+x23，即装于货轮前、中、后舱商品B的件数之和；

商品C的件数为：x31+x32+x33，即装于货轮前、中、后舱商品C的件数之和。

为使运费总收入最大，目标函数为

maxZ=1000(x11+x12+x13)+700(x21+x22+x23)+600(x31+x32+x33)线性规划(2)确定目标函数线性规划55

(3)确定约束条件

前、中、后舱位载重量限制为：

8x11+6x21+