运筹学案例(改).doc

4.2仓库布设与物资调运
数学112 程文君 高慧婷 聂雅倩 汤小坚 季若若（18、 21、 33 、34、 42）
【摘要】:公司须货物从生产厂运往中转仓库或用户，中转仓库也须将货物运往用户，运输过程就会出现许多方案，厂方如何确定一个可行且实惠的调配方案，使总调运费用最小。为实现合理调配，就运用相关数学方法，软件或工具，本案例属于运筹学原理中整数规划与分配问题，除具体方法，数据处理用到LINGO软件，相应的就减少了运算量。
关键词：运输问题，0-1规划，最小费用
1.问题的重述
红梅食品公司有两个生产厂、，四个中转仓库、、、，供应六家用户、、、、和。各用户可从生产厂家直接进货，也可从中转仓库进货，其所需的调运费用（元/t）如表4-27所示：
表4-27

注：表中“——”为不允许调运。
部分用户希望优先从某厂或某仓库得到供货。他们是：,,,或。
已知各生产厂月最大供货量为：，；各中转仓库月最大周转量为：，，，；用户每月的最低需求为：，，，，，。
要求回答：（a）该公司采用什么供货方案，使总调运费用最小；
（b）有人提出建议开设两个新的中转仓库和，以及扩大的中转能力，假如最多允许开设4个仓库，因此考虑关闭原仓库和，或两个都予关闭。
新建仓库和扩建的费用及中转能力为：建需投资1200 000万，中转能力为每月30000t，建需投资400000元，月中转能力为25000t；扩建需投资300000元，月中转能力比原增加20000t。关闭原仓库可带来的节约为：关闭月节省100000元；关闭可月节省50000元。
新建仓库、同生产厂及各用户间单位物资的调运费用（元/t）见表4—28.
表4-28

要求确定、中哪一个应新建，是否需扩建，和要否关闭及重新确立使总费用为最小的供货关系。
2.模型假设
1．部分用户希望优先从某厂或某仓库得到供货时，优先考虑并首先满足其最低需求。
2．不考虑货物运输过程中除运费外的其他费用。
3.符号说明：
1、：某地到某地的运货量；
2、Z：满足条件下的最小费用；
3、（i=1…6）：中转站开设或关闭；=0，第i个中转站开设；=1，第i个中转站关闭

4、：某地到某地的运费；
5、分别为的最大供货量，的最大中转量，的最低需求。

4.模型建立及求解
(A)
本问题的目的在找出最优调运方案，使总的调运费最省，解决的方法很多，主要的有表上作业法和单纯形法，单纯形法可以解决一般的线形规划问题，本题为产销模式的运输问题，也属于线形规划，而且操作过程中涉及到的变量较多，计算量庞大，通过计算机软件lingo就很好的解决了计算量问题，基于单纯形法的简洁方便，我们就选择此数学方法来求解
1． 确定目标函数
将表4-27中数据转化为目标函数和约束条件
目标函数为所求最小费用，公式：
(1)
这里将中转地即看成产地又是销地，那么由表4-27得有6个产地，10个销地方，表示为从产地运到销地的费用，公式（1）就是所有运费的相加，并取最小。
2．确定约束条件
由于有最大供货量，有最大周转量，有最低需求，那么在调运，中转，供货都有一定的限制，在运算中可列出相应的约束条件，
对的限制，公式：
（2）
表示为的最大供货量。
对的限制，公式：
（3）
为的最大中转量。
由于是中转站，所以与之间还有约束关系，即在某个中得到的供货量不能超过此从得到的中转量。公式为：
（4）
对的限制，在考虑优先的前提下，满足最低需求即可，公式：

（5）
下面就对以上的目标函数和约束条件进行程序编辑，再用LINGO软件对数据进行处理。
程序如下：
min =50*X10+50*X11+100*X12+20*X13+100*X14+150*X16+200*X17+100*X19
+30*X21+50*X22+20*X23+200*X24+150*X35+50*X36+150*X37+100*X39
+100*X44+50*X45+50*X46+100*X47+50*X48
+150*X55+200*X56+50*X58+150*X59
+20*X66+150*X67+50*X68+150*X69;

x10+x11+x12+x13+x14+x15+x16+x17+x18+x19<150000;
x21+x22+x23+x24<200000;

x10<70000;
x11+x21<50000;
x12+x22<100000;
x13+x23<40000;

x35+x36+x37+x3950000;
x35>10000;
x16+x36+x46+x56+x66>40000;
x17+x37+x47+x67>35000;
x48>50000;
x59+x69>20000;
x58+x68>10000;

运行结果：
Global optimal solution found.
Objective value: 0.2460000E+08
Total solver iterations: 12

Variable Value Reduced Cost
X10 45000.00 0.000000
X11 0.000000 20.00000
X12 0.000000 50.00000
X13 40000.00 0.000000
X14 50000.00 0.000000
X16 0.000000 50.00000
X17 0.000000 0.000000
X19 0.000000 100.0000
X21 50000.00 0.000000
X22 30000.00 0.000000
X23 0.000000 0.000000
X24 0.000000 200.0000
X35 10000.00 0.000000
X36 0.000000 0.000000
X37 35000.00 0.000000
X39 0.000000 150.0000
X44 0.000000 200.0000
X45 0.000000 150.0000
X46 0.000000 50.00000
X47 0.000000 0.000000
X48 50000.00 0.000000
X55 0.000000 200.0000
X56 0.000000 150.0000
X58 10000.00 0.000000
X59 20000.00 0.000000
X66 40000.00 0.000000
X67 0.000000 30.00000
X68 0.000000 30.00000
X69 0.000000 30.00000
X15 0.000000 0.000000
X18 0.000000 0.000000

Row Slack or Surplus Dual Price
1 0.2460000E+08 -1.000000
2 15000.00 0.000000
3 120000.0 0.000000
4 25000.00 0.000000
5 0.000000 70.00000
6 70000.00 0.000000
7 0.000000 60.00000
8 0.000000 50.00000
9 0.000000 100.0000
10 0.000000 50.00000
11 0.000000 80.00000
12 0.000000 -100.0000
13 0.000000 -200.0000
14 0.000000 -100.0000
15 0.000000 -200.0000
16 0.000000 -150.0000
17 0.000000 -200.0000
18 0.000000 -100.0000

结果分析：在满足部分用户优先供货的前提下，总调运费用最小为2460万元，具体供货方案如下表所示; 表1-1
注：表中空格处的值为0，即没有货物调运
表1-1

B1
B2
B3
B4
C1
C2
C3
C4
C5
C6
A1
4.5

4
5

A2

5
3

B1

1

3.5

B2

5

B3

1
2
B4

4

(b)由表4-27和表4-28合并可得：

(1)假设B2不扩建：
min=50*X10+50*X11+100*X12+20*X13+60*X14+40*X15+100*X16+150*X18+200*X19+100*X111+30*X21+50*X22+20*X23+40*X24+30*X25+200*X26+150*X37+50*X38+150*X39+100*X311+100*X46+50*X47+50*X48+100*X49+50*X410+150*X57+200*X58+50*X510+150*X511+20*X68+150*X69+50*X610+150*X611+120*X76+60*X77+40*X78+30*X710+80*X711+40*X87+50*X89+60*X810+90*X811+100000*B3-1)+50000*(B4-1)+1200000*B5+400000*B6;
x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x110+x111<150000;
x21+x22+x23+x24+x25+x26<200000;
x10<70000;
x11+x21<50000;
x12+x22<100000;
x13+x23<40000;
x14+x24<30000;
x15+x25<25000;

x37+x38+x39+x31150000;
x37>10000;
x18+x38+x48+x58+x68+x78>40000;
x19+x39+x49+x69+x89>35000;
x410>50000;
x511+x611>20000;
x510+x610+x710+x810>10000;

B1+B2+B3+B4+B5+B6<4;
X10<400000*B1;
X11<400000*B2;
X21<400000*B2;
X12<400000*B3;
X22<400000*B3;
X13<400000*B4;
X23<400000*B4;
X14<400000*B5;
X24<400000*B5;
X15<400000*B6;
X25<400000*B6;
X37<400000*B1;
X38<400000*B1;
X39<400000*B1;
X311<400000*B1;
X46<400000*B2;
X47<400000*B2;
X48<400000*B2;
X49<400000*B2;
X410<400000*B2;
X57<400000B3;
X58<400000*B3;
X510<400000*B3;
X511<400000*B3;
X68<400000*B4;
X69<400000*B4;
X610<400000*B4;
X611<400000*B4;
X76<400000*B5;
X77<400000*B5;
X78<400000*B5;
X710<400000*B5;
X711<400000*B5;
X87<400000*B6;
X89<400000*B6;
X810<400000*B6;
X811<400000*B6;

@bin(B1);
@bin(B2);
@bin(B3);
@bin(B4);
@bin(B5);
@bin(B6);

（bin表示二进制，Bi只能取值0或者1）
Global optimal solution found.
Objective value: 0.2280000E+08
Extended solver steps: 0
Total solver iterations: 32

Variable Value Reduced Cost
X10 50000.00 0.000000
X11 0.000000 20.00000
X12 0.000000 100.0000
X13 4000000 0.000000
X14 0.000000 60.00000
X15 0.000000 10.00000
X16 50000.00 0.000000
X18 0.000000 50.00000

X19 0.000000 0.000000
X111 0.000000 100.0000
X21 50000.00 0.000000
X22 0.000000 50.00000
X23 0.000000 0.000000
X24 0.000000 40.00000
X25 25000.00 0.000000
X26 0.000000 200.0000
X37 10000.00 0.000000
X38 30000.00 0.000000
X39 10000.00 0.000000
X311 0.000000 150.0000
X46 0.000000 200.0000
X47 0.000000 150.0000
X48 0.000000 50.00000
X49 0.000000 0.000000
X410 50000.00 0.000000
X57 0.000000 150.0000
X58 0.000000 100.0000
X510 0.000000 0.000000
X511 0.000000 0.000000
X68 10000.00 0.000000
X69 0.000000 30.00000
X610 10000.00 0.000000
X611 20000.00 0.000000
X76 0.000000 120.0000
X77 0.000000 60.00000
X78 0.000000 0.000000
X710 0.000000 0.000000
X711 0.000000 80.00000
X87 0.000000 190.0000
X89 25000.00 0.000000
X810 0.000000 80.00000
X811 0.000000 240.0000
B3 0.000000 -0.6390000E+08
B4 1.000000 50000.00
B5 0.000000 -0.6280000E+08
B6 1.000000 400000.0
X17 0.000000 0.000000
X110 0.000000 0.000000
X59 0.000000 0.000000
B1 1.000000 0.000000
B2 1.000000 0.000000

Row Slack or Surplus Dual Price
1 0.2280000E+08 -1.000000
2 10000.00 0.000000
3 125000.0 0.000000
4 20000.00 0.000000
5 0.000000 70.00000
6 100000.0 0.000000
7 0.000000 60.00000
8 30000.00 0.000000
9 0.000000 120.0000
10 0.000000 50.00000
11 0.000000 100.0000
12 0.000000 0.000000
13 0.000000 80.00000
14 0.000000 0.000000
15 0.000000 150.0000
16 0.000000 -100.0000
17 0.000000 -200.0000
18 0.000000 -100.0000
19 0.000000 -200.0000
20 0.000000 -150.0000
21 0.000000 -230.0000
22 0.000000 -130.0000
23 0.000000 0.000000
24 350000.0 0.000000
25 400000.0 0.000000
26 350000.0 0.000000
27 0.000000 0.000000
28 0.000000 0.000000
29 360000.0 0.000000
30 400000.0 0.000000
31 0.000000 0.000000
32 0.000000 0.000000
33 400000.0 0.000000
34 375000.0 0.000000
35 390000.0 0.000000
36 370000.0 0.000000
37 390000.0 0.000000
38 400000.0 0.000000
39 400000.0 0.000000
40 400000.0 0.000000
41 400000.0 0.000000
42 400000.0 0.000000
43 350000.0