模型求解

在MicroCity中可以对数学模型进行求解。接下来，本文将介绍在MicroCity中求解数学模型的常见过程，并提供一些技巧帮助你更好地建模。

规划模型中所有函数的详细用法可以参考文档 4.8混合整数线性规划

提示

本页内容基于 MicroCity 桌面版。如果你在寻找 MicroCity Web 版的混合整数规划求解方法，请参考 MicroCity Web 笔记中对应的混合整数规划部分。

创建模型对象

创建规划模型对象，存入变量lp中。

local lp = CreateLP()

官方文档中将创建的数学模型对象存入变量LPModel中，作用同本文的lp

写入数学模型

此时，数学模型的对象已经创建并存入了变量lp中，可以对其进行更进一步的操作。数学模型一般分为两个部分：

目标函数
约束方程

接下来，先介绍创建目标函数的具体做法。

创建目标函数

MicroCity中，使用SetObjectFunction()设置模型对象的目标函数。允许选择目标函数求最大值或最小值。具体用法如下：

最大值

SetObjFunction(lp, coeff, "max") --求最大值

最小值

SetObjFunction(lp, coeff, "min") --求最小值

"min"和"max"不区分大小写，写"MIN"和"MAX"也可以

参数说明及示例

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

coeff是目标函数的系数列表，是一个table类型的变量。假设你要求函数 $4x_1+12x_2+18x_3$ 的最小值，则添加目标函数的做法如下：

-- 假设你已经创建了模型对象，并存入变量lp中

-- 4*x1 + 12*x2 + 18*x3
local coeff = {4, 12, 18}

-- 设置目标函数：求最小
SetObjFunction(lp, coeff, "min")

添加约束方程

在MicroCity中，添加模型约束的函数为AddConstraint()，用法如下：

≤

-- 使用符号表达
AddConstraint(lp, cons, "<=", b)

-- 或者可以使用缩写表达
AddConstraint(lp, cons, "le", b)

≥

-- 使用符号表达
AddConstraint(lp, cons, ">=", b)

-- 或者可以使用缩写表达
AddConstraint(lp, cons, "ge", b)

-- 使用符号表达
AddConstraint(lp, cons, "==", b)

-- 或者可以使用缩写表达
AddConstraint(lp, cons, "eq", b)

参数说明

参数	作用
`lp`	数学模型对象。将数学模型输入函数中，为模型添加约束
`cons`	约束方程系数。和设置目标函数中的`cons`一样，也是一个`table`类型的变量。用于确定约束方程中各个变量的系数。
`"<="` 或 `">="` 或 `"=="`，或其对应的字母表达	确定约束方程与右端项的关系
`b`	一个数字，表示约束方程的右端项。可以是变量也可以是常量

示例

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

\left\{\begin{matrix} x_1+3x_3\ge3 \\ 2x_2+2x_3\ge5 \end{matrix}\right.

添加对应约束方程：

-- 添加约束：x1+3*x3≥3
cons = { 1, 0, 3 }
AddConstraint(lp, cons, ">=", 3)

-- 添加约束：2*x2+2*x3≥5
cons = { 0, 2, 2 }
AddConstraint(lp, cons, ">=", 5)

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

设置变量类型

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

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

整数变量

SetInteger(lp, i) --整数变量

0-1变量

SetBinary(lp, i) --0-1变量

让第i个变量的值可以是负数（默认取不到负数）：

SetUnbounded(lp, i)

模型求解和输出

模型求解

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

SolveLP(lp)

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

输出

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

获取目标函数值：

GetObjective(lp)

获取第i个变量的值：

GetVariable(lp, i)

SolveLP

SolveLP()函数在求解完毕后也有输出，输出代码的含义如下：

输出代码	含义
0	成功
-1	无效的LP模型
-2	无内存
1	次优
2	无可行解
3	无界解
4	退化
5	遇到数值错误
6	用户终止了求解
7	超时错误

其他返回值表示的含义请参阅文档 4.8混合整数线性规划中的SolveLP()函数。

模型求解示例

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

算例：

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 lp = CreateLP()

local n = 3 --设置目标函数个数

-- 目标函数：4*x1 + 12*x2 + 18*x3
-- 设置目标函数系数，目标函数求最小
local coeff = { 4, 12, 18 }
SetObjFunction(lp, coeff, "min")

-- 添加约束1：x1 + 3*x3 ≥ 3
cons = { 1, 0, 3 }
AddConstraint(lp, cons, ">=", 3)

-- 添加约束2：2*x2 + 2*x3 ≥ 5
cons = { 0, 2, 2 }
AddConstraint(lp, cons, ">=", 5)

-- 由于没有设置SetUnbounded()，
-- 默认所有变量取值非负，
-- 因此不用针对变量非负添加约束。

-- 设置所有变量为整数
for i = 1, n do
    SetInteger(lp, i)
end

-- 求解模型
SolveLP(lp)

-- 输出目标函数值
print("目标函数值：",GetObjective(lp))

-- 输出各个变量的值
for i = 1, n do
    print("x",i,"=",GetVariable(lp, i))
end

输出结果

目标函数值：42
x1=0
x2=2
x3=1

建模的一些技巧

线性化

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

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

列1	列2	列3	列4
$x_{11}$	$x_{12}$	$x_{13}$	$x_{14}$
$x_{21}$	$x_{22}$	$x_{23}$	$x_{24}$
$x_{31}$	$x_{32}$	$x_{33}$	$x_{34}$

假设目标函数要将这些决策变量求和，即 $F=\sum_{i=1}^3\sum_{j=1}^4x_{ij}$ 如果要将其输入目标函数，此时可以将其线性化为 $x_{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四种货物，所需时间如表所示。若一种货物只交一人送货，则应指派何人配送何种货物，能使总的时间最少？

人\工件	A	B	C	D
甲	14	9	4	15
乙	11	7	9	10
丙	13	2	10	5
丁	17	9	15	13

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

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

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 lp = CreateLP()

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

SetObjFunction(lp, 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
    AddConstraint(lp, 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
    AddConstraint(lp, cons, "==", 1)
end

-- 求解模型
SolveLP(lp)

-- 输出目标函数值
print("目标函数值：",GetObjective(lp))

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

输出

目标函数值：29
x[1][3]=1
x[2][1]=1
x[3][4]=1
x[4][2]=1

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

中间变量的处理

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

假设 $x_1,x_2,x_3,x_4$ 为决策变量， $y_1,y_2$ 为中间变量。目标函数为:

z=\sum_{i=1}^4x_i

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

local fcons = {1, 1, 1, 1, 0, 0}

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