线性规划单纯形法

Page1单纯形法的计算步骤单纯形表jcnmmcccc11BcBXbmcc1mxx1mbb1nmmxxxx11im1mnmmnmaaaa1,11,1100100ijijjaccj0kjkjiiaab其中：Page2单纯形法的计算步骤例1.8用单纯形法求下列线性规划的最优解0,1241648232max21212121xxxxxxxxZ解：1）将问题化为标准型，加入松驰变量x3、x4、x5则标准型为:0,,,,1241648200043max54321524132154321xxxxxxxxxxxxxxxxxZPage3单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。11311421531()2(010400)2ccacacacj23000θiCBXBbx1x2x3x4x50x381210040x41640010--0x51204001323000Z=0检验数j3)400020(3)(32522412322acacacc2)004010(2)(31521411311acacaccPage4单纯形法的计算步骤3）进行最优性检验如果表中所有检验数，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。0j4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表①确定换入基的变量。选择，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：，其对应的xk作为换入变量。②确定换出变量。根据下式计算并选择θ，选最小的θ对应基变量作为换出变量。0j}0|max{jjk0minikikiLaabPage5单纯形法的计算步骤③用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。5）重复3）、4）步直到计算结束为止。Page6单纯形法的计算步骤（表1-3）cj23000θicB基变量bx1x2x3x4x50x38121000x416400100x5120400123000Z=0表1-40x320x4163x23j换入列bi/ai2，ai2043换出行将4化为1，本列的其他值化为010201/401－1/2100－3/4j04001000第一步：将第三行除以4第二步：将第一行减去第三行乘以2Page7单纯形法的计算步骤（表1-4）Cj23000θicB基变量bx1x2x3x4x50x321010-1/20x416400100x2301001/42000-3/4Z=9表1-52x120x43x23j换入列bi/ai2，ai20换出行10001/401－1/210-21/4j000-41200将4化为0第一步：将第二行减去第一行乘以4248Page8单纯形法的计算步骤（表1-5）Cj23000θicB基变量bx1x2x3x4x50x121010-1/20x4800-4120x2301001/400-201/4Z=13表1-62x10x53x2j换入列换出行1001/2000010-3/20j-1/800-21/211/4将2化为1，本列的其他值化为0第一步：将第二行除以244第二步：将第一行加上第二行乘以1/2第三步：将第三行减去第二行乘以1/442-1/8Page9单纯形法的计算步骤表1-6中所有的都小于或者等于0，表明已经达到了最优解，因此，现行的基本可行解X=（4，2，0，0，4）T是最优解，Z=14是该线性规划的最优值。jPage10单纯形法的计算步骤例1.9用单纯形法求解02053115232.2max321321321321xxxxxxxxxtsxxxZ、、解：将数学模型化为标准形式：5,,2,1,02053115232.2max53214321321jxxxxxxxxxtsxxxZj不难看出x4、x5可作为初始基变量，列单纯形表计算。Page11单纯形法的计算步骤cj12100θicB基变量bx1x2x3x4x50x4152-32100x5201/31501121000x42x2j20－x221/3150120753017131/30－90－2j2560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3jPage12单纯形法的计算步骤表1-6中所有的都小于或者等于0，表明已经达到了最优解，因此，现行的基本可行解X=（25，35/3，0，0，0）T是最优解，Z=95/3是该线性规划的最优值。jPage13单纯形法的计算步骤学习要点：1.线性规划解的概念以及3个基本定理2.熟练掌握单纯形法的解题思路及求解步骤Page14单纯形法的进一步讨论－人工变量法人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。Page15单纯形法的进一步讨论－人工变量法例1.10用大M法解下列线性规划0123241123max32131321321321xxxxxxxxxxxxxxZ、、解：首先将数学模型化为标准形式5,,2,1,012324112003max315321432154321jxxxxxxxxxxxxxxxxZj系数矩阵中不存在单位矩阵，无法建立初始单纯形表。Page16单纯形法的进一步讨论－人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：7,,2,1,0121024112003max7316532143217654321jxxxxxxxxxxxxxMxMxxxxxxZj－其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。Page17单纯形法的进一步讨论－人工变量法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→→jj→jjPage18单纯形法的总结解的判别：j1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个0且aij≤０（i=1，2,…,m）则线性规划具有无界解。4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri0时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。Page19单纯形法小结建立模型决策变量个数取值右端项等式或不等式极大或极小新加变量系数求解不处理图解法、单纯形法xj≥0xj无约束令xj=xj′-xj″xj′≥0xj″≥0xj≤0令xj’=-xjxj’≥0bi≥0不处理不处理bi0约束条件两端同乘以-1≤=≥加松弛变量xs加入人工变量xa减去xs,加入xamaxZminZ令z′=-ZminZ=－maxz′xs0xa-M两个三个以上单纯形法jmiijjacc1:求0j所有kj即找出max)()0(0jika对任一)0(lklkiiaab计算lkxx替换基变量用非基变量新单纯形表列出下一个ax含有量中是否基变0j非基变量的有某个最优解一唯无可行解最优解无穷多是否环循否否否是是是循环无界解列出初始单纯形表找出基变量Page21单纯形法的计算步骤单纯形表jcnmmcccc11BcBXbmcc1mxx1mbb1nmmxxxx11im1mnmmnmaaaa1,11,1100100ijijjaccj0kjkjiiaab其中：Page22线性规划模型的应用一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。要求解问题的目标函数能用数值指标来反映，且为线性函数存在着多种方案要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述Page23线性规划在管理中的应用1.人力资源分配问题例1.11某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：班次时间所需人员16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少?Page24线性规划在管理中的应用解：设xi表示第i班次时开始上班的司机和乘务人员人数。0,,,,,302050607060.min654321655443322161654321xxxxxxxxxxxxxxxxxxtsxxxxxx此问题最优解：x1＝50，x2＝20，x3＝50，x4＝0，x5＝20，x6＝10，一共需要司机和乘务员150人。Page25线性规划在管理中的应用2.生产计划问题某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1和A2上完成，有B1、B2、B3三种设备可用于完成B工序。已知产品Ⅰ可在A、B任何一种设备上加工；产品Ⅱ可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品Ⅲ只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。Page26线性规划在管理中的应用设备产品设备有效台时设备加工费（单位小时）ⅠⅡⅢA151060003.00A27912100003.21B16840002.50B241170007.83B3740002.00原料费（每件）0.250.350.5售价（每件）1.252.002.8Page27线性规划在管理中的应用解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有：）（上加工的数量相等），在工序（产品上加工的数量相等），在工序（产品上加工的数量相等），在工序（产品设备设备）（设备）（设备设备3,2,1;2,1;3,2,10BAIIIBAIIBAI)3B(40007)2B(70001141B4000862A100001297)1A(6000105322312221212211123122121112111123322122221121312212112211111kjixxxxxxxxxxxxxxxxxxxx