线性规划图解法和单纯形法

第1页，课件共88页，创作于2023年2月Chapter1线性规划

(LinearProgramming)LP的数学模型图解法单纯形法单纯形法的进一步讨论－人工变量法

LP模型的应用本章主要内容：第2页，课件共88页，创作于2023年2月线性规划问题的数学模型1.规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.）第3页，课件共88页，创作于2023年2月线性规划问题的数学模型例1.1如图所示，如何截取x使铁皮所围成的容积最大？xa第4页，课件共88页，创作于2023年2月线性规划问题的数学模型例1.2某厂生产两种产品，下表给出了单位产品所需资源及单位产品利润问：应如何安排生产计划，才能使总利润最大？解：1.决策变量：设产品I、II的产量分别为x1、x22.目标函数：设总利润为z，则有：

maxz=2x1+x23.约束条件：

5x2≤156x1+2x2≤24x1+x2≤5

x1，x2≥0x1=3.8,x2=1.2,z=22.8第5页，课件共88页，创作于2023年2月线性规划问题的数学模型例1.3已知资料如下表所示，问如何安排生产才能使利润最大？或如何考虑利润大，产品好销。

设备产品AB

C

D利润（元）

Ⅰ21402

Ⅱ22043

有效台时1281612解：1.决策变量：设产品I、II的产量分别为x1、x22.目标函数：设总利润为z，则有：maxz=2x1+x23.约束条件：

x1≥0,x2≥0

2x1+2x2≤12

x1+2x2≤84x1≤164x2≤12第6页，课件共88页，创作于2023年2月线性规划问题的数学模型例1.4

某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量解：要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。1.决策变量：设四种原料的使用量分别为：x1、x2、x3

、x42.目标函数：设总成本为z

min

z=5x1+6x2+7x3+8x43.约束条件：

x1+2x2+x3+x4≥1602x1+4x3+2x4

＝2003x1

＋x2+x3+2x4

≤180

x1、x2

、x3

、x4≥0第7页，课件共88页，创作于2023年2月

例1.5

某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：航线号船队类型编队形式货运成本（千元／队）货运量（千吨）拖轮A型驳船B型驳船1112—362521—4362023224724041—42720船只种类船只数拖轮30A型驳船34B型驳船52航线号合同货运量12002400问：应如何编队，才能既完成合同任务，又使总货运成本为最小？线性规划问题的数学模型第8页，课件共88页，创作于2023年2月

解：设：xj为第j号类型船队的队数（j=1，2，3，4），

z

为总货运成本则：

minz=36x1+36x2+72x3+27x4

x1+x2+2x3+x4≤302x1+2x3≤344x2+4x3+4x4≤5225x1+20x2

＝20040x3+20x4＝400

xj

≥0（j=1,2,3,4）线性规划问题的数学模型第9页，课件共88页，创作于2023年2月线性规划问题的数学模型2.线性规划的数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。

怎样辨别一个模型是线性规划模型？

第10页，课件共88页，创作于2023年2月线性规划问题的数学模型3.建模条件(1)

优化条件：问题所要达到的目标能用线型函数描述，且能够用极值（max或min）来表示；(2)

限定条件（约束条件）：达到目标受到一定的限制，且这些限制能够用决策变量的线性等式或线性不等式表示；(3)

选择条件：有多种可选择的方案供决策者选择，以便找出最优方案。第11页，课件共88页，创作于2023年2月线性规划问题的数学模型4.建模步骤(1)

确定决策变量：即需要我们作出决策或选择的量。一般情况下，题目问什么就设什么为决策变量；(2)

找出所有限定条件：即决策变量受到的所有的约束；(3)

写出目标函数：即问题所要达到的目标，并明确是max还是min。第12页，课件共88页，创作于2023年2月线性规划问题的数学模型目标函数：约束条件：5.线性规划数学模型的一般形式简写为：第13页，课件共88页，创作于2023年2月线性规划问题的数学模型向量形式：其中：第14页，课件共88页，创作于2023年2月线性规划问题的数学模型矩阵形式：其中：第15页，课件共88页，创作于2023年2月线性规划问题的数学模型6.线性规划问题的标准形式特点：(1)目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。第16页，课件共88页，创作于2023年2月线性规划问题的数学模型（2）如何化标准形式

目标函数的转换

如果是求极小值即，则可将目标函数乘以(-1)，可化为求极大值问题。也就是：令，可得到上式。即

若存在取值无约束的变量，可令其中：

变量的变换第17页，课件共88页，创作于2023年2月线性规划问题的数学模型

约束方程的转换：由不等式转换为等式。称为松弛变量称为剩余变量

常量bi＜0

的变换:约束方程两边乘以（－1）第18页，课件共88页，创作于2023年2月线性规划问题的数学模型例1.6

将下列线性规划问题化为标准形式用替换，且解:（１）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以第19页，课件共88页，创作于2023年2月线性规划问题的数学模型(2)第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4，x4≥0,化为等式；(3)第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5，x5≥0；(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令z′=-z,得到maxz′=-z，即当z达到最小值时z′达到最大值，反之亦然;第20页，课件共88页，创作于2023年2月线性规划问题的数学模型标准形式如下：第21页，课件共88页，创作于2023年2月

例1.7将下列线性规划问题化为标准形式为无约束（无非负限制）线性规划问题的数学模型第22页，课件共88页，创作于2023年2月

解:用替换，且，将第3个约束方程两边乘以（－1）将极小值问题反号，变为求极大值标准形式如下：引入变量线性规划问题的数学模型第23页，课件共88页，创作于2023年2月

例1.8将线性规划问题化为标准型解：线性规划问题的数学模型第24页，课件共88页，创作于2023年2月

例1.9将线性规划问题化为标准型解：Minf=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

≥396x2+2x3+3x4≤-58

x1,x3,x4

≥0；x2无约束

Maxz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7

=58

x1,x2’,x2”,x3,x4,x5,x6,x7

≥0

线性规划问题的数学模型第25页，课件共88页，创作于2023年2月线性规划问题的数学模型7.线性规划问题的解线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。第26页，课件共88页，创作于2023年2月线性规划问题的数学模型

可行解：满足约束条件②、③的解为可行解。所有可行解的集合为可行域。

最优解：使目标函数达到最大值的可行解。

基：设A为约束条件②的m×n阶系数矩阵(m<n)，其秩为m，B是矩阵A中m阶满秩子方阵（∣B∣≠0），称B是规划问题的一个基。设：称B中每个列向量Pj

(j=1,2,…,m)为基向量。与基向量Pj

对应的变量xj

为基变量。除基变量以外的变量为非基变量。第27页，课件共88页，创作于2023年2月线性规划问题的数学模型

基解：某一确定的基B，令非基变量等于零，由约束条件方程②解出基变量，称这组解为基解。在基解中变量取非零值的个数不大于方程数m，基解的总数不超过

基可行解：满足变量非负约束条件的基本解，简称基可行解。可行基：对应于基可行解的基称为可行基。非可行解可行解基解基可行解第28页，课件共88页，创作于2023年2月线性规划问题的数学模型例1.10

求线性规划问题的所有基矩阵。解:约束方程的系数矩阵为2×5矩阵r(A)=2，2阶子矩阵有10个，其中基矩阵只有9个，即第29页，课件共88页，创作于2023年2月图解法线性规划问题的求解方法一般有两种方法图解法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量、但必需将一般形式变成标准形式下面我们分析一下简单的情况——

只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观的优点，便于初学者窥探线性规划基本原理和几何意义。第30页，课件共88页，创作于2023年2月

解题步骤4将最优解代入目标函数，求出最优值。1在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部分，称为可行域，可行域中的点即为可行解。2标出目标函数值增加或者减小的方向。3若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向平行移动，找与可行域最后相交的点，该点就是最优解。图解法第31页，课件共88页，创作于2023年2月图解法maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0例1.11用图解法求解线性规划问题第32页，课件共88页，创作于2023年2月图解法x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X2

20=2X1+X2

17.2=2X1+X2

Lo：0=2X1+X2

（7.6，2）DmaxZminZ此点是唯一最优解，且最优目标函数值

maxZ=17.2可行域maxZ=2X1+X2第33页，课件共88页，创作于2023年2月图解法maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2

maxZ（3.8，4）34.2=3X1+5.7X2

蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值maxZ=34.2是唯一的。可行域第34页，课件共88页，创作于2023年2月图解法minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2

maxZminZ8=5X1+4X2

43=5X1+4X2

（0，2）可行域此点是唯一最优解第35页，课件共88页，创作于2023年2月图解法246x1x2246无界解(无最优解)maxZ=x1+2x2例1.6x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ第36页，课件共88页，创作于2023年2月x1x2O10203040102030405050无可行解(即无最优解)maxZ=3x1+4x2例1.7第37页，课件共88页，创作于2023年2月

由图解法得到的几种情况

根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况：

1.可行域为封闭的有界区域

(a)有唯一的最优解；(b)有无穷多个最优解；

2.可行域为封闭的无界区域

(c)有唯一的最优解；(d)有无穷多个最优解；

(e)目标函数无界(即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少)，因而没有有限最优解。

3.可行域为空集

(f)没有可行解，原问题无最优解图解法第38页，课件共88页，创作于2023年2月

由图解法得到的启示线性规划问题解的情况：

唯一最优解；无穷多最优解；无界解；无可行解(2)线性规划问题的可行域是凸集（凸多边形）图解法第39页，课件共88页，创作于2023年2月图解法x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)17.2=2X1+X2

Lo：0=2X1+X2

（7.6，2）DmaxZminZ可行域maxZ=2X1+X2(3)最优解一定是在凸集的某个顶点第40页，课件共88页，创作于2023年2月

解题思路先找出凸集的任一顶点，计算其目标函数值，再与周围顶点的目标函数值比较，如不是最大（或最小），继续比较，直到找出最大（或最小）为止。图解法第41页，课件共88页，创作于2023年2月图解法

学习要点：

1.通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）

2.作图的关键有三点：

(1)可行解区域要画正确

(2)目标函数增加的方向不能画错

(3)目标函数的直线怎样平行移动第42页，课件共88页，创作于2023年2月

连接几何形体中任意两点的线段仍完全在该几何形体之中。有限个凸集的交集仍然是凸集。单纯形法基本原理凸集第43页，课件共88页，创作于2023年2月单纯形法基本原理凸集：如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，称C为凸集。凸集凸集不是凸集第44页，课件共88页，创作于2023年2月单纯形法基本原理凸集凸集顶点

顶点：如果凸集C中不存在任何两个不同的点X1，X2，使X成为这两个点连线上的一个点第45页，课件共88页，创作于2023年2月单纯形法基本原理定理1：若线性规划问题存在可行解，则该问题的可行域是凸集。定理2：线性规划问题的基可行解X对应可行域(凸集)的顶点。定理3：若问题存在最优解，一定存在一个基可行解是最优解。（即在某个顶点取得）第46页，课件共88页，创作于2023年2月几个基本定理的证明定理1

若线性规划问题存在可行解，则问题的可行域是凸集。思路：若满足线性规划约束条件的所有点组成的几何图形C是凸集，根据凸集的定义，C内任意两点X1,X2连线上的点也必然在C内。【证】设为C内任意两点，即 ，将X1,X2代入约束条件有X1,X2连线上任意一点可以表示为：第47页，课件共88页，创作于2023年2月将(1.9)代入约束条件并由式(1.8)得：所以。由于集合内任意两点连线上的点均在集合内，所以C

为凸集。第48页，课件共88页，创作于2023年2月一个引理引理

线性规划问题的可行解为基可行解的的充要条件是X的正分量所对应的系数列向量是线性独立的。【证】必要性由基可行解的定义是显然的。充分性：若向量P1,P2,…,Pk是线性独立的，则必有k≤m。1)当k=m时，它们恰好构成一个基，从而相应的基可行解为2)当k<m时，则一定可以从其余列向量中找出(m-k)个向量与P1,P2,…,Pk构成一个基，其对应的解恰为X，根据定义它是基可行解。第49页，课件共88页，创作于2023年2月定理2线性规划问题的基可行解X对应于线性规划问题可行域（凸集）的顶点。本定理需要证明：X是可行域顶点X是基可行解。采用的是反证法，即证明X不是可行域的顶点X不是基可行解。【证】（1）X不是基可行解X不是可行域的顶点。不失一般性，假设X的前m个分量为正，故有根据假设X不是基可行解，由引理知线性相关，即存在一组不全为零的数使得有第50页，课件共88页，创作于2023年2月上式乘上一个不为零的数得：

±令

即X不是可行域的顶点。第51页，课件共88页，创作于2023年2月（2）X不是可行域的顶点X不是基可行解。不失一般性，设不是可行域的顶点，因而可以找到可行域内另外两个不同点Y和Z，有：

或可写为：因，故当时，必有因有第52页，课件共88页，创作于2023年2月故有两式相减得因不全为零，故线性相关，由引理知X不是基可行解。第53页，课件共88页，创作于2023年2月定理3

若线性规划问题有最优解，一定存在一个基可行解是最优解。【证】设是线性规划的一个最优解， 是目标函数的最大值。若不是基可行解，由定理2知不是顶点，一定能在可行域内找到通过的直线上的另外两个点将这两个点代入目标函数有第54页，课件共88页，创作于2023年2月因为目标函数的最大值，故有由此，即有如果仍不是基可行解，按上面的方法继续做下去，最后一定可以到到一个基可行解，其目标函数值等于，问题得证。第55页，课件共88页，创作于2023年2月单纯形法的计算步骤单纯形法的思路找出一个初始可行解是否最优转移到另一个基本可行解（找出更大的目标函数值）最优解是否循环核心是：变量迭代结束第56页，课件共88页，创作于2023年2月STEP1确定初始基可行解当线性规划的约束条件全部为“≤”时，在第i个约束条件上加上松弛变量xsi(i=1,…,m)，化为标准形式第57页，课件共88页，创作于2023年2月那么约束方程满足的系数矩阵为该矩阵中含一个单位矩阵，只要以此作为基，就可以立即解出基变量的值xsi=bi(i=1,…,m)。因为有bi≥0(i=1,…,m)，由此得到X=(0,…,0,b1,…,bm)T就是一个基可行解。当线性规划约束条件为“＝”或者“≥”时，化为标准形后，一般约束条件的系数矩阵也不含有单位矩阵。人工基→初始可行解人工变量法第58页，课件共88页，创作于2023年2月STEP2从初始基可行解转化为另一基可行解设初始基可行解为，其中非零坐标有m个。不失一般性，假定前m个坐标为非零，即可行基为：[P1

P2

…

Pm]因，故有写出其系数矩阵的增广矩阵，用构造人工基的方法可以使基矩阵是单位矩阵形式。第59页，课件共88页，创作于2023年2月因为是一个基，其他向量可用这个基的线性组合来表示将（1.16）式乘上一个正的数>0得第60页，课件共88页，创作于2023年2月式(1.15)+式(1.17)，并经过整理后有由上式找到满足约束方程组的另外一个点：其中是的第j

个坐标的值。要使是一个基可行解，因>0，故应对所有i=1,..,m存在且这m个不等式中至少有一个等号成立，因为当时，上式显然成立。第61页，课件共88页，创作于2023年2月这样中正分量最多有m个，容易证明m个向量线性无关，故只需按式(1.20)来确定的值，就是一个新的基可行解。令第62页，课件共88页，创作于2023年2月基本可行解和可行基的变换基本可行解：可行基：换出基换入基第63页，课件共88页，创作于2023年2月STEP3最优性检验和解的判别将基可行解分别代入目标函数得因

>0为给定，所以只要有通常简写为，它是对线性规划问题的解进行最优性检验的标志。第64页，课件共88页，创作于2023年2月当所有的时，表明现有顶点（基可行解）的目标函数值比起相邻各顶点（基可行解）的目标函数值都大，现有顶点对应的基可行解即为最优解。当所有时，对某个非基变量xj有，且按公式(1.20)可找到>0，这表明可以找到另一顶点（基可行解）目标函数也达到最大。由于该两点连线上的点也属可行域内的点，且目标函数值相等，即该线性规划问题有无穷多最优解。如果存在某个又Pj向量的所有分量aij≤0。换基时对任意

>0,恒有因取值可无限大，在由X(0)换到X(1)时目标函数值也可无限大，则线性规划问题存在无界解。第65页，课件共88页，创作于2023年2月引例：求解线性规划问题LP规划问题的最优解可从基可行解（顶点）中找到

图解法有局限性；

枚举法计算量大；第66页，课件共88页，创作于2023年2月解：第一:将该问题化成标准形第二:

找初始可行解(即一个顶点)。系数矩阵A=(P1

P2

P3

P4

P5)矩阵形式第67页，课件共88页，创作于2023年2月

因为P3，P4，

P5线性独立，故B=(P3,P4,P5)构成一个基，其对应的基变量x3，x4，x5，解出来为（用非基变量表示基变量）

x3=8-x1-2x2

x4=16-4x1(1)

x5=12-4x2XB=B-1

b

–B-1NXN将(1)代入目标函数中得z=0+2x1+3x2令非基变量x1=x2=0，则有z=0。这时得到一个基可行解：

X(0)=(0,0,8,16,12)T---原点第68页，课件共88页，创作于2023年2月第三:判别从目标函数z=0+2x1+3x2中得知，非基变量x1和x2的系数为正，因此，将非基变量换入基后可使目标函数增大，转入第四步第四：换基(旋转迭代)

确定换入变量：由于非基变量x2的系数（正）贡献最大，故需换入的基变量为x2。换入变量已定，必须从x3，x4，x5换出一个，并且要保证其余均是非负的，即x3，x4，x50。当x1=0时，有x3=8-2x2

0

x4=160

x5=12-4x20x2换入基，x1未换入，还是非基变量第69页，课件共88页，创作于2023年2月

只要选择x2=min(8/2，-，12/4)=3，对应基变量x5=0，从而确定用x2和x5对换，即将x5

换出，（用非基变量表示基变量）2x2+

x3=8-x1

x4=16-

4x1

4x2=12-x5

用高斯消去法（行变换），得

x3=2-x1+1/2x5

x4=16-

4x1

x2

=3-1/4x5

（2）将上式代入原目标函数中得z=9+2x1-3/4x5（1）第70页，课件共88页，创作于2023年2月

返回第三步：从z=9+2x1-3/4x5，非基变量x1的系数是正的，还可增大。重复上述步骤。由于x1的系数是正的，则x1为转入变量，再由当x5=0时

x3=2-x1

0

x4=16-

4x10

x2=30

只要选x1=min{2，16/4，-}=2上式就成立，因为x1=2时，基变量x3=0，从而由x1换出x3令非基变量x1和x5为零有z=9，又得到另一个基可行解

X(1)=(0,3,2,16,0)T–顶点Q4第71页，课件共88页，创作于2023年2月

x1+2x2=8-x3

4x1+x4=16

(3)4x2=12-x5高斯消去法（行变换）得

x1=2-x3+1/2x50

x4=8-2x5+4x30

x2=3-1/4x5

0

代入目标函数中，得

z=13-2x3+1/4x5令非基变量x3=x5=0有z=13，又得到另一个基可行解

X(2)=(2,3,0,8,0)T–顶点Q3;（2）用非基变量表示基变量第72页，课件共88页，创作于2023年2月同理，返回第三步，再迭代，x5作为转入变量只要取x5=min{-，8/2，12}=4就有上式成立。x5=4时，x4=0，故用x5换x4

x1=4-1/4x4

x5=4-1/2x4+2x3

x2=2+1/8x4–1/2x3

令x3=0，有x1=2+1/2x5

0

x4=8-2x50

x2=3-1/4x5

0

（3）+高斯第73页，课件共88页，创作于2023年2月0Q4Q3Q2Q11123234X1X2x1+2x2=84x1=164x2=12代入得z=14-3/2x3-1/8x4

，令x3=x4=0得z=14。新的基可行解为

X(3)=(4,2,0,0,4)T–顶点Q2(最优解)最优目标值z=14

。(0,3,2,16,0)(0,0,8,16,12)(2,3,0,8,0)(4,2,0,0,4)第74页，课