管理运筹学考试题型整理

《管理运筹学考试题型整理》由会员分享，可在线阅读，更多相关《管理运筹学考试题型整理（45页珍藏版）》请在装配图网上搜索。

1、线性规划问题一、 建模(除排队论，都可以线性规划)关键：决策变量（维度），目标函数、约束条件； a, b, c 例：例：某工厂在计划期内要安排生产、两种产品，这些产品分别需要在A、B、C、D四种不同的设备上加工。按工艺规定：产品和在个设备上所需要的加工时数于下表中。已知各设备在计划期内的有效台时数分别是12、8、16和12。该工厂每生产一件产品可得利润2圆，每生产一件产品可得利润3圆，问：应如何安排生产，可获得最大利润。 设备产品ABCD21423214解 设生产产品和分别为和件，则由条件可得关系 练习：二、 转化为标准型 关键：决策变量0，目标函数Max、约束条件= （b0）三、 图解法（两

2、维）关键：纵轴X2系数的正负，目标求大求小Max(Z)Min(Z)X20X20 例 用图解法求解线性规划问题 极大化 Max (? min或 -3x2) 解：最优解四、 简单计算(包括大M法,两阶段法)关键： 标准型转化，步骤 （换基，入基， “Xb=B”） 例 用单纯形法求解线性规划 极大化 解 引入松弛变量，得到原规划的标准型 极大化 单纯形表为 所以，最优解为最优解值为21.利用大M法或两阶段法求解下列问题五、 复杂计算关键：目标函数和检验数 (Z1新 和 Z0 旧的对比)Max(Z)Min(Z)Cj-Zj Z1-Z0*Zj-Cj Z0-Z1六、 解类型的判断关键：七、 填表题关键：（若

3、干行变换）左乘B-1， 基变量对应的I，2-4 已知某求极大值线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如表所示，求表中各括弧内未知数的值。c j322000CB基bx1x2x3x4x5x60 x4（b）1111000 x515(a)120100 x6202(c)1001cjz j3220000 x45/400（d）( l )1/41/43x125/410（e）03/4（i）2x25/201（f）0（h）1/2c jz j0（k）（g）0-5/4（j）求解I,kI=1K=0, , , 即得出： 15*h+20/2=5/2 h=-1/2 或（另一种方法：0-3*3/4 -2*h=-

4、5/4 h= -1/2）b-15/4-20/4=5/4 b=40/4=1015*3/4+20*i=25/4 i= -1/4于是：，之后： 1-1/4*a-1/4*2=0 a=2 1-1/4-1/4*c=0 c=3得出：于是得出：g=2-3*5/4-2*(-1/2)=-3/45.已知下表为求解某线性规划问题的最终单纯形表，表中x4和x5为松弛变量，问题的约束为形式。x1x2x3x4x5x35/201/211/20X15/21-1/20-1/61/3cjzj040- 4-2（1）写出原线性规划问题对偶问题八、 写出对偶问题关键：口诀 例 求下面问题的对偶规划极大化 Max 无非负限制。 解 极小化

5、 Min 九、 对偶单纯型法关键：与传统互置（翻） 十、 利用对偶性质广泛：如(1) 对称性 (2)弱对偶性CXYb; (3) 无界性 (4)可行解相等是最优解; (5) 对偶定理 都有最优解；且目标函数值相等; (6) 兼容性，松弛变量-变量，剩余变量-原变量；(7)互补松弛性. （8）对偶变量的经济含义1）.已知下表为求解某线性规划问题的最终单纯形表，表中x4和x5为松弛变量，问题的约束为形式。x1x2x3x4x5x35/201/211/20X15/21-1/20-1/61/3cjzj040- 4-2（1）写出原线性规划问题（2）写出原问题的对偶问题。（3）直接由表写出对偶问题的最优解。2

6、、已知线性规划问题（20分） 其最优解为1求k的值；2求出对偶问题的最优解一、 解：写出原问题的对偶问题得 由互补松弛定理：得 得 联立得 而代入 则 综上，对偶问题最优解为敏感性分析除了单纯性表，运输问题等许多问题都可以敏感性分析关键：找到B-1，“左乘”b变动C变动A变动出现新系数，最优解变化最优不变的区间范围C，A同时变化B, C, A同时出现变化引入一行新约束（）十一、 B变动； （2）若b2 变为30，求新的最优解 15 b2 25 时，最优基不变。变化后基变量的 取值为: 两种求解方法，1）直接相乘；2）B+B 十二、 C变动；注：也可以直接让2+= K (c1)十三、 a变动(有

7、时C同时变动)；1）增加一个新产品2）技术变革后面利用对偶单纯型法，大M法，两阶段法十四、 B, C, A同时出现变化引入一行新约束（）运输问题十五、 运输问题建模；关键：明确产地（输出）和销地（输入），变量、约束和目标 运输问题：产地、销地、产量、销量 引例：有A1，A2，A3三座铁矿，每天要把生产的铁矿石运往B1，B2，B3，B4四个炼铁厂。各矿的产量、各厂的销量以及各厂矿间的运价如下表所示。问应如何组织调运才能使运费最少？B1 B2 B3 B4产量A1A2A36 3 2 57 5 8 43 2 9 7523销量2 3 1 4十六、 供求“平衡”下的表上作业法；关键：明确计算方法，初始方案

8、最优方案（基变量，非基变量，检验数）（1.西北角法2.最小元素法3. Vogel法1.闭回路法2.位势法） 例 求下面运输问题的最小值解：12341311310721923437410593656重新计算位势及影响系数，得下表：v1=3v2=4v3=3v4=51234u1=01311310725u2=-221923413u3=03741059633656，此时，故当前解为最优解。最优解值为：十七、 供求“不平衡”下的表上作业法；关键：使之平衡，增加或 十八、 敏感性分析；关键：设变量，求检验数 3154134另外，有求范围的，我们以前做过十九、 最大化问题（如收益，利润）；关键：最大数一各个运

9、价 二十、 转运下的运输问题；关键：加上总运转量 随便运输整数规划二十一、 分支定界法；关键：上界，下界，范围缩小，剪枝 运输问题：产地、销地、产量、销量二十二、 割平面法；关键：等号一边为整数，另一边为“真”分数；可用原变量X表示; 真分数大的收敛性好二十三、 0-1规划建模；关键：基本形式y1+y2=1, b*y1，M*y （相互排斥的计划、约束条件，固定费用）二十四、 0-1规划隐枚举法；关键：（Max）从大到小，设定门槛(后设)，01互换并剪枝 二十五、 0-1规划分支定界法；关键：（Max）从大到小， 01互换并剪枝 , 非可行解另外：二十六、 指派建模；关键：目标，约束，变量(二维

10、)，近似运输运输问题：产地、销地、产量、销量二十七、 指派基本求解；关键：横列最少取（m个），口诀（P2网络规划三十三、 网络性质；关键：点线的有关系 , 奇点、偶点等1.一个硬币正面为币值，反面为国徽图案。将这个硬币随机掷10次， 如果用树图表示所有可能出现的结果，试问这个树图有多少个节点，多少条边。. . . . 正反解：有个节点，条边3.有八种化学药品A，B，C，D，P，R，S，T要放进贮藏室保管。出于安全原因，下列各组药品不能贮在同一室内：A-R，A-C，A-T，R-P，P-S，S-T，T-B，B-D，D-C，R-S，R-B，P-D，S-C，S-D，问贮藏这八种药品至少需要多少间贮藏室

11、。解：用八个点分别代表八种药品，哪两种药品不能贮于同一室 内，就在代表它们的两个点间连一条边。其中S，P，R两两相邻，必须占用3间贮藏室。与S不相邻，彼此也不相邻的有A，B点，可与S贮于一室。类似可推出此题最少需要3间贮藏室。(不与黑线重合)ABCDPRST三十四、 最小树；关键：破圈法（去大），避圈法（加小），顶点扩充法（连线的最短边在最小支撑树内）大连银行计划采用专用的加密网络将总部的计算机与市内五个区的分支银行的计算机互联起来（不一定是每一个支行都与总部直接相连）。这种专用的加密网络的铺设费用是连接距离的100倍。表8-1给出了总部和五个分支机构之间的连接距离。银行的管理者希望能够在使得

12、所有分支结构和总部都能直接或间接互联的前提下最小化专用网络的铺设费用，请你给出最优的铺设方案。 距离（km）总部分支1分支2分支3分支4分支5总部1.90.711.52.71.6分支11.91.01.12.20.5分支20.71.01.41.22.2分支311.51.11.41.80.8分支42.72.21.21.83.1分支51.60.52.20.83.1三十五、 最短路Dijkstra求解关键：累积值最小，逐一标号（Dijkstra）五、求V1到各点的最短路及最短路径。（20分） 0* 11 9* 10 11 10* 20 11* 21 20 21 21* 21* 28 25* 11 ：

13、9 ： 10 ： 21 ： 20 ： 25 ： 三十六、 最短路Floyed求解关键：算子(+，) ，负权，理解，较小计算三十七、 最短路建模应用关键：累积值最小，逐一标号三十八、 单源和单汇最大流建模；关键：源汇=f，中间点平衡三十九、 单源和单汇最大流求解；关键：增广链，非饱和流+，非零流-（调整-非饱和、非零，原则：最大，近源汇），最大流=最小割 四十、 多源和多汇最大流求解；关键：增加虚拟源点和汇点 四十一、 最小费用最大流；关键：对偶网络（可调整的单位成本，Floyd算法），最短路径确定原网络路线 决策问题四十二、 不确定型决策；关键：乐观, 悲观, 折衷和最小机会损失3）3） S1

14、和S2皆可四十三、 决策树问题；关键：从后向前，方框去枝（方策点），圆圈求均（不同状态 ）某工厂，有六台自动车床同时生产一种产品，这种产品的销售量一直在增加，工厂所面临的问题，是再装一台自动车床，还是让职工加班，通过对市场的调查发现，这种产品在下一年销售量增加的概率是0.656，通过计算，得到下一年两个方案在不同销售量情况下的纯利润如下表所示，那么，在下一年内是加班好，还是再加一台机床更好？请用决策树法说明 销售情况 收益 概率方案销售量增加S1 销售量增加S20.656 0.344装一台A1加班A23.5 2 3.25 2.8答案：本题的目的是想选择一个方案，使工厂在下一年内获得的纯利润最大。（1）画出决策树，如图所示2.984A223.5销售量减少（0.344）销售量减少（0.344）销售量增加（0.656）加班装一台销售量增加（0.656）3.252.8A1S1S2S3S43.0952（2）计算各方案结点的期望值：（3）将各个方案结点的期望值标在相应的结点上。（4）比较各方案结点上的值，从图中我们可以看出，E（A2）大于E（A1），可见在下一年内最优的选择是加班。多点决策问题：四十四、 效用决策问题；关键：费用变效用