Integer-programming

整数规划

线性规划 LP 问题

各变量可以是小数来逼近最值

model:
max 5*x1+8*x2;
x1+x2<6;
5*x1+9*x2<=45;
end
输出
 Objective value:             41.25000
 X1        2.250000            0.000000
 X2        3.750000            0.000000

整数规划 IP 松弛问题

model:
sets:
col/1,2/;
hh(col):x;
endsets
MAX = 5*x(1)+8*x(2);
x(1)+x(2)<6;
5*x(1)+9*x(2)<=45;
@for(col(j):@gin(x(j)));!这句话是限制变量为整数（gin）;
END
输出
Objective value:                              40.00000
Variable           Value        Reduced Cost
X( 1)        0.000000           -5.000000
X( 2)        5.000000           -8.000000

动态规划–最短路径

model:
sets:
citles/1..9/:L;
roads(citles,citles)/
9,6,9,7,9,8
6,4,6,5,7,4,7,5,8,4,8,5
4,2,4,3,5,2,5,3
2,1,3,1/:D;
endsets
data:
D=
6 3 3
6 5 8 6 7 4
6 7 8 9
5 6;
enddata
L(1)=0;
@for(citles(i)|i#GT#1:
L(i) = @min(roads(i,j):D(i,j)+L(j)));
end
输出
 Variable           Value
    L( 1)        0.000000
    L( 2)        5.000000
    L( 3)        6.000000
    L( 4)        11.00000
    L( 5)        13.00000
    L( 6)        17.00000
    L( 7)        19.00000
    L( 8)        17.00000
    L( 9)        20.00000
D( 9, 6)        6.000000
D( 9, 7)        3.000000
D( 9, 8)        3.000000
D( 6, 4)        6.000000
D( 6, 5)        5.000000
D( 7, 4)        8.000000
D( 7, 5)        6.000000
D( 8, 4)        7.000000
D( 8, 5)        4.000000
D( 4, 2)        6.000000
D( 4, 3)        7.000000
D( 5, 2)        8.000000
D( 5, 3)        9.000000
D( 2, 1)        5.000000
D( 3, 1)        6.000000

1. 所有函数均以@开头
2. citles 表示从 1~9 组成的集合，属性 L(i)表示最优行驶路线长
3. 集合循环语句#GT#表示逻辑关系大于
4. L(i) = @min(roads(i,j):D(i,j)+L(j)))即为动态规划基本方程

选课模型–0-1 规划

model:
sets:
Shuliang/1..18/:m;
Xuanke(Shuliang):x;
endsets
data:
m = 5,5,4,4,3,3,3,2,3,3,3,2,2,2,2,1,1,1;
enddata
min=@sum(Xuanke(i):x(i));
@for(Xuanke(k):@bin(x(k)));
@sum(Xuanke(i):m(i)*x(i))>=18;
@sum(Xuanke(j)|j#ge#9#and#j#le#18:m(j)*x(j))<=@sum(Xuanke(i):m(i)*x(i))/3;!j大于9小于18，i的范围为1~18
@sum(Xuanke(j)|j#ge#9#and#j#le#18:m(j)*x(j))>=@sum(Xuanke(i):m(i)*x(i))/6;
x(1)>=x(5);
x(2)>=x(7);
x(8)>=x(9);
x(6)>=x(10);
x(4)>=x(11);
x(5)>=x(12);
x(7)>=x(13);
x(6)>=x(14);
end
输出
Objective value:                              5.000000
X( 1)        1.000000            1.000000
X( 2)        1.000000            1.000000
X( 3)        0.000000            1.000000
X( 4)        1.000000            1.000000
X( 5)        0.000000            1.000000
X( 6)        0.000000            1.000000
X( 7)        0.000000            1.000000
X( 8)        0.000000            1.000000
X( 9)        0.000000            1.000000
X( 10)        0.000000            1.000000
X( 11)        1.000000            1.000000
X( 12)        0.000000            1.000000
X( 13)        0.000000            1.000000
X( 14)        0.000000            1.000000
X( 15)        1.000000            1.000000
X( 16)        0.000000            1.000000
X( 17)        0.000000            1.000000
X( 18)        0.000000            1.000000

由此得出选课方案，一共选 5 门，为 x 矩阵中为 1 的变量。
这里发现了 Lingo 的一个非常棒的检查代码的功能！就是模型编译！它可以直接把代码翻译成数学公式，如图 简直神器！！这样就可以看看翻译成的式子是不是自己想要的从而检查代码哪里写错了！点赞 👍

连续规划 –石油购买

这里遇到一种新情况，即分段规划，比如：当购买量不超过 500 吨时，单价 10000 元；当购买量超过 500 吨但不超过 1000 吨，超过的部分 8000 元，当超过 1000 吨但不超过 1500 吨，超过的部分 6000 元。
这里有多种方法可以实现。
第一种–巧用 if 语句

model:
sets:
buy/1,2,3/:r;
nums/1,2/;
goods(nums):x;
endsets
max = 4800*x(1)+5600*x(2)-10000*r(1)-8000*r(2)-6000*r(3);
0.5*x(1)+0.6*x(2)<=500+r(1)+r(2)+r(3);
0.5*x(1)+0.4*x(2)<=1000;
r(1)<=500;
r(3)<=500;
r(2)<=500;
r(2)=@if(r(1)#lt#500,0,r(2));!由于@if语句第一个是判断条件，第二个是为真时的值，第三个是为假的值，而这里必须是个数而不能表示成<=500，因此让它等于自身;
r(3)=@if(r(2)#lt#500,0,r(3));
end

第二种–引入 0-1 变量，转换成线性约束
这里约定，为第一阶段购买原油吨，为第二阶段，为第三阶段,表示是否购买.
核心代码：

x1-500*y1<=0;
x2-500*y2<=0;
x3-500*y3<=0;
x1-500*y2>=0;
x2-500*y3>=0;
@bin(y1);
@bin(y3);
@bin(y2);
得到方案
Variable           Value        Reduced Cost
R( 1)        500.0000            0.000000
R( 2)        500.0000            0.000000
R( 3)        0.000000            6000.000
X( 1)        0.000000            2200.000
X( 2)        2500.000            0.000000