补充—整数规划例题

1.将非线性0-1问题转成线性0-1问题

• 例题1
  

先做变量替换，把y=x(1)x(2)，有如下关系：

x(1) + x(2) - 1 ≤ y ≤ x(1)
x(1) + x(2) - 1 ≤ y ≤ x(2)

从而有线性0-1规划为：

max z = x(1) + y - x(3)
s.t.:
     -2x(1) + 3x(2) + x(3) ≤ 3,
      x(1) + x(2) - 1 ≤ y ≤  x(1),
      x(1) + x(2) - 1 ≤ y ≤  x(2),
      x(j) = 0 或 1, j = 1:3
      y = 0 或 1 
     

2.指派问题

• 例题2
  一车队有8辆车 这8辆车存放在不同的地点，队长要 要派其中5辆到5个不同的工地去运货。各车从存放 处调到装货地点所需费用列于表2 5，问应选用哪5辆车调 到何处去运货,才能使各车从所在地点调到装货地点所需的总费用最少？
  
  记c(i)(j)表示第 j 号车调到装货地点 i 所需的费用。引入0-1变量：
  x(i)(j) = 1表示第 j 号车调到装货地点 i ，反之x(i)(j) = 0表示第 j 号车没有被调到装货地点 i。
  建立0-1整数规划模型：
  

% 将二维决策变量Xij(i=1:5,j=1:8)变为一维决策变量yk(k=1:40)
clc,clear
c = [30,25,18,32,27,19,22,26
     29,31,19,18,21,20,30,19
     28,29,30,19,19,22,23,26
     29,30,19,24,25,19,18,21
     21,20,18,17,16,14,16,18];
c=c(:);
a=zeros(8,40); % 8行40列的零矩阵
intcon=1:40; % 一维决策变量中k的取值
for j=1:8 % 对行操作
    a(j,(j-1)*5+1:j*5) = 1;
end
b=ones(8,1); % 8行1列的为1矩阵
Aeq=zeros(5,40);
for i=1:5 % 对列操作
    Aeq(i,i:5:40) = 1;
end
beq=ones(5,1);
lb=zeros(40,1);
ub=ones(40,1);
[x,y] = intlinprog(c,intcon,a,b,Aeq,beq,lb,ub);
x = reshape(x,[5,8]),y % reshape是输出5行8列矩阵

输出为

x =

     0     0     1     0     0     0     0     0
     0     0     0     1     0     0     0     0
     0     0     0     0     1     0     0     0
     0     0     0     0     0     0     1     0
     0     0     0     0     0     1     0     0

最低总费用为 y = 87