第二章 线性规划解的概念、性质及图解法

图解法线性规划问题求解的几种可能结果由图解法得到的启示

2.2线性规划解的概念、性质及图解法继续返回例1的数学模型

目标函数MaxZ=2x1+3x2

约束条件x1+2x2

84x1

164x2

12x1、x2

0x1

x29—8—7—6—5—4—3—2—1—0

| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2x1+2x2

8(0,4)(8,0)

目标函数MaxZ=2x1+3x2约束条件x1+2x2

8

4x1

164x2

12x1、x2

04x1

164x2

12图解法可行域步骤一：由全部约束条件作图求出可行域；9—8—7—6—5—4—3—2—1—0

| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0x1+2x2

84x1

164x2

12可行域BCDEA图解法B9—8—7—6—5—4—3—2—1—0

x2

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

12BCDEA2x1+3x2=6图解法步骤二：作目标函数等值线，确定使目标函数最优的移动方向；9—8—7—6—5—4—3—2—1—0

x2

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

12BCDEA图解法x1+2x2=84x1=16MaxZ=14最优解(4,2)步骤三：平移目标函数的等值线，找出最优点，算出最优值。图解法求解步骤由全部约束条件作图求出可行域；作目标函数等值线，确定使目标函数最优的移动方向；平移目标函数的等值线，找出最优点，算出最优值。9—8—7—6—5—4—3—2—1—0

x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1BCDEA最优解(4,2)改变约束条件或目标函数，解的结果如何？线性规划问题求解的

几种可能结果(a)唯一最优解

9—8—7—6—5—4—3—2—1—0

x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1BCDEA线性规划问题求解的

几种可能结果x1+2x2

=8

目标函数MaxZ=x1+2x2约束条件x1+2x2

84x1

164x2

12x1、x2

0(b)无穷多最优解(c)无界解

MaxZ=x1+x2

-2x1+x2

4

x1-x2

2

x1、x2

0

x2x1线性规划问题求解的

几种可能结果(d)无可行解

MaxZ=2x1+3x2

x1+2x2

84x1

164x2

12

-2x1+x24x1、x2

0可行域为空集线性规划问题求解的

几种可能结果图解法的几点结论:

（由图解法得到的启示）可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函数值，比较即得。练习：

用图解法求解LP问题

MaxZ=15

x1+25

x2x1+3x2

60

x1+

x2

40

x1、x2

0maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

L1Z=250目标函数变形：x2=-3/5

x1+z/25x2x1最优解：

x1=30x2=10最优值：zmax=700B点是使z达到最大的唯一可行点(30,10)A（0,20）C（40,0）0B习题：用图解法求下列线性规划:习题2maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4

x1，x2≥0习题3maxz=2x1+2x2s.t.x1+x2≥1x1

–

3x2≥–

3

x1≤3

x1，x2≥0习题4maxz=5x1+3x2s.t.x1+x2≤1x1+2x2≥4

x1，x2≥0Ox1x2Note:可行域为无界区域，目标函数值可无限增大，即解无界。称为无最优解。A(1,0)可行域为无界区域一定无最优解吗？maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4

x1，x2≥0习题：用图解法求下列线性规划:

0x1x2A(1,0)minZ(多解)线段AD上的任一点都是最优解minZ=2习题3maxz=2x1+2x2s.t.x1+x2≥1x1

–

3x2≥–

3

x1≤3

x1，x2≥0(30,10)B(3,0)C(3,2)D(0,1)若minZ换为maxZ则最优解为?点

0x1x2A(1,0)(30,10)B(4,0)D(0,1)习题4maxz=5x1+3x2s.t.x1+x2≤1x1+2x2≥4

x1，x2≥0C(0,2)无可行解

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

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

(a)有唯一的最优解；

(b)有无穷多个最优解；

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

(c)有唯一的最优解；

(d)有无穷多个最优解；

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

3.可行域为空集

(f)没有可行解，原问题无最优解

二、线性规划解的有关概念可行解、最优解基、基变量、非基变量基本解、基本可行解可行基、最优基继续返回Ax=b，x≥0；1.可行解与最优解极点定义1设集合是n维欧氏空间中的一个点集，如果及实数

则称

S是一个凸集。几何意义：如果集合中任意两点连线上的一切点都在该集合中，则称该集合为凸集。

凸集定义2

设则称为点的一个凸组合。定义3设凸集两点表示为则称x为S

的一个极点（或顶点）。

定理LP问题的可行解集ＬＰ的可行域以及最优解有以下性质:1.若线性规划的可行域非空，则可行域必定为一凸集．2.若线性规划的可行域非空，则至多有有限个极点.3.若线性规划有最优解,则至少有一个极点是最优解.可行域内无限个可行解可行域的有限个极点搜索1.图解法求解步骤由全部约束条件作图求出可行域；作目标函数等值线，确定使目标函数最优的移动方向；平移目标函数的等值线，找出最优点，算出最优值。小结：1.可行域为封闭的有界区域

(a)有唯一的最优解；

(b)有无穷多个最优解；

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

(c)有唯一的最优解；

(d)有无穷多个最优解；

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

3.可行域为空集

(f)没有可行解，原问题无最优解

2.线性规划的可行域和最优解Ax=b，x≥0；3.可行解与最优解1.若线性规划的可行域非空，则可行域必定为一凸集．2.若线性规划的可行域非空，则至多有有限个极点.3.若线性规划有最优解,则至少有一个极点是最优解.可行域内无限个可行解可行域的有限个极点搜索4.线性规划的可行域和最优解的性质2.线性规划的基、基本解与基本可行解

在一般情况下，由于图解法无法解决三个变量以上的线性规划问题，对于n个变量的线性规划问题，我们必须用解方程的办法来求得可行域的极点。再来进一步考察前例。

2.线性规划的基、基本解与基本可行解

例2.8把例2.1的线性规划模型标准化，引入松驰变量 x3

，x4

，x5≥0，得到

Maxz=1500x1

+2500x2

s.t.3x1+2x2+x3=65(A)

2x1+x2+x4=40(B)

3x2+x5=75(C)

x1

,x2

,x3,x4

,x5

≥0

用（D）（E）（F）（G）（H）分别表示x1

=0、x2

=0、x3=0、x4

=0、x5

=0。

这里一共有8个约束条件，其中3个等式约束（一般情况下，等式约束的个数少于决策变量的个数），5个变量非负约束（与决策变量个数相同）。每5个方程若线性无关可解得一个点，我们可以看到前例图解法得到的区域中每两条直线的交点与此例的各个方程有如下关系：见下图。

由上图可以看出：直线A、B的交点对应于约束条件(A)、（B）、（C）、（F）、（G）的解，即：x(1)=(15,10,0,0,45)T

直线A、C的交点对应于约束条件(A)、（B）、（C）、（F）、（H）的解，即：x(2)=(5,25,0,5,0)T

直线A、D的交点对应于约束条件(A)、（B）、（C）、（D）、（F）的解，即：x(3)=(0,32.5,0,7.5,-22.5)TMaxz=1500x1+2500x2

s.t.3x1+2x2+x3=65(A)

2x1+x2+x4=40(B)

3x2+x5=75(C)

x1,x2,x3,x4,x5≥0用（D）（E）（F）（G）（H）分别表示x1=0、x2=0、x3=0、x4=0、x5=0。X(1)X(2)X(3)DE

直线A、E的交点对应于约束条件(A)、（B）、（C）、（E）、（F）的解，即：x(4)=(65/3,0,0,-10/3,75)T

直线B、C的交点对应于约束条件(A)、（B）、（C）、（G）、（H）的解，即：x(5)=(7.5,25,-7.5,0,0)T

直线B、D的交点对应于约束条件(A)、（B）、（C）、（D）、（G）的解，即：x(6)=(0,40,-15,0,-45)TEDX(5)X(6)

直线B、E的交点对应于约束条件(A)、（B）、（C）、（E）、（G）的解，即：x(7)=(20,0,5,0,75)T

直线C、D的交点对应于约束条件(A)、（B）、（C）、（D）、（H）的解，即：x(8)=(0,25,15,15,0)T

直线C、E无交点（C、E相互平行）直线D、E的交点对应于约束条件(A)、（B）、（C）、（D）、（E）的解，即：x(9)=(0,0,65,40,75)TEX(8)X(9)

如果某一交点的坐标(x1

,x2,x3,x4,x5

)T全为非负，则该交点就对应于线性规划可行域的一个极点（如A、B，A、C，B、E，C、D和D、E的交点，共5个）如果某一交点的坐标中至少有一个分量为负值（如A、D，A、E，B、C和B、D的交点），则该交点不是可行域的极点。E定义线性规划的约束条件：

Ax=b，x≥0；A是m×n矩阵，m≤n并且r(A)=m。

（1）线性规划的基基

(basis)：B是A中的一个非奇异（可逆）的m×m子矩阵，即|B|≠0

，则称B是线性规划的一个基(或基矩阵)。当m=n时，基矩阵惟一，当m<n时，基矩阵就可能有多个，但数目不超过。行满秩的矩阵基向量：基B中的列

pj(j=1,2,…,m);基变量：与基向量对应的决策变量

xj(j=1,2,…,m)；非基变量：与非基向量对应的决策变量

xj(j=m+1,…,n)非基向量：A中除基向量外，其余的列pj(j=m+1,…,n);（1）线性规划的基任取A中的m个线性无关列向量构成矩阵B，则B是A的一个基；【解】约束方程的系数矩阵为2×4矩阵

容易看出r(A)=2，2阶可逆子矩阵最多有几个？C42=6基向量：

p1和p2基变量：x1和x2，基向量：

p3和p4基变量：x3

和x4基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。非基向量：

p3和p4非基向量：

p1和p2非基变量：x1和x2非基变量：x3和x4若B是线性规划的一个基，设是A的前m列，则A可以表示为A=[B,N]，x也可相应地分成

xBx=xN其中:xB为m维列向量，它的各分量称为基变量，与基B的列向量对应；

xN为n-m维列向量，它的各分量称为非基变量，与非基矩阵N的列向量对应。（2）基本解、基本可行解和可行基

基矩阵这时约束等式Ax=b可表示为

xB

（B,N）=b

xN

或

BxB

+NxN

=b

如果对非基变量xN取确定的值，则xB有唯一的值与之对应

xB=B-1b-B-1NxN

特别，当取xN=0，这时有xB=B-1b。

求解

基变量令非基变量T可求出：基本解：称由约束求出的X解为基本解。矩阵描述为，对于线性规划的解

xB

B-1b

x==

xN0

称为线性规划与基B对应的基本解。若其中B-1b≥

0，则称以上的基本解为一基本可行解（即非负的基本解），相应的基B称为可行基。

系数阵A中可找出多个基B返回非负的基本解就是基本可行解每个基B都对应于一个基本解注意：线性规划的基本解、基本可行解和可行基只与线性规划问题标准形式的约束条件有关。与目标函数无关。

线性规划解的关系图非可行解可行解

基本可行解

基本解

结论：线性规划的基本可行解就是可行域的极点。最优解？求相应于B1和B6的基本解，是否基本可行解？相应于基B6的基本解为X=(0,0,1,3)，是基本可行解.相应于基B1的基本解为X=(7/5,-1/5,0,0)，不是基本可行解.

线性规划的基本定理

“线性规划的基本可行解就是可行域的极点”．－－线性规划的基本定理

这一基本定理把可行域的极点这一几何概念与基本可行解这一代数概念联系起来，因而可以通过求基本可行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。这里指出了一种求解线性规划问题的可能途径，就是先确定线性规划问题的基，如果是可行基，则计算相应的基本可行解以及相应解的目标函数值。由于基的个数是有限的,因此必定可以从有限个基本可行解中找到最优解。1、线性规划的基基

(basis)：B是A中的一个非奇异（可逆）的m×m子矩阵，即|B|≠0

，则称B是线性规划的一个基(或基矩阵)