线性规划单纯形法-课件

线性规划单纯形法线性规划单纯形法单单纯纯形形法法的的计计算算步步骤骤例例1.8 用单纯形法求下列线性规划的最优解用单纯形法求下列线性规划的最优解解：解：1）将问题化为标准型，加入松驰变量）将问题化为标准型，加入松驰变量x3、x4、x5则标准则标准型为型为:单单纯纯形形法法的的计计算算步步骤骤2）求出线性规划的初始基可行解，）求出线性规划的初始基可行解，列出初始单纯形表。列出初始单纯形表。cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x51204001323000Z=0检验数检验数单单纯纯形形法法的的计计算算步步骤骤3）进行最优性检验）进行最优性检验如果表中所有检验数如果表中所有检验数 ，则表中的基可行解就是问题，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。的最优解，计算停止。否则继续下一步。4）从一个基可行解转换到另一个目标值更大的基可行解，）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表列出新的单纯形表确定换入基的变量。选择确定换入基的变量。选择 ，对应的变量，对应的变量xj作为换入作为换入变量，当有一个以上检验数大于变量，当有一个以上检验数大于0时，一般选择最大的一个时，一般选择最大的一个检验数，即：检验数，即：，其对应的，其对应的xk作为换作为换入变量。入变量。确定换出变量。根据下式计算并选择确定换出变量。根据下式计算并选择，选最小的选最小的对应基对应基变量作为换出变量。变量作为换出变量。单单纯纯形形法法的的计计算算步步骤骤用换入变量用换入变量xk替换基变量中的换出变量，得到一个新的基。替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。一个新的单纯形表。5）重复）重复3）、）、4）步直到计算结束为止。）步直到计算结束为止。单单纯纯形形法法的的计计算算步步骤骤（表（表1-3）cj23000icB基变量基变量bx1x2x3x4x50 x38121000 x416400100 x5120400123000Z=0表表1-40 x320 x4163x23换入列换入列bi/ai2，ai2043换换出出行行将将4化为化为1，本列，本列的其他值化为的其他值化为010201/4011/21003/404001000第一步：将第三行除以第一步：将第三行除以4第二步：将第一行减去第三行乘以第二步：将第一行减去第三行乘以2大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点单单纯纯形形法法的的计计算算步步骤骤（表（表1-4）Cj23000icB基变量基变量bx1x2x3x4x50 x321010-1/20 x416400100 x2301001/42000-3/4Z=9表表1-52x120 x43x23换入列换入列bi/ai2，ai20换换出出行行10001/4011/210-21/4000-41200将将4化为化为0第一步：将第二行减去第一行乘以第一步：将第二行减去第一行乘以4248单单纯纯形形法法的的计计算算步步骤骤（表（表1-5）Cj23000icB基变量基变量bx1x2x3x4x50 x121010-1/20 x4800-4120 x2301001/400-201/4Z=13表表1-62x10 x53x2换入列换入列换换出出行行1001/2000010-3/20-1/800-21/211/4将将2化为化为1，本列的其他值化为，本列的其他值化为0第一步：将第二行除以第一步：将第二行除以244第二步：将第一行加上第二行乘以第二步：将第一行加上第二行乘以1/2第三步：将第三行减去第二行乘以第三步：将第三行减去第二行乘以1/442-1/8单单纯纯形形法法的的计计算算步步骤骤 表表1-6中所有的中所有的 都小于或者等于都小于或者等于0，表明已经达到了最，表明已经达到了最优解，因此，现行的基本可行解优解，因此，现行的基本可行解X=（4，2，0，0，4）T是是最优解，最优解，Z=14是该线性规划的最优值。是该线性规划的最优值。单单纯纯形形法法的的计计算算步步骤骤例例1.9 用单纯形法求解用单纯形法求解解：将数学模型化为标准形式：解：将数学模型化为标准形式：不难看出不难看出x4、x5可作为初始基变量，列单纯形表计算。可作为初始基变量，列单纯形表计算。单单纯纯形形法法的的计计算算步步骤骤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单单纯纯形形法法的的计计算算步步骤骤 表表1-6中所有的中所有的 都小于或者等于都小于或者等于0，表明已经达到了最，表明已经达到了最优解，因此，现行的基本可行解优解，因此，现行的基本可行解X=（25，35/3，0，0，0）T是最优解，是最优解，Z=95/3是该线性规划的最优值。是该线性规划的最优值。单单纯纯形形法法的的计计算算步步骤骤学习要点：学习要点：1.线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2.熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤单单纯纯形形法法的的进进一一步步讨讨论论人人工工变变量量法法人工变量法：人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大的变量称为人工变量，构成的可行基称为人工基，用大M M法法或两阶段法求解，这种用人工变量作桥梁的求解方法称为或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。人工变量法。单单纯纯形形法法的的进进一一步步讨讨论论人人工工变变量量法法例例1.10 用大用大M法解下列线性规划法解下列线性规划解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。单单纯纯形形法法的的进进一一步步讨讨论论人人工工变变量量法法故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型：其其中中：M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理理解解为为它它能能大大于于给给定定的的任任何何一一个个确确定定数数值值；再再用用前前面面介介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。单单纯纯形形法法的的进进一一步步讨讨论论人人工工变变量量法法cj3-1-100-M-MCBXBbx1x2x3x4x5x6x7i0 x4111-21100011-Mx63-4120-1103/2-Mx71-201000113-6M-1+M-1+3M0-M000 x4103-20101-1-Mx610100-11-21-1x31-20100011-1+M00-M01-3M0 x4123001-22-54-1x210100-11-2-1x32010001 1 000-1-M+1-M-13x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3000-1/3-1/3-M+1/3-M+2/3单单纯纯形形法法的的总总结结解的判别：解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非）唯一最优解判别：最优表中所有非基变量的检验数非零零,则线则线 规划具有唯一最优解。规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为）多重最优解判别：最优表中存在非基变量的检验数为零零,则线则性规划具有多重最优解（或无穷多最优解）。则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个）无界解判别：某个 0且且aij（i=1，2,m）则线）则线性规性规 划具有无界解。划具有无界解。4）无可行解的判断：当用大）无可行解的判断：当用大M单纯形法计算得到最优解单纯形法计算得到最优解并且存在并且存在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。）退化解的判别：存在某个基变量为零的基本可行解。单单纯纯形形法法小小结结建建立立模模型型决策变决策变量个量个 数数取取 值值右右 端端 项项等式或等式或不等式不等式极大或极小极大或极小新加变新加变量系数量系数 求求解解不不处处理理图图解解法法、单单纯纯形形法法xj0 xj无无约约束束令令xj=xj-xj xj 0 xj 0 xj 0令令 xj=-xj xj 0 bi 0不不处处理理不不处处理理bi 0约束约束条件条件两端两端同乘同乘以以-1=加加松松弛弛变变量量xs加加入入人人工工变变量量xa减减去去xs,加加入入xamaxZminZ令令z=-ZminZ=max zxs0 xa-M两两个个三个三个以上以上单单纯纯形形法法单单纯纯形形法法的的计计算算步步骤骤单纯形表单纯形表 线线性性规规划划模模型型的的应应用用一般而言，一个经济、管理问题凡是满足以下条一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。件时，才能建立线性规划模型。要求解问题的目标函数能用数值指标来反映，且要求解问题的目标函数能用数值指标来反映，且为线性函数为线性函数 存在着多种方案存在着多种方案 要求达到的目标是在一定条件下实现的，这些约要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述束可用线性等式或不等式描述 线线性性规规划划在在管管理理中中的的应应用用1.人力资源分配问题人力资源分配问题例例1.11 某昼夜服务的公交线路每天各时间段内某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：所需司机和乘务人员人数如下表所示：班次班次时间时间所需人员所需人员16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少足工作需要，又使配备司机和乘务人员的人数减少?线线性性规规划划在在管管理理中中的的应应用用解：设解：设xi表示第表示第i班次时开始上班的司机和乘务人员人数。班次时开始上班的司机和乘务人员人数。此问题最优解：此问题最优解：x150，x220，x350，x40，x520，x610，一共需要司机和乘务员，一共需要司机和乘务员150人。人。线线性性规规划划在在管管理理中中的的应应用用2.生产计划问题生产计划问题某厂生产某厂生产、三种产品，都分别经三种产品，都分别经A、B两两道工序加工。设道工序加工。设A工序可分别在设备工序可分别在设备A1和和A2上完成，上完成，有有B1、B2、B3三种设备可用于完成三种设备可用于完成B工序。已知产工序。已知产品品可在可在A、B任何一种设备上加工；产品任何一种设备上加工；产品可在任何可在任何规格的规格的A设备上加工，但完成设备上加工，但完成B工序时，只能在工序时，只能在B1设设备上加工；产品备上加工；产品只能在只能在A2与与B2设备上加工。加工设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。安排最优生产计划，使该厂获利最大。线线性性规规划划在在管管理理中中的的应应用用设备设备产品产品设备有效设备有效台时台时设备加工费设备加工费（单位小时）（单位小时）A151060003.00A2791210 0003.21B16840002.50B241170007.83B3740002.00原料费（每件）原料费（每件）0.250.350.5售价（每件）售价（每件）1.252.002.8 线线性性规规划划在在管管理理中中的的应应用用解：设解：设xijk表示产品表示产品i在工序在工序j的设备的设备k上加工的数量。约束条上加工的数量。约束条件有：件有：线线性性规规划划在在管管理理中中的的应应用用目标是利润最大化，即利润的计算公式如下：目标是利润最大化，即利润的计算公式如下：带入数据整理得到：带入数据整理得到：线线性性规规划划在在管管理理中中的的应应用用因此该规划问题的模型为：因此该规划问题的模型为：线线性性规规划划在在管管理理中中的的应应用用3.套裁下料问题套裁下料问题例：现有一批某种型号的圆钢长例：现有一批某种型号的圆钢长8米，需要截取米，需要截取2.5米米长的毛坯长的毛坯100根，长根，长1.3米的毛坯米的毛坯200根。问如何才能根。问如何才能既满足需要，又能使总的用料最少？既满足需要，又能使总的用料最少？解：为了找到一个省料的套裁方案，必须先设计出较好的几解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格个下料方案。其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出的，为此可以设计出4种下料方案以供套裁用。种下料方案以供套裁用。2.5m32101.3m0246料头料头0.500.30.2 线线性性规规划划在在管管理理中中的的应应用用设按方案设按方案、下料的原材料根数分别为下料的原材料根数分别为xj(j=1，2,3,4)，可列出下面的数学模型：，可列出下面的数学模型：线线性性规规划划在在管管理理中中的的应应用用3.多周期动态生产计划问题多周期动态生产计划问题 华华津津机机器器制制造造厂厂专专为为拖拖拉拉机机厂厂配配套套生生产产柴柴油油机机。今今年年头头四四个个月月收收到到的的订订单单数数量量分分别别为为3000，4500，3500，5000台台柴柴油油机机。该该厂厂正正常常生生产产每每月月可可生生产产柴柴油油机机3000台台，利利用用加加班班还还可可生生产产1500台台。正正常常生生产产成成本本为为每每台台5000元元，加加班班生生产产还还要要追追加加1500元元成成本本，库库存存成成本本为为每每台台每每月月200元元。华华津津厂如何组织生产才能使生产成本最低。厂如何组织生产才能使生产成本最低。线线性性规规划划在在管管理理中中的的应应用用决策变量：决策变量：xi 为第为第 i月正常生产的柴油机数；月正常生产的柴油机数；yi 为第为第 i月加班生产的柴油机数；月加班生产的柴油机数；zi 为第为第 i月初柴油机的库存数。月初柴油机的库存数。线线性性规规划划在在管管理理中中的的应应用用 数学模型如下：min z=5000(x1+x2+x3+x4)+6500(y1+y2+y3+y4)+200(z2+z3+z4)s.t.x1+y1 -z2 =3000 x2+y2+z2-z3=4500 x3+y3+z3-z4=3500 x4+y4+z4 =5000 0 xi 3000 i=1,2,3,4 0 yi 1500 i=1,2,3,4 zi 0 i=1,2,3,4 线线性性规规划划在在管管理理中中的的应应用用 线线性性规规划划在在管管理理中中的的应应用用5.证券投资组合优化证券投资组合优化 某人有一笔某人有一笔50万元的资金可用于长期投资，可供选择的万元的资金可用于长期投资，可供选择的投资机会包括购买国库卷、债卷、房地产、股票或银行储蓄投资机会包括购买国库卷、债卷、房地产、股票或银行储蓄等。他希望投资组合的平均年限不超过等。他希望投资组合的平均年限不超过5年，平均的期望收年，平均的期望收益率不低于益率不低于13%，风险系数不超过，风险系数不超过4，收益的增长潜力不低，收益的增长潜力不低于于10%。在满足上述要求的前提。在满足上述要求的前提应应如何选择投资组合如何选择投资组合才能才能使使平均收益率最高。平均收益率最高。线线性性规规划划在在管管理理中中的的应应用用 投资 投资期 年收益 风险 增长潜 方式 限(年)率()系数 力()国库卷 3 11 1 0 债卷 10 15 3 15 房地产 6 25 8 30 股票 2 20 6 20 短期存款 1 10 1 5 长期存款 5 12 2 10 现金存款 0 3 0 0 线线性性规规划划在在管管理理中中的的应应用用决策变量：各种投资方式站总投资的比例；决策变量：各种投资方式站总投资的比例；目标函数：平均投资收益最大目标函数：平均投资收益最大；约束方程：满足各种指标要求：约束方程：满足各种指标要求：1、平均投资年限不超过、平均投资年限不超过5年年 2、平均的期望收益率不低于平均的期望收益率不低于13%3、风险系数不超过风险系数不超过4 4、收益的增长潜力不低于收益的增长潜力不低于15%线线性性规规划划在在管管理理中中的的应应用用证券组合优化模型证券组合优化模型max z=11x1+15x2+25x3+20 x4+10 x5+12x6+3x7 s.t.3x1+10 x2+6x3+2x4+x5+5x6 5 11x1+15x2+25x3+20 x4+10 x5+12x6+3x7 13 x1+3x2+8x3+6x4+x5+2x6 4 15x2+30 x3+20 x4+5x5+10 x6 10 x1 +x2 +x3 +x4+x5 +x6+x7=1 x1,x2,x3,x4,x5,x6,x7 0 线线性性规规划划在在管管理理中中的的应应用用 线线性性规规划划在在管管理理中中的的应应用用6.生产库存计划问题生产库存计划问题例：例：企业根据预测知道上半年市场对该企企业根据预测知道上半年市场对该企业产品的需求变化较大（见下表）：业产品的需求变化较大（见下表）：月份月份 1 2 3 4 5 6 需求需求 6000 2500 5000 3500 5500 6000企业目前有企业目前有100名工人，每人每月可生产名工人，每人每月可生产40件件产品，工人平均工资每月产品，工人平均工资每月800元，企业可元，企业可以通过以下方法调节生产：以通过以下方法调节生产：线线性性规规划划在在管管理理中中的的应应用用利用加班：加班需付加倍工资，每人每月利用加班生产的产品不能超过10件。利用库存：每件产品库存费用为10元/月。临时增聘或解雇工人：新聘工人培训费为1000元，解雇工人的解聘费为600元。每月新聘工人数量不能超过10人。企业目前有库存500件，希望六月底的库存不低于700件，其他月份应保持不少于 200件的安全库存，企业应如何组织生产。线线性性规规划划在在管管理理中中的的应应用用变量设置：变量设置：xi：第：第 i 月在岗的工人数；月在岗的工人数；yi：第：第 i 月新聘的工人数；月新聘的工人数；zi：第：第 i 月解聘的工人数；月解聘的工人数；ki：产品在第：产品在第 i 月期末的库存数量；月期末的库存数量；ui：第：第 i 月正常生产的产品数量；月正常生产的产品数量；vi：第：第 i 月加班生产的产品数量；月加班生产的产品数量；线线性性规规划划在在管管理理中中的的应应用用目标函数：生产和库存费用最小目标函数：生产和库存费用最小min i(800 xi+1000yi+600zi+10ki)线线性性规规划划在在管管理理中中的的应应用用约束条件：约束条件：1)每月在岗工人的平衡约束每月在岗工人的平衡约束 x1-x0-y1+z1=0 x2-x1-y2+z2=0 x3-x2-y3+z3=0 x4-x3-y4+z4=0 x5-x4-y5+z5=0 x6-x5-y6+z6=0 线线性性规规划划在在管管理理中中的的应应用用2）每月生产的平衡约束）每月生产的平衡约束 ui+vi+ki-1-ki di i=1,6 u1+v1+k0-k1 5500 u2+v2+k1-k2 3200 u3+v3+k2-k3 6700 u4+v4+k3-k4 4300 u5+v5+k4-k5 6400 u6+v6+k5-k6 7500 线线性性规规划划在在管管理理中中的的应应用用3）正常生产限制约束：）正常生产限制约束：ui 40 xi i=1,6u1 40 x1 u2 40 x2u3 40 x3 u4 40 x4u5 40 x5u6 40 x6 线线性性规规划划在在管管理理中中的的应应用用4）加班生产限制约束：）加班生产限制约束：vi 10 xi i=1,6v1 10 x1 v2 10 x2 v3 10 x3 v4 10 x4 v5 10 x5 v6 10 x6 线线性性规规划划在在管管理理中中的的应应用用5）变量的界约束和非负约束：）变量的界约束和非负约束：安全库存约束：ki 200 i=2,5 k0=500,k6 700新聘人数约束：yi 10 i=1,6在岗初始人数：x0=100变量非负约束：xi,yi,zi,ki,ui 0 i=1,6；