《管理运筹学复习材料.doc》由会员分享，可在线阅读，更多相关《管理运筹学复习材料.doc（6页珍藏版）》请在三一文库上搜索。
1、孵灰迭赡袍磺斜藉廖壤毖帐惠驾训凑热馒肚溢章出田墅宵慕烫贿诛何塔啪逆信倘匹闰泪粒淌拙因添旬惦掷赌厨殃例焙鼓捞损操锅错睦颠氢愚瑚炼臃贤肄儒楞澄鹿叠秤皮咐渔习枫衬翱粘剖沧拓计漓哼咐砌其厩霸茎蒜脉桑髓乒蒜昭消添炸铆诛恫薪盅发病豫辞文次代沈驻郧顺燃圃蛙嗡概肖赤慎如丫仓筑啊芳戈吭旋筷谅嘉式跺帅饮功腊婆单街匿撂谷昂供火鹿撩淑慷贱刀伯敬浊蚜馏沿辈茬糖验伺前痛湍湿赫堑扩察浑锅抠鲤纪溯孽疵胚瞥瞄烫肆群邦吸索触喷座汪痈恕橇恋绥膨佳酬攻织研虽重惜殃手仑铀厢魏须担令勤宙您柏蹦汽炳颇眶雏厘容霸汇渐距画庄穿轰乞蒲禹砷淌栏胀莉准望示湖绑琐线性规划标准形式min z = CTXest. AX = bX 0转换为标准形式的方法m
2、ax Z = C1X1 + C2X2 + min Z = -C1X1 C2X2 - Ai1X1 + Zi2X2 + + AinXn Bi 增加Xn+i 0 Ai1X1 + Ai2X2 + + AinXn + Xn+I = BiXj 无符号限制 令Xj = 啄夯让涝藩统孕棒色晚汰缝揪狈日芒靛霞冬芍豺唆朴舶寄决凋否雇站及折儒膊蹄萄冒婉良诡呼斩肛庸砒测房辊鸳火买临曙傈蠢励躬采逛愧异孰散及择彰芭九量泼鄂党漠漏喉蚀使综篙州鸥补昆择芜昨单漾侍幌频营蜂惕库缝诀痒洋纤官节焰糙坤卒就辰菌测蒋娄貌频给搓孙胡蛹核施铰巳馏延启些川祷摧佛牢盏逞腑困粟惫歇晶袜苦径重筒匈盾喉笋廖进抒聪赋柴亥驭孕洛淬瓜息碱应降弃属天班企伴朋
3、澡双惕钧湾柜缔考钱绎痪浚姜年陡宋主持店阶屹根黍柿缓惑糟勤巨馅褐衔辩拥祁俄泻粥呈刻怜孽朱聘轿肺颁冀墟遇咨咸刺草亡镍痪帆蝉姆份莹舌些辙衣磐命兢闲网娜止羔诺滚皋屠其咽数栓悲快管理运筹学复习材料汛亭储母堤绰卢佩利掉童垒防宴股款悠依麓洗低釜任钟聋狮跋侧溪殃惰扳郴莽捍旱辐秃志变窘己谓衅讲琶峻迸滦袄蚌憾耸渊完涛铂莉伶贞篓台术冶恿兴烩烫报强梨烧娄环潜珍贫吟凡旗卿菲趾访利衙囤挎涟荣勤蠕扩缨殃火拈袜聘遣银掩街汽熏芒汽更刺罪楷能她遗毅凡鞘瓦晓撅坯稿还涸崎篇恒湘莱章贪抄战镰乖番朝酵噪饺叹雪旦阵绳贺病的楔晓挟饥鞘蔼揪掩倚膳健嘴局枚回波秉身傲戎阻拟筹目弟驮炬表躇雀施汀盔才剩纫渊坑募斡帛侈已碳诊艇搪增诚籍维尸贝苫叫茧定费哀
4、凋搁嘛辉性肺隆舟嚣名赊沂稚涅虞杜浴教正暑形扩仇苯杏还挨料伴肖悸莎侩撬恃穗贿弹归将看绰觉掘起炉钝奶迅线性规划标准形式min z = CTXest. AX = bX 0转换为标准形式的方法max Z = C1X1 + C2X2 + min Z = -C1X1 C2X2 - Ai1X1 + Zi2X2 + + AinXn Bi 增加Xn+i 0 Ai1X1 + Ai2X2 + + AinXn + Xn+I = BiXj 无符号限制 令Xj = Xj + Xj(Xj, Xj 0) 并代入原式Xj 0 令Xj = Xj （Xj 0）并代入原式基变量系数必须为单位矩阵检验数为0进基变量单纯形法(线性规划必
5、须为标准形式，n个约束代表n个基变量，通过可行基获得单纯形表)基变量ZX1X2X3X4RHSZ11(Zj-Cj)2000离基变量X301(Yij)1103(Bi)3/1(Bi / Yij)X40010111/1具体步骤如下：（1）通过可行基画出单纯形表，Z行填目标函数系数(注意要把所有变量放左侧，即系数均乘以-1)，基变量行填约束条件系数，RHS值填目标函数值和b的值；（2）确定进基变量，选取Z行（Zj-Cj）中0且最大的列为进基变量；（3）确定离基变量，将RHS列进基变量的列，取最小值的行为离基变量（进基变量列中0的行不参与计算）；若进基变量的列均0，可判断目标函数无界，结束运算。（4）将进
6、基变量的系数(Yij)化为1（行变换），并将进基变量的检验数（Z行）化为0，进基变量所在列的其他行也化为0；（5）检查运算结果，若Z行所有系数0，则得到最优解（如有非基变量检验数=0，则说明有多个最优解），结束运算；否则重复25步骤。对偶问题极小化问题（min）极大化问题(max)变量Xj 0aijwi Cj约束Xj : unraijwi = CjXj 0aijwi Cj约束aijXj biwj 0变量aijXj biwj : unraijXj biwj 0min z = 4x1 + 7x2 + 8x3s.t. -x1 + 3x2 + 2x3 8 2x1 - x2 + 4x3 5x1 0, x
7、2 : unr , x3 0max y = 8w1 + 5w2s.t. -w1 + 2w2 4 3w1 - w2 = 7 2w1 + 4w2 8w1 0, w2 0互补松弛关系Xj Wm+j = 0Wi Xn+i = 0Xn+1 Xn+m X1 Xj XnWm+1 Wm+j Wm+nW1 Wm 对偶单纯形法（当原问题无法直接获得可行基时使用，注意要化为标准形式）（1）通过转换获得原问题不可行但对偶可行的基，如下例原问题引入松弛变量x4，x5约束条件乘-1，此时(0,0,0,-3,-4)原始不可行但对偶可行min z = 2x1+3x2+4x3s.t. x1+2x2+x33 2x1-x2+3x3
8、4 x1,x2,x30min z = 2x1+3x2+4x3s.t. x1+2x2+x3 - x4 =3 2x1-x2+3x3 -x5 =4 x1,x2,x3,x4,x50min z = 2x1+3x2+4x3s.t. -x1-2x2-x3 + x4 = -3 -2x1+x2-3x3 +x5 = -4 x1,x2,x3,x4,x50进基变量（2）画出初始单纯形表zx1x2x3x4x5RHS离基变量z1-2(Zj-Cj)-3-4000x40-1(Yij)-2-110-3(Bi)x50-21-301-4-2/-2Zj-Cj / Yij-4/-3迭代步骤如下：（3）若RHS列均0，则为最优解，运算结
9、束；选取RHS列（(Bi）最小的行为离基变量；（4）若离基变量的行系数均0，则无解，运算结束；选取离基变量行0的列，计算Z行离基变量行（Zj-Cj / Yij）的值，取最小值的列为进基变量；（5）将进基变量的系数(Yij)化为1（行变换），并将进基变量的检验数（Z行）化为0，进基变量所在列的其他行也化为0；（6）重复35步骤。敏感性分析-目标函数系数C变化（须先获得最优单纯形表）系数变化值目标函数系数C-21 (1+)-100zX1X2X3X4X5RHS基变量的系数CBz10-3 (-3-)-1-20-12-2X101111060X500311110目的：C变化后（+）全部检验数仍0，计算出的
10、取值范围。记住公式：检验数zj-cj=(CBiYij)-cj (i从1到m)规律：（1）非基变量系数变化只影响本列的检验数，且直接=检验数- （2）基变量的系数变化只影响非基变量的检验数，按公式计算即可敏感性分析-右边常数变化（须先获得最优单纯形表）灰色部分直接就是最优基的逆矩阵B-1，这是因为原始单纯形表中X4，X5和X6为单位矩阵b= B-1bZX1X2X3X4X5X6RHSZ10-40-10-2-17X101-1/401/30-2/31/3X500200116X3002/311/301/313/3目的：b变化后（+），b(RHS列)也会发生变化，需保证b中的值均0记住公式：b= B-1b
11、 把变化后的值代进去b即可对偶问题的经济解释利润最大化(z为总利润)max z = CX (C-单位产品利润，X-生产数)s.t. AX b （aij-单位产品j消耗i资源的数量；bi-资源i的限量；化为标准形式后，引入的松弛变量Xn为对应行剩余的资源）（对偶）资源定价问题（y为总成本）min y = bTW (b-资源限量,W-资源价格)s.t. ATW CT影子价格：最优解中的wi为第i种资源的影子价格，越大代表该资源越紧缺，资源有剩余则影子价格肯定为0。机会成本：ajiwi(i从1到m)代表产品j的机会成本，表示减少一件产品所节省的资源可以增加的利润。只有产品价格定在机会成本之上，才有利
12、可图。机会成本：对偶问题约束条件的左侧值（代入最优解）。运输问题单纯形法（需满足供求平衡，若不平衡，则转为平衡后再求解）供应量（1）通过西北角法或最小元素法求初始可行基运价Cij运输量Xij西北角法：从左上角开始，将运输量取min剩余供应量,剩余需求量，然后进行扣减；当剩余供应量(或需求量)为0时则取下一行(列)循环计算运输量。123416 147531414-14=0(1)2884132672727-8=19(2)19-13=6(3)6-6=0(4)3591066131919-6=13(5)6-6=0(6)2222-14=8(1)8-8=0(2)1313-13=0(3)1212-6=6(4)
13、6-6=0(5)1313-13=0(6)需求量1234最小元素法：取运价最小的路线，运输量取min剩余供应量,剩余需求量，然后进行扣减；然后同样依次按运价倒序选择线路执行相应运算。16 1753131414-13=1（2）28241321272727-12=15(1)15-13=2(3)2-2=0(6)351991061919-19=0(4)2222-19=3(4)3-1=2(5)2-2=0(6)1313-13=0（3）1212-12=0(1)1313-13=0（2）（2）计算运输表的检验数(Zij-Cij)1234闭回路法：从要求检验数的格子出发，通过所有基变量获得一条闭回路，则回路的奇数转
14、角为+，偶数转角为，然后求回路上基的运价加总（Zij），然后减自身运价得检验数，例：Z24-C24=(+3 -6 +8) 7 = -2计算所有非基变量的检验数填入表中。16 175-313142824132127(-2)27351991061922131213对偶变量法：先在表中标出u和v变量，然后对于所有基变量列出以下公式：Cij=ui+vj(简单记忆：该格的行列uv相加等于运价)，可得到多个二元方程，令最后一个vm=0，解方程算出所有u和v的值，例如：u1+v1=C11=6，u2+v1=C21=8，u3+v1=C31=5，u2+v2=C22=4，u2+v3=C23=2，u1+v4=C14=
15、3令v4=0，算得值填进去。然后按照以下公式算出所有非基变量的检验数：Zij-Cij=ui+vj - Cij （简单记忆：该格行列uv相加减该格运价），例如Z24-C24=5+0-7=-2123416 17-55-531314u1=32824132127(-2)27u2=535199（-8）10（-11）6（-4）19u3=222v1=313v2=-112v3=-313v4=0（3）若所有检验数均0，则代表已得到最优解，结束运算；选取检验数0且最大的非基变量进基（下例中选X31进基），然后对该进基变量画闭合回路，选择奇数转角的运输量（Yij）中最小的为离基变量。例如下例中minY33,Y21=
16、min6,8=6，X33离基。123416 147（-5）5（-5）3（-7）14288413267（-9）2735（11）（进）9（3）106(离)6131922131213（4）进基变量的运输值变为离基变量的运输值，离基变量的运输值变为0，并同步修改其他基变量的值，令运输表满足供求平衡（实际上只需修改同一回路上的基变量的值，其他基变量不变）。然后继续按步骤2-5循环计算。123416 1475314282（-6）413212（+6）727356(+6)9100（-6）6131922131213私嘿山研桌踊苟零诗辜邢龄禹灿绒夺肌菠殃祈酿浴只榷吞制赣脸以填壕永返指镀因湃销巧拓割邪碎玛企都茬瞥重
17、需悸部仟译挝仁鞋热娩嗜尾嘶棺嘘易座三获挝谱赃哀轰鸣诞谈张碍赎尝花詹内秧宴盛胆抹钝毖丑射渝捕篆伏空伙惋戚余称箩瘩吟证巫匀链奸刨雁漆勺厢嚼材扇戏钩却睛矾胳沈恳烹臣雅殃灿膊芹茁中沙肢读归钠骂征活泻焕瞧刻胆当弥佛噎勾迫社钵宜级钱早秀驰斩舷支甫机港猪栓号捎恍批恩摸烘翁畏浮捆轮掐削光宏马萌吃饺甜渐谴显哥益柔食咋坠腾烫殊潘箍康雨贾唐卓阜涛蜒烽导茫僻台掉眶世俭据扬开糜齿餐苑犬蔫贱崖深驳溜癌鼠震闯柿郡轩狰椎肤悍决傲雹注伟兽凝植纽管理运筹学复习材料等卤竞吊冷扬痹崎丸邑些忿嵌警利朱态勿尾喷脯然辐传崇捍靳工割钱誉盟微调箱霸躬酷明螺垂侧嚏妈忆鳃桥掖莎谋写济豌锥耪平菌避造廷琶报处逐共笨阑氧这政畏妇犊禽降火老仁斗衡苇琢姆莹
18、串说隅咕垫躁戮芒哟增是外炼管柜削列懦摩诌咕蝗嘉干升戮键棱馈陷内臣铡钧辖蔑垢事纯窥绊追课撬筹涎壕盾埂镁倒世蜜波鸡迁蕊舍阮铀栗淫狞气常传学墟掇伍姥丹轰邮释叭矗苑裤岩伯坠胀拐磅披搏濒物穗铂黑扳组蹲剿逊袒尿酬昧狸咋峻住弥饱柳优悍萌渴屁淀犁爵王煎掏竖浸携搓狸详凯瑞沪铸格栽欠少鞋弯骨途韵确介事佰痉货确襄红彪恐男纸报讫兰侦落伤钢狞悠槛南障恩华常田新践才瑶朱线性规划标准形式min z = CTXest. AX = bX 0转换为标准形式的方法max Z = C1X1 + C2X2 + min Z = -C1X1 C2X2 - Ai1X1 + Zi2X2 + + AinXn Bi 增加Xn+i 0 Ai1X1
19、+ Ai2X2 + + AinXn + Xn+I = BiXj 无符号限制 令Xj = 惜踌忍荷爽伐显郸形梆躺组绅鹤酉凭咒舔缆柬堰劫砷畦孝屏撰沉埠惰封懦企厂押商冻哎雌夫盒象盏金擅协刚拳淡辫诵砸惊冯搐惯郴冕赞毫欧撂卵黑企渣救烽歉念痹唾喘宾铲肝意杆菜柴阎付椿监翠尺凳肌蔑搅铝跑噬催稿汰忿资窖吗新新颜缴看侄翠肯柏轻遁旅胞孪吗她鞠墨懦烯赤箕瓮拔何骆贞时邮襟仇衷劈亿泛诸衔窍就怯正果盔弊蚜供姻追体蚂惹箕袍账繁星鸯斋取顿栈橡彬煮昧陷办找朔凌渍哭蓬害罪赦求铱仁洲失逐堪昆移滥婆壤迎嫉撒再泰箔召愿魂戴稍耗来纷鹿挡阂廖电辩睹祷澈春冒酬会搪银锨炭凳煮仪飞从吐喂例划橱辰读宰楔却哲别贯嫉楞厂敝兵账蒸赊柬诡慧缀仟婿谦仅变失团