运筹学笔记.doc

运筹学笔记第1章4 单纯形法的计算步骤1.单纯形表标准化方程组P1P2P3P4P5备注Cj-1-2-100表12.确定出基变量：取min，L为出基的行，标 CBXBX1X2X3X4X5b0X42-321015-0X51315016020 Cj-CbPj-1-2-100表2判断：1.对于min问题，当所有检验数0时达到最优(对于max问题则相反)。2.对于max问题，若某个检验数且某个基变量系数时，问题有无界解（对于min问题则是且时）0X43017117525 -2X21502060Cj-CbPj090表3-1X11025-2X201检验数00备注换基迭代 1.选择进基变量：对于max问题，若max，则K列变量进基（对于min问题则相反）对于min问题，当所有检验数j0时达到最优(对于max问题则相反)解得 2.人工变量法（大M法）（人工变量法中如有最优值，则人工变量必为0）引入辅助模型目标函数【若是求max，则目标函数化为 （其中M表示充分大的正数，为人工变量）若是求min，则目标函数化为 约束条件为添加人工变量后的约束】【例6】 用单纯形法求线性规划问题解：引入辅助模型 ，取基 ，基变量cj0100CBXBx1x2x3x4x5y1y2b0x4111100044y1101011y2031000199Cj-CbPj10000x4302110310x21001y260403161Cj-CbPj6M304M+103M00x400011/200x2011/300393x1102/301/213/2Cj-CbPj00303/20x400011/200x21/21001/45/21x33/20103/43/2Cj-CbPj9/20003/4人工变量在迭代中一旦出基不可能再进基，所以某人工变量出基后，列系数可以不参与计算。解得辅助模型的最优解所以原问题的最优解为当辅助问题的最优解中存在某人工变量，则原问题无可行解。第2章2 原问题与对偶问题原问题（LP1） 对偶问题（LP2） 原问题（对偶问题）对偶问题（原问题）方向相（反）方向相（同）方向相（反）（大）目标函数 max（变）变量n个（约）约束m个 约束条件右端项（小）目标函数 min（约）约束n个（变）变量m个 目标函数中变量的系数1. 弱对偶性.存在原问题、对偶问题的可行解 则有2. 最优性（4.强对偶性，又称对偶定理）（可逆）如果原问题有最优解，则其对偶问题也一定有最优解，且有3. 无界性.原问题（对偶问题）-对偶问题（原问题）有无界解不可逆无可行解无可行解无可行解或有无界解5. 互补松弛型如果 则如果 则P78 2.4 已知线性规划问题：要求：（a）写出其对偶问题；（b）已知原问题最优解为，试根据对偶理论，直接求出对偶问题的最优解.解：原问题的对偶问题：原问题最优解为，由对偶问题的互补松弛性可得将代入原问题知原问题的第4个约束为严格不等式，即由互补松弛性得所以解得即对偶问题的最优解为第3章2 表上作业法步骤：1. 求初始基可行解（初始调用方案），常用方法有最小元素法和Vogel法；2. 求非基变量的检验数，判断是否达到最优。一般的运输问题求极小值，当所有检验数时达到最优。（求检验数方法：1.闭合回路法，2.位势法）2-1Vogel法步骤：从运价表上分别找出每行与每列的最小的两个元素之差再从差值最大的行或列中找出最小运价确定供需关系和供应数量.当产地或销地中有一方数量上供应完毕或得到满足时，划去运价表中对应的行或列，再重复上述步骤.一般当产销地的数量不多时，Vogel法给出的初始方案有时就是最优方案，所以Vogel法有时就用作求运输问题最优方案的近似解.表3-14产地销地B1B2B3B4产量两最小元素之差A13x11x351027|7|7|7|00007A2139x2x814|4|4|1|01116A37x4610x539|3|012销量3|3|3|06|05|5|5|5|06|6|3|3|0两最小元素之差25132132112-21. 闭合回路法.运输问题中的闭回路是指调运方案中由一个空格和若干个有数字格的水平和垂直连线包围成的封闭回路.求某非基变量的检验数：以该非基变量为起点，其他基变量为顶点，找一个闭合回路（唯一的）由起点开始，分别在顶点上交替标上代数符号“+”、“”，用这些符号分别乘以相应格的运价，其代数和就是该非基变量的检验数.表3-15产地销地B1B2B3B4产量A1（[phone]A23(-1)11(+1)24A3764359销量3656对应(A3，B1)的检验数为（7-1+2-3+10-5）=10*设产地m个，销地n个，则最优方案的基变量个数必为m+n-1个.2. 位势法.令，在基变量处根据(运价)求出各，的值，然后在非基变量处根据求各基变量的检验数.表3-21产地销地B1B2B3B4A13101A2120A3()45-41829当所有检验数时得到最优调运方案，否则需要调整运量.3.调整运量（有检验数时）1确定进基变量，若，则进基.2确定出基变量，在进基变量的闭合回路中，以标有“”的最小运量作为调整量，对应的基变量出基.3调整运量，在进基变量闭合回路中，标有“”的运量加上调整量，标有“”的运量减去调整量，出基变量处运量留空，其他地方运量不变.例 产地销地B1B2B3B4产量A155 +865(3)9(2)2700A2330(0)6450(9)780-2A31010(-1)12(4)15530405销量456550305860=10，调整运量后产地销地B1B2B3B4产量A1515 855(3)9(1)2700A2330(0)6450(8)780-2A3(1)101210(5)15530404销量456550305861，.所有检验数，运输调运方案最优.2 产销不平衡的运输问题及其应用产大于销，用最小元素法.P102 表3-36产地销地B1B2B3B4产量A184127A2694725A3534326销量10102015产量=7+25+26=58，销量=10+10+20+15=55该运输问题产销不平衡.给该运输问题添加库存变量产地销地B1B2B3B4库存量B5产量A18x4x172x0x7A2699x4137x0325A3513104x3150x26销量101020153取产地销地B1B2B3B4库存量B5产量A18x4x172x0x70A2699x4137x03253A3513104x3150x262销量1010201533111-3，.所有检验数，问题达到最优.第4章1 整数规划与分配问题1. 整数规划：1） 纯整数规划：要求全部变量取整数.2） 混合整数规划：要求部分变量取整数.3） 0-1规划：全部变量取0，1.（枚举法）2.整数规划的特点1）如果松弛问题的最优解是整数解，则松弛问题的最优解也是原整数规划的最优解.2）如果松弛问题的最优解不是整数解，则松弛问题最优解与原整数规划最优解无关.整数规划如 对应的松弛问题 3. 逻辑变量（0-1变量、二进制变量）1）m个约束条件中只有k个起作用设m个约束条件可表示为：定义又M为任意大的正数，则2） 约束条件的右端项可能是r个值（）中的某一个，即定义上述约束条件可表示为3） 两组条件中满足其中一组若引入0-1变量，则2 分配问题与匈牙利法2-2 匈牙利法匈牙利法：1）问题为求极小值 2）人数和工作数相等 3）效率矩阵非负匈牙利法的计算步骤：第一步：找出效率矩阵每行的最小元素，并分别从每行中减去，有第二步：再找出效率矩阵每列的最小元素，再分别从各列中减去，有第三步：覆盖零元素的最少直线数为n时（工作数），寻找独立零元素，写出最优解，否则需要第四步的矩阵变换第四步：1） 从矩阵未被直线覆盖的数字中找出一个最小值k；2） 对矩阵的每行，当该行有直线覆盖时，令，无直线覆盖的，令；3） 对矩阵中有直线覆盖的列，令，对无直线覆盖的列；4） 从原矩阵的每个元素中分别减去和，得到一个新矩阵.