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