胡云权运筹学课件第二部分

运筹学基础 第十一讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48对偶问题的提出 例1.美佳公司计划制造、两种家电产品。各制造一件时分别占用的设备A、B的台时、调试时间及每天这两种家电可用能力、各售出一件时获利情况如表所示：项目每天可用能力设备A(h)0515设备B(h)6224调试时间(h)115利润（元）21问公司应制造两种家电各多少台，使获取的利润最大。对偶问题的提出 假定有某个公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源？项目每天可用能力设备A(h)0515设备B(h)6224调试时间(h)115利润（元）21对偶问题的提出 项目每天可用能力设备A(h)0515设备B(h)6224调试时间(h)115利润（元）21设y1，y2，y3代表单位时间设备A、设备B和调试工序的出让代价对偶问题的提出 （L1）（L2）原问题 对偶问题对称形式下对偶问题的一般形式 原问题 对偶问题例2 写出下列问题的对偶问题（2.7a）（2.7b）（2.7c）（2.7d）非对称形式的原对偶问题关系例2 写出下列问题的对偶问题（2.7a）（2.7b）（2.7c）（2.7d）对偶变量y1 y2 y2 y3先转换成对称形式，如下：非对称形式的原对偶问题关系例2-4 令各约束对应的对偶变量分别为y1、y2、y2、-y3令y2=y2-y2，y3=-y3，原问题的对偶问题为非对称形式的原对偶问题关系运筹学基础 第十二讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48对应关系总结项目原问题（对偶问题）max对偶问题（原问题）minA约束系数矩阵其约束系数矩阵的转置b约束条件的右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件的右端项向量目标函数max z=CjXjmin w=biyi对应关系总结项目原问题（对偶问题）对偶问题（原问题）A约束系数矩阵其约束系数矩阵的转置b约束条件的右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件的右端项向量目标函数max z=CjXjmin w=biyi对偶问题的基本性质本章讨论先假定原问题及对偶问题为对称形式线性规划问题：原问题 对偶问题单纯形法计算的矩阵描述对称形式线性规划矩阵表达式加上松弛变量Xs后为：其中松弛变量Xs=（xn+1,xn+2,.,xn+m）,I为mm单位矩阵项目基变量基变量XB XNXs0 XB bB NICB CN0选取I为初始基，对应基变量为Xs。设迭代若干步后，基变量为XB，XB在初始单纯形表中的系数矩阵为B。A中去掉B的若干列后剩下的列组成矩阵N。进一步迭代,新的单纯形表如下：项目基变量非基变量XBXN XsCB XB B-1bIB-1N B-1 0CN-CBB-1N CBB-1 对应初始单纯形表中的单位矩阵I，迭代后的单纯形 表中为B-1 初始单纯形表中基变量Xs=b，迭代后的表中XB=B-1b 初始单纯形表中约束系数矩阵为 A,I=B,N,I，迭代后的表中约束系数矩阵为 B-1A,B-1I=B-1B,B-1N,B-1I=I,B-1N,B-1若初始矩阵中变量xj的系数向量为Pj，迭代后为 Pj，则有Pj=B-1Pj当B为最优基时，表中应有 CN-CBB-1N0,-CBB-10单纯形法计算的矩阵描述项目基变量基变量XB XNXs0 XB bB NICB CN0例3 参看例1中的原问题和对偶问题，并分别加上松弛变量和剩余变量，如下：对偶变量y1y2y3对偶变量x1x2单纯形法计算的矩阵描述两个问题的最终单纯形表如下：项目原问题变量原问题松弛变量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2000-1/4-1/2变量对偶问题的剩余变量对偶问题变量y4y5y1y2y3项目对偶问题变量对偶问题剩余变量y1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2-15/200-7/2-3/2变量原问题松弛变量原问题变量x3x4x5x1x2对偶问题的基本性质1.弱对偶性 如果（j=1，.，n）是原问题的可行解，（i=1，.，m）是其对偶问题的可行解，则恒有对偶问题的基本性质弱对偶性的推论：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界如原问题有可行解且目标函数值无界(具有无界解)，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然。若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界对偶问题的基本性质2.最优性如果 (j=1,.,n)是原问题的可行解，(i=1,.,m)是其对偶问题的可行解，且有则 (j=1,.,n)是原问题的最优解，(i=1,.,m)是其对偶问题的最优解。对偶问题的基本性质 3.强对偶性(或称对偶定理)若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。对偶问题的基本性质4.互补松弛性在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。也即若 0，则有 ，即若 ，即 ，则有因此一定有 ，影子价格对偶最优解的经济含义影子价格 对偶变量 的意义代表在资源最优利用条件下对单位第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价,为区别起见，称为影子价格。当B是原问题的最优基时，Y=CBB-1就是影子价格向量。影子价格资源的市场价格是其价值的客观体现，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。因企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。影子价格是一种边际价格。影子价格资源的影子价格实际上又是一种机会成本。随着资源的买进卖出，其影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。影子价格反映单纯形表中各个检验数的经济意义。一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用。Cc1 c2 c3 c4 CBXBB-1b x1 x2 x3 x4 46x2x12020 0 1 1/2 -1/4 1 0 -1/4 3/8 0 0 -1/2 -5/4计算下面线性规划问题各种资源的影子价格：影子价格运筹学基础 第十三讲第十三讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48对偶单纯形法对偶单纯形法步骤1 确定原问题的初始基，使所有的 ，即 是对偶可行解，建立初始单纯形表。步骤2 检查基变量所取的值，若则已取得最优解，计算停；否则求 确定XBL为旋出变量步骤3 若所有的aLj大于等于零，则原问题无解，计算停；否则计算，确定 Xk为旋入变量步骤4 以aLk为旋转主元做旋转变换，转步骤2例4 用对偶单纯形法求解：对偶单纯形法cj-15-24-500CBXBB-1by1y2y3y4y50y4-20-6-1100y5-1-5-2-101-15-24-500-24y21/3011/6-1/600y5-1/3-50-2/3-1/31-150-1-40-24y21/4-5/410-1/41/4-5y31/215/2011/2-3/2-15/200-7/2-3/2对偶单纯形法对偶单纯形法对偶单纯形法的优点：可以尽量避开人工变量，简化计算进行灵敏度分析对偶问题单纯形法的应用条件：所有约束全是不等式；问题标准化后，价值系数全非正灵 敏 度 分 析 在生产计划问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，而C代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。灵敏度分析：就是分析研究线性规划问题某些参数(如Cj，bi，aij)变化对最优解影响的程度，或者说是最优解对数据变化反应的敏感程度。灵敏度分析的主要内容：这些参数究竟在什么样的范围内变化，原先求解出的最优解或最优基不变？如果这些参数的变化引起了最优解的变化，如何用最简便的办法来求出新的最优解。灵 敏 度 分 析以线性规划的标准型分别研究各类参数的灵敏度分析灵 敏 度 分 析最优基为B，最优解为 ,其它xj0，最优值 Cc1 c2 cm cm+1 cn CBXBB-1bx1 x2 xm xm+1 xnc1cmx1xma10am01 0 0 a1m+1 a1n 1 0 0 1 amm+1 amn0 0 0 m+1 nj=cj-CBB-1PjB-1PjPj以线性规划的标准型分别研究各类参数的灵敏度分析灵 敏 度 分 析最优基为B，最优解为 ,其它xj0，最优值 Cc1 c2 cm cm+1 cn CBXBB-1bx1 x2 xm xm+1 xnc1cmx1xma10am01 0 0 a1m+1 a1n 1 0 0 1 amm+1 amn0 0 0 m+1 nj=cj-CBB-1PjB-1PjPj价值系数的变化将仅影响检验数的变化：j=cj-CBB-1Pj目标函数中的价值系数的分析 Cc1 c2 cm cm+1 cn CBXBB-1bx1 x2 xm xm+1 xnc1cmx1xma10am01 0 0 a1m+1 a1n 1 0 0 1 amm+1 amn0 0 0 m+1 nj=cj-CBB-1PjB-1PjPj价值系数的变化将仅影响检验数的变化：j=cj-CBB-1Pj非基变量价值系数cj的变化仅仅影响非基变量xj的检验数，而对其它检验数没有影响。基变量xBr的价值系数cBr将影响所有非基变量的检验数值。若出现正的检验数，原最优解不再是最优解，以该解为初始解，用单纯形法在原来的最优单纯形表上进行迭代，尽快得到新的最优解。目标函数中的价值系数的分析 运筹学基础 第十四讲第十四讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48目标函数中的价值系数的分析分析cj的变化例5 在第一章例1的美佳公司例子中：（1）若家电的利润降至1.5元/件，而家电的利润增至2元/件时，美佳公司最优生产计划有何变化?c1.52000CBXBB-1bx1x2x3x4x50 x315/20015/4-15/21.5x17/21001/4-1/22x23/2010-1/43/20001/8-9/40 x46004/51-61.5x1210-1/5012x23011/50000-1/100-3/2即美佳公司随家电，的利润变化应调整为生产2件，生产3件。c21+000 CB XB B-1bx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21+x23/2010-1/43/2000-1/4+1/4-1/2-3/2（2）若家电的利润不变，则家电的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？设家电的利润为（1+）元，如下为保证最优解，解得即家电的利润c2的变化范围应满足目标函数中的价值系数的分析约束条件中的资源系数的分析 设资源系数bi有增量bi，其它参数不变，求使最优基不变的bi变化范围；设如果bi不在上述范围内，则一定会出现负的基变量值，但由于bi不影响检验数的变化，因此可以 为初始解，利用对偶单纯形法继续求解。Cc1 c2 cm cm+1 cn CBXBB-1bx1 x2 xm xm+1 xnc1cmx1xma10am01 0 0 a1m+1 a1n 1 0 0 1 amm+1 amn0 0 0 m+1 nj=cj-CBB-1PjB-1PjPj分析bi的变化例6 在美佳公司的例子中：（1）若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32h，分析公司最优计划的变化；c21000CBXBB-1bx1x2x3x4x50 x335/20015/4-15/22x111/21001/4-1/21x2-1/2010-1/43/2000-1/4-1/20 x315051002x15110010 x420-401-60-100-2约束条件中的资源系数的分析（2）设设备A和设备B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。设调试工序每天可用能力为（5+）h，因有最终单纯形表中B-1b列数字为因B-1b0时最优基不变，故-11。调试工序的能力应在4h6h之间。约束条件中的资源系数的分析 约束条件中的技术系数的分析 增加一个新变量Xn+1的分析先计算 及 ，若则原最优解不变，否则将 填到最优单纯形表的最后一列，用单纯形法继续迭代。Cc1 c2 cm cm+1 cn c cn+1n+1 CBXBB-1bx1 x2 xm xm+1 xn x xn+1n+1c1cmx1xma10am01 0 0 a1m+1 a1n a a1n+1 1 0 0 1 amm+1 amn amn+10 0 0 m+1 n n+1例7 设美佳公司又计划推出新型号的家电，生产一件所需设备A、B及调试工序的时间分别为3h、4h、2h，该产品的预期盈利为3元/件，试分析该产品是否值得投产；如投产，对该公司的最优生产计划有何影响。设生产x6件家电，有c6=3，P6=（3，4，2）T约束条件中的技术系数的分析 c210003CBXB B-1bx1x2x3x4x5x60 x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/22000-1/4-1/210 x351/407/213/8-9/402x17/21001/4-1/203x63/401/20-1/83/410-1/20-1/8-5/40最优生产计划应为每天生产7/2件家电，51/4件家电。约束条件中的技术系数的分析 约束条件中的技术系数的分析 增加一个新变量Xn+1的分析先计算 及 ，若则原最优解不变，否则将 填到最优单纯形表的最后一列，用单纯形法继续迭代。增加一个新的约束条件分析设 是新增加的约束条件 将 填到最优单纯形表中的最后一行，变化后的单纯形表增加一行和一列，新约束方程对应的基变量为 ；Cc1 c2 cm cm+1 cn 0 0 CBXBB-1bx1 x2 xm xm+1 xn x xn+1n+1c1cm0 x1xmx xn+1n+1a10am0 bm+11 0 0 a1m+1 a1n 0 0 1 0 0 1 amm+1 amn 0am+1,1 am+1,2 am+1,m am+1,m+1 am+1,n 1Cc1 c2 cm cm+1 cn 0 0 CBXBB-1bx1 x2 xm xm+1 xn x xn+1n+1c1cm0 x1xmx xn+1n+1a10am0 bm+11 0 0 a1m+1 a1n 0 0 1 0 0 1 amm+1 amn 00 0 0 am+1,m+1 am+1,n 10 0 0 m+1 n 0约束条件中的价值系数的分析 将基变量对应的列变为单位列向量变化后，原单纯形表的检验数不变但基变量 取值变了。若 ，则已取得最优解，反之，若 利用对偶单纯形法进行求解。运筹学基础 第十五讲第十五讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48例9 设家电，经调试后，还需经过一道环境试验工序。家电每件需环境试验3h，家电每件需2h，又环境试验工序每天生产能力为12h。试分析增加该工序后的美佳公司最优生产计划。（1）检验原问题的最优解是否仍适用。将x1=7/2，x2=3/2代入3x1+2x212，27/212，所以不适用。（2）加入松弛变量x6，得3x1+2x2+x6=12（3）单纯形表求解。约束条件中的价值系数的分析 c210000CBXB B-1bx1x2x3x4x5x60 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x612320001000-1/4-1/200 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x6-3/2000-1/4-3/21000-1/4-1/200 x3150015/20-52x141001/30-1/31x20010-1/2010 x510001/61-2/3000-1/60-1/3注：表中同，=-3-2。约束条件中的价值系数的分析 约束条件中的技术系数的分析 改变某非基变量xj的系数列向量分析该变化只影响最优单纯形表的第j列及其检验数。因此，可先计算 及 ，若 ，则原最优解不变；反之，若 ，则以 代替原最优表的第j列，用单纯形法继续求解。Cc1 c2 cm cm+1 cn CBXBB-1bx1 x2 xm xm+1 xnc1cmx1xma10am01 0 0 a1m+1 a1n 1 0 0 1 amm+1 amn0 0 0 m+1 nj=cj-CBB-1PjB-1PjPj约束条件中的价值系数的分析 改变某基变量xBr的系数列向量分析 设基变量xBr的系数列向量为将xBr看作是新增加的变量，用替代原最优表的第j列（单位列向量)然后再用初等行变换将表中的恢复为原来的单位列向量。变化后单纯形表有以下几种情况：基变量的值全非负，检验数全非正，已得最优解；基变量的值全非负，但存在正的检验数，用单纯形法继续求解；存在取负值的基变量，但检验数全非正，用对偶单纯形法继续求解；存在取负值的基变量，存在取正值的检验数，可以这样做：约束条件中的价值系数的分析 约束条件中的价值系数的分析 将表中取负值的基变量对应的行还原成约束方程；用-1乘约束方程的两端，再在方程的左端加上人工变量xn+1用该方程替代最优单纯形表中第r行，则表中第r行对应的基变量为xn+1，其对应的值为 其价值系数为-M。例8 在美佳公司的例子中，若家电每件需设备A,B和调试工时变为8h、4h、1h，该产品的利润变为3元/件，试重新确定该公司最优生产计划。设生产工时变化后的新家电的生产量为x2，其中：约束条件中的价值系数的分析 c23000CBXB B-1bx1x2x3x4x50 x315/2011/215/4-15/22x17/211/201/4-1/21x23/201/20-1/43/203/20-1/4-1/20 x3-90014-242x121001/2-23x23010-1/230001/2-5原问题和对偶问题均为非可行解约束条件中的价值系数的分析 上表中第二阶段第一行的约束为：x3+4x4-24x5=-9 -x3-4x4+24x5+x6=9替换后重新得表：c23000-MCBXB B-1bx1x2x3x4x5x6-Mx6900-1-42412x121001/2-203x23010-1/23000-M1/2-4M-5+24M00 x53/800-1/24-1/611/242x111/410-1/121/601/123x215/8011/800-1/800-5/24-1/30-M+5/24最优生产计划为每天生产11/4台家电，15/8台家电约束条件中的价值系数的分析 运 输 问 题|运输问题与有关概念|产销平衡运输问题的求解表上作业法本章内容重点运 输 问 题 前面讨论了线性规划问题的一般解法，在实际生活中，碰到的线性规划问题的系数矩阵往往具有特殊的结构，这就可能找到比单纯形法更为简单的方法，从而节省计算时间和空间。本章讨论的运输问题就是这样一类特殊的线性规划问题。在经济生活中，常碰到大宗物资的调运问题，如煤、钢铁、木材、粮食等物资，他们在全国有若干生产基地，根据已有的交通网络，制定调运方案，将这些物资运到各个消费地点，而总运费最省。运 输 问 题 运输问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的产量（供应量）与每个销地的销量(需求量)已知，并知道各地之间的运输单价的前提下，如何确定一个使得总运费用最省的调运方案。例1 某部门有3个生产同类产品的工厂(产地)，生产的产品由4个销售点(销地)出售，各工厂的生产量、各销售点的销售量(假定单位均为t)以及各工厂到各销售点的单位运价(元t)示于表3-2中，要求研究产品如何调运才能使总运费最小?表3-2 销地产地B1B2B3B4产量A116A210A322销量8141214484281254101139611运输问题该问题的数学模型：运输问题 销地产地B1B2B3B4产量A116A210A322销量8141214484281254101139611该问题的数学模型：运输问题 销地产地B1B2B3B4产量A116A210A322销量8141214484281254101139611设某物资有m个产地A1，A2，Am其产量分别是a1,a2,am,有n个销地B1，B2，Bm,其销量分别是b1,b2,bn。已知产地Ai到销地Bj的单位运价是Cij（i=1,2,m；j=1,2,n）这些数据可以用运输表表示。若总产量等于总销量（产销平衡）试确定总运费最省调运方案运输问题及其数学模型运输表运输问题及其数学模型运 输 问 题 设xij为从产地Ai运往销地Bj的运输量，则此问题的数学模型为：二、运输问题数学模型的特点：二、运输问题数学模型的特点：1.运输问题一定有最优解；基变量的个数=m+n-12.运输问题约束条件的系数矩阵：x1mx2mxm1xmmx11x12x21x22xm2m行n行运输问题及其数学模型运输问题具有下述特点：(1)约束条件系数矩阵的元素等于0或1；(2)约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。运输问题及其数学模型对产销平衡运输问题，除上述两个特点外，还有以下特点：(1)所有结构约束条件都是等式约束；(2)各产地产量之和等于各销地销量之和。运输问题及其数学模型75运输问题的解运筹学基础 第十六讲第十六讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48表上作业法表上作业法求解思路：初始调运方案初始调运方案是否是是否是最优解最优解结束结束方案调整方案调整NY确定初始调运方案最小元素法：这种方法的基本思想是就近供应，从运价表中最小运价开始确定运量，然后次小，一直到给出初始调运方案为止。具体做法为：找出运价表中最小元素 ，确定 ，若 ,则令划掉运价表中的第L行；反之,若则令 ，划掉运价表中的第K列在运价表中剩余元素中重复，直至运价表中所有的元素全被划掉 销地产地B1B2B3B4产量A1 16A2 10A3 22销量 814 12 14484285101112346911 821014 861.1.最小元素法最小元素法总费用 z=104+611+82+23+145+86=246确定初始调运方案确定初始调运方案西北角法（左上角法）：这种方法的基本思想是给运输表左上角变量分配运输量，以确定产销关系，依此类推，一直到给出初始可行方案为止。具体做法为：先决定运输表左上角变量xLK，令这个变量取尽可能大的值即xLK=minaL,bk，在这个变量对应的数字格上填上变量所取的值。确定初始调运方案西北角法：若xLK=aL,则 划去掉运输表的第L行，这些空格不再赋值；若xLK=bk,则 划去第k列，这些空格不再赋值。对表上剩余元素重复，直到所有的格子都有标记。销地产地B1B2B3B4产量A1 16A2 10A3 22销量 8 14 12 14484285101112346911 846 14882.2.西北角法西北角法总费用 z=84+812+610+43+811+146=372确定初始调运方案3.沃格尔法罚数=次小费用-最小费用找出最大的罚数行或列所对应的最小费用优先安排。重复计算步骤1和2确定初始调运方案3.沃格尔法沃格尔法 销地产地B1B2B3B4产量行罚数12345A116A210A322销量 814121448列罚数123454101211346911285201513221011321148810217062201242总费用 z=244确定初始调运方案最优性检验检验数：对于空格（i，j），假定给它一个单位运量，调整其它有关数字格运量，则这一系列变化导致的总运费变化值称为该空格的检验数，记为 。最优方案的判别准则：如果一个可行方案的所有空格的检验数都大于等于零，则该方案是最优方案。闭回路法以空格为起点的闭回路：它是以空格为起点，沿水平方向或垂直方向前进，碰到合适数字格后转90，继续前进直至回到起始空格为止。可以证明：在任何可行方案中，以空格（i，j）为顶点，其余顶点全是数字格的闭回路存在且唯一。闭回路示意图闭回路法检验数：为了确定空格（i，j）的检验数，可以先找出以该空格为一个顶点，其余顶点全是数字格的闭回路，然后假定给空格（i，j）一个单位运量，调整该闭回路上所有数字格顶点的运量，使产销平衡，则闭回路上总运费的变化值就等于空格（i，j）的检验数。运筹学基础 第十七讲第十七讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48闭回路法判别准则：当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。销地产地B1B2B3B4产量A1 16A2 10A3 22销量 814 12 1448428510111234691182101486对对偶偶变变量量法法对偶变量法（位势法）对偶变量法（位势法）设对偶变量向量为设对偶变量向量为对偶规划为对对偶偶变变量量法法 j =C j-CBB-1 Pj=Cj -Y Pj ij =C ij-CBB-1 Pij=Cij -Y Pij =Cij -(u1,u2,um,v1,v2,vn)Pij =Cij -(ui+vj )当xij 为基变量时 ij=Cij -(ui+vj )=0 由此，任选一个对偶变量为0，可求出其余所有的ui，vj。再根据ij=Cij -(ui+vj )求出所有非基变量的检验数。对对偶偶变变量量法法 销地产地B1B2B3B4产量uiA116A210A322销量814121448vj2.计算检验数4281254101139611对对偶偶变变量量法法 销地产地B1B2B3B4产量uiA1161A2100A322-4销量814121448vj293102.计算检验数4281254101139611对对偶偶变变量量法法 销地产地B1B2B3B4产量uiA1161A2100A322-4销量814121448vj293102.计算检验数42812541011396111211012-1检验数13=8-（-4）-2=10；24=9-10=-10,故这个解不是最优解对对偶偶变变量量法法运筹学基础 第十八讲第十八讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48调整方案确定检验数最小的空格（L,K）,即找出以该空格（L,K）为顶点，其余顶点全是数字格得闭回路（该回路存在且唯一），规定该空格（L,K）为闭回路得第一个顶点，闭回路上其它顶点依次为第二个顶点，第三个顶点（顺时针或逆时针排序均可），取闭回路上偶数顶点的最小运量为调整量。闭回路法闭回路顶点上偶数序号顶点的运量均减，奇数序号顶点的运量均加，不在闭回路上的运量不变。在调整中，如果偶数序号的顶点中仅有一个数字格的运量等于调整数，则调整后，该数字格变为空格；如果偶数序号顶点中两个以上数字格的运量等于调整量，则调整后仅让其中一个数字格为空格，其它调整后要记为“0”，该“0”要看作数字格。调整后，就可以得到一个含有m+n-1个数字格的新的调运方案。销地产地B1B2B3B4产量A1 16A2 10A3 22销量 814 12 1448428510111234691182101486习题习题1 某糖果公司下设三个工厂，每日产量分别为：A17吨，A24吨，A39吨。该公司将这些产品运往四个门市部，各门市部每日销量为B13吨，B26吨，B35吨,B46吨。各工厂到各门市部的单位运价见下表，用最小元素法确定一初始调运方案。销地产地B1B2B3B4产量A1 7A2 4A3 9销量 36 5 6317491011235810 销地产地B1B2B3B4产量A1 7A2 4A3 9销量 36 5 6317491011235810314633运筹学基础 第十九讲第十九讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48 销地产地B1B2B3B4产量A1 7A2 4A3 9销量 36 5 6317491011235810315632产销不平衡运输问题|产大于销情况：如果总产量大于总销量，就会出现多余物资没地方要的情况，就需要考虑多余物资在哪些产地就地存储的问题。将各地的仓库设成一个假想的销地Bn+1，该销地总需求量:=+-=njjmiinbab111产销不平衡运输问题如果某产地i允许物资就地存储，则Ci,n+1=0因为物资就地存储不存在运输费用问题，运输单价应该是“0”。产销不平衡运输问题如果某产地i不允许物资就地存储，Ci,n+1=M，M 是一个相当大的正数 这样对于某产地i，如果物资就地存储就付出相当大的代价，使得在求解时不得不将产地i的物资都运出去。在最优解中，产地Ai到虚拟销地Bj的运量就是产地Ai就地存储的多余物资的数量。产销不平衡运输问题|销大于产情况（供不应求情况）：如果总销量大于总产量，必然会出现某销地缺货情况，就需要考虑确定哪些销地缺货多少的问题，为了求解这种问题设虚拟产地Am+1，认为该虚拟产地至各销地的运量为各销地的缺货量。该产地总产量为：产销不平衡运输问题如果某销地j允许缺货，则Cm+1,j=0 即求解的结果会出现从虚拟产地Am+1向销地Bj运送货物的情况，实际上这部分运量是不可能存在的，是最后分配方案中Bj的缺货量。由于这个产地是不存在的，当然运价为0。产销不平衡运输问题如果某销地j不允许缺货，Cm+1,j=M,M 是一个相当大的正数 从虚拟产地到销地的运价为M，则意味着不可能从虚拟产地Am+1向销地Bj运送货物，则销地Bj的销量bj需要完全是从产地A1 Am运来的，这样就可以保证销地j不缺货。在最优解中，虚设产地Am+1到销地Bj的运量实际上就是最后分配方案中Bj的缺货量。产销不平衡运输问题|例2 设有A1、A2和A3三个产地生产某种物资，其产量分别是5，6，8吨，B1、B2和B3三个销地需要该物资，销量分别是4，6，8吨，又已知各产销地之间的单位运价如下表，试确定总运费最省的调运方案。产销不平衡运输问题有转运的运输问题 接收发送产地销地发送量1mm+1m+n产地1x11x1mx1,m+1x1,m+nQ+a1mxm1xmnxm,m+1xm,m+nQ+am销地m+1xm+1,1xm+1,mxm+1,m+1xm+1,m+nQm+nxm+n,1xm+n,mxm+n,m+1xm+n,m+nQ接收量QQQ+bm+1Q+bm+n表3-15 有转运输问题的运输表有转运的运输问题表3-16 有转运输问题的运价表 接收发送产地销地发送量1mm+1m+n产地1-c1c1mc1,m+1c1,m+nQ+a1mcm1-cmcm,m+1cm,m+nQ+am销地m+1cm+1,1cm+1,m-cm+1cm+1,m+nQm+ncm+n,1cm+n,mcm+n,m+1-cm+nQ接收量QQQ+bm+1Q+bm+n有转运的运输问题例 5图3-3示出了一个运输系统，它包括两个产地(和)、两个销地(和)及一个中间转运站()，各产地的产量和各销地的销量用相应节点处箭线旁的数字表示，节点连线上的数字表示其间的运输单价，节点旁的数字为该地的转运单价，试确定最优运输方案。有转运的运输问题 接收发送产地转运销地发送量12345产地160290转运350销地450550接收量5050 5080702-35M632-355-45M2-14532MM456-5表3-17有转运的运输问题 接收发送产地转运销地发送量12345产地1501060250202090转运3302050销地4505055050接收量5050 5080702-35M632-355-45M2-14532MM456-5表3-19Z=c14x14+c25x25+c23x23+c33x33+c34x34 =210+420+220+320+520=300有转运的运输问题应用问题举例例6 有三个产地A1,A2 和 A3生产同一种物品，使用者为B1,B2 和 B3，各产地到各使用者的单位运价示于表323中。这三个使用者的需求量分别为10、4和6个单位。由于销售需要和客观条件的限制，产地A1至少要发出6个单垃的产品，它最多只能生产11个单位的产品,A2必须发出7个单位的产品;A3至少要发出4个单位的产品。试根据上述条件用表上作业法求该运输问题的最优运输方案。整数规划在一个线性规划中，如果它的全部决策变量或者部分决策变量要求取整数时，这个问题就称为整数线性规划问题，简称整数规划。整数规划中如果所有的变量都限制为整数，就称为纯整数规划。整数规划中如果仅一部分变量被限制为整数，就称为混和整数规划。整数规划中如果变量的取值仅限于0和1，就称为0-1规划。松弛问题IPLP（5.1a）（5.1b）（5.1c）（5.1d）（5.1a）（5.1b）（5.1c）整数规划的例子例1 某服务部门各时段(每2h为一时段)需要的服务员人数见表51。按规定，服务员连续工作8h(即四个时段)为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。时段12345678服务员最少数目10891113853解 设在第j时段开始时上班的服务员人数为xj。整数规划的例子时段12345678服务员最少数目10891113853解 设在第j时段开始时上班的服务员人数为xj。整数规划的例子时段12345678服务员最少数目10891113853解 设在第j时段开始时上班的服务员人数为xj。整数规划的例子时段12345678服务员最少数目10891113853运筹学基础 第二十讲第二十讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48例2 现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj(j=1,2,，n)。此外，由于种种原因，有三个附加条件：第一，若选择项目1，就必须同时选择项目2。反之，则不一定；第二，项目3和项目4中至少选择一个；第三，项目5、项目6和项目7中恰好选择两个。应当怎样选择投项目，才能使总预期收益最大?整数规划的例子整数规划的例子对项目j投资对项目j不投资IPLP（5.1a）（5.1b）（5.1c）（5.1d）（5.1a）（5.1b）（5.1c）整数规划和其松弛问题解的特点割平面法只能用于求解纯整数规划IPLP 割平面法 用割平面法解整数规划时，若其松弛问题的最优解x*不满足(5.3d)，则从x*的非整分量中选取一个，用以构造一个线性约束条件，将其加入L1，形成一个新的线性规划,然后求解之。若新的最优解满足整数要求，则它就是整数规划的最优解；否则，重复上述步骤，直到获得整数最优解为止。例5用割平面求解纯整数线性规划第一步：解整数规划问题的松弛问题，见表5-3，x1=13/7，x2=9/7；割平面法cj3-1000CBXBB-1bx1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70 x431/700-3/7122/700-5/70-3/7表 5-3第二步：写出割平面方程，选择第一行产生割平面约束，cj3-10000CBXBB-1bx1x2x3x4x5x63-100 x1x2x4x613/79/731/7-6/7100001001/7-2/7-3/7-1/700102/73/722/7-2/7000100-5/70-3/703-100 x2x1x3x515/45/27/41000010000100-1/4-1/21/400011-5/4-11/2-3/4000-1/40-17/4表 5-4cj3-1000 00CBXBB-1bx1x2x3x4x5x6x73-1000 x1x2x3x5x41241310000010000010000001000101-1-5-110-1-21-400000-4-1表 5-5原整数规划问题的最优解为，x1=1,x2=2,max z=1割平面法cj3-1000CBXBB-1bx1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70 x431/700-3/7122/700-5/70-3/7表 5-3割平面法割平面法割平面法割平面法运筹学基础 第二十一讲第二十一讲主讲教师：郑黎黎学时：主讲教师：郑黎黎学时：48割平面计算步骤：1.用单纯形法解整数问题IP的松弛问题L0若L0没有最优解，则IP没有最优解。停止若L0有最优解X0:(1)X0是整数解，则X0也是IP的最优解，停止(2)X0不是整数解，转第二步2.求割平面方程割平面法3.将割平面加到L0得L14.解L1在L0的最优单纯形表中增加一行一列，得L1的单纯形表，用对偶单纯形法求解，若其解是整数解，则该解也是原整数规划的最优解否则将该解记为X0，返回第二步割平面法分支定界法分支定界法是求整数规划的常用方法，即可用来求解纯整数规划又可用求解混和整数规划。分支定界法求解整数规划的步骤：步骤1:称整数规划问题为问题A，它的松弛问题为问题B，以Zb表问题A的目标函数的初始界(如已知问题A的一个可行解，则可取它的目标函数值为Zb)。对最大化问题A,Zb为下界;对最小化问题A，Zb为上界。解问题B。转步骤2；分支定界法步骤2：如问题B无可行解，则问题A也无可行解；如问题B的最优解符合问题A的整数要求，则它就是问题A的最优解对于这两种情况，求解过程到此结束。如问题B的最优解存在，但不符合问题A的整数要求，则转步骤3；分支定界法步骤3:对问题B，任选一个不符合整数要求的变量进行分支。设选择 为不超过 的最大整数。对问题B分别增加下面两个约束条件中的一个：和从而形成两个后继问题。解这两个后继问题。转步骤4；分支定界法步骤4：考查所有后继问题，如其中有某几个存在最优解，且其最优解满足问题A的整数要求，则以它们中最优的目标函数值和界Zb作比较。若比界Zb更优，则以其取代原来的界Zb，并称相应的后继问题为问题c。否则，原来的界Zb不变转步骤5；分支定界法步骤5：不属于c的后继问题中，称存在最优解、且其目标函数值比界Zb更优的后继问题为待检查的后继问题。若不存在待检查的后继问题，当问题c存在时，问题c的最优解就是问题A的最优解；当问题c不存在时，和界Zb对应的可行解就是问题A的最优解。Zb即为问题A的最优解的目标函数值，求解到此束。若存在待检查的后继问题则选择其中目标函数值最优的一个后继问题改称其为问题B。回到步骤3。分支定界法采用分支定界法求解下面的整数规划问题Lx1=4.81x2=1.82z0=356问题L1x1=4.00 x2=2.10z1=349问题L2x1=5.00 x2=1.57z2=341X14 X15 问题Lx1=4.81x2=1.82z0=356问题L1x1=4.00 x2=2.10z1=349问题L2x1=5.00 x2=1.57z2=341X14 X15界限值Z b=-问题L1x1=4.00 x2=2.10z1=349问题L4x1=1.42x2=3.00z4=327问题L3x1=4.00 x2=2.00z3=340X22 X23 X22 X23问题L1x1=4.00 x2=2.10z1=349问题L4x1=1.42x2=3.00z4=327问题L3x1=4.00 x2=2.00z3=340界限值Z b=340X21 X22问题L2x1=5.00 x2=1.57z1=341问题L6x1=1.42x2=3.00z4=327问题L5x1=4.00 x2=2.00z3=340X21 X21问题L2x1=5.00 x2=1.57z1=341问题L6无可行解问题L5x1=5.44x2=1.00z5=308例6 求解下述整数规划分支定界法分支定界法第一步：舍弃整数要求，用单纯形法求解，得X(0)=(3/2,10/3),点 A,目标函数值z(0)=29/6（上界），（0，0）显然是一个可行解，目标函数值0（下界）分支定界法第二步，由于x1,x2都不是整数，分解成子问题（分支）。先考虑x1，x1=3/2。（1）（2）X(1)=(2,23/9),B点z(1)=41/9X(2)=(1,7/3),C点,z(2)=10/3(新下界)分支定界法分支定界法第三步，由于z(2)z(1)z(0),z(1)=41/9代替z(0)成为新的上界。此时，问题（2）已探明，结束。问题（1）需继续分支。（3）（4）无可行解，删去（剪枝）X(4)=(33/14,2),D点，z(4)=61/14分支定界法分支定界法第四步，由于z(2)z(4)n工作人费用1 2 j n12imn+1 n+2 m 用匈牙利法求解非标准化指派问题工作人费用1 2 j n12imm+1 m+2 n (b)mn用匈牙利法求解非标准化指派问题一个人可做几件事的指派问题设n个人中的第k个人可同时做t件事：把第k个人视为t个人，这t个人做同一件事的费用系数都一样问题化为人数为n-1+t个人的指派问题某人一定不能做某事的指派问题如在minZ问题中，第k个人一定不能做第t件事：如在maxZ问题中，第k个人一定不能做第t件事，非标准化指派问题动态规划|某些问题的决策过程可以划分为几个相互联系的阶段，每个阶段都有若干种方案可供选择，而决策的任务就是在每个阶段选择一个适当的方案，从而使整个过程取得最优效果，动态规划就是解决这样多阶段决策问题的运筹学方法。|动态规划是运筹学的一个分支，是 1951年美国数学科学家贝尔曼（R.Bellman）等人提出的。动态规划|动态规划广泛应用于经济、管理、军事、工程技术等方面，解决很多实际问题，如可用于解决资源分配问题、生产与存储问题、背包问题、复合系统工作可靠性问题、设备更新问题、排序问题、货郎担问题等等。|动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不像线性规划那样有一个标准的数学表达式和明确定义的一组求解规规则，它没有统一的处理方法，必须对具体问题具体分析处理，在分析时还需要大量的经验和技巧。多阶段决策问题|所谓多阶段决策问题，是指这样一类活动过程：即根据问题本身的特点，可以将其求解的全过程划分为若干个相互联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到指标最优 多阶段决策问题 各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响后一个阶段的状态，从而影响后一阶段的决策，进而影响整个过程的总指标。因此，在每个阶段进行决策时，不能仅仅从局部利益出发，而是要从系统所经过的整个区间的总指标出发。当各个阶段决策确定后，就组成了一个决策序列，找到了多阶段决策过程的最优解。多阶段决策问题|在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生的，故有“动态”的含义。因而把处理它的方法称为动态规划方法。|但是，一些与时间没有关系的静态规划（线性规划、非线性规划等）问题，只要人为地引进“时间”因素，也可以把它视为多阶段决策问题，用动态规划去处理。多阶段决策问题|例1（最短路问题）如下图所示，给定一个线路网络图，要从A地向F地铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短?多阶段决策问题|例2 设备更新问题 某厂新购某种机床125台。据估计，这种设备5年后将被其它设备所取代。此机床如在高负荷状态下工作，年损坏率为1/2，年利润为10万元；如在低负荷状态下工作，年损坏率为1/5，年利润为6万元。问应如何安排这些机床的生产负荷，才能使5年内获得最大利润。多阶段决策问题|例2分析 本问题具有时间上的次序性，在五年计划的每一年都要做出关于这些机床生产负荷的决策，并且一旦做出决策，不仅影响到本年的利润多少，而且影响到下一年初完好机床数，从而影响以后各年的利润。所以在每年初作决策时，必须将当年的利润和以后各年的利润结合起来，统筹考虑。例3 生产与存贮问题 某工厂生产并销售某种产品，已知今后四个月市场需求预测如表7-7，又每月生产j单位产品费用为：C(j)=0(j=0)3+j(j=1,2,，6)(千元)每月库存j单位产品的费用为E(j)=0.5j(千元)，该厂最大库存容量为3单位，每月最大生产能力为6单位，计划开始和计划期末库存量都是零。试制定四个月的生产计划，在满足用户需求条件下总费用最小。假设第i+1个月的库存量是第i个月可销售量与该月用户需求量之差；而第i个月的可销售量是本月初库存量与产量之和。多阶段决策问题动态规划的基本概念和基本原理|动态规划的基本概念阶段 动态规划问题通常都具有时间或空间上的次序性，因此求解这类问题时首先要将问题按一定的次序划分成若干相互联系的阶段，以便能按一定的次序求解。描述阶段的变量称为阶段变量，常用k表示。如例1可以按照空间次序划分为ABCDE F五个阶段，k1，2，3，4，5；例2可以按照时间次序划分为5个阶段k1，2，3，4，5。动态规划的基本概念和最优性原理|动态规划的基本概念状态状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况，是进行决策的依据。描述过程状态的变量称为状态变量记第k阶段的状态变量为sk，它可以用一个数、一向量来描述。动态规划的基本概念和最优性原理|在例1中状态表示某阶段的出发位置，是选择后续路线的依据，第一阶段有一个状态就是A，s1=A；第二个阶段有两个状态，s2可取两个值，即B1和B2,，点集合B1,B2,就称为第二个阶段的可达状集合，通常一个阶段有若干个状态。|例2中每年年初拥有的完好机床数是做出机床负荷安排的依据，所以k年初完好机床数是状态。动态规划的基本概念和最优性原理|动态规划的基本概念状态这里的状态应具有如下性质：如果某阶段状态确定后，则在这个阶段以后的过程发展不受这个阶段以前各阶段状态的影响。换句话说，过程的过去历史只能通过当前的状态去影响它未来的发展，当前的状态是以往历史的一个总结。这个性质称为无后效性（即马尔可夫性）。动态规划的基本概念和最优性原理如何判断状态是否满足无后效性多阶段决策过程的发展是用各阶段的状态演变来描述的，则可以这样判断选择的决策变量是否满足无后效性：下一个阶段的状态只与这个阶段的状态和决策有关，与这个阶段以前各阶段状态无关。而决策变量是促使状态发生演变的，因此也可以这样判断选择的决策变量是否满足无后效性：这个阶段的决策只和这个阶段的状态有关，与该阶段以前各阶段状态无关；动态规划的基本概念和最优性原理|动态规划的基本概念状态如例1，当某阶段选定某状态点后，这个点以后的路线情况，即各阶段状态，只与该点有关，不受以前线路的影响，不受以前各阶段状态影响，满足状态的无后效性。动态规划的基本概念决策阶段决策就是决策者从某状态出发对下一阶段状态所做出的选择。描述决策的变量称为决策变量，一般，在某阶段的决策受这一阶段的状态影响，因此，决策变量是状态变量的函数，决策变量记为uk(sk)，它可以用一个数、一向量来描述。在实际问题中，决策变量的取值往往限制在某一范围内，此范围称为允许决策集合，常用Dk（sk）表示第k阶段从状态sk出发的允许决