线性规划——运输问题（产销平衡）

1047521767

运输问题（产销平衡）
$ S( O  i  _5 o, U1 T  某商品有m 个产地、n 个销地，各产地的产量分别为a1,a2,…am ，各销地的 需求量分别为b,…bn , , 1 L 。若该商品由i 产地运到 j 销地的单位运价为 cij ，问应该如何调 运才能使总运费最省？
3 P! t6 R  E9 t  r" n7 j
  解：引入变量 xij ，其取值为由i 产地运往 j 销地的该商品数量，数学模型为
% h* }! F3 Q$ c- n
0 I2 f) L. L0 `4 j# |' ], ~* i                                         
' E7 N5 a3 \8 K* {/ x* V          显然是一个线性规划问题，当然可以用单纯形法求解。

  对产销平衡的运输问题，由于有以下关系式存在：

其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习惯上称为表上作业法（由 康托洛维奇和希奇柯克两人独立地提出，简称康—希表上作业法）
- ~' M3 _0 _1 Q9 ^  k
例题：
+ [3 U0 t5 @7 f. q4 Q! b) q8 G
7 }" w# ]9 {6 }) ~  某公司有三个加工厂A1，A2.A3生产某产品，每日的产量分别为：7吨、4吨、9吨；该公司把这些产品分别运往四个销售点B1，B2、B3、B4，各销售点每日销量分别为：3吨、6吨、5吨、6吨；从各工厂到各销售点的单位产品运价如表4-1所示。问该公司应如何调运这些产品，在满足各销售点的需要量的前提下，使总运费最少？
" u( x( }3 w1 j* Y) }) M0 P4 A5 c
解析： 典型的产销平衡问题，将已知数据做成表格如下：


将所有数据列成表格会更加清晰，根据题意可以得到目标函数的表达式如下：
4 s* w- n+ \6 }: d4 l! w  G
1 n  u0 Z' X8 f然后将已知约束关系整理如下：
, _( V6 t; a0 X
" v8 v" T/ |& S% B, X9 T- }可见题目中并没有不等式约束关系，同时也没有约束上界ub。
Matlab 程序实现
clc;clear                                %清空数据防止干扰
3 L9 L+ o# e0 h7 K7 Cf=[3;11;3;10;1;9;2;8;7;4;10;5];        %价值向量
aeq=[ones(1,4),zeros(1,8);                %线性等式约束        构造矩阵
) B, D% d1 p% ?, A1 l: R% I+ Z    zeros(1,4),ones(1,4),zeros(1,4);
    zeros(1,8),ones(1,4);
4 O( e, ]( ~  q$ Z, ]    1,zeros(1,3),1,zeros(1,3),1,zeros(1,3);
$ c- V- y) B3 E- ]& K    0,1,zeros(1,2), 0,1,zeros(1,2), 0,1,zeros(1,2);
5 {0 g# D7 ]1 f: M( @. H    zeros(1,2),1,0, zeros(1,2),1,0, zeros(1,2),1,0;
% g0 q+ Y) Q. h& y, G8 }/ r1 k    zeros(1,3),1,zeros(1,3),1,zeros(1,3),1];
4 x- y, t' J: V( q2 F# ?  s1 @beq=[7;4;9;3;6;5;6];                        %线性等式约束
" m! a( x( |" E8 R1 J3 Q[x,y]=linprog(f,[],[],aeq,beq,zeros(12,1))        %求解
4 B! K  A) `% Q; q题目答案：
x=[0;0;5;2;3;0;0;1;0;6;0;3]
( A  z8 p. e: R1 ?3 w9 x* i3 xy=85



7 ?5 c+ x) G" {. Q( g6 X