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

1047521767

运输问题（产销平衡）
* F9 a0 K8 ~4 I7 q0 I/ c  某商品有m 个产地、n 个销地，各产地的产量分别为a1,a2,…am ，各销地的 需求量分别为b,…bn , , 1 L 。若该商品由i 产地运到 j 销地的单位运价为 cij ，问应该如何调 运才能使总运费最省？
8 H  D& g4 p( K! [1 s/ W6 u
, v( ^; j9 S# ^* r: [! [  解：引入变量 xij ，其取值为由i 产地运往 j 销地的该商品数量，数学模型为
2 O' ]9 O0 z# V1 ^% R
1 u8 f0 K" y: ]' `: u: {2 \5 B8 p                                         
. ]' [5 `! s& f7 h5 @1 b          显然是一个线性规划问题，当然可以用单纯形法求解。

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

其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习惯上称为表上作业法（由 康托洛维奇和希奇柯克两人独立地提出，简称康—希表上作业法）

* Q# N- ?& Q# }. c( n# P. |! z例题：
4 S0 A; c! _3 |; X- Y. J
5 R$ j0 R9 f3 l) X  某公司有三个加工厂A1，A2.A3生产某产品，每日的产量分别为：7吨、4吨、9吨；该公司把这些产品分别运往四个销售点B1，B2、B3、B4，各销售点每日销量分别为：3吨、6吨、5吨、6吨；从各工厂到各销售点的单位产品运价如表4-1所示。问该公司应如何调运这些产品，在满足各销售点的需要量的前提下，使总运费最少？
$ m: d+ G" G( d6 F5 w& L
解析： 典型的产销平衡问题，将已知数据做成表格如下：
2 f  D2 K" M6 x! V

6 C- `3 a: o8 U' s$ a将所有数据列成表格会更加清晰，根据题意可以得到目标函数的表达式如下：
. m* l8 q' `$ N" D# N+ w+ G* }
. y. u! k8 L' o6 g( R1 j# C+ e: L$ G  a然后将已知约束关系整理如下：

$ k( ?) A  t. ]6 h可见题目中并没有不等式约束关系，同时也没有约束上界ub。
1 Q+ n) `; y* r7 @- D: U  VMatlab 程序实现
4 z5 D+ Q" j& p# R+ e1 {clc;clear                                %清空数据防止干扰
4 X; ^$ E: z& o2 E" yf=[3;11;3;10;1;9;2;8;7;4;10;5];        %价值向量
aeq=[ones(1,4),zeros(1,8);                %线性等式约束        构造矩阵
    zeros(1,4),ones(1,4),zeros(1,4);
    zeros(1,8),ones(1,4);
: W1 L9 @0 z) W# L8 J$ x: Z    1,zeros(1,3),1,zeros(1,3),1,zeros(1,3);
    0,1,zeros(1,2), 0,1,zeros(1,2), 0,1,zeros(1,2);
    zeros(1,2),1,0, zeros(1,2),1,0, zeros(1,2),1,0;
    zeros(1,3),1,zeros(1,3),1,zeros(1,3),1];
beq=[7;4;9;3;6;5;6];                        %线性等式约束
1 X2 b) j  x+ f: ?( X% N& R4 N[x,y]=linprog(f,[],[],aeq,beq,zeros(12,1))        %求解
3 L. D1 [, [0 o" c3 e/ k! H题目答案：
  u7 F1 B) I# n) `& T# j* ]x=[0;0;5;2;3;0;0;1;0;6;0;3]
# S8 R" G; \  k* M- O  V  C( Q1 iy=85


9 u7 Q' f- T$ e8 W& |, Q) v
5 i! S) E& \7 I$ i& u