21-线性规划方法应用的典型情况22-线性规划问题及其数课件

2.1线性规划方法应用的典型情况2.2线性规划问题及其数学模型2.3简单最大化问题的图解法求解2.4简单最小化问题的图解法求解2.5图解法的特殊情况2.6线性规划模型及图解法得到的启示2.7使用计算机软件求解LP问题第2章线性规划模型和图解法基本概念（1）可行解：满足约束条件的决策变量的取值（2）可行域：可行解的全体（3）最优解：使目标函数取得最优值的可行解（4）最优值：最优解代入目标函数所得到的值（5）凸集：如果集合C中任意两点连线上所有的点都是集合C中的点，该集合为凸集上周内容回顾图解法求解步骤1.由全部约束条件作图求出可行域；2.作目标函数等值线，确定使目标函数最优的移动方向；3.平移目标函数的等值线，找出最优点，算出最优值。解的情况可归结如下

唯一解无穷多解无有限最优解无可行解有最优解无最优解线性规划的几何意义

1）当线性规划问题的可行解域非空时，它是有界或无界凸多边形。

2）若线性规划问题存在最优解，它一定在可行域的某个顶点得到。

3）若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。

第3章线性规划模型的单纯形法3.1线性规划数学模型的结构及特征3.2线性规划模型的标准形式3.3基、基本解、基本可行解3.4单纯形表的数学原理3.5从一个基本可行解转化为相邻的基本可行解3.6最优性检验和解的判别3.7单纯形表法3.8人工变量法和两阶段法3.9计算机软件QM求解线性规划模型的一般形式为3.2.2一般形式的线性规划模型变换为标准形式线性规划模型的标准形式为1.目标函数为求极小值，即为：

因为求minz等价于求max(-z)，令z’=-z，即转换为：①约束方程为在“≤”左端加入一个非负松弛变量，把原“≤”的不等式变为等式。2.约束条件为不等式，②约束方程为在“≥”左端减去一个非负剩余变量，把原“≥”的不等式变为等式。３.右端项bi<0时，只需将等式两端同乘（-1），则右端项必大于零

4.决策变量无非负约束,设xj没有非负约束，若xj≤0，可令xj=-xj’，则xj’≥0；若xj为自由变量，即xj可为任意实数，可令xj=xj’-xj’’，且xj’,xj’’≥05.决策变量xj有上界或者下界，即xj≥u或者xj≤v若xj≥u，可令xj’=xj-u，xj’≥0；若xj≤v，可令xj’=v-xj，xj’≥0；【例3-2】将下面的线性规划问题化为标准型：

将下面的线性规划问题化为标准型：（2）对于“”约束9x+3y

360，引入松弛变量x1，得到（3）对于“”约束3x+10y300，引入剩余变量

x2，得到解（1）对目标函数，令则（4）对于y

无非负约束，令y＝y(1)-y(2)，且y(1)

0，y(2)0.（5）统一变量，令x=x3，y(1)=x4，y(2)=x5，得到该线性规划问题的标准形式：3.3基、基本解、基本可行解3.3.1基、基本解、基本可行解的定义基：若B是矩阵A中m×n阶非奇异子矩阵（），则

B是线性规划问题的一个基。基向量：Ｂ中的每一个列向量（j=1，2，…,m）基变量：与基向量对应的变量，用XB表示。非基变量：线性规划模型的决策变量中除基变量以外的变量，用XN表示。基解：设B为某一个基，A=（B,N),则有BXB+NXN=b

令XN=0，则得一个满足AX=b式的解这个解称为基解。基可行解：若为一个基解，且则得到一个满足AX=b、X≥0的可行解，称为基可行解。可行基：对应基可行解的基称为可行基。注意两点：B在A中是任意取的。故A中有很多基B。基变量是针对B而言的，不同B，其对应的基变量和非基变量是不同的。3.3.2基本解和基本可行解的计算与几何解释通过【例3-3】说明线性规划模型的基、对应的基本解、基本可行解。将模型化为标准型：X2、X3、X5不能构成B的一组基变量。X1、X3、X4不能构成B的一组基变量。基基变量基解X=(x1,x2,x3,x4,x5)T是否可行对应点Z值B1x1,x2,x3X=(4,3,-2,0,0)T不可行D—B2x1,x2,x4X=(2,3,0,8,0)T可行C13B3x1,x2,x5X=(4,2,0,0,4)T可行E14B5x1,x3,x5X=(4,0,4,0,12)T可行G8B6x1,x4,x5X=(8,0,0,-16,12)T不可行F—B7x2,x3,x4X=(0,3,2,6,0)T可行A9B9x2,x4,x5X=(0,4,0,16,-4)T不可行B—B10x3,x4,x5X=(0,0,8,16,12)T可行O0该模型所对应的基、基本解、基本可行解，如下表：x1(0,0)(2,3)(0,3)(0,4)(4,3)(4,0)(4,2)(8,0)9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

16可行域ABCDOEFG约束条件的交点有8个，基本解就有8个；可行域顶点有5个：基可行解就有5个：：（0，0）、（0，3）、(2,3)、（4，2）和（4，0），其中E为最优解。该模型所对应的基、基本解、基本可行解，如下图：可行解：满足约束条件AX=b与X0的解X基本解：对于某一特定的基B，非基变量取0值的解，即基本可行解：满足非负约束条件的基础解，即最优解：满足目标函数MaxZ=CX的可行解X基本最优解：满足目标函数MaxZ=CX的基本可行解X3.3.3线性规划模型解之间的关系基本解可行解最优解基本最优解基本可行解基最优基可行基

线性规划模型解、基的关系图定义1：如果集合C中任意两个点X1、X2，其连线上所有点都是集合C中的点，那么称C为凸集。即:则称为C凸集。定义2：凸集C中满足下述条件的点X称为顶点；如果C中不存在任何两个不同的点X1、X2，使X成为这两个点连线上的一个点。即对于任何，不存在，则称X是凸集C的顶点。3.4单纯形表的数学原理定理1：若线性规划问题存在可行解域，则其可行解域是凸集。定理2：线性规划问题的可行解

为基可行解的充要条件是，X的正分量所对应的系数列向量是线性无关。定理3：线性规划问题的基可行解X对应于可行域

D的顶点。定理4：一个标准的线性规划模型，如果有可行解，则至少有一个基本可行解定理5：一个标准的线性规划模型，如果有有限的最优值，则一定存在一个基本可行解是最优解由上述线性规划的基本定理，得以下结论：线性规划问题的可行解域是凸集；基可行解是可行域的顶点，可行域的顶点即是基可行解，因此，每个基可行解对应可行域的一个顶点；3.可行解域的顶点个数是有限的，不超过