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

线性规划问题

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

关键：决策变量（维度），目标函数、约束条件； 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

二十三、 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条边

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