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

1047521767

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

, W* X; E3 ?+ m  D: }; m9 S* ]. ~  解：引入变量 xij ，其取值为由i 产地运往 j 销地的该商品数量，数学模型为
5 l" y- I+ N5 j0 f  l
: j6 E+ o1 x( U0 s6 |                                         
  w+ Y- B- l& V1 l          显然是一个线性规划问题，当然可以用单纯形法求解。

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

其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习惯上称为表上作业法（由 康托洛维奇和希奇柯克两人独立地提出，简称康—希表上作业法）
6 L3 |  Y. Y  D4 r6 z9 O
  ~. {0 e1 g9 X  ]% m( t& Z  x例题：
# a; N# [1 L5 K& D4 ?0 H: K- k
  某公司有三个加工厂A1，A2.A3生产某产品，每日的产量分别为：7吨、4吨、9吨；该公司把这些产品分别运往四个销售点B1，B2、B3、B4，各销售点每日销量分别为：3吨、6吨、5吨、6吨；从各工厂到各销售点的单位产品运价如表4-1所示。问该公司应如何调运这些产品，在满足各销售点的需要量的前提下，使总运费最少？
  l! |- f4 ~; P0 |" j
% w2 T1 Y# b8 v" q- n% T: c% H解析： 典型的产销平衡问题，将已知数据做成表格如下：

3 p! L, Y% j  S
将所有数据列成表格会更加清晰，根据题意可以得到目标函数的表达式如下：
2 ^9 f& Q& ]/ j6 ~' N0 w0 _7 L
3 V* `0 G, w/ A5 _  c( u6 |然后将已知约束关系整理如下：

可见题目中并没有不等式约束关系，同时也没有约束上界ub。
Matlab 程序实现
clc;clear                                %清空数据防止干扰
f=[3;11;3;10;1;9;2;8;7;4;10;5];        %价值向量
4 n7 \4 y% ]: F: oaeq=[ones(1,4),zeros(1,8);                %线性等式约束        构造矩阵
2 y0 l  A  `; X' a' g( N    zeros(1,4),ones(1,4),zeros(1,4);
    zeros(1,8),ones(1,4);
' i: M8 O; Q5 g6 L    1,zeros(1,3),1,zeros(1,3),1,zeros(1,3);
/ t' j9 _+ L/ r. s/ r8 V' }5 Q. O    0,1,zeros(1,2), 0,1,zeros(1,2), 0,1,zeros(1,2);
- J4 }7 m8 E8 F( t6 v3 I* ^    zeros(1,2),1,0, zeros(1,2),1,0, zeros(1,2),1,0;
9 V3 g$ G) X% T# R) c    zeros(1,3),1,zeros(1,3),1,zeros(1,3),1];
beq=[7;4;9;3;6;5;6];                        %线性等式约束
[x,y]=linprog(f,[],[],aeq,beq,zeros(12,1))        %求解
9 {% k7 I% `2 p! J! c0 l题目答案：
& S. l9 o1 a! ]% d9 u2 @4 kx=[0;0;5;2;3;0;0;1;0;6;0;3]
) k3 w( m& r" y8 ]- Gy=85
' [6 F0 s. r7 B, w* Q1 M  S- S7 J

. ?: m: K+ x: `; i. c" S, o& }; g5 ?