线性规划问题的图解法课件.ppt

线性规划问题的图解法线性规划问题的图解法第1页，此课件共50页哦第2页，此课件共50页哦凸集凸集凹集凹集第3页，此课件共50页哦 顶点顶点:若若K是凸集，是凸集，XK；若若X不能用不同的不能用不同的两点的线性组合表示为：两点的线性组合表示为：则则X为顶点为顶点.第4页，此课件共50页哦 凸组合凸组合：X n=2，k=3第5页，此课件共50页哦标准型标准型可行解可行解:满足满足AX=b,X=0的解的解X称为线性规划问题的可称为线性规划问题的可行解。所有可行解的集合称为行解。所有可行解的集合称为可行域可行域。最优解最优解：使：使Z=CX达到最大值的可行解称为最优解。达到最大值的可行解称为最优解。等值线：等值线：目标函数为常数的光滑连续曲线。目标函数为常数的光滑连续曲线。第6页，此课件共50页哦9 8 7 6 5 4 3 2 1 0|123456789x1x2x1+2x2 8(0,4)(8,0)目标函数目标函数 Max Z=2x1+3x2 约束条件约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0 04x1 164 x2 16v图解法图解法第7页，此课件共50页哦9 8 7 6 5 4 3 2 1 0 x2 目标函数目标函数 Max Z=2x1+3x2 约束条件约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0 0|123456789x1x1+2x2 84x1 164 x2 12可行域可行域v图解法图解法第8页，此课件共50页哦9 8 7 6 5 4 3 2 1 0|123456789x1x2 目标函数目标函数 Max Z=2x1+3x2 约束条件约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0 0 x1+2x2 84x1 164 x2 16可行域可行域BCDEAv图解法图解法第9页，此课件共50页哦9 8 7 6 5 4 3 2 1 0 x2 目标函数目标函数 Max Z=2x1+3x2 约束条件约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0 0|123456789x1x1+2x2 84x1 164 x2 16BCDEA2x1+3x2=6v图解法图解法第10页，此课件共50页哦9 8 7 6 5 4 3 2 1 0 x2 目标函数目标函数 Max Z=2x1+3x2 约束条件约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0 0|123456789x1x1+2x2 84x1 164 x2 16BCDEA最优解最优解(4,2)v图解法图解法第11页，此课件共50页哦图解法求解步骤图解法求解步骤1.由全部约束条件作图求出可行域；2.作目标函数等值线，确定使目标函数最优的移动方向；3.平移目标函数的等值线，找出最优点，算出最优值。第12页，此课件共50页哦图解法图解法max Z=2X1+X2 X1+1.9X2 3.8 X1 -1.9X2 3.8s.t.X1+1.9X2 11.4 X1 -1.9X2 -3.8 X1 ，X2 0例例1 用图解法求解线性规划问题用图解法求解线性规划问题第13页，此课件共50页哦图解法图解法-唯一最优解唯一最优解 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）Dmax Zmin Z此点是唯一最优解，且最优目标函数值 max Z=17.2可行域可行域max Z=2X1+X2 X1+1.9X2 3.8 X1 -1.9X2 3.8s.t.X1+1.9X2 11.4 X1 -1.9X2 -3.8 X1 ，X2 0第14页，此课件共50页哦图解法图解法-唯一最优解唯一最优解 min Z=5X1+4X2x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1+1.9X2=11.4()DL0：0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2（0，2）可行域可行域此点是唯一最优解第15页，此课件共50页哦图解法图解法-无穷多最优解无穷多最优解max Z=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 max Z（3.8，4）34.2=3X1+5.7X2 蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值max Z=34.2是唯一的。可行域可行域第16页，此课件共50页哦图解法图解法-无界解246x1x2246无界解无界解(无最优解无最优解)max Z=x1+2x2例例1.6x1+x2=4()x1+3x2=6()3x1+x2=6()max Z min Z第17页，此课件共50页哦x1x2O10203040102030405050无可行解无可行解(即无最优解即无最优解)max Z=3x1+4x2例例1.7图解法图解法-无可行解无可行解第18页，此课件共50页哦小结小结 第19页，此课件共50页哦图解法图解法学习要点：学习要点：1.通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）（唯一最优解；无穷多最优解；无界解；无可行解）2.作图的关键有三点：作图的关键有三点：(1)可行解区域要画正确可行解区域要画正确(2)目标函数增加的方向不能画错目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动目标函数的直线怎样平行移动第20页，此课件共50页哦n n可行域是有界或无界的凸多边形。可行域是有界或无界的凸多边形。可行域是有界或无界的凸多边形。可行域是有界或无界的凸多边形。n n若线性规划问题存在最优解，它一定可以在可若线性规划问题存在最优解，它一定可以在可若线性规划问题存在最优解，它一定可以在可若线性规划问题存在最优解，它一定可以在可行域的顶点得到。行域的顶点得到。行域的顶点得到。行域的顶点得到。n n若两个顶点同时得到最优解，则其连线上的所若两个顶点同时得到最优解，则其连线上的所若两个顶点同时得到最优解，则其连线上的所若两个顶点同时得到最优解，则其连线上的所有点都是最优解。有点都是最优解。有点都是最优解。有点都是最优解。n n解题思路：找出凸集的顶点，计算其目标函数解题思路：找出凸集的顶点，计算其目标函数解题思路：找出凸集的顶点，计算其目标函数解题思路：找出凸集的顶点，计算其目标函数值，比较即得。值，比较即得。值，比较即得。值，比较即得。第21页，此课件共50页哦练习：练习：设设式中变量式中变量 满足下列条件满足下列条件xyO 求求 的最大值和最小值的最大值和最小值2x+y=0第22页，此课件共50页哦练习：练习：设设式中变量式中变量 满足下列条件满足下列条件x-4y+3=03x+5y-25=0 x=1xyO 求求 的最大值和最小值的最大值和最小值2x+y=0A(5,2)B(1,1)第23页，此课件共50页哦单纯形法基本原理单纯形法基本原理定理定理1：若线性规划问题存在可行解，则该问题的可行域是凸集。：若线性规划问题存在可行解，则该问题的可行域是凸集。定理定理定理定理2 2：线性规划问题的基可行解：线性规划问题的基可行解：线性规划问题的基可行解：线性规划问题的基可行解X X对应可行域对应可行域对应可行域对应可行域(凸集凸集凸集凸集)的顶点。的顶点。的顶点。的顶点。定理定理3：若问题存在最优解，一定存在一个基可行解是最优解。：若问题存在最优解，一定存在一个基可行解是最优解。（或在某个顶点取得）（或在某个顶点取得）第24页，此课件共50页哦单纯形法的计算步骤单纯形法的计算步骤单纯形法的思路单纯形法的思路单纯形法的思路单纯形法的思路找出一个初始可行解找出一个初始可行解找出一个初始可行解找出一个初始可行解是否最优是否最优是否最优是否最优转移到另一个基本可行解转移到另一个基本可行解转移到另一个基本可行解转移到另一个基本可行解（找出更大的目标函数值）（找出更大的目标函数值）（找出更大的目标函数值）（找出更大的目标函数值）最优解最优解最优解最优解是是是是否否否否循循循循环环环环核心是：变量迭代核心是：变量迭代核心是：变量迭代核心是：变量迭代结束结束结束结束第25页，此课件共50页哦单纯形法的计算步骤单纯形法的计算步骤单纯形表单纯形表第26页，此课件共50页哦单纯形法的计算步骤单纯形法的计算步骤例例1.8 用单纯形法求下列线性规划的最优解用单纯形法求下列线性规划的最优解解：解：1）将问题化为标准型，加入松驰变量将问题化为标准型，加入松驰变量x3、x4则标准型为则标准型为:第27页，此课件共50页哦单纯形法的计算步骤单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。）求出线性规划的初始基可行解，列出初始单纯形表。cj3400icB基bx1x2x3x40 x34021100 x43013013400检验数检验数第28页，此课件共50页哦单纯形法的计算步骤单纯形法的计算步骤3）进行最优性检验）进行最优性检验如果表中所有检验数如果表中所有检验数 ，则表中的基可行解就是问题的，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。最优解，计算停止。否则继续下一步。4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表纯形表确定换入基的变量。选择确定换入基的变量。选择 ，对应的变量，对应的变量xj作为换入变量，作为换入变量，当有一个以上检验数大于当有一个以上检验数大于0时，一般选择最大的一个检验数，即：时，一般选择最大的一个检验数，即：，其对应的，其对应的xk作为换入变量。作为换入变量。确定换出变量。根据下式计算并选择确定换出变量。根据下式计算并选择，选最小的选最小的对应基变量作对应基变量作为换出变量。为换出变量。第29页，此课件共50页哦单纯形法的计算步骤单纯形法的计算步骤用换入变量用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。5）重复）重复3）、）、4）步直到计算结束为止。）步直到计算结束为止。第30页，此课件共50页哦单纯形法的计算步骤单纯形法的计算步骤cj3400icB基变量bx1x2x3x40 x34021100 x430130134000 x34x23x14x2换入列bi/ai2，ai204010换出行将3化为15/311801/301/31011/3303005/304/3乘以1/3后得到103/51/518011/52/540011第31页，此课件共50页哦单纯形法的计算步骤单纯形法的计算步骤例例1.9 用单纯形法求解用单纯形法求解解：将数学模型化为标准形式：解：将数学模型化为标准形式：不难看出不难看出x4、x5可作为初始基变量，列单纯形表计算。可作为初始基变量，列单纯形表计算。第32页，此课件共50页哦单纯形法的计算步骤单纯形法的计算步骤cj12100icB基变量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x220 x x2 22 21/3150120753017131/309022560 x x1 111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第33页，此课件共50页哦单纯形法的计算步骤单纯形法的计算步骤学习要点：学习要点：1.线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2.熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤第34页，此课件共50页哦单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法人工变量法：人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大的变量称为人工变量，构成的可行基称为人工基，用大MM法或两阶段法求解，这种用人工变量作桥梁的求解方法称法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。为人工变量法。第35页，此课件共50页哦单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法例例1.10 用大用大M法解下列线性规划法解下列线性规划解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。第36页，此课件共50页哦单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型：其其中中：M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理理解解为为它它能能大大于于给给定定的的任任何何一一个个确确定定数数值值；再再用用前前面面介介绍绍的的单单纯纯形法求解该模型，计算结果见下表。形法求解该模型，计算结果见下表。第37页，此课件共50页哦单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i0 x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M-M0 x63-650-1013/5-Mx58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/50-Mx531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3第38页，此课件共50页哦单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法解的判别：解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零）唯一最优解判别：最优表中所有非基变量的检验数非零,则线则线 规划具有唯一最优解。规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零）多重最优解判别：最优表中存在非基变量的检验数为零,则线则则线则性规划具有多重最优解（或无穷多最优解）。性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个）无界解判别：某个k0且且aik（i=1，2,m）则线性规划具有）则线性规划具有无界解。无界解。4）无无可可行行解解的的判判断断：当当用用大大M单单纯纯形形法法计计算算得得到到最最优优解解并并且且存存在在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。）退化解的判别：存在某个基变量为零的基本可行解。第39页，此课件共50页哦单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法单纯性法小结单纯性法小结:建立模型个 数取 值右 端 项等式或不等式极大或极小新加变量系数两个三个以上xj0 xj无约束xj 0 bi 0bi 0=maxZminZxs xa求解图解法、单纯形法单纯形法不处理令xj=xj-xj xj 0 xj 0令 xj=-xj不处理约束条件两端同乘以-1加松弛变量xs加入人工变量xa减去xs加入xa不处理令z=-ZminZ=max z0-M第40页，此课件共50页哦A A第41页，此课件共50页哦 线性规划模型的应用线性规划模型的应用一般而言，一个经济、管理问题凡是满足以下条一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。件时，才能建立线性规划模型。要求解问题的目标函数能用数值指标来反映，且为线性函要求解问题的目标函数能用数值指标来反映，且为线性函数数 存在着多种方案存在着多种方案 要求达到的目标是在一定条件下实现的，这些约束可用要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述线性等式或不等式描述第42页，此课件共50页哦 线性规划在管理中的应用线性规划在管理中的应用1.人力资源分配问题人力资源分配问题例例1.11 某昼夜服务的公交线路每天各时间段内所需司某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：机和乘务人员人数如下表所示：班次时间所需人员16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少使配备司机和乘务人员的人数减少?第43页，此课件共50页哦 线性规划在管理中的应用线性规划在管理中的应用解：设解：设xi表示第表示第i班次时开始上班的司机和乘务人员人数。班次时开始上班的司机和乘务人员人数。此问题最优解：此问题最优解：x150，x220，x350，x40，x520，x610，一共需要司机和乘务员，一共需要司机和乘务员150人。人。第44页，此课件共50页哦 线性规划在管理中的应用线性规划在管理中的应用2.生产计划问题生产计划问题某厂生产某厂生产、三种产品，都分别经三种产品，都分别经A、B两道工两道工序加工。设序加工。设A工序可分别在设备工序可分别在设备A1和和A2上完成，有上完成，有B1、B2、B3三种设备可用于完成三种设备可用于完成B工序。已知产品工序。已知产品可在可在A、B任何一种设备上加工；产品任何一种设备上加工；产品可在任何规格的可在任何规格的A设备上加设备上加工，但完成工，但完成B工序时，只能在工序时，只能在B1设备上加工；产品设备上加工；产品只能只能在在A2与与B2设备上加工。加工单位产品所需工序时间及设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂其他各项数据如下表，试安排最优生产计划，使该厂获利最大。获利最大。第45页，此课件共50页哦 线性规划在管理中的应用线性规划在管理中的应用设备产品设备有效台时设备加工费（单位小时）A15106000300A27910 000321B168124000250B247000783B37114000200原料费（每件）0.250.350.5售价（每件）1.252.002.8第46页，此课件共50页哦 线性规划在管理中的应用线性规划在管理中的应用解：设解：设xijk表示产品表示产品i在工序在工序j的设备的设备k上加工的数量。约束条上加工的数量。约束条件有：件有：第47页，此课件共50页哦 线性规划在管理中的应用线性规划在管理中的应用目标是利润最大化，即利润的计算公式如下：目标是利润最大化，即利润的计算公式如下：带入数据整理得到：带入数据整理得到：第48页，此课件共50页哦 线性规划在管理中的应用线性规划在管理中的应用因此该规划问题的模型为：因此该规划问题的模型为：第49页，此课件共50页哦 线性规划在管理中的应用线性规划在管理中的应用3.套裁下料问题套裁下料问题例：现有一批某种型号的圆钢长例：现有一批某种型号的圆钢长8米，需要截取米，需要截取2.5米长的毛米长的毛坯坯100根，长根，长1.3米的毛坯米的毛坯200根。问如何才能既满足需要，根。问如何才能既满足需要，又能使总的用料最少？又能使总的用料最少？解：为了找到一个省料的套裁方案，必须先设计出较好的几个解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格的圆下料方案。其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出此可以设计出4种下料方案以供套裁用。种下料方案以供套裁用。2.5m32101.3m0246料头00.40.30.2第50页，此课件共50页哦