【备战美赛】Lingo与规划问题

Lingo——解决规划问题yyds！

Fellyhosn

5386人浏览 · 2022-01-21 15:35:57

Fellyhosn · 2022-01-21 15:35:57 发布

引入

规划问题其实我们在高一数学必修五里面已经见过，当时的题目都是线性规划模型，做法也非常直观：通过画图和观察加上一点点计算得出最优解。当时我们处理的是只有x和y两个变量并且约束条件都是一次函数的情况。实际上，我们的最优解常常要考虑多个变量以及多个约束条件，这就是所谓的规划问题。

两年半前的暑假，我去中山大学参加人工智能夏令营。期间，组织者给了我们小组五个课题，我们需要选择其中一个课题作为结业展示。其中有一个课题便是数学规划模型问题（自来水运输问题），由于当时没有什么思路，我们小组选择了另外的课题。但是我始终对这个课题保留兴趣，一是因为当时读完问题觉得这应该就是一道不难的OI里面的问题；二是这个课题里只涉及到简单的数学知识并且数据量很小，完全应该做出来。在结营仪式的汇报上，有两个小组选择了这个规划问题作为课题。其中一个小组直接使用了最小费用最大流的网络流类算法，当时我对这个算法虽有所耳闻但是从没学会，看着代码也是一脸茫然。另外一个小组则是另辟蹊径，使用了Lingo代替C语言，代码简短。这个小组汇报时向我们介绍了Lingo在解决线性问题的便捷性。我虽然听不懂，但是我大受震撼！

后来由于高考，没有时间钻研这方面的问题，进入大学后也疲于专业课。这个寒假正巧准备美赛，在建模的规划问题上又再一次看到了“Lingo”这个词，当时的记忆被一下子唤醒。也许是知识增长的原因，在b站短暂学习了几个小时后，我也渐渐能够上手Lingo。再翻出当年的课题，从两年半前的茫然到现在的“有手就行”，实在是感慨万千！

规划问题

规划问题指针对一个目标再加上一定的约束条件找到目标的最优解。一般的规划问题包含线性规划、整数规划、非线性规划等。在高中我们遇到的就是线行规划，有一个目标函数和两到三个线性的约束条件。整数规划顾名思义，即决策变量必须是整数，而一般的规划问题的决策变量只限制在非负。非线性规划指的是约束条件非线性。对于不同的规划问题有不同的方法，但是放在专门解决规划问题的Lingo上，其实也就几行代码的事！

Lingo

全称：Linear Interactive and General Optimizer。其特色在于内置建模语言，提供十几个内部函数，可以允许决策变量是整数（即整数规划，包括 0-1 整数规划），方便灵活，而且执行速度非常快。能方便与EXCEL，数据库等其他软件交换数据。（摘自百科）

下载和安装也非常方便，页面简洁易懂。虽然相比主流的编程语言不够全面，但是在规划问题上是独树一帜的！所以很有必要学习！下面通过和实际例子相结合的方式来介绍Lingo的用法。

Lingo解决规划问题实例

1.简单的线性规划/非线行规划

这是高中数学的一道典型的线性规划的题目，之前是通过动手作图，再将目标函数代入图像找到最值点解决的。现在我们可以用Lingo“秒杀”！

首先，对于任何一个规划问题，我们都要找到其目标函数、决策变量和约束条件。这里，目标函数就是2x+y的最大值，在lingo里面，可以用 max=2*x+y; 来表示（若求最小值则将max改为min）。 决策变量即是两个未知的变量x和y，约束条件是题目中给出的三个条件。Lingo代码如下：

max=2*x+y; !目标函数;
y<1;
x+y>0;
x-y-2<0;  !三个约束条件,Lingo中不严格区分＜和≤
@free(x); !由于Lingo中所有变量默认是非负的,这里要去掉该限制;
@free(y);

由此可见，Lingo解决规划问题的代码一般分为三段：目标函数——决策变量初始化——约束条件。之后点击Lingo——solve即可运行。运行结果如下：

它不仅给出了最终的结果7，还给出了两个变量的取值3和1。

2.指派问题（多变量的线性规划）

这是当年中山大学夏令营给出的课题，是一个典型的指派问题（即分配任务使得利益或者效率最大化）。这道题里，目标函数是三个公司的获利之和，约束条件是三个水库的最大送水量和每个居民区的用水量最大值和最小值，决策变量是每个水库向每个地区送水量。显然，对于3个公司和4个居民区，一共得有12个决策变量，一个一个写显然是复杂的。因此需要用到循环和数组来减少处理难度。

不妨设 $s1(j),s2(j),k(i),g(i,j),a(i,j)$ 分别表示地区j的最小/最大送水量，公司i的最大送水量，公司i给地区j的送水量，公司i向地区j送水的管理费。那么 $s1(j),s2(j),k(i)$ 都是由题目已知的，未知的决策变量是 $g(i,j)$ ，目标函数是 $max=\displaystyle\sum_{i=1}^3 \displaystyle\sum_{j=1}^4(450-a_{i,j})g_{i,j}$ ,

约束条件为 $\begin{equation} \left\{ \begin{array}{lr} s1(i)\leq \displaystyle\sum_{i=1}^3g(i,j)\leq s2(i) & \\ \displaystyle\sum_{j=1}^4 g(i,j)\leq k(j) \end{array} \right. \end{equation}$ ，Lingo代码如下：

model:

sets:
supply/1..3/:k;   !3个输水公司  supply是类型名,k是变量名;
demand/1..4/:s1,s2;   !4个地区 同上,demand是类型名,s1和s2是变量名;
link(supply,demand):a,g;  !sets部分是对变量的初始化;
endsets

data:
a=160,130,220,170,140,130,190,150,190,200,230,450; !由于C到丁不连通,可设最终收益为0;
s1=30,70,10,10;
s2=80,140,30,50;
k=50,60,50;
enddata   !对一些已知的变量赋值;

max=@sum(link(i,j):(450-a(i,j))*g(i,j)); !目标函数,sum表示求和;

@for(supply(i):@sum(demand(j):g(i,j))<k(i));!三个for循环;
@for(demand(j):@sum(supply(i):g(i,j))<s2(j));
@for(demand(j):@sum(supply(i):g(i,j))>s1(j));

end

运行后得到的Objective Value为47600，输出还给出了最佳的运输方案：

第二问中若每个水库的供应量增大一倍，只需要把原代码里的k数组的值变化一下即可。至此，两年半前的遗留问题已被完全解决！

3.其他应用

对于一般地最小费用最大流问题，Lingo也能有效地解决，这里不再赘述。由于实际上有的问题的变量较多，不适合手动输入，Lingo也可以用ole函数从Excel里导入，非常方便。对于非线性规划问题，对于Lingo来说只是约束条件不再线性了而已，写代码的时候没有任何区别。对于整数规划，可以用qin函数将非负的变量变为非负整数变量，从而实现取整。所以总体而言，Lingo几乎可以解决一切规划问题！