[建模教程] 线性规划（二）：运输问题 (产销平衡) & 指派问题

[复制链接]

字体大小: 正常放大

浅夏110

542 主题	15 听众	1万积分

TA的每日心情

	开心 2020-11-14 17:15

签到天数: 74 天

[LV.6]常住居民II

群组: 2019美赛冲刺课程

群组: 站长地区赛培训

群组: 2019考研数学桃子老师

群组: 2018教师培训（呼伦贝

群组: 2019考研数学站长系列

电梯直达

1^#

发表于 2020-6-6 10:08 |只看该作者 |倒序浏览

|招呼Ta 关注Ta |邮箱已经成功绑定

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

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

3. 指派问题的数学模型

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

求解指派问题的匈牙利算法

有时问题会稍复杂一些。

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

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

解：编写 Matlab 程序如下：求得最优值为 21，最优指派方案为

c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5
8 4 2 3 5;9 10 6 9 10];
c=c(

;
a=zeros(10,25);
for i=1:5
a(i,(i-1)*5+1:5*i)=1;
a(5+i,i:5:25)=1;
end
b=ones(10,1);
[x,y]=bintprog(c,[],[],a,b);
x=reshape(x,[5,5]),y

求解的 LINGO 程序如下：

model:
sets:
var/1..5/;
link(var,var):c,x;
endsets
data:
c=3 8 2 10 3
  8 7 2 9 7
  6 4 2 7 5
  8 4 2 3 5
  9 10 6 9 10;
enddata
min=@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(link

bin(x));
end

————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/88894966

zan