-
-
4.19 MB, 下载次数: 1085, 下载积分: 体力 -2 点
运筹学案例集
4.19 MB, 下载次数: 1085, 下载积分: 体力 -2 点
运筹学案例集
好东西
可是分数不够
支持
[em01]
林区汽车修理网的布局问题
第一页
摘要：林区的汽车往往需要定期送往不同的修理厂进行大修，不同的汽车分配方案往往消耗不同的修理成本.本文主要利用图论和运筹学理论建立了一套线性规划数学模型，用于求解不同的修理厂规模的条件下最优的汽车分配方案，以及所对应的总费用，并对其进行分析评估.但为寻求最佳的修理厂规模调整方案，本文模拟实际情况中的市场机理，把市场作为资源分配的主要手段，国家（此处为方案制定制者）对市场进行必要的宏观调控.在此方案下得到了相当满意的结果，这也是本文的独到之处.本模型对实际情况中汽车修理分配方案的制定有很大的指导作用.且本模型的处理思想，对市场体制下的很多类似问题都有借鉴作用. 5 I* ^7 j3 R2 V U% U. L' w; e
1.问题重述：在林业发展中，汽车是主要的运输工具，定期的对汽车进行大修是一个必需的环节.各个林业局都有待修的汽车，都有汽车修理厂，但待修汽车派往不同的修理厂将花费不同的成本，因此不同的分配方案将导致不同的总成本.现要求在不同的现实允许条件下，求得最优的分配方案，使总成本最少.
2.基本假设：
（1） 沿用题中所给的基本假设，认为每辆汽车一年只大修一次，且不考虑关闭、扩建大修厂的费用. + \/ @7 R: G# d9 ?
（2） 修理汽车的总费用由运输费用和修理成本两部分组成. ' R9 n# I4 z6 m( K
（3） 不考虑公路运输与铁路运输之间相互转换对运输造成的不便或对运输成本造成的影响. ) L8 j) F1 Q; a, w7 E
（4） 不考虑修理厂的停产倒闭给社会上带来的负面影响. 1 u; Q) \) E! R! {, Z
（5） 考虑修理厂厂点分散规模小对经济效益产生的不良影响，认为生产的相对集中是对我们有利的.
+ q6 L" k; b! X# _. J
3．变量说明：
: 下标序列,表示某待修汽车所属的林业局序号,取1到18.
$ W7 N- t, T, Z f" [. L& y
: 下标序号,表示某汽车修理厂所属的林业局序号,取1到18.
$ p" K! C/ U# P$ g$ [. J9 Q y
: 表示第i号林业局每年待修的汽车数量.
- M8 {( f t# F ?
: 表示第j 号林业局的汽车修理厂每年能够修理的汽车数.
4 i) v1 D! @$ K' f* o$ Z
： 按问题3的方案扩建后的修理厂产量.
: 表示第 i号林业局的汽车送往第j 号林业局的修理厂修理时的运输费用(往返双程).
: 表示第j 号林业局的修理厂修理一辆汽车的修理成本.
: 表示第 i号林业局的汽车送往第j 号林业局的修理厂修理的总量数.
：0-1变量.表示第 j 号林业局的修理厂是否有修理汽车，有则为1，否则为0.
4.模型的建立:
4.1 问题的分析:
目标函数为林区所有汽车的修理费用之和,修理费用包括两部分,运输费用和修理成本, 对每辆汽车,修理费用应为
+
.因此整个林区的修理总费用为:
约束条件中有一项公共约束,即供需约束.每个林业局实际被修的汽车数必须等于待修汽车数;而每个修理厂实际所修的汽车数,必须不超过其最大产量.
* N- H% `. A+ _- p9 l! x3 r Q
i=1，2，3，……18
) q' [/ I# q3 \8 s9 L- d* B @
j=1，2，3，……18
其中 & `9 k" ?1 I% b9 [4 U
、
、
、
都是已知量.
对于各问中的具体情况,只需增加不同的约束条件,根据具体问题具体分析即可.
4.2具体模型的建立: 3 ]; Y6 B1 q4 m2 O
4.2.1 , m$ z* B; i# P: f
的求解.
问题分析中的模型中,还有
是未知的, 首先必需求出
.下面将用图论的方法求解
.
首先将18个林业局的位置以及相互之间的交通联系用一副无向赋权图表示.图的每个顶代表点一个林业局;每条边代表两个林业局之间的直达路线;边上的权代表此路线的双程运输费用,即为公路距离乘以6或铁路费用乘以5.所得图如下:
. \" [9 {3 ~8 F% h- s' [
最短路概念的简介：设 i 、j是一赋权图的两个顶点，i 、j连通，从i到j的所有路径中，边的权相加总合最小者，即为 i 、j的最短路.用动态规划法编制一段matlab程序即可解得上图中任意 i 、j之间的最短路，以及其相对应的权. 程序见附录2.
即为从i到j 的最短路的权. 
的值如附录1所示.
4.2.2在第1问中应对4.1中模型的补充：
条件：分区协作，不得跨区修理. + `: J( K2 ]: n& Q' E2 u
分协作区，即本区派往本区去修的汽车总数应与本区所修的总数相等.
其中t=1，4， 12
2 b" o% r8 g# E$ ]8 `! F
其中 t=15
, o. d( @/ W/ h p, S+ ?
% U# I8 R" _2 ~( v
其中 t=7
4.2.3第2问要求不分区协作，不需对4.1中模型作任何改动.
4.2.4在第3问中应对4.1中模型的补充： ) s2 f- N' _" |2 ~! t
条件：2、5 、8、14、16增产80辆.
只需把常数
作相应的改动，模型本身不需动. 即
j=1，2，3，……18
4.2.5在第4问第一小问中应对4.2中的模型作如下修改：
条件：在2、5、8、14、16五个林业局中选两个作为集中大修点.
利用0-1变量 7 o! o' D% B9 E- M
表示4问中的约束，并将其转化为线性规划.增加以下两条约束：
j = 1，2，……18
4.2.6为了提出更优的修理厂扩建规模与车辆分配方案而建立的模型： 4 }+ }" B1 o( T- y n
注意到问题1、2、3中存在很明显的不足之处，一、修理厂过度分散，规模都不大，影响经济效益；二、汽车分配方案复杂，不便于管理调整；三、总修理费用并没有因为调整方案的复杂而优化，总费用仍不尽人意.
注意到问题4 中的方案一定程度上解决了上述问题，而且费用没有增加.可见，相对的集中是有利的.但是如何安排集中度，如何选择最优的集中点的个数及位置，仍不能用问题4 中的模型来求解.
为解决以上问题，我们按如下思路解决.模拟市场上优胜劣汰的竞争机制，不限制修车厂的产量上下限，以总费用最小为目标，在此目标下，任由修理厂的规模随需求量自由变换；即退一步取消修理厂产量的约束条件.这样我们得到一组修理厂规模方案.当然，市场的自由竞争机制具有一定的盲目性、滞后性，因此我们同时要对它进行宏观调控，把“看得见的手”与“看不见的手”结合起来. 3 R" Q) D) M4 K% l
在没有产量约束的情况下，其模型如下： : U8 v/ d" O7 \6 }% l5 Z
( h, @3 n: i) w, L, E
8 O: U; P+ ?$ A3 S' q4 n
i=1，2，3，……18
在计算得到结果之后，在对结果进行分析，制定宏观调控方案，取消产量不大，对结果影响不明显的厂点，从而制定总体最优方案.对结果的处理详见“模型求解与结果的分析”. , C/ }8 @7 ~; C- i
4.3 最终规划模型：
4.3.1 第1问：(分区协作)
5 ~. z# E2 j3 Y3 _5 K; p; |" C
i=1，2，3，……18
j=1，2，3，……18
其中t=1，4， 12
% f. e' b% T' a) [: m s
其中 t=15
其中 t=7
4.3.2 第2问：(不分区)
+ M: \& C1 H; e7 V9 A
* u9 G, o6 \% r& `- v
i=1，2，3，……18
; z5 n! F6 {' D7 t" i1 }3 Y
! m" d6 c! _# H3 n, q: K) N
j=1，2，3，……18
4.3.3 第3问：(2、5 、8、14、16修车厂增产80辆)
7 O' x$ e2 M7 k7 G8 l2 r: K9 }
8 T% \' }; V E
i=1，2，3，……18
j=1，2，3，……18
4.3.4第4 问第1小问：(在2、5、8、14、16五个林业局中选两个作为集中大修点.)
: c9 ~+ P P! U/ {5 u" W4 Z7 o
- H3 H& O8 j; b
i=1，2，3，……18
7 b, N, O; k6 i3 C2 T3 I6 l
) s5 P+ t# Q' k6 Y' u
j=1，2，3，……18
j = 1，2，……18
' f v% @9 a8 _/ e& r
4.3.5为得到最优的修理厂规模调整方案而建立的模型： 3 f( V* T) _; \
% x' N K2 V4 h2 ]9 p) I
i=1，2，3，……18
5.模型求解与结果分析： - v. Q: o! I, \3 m9 L* K: j% A
5.1 由于上文中所建立的模型都是简单的线性规划模型,因此其求解甚为容易.直接利用Lingo 软件,将模型输入,然后就可以得到全局最优解.所有的Lingo程序见附录3. 0 p/ |3 r* n! h/ a; @
5.2 模型4.3.1的结果： # `4 y) y% E+ D/ L) K3 D1 U- w
分区协作的最少总费用为：6181200元.
最优分配方案如下表所示，X（i，j）表示j号林业局分往j号修理厂的车辆数.
1
| X( 1, 1)=10
| 7
| X( 7, 7)=40 5 U& G; k8 a o/ B5 ^9 b/ U
| 13
| X( 13, 13)=60 ) |8 U0 {7 U6 S7 R9 x. C
|
| X( 1, 2)=15 s E4 `! ~ ~1 C8 E# p) J
| 8
| X( 8, 8)=180 8 t$ T$ B% }. X
| 14 4 z* O7 [% E; W2 j- L8 O0 F/ x# I
| X( 14, 14)=150 2 p' S" F) {$ ^- j. A
|
2 / M4 `( v/ |, `! _
| X( 2, 2)=25
| 9 9 a8 m( r+ g2 k- M2 L9 `, v
| X( 9, 9)=70
| 15
| X( 15, 15)=25 3 {" S2 c# N3 I# L
|
| X( 2, 3)=10 . N) V5 f' `% r9 g) v5 K
| 10
| X( 10, 10)=60 " q, U( r9 a; }) U- V% u
| 9 M3 c" T! h; J" C" f Q0 Z6 @
| X( 15, 17)=15 5 n% U9 d* v" o$ |( _% [
|
3
| X( 3, 3)=30 ; Z" B0 J* \" v: w' {
| 11
| X( 11, 8)=20
| 16
| X( 16, 16)=100 2 ]" ~4 E9 e1 G5 l# d
|
4 & A# ]& G" n; i7 m% g4 M" x
| X( 4, 4)=45 + [" {$ |. t7 Y2 m7 f. O5 L7 k
| ) S) b! P, P( V0 O7 b) t5 ]: q3 x
| X( 11, 11)=30 . q5 {( E) [% h; A7 T
| 17
| X( 17, 16)=10 $ X% }. C; [- b" H8 @. r
|
5
| X( 5, 4)=5
| 12 + Q, m# p# r3 z0 R
| X( 12, 12)=10
|
| X( 17, 17)=25
|
$ Q) r4 O2 ]# M( D3 }1 r5 L) h, p
| X( 5, 5)=75
| % T5 u" a1 q5 s" T4 v; S
| X( 12, 13)=20 8 a2 L# @/ j7 A" E
| 18
| X( 18, 18)=55 ) h4 {' R" d' M. L; k
|
6 # Q/ K) f* K# |6 _$ I
| X( 6, 6)=55
| 2 D$ x1 U; m s" |
| X( 12, 14)=30 E* Z' s. z0 \, K5 p9 e: n3 C
|
| 7 g. G% b/ M5 p: r% m D
|
模型4.3.2的结果： + k8 [# g& x3 O s$ S5 b
不分区协作的最少总费用为：6136400元. & a( S! J0 n5 O
最优分配方案如下表所示：
1 : ]) }# p% ]( N8 n' F
| X(1,1)=25 " w X- r q" m; d
| 6 " I! P: L, k% y% R+ j4 m8 m! A4 ?
| X(6,1)=5 ; y7 W; E r/ b
| 10 ( P) q2 A1 u }! l- o; P! [
| X(10,10)=60 , c/ r, N: ^) r" @+ t6 D
| 15
| X(15,15)=40 8 `( F f3 e$ w' A) y
|
2
| X( 2, 2)=35 | 3 P1 m* S N3 N: r7 z' w3 Z) w/ `; s
| X(6,2)=5 ) _6 H) ]2 _% t
| 11
| X(11,11)=45 * [+ t9 {5 z5 H1 L
| 16 ( \: `" G$ [# I7 P) l
| X(16 16)=95 ; S( W6 c. A6 u' G
|
3 N+ [4 j- H0 \* O) y7 _
| X(3,3)=30
| 0 G$ n' X" H* G3 s/ j
| X(6,6)=10 + E' Q5 b" V2 w* ]0 P- G; I+ e
|
| X(11,18)=5
| 1 A: j5 u$ G! \: y4 y2 L) t( a
| X(16,17)=5
|
4
| X(4,4)=45 % B5 e A& y' [
| 0 Y# a Z) }* T) @9 n7 f$ @
| X(6,8)=20
| 12
| X(12,9)=10 + d- Y# c& d8 ]. N, O
| 17
| X(17,17)=35
|
5
| X(5,3)=10
| 3 f2 [: ~# L+ e# o# E
| X(6,16)=15 3 t3 g9 k. v$ F5 g3 A, J
| 8 g* P1 p$ z3 J
| X( 12, 13)=20
| 18 4 t" M! Y q; X* m+ S5 f, l
| X(18,18)=55 4 l% J0 g$ m e
|
| X(5,4)=5
| 7
| X(7,7)=40 + U: c8 |6 d& g
| ( ?4 q+ } Q9 |0 w* w
| X(12,13)=20
|
|
|
| X(5,5)=55 4 |: F, Q# B5 ~* g
| 8
| X(8,8)=180 |: I8 b; o; E- h5 E: _
| 13
| X(13,13)=60 * R" d3 y m) J) C3 ?' I
|
|
|
| X(5,7)=10 5 S3 ~! \; [. q+ k5 O+ ~
| 9 + ]- o0 \9 ]; [. J- s
| X(9,9)= 70 7 p8 w" Q5 e2 }
| 14
| X(14,14)=150 9 ]( s8 k; |! t$ X6 g$ X& }# c
|
|
|
7 X, K$ f5 Q8 |$ |+ n
模型4.3.3的结果： / h" X4 T5 c! r
2、5 、8、14、16修车厂增产80辆后的最少总费用为：5863400元.
最优的分配方案如下表所示： : R8 }" e) I, l: f; p5 b
1
| X(1,2)= 25
| 10 # E7 T& r% b9 E6 b
| X(10,8)= 50 4 p# s! }' B/ @) T- P2 {
|
2
| X(2,2)= 35 : L) E: L+ p" N( u$ ]4 j! W7 l* i0 U
|
| X(10,16)= 10 : M1 ]& f, v; W, R6 q8 H* n7 _
|
3 & s4 c& c j. [6 U1 C1 P' @' Q
| X(3,3)= 30
| 11
| X(11,16)= 45
|
4 ' ]# Y: q+ m$ e3 r1 E) c, z% T
| X(4,4)= 45 ' F, e4 U. ^ m) e R" C
|
| X(11,18)= 5
|
5 : r( U: z0 ?* X: S
| X(5,2)= 55
| 12
| X(12,14)= 60 , I6 X$ Y/ U/ v& m- O7 T
|
& u8 `4 z8 [- \+ [
| X(5,3)= 10
| 13
| X(13,13)= 10
|
7 _& g3 O! z/ H7 i
| X(5,4)= 5
| % E9 C- a K4 k) N( J) w) I
| X(13,14)= 50
|
| X(5,7)= 10
| 14
| X(14,14)=150 & A8 S# L& _2 t7 I9 S _
|
6 - k' w7 q- r& D( L$ R! D) y
| X(6,2)= 5 6 P$ S- r+ C/ G) }; m4 D& b
| 15
| X(15,16)= 35
|
| X(6,8)= 50 ; I5 Y/ m# _7 |/ d! ^% v) }
| 6 |+ I0 _& N( ?4 G; C
| X(15,17)= 5 ' ^7 r' k* f. z2 q
|
7
| X(7,7)= 40
| 16 8 T( g" t6 f7 M! i/ t
| X(16,16)=100
|
8 2 j! }. s1 U1 K$ F! a# F2 A% i
| X(8,8)=180
| 17
| X(17,17)= 35
|
9 ) Y* E, ^9 ?0 R6 z& W
| X(9,9)= 70
| 18
| X(18,18)= 55 0 H5 N2 s. y% _$ x+ ~3 ]
|
模型4.3.4的结果：
在2、5 、8、14、16中选择8和14两个点作为集中修理点，其余修理厂停产.8处修理900辆，14处修理270辆.
最优的分配方案如下表所示： 9 y) J9 z3 d/ I) Y7 x
1 0 v- h8 ?0 e' |+ q( [
| X(1,8)= 25 & ]' e* j' Z; [! [% H
| 10 & ~8 p5 F4 J0 {1 h2 m! O6 K
| X(10,8)= 60 - G6 G4 l# Q" i4 w
|
2 ) H4 y% n& l% ]. G
| X(2,8)= 35 6 v7 \* K- _& Z# l. M
| 11 ! U$ a7 V; L9 E$ u. ~
| X(11,8)= 50
|
3
| X(3,8)= 30 9 Q! \/ {3 n3 x! W% n
| 12 ! t7 {& G5 e9 O4 I& ^% E2 O
| X(12,14)= 60 , O4 k X; ^% t9 y! {! H
|
4
| X(4,8)= 45
| 13 * E# g9 q# d4 E! X
| X(13,14)= 60
|
5
| X(5,8)= 80 & T0 J9 [) v/ W
| 14 ; T$ M5 N! \) S+ U5 Q
| X(14,14)=150
|
6 j* e7 N0 I2 D4 }9 j
| X(6,8)= 55
| 15 , T n$ R2 G, h( m2 S
| X(15,8)= 40 ' _: n! M `5 U8 {
|
7
| X(7,8)= 40
| 16 2 c3 E5 N3 U9 q8 f0 s, a2 E- h
| X(16,8)=100 B2 _5 O4 e. g
|
8
| X(8,8)=180 + M; l6 d9 X- ^9 m/ y
| 17 / l2 E" m* S4 g% C5 Q
| X(17,8)= 35
|
9
| X(9,8)= 70
| 18
| X(18,14)= 55 # o$ W$ Q7 W# y% c4 k9 t
|
由以上四个结果可以得到如下结论： ' r% |8 _2 i* @" E2 }( j2 Z/ V2 G
1.分协作区与不分协作区相比较，更容易进行管理实施，但以增加总费用为代价； 8 ?7 e. ?# U/ e
2.适当地增加某些厂点的生产规模，能节省大量费用；
3.前三个模型的规划方案都比较复杂，不易于管理实施；且厂点分散，生产规模较小，效益差；第四个方案有明显的改进；
4.第四个方案选择的两个厂点在8和14，8和14位置比较靠近整个林区的中心，交通发达，尤其是8，是整个区的“十字路口”.这些都是符合实际的情况和常理的.
5.3 修理厂规模调整方案:
按模型4.3.5可以得到最少总费用：5605900元.修理厂有5个：3、8、14、16、18.产量为：
3 + d( c) k2 F) i
| 8 $ s+ ?: z+ F8 j- i# m
| 14 | 16 | 18
|
215 , e; i; `1 D& p# X3 G
| 455
| 270 - s- b% [& j( T% E
| 175 ' i# n4 e, H0 Y% d
| 55 ; C) T% p I5 Q) B3 e
|
从表中可以看出，最费用比前几种方案都少. 厂点3、8、14、16 的产量大，效益好；厂点18产量不大.为使生产集中，提高企业效益，减轻管理难度，我们试着把厂点18关闭.代入模型再解得到以下结果：
3
| 8
| 14 # G, m% U/ P$ n! b+ S- g
| 16
|
215
| 585 / Q. g+ H$ }* W e
| 270 | 100
|
即16区不变，3、8、14区扩建分别至215、585、270，其余区的修理厂停产.令人吃惊的是，此方案下的总费用仍为5605900元，看来该问题有很多最优解。 ) l* ?! S, t3 I/ i; I/ W2 o+ O
此方案下的车辆分配状况为：
3
| X(1,3)= 25 ; e L& V" J9 T9 M" {5 _: L6 P
| 8
| X(18,8)= 55 , D" s% r3 ]3 V, R8 J) m
|
8 H- J4 `/ d' y; I+ ?1 \( j
| X(2,3)= 35
|
| X(6,8)= 55
|
3 C# E1 D% K2 l9 b- l: K5 ~
| X(3,3)= 30 6 M1 x" }1 p! p- m2 y" q# n
|
| X(7,8)= 40 ( S1 l& w( e$ X' B2 R4 z0 W. F
|
. ~ ? X- Q6 {$ j7 N$ l1 f* N
| X(4,3)= 45
| $ l/ [/ @) P1 {! c: q' t5 O* ?
| X(8,8)=180 7 x3 E) m+ S, C8 _* V4 v( p2 \! ]
|
0 M) X0 U) e6 i: ^# [' E: n' c
| X(5,3)= 80
| ( X; A( {- F4 M* j5 |% O& w2 ]
| X(9,8)= 70
|
8
| X(10,8)= 60
| 14
| X(12,14)= 60
|
| X(11,8)= 50 8 }8 Z, Z" W: P. m
| $ S# ?" Q& j2 `/ }0 K9 y6 @0 \
| X(13,14)= 60
|
| X(15,8)= 40 , @( e+ C F; q
|
| X(14,14)=150 & z8 d( G( Y, ?+ i' S2 Z7 Y5 `2 H
|
8 F3 P, c8 t. K3 {' R- ^7 k+ P( b
| X(17,8)= 35
| 16 8 M6 }. C$ y3 P$ `/ m/ u. v
| X(16,16)=100
|
此方案即可作为最后的制定方案，此方案不仅费用最低，而且生产相对集中.
6.模型的推广与讨论：
本模型的不足之处主要在于忽略了扩建修理厂的费用，因此所得方案在实际实施时所产生的效应可能与模型的预测有较大的出入.
本模型的最大特色在于通过模拟现实中的市场机制，放宽管理者对企业的过多干预，收到了非常可观的经济效益. 0 {, y' O6 s: b: R0 Q, I$ c
我们认为,管理者的规划固然重要,但是有时过多的人为干预又会减弱市场的作用.同时市场有很大的弊端,需要管理者宏观上调节.本模型的思想就是先模拟市场自由竞争的过程,分析其竞争结果,在对结果进行分析,提出干预措施,从而提出既能充分利用市场功能又能克服市场弊端的合适方案.这种处理问题,制定方案的思想应该是具有普遍意义的,尤其是在现在有中国特色的社会主义市场经济体系下.因此本文的思想不仅可以推广到其它类似的供需分配问题,甚至可以推广到所有以市场为背景的管理规划问题中. * \& i% O: W' M( e/ j
6 w6 T0 x$ h2 S2 Z5 S+ A
7．参考书目 * Q/ H5 @" h* n% l/ _2 t q8 q
1．姜启源，数学模型（第三版），高等教育出版社，2002 - s( I/ {7 o3 A' I ^
2．王脉然，Matlab与科学计算（第二版），电子工业出版社2003.
dingding
看看吧
好东西,真不错
太好了，以后天天来这里
谢谢楼主
多谢分享
[/img]
{:3_66:}
好
顶啊，呵呵
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) | Powered by Discuz! X2.5 |