数学建模社区-数学中国
标题:
线性规划——运输问题（产销平衡）
[打印本页]
作者:
1047521767
时间:
2021-10-28 18:50
标题:
线性规划——运输问题（产销平衡）
运输问题（产销平衡）
' t- l- n9 {% ]8 O* c2 _
某商品有m 个产地、n 个销地，各产地的产量分别为a1,a2,…am ，各销地的 需求量分别为b,…bn , , 1 L 。若该商品由i 产地运到 j 销地的单位运价为 cij ，问应该如何调 运才能使总运费最省？
: { G/ N2 m9 T
. q. a2 B4 `/ R
解：引入变量 xij ，其取值为由i 产地运往 j 销地的该商品数量，数学模型为
% w( }5 M+ e, @% Q" a
+ j U0 {6 j7 U: B
! K" x O8 X# H5 C) |) ^
显然是一个线性规划问题，当然可以用单纯形法求解。
对产销平衡的运输问题，由于有以下关系式存在：
其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习惯上称为表上作业法（由 康托洛维奇和希奇柯克两人独立地提出，简称康—希表上作业法）
* ^) }3 U, B* [& \- K; t0 d% L5 ~9 E
' _0 V) S' _9 P! t/ q
例题：
0 x' \( g0 Y) H- I" q$ _
; Z% p5 f- o! r" n! o' h. p
某公司有三个加工厂A1，A2.A3生产某产品，每日的产量分别为：7吨、4吨、9吨；该公司把这些产品分别运往四个销售点B1，B2、B3、B4，各销售点每日销量分别为：3吨、6吨、5吨、6吨；从各工厂到各销售点的单位产品运价如表4-1所示。问该公司应如何调运这些产品，在满足各销售点的需要量的前提下，使总运费最少？
% G5 |1 C1 o4 E9 F
# H/ L. J4 W* O, s/ E/ w
解析： 典型的产销平衡问题，将已知数据做成表格如下：
# Q8 z# t) E0 e0 Z4 f
+ t: J4 `- o0 O) H
4 W2 j* A4 F/ O6 k! w* ~ [* Q5 {
将所有数据列成表格会更加清晰，根据题意可以得到目标函数的表达式如下：
) [& \) ~8 v( B% k
4 b& h8 t# j7 y$ u( R4 k4 v! {
然后将已知约束关系整理如下：
4 `2 [* E' {% e( S: j
2 S/ N! O) S7 a% C
可见题目中并没有不等式约束关系，同时也没有约束上界ub。
0 E; U" `" q! o. _+ |& M2 J
Matlab
程序实现
$ G5 y+ I$ d' J8 d5 ?
clc;clear %清空数据防止干扰
1 G; s" b% ^7 d+ D4 m( j# _
f=[3;11;3;10;1;9;2;8;7;4;10;5]; %价值向量
, K2 F( C( T2 k8 Q0 u. G
aeq=[ones(1,4),zeros(1,8); %线性等式约束 构造矩阵
! G3 _8 a5 _: b& ?8 o/ z* G
zeros(1,4),ones(1,4),zeros(1,4);
7 G& v( j4 t! I$ a. E2 T. D
zeros(1,8),ones(1,4);
+ u0 T8 d) P# u2 O
1,zeros(1,3),1,zeros(1,3),1,zeros(1,3);
# ~4 Y7 j# R% f
0,1,zeros(1,2), 0,1,zeros(1,2), 0,1,zeros(1,2);
" {* r+ y5 I: ?$ x" \
zeros(1,2),1,0, zeros(1,2),1,0, zeros(1,2),1,0;
- x5 d8 C3 E3 \9 D2 J/ f5 M
zeros(1,3),1,zeros(1,3),1,zeros(1,3),1];
* K. q; H' n" E/ f$ Q& E h7 `8 x
beq=[7;4;9;3;6;5;6]; %线性等式约束
& h1 ~: I+ ]) V1 |9 r" G: |/ q+ N$ |
[x,y]=linprog(f,[],[],aeq,beq,zeros(12,1)) %求解
7 Y( Z5 u9 r* _8 E, J; B* @
题目答案：
: Q% m( D2 V: d$ I
x=[0;0;5;2;3;0;0;1;0;6;0;3]
* V D3 Z7 N6 F# T8 E) e
y=85
7 M* b9 | T ]6 R8 p) q, K
. Q6 T i5 [4 w$ Q. c [" F
2 p" v6 u; n/ X2 P K
. O- \9 d9 b3 P+ E
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
+ t: J4 `- o0 O) H
2 S/ N! O) S7 a% C