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

上页下页返回图解法线性规划问题求解的几种可能结果由图解法得到的启示2.2线性规划解的概念、性质及图解法继续返回上页下页返回上页下页返回例1的数学模型目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20x1x2上页下页返回9—8—7—6—5—4—3—2—1—0|||||||||123456789x1x2x1+2x28(0,4)(8,0)目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x204x1164x212图解法可行域步骤一：由全部约束条件作图求出可行域；上页下页返回9—8—7—6—5—4—3—2—1—0|||||||||123456789x1x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20x1+2x284x1164x212可行域BCDEA图解法B上页下页返回9—8—7—6—5—4—3—2—1—0x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20|||||||||123456789x1x1+2x284x1164x212BCDEA2x1+3x2=6图解法步骤二：作目标函数等值线，确定使目标函数最优的移动方向；上页下页返回9—8—7—6—5—4—3—2—1—0x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20|||||||||123456789x1x1+2x284x1164x212BCDEA图解法x1+2x2=84x1=16MaxZ=14最优解(4,2)步骤三：平移目标函数的等值线，找出最优点，算出最优值。上页下页返回图解法求解步骤•由全部约束条件作图求出可行域；•作目标函数等值线，确定使目标函数最优的移动方向；•平移目标函数的等值线，找出最优点，算出最优值。上页下页返回9—8—7—6—5—4—3—2—1—0x2|||||||||123456789x1BCDEA最优解(4,2)改变约束条件或目标函数，解的结果如何？线性规划问题求解的几种可能结果(a)唯一最优解上页下页返回9—8—7—6—5—4—3—2—1—0x2|||||||||123456789x1BCDEA线性规划问题求解的几种可能结果x1+2x2=8目标函数MaxZ=x1+2x2约束条件x1+2x284x1164x212x1、x20(b)无穷多最优解上页下页返回(c)无界解MaxZ=x1+x2-2x1+x24x1-x22x1、x20x2x1线性规划问题求解的几种可能结果上页下页返回(d)无可行解MaxZ=2x1+3x2x1+2x284x1164x212-2x1+x24x1、x20可行域为空集线性规划问题求解的几种可能结果上页下页返回图解法的几点结论:（由图解法得到的启示）–可行域是有界或无界的凸多边形。–若线性规划问题存在最优解，它一定可以在可行域的顶点得到。–若两个顶点同时得到最优解，则其连线上的所有点都是最优解。–解题思路：找出凸集的顶点，计算其目标函数值，比较即得。上页下页返回练习：用图解法求解LP问题MaxZ=15x1+25x2x1+3x260x1+x240x1、x20上页下页返回maxz=15x1+25x2s.t.x1+3x2≤60x1+x2≤40x1，x2≥012360xx1240xxL1Z=250目标函数变形：x2=-3/5x1+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≤4x1，x2≥0习题3maxz=2x1+2x2s.t.x1+x2≥1x1–3x2≥–3x1≤3x1，x2≥0习题4maxz=5x1+3x2s.t.x1+x2≤1x1+2x2≥4x1，x2≥0上页下页返回1222xx1244xxOx1x2Note:可行域为无界区域，目标函数值可无限增大，即解无界。称为无最优解。A(1,0)可行域为无界区域一定无最优解吗？maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4x1，x2≥0习题：用图解法求下列线性规划:上页下页返回0x1x2121xx3321xx13xA(1,0)minZ(多解)线段AD上的任一点都是最优解minZ=2习题3maxz=2x1+2x2s.t.x1+x2≥1x1–3x2≥–3x1≤3x1，x2≥0(30,10)B(3,0)C(3,2)D(0,1)若minZ换为maxZ则最优解为?点上页下页返回0x1x2121xx1224xxA(1,0)(30,10)B(4,0)D(0,1)习题4maxz=5x1+3x2s.t.x1+x2≤1x1+2x2≥4x1，x2≥0C(0,2)无可行解上页下页返回根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况1.可行域为封闭的有界区域(a)有唯一的最优解；(b)有无穷多个最优解；2.可行域为非封闭的无界区域(c)有唯一的最优解；(d)有无穷多个最优解；(e)目标函数无界(即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少)，因而没有有限最优解。3.可行域为空集(f)没有可行解，原问题无最优解上页下页返回二、线性规划解的有关概念可行解、最优解基、基变量、非基变量基本解、基本可行解可行基、最优基继续返回上页下页返回Ax=b，x≥0；1.可行解与最优解上页下页返回极点定义1设集合是n维欧氏空间中的一个点集，如果及实数(1)(2)(1)xxSnSR(1)(2)xxS、0,1都有则称S是一个凸集。几何意义：如果集合中任意两点连线上的一切点都在该集合中，则称该集合为凸集。凸集上页下页返回定义2设则称()1,0,1,2,,,1kiniiixRik且，(1)(2)()12kkxxxx为点的一个凸组合。(1)(2)()kxxx，，，定义3设凸集两点表示为则称x为S的一个极点（或顶点）。,,nSRxSxS如果不能用中不同的(1)(2)xx，(1)(2)(1)(01)xxx定理LP问题的可行解集,0DxAxbx是凸集。上页下页返回ＬＰ的可行域以及最优解有以下性质: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+2500x2s.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+2500x2s.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是线性规划的一个基(或基矩阵)。mnC当m=n时，基矩阵惟一，当mn时，基矩阵就可能有多个，但数目不超过。mnC行满秩的矩阵上页下页返回111121,,,mmmmmaaBpppaa基：基向量：基B中的列pj(j=1,2,…,m);基变量：与基向量对应的决策变量xj(j=1,2,…,m)；非基变量：与非基向量对应的决策变量xj(j=m+1,…,n)非基向量：A中除基向量外，其余的列pj(j=m+1,…,n);（1）线性规划的基1212,,...,,,,TnjjjmjAppppaaaAj，为的第列向量;任取A中的m个线性无关列向量构成矩阵B，则B是A的一个基；上页下页返回12102-101A【解】约束方程的系数矩阵为2×4矩阵上页下页返回112,2-1B211,20B310,21B