线性规划（一）：运输问题 (产销平衡) & 指派问题

1440359316

1.可以转化为线性规划的问题

很多看起来不是线性规划的问题也可以通过变换变成线性规划的问题来解决。下面举几个例子：

2. 运输问题(产销平衡)  ：康—希表上作业法

3. 指派问题的数学模型

上述指派问题的可行解可以用一个矩阵表示，其每行每列均有且只有一个元素为 1，其余元素均为 0；可以用 1,...,n 中的一个置换表示。 问题中的变量只能取 0 或 1，从而是一个 0-1 规划问题。一般的 0-1 规划问题求解 极为困难。但指派问题并不难解，其约束方程组的系数矩阵十分特殊（被称为全单位模矩阵，其各阶非零子式均为正负1 ），其非负可行解的分量只能取0或1，故约束 =0或1 可改写为 而不改变其解。此时指派问题被转化为一个特殊的运输问题，其中m=n,
求解指派问题的匈牙利算法

有时问题会稍复杂一些。

例 9 求解系数矩阵C 的指派问题

3 T& _6 ^1 G$ Q2 j, M" }* o- V

* s5 v  f  }6 l  p+ S+ j8 g: o

4. 指派问题的计算机求解整数规划问题的求解可以使用 Lingo 等专用软件。对于一般的整数规划问题，无法 直接利用 Matlab 的函数，必须利用 Matlab 编程实现分枝定界解法和割平面解法。但对 于指派问题等 0−1整数规划问题，可以直接利用 Matlab 的函数 bintprog 进行求解。
$ I6 |  F. J" X/ E  l0 R2 d8 x

9 w3 c0 u* g: ?6 [  f4 t解：编写 Matlab 程序如下： 求得最优值为 21，最优指派方案为 .
c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5   
+ d6 y$ ]5 U7 E2 h- S   8 4 2 3 5;9 10 6 9 10];
c=c(;
- G' s( f: f3 L8 J" T& Ua=zeros(10,25);
8 `: |- B9 L. M2 \6 s; Jfor i=1:5   
, v% G2 {4 q+ F0 V+ u  e    a(i,(i-1)*5+1:5*i)=1;   
    a(5+i,i:5:25)=1;
) R( D# T( w3 Y& G" Bend
& e/ X& R3 P5 a) ]b=ones(10,1);
[x,y]=bintprog(c,[],[],a,b);
! e! [5 d* t5 d  O. _# v: x: mx=reshape(x,[5,5]),y

7 V2 v' U# U  U8 j1 K" X求解的 LINGO 程序如下：
) N4 o/ t5 r9 \' \model:
sets:
5 p, M1 k' V8 p* L4 y4 U/ H+ jvar/1..5/;
link(var,var):c,x;
endsets
data:
" s% r0 Q3 z& e* Q0 r5 w5 m  C6 H! \c=3 8 2 10 3   
  8 7 2 9 7   
% p* G  t  K! i! M  j  6 4 2 7 5   
  8 4 2 3 5   
  9 10 6 9 10;
; h% [) [- ?, H7 C  Oenddata
( K! ]: A, x4 p! c- _! n' }" Hmin=@sum(link:c*x);
@for(var(i)sum(var(j):x(i,j))=1);
@for(var(j)sum(var(i):x(i,j))=1);
@for(linkbin(x));
end

* {! K% z; F4 K! v

sjlxdn

1111111111111