管理运筹学考试题型整理

线性规划问题一、建模(除排队论，都可以线性规划)关键：决策变量（维度），目标函数、约束条件；a,b,c例：例：某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，这些产品分别需要在A、B、C、D四种不同的设备上加工。按工艺规定：产品Ⅰ和Ⅱ在个设备上所需要的加工时数于下表中。已知各设备在计划期内的有效台时数分别是12、8、16和12。该工厂每生产一件产品Ⅰ可得利润2圆，每生产一件产品Ⅱ可得利润3圆，问：应如何安排生产，可获得最大利润。设备产品ABCDⅠ2142Ⅱ3214解设生产产品Ⅰ和Ⅱ分别为1x和2x件，则由条件可得关系max1223zxx121212122312284162412xxxxxxxx0,1,2ixi练习：二、转化为标准型关键：决策变量≥0，目标函数Max、约束条件=（b≥0）三、图解法（两维）关键：纵轴X2系数的正负，目标求大求小Max(Z)Min(Z)X20X20例用图解法求解线性规划问题极大化Max1223zxx(??min或-3x2)121228416412xxxx0,1,2ixi解：最优解(4,2),14Xz四、简单计算(包括大M法,两阶段法)关键：标准型转化，步骤（换基，入基，“Xb=B”）例用单纯形法求解线性规划极大化123235zxxx123123725310xxxxxx0,1,2,3ixi解引入松弛变量54,xx，得到原规划的标准型极大化5123423500zxxxxx12345123725310xxxxxxxx0,1,2,3,4,5ixi单纯形表为12345452523500111107253011023500011110770851451083021xxxxxxcxxxx所以，最优解为,(0,7,0)t最优解值为21.利用大M法或两阶段法求解下列问题五、复杂计算关键：目标函数和检验数(Z1新和Z0旧的对比)Max(Z)Min(Z)Cj-ZjσZ1-Z0**Zj-CjσZ0-Z1六、解类型的判断关键：七、填表题关键：（若干行变换）左乘B-1，基变量对应的I，2-4已知某求极大值线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如表所示，求表中各括弧内未知数的值。cj→322000CB基bx1x2x3x4x5x60x4（b）1111000x515(a)120100x6202(c)1001cj→zj322000︰︰0x45/400（d）(l)1/41/43x125/410（e）03/4（i）2x25/201（f）0（h）1/2cj→zj0（k）（g）0-5/4（j）求解I,kI=1K=011-1/4-1/403/4i0h1/2B,_1520bbfirst,5/4_25/45/2blater__blaterBbfirst,即5/41-1/4-1/425/403/4i155/20h1/220b得出：15*h+20/2=5/2h=-1/2或（另一种方法：0-3*3/4-2*h=-5/4h=-1/2）b-15/4-20/4=5/4b=40/4=1015*3/4+20*i=25/4i=-1/4于是：11-1/4-1/403/4-1/40-1/21/2B，10_1520bfirst，5/4_25/45/2blater之后：101-1/4-1/411'1103/4-1/400-1/21/22PBPa1-1/4*a-1/4*2=0a=2101-1/4-1/412'2003/4-1/4110-1/21/2PBPc1-1/4-1/4*c=0c=310111100_|1521201020231001bfirstA'1'1-1/4-1/410111100_|_|03/4-1/4152120100-1/21/220231001blaterABbfirstA'5/4001/411/41/4_|25/4105/403/41/45/2011/201/21/2blaterA得出：1/45/41/2def于是得出：g=2-3*5/4-2*(-1/2)=-3/45..已知下表为求解某线性规划问题的最终单纯形表，表中x4和x5为松弛变量，问题的约束为≤形式。x1x2x3x4x5x35/201/211/20X15/21-1/20-1/61/3cjzj040-4-2（1）写出原线性规划问题对偶问题八、写出对偶问题关键：口诀例求下面问题的对偶规划极大化Max12343257zxxxx1234134123423272+223248xxxxxxxxxxx12340,0,0,xxxx无非负限制。解极小化Min123238wyyy12313123123223322245727yyyyyyyyyyy1230,0,0yyy九、对偶单纯型法关键：与传统互置（翻）十、利用对偶性质广泛：如(1)对称性(2)弱对偶性CX≤Yb;(3)无界性(4)可行解相等是最优解;(5)对偶定理都有最优解；且目标函数值相等;(6)兼容性，松弛变量-变量，剩余变量-原变量；(7)互补松弛性.（8）对偶变量的经济含义1）..已知下表为求解某线性规划问题的最终单纯形表，表中x4和x5为松弛变量，问题的约束为≤形式。x1x2x3x4x5x35/201/211/20X15/21-1/20-1/61/3cjzj040-4-2（1）写出原线性规划问题（2）写出原问题的对偶问题。（3）直接由表写出对偶问题的最优解。2、已知线性规划问题（20分）0,06422m21321321321xxkxxxxxxxxxinz其最优解为xxx12501,,31．求k的值；2．求出对偶问题的最优解一、解：写出原问题的对偶问题得021264max2121212121'yykyyyyyyyyZ无约束，由互补松弛定理：011syx得2,0211yyys①033syx得2,0213kyyys②①②联立得kykky14*,126*21而**,'*,12*21yyZZ将代入③12*6*421yy③则2*,6*,321yyk综上，3k，对偶问题最优解为TTyyY)2,6(),(*21敏感性分析除了单纯性表，运输问题等许多问题都可以敏感性分析关键：找到B-1，“左乘”b变动C变动A变动出现新系数，最优解变化最优不变的区间范围△C，A同时变化B,C,A同时出现变化——引入一行新约束（）十一、B变动；（2）若b2变为30，求新的最优解15≤b2≤25时，最优基不变。变化后基变量的取值为:两种求解方法，1）直接相乘；2）B’+△B’*1*111400510501120105101500115015015BXBb十二、C变动；注：也可以直接让2+λ=K(△c1)十三、a变动(有时C同时变动)；1）增加一个新产品2）技术变革后面利用对偶单纯型法，大M法，两阶段法十四、B,C,A同时出现变化——引入一行新约束（）运输问题十五、运输问题建模；关键：明确产地（输出）和销地（输入），变量、约束和目标运输问题：产地、销地、产量、销量引例：有A1，A2，A3三座铁矿，每天要把生产的铁矿石运往B1，B2，B3，B4四个炼铁厂。各矿的产量、各厂的销量以及各厂矿间的运价如下表所示。问应如何组织调运才能使运费最少？B1B2B3B4产量A1A2A3632575843297523销量2314十六、供求“平衡”下的表上作业法；关键：明确计算方法，初始方案→最优方案（基变量，非基变量，检验数）（1.西北角法2.最小元素法3.Vogel法→1.闭回路法σ2.位势法σ）例求下面运输问题的最小值解：12341311310721923437410593656重新计算位势及影响系数，得下表：v1=3v2=4v3=3v4=51234u1=01311310725u2=-221923413u3=037410596336561214222331337,5,7,1,4,7，此时，0ij，故当前解为最优解。最优解值为：32351133465370Y十七、供求“不平衡”下的表上作业法；关键：使之平衡，增加０或Ｍ十八、敏感性分析；关键：设变量，求检验数4314513另外，有求范围的，我们以前做过十九、最大化问题（如收益，利润）；关键：最大数一各个运价二十、转运下的运输问题；关键：加上总运转量随便运输整数规划二十一、分支定界法；关键：上界，下界，范围缩小，剪枝运输问题：产地、销地、产量、销量二十二、割平面法；关键：等号一边为整数，另一边为“真”分数；可用原变量X表示;真分数大的收敛性好二十三、0-1规划———建模；关键：基本形式y1+y2=1,∑b*y1，M*y（相互排斥的计划、约束条件，固定费用）二十四、0-1规划——隐枚举法；关键：（Max）从大到小，设定门槛(后设)，01互换并剪枝二十五、0-1规划——分支定界法；关键：（Max）从大到小，01互换并剪枝,非可行解另外：二十六、指派建模；关键：目标，约束，变量(二维)，近似运输运输问题：产地、销地、产量、销量二十七、指派基本求解；关键：横列最少取０（m个０），口诀（m）3、某公司要把4个有关能源工程项目承包给4个互不相关的外商投标者，规定每个承包商只能且必须承包一个项目，试在总费用最小的条件下确定各个项目的承包者，总费用为多少？各承包商对工程的报价如表2所示：（15分）项目投标者ABCD甲15182124乙19232218丙26171619丁19212317答最优解为：X=0100100000100001总费用为50二十八、指派—人数与任务不等（非标准型）；关键：增加０或Ｍ，补全（１人可多做任务；一定要做，一定不能做）四、从甲,乙,丙,丁,戊五人中挑选四人去完成四项工作，已知每人完成各项工作的时间如下表所示。规定每项工作只能由一个人去单独完成，每个人最多承担一项工作，假定甲必须保证分配到工作，丁因某种原因不同意承担第四项工作。在满足上述条件下，如何分配工作，使完成四项工作总的花费时间最少。人工作一二三四甲1051520乙210515丙3151413丁15276戊94158一、解：1051520M831012M5079M-32105150080700807031514130~113950~113950~1527M01302M-801302M-809415807210007210004068M-3090710138401201M-90731001此时，费用最小，218553*Z其中，丙一，甲二，乙三，戌四二十九、指派－极大下的指派问题（非标准型）；关键：最大数减去所有数，不能做的用Ｍ目标规划三十、建模；关键：Min目标(d+,d-,d++d-)，约束，变量(“维度”)----适用所有的内容6.某彩色电视机组装工厂，生产A，B，C三种规格电视机。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为6，8和10小时。生产线每月正常工作时间为200