线性规划问题的图解法

1、线性规划问题的求解方法线性规划问题的求解方法一一 般般 有有两种方法两种方法图图 解解 法法单纯形法单纯形法两个变量、直角坐标两个变量、直角坐标三个变量、立体坐标三个变量、立体坐标适用于任意变量、但必需将适用于任意变量、但必需将一般形式变成标准形式一般形式变成标准形式下面我们分析一下简单的情况下面我们分析一下简单的情况 只有两个决策只有两个决策变量的线性规划问题，这时可以通过图解的方法变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。探线性规划基本原理和几何意义等优点。为凸集。K），

2、则10（，KX ）1（X连线上的一切点KX，KX对维欧氏空间的一点集，n是k设）2（）1（）2（）1（凸集凸集凹集凹集 顶点顶点: 若若K是凸集，是凸集，XK；若若X不能用不同不能用不同的两点的线性组合表示为：的两点的线性组合表示为： 则则X为顶点为顶点. KXKX)2()1(和) 10( )1 ()2()1 (XXX 凸组合凸组合： .,.,., 1,.,2, 1, 10,.,.,)()1()()2(21111)()1的凸组合为则使且若存在个点维向量空间中的是设（kkkkiiikkXXXXXXXkiknXXX n=2，k=3标准型标准型可行解可行解: :满足满足AX=b, X=0AX=b,

3、X=0的解的解X X称为线性规划问题的称为线性规划问题的可行解。所有可行解的集合称为可行解。所有可行解的集合称为可行域可行域。最优解最优解：使：使Z=CXZ=CX达到最大值的可行解称为最优解。达到最大值的可行解称为最优解。等值线：等值线：目标函数为常数的光滑连续曲线。目标函数为常数的光滑连续曲线。 min 0ZCXAXbX9 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

4、169 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可行域可行域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可行域可行域BCDEA9 8 7 6 5 4 3 2 1 0 x2目标

5、函数目标函数 Max Z = 2x1 + 3x2 约束条件约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0 0|123456789x1x1 + 2x2 84x1 164 x2 16BCDEA9 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 16BCDEAmax Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8s.t. X1 + 1.

6、9X2 11.4 X1 - 1.9X2 -3.8 X1 ，X2 0例例1 用图解法求解线性规划问题用图解法求解线性规划问题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

7、 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8s.t. X1 + 1.9X2 11.4 X1 - 1.9X2 -3.8 X1 ，X2 0min 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）可行域可行域此点是唯一最优解此点是唯一最优解max Z=3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8(

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是唯一的。是唯一的。可行域可行域 006346321212121xxxxxxxx、246x1x2246无界解无界解( (无最优解无最优解) )max Z=x1+2x2例例1.6x1+x2=4()x1+3x2=6()3x1+x2=6() max Z min Zx1x2O1020304010

9、2030405050无可行解无可行解(即无最优解即无最优解)0,050305.140221212121 xxxxxxxxmax Z=3x1+4x2例例1.7小结小结 学习要点：学习要点：1. 通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）（唯一最优解；无穷多最优解；无界解；无可行解）2. 作图的关键有三点：作图的关键有三点： (1) 可行解区域要画正确可行解区域要画正确 (2) 目标函数增加的方向不能画错目标函数增加的方向不能画错 (3) 目标函数的直线怎样平行移动目标函数的直线怎样平行移动n可行域是有界或无界的凸多边形。

10、可行域是有界或无界的凸多边形。n若线性规划问题存在最优解，它一定可以在可若线性规划问题存在最优解，它一定可以在可行域的顶点得到。行域的顶点得到。n若两个顶点同时得到最优解，则其连线上的所若两个顶点同时得到最优解，则其连线上的所有点都是最优解。有点都是最优解。n解题思路：找出凸集的顶点，计算其目标函数解题思路：找出凸集的顶点，计算其目标函数值，比较即得。值，比较即得。练习：练习：设设yxz2式中变量式中变量 满足下列条件满足下列条件yx,1255334xyxyxxyO 求求 的最大值和最小值的最大值和最小值z2x+y=01255334xyxyx练习：练习：设设yxz2式中变量式中变量 满足下列条

11、件满足下列条件yx,1255334xyxyxx-4y+3=03x+5y-25=0 x=1xyO 求求 的最大值和最小值的最大值和最小值z2x+y=00l1ll2lA(5,2)B(1,1)312minmaxzz1255334xyxyx定理定理1：若线性规划问题存在可行解，则该问题的可行域是：若线性规划问题存在可行解，则该问题的可行域是凸集。凸集。定理定理3：若问题存在最优解，一定存在一个基可行解是最优：若问题存在最优解，一定存在一个基可行解是最优解。（或在某个顶点取得）解。（或在某个顶点取得）单纯形表单纯形表jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im

12、1mnmmnmaaaa1,11, 110010 0 ijijjacc j 0 kjkjiiaab其其中中：例例1.8 用单纯形法求下列线性规划的最优解用单纯形法求下列线性规划的最优解 0,30340243max21212121xxxxxxxxZ解：解：1）将问题化为标准型，加入松驰变量将问题化为标准型，加入松驰变量x3、x4则标准型为则标准型为: 0,30340243max432142132121xxxxxxxxxxxxZ2）求出线性规划的初始基可行解，列出初始单纯形表。）求出线性规划的初始基可行解，列出初始单纯形表。cj3400icB基基bx1x2x3x40 x34021100 x43013

13、0134003) 1020(3)(2141131acacc1检验数检验数j 3）进行最优性检验）进行最优性检验如果表中所有检验数如果表中所有检验数 ，则表中的基可行解就是问题，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。的最优解，计算停止。否则继续下一步。0 j4）从一个基可行解转换到另一个目标值更大的基可行解，）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表列出新的单纯形表确定换入基的变量。选择确定换入基的变量。选择 ，对应的变量，对应的变量xj作为换入变作为换入变量，当有一个以上检验数大于量，当有一个以上检验数大于0时，一般选择最大的一个时，一般选择最大的

14、一个检验数，即：检验数，即： ，其对应的，其对应的xk作为换入作为换入变量。变量。确定换出变量。根据下式计算并选择确定换出变量。根据下式计算并选择 ，选最小的选最小的对应基对应基变量作为换出变量。变量作为换出变量。0 j0|max jjk 0minikikiLaab用换入变量用换入变量xk替换基变量中的换出变量，得到一个新的基。替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。一个新的单纯形表。5）重复）重复3）、）、4）步直到计算结束为止。）步直到计算结束为止。cj3400icB基

15、变量基变量bx1x2x3x40 x34021100 x430130134000 x34x23x14x2j j j 换入列换入列bi /ai2，ai204010换换出出行行将将3化为化为15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011例例1.9 用单纯形法求解用单纯形法求解 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：将数学模型化为标准形式：解：将数学模型化为标准形式： 5 , 2 , 1, 02053115232.2max53214321321jxxxxxx

16、xxxtsxxxZj不难看出不难看出x4、x5可作为初始基变量，列单纯形表计算。可作为初始基变量，列单纯形表计算。cj12100icB基变量基变量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x2j 201/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9 -1/9 -7/3j 学习要点：学习要点：1. 线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2. 熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤人工变量法：人工变量法：前

17、面讨论了在标准型中系数矩阵有单位矩阵，很容易前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大的变量称为人工变量，构成的可行基称为人工基，用大MM法或两阶段法求解，这种用人工变量作桥梁的求解方法称法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量

18、法。为人工变量法。例例1.10 用大用大M法解下列线性规划法解下列线性规划 012210243423max321321321321321xxxxxxxxxxxxxxxZ、解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式 5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型： 7 , 2 , 1, 012210243423

19、max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj其中：其中：M是一个很大的抽象的数，不需要给出具体的数值，是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。 cj32-100-M-MCBXBbx1x2x3x4x5x6x7i0 x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M-M0 x63-650-1013/5-Mx58

20、-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/3j j j j 解的判别：解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零）唯一最优解判别：最优表中所有非基变量的检验数非零,则线则线 规划具有唯一最优解。规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优

21、解（或无穷多最优解）。则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个）无界解判别：某个k0且且aik（i=1，2,m）则线性）则线性规划具有无界解。规划具有无界解。4）无可行解的判断：当用大）无可行解的判断：当用大M单纯形法计算得到最优解并单纯形法计算得到最优解并且存在且存在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。）退化解的判别：存在某个基变量为零的基本可行解。单纯性法小结单纯性法小结:建建立立模模型型个个 数数取取 值值右右 端端 项项等式或等式或不等式不等式极大或极小极大或极小新加变量新加变量系

22、数系数两两个个三个三个以上以上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停止停止A Ajjjzc :求求0 j所所有有kj即即找找出出max)()0(0 jika对对任任一一)0( lklkiiaab 计计算算lkxx替替换换基基变变量量用用非非

23、基基变变量量新新单单纯纯形形表表列列出出下下一一个个ax含有含有量中是否量中是否基变基变 0 j非非基基变变量量的的有有某某个个最最优优解解一一唯唯 无无可可行行解解最优解最优解无穷多无穷多是是否否环环循循否否否否否否是是是是是是循环循环无无界界解解一般而言，一个经济、管理问题凡是满足以下条一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。件时，才能建立线性规划模型。 要求解问题的目标函数能用数值指标来反映，且要求解问题的目标函数能用数值指标来反映，且为线性函数为线性函数 存在着多种方案存在着多种方案 要求达到的目标是在一定条件下实现的，这些约要求达到的目标是在一定条件下实

24、现的，这些约束可用线性等式或不等式描述束可用线性等式或不等式描述1. 人力资源分配问题人力资源分配问题例例1.11 某昼夜服务的公交线路每天各时间段内某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：所需司机和乘务人员人数如下表所示：班次班次时间时间所需人员所需人员16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满小时，问该公

25、交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少足工作需要，又使配备司机和乘务人员的人数减少?解：设解：设xi表示第表示第i班次时开始上班的司机和乘务人员人数。班次时开始上班的司机和乘务人员人数。 0,302050607060.min654321655443322161654321xxxxxxxxxxxxxxxxxxtsxxxxxx此问题最优解：此问题最优解：x150， x220， x350， x40， x520， x610，一共需要司机和乘务员，一共需要司机和乘务员150人。人。2. 生产计划问题生产计划问题某厂生产某厂生产、三种产品，都分别经三种产品，都分

26、别经A、B两道工序加工。设两道工序加工。设A工序可分别在设备工序可分别在设备A1和和A2上完上完成，有成，有B1、B2、B3三种设备可用于完成三种设备可用于完成B工序。已工序。已知产品知产品可在可在A、B任何一种设备上加工；产品任何一种设备上加工；产品可可在任何规格的在任何规格的A设备上加工，但完成设备上加工，但完成B工序时，只能工序时，只能在在B1设备上加工；产品设备上加工；产品只能在只能在A2与与B2设备上加工。设备上加工。加工单位产品所需工序时间及其他各项数据如下表，加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。试安排最优生产计划，使该厂获利最大。设备

27、设备产品产品设备有效设备有效台时台时设备加工费设备加工费（单位小时）（单位小时）27910 000321B168124000250B247000783B37114000200原料费（每件）原料费（每件）0.250.350.5售价（每件）售价（每件）1.252.002.8解：设解：设xijk表示产品表示产品i在工序在工序j的设备的设备k上加工的数量。约束条上加工的数量。约束条件有：件有：）（上加工的数量相等）上加工的数量相等），在工序在工序（产品（产品上加工的数量相等）上加工的数量相等），在工序在工序（产品（产品上加工的数量相等）上加工的数量相等），在工序在工序（产品（

28、产品设备设备设备设备）（设备（设备）（设备（设备设备设备3 , 2 , 1; 2 , 1; 3 , 2 , 10BAIIIBAIIBAI)3B(40007)2B(70001141B4000862A100001297)1A(6000105322312221212211123122121112111123322122221121312212112211111 kjixxxxxxxxxxxxxxxxxxxxxijk目标是利润最大化，即利润的计算公式如下：目标是利润最大化，即利润的计算公式如下： 5131)()(ii该该设设备备实实际际使使用用台台时时每每台台时时的的设设备备费费用用该该产产品品件件数数销销售售单单价价原原料料单单价价利利润润带入数据整理得到：带入数据整理得到：12332212222112131221221111211135. 023. 1448. 05 . 0375. 0915. 136. 115. 1775. 075. 0maxxxxxxxxxxx 因此该规划问题的模型为：因此该规划问题的模型为： ）（3,2,1;2,1;3,2,104000770001144000861000012976000105.35.023.1448