教案线性规划

第1章线性规划第1节线性规划问题及其数学模型第2节线性规划问题的几何意义第3节单纯形法第4节单纯形法的计算步骤第5节单纯形法的进一步讨论第1节线性规划问题及其数学模型1.1问题的提出1.2图解法1.3线性规划问题的标准形式1.4线性规划问题的解的概念1.1问题的提出1.1问题的提出

例1

某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。资源产品ⅠⅡ

拥有量设备128台时原材料A4016kg原材料B0412kg每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排计划使该工厂获利最多?

1.1问题的提出用数学关系式描述这个问题1.1问题的提出得到本问题的数学模型为:这就是一个简单的线性规划模型。1.1问题的提出每一个线性规划问题都用一组决策变量表示某一方案，这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的；都有关于各种资源和资源使用情况的技术数据，创造新价值的数据；存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示;都有一个达到某一目标的要求，可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同，要求目标函数实现最大化或最小化。上述问题具有的特征：1.1问题的提出决策变量及各类系数之间的对应关系1.1问题的提出线性规划模型的一般形式1.2图解法1.2图解法例1是一个二维线性规划问题，因而可用作图法直观地进行求解。1.2图解法目标值在（4，2）点，达到最大值141.2图解法（1）无穷多最优解(多重最优解)，见图1-4。（2）无界解，见图1-5-1。（3）无可行解，见图1-5-2。通过图解法，可观察到线性规划的解可能出现的几种情况：1.2图解法目标函数maxz=2x1+4x2

图1-4无穷多最优解（多重最优解）1.2图解法图1-5-1无界解

当存在相互矛盾的约束条件时，线性规划问题的可行域为空集。例如，如果在例1的数学模型中增加一个约束条件:

则该问题的可行域即为空集，即无可行解，无可行解的情形1.2图解法增加的约束条件图1-5-2不存在可行域1.2图解法1.3线性规划问题的标准型式1.3线性规划问题的标准型式1.3线性规划问题的标准型式用向量形式表示的标准形式线性规划线性规划问题的几种表示形式1.3线性规划问题的标准型式用矩阵形式表示的标准形式线性规划1.3线性规划问题的标准型式(1)若要求目标函数实现最小化，即minz=CX，则只需将目标函数最小化变换求目标函数最大化，即令z′=−z，于是得到maxz′=−CX。(2)约束条件为不等式。分两种情况讨论：若约束条件为“≤”型不等式，则可在不等式左端加入非负松弛变量，把原“≤”型不等式变为等式约束；若约束条件为“≥”型不等式，则可在不等式左端减去一个非负剩余变量(也称松弛变量)，把不等式约束条件变为等式约束。(3)若存在取值无约束的变量xk,可令如何将一般线性规划转化为标准形式的线性规划1.3线性规划问题的标准型式例3

将例1的数学模型化为标准形式的线性规划。例1的数学模型在加入了松驰变量后变为1.3线性规划问题的标准型式例4

将下述线性规划问题化为标准形式线性规划(1)用x4−x5替换x3，其中x4，x5≥0；(2)在第一个约束不等式左端加入松弛变量x6；(3)在第二个约束不等式左端减去剩余变量x7；(4)令z′=−z，将求minz

改为求maxz′即可得到该问题的标准型。1.3线性规划问题的标准型式例4的标准型1.4线性规划问题的解概念1.可行解2.基3.基可行解4.可行基1.4线性规划问题的解的概念定义满足约束条件(1-5)、(1-6)式的解X=(x1,x2，…，xn)T，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。1.可行解1.4线性规划问题的解的概念2.基，基向量，基变量1.4线性规划问题的解的概念对应每一个基B,令所有非基变量为零，由(1-5)约束方程组求得的解X称为基解；满足非负条件（1-6）的基3基可行解解，称为基可行解.基可行解的非零分量的数目不大于m，并且都是非负的。1.4线性规划问题的解的概念对应于基可行解的基，称为可行基。约束方程组(1-5)具有的基解的数目最多是个，一般基可行解的数目要小于基解的数目。以上提到了几种解的概念，它们之间的关系可用图1-6表明。说明：当基解中的非零分量的个数小于m时，该基解是退化解。在以下讨论时，假设不出现退化的情况。4可行基1.4线性规划问题的解的概念不同解之间的关系第2节线性规划问题的几何意义2.1基本概念2.2几个定理2.1基本概念定义设K是n维欧氏空间的一点集，若任意两点X(1)∈K，X(2)∈K的连线上的所有点αX(1)+(1−α)X(2)∈K，(0≤α≤1)，则称K为凸集。图1-71.凸集2.1基本概念实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。图1-7中的(a)(b)是凸集，(c)不是凸集。图1-2中的阴影部分是凸集。任何两个凸集的交集是凸集，见图1-7(d)2.1基本概念设X(1)，X(2)，…，X(k)是n维欧氏空间En中的k个点。若存在μ1，μ2，…，μk，且0≤μi≤1,i=1,2,…，k

使X=μ1X(1)+μ2X(2)+…+μkX(k)

则称X为X(1)，X(2)，…，X(k)的一个凸组合（当0＜μi＜1时，称为严格凸组合）。2.凸组合2.1基本概念设K是凸集，X∈K；若X不能用不同的两点X(1)∈K和X(2)∈K的线性组合表示为

X=αX(1)+(1−α)X(2)，(0＜α＜1)

则称X为K的一个顶点(或极点)。图中的0，Q1,2,3,4都是顶点。3.顶点2.2几个定理定理1

若线性规划问题存在可行域，则其可行域

是凸集。2.2几个定理定理1的证明：只需证明D中任意两点连线上的点必然在D内即可。设是D内的任意两点；且X(1)≠X(2)。2.2几个定理2.2几个定理引理1

线性规划问题的可行解X=(x1,x2,…，xn)T为基可行解的充要条件是：X的正分量所对应的系数列向量是线性独立的。2.2几个定理定理2

线性规划问题的基可行解X对应于可行域D的顶点。（充要条件）证：不失一般性，假设基可行解X的前m个分量为正。故现分两步来讨论，分别用反证法。2.2几个定理

(1)若X不是基可行解，则它一定不是可行域D的顶点。根据引理1，若X不是基可行解，则其正分量所对应的系数列向量P1，P2，…，Pm线性相关，即存在一组不全为零的数αi,i=1,2,…,m，使得

α1P1+α2P2+…+αmPm=0(1-9)用一个数μ＞0乘(1-9)式再分别与(1-8)式相加和相减，得

(x1−μα1)P1+(x2−μα2)P2+…+(xm−μαm)Pm=b

(x1+μα1)P1+(x2+μα2)P2+…+(xm+μαm)Pm=b

402.2几个定理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)

，

0＜α＜1

设X是基可行解，对应的向量组P1…Pm线性独立，当j＞m时，有xj=xj(1)=xj(2)=0。由于X(1)，X(2)是可行域的两点，因而满足

（2）若X不是可行域D的顶点，则它一定不是基可行解。将两式相减，得

因X(1)≠X(2)，所以上式中的系数不全为零，故向量组P1,P2,…，Pm线性相关，与假设矛盾，即X不是基可行解。2.2几个定理引理2

若K是有界凸集，则任何一点X∈K可表示为K的顶点的凸组合。

本引理的证明从略，用以下例子说明本引理的结论。例5

设X是三角形中任意一点，X(1)，X(2)和X(3)是三角形的三个顶点，试用三个顶点的凸组合表示X(见图1-8)图1-82.2几个定理

解：任选一顶点X(2)，做一条连线XX(2)，并延长交于X(1)、X(3)连接线上一点X′。因为X′是X(1)、X(3)连线上一点，故可用X(1)、X(3)线性组合表示为X′=αX(1)+(1−α)X(3)0＜α＜1

又因X是X′与X(2)连线上的一个点，故X=λX′+(1−λ)X(2)0＜λ＜1

将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)∑iμi=1,0＜μi＜12.2几个定理定理3

若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。证：设X(1),X(2)，…，X(k)是可行域的顶点，若X(0)不是顶点，且目标函数在X(0)处达到最优z*=CX(0)(标准型是maxz=CX

)。因X(0)不是顶点，