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

1047521767

运输问题（产销平衡）
2 s) T2 R% R8 Z# y  某商品有m 个产地、n 个销地，各产地的产量分别为a1,a2,…am ，各销地的 需求量分别为b,…bn , , 1 L 。若该商品由i 产地运到 j 销地的单位运价为 cij ，问应该如何调 运才能使总运费最省？

$ \& @2 f, l) J3 Z. O8 p9 \  解：引入变量 xij ，其取值为由i 产地运往 j 销地的该商品数量，数学模型为
- d& b* W8 a( Q1 w
                                         
          显然是一个线性规划问题，当然可以用单纯形法求解。

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

其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习惯上称为表上作业法（由 康托洛维奇和希奇柯克两人独立地提出，简称康—希表上作业法）
; y- S( G2 a: ^2 \- H% e8 H+ C: T7 Y
例题：

7 X( f. \* v1 a+ w5 u: H  某公司有三个加工厂A1，A2.A3生产某产品，每日的产量分别为：7吨、4吨、9吨；该公司把这些产品分别运往四个销售点B1，B2、B3、B4，各销售点每日销量分别为：3吨、6吨、5吨、6吨；从各工厂到各销售点的单位产品运价如表4-1所示。问该公司应如何调运这些产品，在满足各销售点的需要量的前提下，使总运费最少？
  Q8 E! X% v0 i
* g) W* b8 F$ ^5 H9 S8 W/ q解析： 典型的产销平衡问题，将已知数据做成表格如下：
1 W3 u3 d; H0 Q( o
5 j' y# c5 X. u: u
将所有数据列成表格会更加清晰，根据题意可以得到目标函数的表达式如下：
4 o# E1 C0 D* Z& {
7 D6 g8 p+ [% B. C然后将已知约束关系整理如下：

可见题目中并没有不等式约束关系，同时也没有约束上界ub。
* L; D4 n2 N# O4 I, ~3 D# ~, QMatlab 程序实现
8 h  k& i6 W2 l9 gclc;clear                                %清空数据防止干扰
+ t/ J8 u" N' T9 S: D, C" xf=[3;11;3;10;1;9;2;8;7;4;10;5];        %价值向量
8 m2 e. t4 r5 [aeq=[ones(1,4),zeros(1,8);                %线性等式约束        构造矩阵
% I. ^# ?; O# |4 K; W* L    zeros(1,4),ones(1,4),zeros(1,4);
, E5 T* J- Q  H1 M    zeros(1,8),ones(1,4);
- m4 z: r) O8 Z$ n3 H! b. c    1,zeros(1,3),1,zeros(1,3),1,zeros(1,3);
$ \9 K: j7 L+ ]- a1 v; d    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];                        %线性等式约束
2 w- }; L, N% J; G0 z[x,y]=linprog(f,[],[],aeq,beq,zeros(12,1))        %求解
/ R/ l+ W% t( |( o+ v! q' o题目答案：
' Q) x7 W$ Y3 Vx=[0;0;5;2;3;0;0;1;0;6;0;3]
0 l! r; l- N7 Q2 |$ vy=85
% |# ]! O. G6 Y. E- n% L

5 |" _- G, \' o7 X