线性规划问题的图解法

线性规划问题的图解法第1页，共50页，2023年，2月20日，星期二线性规划问题的几何意义第2页，共50页，2023年，2月20日，星期二凸集凹集第3页，共50页，2023年，2月20日，星期二

顶点:若K是凸集，X∈K；若X不能用不同的两点的线性组合表示为：

则X为顶点.

线性规划问题的几何意义第4页，共50页，2023年，2月20日，星期二

凸组合：

Xn=2，k=3线性规划问题的几何意义第5页，共50页，2023年，2月20日，星期二标准型可行解:满足AX=b,X>=0的解X称为线性规划问题的可行解。所有可行解的集合称为可行域。最优解：使Z=CX达到最大值的可行解称为最优解。等值线：目标函数为常数的光滑连续曲线。第6页，共50页，2023年，2月20日，星期二9—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

84x1

164x2

12x1、x2

04x1

164x2

16图解法第7页，共50页，2023年，2月20日，星期二9—8—7—6—5—4—3—2—1—0x2

目标函数MaxZ=2x1+3x2

约束条件x1+2x2

84x1

164x2

12x1、x2

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

84x1

164x2

12可行域图解法第8页，共50页，2023年，2月20日，星期二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

16可行域BCDEA图解法第9页，共50页，2023年，2月20日，星期二9—8—7—6—5—4—3—2—1—0x2

目标函数MaxZ=2x1+3x2

约束条件x1+2x2

84x1

164x2

12x1、x2

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

84x1

164x2

16BCDEA2x1+3x2=6图解法第10页，共50页，2023年，2月20日，星期二9—8—7—6—5—4—3—2—1—0x2

目标函数MaxZ=2x1+3x2

约束条件x1+2x2

84x1

164x2

12x1、x2

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

84x1

164x2

16BCDEA最优解(4,2)图解法第11页，共50页，2023年，2月20日，星期二图解法求解步骤1.由全部约束条件作图求出可行域；2.作目标函数等值线，确定使目标函数最优的移动方向；3.平移目标函数的等值线，找出最优点，算出最优值。第12页，共50页，2023年，2月20日，星期二图解法maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤11.4X1-1.9X2≥-3.8X1，X2≥0例1用图解法求解线性规划问题第13页，共50页，2023年，2月20日，星期二图解法---唯一最优解

x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=11.4(≤)4=2X1+X2

20=2X1+X2

17.2=2X1+X2

11=2X1+X2

Lo：0=2X1+X2

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

maxZ=17.2可行域maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤11.4X1-1.9X2≥-3.8X1，X2≥0第14页，共50页，2023年，2月20日，星期二图解法---唯一最优解

minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1+1.9X2=11.4(≤)DL0：0=5X1+4X2

maxZminZ8=5X1+4X2

43=5X1+4X2

（0，2）可行域此点是唯一最优解第15页，共50页，2023年，2月20日，星期二图解法---无穷多最优解maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=11.4(≤)（7.6，2）DL0：0=3X1+5.7X2

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

蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值maxZ=34.2是唯一的。可行域第16页，共50页，2023年，2月20日，星期二图解法---无界解246x1x2246无界解(无最优解)maxZ=x1+2x2例1.6x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ第17页，共50页，2023年，2月20日，星期二x1x2O10203040102030405050无可行解(即无最优解)maxZ=3x1+4x2例1.7图解法---无可行解第18页，共50页，2023年，2月20日，星期二小结

第19页，共50页，2023年，2月20日，星期二图解法

学习要点：

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

2.作图的关键有三点：

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

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

(3)目标函数的直线怎样平行移动第20页，共50页，2023年，2月20日，星期二图解法的几点结论:

（由图解法得到的启示）可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函数值，比较即得。第21页，共50页，2023年，2月20日，星期二练习：设式中变量满足下列条件①xyO求的最大值和最小值2x+y=0第22页，共50页，2023年，2月20日，星期二练习：设式中变量满足下列条件①x-4y+3=03x+5y-25=0x=1xyO求的最大值和最小值2x+y=0A(5,2)B(1,1)第23页，共50页，2023年，2月20日，星期二单纯形法基本原理定理1：若线性规划问题存在可行解，则该问题的可行域是凸集。定理2：线性规划问题的基可行解X对应可行域(凸集)的顶点。定理3：若问题存在最优解，一定存在一个基可行解是最优解。（或在某个顶点取得）第24页，共50页，2023年，2月20日，星期二单纯形法的计算步骤单纯形法的思路找出一个初始可行解是否最优转移到另一个基本可行解（找出更大的目标函数值）最优解是否循环核心是：变量迭代结束第25页，共50页，2023年，2月20日，星期二单纯形法的计算步骤单纯形表第26页，共50页，2023年，2月20日，星期二单纯形法的计算步骤例1.8用单纯形法求下列线性规划的最优解解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:第27页，共50页，2023年，2月20日，星期二单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。cj3400θicB基bx1x2x3x40x34021100x43013013400检验数第28页，共50页，2023年，2月20日，星期二单纯形法的计算步骤3）进行最优性检验如果表中所有检验数，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表确定换入基的变量。选择，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：，其对应的xk作为换入变量。确定换出变量。根据下式计算并选择θ

，选最小的θ对应基变量作为换出变量。 第29页，共50页，2023年，2月20日，星期二单纯形法的计算步骤用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。5）重复3）、4）步直到计算结束为止。 第30页，共50页，2023年，2月20日，星期二单纯形法的计算步骤cj3400θicB基变量bx1x2x3x40x34021100x430130134000x34x23x14x2换入列bi/ai2，ai2>04010换出行将3化为15/311801/301/3101－1/3303005/30－4/3乘以1/3后得到103/5－1/51801－1/52/5400－1－1第31页，共50页，2023年，2月20日，星期二单纯形法的计算步骤例1.9用单纯形法求解解：将数学模型化为标准形式：不难看出x4、x5可作为初始基变量，列单纯形表计算。第32页，共50页，2023年，2月20日，星期二单纯形法的计算步骤cj12100θicB基变量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第33页，共50页，2023年，2月20日，星期二单纯形法的计算步骤

学习要点：

1.线性规划解的概念以及3个基本定理

2.熟练掌握单纯形法的解题思路及求解步骤第34页，共50页，2023年，2月20日，星期二单纯形法的进一步讨论－人工变量法人工变量法： 前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。第35页，共50页，2023年，2月20日，星期二单纯形法的进一步讨论－人工变量法例1.10用大M法解下列线性规划解：首先将数学模型化为标准形式系数矩阵中不存在单位矩阵，无法建立初始单纯形表。第36页，共50页，2023年，2月20日，星期二单纯形法的进一步讨论－人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。第37页，共50页，2023年，2月20日，星期二单纯形法的进一步讨论－人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7θi0x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M↑-M0x63-650-1013/5-Mx58-3300108/3-1x312-21000——5-6M5M↑0-M002x23/5－6/510－1/50——-Mx531/53/5003/5131/3-1x311/5－2/501－2/50——5↑00002x213010123x131/310015/3-1x319/300102/3000-5-25/3→→→第38页，共50页，2023年，2月20日，星期二单纯形法的进一步讨论－人工变量法

解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个λk>0且aik≤０（i=1，2,…,m）则线性规划具有无界解。4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri>0时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。第39页，共50页，2023年，2月20日，星期二单纯形法的进一步讨论－人工变量法单纯性法小结:建立模型个数取值右端项等式或不等式极大或极小新加变量系数两个三个以上xj≥0xj无约束xj≤0

bi

≥0bi<0≤=≥maxZminZxs

xa求解图解法、单纯形法单纯形法不处理令xj=

xj′

-xj″

xj′

≥0xj″

≥0令

xj’

=-xj不处理约束条件两端同乘以-1加松弛变量xs加入人工变量xa减去xs加入xa不处理令z′=-ZminZ=－maxz′0-M第40页，共50页，2023年，2月20日，星期二A第41页，共50页，2023年，2月20日，星期二

线性规划模型的应用

一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。

要求解问题的目标函数能用数值指标来反映，且为线性函数存在着多种方案要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述第42页，共50页，2023年，2月20日，星期二

线性规划在管理中的应用

人力资源分配问题例1.11某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：班次时间所需人员16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少?第43页，共50页，2023年，2月20日，星期二

线性规划在管理中的应用解：设xi表示第i班次时开始上班的司机和乘务人员人数。此问题最优解：x1＝50，x2＝20，x3＝50，x4＝0，x5＝20，x6＝10，一共需要司机和乘务员150人。第44页，共50页，2023年，2月20日，星期二

线性规划在管理中的应用2.