线性规划单纯形法

线性规划单纯形法第一页，共五十一页，2022年，8月28日单纯形法的计算步骤单纯形表第二页，共五十一页，2022年，8月28日单纯形法的计算步骤例1.8用单纯形法求下列线性规划的最优解解：1）将问题化为标准型，加入松驰变量x3、x4、x5则标准型为:第三页，共五十一页，2022年，8月28日单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。cj23000θiCBXBbx1x2x3x4x50x381210040x41640010--0x51204001323000Z=0检验数第四页，共五十一页，2022年，8月28日单纯形法的计算步骤3）进行最优性检验如果表中所有检验数，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表确定换入基的变量。选择，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：，其对应的xk作为换入变量。确定换出变量。根据下式计算并选择θ

，选最小的θ对应基变量作为换出变量。 第五页，共五十一页，2022年，8月28日单纯形法的计算步骤用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。5）重复3）、4）步直到计算结束为止。 第六页，共五十一页，2022年，8月28日单纯形法的计算步骤（表1-3）cj23000θicB基变量bx1x2x3x4x50x38121000x416400100x5120400123000Z=0表1-40x320x4163x23换入列bi/ai2，ai2>043换出行将4化为1，本列的其他值化为010201/401－1/2100－3/404001000第一步：将第三行除以4第二步：将第一行减去第三行乘以2第七页，共五十一页，2022年，8月28日单纯形法的计算步骤（表1-4）Cj23000θicB基变量bx1x2x3x4x50x321010-1/20x416400100x2301001/42000-3/4Z=9表1-52x120x43x23换入列bi/ai2，ai2>0换出行10001/401－1/210-21/4000-41200将4化为0第一步：将第二行减去第一行乘以4248第八页，共五十一页，2022年，8月28日单纯形法的计算步骤（表1-5）Cj23000θicB基变量bx1x2x3x4x50x121010-1/20x4800-4120x2301001/400-201/4Z=13表1-62x10x53x2换入列换出行1001/2000010-3/20-1/800-21/211/4将2化为1，本列的其他值化为0第一步：将第二行除以244第二步：将第一行加上第二行乘以1/2第三步：将第三行减去第二行乘以1/442-1/8第九页，共五十一页，2022年，8月28日单纯形法的计算步骤

表1-6中所有的都小于或者等于0，表明已经达到了最优解，因此，现行的基本可行解X=（4，2，0，0，4）T是最优解，Z=14是该线性规划的最优值。第十页，共五十一页，2022年，8月28日单纯形法的计算步骤例1.9用单纯形法求解解：将数学模型化为标准形式：不难看出x4、x5可作为初始基变量，列单纯形表计算。第十一页，共五十一页，2022年，8月28日单纯形法的计算步骤cj12100θicB基变量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第十二页，共五十一页，2022年，8月28日单纯形法的计算步骤

表1-6中所有的都小于或者等于0，表明已经达到了最优解，因此，现行的基本可行解X=（25，35/3，0，0，0）T是最优解，Z=95/3是该线性规划的最优值。第十三页，共五十一页，2022年，8月28日单纯形法的计算步骤 学习要点： 1.线性规划解的概念以及3个基本定理 2.熟练掌握单纯形法的解题思路及求解步骤第十四页，共五十一页，2022年，8月28日单纯形法的进一步讨论－人工变量法人工变量法： 前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。第十五页，共五十一页，2022年，8月28日单纯形法的进一步讨论－人工变量法例1.10用大M法解下列线性规划解：首先将数学模型化为标准形式系数矩阵中不存在单位矩阵，无法建立初始单纯形表。第十六页，共五十一页，2022年，8月28日单纯形法的进一步讨论－人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。第十七页，共五十一页，2022年，8月28日单纯形法的进一步讨论－人工变量法cj3-1-100-M-MCBXBbx1x2x3x4x5x6x7θi0x4111-21100011-Mx63-4120-1103/2-Mx71-201000113-6M-1+M-1+3M↑0-M000x4103-20101-1——-Mx610100-11-21-1x31-2010001——1-1+M↑00-M01-3M0x4123001-22-54-1x210100-11-2——-1x3－2010001——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→→→第十八页，共五十一页，2022年，8月28日单纯形法的总结 解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个>0且aij≤０（i=1，2,…,m）则线性规划具有无界解。4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri>0时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。第十九页，共五十一页，2022年，8月28日单纯形法小结建立模型决策变量个数取值右端项等式或不等式极大或极小新加变量系数

求解不处理图解法、单纯形法xj≥0xj无约束令xj=xj′-xj″xj′≥0xj″≥0xj≤0令xj’=-xjxj’≥0

bi

≥0不处理不处理bi

<0约束条件两端同乘以-1≤=≥加松弛变量xs加入人工变量xa减去xs,加入xamaxZminZ令z′=-ZminZ=－maxz′xs0xa-M两个三个以上单纯形法第二十页，共五十一页，2022年，8月28日第二十一页，共五十一页，2022年，8月28日单纯形法的计算步骤单纯形表第二十二页，共五十一页，2022年，8月28日线性规划模型的应用 一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。要求解问题的目标函数能用数值指标来反映，且为线性函数存在着多种方案要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述第二十三页，共五十一页，2022年，8月28日线性规划在管理中的应用人力资源分配问题例1.11某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：班次时间所需人员16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少?第二十四页，共五十一页，2022年，8月28日线性规划在管理中的应用解：设xi表示第i班次时开始上班的司机和乘务人员人数。此问题最优解：x1＝50，x2＝20，x3＝50，x4＝0，x5＝20，x6＝10，一共需要司机和乘务员150人。第二十五页，共五十一页，2022年，8月28日线性规划在管理中的应用2.生产计划问题

某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1和A2上完成，有B1、B2、B3三种设备可用于完成B工序。已知产品Ⅰ可在A、B任何一种设备上加工；产品Ⅱ可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品Ⅲ只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。第二十六页，共五十一页，2022年，8月28日线性规划在管理中的应用设备产品设备有效台时设备加工费（单位小时）ⅠⅡⅢA151060003.00A27912100003.21B16840002.50B241170007.83B3740002.00原料费（每件）0.250.350.5售价（每件）1.252.002.8第二十七页，共五十一页，2022年，8月28日线性规划在管理中的应用解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有：第二十八页，共五十一页，2022年，8月28日线性规划在管理中的应用目标是利润最大化，即利润的计算公式如下：带入数据整理得到：第二十九页，共五十一页，2022年，8月28日线性规划在管理中的应用因此该规划问题的模型为：第三十页，共五十一页，2022年，8月28日线性规划在管理中的应用3.套裁下料问题例：现有一批某种型号的圆钢长8米，需要截取2.5米长的毛坯100根，长1.3米的毛坯200根。问如何才能既满足需要，又能使总的用料最少？解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出4种下料方案以供套裁用。ⅠⅡⅢⅣ2.5m32101.3m0246料头0.500.30.2第三十一页，共五十一页，2022年，8月28日线性规划在管理中的应用设按方案Ⅰ、Ⅱ、Ⅲ、Ⅳ下料的原材料根数分别为xj(j=1，2,3,4)，可列出下面的数学模型：第三十二页，共五十一页，2022年，8月28日线性规划在管理中的应用3.多周期动态生产计划问题

华津机器制造厂专为拖拉机厂配套生产柴油机。今年头四个月收到的订单数量分别为3000，4500，3500，5000台柴油机。该厂正常生产每月可生产柴油机3000台，利用加班还可生产1500台。正常生产成本为每台5000元，加班生产还要追加1500元成本，库存成本为每台每月200元。华津厂如何组织生产才能使生产成本最低。第三十三页，共五十一页，2022年，8月28日线性规划在管理中的应用决策变量：

xi为第i月正常生产的柴油机数； yi为第i月加班生产的柴油机数； zi为第i月初柴油机的库存数。第三十四页，共五十一页，2022年，8月28日线性规划在管理中的应用数学模型如下：

minz=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

0xi

3000

i=1

,

2

,

3

,

4

0yi

1500

i=1

,

2

,

3

,

4 zi

0

i=1

,

2

,

3

,

4第三十五页，共五十一页，2022年，8月28日线性规划在管理中的应用第三十六页，共五十一页，2022年，8月28日线性规划在管理中的应用5.证券投资组合优化

某人有一笔50万元的资金可用于长期投资，可供选择的投资机会包括购买国库卷、债卷、房地产、股票或银行储蓄等。他希望投资组合的平均年限不超过5年，平均的期望收益率不低于13%，风险系数不超过4，收益的增长潜力不低于10%。在满足上述要求的前提应如何选择投资组合才能使平均收益率最高。第三十七页，共五十一页，2022年，8月28日线性规划在管理中的应用

投资投资期 年收益风险增长潜方式限(年)率(％)系数力(％)国库卷311

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第三十八页，共五十一页，2022年，8月28日线性规划在管理中的应用决策变量：各种投资方式站总投资的比例；目标函数：平均投资收益最大；约束方程：满足各种指标要求：1、平均投资年限不超过5年2、平均的期望收益率不低于13%3、风险系数不超过44、收益的增长潜力不低于15%第三十九页，共五十一页，2022年，8月28日线性规划在管理中的应用证券组合优化模型maxz=11x1+15x2+25x3+20x4+10x5+12x6+3x7s.t. 3x1+10x2+6x3+2x4+x5+5x6

511x1+15x2+25x3+20x4+10x5+12x6+3x7

13x1+3x2+8x3+6x4+x5+2x6

4 15x2+30x3+20x4+5x5+10x6

10x1+x2+x3+x4+x5+x6+x7=1

x1

,

x2

,

x3

,

x4

,

x5

,

x6

,x7

0第四十页，共五十一页，2022年，8月28日线性规划在管理中的应用第四十一页，共五十一页，2022年，8月28日线性规划在管理中的应用6.生产库存计划问题例：企业根据预测知道上半年市场对该企业产品的需求变化较大（见下表）：月份123456需求600025005000350055006000企业目前有100名工人，每人每月可生产40件产品，工人平均工资每月800元，企业可以通过以下方法调节生产：

第四十二页，共五十一页，2022年，8月28日线性规划在管理中的应用利用加班：加班需付加倍工资，每人每月利用加班生产的产品不能超过10件。利用库存：每件产品库存费用为10元/月。临时增聘或解雇工人：新聘工人培训费为1000元，解雇工人的解聘费为600元。每月新聘工人数量不能超过10人。企业目前有库存500件，希望六月底的库存不低于700件，其他月份应保持不少于200件的安全库存，企业应如何组织生产。第四十三页，共五十一页，2022年，8月28日线性规划在管理中的应用变量设置：

xi：第i月在岗的工人数； yi：第i月新聘的工人数； zi：第i月解聘的工人数； ki：产品在第i月期末的库存数量； ui：第i月正常生产的产品数量； vi：第i月加班生产的产品数量；第四十四页，共五十一页，2022年，8月28日线性规划在管理中的应用目标函数：生产和库存费用最小min

i(800xi+1000yi+600zi+10ki)第四十五页，共五十一页，2022年，8月28日线性规划在管理中的应用约束条件：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第四十六页，共五十一页，2022年，8月28日线性规划在管理中的应用2）每月生产的平衡约束