线性规划单纯形法ppt课件.ppt

单纯形法的计算步骤,单纯形表,单纯形法的计算步骤,例1.8 用单纯形法求下列线性规划的最优解,解：1）将问题化为标准型，加入松驰变量x3、x4、 x5则标准型为:,单纯形法的计算步骤,2）求出线性规划的初始基可行解，列出初始单纯形表。,检验数,单纯形法的计算步骤,3）进行最优性检验,如果表中所有检验数 ，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。,4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表,确定换入基的变量。选择 ，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即： ，其对应的xk作为换入变量。确定换出变量。根据下式计算并选择 ，选最小的对应基变量作为换出变量。,单纯形法的计算步骤,用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。5）重复3）、4）步直到计算结束为止。,单纯形法的计算步骤,换入列,bi /ai2，ai20,4,3,换出行,将4化为1，本列的其他值化为0,1,0,2,0,1/4,0,1,1/2,1,0,0,3/4,0,4,0,0,1,0,0,0,第一步：将第三行除以4,第二步：将第一行减去第三行乘以2,单纯形法的计算步骤,换入列,bi /ai2，ai20,换出行,1,0,0,0,1/4,0,1,1/2,1,0,-2,1/4,0,0,0,-4,1,2,0,0,将4化为0,第一步：将第二行减去第一行乘以4,2,4,8,单纯形法的计算步骤,换入列,换出行,1,0,0,1/2,0,0,0,0,1,0,-3/2,0,-1/8,0,0,-2,1/2,1,1/4,将2化为1，本列的其他值化为0,第一步：将第二行除以2,4,4,第二步：将第一行加上第二行乘以1/2,第三步：将第三行减去第二行乘以1/4,4,2,-1/8,单纯形法的计算步骤,表1-6中所有的 都小于或者等于0，表明已经达到了最优解，因此，现行的基本可行解X=（4，2，0，0，4）T是最优解，Z=14是该线性规划的最优值。,单纯形法的计算步骤,例1.9 用单纯形法求解,解：将数学模型化为标准形式：,不难看出x4、x5可作为初始基变量，列单纯形表计算。,单纯形法的计算步骤,20,x2,2,1/3,1,5,0,1,20,75,3,0,17,1,3,1/3,0,9,0,2,25,60,x1,1,1,0,17/3,1/3,1,25,0,1,28/9,-1/9,2/3,35/3,0,0,-98/9,-1/9,-7/3,单纯形法的计算步骤,表1-6中所有的 都小于或者等于0，表明已经达到了最优解，因此，现行的基本可行解X=（25，35 /3，0，0，0）T是最优解，Z=95/3是该线性规划的最优值。,单纯形法的计算步骤,学习要点：1. 线性规划解的概念以及3个基本定理2. 熟练掌握单纯形法的解题思路及求解步骤,单纯形法的进一步讨论人工变量法,人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。,单纯形法的进一步讨论人工变量法,例1.10 用大M法解下列线性规划,解：首先将数学模型化为标准形式,系数矩阵中不存在单位矩阵，无法建立初始单纯形表。,单纯形法的进一步讨论人工变量法,故人为添加两个单位向量，得到人工变量单纯形法数学模型：,其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。,单纯形法的进一步讨论人工变量法,单纯形法的总结,解的判别：,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,加入xa,maxZ,minZ,令z=- ZminZ=max z,xs,0,xa,-M,两个,三个以上,单纯形法,单纯形法的计算步骤,单纯形表,线性规划模型的应用,一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。,要求解问题的目标函数能用数值指标来反映，且为线性函数 存在着多种方案 要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述,线性规划在管理中的应用,人力资源分配问题,例1.11 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：,设司机和乘务人员分别在各时间段开始时上班，并连续工作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设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。,线性规划在管理中的应用,线性规划在管理中的应用,解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有：,线性规划在管理中的应用,目标是利润最大化，即利润的计算公式如下：,带入数据整理得到：,线性规划在管理中的应用,因此该规划问题的模型为：,线性规划在管理中的应用,3. 套裁下料问题,例：现有一批某种型号的圆钢长8米，需要截取2.5米长的毛坯100根，长1.3米的毛坯200根。问如何才能既满足需要，又能使总的用料最少？,解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出4种下料方案以供套裁用。,线性规划在管理中的应用,设按方案、下料的原材料根数分别为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. 生产库存计划问题,线性规划在管理中的应用,利用加班：加班需付加倍工资，每人每月利用加班生产的产品不能超过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 ；,线性规划在管理中的应用,