数学建模社区-数学中国
标题:
线性规划——运输问题（产销平衡）
[打印本页]
作者:
1047521767
时间:
2021-10-28 18:50
标题:
线性规划——运输问题（产销平衡）
运输问题（产销平衡）
7 h* Q+ e2 r5 T5 z1 I2 o) f) K
某商品有m 个产地、n 个销地，各产地的产量分别为a1,a2,…am ，各销地的 需求量分别为b,…bn , , 1 L 。若该商品由i 产地运到 j 销地的单位运价为 cij ，问应该如何调 运才能使总运费最省？
5 m* p- b& V: y
^2 f3 p( F% F" P, T+ E- W
解：引入变量 xij ，其取值为由i 产地运往 j 销地的该商品数量，数学模型为
Q3 ^# ?( A0 W$ S5 Y7 c
, y" H" d' i3 q- U+ f6 i! F
- K/ U8 ~7 C, e5 x8 ^* Q
显然是一个线性规划问题，当然可以用单纯形法求解。
对产销平衡的运输问题，由于有以下关系式存在：
其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习惯上称为表上作业法（由 康托洛维奇和希奇柯克两人独立地提出，简称康—希表上作业法）
% A( b2 {. B c8 J! M3 t
! d3 i/ F( c. j$ J
例题：
T5 x, x- T' e5 K4 R& b. `# d
: Q" R- X! }. E/ q' q
某公司有三个加工厂A1，A2.A3生产某产品，每日的产量分别为：7吨、4吨、9吨；该公司把这些产品分别运往四个销售点B1，B2、B3、B4，各销售点每日销量分别为：3吨、6吨、5吨、6吨；从各工厂到各销售点的单位产品运价如表4-1所示。问该公司应如何调运这些产品，在满足各销售点的需要量的前提下，使总运费最少？
: S& E) C. q6 |- x
) i' B: Y1 h5 \& a5 N$ w% s
解析： 典型的产销平衡问题，将已知数据做成表格如下：
( E2 d* A3 p6 C6 T
! ]8 H$ T$ C8 k* h4 D
. c8 Z1 p2 k+ ~
将所有数据列成表格会更加清晰，根据题意可以得到目标函数的表达式如下：
' I' r) p( ^$ U& b8 W! h2 o
1 r' n0 x$ H5 h( A/ Y) K! D; y
然后将已知约束关系整理如下：
* l/ n. t! }+ z6 y$ h2 m9 L
8 n: u5 l. X& S
可见题目中并没有不等式约束关系，同时也没有约束上界ub。
8 c- W; j( w4 G
Matlab
程序实现
' w5 V) h0 a5 E+ ]
clc;clear %清空数据防止干扰
t8 M! ~$ S4 m8 Q) R
f=[3;11;3;10;1;9;2;8;7;4;10;5]; %价值向量
7 m1 u. }" L8 K' B; P( H$ x
aeq=[ones(1,4),zeros(1,8); %线性等式约束 构造矩阵
6 o" ^9 }4 W: q8 W
zeros(1,4),ones(1,4),zeros(1,4);
* U2 p: e, _) p6 N( H, x% Q
zeros(1,8),ones(1,4);
6 R8 {) Q+ s; g& k
1,zeros(1,3),1,zeros(1,3),1,zeros(1,3);
( Q2 e* {0 k( P& z0 }' P
0,1,zeros(1,2), 0,1,zeros(1,2), 0,1,zeros(1,2);
+ k# o- F% W. O3 j, ^: J3 P5 F0 m
zeros(1,2),1,0, zeros(1,2),1,0, zeros(1,2),1,0;
4 X8 U7 [) D$ E" T: Y- N
zeros(1,3),1,zeros(1,3),1,zeros(1,3),1];
& h7 C. K ^: f) z+ R
beq=[7;4;9;3;6;5;6]; %线性等式约束
! B, j0 y- _2 {# k
[x,y]=linprog(f,[],[],aeq,beq,zeros(12,1)) %求解
7 r, r+ t8 u2 v1 f) l% C. }/ t
题目答案：
( B' u4 i* m, N& U* | K
x=[0;0;5;2;3;0;0;1;0;6;0;3]
: J e& w, J' H" x/ s+ c5 d- n
y=85
6 ~2 {" B8 |; t* x' m* S
! \" C, h2 Y O2 x, z" \/ t
* E% G2 K" G, X: N" Z3 H
; G, T! c! n" q. H1 G/ ?: C
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
1 r' n0 x$ H5 h( A/ Y) K! D; y
8 n: u5 l. X& S