运筹学复习大纲1

.约束方程标准化处理：[xx+3x.<4如I：《[2玉+5x2>6,线性规划问题的解：P9线性规划问题的解的判定(尤其对偶问题解的状况)。minZ=3玉+2x2-3x3+4x433.线性规划问题的对偶问题转化(表2.2)：如3.线性规划问题的对偶问题转化(表2.2)：如X]-lx2+3x3+4x3.线性规划问题的对偶问题转化(表2.2)：如<2X]—3%2-IX3-4x4—2石之0,x2<0,x3>z无约束maxW=3%一5y2+2y3Yi+2丫3<3对偶问题:对偶问题:对偶问题:-2yi+y2-3Y3-2<3y1+3y2-7y3=-3

4yl+4y2-4y3=4对偶问题:Yi^0,y220»3无约束4.对偶问题的基本性质：P45-P46重点是性质1—5。如：已知原问题的最优解为X*=(0.0.4),Z=12试求对偶问题的最优解?minW=2y+y2+4y32M+3%+%之1(1)解：对偶问题)3%一%+%<4(2)-5必+6y2+必=3(3)712。,％(。-3无约束将X*=(0.0.4)代入原问题中，有下式：所以，依据互补松弛条件，必有y*产y*2=0,代入对偶问题(3)式，y3=3。因此，对偶问题的最优解为丫於(0.0.3),W=12o5.灵敏度分析：重点分析也的影响。maxZ=5%+4x2%+3x2<90如：2否+々(80仇在什么范围内变化，原最优基不变？或者给定b的值求最优解的变化。V%+x2<45xpx2>0最优基：54000CbXbbxlx2x3x4x50x3250012-55xl351001-14x210010-12C「Zj000-1-3B=(尸3，Pi，P2)解得40助3350,即当必£[40,50]时，最优基B不变。6.初始方案的确定Vogel法、位势法方案的调整。如：已知运输问题的产销平衡表、最优调运方案及单位运价表如下表所示:产股、Bib2产股、Bib2b3b4产量A)A?A305510151015255销量5151510产销平衡表及最优方案地产疝、Bib2b3b4A\1012011A2127920A32141618单位运价表试分析：从A2到B2的单位运价C24在什么范围变化时，上述最优调运方案不变?或者什么状况下有多个最优方案。7.整数规划问题：重点把握割平面法匈牙利法maxZ=x2如:3玉+2x2<6<一3否+2x2<0如:不々>。且为整数对应LP模型的最终单纯形表Cj0100CBXBbxlx2x3x40Xl1101/6-1/61X23/2011/41/4Cj%00-1/4-1/4解：对X2一行，引入割平面方程：-X3+-X4>-43442标准化：X?X4+5,=434412222Cj01000CbXbbXlX2X3X4si0Xl1101/6-1/601X23/2011/41/400Si-1/200-1/4-1/41Cj%00-1/4-1/40CBXBbXlX2X3上4Si0Xl2/3100-1/32/31X21010010X320011-4Cj•幻0000-1对汨一行，引入割平面方程：一%+—与之一34313一222标准化：％+5*2=CbXbbXlX2X3X4SiS20Xl2/3100-1/32/301X21010010

8.目标规划问题：重点理解目标规划为题的建模和图解法求解。0X320011-400$2-2/3000•2/3-2/310000-10CbXbbXlX2X4SiS20XI0100-1011X20010-103/20X3600150-60Si100011-3/2勺为00010-3/2CBXbbXlX2K3X4si$20Xl110001-1/21X210100100X310010-53/20X4100011-3/2Cjlj000010如：已知一个生产方案线性规划模型如下：其中目标函数为总利润，xl,x2为产品A、B产量。现有下列目标:1、要求总利润必需超过2500元；2、考虑产品受市场影响，为避开积压，A、B的生产量不超过60件和100件；3、由于甲资源供应比较紧急，不要超过现有量140。试建立目标规划模型，并用图解法求解。解：以产品A、B的单件利润比2.5：1为权系数，模型如下：图解法求解：（留意需要简洁分析）结论:C（60,58.3）为所求的满足解。.用Dijkstra算法求下图从w到V6的最短路。树的性质、中国邮路问题（欧拉回路、欧拉通路）.最大流问题：福克逊标号法：此时可行流即为最大流流量：3+2=51L对策论：（把握基本概念，最优纯策略的求解，（最大最小和最小最大优势原则））.A、B两人分别有10分（1角）、5分、1分的硬币各一枚，双方都不知道的状况下各出一枚，规定和为偶数，A赢得B所出硬币；和为奇数，B赢得A所出硬币。试据此列出二人零和对策模型。解：G=S，S2;A}15-「A的赢得矩阵4=15-5-10-1010（2）试通过对策分析，