混合整数规划

本文档介绍MicroCity Web中混合整数规划的建模方法。

创建混合整数规划模型

创建整数规划模型对象

local mip = math.newmip() -- 将创建的模型对象赋值给 mip

设置目标函数

MicroCity Web中，模型的第一行是目标函数，使用mip:addrow()函数添加。

允许选择目标函数求最大值或最小值。具体用法如下：

最大值
mip:addrow(coeff, 'max') --求最大值

参数说明及示例

参数作用
mip数学模型对象。将数学模型输入函数中，为模型设置目标函数
coeff目标函数系数，是一个table类型的变量。用于确定模型中目标函数的系数。
"min"或"max"确定目标函数求最大还是求最小。

coeff是目标函数的系数列表，是一个table类型的变量。假设你要求函数

4x1+12x2+18x3 4x_1+12x_2+18x_3

的最小值，则添加目标函数的做法如下：

-- 假设你已经创建了模型对象，并存入变量mip中
-- 设定目标函数为 4*x1 + 12*x2 + 18*x3，求最小
mip:addrow({4, 12, 18}, "min")

添加约束

添加约束方程

在MicroCity Web中，使用mip:addrow()添加剩下的约束方程，用法如下：

≤
mip:addrow(cons, "<=", b)

参数说明

参数作用
mip一开始创建的整数规划模型对象
cons约束方程系数。和设置目标函数中的cons一样，也是一个table类型的变量。用于确定约束方程中各个变量的系数。
"<=" 或 ">=" 或 "=="确定约束方程与右端项的关系
b约束方程的右端项。

示例

上面已经设置了目标函数为4x1+12x2+18x34x_1+12x_2+18x_3，假设你要为这个函数添加两个约束方程：

{x1+3x3≥32x2+2x3≥5 \left\{\begin{matrix} x_1+3x_3\ge3 \\ 2x_2+2x_3\ge5 \end{matrix}\right.

添加对应约束方程：

-- 添加约束：x1+3*x3≥3
mip:addrow({ 1, 0, 3 }, ">=", 3)

-- 添加约束：2*x2+2*x3≥5
mip:addrow({ 0, 2, 2 }, ">=", 5)

不难注意到，系数的个数和目标函数中变量的个数一致。因此，在编程求解之前首先要搞清楚变量的总数，并安排好各个变量的位置。

设置变量类型

MicroCity Web 中的数学规划支持整数规划。默认变量的取值范围是非负实数(≥0)。下面介绍变量类型设置的详细做法。

你可以将模型中第i个变量设置为整数变量或0-1变量。如果不将变量设置为这些类型，则默认变量为非负实数。

整数变量
mip:addrow('c1', 'int') --将第1个变量（第一列，col 1）设置为整数变量(Integer)

模型求解和输出

模型求解

由于目标函数和约束方程都已经添加完毕，因此模型的求解就很简单了，只需要一步：

mip:solve()

执行完这条语句后，存放于变量mip内的数学模型就求解完毕了🎉

输出

求解完还需要输出，否则就不知道求解的结果如何。以下是常用的输出求解结果的函数。

获取目标函数值：

mip['obj']

获取第i个变量的值：

mip['c'..i]

这里提供一个简单的从建模至求解的示例供参考。（其实就是将前面的拼起来）

算例：

minf=4x1+12x2+18x3s.t.{x1+3x3≥32x2+2x3≥5x1,x2,x3∈N minf=4x_1+12x_2+18x_3\\ s.t.\left\{\begin{matrix} x_1+3x_3\ge3 \\ 2x_2+2x_3\ge5 \\ x_1,x_2,x_3\in N \end{matrix}\right.

N表示自然数（非负整数集合）

脚本

local mip = math.newmip()

-- 设置目标函数
mip:addrow({4, 12, 18}, "min")

-- 添加约束
mip:addrow({ 1, 0, 3 }, ">=", 3) -- x1+3*x3≥3
mip:addrow({ 0, 2, 2 }, ">=", 5) -- 2*x2+2*x3≥5

-- 设置所有变量为整数
for i = 1, 3 do
    mip:addrow('c'..i, 'int')
end

-- 求解模型
mip:solve()

-- 输出目标函数值
print("目标函数值:", mip['obj'])

-- 输出各个变量的值
for i = 1, 3 do
    print("x"..i.."=",mip['c'..i])
end

输出结果

目标函数值: 42.0
x1= 0.0
x2= 2.0
x3= 1.0

在线运行

在MicroCity Web中查看这个示例

建模的一些技巧

线性化

有时候我们会遇到多下标的建模问题，如决策变量为xijx_{ij}，这个时候就要将其进行线性化编码。

假设决策变量本身的形状共有3行4列，即：

列1列2列3列4
x11x_{11}x12x_{12}x13x_{13}x14x_{14}
x21x_{21}x22x_{22}x23x_{23}x24x_{24}
x31x_{31}x32x_{32}x33x_{33}x34x_{34}

假设目标函数要将这些决策变量求和，即 F=∑i=13∑j=14xijF=\sum_{i=1}^3\sum_{j=1}^4x_{ij} 如果要将其输入目标函数，此时可以将其线性化为 x11+x12+...+x14+x21+...+x24+x31+...+x34x_{11}+x_{12}+...+x_{14}+x_{21}+...+x_{24}+x_{31}+...+x_{34}

由于只有两个维度，因此可以使用两个for实现：

local cons = {}
for i = 1, 3 do -- 第一维
    for j = 1, 4 do -- 第二维
        cons[4 * (i - 1) + j] = 1 -- 填入系数
        -- 其中 4 * (i - 1) + j 的思想类似于进位
    end
end

--结果：
-- cons长度为12，值都为1

例题：指派模型

下面以一个实际的例题来看看多维线性化的具体使用方法及其方便之处。

甲、乙、丙、丁四人配送A，B，C，D四种货物，所需时间如表所示。若一种货物只交一人送货，则应指派何人配送何种货物，能使总的时间最少？

人\工件ABCD
甲149415
乙117910
丙132105
丁1791513

假设货物A、B、C、D对应的编号依次为1、2、3、4，设 xij=1x_{ij}=1 时表示第i个人送j货，xij=0x_{ij}=0 时表示第i个人不送j货。

则上述问题的数学模型可以表示为

minZ=∑i=14∑j=14cijxijs.t.{∑j=14xij=1,i=1,2,...,4∑i=14xij=1,j=1,2,...,4xij=0,1 minZ=\sum_{i=1}^4\sum_{j=1}^4c_{ij}x_{ij}\\ s.t.\left\{\begin{matrix} \sum_{j=1}^4x_{ij}=1, i=1,2,...,4 \\ \sum_{i=1}^4x_{ij}=1, j=1,2,...,4 \\ x_{ij}=0,1 \end{matrix}\right.

求解代码

-- 效率矩阵
local cost = {{14, 9, 4, 15}, {11, 7, 9, 10}, {13, 2, 10, 5}, {17, 9, 15, 13}}

local mip = math.newmip()

-- 创建目标函数
local coeff = {}
for i = 1, 4 do
    for j = 1, 4 do
        -- 此处可以轻松将二维数组转换为一维数组
        coeff[4 * (i - 1) + j] = cost[i][j]
    end
end

mip:addrow(coeff, "min")

-- 添加约束
for k = 1, 4 do -- 第i维的值控制
    local cons = {}
    for i = 1, 4 do
        for j = 1, 4 do
            if i == k then -- j求和，判断i
                cons[4 * (i - 1) + j] = 1
            else
                cons[4 * (i - 1) + j] = 0
            end
        end
    end
    mip:addrow(cons, "==", 1)
end

for k = 1, 4 do -- 第j维的值控制
    local cons = {}
    for i = 1, 4 do
        for j = 1, 4 do
            if j == k then -- i求和，判断j
                cons[4 * (i - 1) + j] = 1
            else
                cons[4 * (i - 1) + j] = 0
            end
        end
    end
    mip:addrow(cons, "==", 1)
end

-- 求解模型
mip:solve()

-- 输出目标函数值
print("目标函数值:", mip['obj'])

-- 输出决策变量
for i = 1, 4 do -- 第一维
    for j = 1, 4 do -- 第二维
        local x = mip['c' .. 4 * (i - 1) + j]
        if x ~= 0 then
            print("x[" .. i .. "][" .. j .. "]=", x)
        end
    end
end

输出

目标函数值: 29.0
x[1][3]= 1.0
x[2][1]= 1.0
x[3][4]= 1.0
x[4][2]= 1.0

在线运行

在MicroCity Web中查看这个示例

结果人配送工件
x13=1x_{13}=1甲C
x21=1x_{21}=1乙A
x34=1x_{34}=1丙D
x42=1x_{42}=1丁B

中间变量的处理

有时候模型中会存在一些中间变量，这些变量必须要在矩阵中有对应的位置才能对其进行求解，而这些中间变量不参与目标函数值的运算。可以将中间变量对应位置的系数设为0。

假设x1,x2,x3,x4x_1,x_2,x_3,x_4为决策变量，y1,y2y_1,y_2为中间变量。目标函数为:

z=∑i=14xi z=\sum_{i=1}^4x_i

则目标函数系数可以设为：

local fcons = {1, 1, 1, 1, 0, 0} -- 前面4位为决策变量，后面2位为中间变量

接下来按照一般流程做就可以啦😎

Last Updated:
Contributors: huuhghhgyg