4.5 混合整数规划
线性规划和混合整数规划是运筹学中重要的工具，在这里提供了解决这些模型的函数和一些示例。请注意，调用 mip:func(args) 是对 math.func(mip, args) 的语法糖。
函数
为了方便后面的解释，请先看一个典型的 线性规划(LP) 模型:
min d1*x1 + d2*x2 + ... + dn*xn
subject to a11*x1 + a12*x2 + ... + a1n*xn >= b1
a21*x1 + a22*x2 + ... + a2n*xn >= b2
........................
am1*x1 + am2*x2 + ... + amn*xn >= bn
这个模型有 n 个列的变量和 m + 1 个行的下界约束（目标函数也是一种特殊的不等式）。还有 m 个对偶变量。混合整数规划(MIP) 问题是一个线性规划问题，其中一些变量需要额外要求为整数。为了简洁地构建 mip 模型并解决它们，我们设计了以下六个函数。请注意，调用 mip:func(args) 是对 math.func(mip, args) 的语法糖。
创建一个新的 mip 模型或从文件 fin 中读取以 CPLEX LP 格式表示的模型并返回。默认情况下，每个列变量都大于或等于 0。
mip:addrow (coltab|colname, bndtype [, b [, rowname]])
添加一行到模型 mip。
- 表 coltab 包含列变量所需的系数(可以是稀疏的)，例如 '{1, 3, [5]=7}' 或 '{x1=1, x2=3, x5=7}'。一个新的以数字索引命名的列变量将自动命名为"cn"，其中 n 是当前最大列数加1。
- colname 是一个带系数为1的单个列变量名称。
- 如果 bndtype 是 "min", "max", "<=", "<", ">=", ">", "=", "==", "unb", "bin", "int" 中的一个，则 bndtype 代表不同的边界类型。
- 当 bndtype 是 "<=", "<", ">=", ">", "=", "==" 时，b（不等式的右值）和 rowname 适用。
- 默认情况下，rowname（行或对偶变量名称）是 "rm"，其中 m 是当前最大行数加1.
从 mip 模型中删除一行。
mip:addcol (rowtab, bndtype, d [, colname])
在模型 mip 中添加一列。
- 表 rowtab 包含行变量需要的系数（可以是稀疏的），例如'{2, 4，[6]=8}'或'{u1=2, u2=4, u6=8}'。一个新的数字索引的行变量会被自动命名为"rm"，其中 m 是当前行数的最大值加 1。
- bndtype 是 "~"、"<="、"<"、">="、">"、"="、"==" 之一，代表不同的对偶问题边界类型。请注意，当对偶问题的不等式作为列添加到原问题中时，系数的符号需要重新判断。例如，如果带有对偶约束">"符号的不等式被添加到最小化原问题的列中，系数的符号需要翻转。一个使用 bndtype "~" 的列可以直接添加到原模型中。
- d 是对偶不等式的右值。
- 默认情况下，colname 为"cn"，其中 n 是当前列数的最大值加 1。
从 mip 模型中删除一列。
解决 mip 模型（将模型以 CPLEX LP 格式保存到文件 fout）。
- 对于线性规划，返回以下之一："optimal"、"feasible"、"infeasible"、"nofeasible"、"unbounded"、"undefined"。将目标、列（原）变量和行（对偶）变量的值分别写入 mip 模型的 'obj'、'colname' 和 'rowname' 属性。
- 对于混合整数规划，返回以下之一："optimal"、"feasible"、"nofeasible"、"undefined"。将目标、列变量的值分别写入 mip 模型的 'obj'、'colname' 属性。
示例模型
这里展示两个简单的模型，首先是一个包含两个变量和两个约束的混合整数规划模型：
max 143x1 + 60x2
subject to 110x1 + 30x2 <= 4000
x1 + x2 <= 75
x1 ∈ {0, 1, 2, ...}
x2 ∈ {0, 1}
将数学模型翻译成代码：
local mip = math.newmip() --创建一个整数规划
mip:addrow({x1 = 143, x2 = 60}, 'max') --设置目标函数
mip:addrow({x1 = 110, x2 = 30}, '<=', 4000) --添加第一个约束
mip:addrow({x1 = 1, x2 = 1}, '<=', 75) --添加第二个约束
mip:addrow('x1', 'int') --设置x1为整数边界
mip:addrow('x2', 'bin') --设置x2为二进制边界
mip:solve() --解决模型
print(mip.obj, ' ', mip.x1, ' ', mip.x2) --打印目标函数和变量的值
让我们展示一个略微复杂一点的例子，这是一个线性规划，其中目标函数和约束条件使用缩写表示：
在这个模型中有100个变量和100个约束条件，无法手动逐个添加。它们需要通过循环进行处理：
local lp = math.newmip() --创建一个线性规划
local c = {} --创建一个系数数组
for i = 1, 100 do --遍历数组
c[i] = i --设置系数
end
lp:addrow(c, "min") --设置目标函数
for i = 1, 100 do --遍历100个约束条件
local w = {} --创建约束系数数组
for j = 1, 100 do --遍历100个约束系数
if i==j then --如果行号等于列号
w[j] = 1 --将系数设为1
else
w[j] = 0 --否则将系数设为0
end
end
lp:addrow(w, ">=", 2) --向模型添加约束
end
lp:solve() --解决模型
print(lp['obj']) --打印目标值
本文使用ChatGPT翻译，如有遗漏请反馈。