线性规划(单纯形法)

1、Page 1Page 2单纯形表单纯形表jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 110010 0 ijijjacc j 0 kjkjiiaab其其中中：Page 3例例1.8 用单纯形法求下列线性规划的最优解用单纯形法求下列线性规划的最优解 0,1241648232max21212121xxxxxxxxZ解：解：1）将问题化为标准型，加入松驰变量将问题化为标准型，加入松驰变量x3、x4、 x5则标准则标准型为型为: 0,1241648200043max54321524132154321xxxxxxxxxxxxxx

2、xxxZPage 42）求出线性规划的初始基可行解，）求出线性规划的初始基可行解，列出初始单纯形表。列出初始单纯形表。11311421531()2(0 1 0 40 0)2cc ac ac a cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x51204001323000Z=0检验数检验数j 3) 400020(3)(32522412322 acacacc 2) 004010(2)(31521411311 acacacc Page 53）进行最优性检验）进行最优性检验如果表中所有检验数如果表中所有检验数 ，则表中的基可行解就是问题，则表中的基可行

3、解就是问题的最优解，计算停止。否则继续下一步。的最优解，计算停止。否则继续下一步。0 j4）从一个基可行解转换到另一个目标值更大的基可行解，）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表列出新的单纯形表确定换入基的变量。选择确定换入基的变量。选择 ，对应的变量，对应的变量xj作为换入变作为换入变量，当有一个以上检验数大于量，当有一个以上检验数大于0时，一般选择最大的一个时，一般选择最大的一个检验数，即：检验数，即： ，其对应的，其对应的xk作为换入作为换入变量。变量。确定换出变量。根据下式计算并选择确定换出变量。根据下式计算并选择 ，选最小的选最小的对应基对应基变量作为换出

4、变量。变量作为换出变量。0 j0|max jjk 0minikikiLaabPage 6用换入变量用换入变量xk替换基变量中的换出变量，得到一个新的基。替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。一个新的单纯形表。5）重复）重复3）、）、4）步直到计算结束为止。）步直到计算结束为止。Page 7j 换入列换入列bi /ai2，ai2043换换出出行行将将4化为化为1，本列，本列的其他值化为的其他值化为010201/4011/21003/4j 04001000第一步：将第三行除以

5、第一步：将第三行除以4第二步：将第一行减去第三行乘以第二步：将第一行减去第三行乘以2Page 8j 换入列换入列bi /ai2，ai20换换出出行行10001/4011/210-21/4j 000-41200将将4化为化为0第一步：将第二行减去第一行乘以第一步：将第二行减去第一行乘以4248Page 9j 换入列换入列换换出出行行1001/2000010-3/20j -1/800-21/211/4将将2化为化为1，本列的其他值化为，本列的其他值化为0第一步：将第二行除以第一步：将第二行除以244第二步：将第一行加上第二行乘以第二步：将第一行加上第二行乘以1/2第三步：将第三行减去第二行乘以第三

6、步：将第三行减去第二行乘以1/442-1/8Page 10 表表1-6中所有的中所有的 都小于或者等于都小于或者等于0，表明已经达到了最，表明已经达到了最优解，因此，现行的基本可行解优解，因此，现行的基本可行解X=（4，2，0，0，4）T是是最优解，最优解，Z=14是该线性规划的最优值。是该线性规划的最优值。jPage 11例例1.9 用单纯形法求解用单纯形法求解 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：将数学模型化为标准形式：解：将数学模型化为标准形式： 5 , 2 , 1, 02053115232.2max53214321321jxxxx

7、xxxxxtsxxxZj不难看出不难看出x4、x5可作为初始基变量，列单纯形表计算。可作为初始基变量，列单纯形表计算。Page 12j 201/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9 -1/9 -7/3j Page 13 表表1-6中所有的中所有的 都小于或者等于都小于或者等于0，表明已经达到了最，表明已经达到了最优解，因此，现行的基本可行解优解，因此，现行的基本可行解X=（25，35 /3，0，0，0）T是最优解，是最优解，Z=95/3是该线性规划的最优值。是该线性规划的最优值。jPage 14学习要

8、点：学习要点：1. 线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2. 熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤Page 15人工变量法：人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人

9、工变量，构成的可行基称为人工基，用大加的变量称为人工变量，构成的可行基称为人工基，用大MM法或两阶段法求解，这种用人工变量作桥梁的求解方法法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。称为人工变量法。Page 16例例1.10 用大用大M法解下列线性规划法解下列线性规划 0123241123max32131321321321xxxxxxxxxxxxxxZ、解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式 5 , 2 , 1, 012324112003max315321432154321jxxxxxxxxxxxxxxxxZj系数矩阵中不存在系数矩阵中不存在单位矩阵，

10、无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。Page 17故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型： 7 , 2 , 1, 0121024112003max7316532143217654321jxxxxxxxxxxxxxMxMxxxxxxZj其中：其中：M是一个很大的抽象的数，不需要给出具体的数值，是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见

11、下表。 Page 18j j j j Page 19解的判别：解的判别：j 1）唯一最优解判别）唯一最优解判别：最优表中所有非基变量的检验数非：最优表中所有非基变量的检验数非零零,则线则线 规划具有唯一最优解。规划具有唯一最优解。2）多重最优解判别）多重最优解判别：最优表中存在非基变量的检验数为：最优表中存在非基变量的检验数为零零,则线则性规划具有多重最优解（或无穷多最优解）。则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别）无界解判别：某个：某个 0且且aij（i=1，2,m）则线）则线性规性规 划具有无界解。划具有无界解。4）无可行解的判断）无可行解的判断：当用大：当用大M单纯

12、形法计算得到最优解单纯形法计算得到最优解并且存在并且存在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别）退化解的判别：存在某个基变量为零的基本可行解。：存在某个基变量为零的基本可行解。Page 20不不处处理理图图解解法、法、单单纯纯形形法法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

13、 zxs0 xa-M两两个个三个三个以上以上单单纯纯形形法法jmiijjacc 1: 求求0 j 所所有有kj即即找找出出max)()0(0 jika对对任任一一)0( lklkiiaab 计计算算lkxx替替换换基基变变量量用用非非基基变变量量新新单单纯纯形形表表列列出出下下一一个个ax含有含有量中是否量中是否基变基变 0 j非非基基变变量量的的有有某某个个最最优优解解一一唯唯 无无可可行行解解最优解最优解无穷多无穷多是是否否环环循循否否否否否否是是是是是是循环循环无无界界解解列列出出初初始始单单纯纯形形表表找找出出基基变变量量Page 22单纯形表单纯形表jcnmmcccc11BcBXbm

14、cc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 110010 0 ijijjacc j 0 kjkjiiaab其其中中：Page 23一般而言，一个经济、管理问题凡是满足以一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。下条件时，才能建立线性规划模型。 要求解问题的目标函数能用数值指标来反映，且要求解问题的目标函数能用数值指标来反映，且为线性函数为线性函数 存在着多种方案存在着多种方案 要求达到的目标是在一定条件下实现的，这些约要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述束可用线性等式或不等式描述Page 2

15、4 人力资源分配问题人力资源分配问题例例1.11 某昼夜服务的公交线路每天各时间段内某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：所需司机和乘务人员人数如下表所示：班次班次时间时间所需人员所需人员16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘

16、务人员的人数减少足工作需要，又使配备司机和乘务人员的人数减少?Page 25解：设解：设xi表示第表示第i班次时开始上班的司机和乘务人员人数。班次时开始上班的司机和乘务人员人数。 0,302050607060.min654321655443322161654321xxxxxxxxxxxxxxxxxxtsxxxxxx此问题最优解：此问题最优解：x150， x220， x350， x40， x520， x610，一共需要司机和乘务员，一共需要司机和乘务员150人。人。Page 262. 生产计划问题生产计划问题某厂生产某厂生产、三种产品，都分别经三种产品，都分别经A、B两道工序加工。设两道工序加工

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

18、ijk表示产品表示产品i在工序在工序j的设备的设备k上加工的数量。约束条上加工的数量。约束条件有：件有：）（上加工的数量相等）上加工的数量相等），在工序在工序（产品（产品上加工的数量相等）上加工的数量相等），在工序在工序（产品（产品上加工的数量相等）上加工的数量相等），在工序在工序（产品（产品设备设备设备设备）（设备（设备）（设备（设备设备设备3 , 2 , 1; 2 , 1; 3 , 2 , 10BAIIIBAIIBAI)3B(40007)2B(70001141B4000862A100001297)1A(60001053223122212122111231221211121111233221

19、22221121312212112211111 kjixxxxxxxxxxxxxxxxxxxxxijkPage 29目标是利润最大化，即利润的计算公式如下：目标是利润最大化，即利润的计算公式如下： 5131)()(ii该该设设备备实实际际使使用用台台时时每每台台时时的的设设备备费费用用该该产产品品件件数数销销售售单单价价原原料料单单价价利利润润带入数据整理得到：带入数据整理得到：12332212222112131221221111211135. 023. 1448. 05 . 0375. 0915. 136. 115. 1775. 075. 0maxxxxxxxxxxx Page 30因此该规

20、划问题的模型为：因此该规划问题的模型为： ）（3,2,1;2,1;3,2,104000770001144000861000012976000105.35.023.1448.05.0375.0915.136.115.1775.075.0max322312221212211123122121112111123322122221121312212112211111123322122221121312212211112111kjixxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxxijkPage 313. 套裁下料问题套裁下料问题例：现有一批某种型号的圆钢长例：现有一批某种型号的圆钢长8

21、米，需要截取米，需要截取2.5米米长的毛坯长的毛坯100根，长根，长1.3米的毛坯米的毛坯200根。问如何才能根。问如何才能既满足需要，又能使总的用料最少？既满足需要，又能使总的用料最少？解：为了找到一个省料的套裁方案，必须先设计出较好的几解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格个下料方案。其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出的，为此可以设计出4种下料方案以供套裁用。种下料方案以供套裁用。Page 32 )

22、4.3.2.1(020064210023min4323214321jxxxxxxxxxxxZj设按方案设按方案、下料的原材料根数分别为下料的原材料根数分别为xj (j=1，2,3,4)，可列出下面的数学模型：，可列出下面的数学模型：Page 33 华津机器制造厂专为拖拉机厂配套生产柴油机。今年头华津机器制造厂专为拖拉机厂配套生产柴油机。今年头四个月收到的订单数量分别为四个月收到的订单数量分别为3000，4500，3500，5000台台柴油机。该厂正常生产每月可生产柴油机柴油机。该厂正常生产每月可生产柴油机3000台，利用加台，利用加班还可生产班还可生产1500台。正常生产成本为每台台。正常生产

23、成本为每台5000元，加班生元，加班生产还要追加产还要追加1500元成本，库存成本为每台每月元成本，库存成本为每台每月200元。华津元。华津厂如何组织生产才能使生产成本最低。厂如何组织生产才能使生产成本最低。Page 34决策变量：决策变量：xi 为第为第 i月正常生产的柴油机数月正常生产的柴油机数；yi 为第为第 i月加班生产的柴油机数月加班生产的柴油机数；zi 为第为第 i月初柴油机的库存数。月初柴油机的库存数。Page 35 数学模型如下：数学模型如下： min z = 5000(x1+x2+x3+x4)+6500(y1+y2+y3+y4) +200(z2+z3+z4) s.t. x1

24、+ 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 Page 36Page 375. 证券投资组合优化证券投资组合优化 某人有一笔某人有一笔50万元的资金可用于长期投资，可供选择的万元的资金可用于长期投资，可供选择的投资机会包括购买国库卷、债卷、房地产、股票或银行储蓄投资机会包括购买国库卷、债卷、房地产、股票或银行储蓄

25、等。他希望投资组合的平均年限不超过等。他希望投资组合的平均年限不超过5年，平均的期望收年，平均的期望收益率不低于益率不低于13%，风险系数不超过，风险系数不超过4，收益的增长潜力不低，收益的增长潜力不低于于10%。在满足上述要求的前提应如何选择投资组合才能使。在满足上述要求的前提应如何选择投资组合才能使平均收益率最高。平均收益率最高。Page 38 投资 投资期 年收益 风险 增长潜 方式 限(年) 率() 系数 力() 国库卷 3 11 1 0 债卷 10 15 3 15 房地产 6 25 8 30 股票 2 20 6 20 短期存款 1 10 1 5 长期存款 5 12 2 10 现金存款

26、 0 3 0 0Page 39决策变量决策变量：各种投资方式站总投资的比例；：各种投资方式站总投资的比例；目标函数目标函数：平均投资收益最大：平均投资收益最大 ；约束方程约束方程：满足各种指标要求：满足各种指标要求： 1、平均投资年限不超过、平均投资年限不超过5年年 2、平均的期望收益率不低于平均的期望收益率不低于13% 3、风险系数不超过、风险系数不超过4 4、收益的增长潜力不低于收益的增长潜力不低于15%Page 40max z = 11x1+15x2+25x3+20 x4+10 x5+12x6+3x7 s.t. 3x1+10 x2+ 6x3+ 2x4+ x5 + 5x6 5 11x1+1

27、5x2+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 Page 41证券投资模型证券投资模型年限年限 收益率收益率 风险系数风险系数增长潜力增长潜力 投入比例投入比例国库券国库券3 311111 10 00.48840.488424.4224.42债券债券101015153 315150.11630.11635

28、.8145.814房地产房地产6 625258 830300.39530.395319.7719.77股票股票2 220206 620200 00 0短期存款短期存款1 110101 15 50 00 0长期存款长期存款5 512122 210100 00 0活期储蓄活期储蓄0 03 30 00 00 00 0平均值平均值5 517174 413.6046513.604651 15050希望值希望值5 513134 410101 15050Page 42企业根据预测知道上半年市场对该企企业根据预测知道上半年市场对该企业产品的需求变化较大（见下表）：业产品的需求变化较大（见下表）： 月份月份 1

29、 2 3 4 5 6 需求需求 6000 2500 5000 3500 5500 6000企业目前有企业目前有100名工人，每人每月可生产名工人，每人每月可生产40件件产品，工人平均工资每月产品，工人平均工资每月800元，企业可元，企业可以通过以下方法调节生产：以通过以下方法调节生产： Page 43利用加班：加班需付加倍工资，每人每月利用加班生产的产品不能超过10件。利用库存：每件产品库存费用为10元/月。临时增聘或解雇工人：新聘工人培训费为1000元，解雇工人的解聘费为600元 。每月新聘工人数量不能超过10人。企业目前有库存500件，希望六月底的库存不低于700件，其他月份应保持不少于

30、200件的安全库存，企业应如何组织生产。Page 44xi ：第：第 i 月在岗的工人数；月在岗的工人数；yi ：第：第 i 月新聘的工人数；月新聘的工人数；zi ：第：第 i 月解聘的工人数；月解聘的工人数；ki ：产品在第：产品在第 i 月期末的库存数量；月期末的库存数量；ui ：第：第 i 月正常生产的产品数量；月正常生产的产品数量；vi ：第：第 i 月加班生产的产品数量；月加班生产的产品数量；Page 45目标函数：目标函数：生产和库存费用最小生产和库存费用最小min i (800 xi+1000yi+600zi+10ki)Page 461) 每月在岗工人的平衡约束每月在岗工人的平衡

31、约束 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 = 0Page 472）每月生产的平衡约束 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 7500Page 483）正常生