本文介绍了线性整数规划问题的概念和如何使用 MATLAB 解决该问题。通过一个具体的例子，详细讲解了将目标函数和约束条件转化为标准形式的方法，并给出了求解的代码。最终结果表明，该方法可以成功求解线性整数规划问题。
介绍自己 🙈
生成本文简介 👋
推荐相关文章 📖
前往主页 🏠
前往爱发电购买
这篇文章距离上次更新已经过去了 620 天，其中的某些内容可能不再适用了，请谨慎阅读。
什么是线性整数规划问题
整数规划问题是指在一组线性不等式约束条件下，求解一个线性目标函数的最大值或最小值的问题，且目标函数和约束条件中的变量含有整数。
如何使用 MATLAB 解决线性整数规划问题
常见的线性整数规划问题通常类似于以下形式：
minZ=8x1+x2 s.t. ⎩⎨⎧x2 is an integerx1+2x2≥−14−4x1−x2≤−332x1+x2≤20 其中，公式1为目标函数，公式2为约束条件。
为了便于求解，我们可以将公式1和公式2分别写成矩阵形式：
minZ=[81]⋅[x1x2] s.t. ⎩⎨⎧x2 is an integer−1−42−2−11⋅[x1x2]≤14−3320 这种形式便是 MATLAB 的线性整数规划的标准形式：
xminfTx subject to ⎩⎨⎧x(intcon) are integersA⋅x≤bAeq⋅x=beqlb≤x≤ub. 可以调用 intlinprog 函数来求解，其语法为：
1
| [x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
|
其中，f 为目标函数，intcon 为整数变量的下标，A 为约束条件的系数矩阵，b 为约束条件的右端项，Aeq 为等式约束条件的系数矩阵，beq 为等式约束条件的右端项，lb 为变量的下界，ub 为变量的上界。
本题便可使用如下代码求解：
1
2
3
4
5
6
| f = [8 1];
intcon = 2;
A = [-1 -2; -4 -1; 2 1];
b = [14; -33; 20];
[x,fval] = intlinprog(f,intcon,A,b);
|
结果为：
1
2
3
4
5
6
| x =
6.5000
7.0000
fval =
59.0000
|
附加题
让我们运用上文的方法求解以下问题：
minZ=2x1+3x2+4x3 s.t. ⎩⎨⎧x2 is an integerx3 is an integerx1+2x2+3x3≥1−x1−x2−x3≤−12x1+x2+x3≤2 首先转化为标准形式：
minZ=[234]⋅x1x2x3 s.t. ⎩⎨⎧x2 is an integerx3 is an integer−1−12−2−11−3−11⋅x1x2x3≤−1−12 然后使用 intlinprog 函数求解：
1
2
3
4
5
6
| f = [2 3 4];
intcon = [2 3];
A = [-1 -2 -3; -1 -1 -1; 2 1 1];
b = [-1; -1; 2];
[x,fval] = intlinprog(f,intcon,A,b);
|
最终结果：
1
2
3
4
5
6
7
| x =
1.0000
0
0
fval =
2.0000
|
