管理运筹学考试题型整理 - 图文

线性规划问题

一、 建模(除排队论，都可以线性规划)

关键：决策变量（维度），目标函数、约束条件； a, b, c

例：

例：某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，这些产品分别需要在A、B、C、D四种不同的设备上加工。按工艺规定：产品Ⅰ和Ⅱ在个设备上所需要的加工时数于下表中。已知各设备在计划期内的有效台时数分别是12、8、16和12。该工厂每生产一件产品Ⅰ可得利润2圆，每生产一件产品Ⅱ可得利润3圆，问：应如何安排生产，可获得最大利润。

设备 产品 Ⅰ Ⅱ

解 设生产产品Ⅰ和Ⅱ分别为x1和x2件，则由条件可得关系

A 2 3 B 1 2 C 4 1 D 2 4 max z?2x1?3x2

?2x1?3x2?12??x1?2x2?8 ??4x1?x2?16?2x?4x?122?1 练习：

xi?0,i?1, 2

二、 转化为标准型

关键：决策变量≥0，目标函数Max、约束条件= （b≥0）

三、 图解法（两维）

关键：纵轴X2系数的正负，目标求大求小 X2>0 X2<0 Max(Z) Min(Z)

例 用图解法求解线性规划问题 极大化 Maxz?2x1?3x2 (?? min或 -3x2)

?x1?2x2?8? ?4x1 ?16

?? 4x2?12 解：最优解X

xi?0,i?1, 2?(4,2),z?14

四、 简单计算(包括大M法,两阶段法)

关键： 标准型转化，步骤 （换基，入基， “Xb=B”）

例 用单纯形法求解线性规划 极大化

z?2x1?3x2?5x3 ?

x1?x2?x3?7

2x?5x?3x?1023?1?xi?0,i?1,2,3

解 引入松弛变量x4,x5，得到原规划的标准型 极大化

z?2x1?3x2?5x3?0x4?0x5

??x1?x2?x3?x4?7 ? 2x?5x?3x?x?10?523?1 单纯形表为

xi?0,i?1,2,3,4,5 xx1x2x3x40100153x50010010710 074521

cx4x5?x2x523?51?1?12?53?2?35171100188?所以，最优解为(0,7,0)t,最优解值为21.

利用大M法或两阶段法求解下列问题

五、 复杂计算

关键：目标函数和检验数 (Z1新 和 Z0 旧的对比) Cj-Zj σ Z1-Z0 Zj-Cj σ Z0-Z1

Max(Z) ** Min(Z)

六、 解类型的判断

关键：

七、 填表题

关键：（若干行变换）左乘B-1， 基变量对应的I，

2-4 已知某求极大值线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如表所示，求表中各括弧内未知数的值。 c j→ CB 0 0 0 基 x4 x5 x6 cj→z j ︰ 0 3 2

求解I,k I=1 K=0

x4 x1 x2 c j→z j 5/4 25/4 5/2 0 1 0 0 0 0 1 （k） b （b） 15 20 3 x1 1 (a) 2 3 2 x2 1 1 (c) 2 2 x3 1 2 1 2 ︰ （d） （e） （f） （g） ( l ) 0 0 0 0 x4 1 0 0 0 0 x5 0 1 0 0 0 x6 0 0 1 0 ?1/4 3/4 （h） -5/4 ?1/4 （i） 1/2 （j） ?1-1/4-1/4??b??5/4???????B?1??03/4i?, b_first??15?, b_later??25/4?

?0h?5/2??20?1/2???????

?5/4??1-1/4-1/4??b???????i???15? b_later?B?b_first, 即?25/4???03/4?5/2??0h??1/2??????20?得出：

15*h+20/2=5/2 h=-1/2 或（另一种方法：0-3*3/4 -2*h=-5/4 h= -1/2） b-15/4-20/4=5/4 b=40/4=10 15*3/4+20*i=25/4 i= -1/4

于是：

?1-1/4-1/4??10??5/4???????B?1??03/4-1/4?，b_first??15?，b_later??25/4?

?0-1/21/2??5/2??20???????之后：

?0??1-1/4-1/4??1???????P1'?B?1?P1??1???03/4-1/4???a? 1-1/4*a-1/4*2=0 a=2

?0??0-1/21/2??2????????0??1-1/4-1/4??1???????P2'?B?1?P2??0???03/4-1/4???1? 1-1/4-1/4*c=0 c=3

?1??0-1/21/2??c????????10111100???b_first|A??15 2 1 2 0 1 0?

?20231001????1-1/4-1/4??10111100?????b_later|A'?B?1?b_first|A'??03/4-1/4???15 2 1 2 0 1 0?

?0-1/21/2??20231001??????5/4001/41?1/4?1/4???b_later|A'??25/4 1 0 5/4 0 3/4 ?1/4?

?5/201?1/20?1/21/2???得出：

?d??e?f???1/4?????5/4??? ???1/2????

于是得出：g=2-3*5/4-2*(-1/2)=-3/4

5..已知下表为求解某线性规划问题的最终单纯形表，表中x4和x5为松弛变量，问题的约束为≤形式。 x1 x2 x3 x4 x5 x3 5/2 0 1/2 1 1/2 0 X1 5/2 1 -1/2 0 -1/6 1/3 ?4 cj?zj 0 0 - 4 -2 （1）写出原线性规划问题

对偶问题

八、 写出对偶问题

关键：口诀

例 求下面问题的对偶规划

极大化 Maxz?3x1?2x2?5x3?7x4

?2x1?3x2?2x3?7x4??2? ??x1 +2x3?2x4??3

??2x1?x2?4x3?x4?8 x1?0,x2?0,x3?0,x4无非负限制。

解 极小化 Minw??2y1?3y2?8y3

?2y1?y2?2y3?3??3y1?y3??2 ?

?2y?2y?4y??5?123?7y?2y?y?723?1

y1?0,y2?0,y3?0

九、 对偶单纯型法

关键：与传统互置（翻）

十、 利用对偶性质

广泛：如(1) 对称性 (2)弱对偶性CX≤Yb; (3) 无界性 (4)可行解相等是最优解; (5) 对偶定理 都有最优解；且目标函数值相等; (6) 兼容性，松弛变量-变量，剩余变量-原变量；(7)互补松弛性. （8）对偶变量的经济含义

1）..已知下表为求解某线性规划问题的最终单纯形表，表中x4和x5为松弛变量，

问题的约束为≤形式。 x1 x2 x3 5/2 0 1/2 X1 5/2 1 -1/2 ?4 cj?zj 0 （1）写出原线性规划问题

（2）写出原问题的对偶问题。

（3）直接由表写出对偶问题的最优解。

2、已知线性规划问题（20分）

x3 1 0 0 x4 1/2 -1/6 - 4 x5 0 1/3 -2 ???? ?minz?2x1?x2?2x3?x1?x2?x3?4?x1?x2?kx3?6x1?0,x2?0

其最优解为x1??5,x2?0,1．求k的值；

2．求出对偶问题的最优解

一、解：写出原问题的对偶问题得

x3??1

?maxZ'?4y1?6y2?y1?y2??2??y1?y2??1?y1?ky2?2?y无约束，y2?0

?1 由互补松弛定理：x1?ys1?0得ys1?0,?y1?y2??2 ① x3?ys3?0 得ys3?0,?y1?ky2??2 ②

①②联立得

y1*?6?2k?4,y2*?1?k1?k

而Z*??12?Z'*,将y1*,y2*代入③

?4y1*?6y2*??12 ③ 则k??3,y1*??6,y2*?2

TTY*?(y,y)?(?6,2)k??312 综上，，对偶问题最优解为

敏感性分析

除了单纯性表，运输问题等许多问题都可以敏感性分析

关键：找到B-1，“左乘” 出现新系数，最优解变化 最优不变的区间范围△ b变动 C，A同时变化 B, C, A同时出现变化——引入一行新约束（） C变动 A变动 十一、 B变动；

（2）若b2 变为30，求新的最优解

15 ≤ b2 ≤ 25 时，最优基不变。变化后基变量的 取值为:

两种求解方法，1）直接相乘；2）B’+△B’

XB*?1?1?1??40?0??5?10???5??????????B?1b*??01?1??20?10???5?10???15?

?001??15?0??15?0??15?????????十二、 C变动；

注：也可以直接让2+λ= K (△c1)

十三、 a变动(有时C同时变动)；

1）增加一个新产品

2）技术变革

后面利用对偶单纯型法，大M法，两阶段法

十四、 B, C, A同时出现变化——引入一行新约束（）

运输问题

十五、 运输问题建模；

关键：明确产地（输出）和销地（输入），变量、约束和目标 运输问题：产地、销地、产量、销量

引例：有A1，A2，A3三座铁矿，每天要把生产 的铁矿石运往B1，B2，B3，B4四个炼铁厂。各矿的 产量、各厂的销量以及各厂矿间的运价如下表所示。 问应如何组织调运才能使运费最少？ B1 B2 B3 B4 产量 A1 A2 A3 销量

6 3 2 5 7 5 8 4 3 2 9 7 2 3 1 4 5 2 3

十六、 供求“平衡”下的表上作业法；

关键：明确计算方法，初始方案→最优方案（基变量，非基变量，检验数） （1.西北角法 2.最小元素法 3. Vogel法 → 1.闭回路法σ 2.位势法σ）

例 求下面运输问题的最小值解：

1 2 3 重新计算位势及影响系数，得下表：

u1=0 1 2 u2=-2 u3=0 2 1 3 3 5 9 7 4 10 5 3 4 1 9 2 v1=3 1 3 v2=4 2 11 v3=3 3 3 v4=5 4 10 7 3 1 3 1 7 6 2 11 9 4 5 3 3 2 10 6 4 10 3 5 7 4 9

四十、 多源和多汇最大流—求解；

关键：增加虚拟源点和汇点

对有多个发点和多个收点的网络,可以另外虚设一个总发点和一个总收点,并将其分别与各发点、收点连起来（见图），就可以转换为只含一个发点和一个收点的网络。sts’t’所以一般只研究具有一个发点和一个收点的网络

四十一、 最小费用最大流；

关键：对偶网络（可调整的单位成本，Floyd算法），最短路径确定原网络路线

决策问题

四十二、 不确定型决策；

关键：乐观, 悲观, 折衷和最小机会损失

3）

3） S1和S2皆可

四十三、 决策树问题；

关键：从后向前，方框去枝（方策点），圆圈求均（不同状态 ）

某工厂，有六台自动车床同时生产一种产品，这种产品的销售量一直在增加，工厂所面临的问题，是再装一台自动车床，还是让职工加班，通过对市场的调查发现，这种产品在下一年销售量增加的概率是0.656，通过计算，得到下一年两个方案在不同销售量情况下的纯利润如下表所示，那么，在下一年内是加班好，还是再加一台机床更好？请用决策树法说明 销售情况 收益 概率 方案 装一台A1 加班A2 销售量增加S1 销售量增加S2 0.656 0.344 3.5 2 3.25 2.8 答案：本题的目的是想选择一个方案，使工厂在下一年内获得的纯利润最大。

（1）画出决策树，如图所示 销售量增加（0.656） 2.984 S1 A1 装一台 销售量减少（0.344） S2 3.0952 销售量增加（0.656） 加班 S3 A2 （2）计算各方案结点的期望值：

销售量减少（0.344） S4 3.5 2

3.25

2.8

点A1：E（A1）=3.5?0.656+2?0.344=2.984点A2：E（A2）=3.25?0.656?2.8?0.344?3.0952

（3）将各个方案结点的期望值标在相应的结点上。

（4）比较各方案结点上的值，从图中我们可以看出，E（A2）大于E（A1），可见在下一年内最优的选择是加班。

多点决策问题：

9.2基本方法115.520-553.8▲a133.83a2-2067.1▲65.5192.5S1(0.6)S(0.4)▲+2×3020▲+2×(-5)132.5105678S1(0.9)S2(0.1)S1(0.2)S2(0.8)S1(0.9)S2(0.1)S1(0.2)S2(0.8)1‖a67S1(0.6)10S2(0.4)▲+2×34▲+2×44726102.530×5-5×530×5-5×510×54×510×54×530×5-5×510×54×530×5-5×510×54×5‖▲67.1-203132.587.1S1(0.6)4122.5▲+2×10926a1‖a2102.5▲-30114710S2(0.124)34▲+2×4a110‖a2-20▲-30131426S1(0.9)S2(0.1)S1(0.9)(0.1)S2S1(0.2)S2(0.8)S1(0.2)S2(0.8)前2年后5年 四十四、 效用决策问题；

关键：费用变效用

?收益M的效用可以如下计算：U(M)= p0U(500)+(1-p0) U(-500)= p0(10)+(1-p0)0=10 p0使用这一步骤，我们计算出了该问题其他收益的效用值。结果如表所示。收益值＄500003000020000 0-20000-30000-50000瑞福公司货币收益的效用P的中立值效用值没有0.950.900.750.550.40没有10.09.59.07.55.54.00.010P0

3 6 6 5 3 6 ?12?7,?14?5,?22?7,?23?1,?31?4,?33?7，此时，?ij?0，故当前解为最优解。最优解值为：

Y?3?2?3?5?1?1?3?3?4?6?5?3?70

十七、 供求“不平衡”下的表上作业法；

关键：使之平衡，增加０或Ｍ

十八、 敏感性分析；

关键：设变量，求检验数

4

4

3

1

5 1

3

另外，有求范围的，我们以前做过

十九、 最大化问题（如收益，利润）；

关键：最大数一各个运价

二十、 转运下的运输问题；

关键：加上总运转量

随便运输

整数规划

二十一、 分支定界法；

关键：上界，下界，范围缩小，剪枝 运输问题：产地、销地、产量、销量

二十二、 割平面法；

关键：等号一边为整数，另一边为“真”分数；可用原变量X表示; 真分数大的收敛性好

二十三、 0-1规划———建模；

关键：基本形式y1+y2=1, ∑b*y1，M*y （相互排斥的计划、约束条件，固定费用）

二十四、 0-1规划——隐枚举法；

关键：（Max）从大到小，设定门槛(后设)，01互换并剪枝

二十五、 0-1规划——分支定界法；

关键：（Max）从大到小， 01互换并剪枝 , 非可行解

另外：

二十六、 指派建模；

关键：目标，约束，变量(二维)，近似运输 运输问题：产地、销地、产量、销量

二十七、 指派基本求解；

关键：横列最少取０（m个０），口诀（

3、某公司要把4个有关能源工程项目承包给4个互不相关的外商投标者，规定每个承包商只能且必须承包一个项目，试在总费用最小的条件下确定各个项目的承包者，总费用为多少？各承包商对工程的报价如表2所示： （15分） 项目 投标者 甲 乙 丙 丁 答最优解为：

X= 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 总费用为50

A 15 19 26 19 B 18 23 17 21 C 21 22 16 23 D 24 18 19 17

二十八、 指派—人数与任务不等（非标准型）；

关键：增加０或Ｍ，补全（１人可多做任务； 一定要做，一定不能做）

四、从甲, 乙, 丙, 丁, 戊五人中挑选四人去完成四项工作，已知每人完成各项工作的时间如下表所示。规定每项工作只能由一个人去单独完成，每个人最多承担一项工作，假定甲必须保证分配到工作，丁因某种原因不同意承担第四项工作。在满足上述条件下，如何分配工作，使完成四项工作总的花费时间最少。

人 工作 甲 乙 丙 丁 戊 10 2 3 15 9 5 10 15 2 4 15 5 14 7 15 20 15 13 6 8 一 二 三 四

一、解：

10 5 15 20 M 8 3 10 12 M 5 0 7 9 M-3 2 10 5 15 0 0 8 0 7 0 0 8 0 7 0 3 15 14 13 0 ~ 1 13 9 5 0 ~ 1 13 9 5 0 ~ 15 2 7 M 0 13 0 2 M-8 0 13 0 2 M-8 0 9 4 15 8 0 7 2 10 0 0 7 2 10 0 0

4 0 6 8 M-3 0 9 0 7 1 0 13 8 4 0 12 0 1 M-9 0 7 3 10 0 1 此时，费用最小，Z?3?5?5?8?21

其中，丙 一， 甲 二， 乙 三， 戌 四

*二十九、 指派－极大下的指派问题（非标准型）；

关键：最大数减去所有数，不能做的用Ｍ

目标规划 三十、 建模；

关键：Min目标(d+, d-, d++d-)，约束，变量(“维度”) ----适用所有的内容

6.某彩色电视机组装工厂，生产A，B，C三种 规格电视机。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为6，8和10小时。生产线每月正常工作时间为200小时。三种规格电视机销售后，每台可获利分别为500，650和800元。每月销售预计为12台，10台和6台。该厂经营目标如下： P1：利润指标定为每月16000元； P2：充分利用生产能力；

P3：加班时间不超过24小时 ； P4：产量以预计销量为标准。

为确立生产计划，试建立该问题的目标规划模型。

解：

设，A,B,C三种规格的电视机每月生产台数分别为x1,x2,x3 minz=P1d1-+P2d2-+P3d3++P4(d４-+ d４++d５-+ d５++d６- +d６+)} s.t.: 500x1+650x2+800x3+d1- -d1+ =16000 6x1+8x2+10x3+d2--d2+=200 6x1+8x2+10x3+d3--d３+=224 x1+d4--d4+=12 x2+d5--d5+=10 x3+d6--d6+=6

x1,x2,x3,di-,di+(i=1,2....6)大于等于零

三十一、 图解法；

关键：纵轴X2系数的正负，正—上面d+, 负—上面d- (增大，箭头方向); ＭinZ, 箭头反方向

三十二、 求解；

关键：Z1-Z0, σ≥0, 看检验数整个列, P1>>P2

网络规划

三十三、 网络性质；

关键：点线的有关系 , 奇点、偶点等

1.一个硬币正面为币值，反面为国徽图案。将这个硬币随机掷10次， 如果用树图表示所有可能出现的结果，试问这个树图有多少个节点，多少条边。

反 正 ... … … ... … … ... … … ... … …

解：有1?2?22??210?211?1个节点，211?2条边

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，问贮藏这八种药品至少需要多少间贮藏室。

解：用八个点分别代表八种药品，哪两种药品不能贮于同一室 内，就在代表它们的两个点间连一条边。其中S，P，R两两相邻，必须占用3间贮藏室。与S不相邻，彼此也不相邻的有A，B点，可与S贮于一室。类似可推出此题最少需要3间贮藏室。(不与黑线重合)

A T B S C R P D

三十四、 最小树；

关键：破圈法（去大），避圈法（加小），顶点扩充法（连线的最短边在最小支撑树内）

大连银行计划采用专用的加密网络将总部的计算机与市内五个区的分支银行的计算机互联起来（不一定是每一个支行都与总部直接相连）。这种专用的加密网络的铺设费用是连接距

离的100倍。表8-1给出了总部和五个分支机构之间的连接距离。银行的管理者希望能够在使得所有分支结构和总部都能直接或间接互联的前提下最小化专用网络的铺设费用，请你给出最优的铺设方案。 总部 距离（km） 总部 — 分支1 分支2 分支3 分支4 分支5 1.9 — 1.0 1.1 2.2 0.5 0.7 1.0 — 1.4 1.2 2.2 11.5 1.1 1.4 — 1.8 0.8 2.7 2.2 1.2 1.8 — 3.1 1.6 0.5 2.2 0.8 3.1 — 分支1 1.9 分支2 0.7 分支3 11.5 分支4 2.7 分支5 1.6

三十五、 最短路——Dijkstra求解

关键：累积值最小，逐一标号（Dijkstra）

五、求V1到各点的最短路及最短路径。（20分）

v39v110v41111v2114v51011v68v7

v1 v2 v3 v4 v5 v6 v7 0* ?? ?? ?? ?? ?? ?? 11 9* 10 ?? ?? ?? 11 10* ?? 20 ?? 11* 21 20 ?? 21 21* ?? 21* 28 25*

?v1?v2 11 ： v1?v2

v1?v3 9 ： v1?v3 v1?v4 10 ： v1?v4 v1?v5 21 ： v1?v4?v5 v1?v6 20 ： v1?v3?v6 v1?v7 25 ： v1?v4?v5?v7

三十六、 最短路——Floyed求解

关键： 算子(+，^) ，负权，理解，较小计算

三十七、 最短路——建模应用

关键：累积值最小，逐一标号

三十八、 单源和单汇最大流—建模；

关键：源汇=f，中间点平衡

三十九、 单源和单汇最大流—求解；

关键：增广链，非饱和流+，非零流-（调整---非饱和、非零，原则：最大Θ，近源汇），最大流=最小割

本文来源：https://www.bwwdw.com/article/4lif.html