整数规划2024.1.17

发布时间：2024年01月18日

线性整数规划

? ? ? ? 约束和目标函数均为线性，但变量值为整数。实际应用有去和不去、取和不取等01决策问题和物品不可拆分、所求人数等要求变量为整数的问题。

????????指派问题

????????????????x_{i,j}=\left\{\begin{matrix} 1 & i \ go\ to\ do \ j\\ 0& i \ not\ go\ to\ do \ j \end{matrix}\right.

????????????????\sum_{i=1}^{n} x_{i,j}=1每个任务指派一个人

????????????????\sum_{j=1}^{m}x_{i,j}=1每个人只做一项任务

? ? ? ? 旅行商问题

? ? ? ? 从任意城市出发，每个城市只经过依次，任意两个城市之间通过有费用，问最终回到出发城市的最小费用。

????????????????x_{i,j}=\left\{\begin{matrix} 1 & i \rightarrow j\\ 0& i\ not\ to \ j \end{matrix}\right.

????????????????c_{i,i}=inf，避免绕环

????????????????optimproblem=min \sum\sum c_{i,j}*x_{i,j}

????????????????s.t.\left\{\begin{matrix} \sum_{i=1}^{n}x_{i,j}=1 &(1) \\ \sum_{j=1}^{n}x_{i,j}=1&(2) \\ u_i-u_j+nx_{i,j}\leq n-1 &i=1,2\cdots n,j=2,3\cdots n&(3) \end{matrix}\right.

????????(1)?指只进入j一次，即j的入度为1

????????(2)?指从i只出去一次，即i的出度为1

  • ?(3)?
    • 定义u_i为从出发点到i的编号，起点编号为0，第二个到达点为1，依次增加。则u_i\in[0,n-1]
    • 若x_{i,j}=1，则u_j> u_i,u_i-u_j=-1。若x_{i,j}=0，则u_i-u_j\leq n-1。
    • 对于不含子回路的路线，由于当u_i> u_j时，只有x_{n,1}=1。所以约定i=1,2\cdots n,j=2,3\cdots n。一定满足u_i-u_j+nx_{i,j}\leq n-1。
    • 对于含子回路的路线，由于当u_i> u_j时，不一定为x_{n,1}=1，还可能有其他的边。\therefore \exists u_i,u_j,u_i-u_j+nx_{i,j}>n-1，所以不满足约束
    • 所以(3)约束排除了含有子回路的路线

?排斥约束线性化——利用01决策

? ? ? ? 单端不等式之间的排斥约束

? ? ? ? 有m个互斥的不等式约束，每次满足一个即可。

????????????????y_i=\left\{\begin{matrix} 1 & s.t.i \ use\\ 0 & s.t.i\ not \ use \end{matrix}\right.

? ? ? ? 将不等式都化为同类型，则

????????????????s.t.\Rightarrow \left\{\begin{matrix} a_{i,1}x_{i,1}+a_{i,2}x_{i,2}+\cdots \leq b_i+(1-y_i)M& \\ \sum_{i=1}^{m} y_i=1 \\ i=1,2,\cdots m\ \ \ \ M\rightarrow inf \end{matrix}\right.

? ? ? ? 等式与双端不等式之间的排斥约束

????????????????x=c?或?a\leqslant x\leqslant b

????????????????s.t.\Rightarrow \left\{\begin{matrix} ay+(1-y)c\leqslant x\leqslant by+(1-y)c\\ y=0/1 \end{matrix}\right.

????????扩展：

? ? ? ? (1)?有n个等式和m个双端不等式，将n个等式放在m个双端不等式中

????????????????y_t=\left\{\begin{matrix} 1 & s.t.t \ use\\ 0 & s.t.t\ not \ use \end{matrix}\right.

????????????s.t.\Rightarrow \left\{\begin{matrix} a_jy_{n+j}+c_1y_1+c_2y_2+\cdots+c_ny_n \leq x\leq b_jy_{n+j}+c_1y_1+c_2y_2+\cdots+c_ny_n & \\ i=1,2,\cdots n\\ j=1,2,\cdots m\\ \sum_{t=1}^{n+m} y_t=1 \end{matrix}\right.

????????(2)?单端不等式可以转为双端不等式

????????????????x\leq b\Rightarrow \varepsilon \leq x\leq b, \varepsilon \rightarrow -inf

????????????????a\leq x\Rightarrow a\leq x\leq M,M\rightarrow inf

? ? ? ? ? ? ? ? ? ?

? ? ? ? 例题：

? ? ? ? ?工厂生产产品有n种方式，问生产一批产品所用的最小成本。

? ? ? ? ?定义：

? ? ? ???????????x_i表示采用第i种方式生产的产品个数

????????????????c_i表示采用第i种方式生产每件产品的变动成本（即额外成本）

????????????????k_i表示采用第i种方式生产的固定成本（即必需成本）

? ? ? ? 则每种生产方式对应的成本为

????????????????P_{i}=\left\{\begin{matrix} k_i+c_ix_i & x_i> 0\\ 0 & x_i=0 \end{matrix}\right.

? ? ? ? 分段函数，有两个互相排斥的约束，用01决策转化，则

????????????????P_i=y_i(k_i+c_ix_i)+(1-y_i)*0

????????????????s.t.=\left\{\begin{matrix} 0*y_i\leq x_i\leqslant M*y_i & \\ y_i=0/1& \end{matrix}\right.

????????\therefore optimproblem=min \sum_{i=1}^n P_i

????????????????

整数规划典型题

???????问题描述? ?

????????10个站点，在站点上建立网点进行网络覆盖 。一个网点可以覆盖到与它距离小于等于10的站点，且一个网点最多只能覆盖5个站点。问如何建立最少的网点实现全覆盖。

????????数据如下

竖着为一个站点坐标
9.4888	8.7928	11.5960	11.5643	5.6756	9.8497	9.1756	13.1385	15.4663	15.5464
5.6817	10.3868	3.9294	4.4325	9.9658	17.6632	6.1517	11.8569	8.8721	15.5868

? ? ? ? 解题思路

  • ? ?y_{i,j}=\left\{\begin{matrix} 1 & i\ cover\ j\\ 0& i\ not\ cover\ j \end{matrix}\right.
  • 一个网点最多覆盖5个，且满足全覆盖，则\sum_{j=1}^{10}y_{i,j}\leq 5,\sum_{i=1}^{10}y_{i,j}\geq 1
  • 求出任意两个站点之间的距离d_{i,j}，利用dist()?（给10个坐标，返回10x10的矩阵）
  • 一个网点可以覆盖到与它距离小于等于d的站点，则d_{i,j}y_{i,j}\leq 10
  • y_{i,i}=1?表示在i处建立网点
  • optimproblem=min\sum_{i=1}^{10}y_{i,i}，即sum(diag(y))
  • y_{i,i}\geq y_{i,j}，

\therefore

????????optimproblem=min \sum_{i=1}^{10}sum(diag(y))\\ s.t.=\left\{\begin{matrix} \sum_{i=1}^{10}y_{i,j}\geq 1& \\ \sum_{j=1}^{10}y_{i,j}\leq 5& \\ d_{i,j}y_{i,j}\leq 10\\ y_{i,i}\geq y_{i,j}\\y_{i,j}=0/1 \end{matrix}\right.

clc,clear,close all
c=load("data1.txt");
d=dist(c);
disp(d);
prob=optimproblem();
y=optimvar("y",10,10,"Type","integer","LowerBound",0,"UpperBound",1);

prob.Objective=sum(diag(y));
prob.Constraints.con1=sum(y,1)>=1;
prob.Constraints.con2=sum(y,2)<=5;

con3=[];con4=[];con5=[];
for i=1:10
    
    for j=1:10
        con3=[con3;d(i,j)*y(i,j)<=10];
        con4=[con4;y(i,i)>=y(i,j)];
    end
end
prob.Constraints.con3=con3;
prob.Constraints.con4=con4;

[s,v]=solve(prob);
disp(s.y);
disp(v);

?可满足的方案有多种，但最小网点数为2

????????

文章来源:https://blog.csdn.net/Xing_ke/article/details/135652413
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章