Lingo学习笔记——平均分配问题（MINLP混合整数非线性规划）

Lingo学习笔记1、情景引入班级采购了一批零食作为举行班级活动时的零嘴，采购列表如下：商品编号份数单价商品1391.79商品2301.3商品3500.95商品4720.94商品5600.84商品6350.71商品7780.69商品8300.45商品9300.45商品10400.078班级总人数为32，要公平地将零食分给每个人。2、情景分析要想实现公平，就必须做到以下几点：

键盘里的咬肌

4874人浏览 · 2021-05-23 12:43:05

键盘里的咬肌 · 2021-05-23 12:43:05 发布

Lingo学习笔记

1、情景引入

班级采购了一批零食作为举行班级活动时的零嘴，采购列表如下：

商品编号	份数	单价
商品1	39	1.79
商品2	30	1.3
商品3	50	0.95
商品4	72	0.94
商品5	60	0.84
商品6	35	0.71
商品7	78	0.69
商品8	30	0.45
商品9	30	0.45
商品10	40	0.078

班级总人数为32，要公平地将零食分给每个人。

2、情景分析

要想实现公平，就必须做到以下几点：

每个人所分得的商品总价的方差尽量的小；
商品总价值尽量的大；
商品总数小于等于32的，分配时每个人所得该商品的个数不得大于1；
商品总数在33~64之间的，分配时每个人所得该商品的个数不得大于2个；
商品总数大于64的，分配时每个人所得该商品的个数不得大于3个；
商品总数大于等于32的，分配时每个人所得该商品的个数不得少于1个；
分得的商品个数均为整数。

3、模型建立

设商品编号为 i = 1，2，……，m（m=10），学生编号为 j = 1，2，……，n（n=32）。

$x_{ij}$ ： $j$ 学生分得 $i$ 商品的数量；

$p_j$ ： $j$ 学生分得商品的总价；

$P_i$ ： $i$ 商品的单价；

$N_i$ ： $i$ 商品的总份数；

$a v g p$ ： { $p_j$ } 平均值；

$s p$ ： { $p_j$ } 方差。

目标函数：

$min\quad sp = \frac{1}{n} * ∑_{j=1}^{n}(p_j - avgp )^2$
约束条件：

$s.t\begin{cases} p_j=\sum_{i=1}^{n}x_{ij}*P_i \\\\ avgp = \frac{1}{n} * \sum_{j=1}^{n} p_j \\ \\ \sum_{j=1}^{n} x_{ij} \leq N_i \quad , \quad i=1,2,...,m \\ \\ x_{ij} \geq 0 \end{cases}$

但是在实际运行过程中，发现运行时长过长，久久不能出结果，于是换了目标函数，转而求
$\quad max\quad z=\sum_{j=1}^{n}p_j$
然后对方差进行约束，根据一次次的运行结果依次取了0.4、0.3、0.2、0.15、0.13，当方差约束为小于0.13时，又出现了久久不能出结果的情况，于是最终只取到了小于0.15，结果得到方差为0.134。

4、代码实现

model:
!平均分配;
sets:
	goods/1..10/:num,price;
	stu/1..32/:;
	link(goods,stu):x;
endsets
data:
	num = 39,30,50,72,60,35,78,30,30,40;
	price = 1.79,1.30,0.95,0.94,0.84,0.71,0.69,0.45,0.45,0.078;
enddata

max = @sum(link(i,j):price(i)*x(i,j));

totalprice = @sum(goods(i):price(i)*num(i));
totalnum = @sum(link:x);
avgprice = 1/32*@sum(link(i,j):price(i)*x(i,j));

!方差约束;
variance = @sum(stu(j):(@sum(goods(i):x(i,j)*price(i))-avgprice)^2)/32;
variance < 0.15;

!每种商品分配的总和不得大于该商品的总数量;
@for(goods(i):@sum(stu(j):x(i,j))<=num(i));
!每个学生分得的商品总数不得少于13，即以平均数14.5为参考;
@for(stu(j):@sum(goods(i):x(i,j))>=13);
!商品总数大于32的商品分配时分给每个学生的商品数量不得小于1;
@for(link(i,j):x(i,j) >= @if(num(i)#ge#32,1,0));
!商品总数小于32的商品分配时分给每个学生的商品数量不得大于1，总数大于64的不得大于3，总数在32-64之间的不得大于2;
@for(link(i,j):x(i,j) <= @if(num(i)#le#32,1,@if(num(i)#ge#64,3,2)));
!分得每种商品的数量不得超过三个;
@for(link(i,j):x(i,j)<=3);
!分得的商品数量只能是整数;
@for(link:@gin(x));

end

5、运行结果

运行结果截图

Local optimal solution found.
Objective value: 383.1800
Objective bound: 383.1800
Infeasibilities: 0.000000
Extended solver steps: 11928
Total solver iterations: 3013236

Model Class: MINLP

Total variables: 323
Nonlinear variables: 321
Integer variables: 320

Total constraints: 1007
Nonlinear constraints: 1

Total nonzeros: 2885
Nonlinear nonzeros: 321

Model Title: Distribution
Variable Value
TOTALPRICE 383.1800
TOTALNUM 464.0000
AVGPRICE 11.97438
VARIANCE 0.1342741

……（太长了）

6、总结

在建模过程中，由于对于Lingo语法的不熟悉，导致花费的时间很长，在此记录一下本次学到的Lingo基本知识。

（1）基本框架

model:（这是一个模型）

sets:

……（建立集合）

集合名称/start…end/:属性1，属性2;

endsets

data:

……（上面的属性赋值）

enddata

initial:

……（据说是给结果进行一个初始化，缩短运行时间，我没有用这个）

endinitial

min = ……（或max）

……（约束条件）

end

非常简单的线性规划可以直接写目标函数和约束条件，不用分模块写，可以直接运行。

（2）几个函数

① @sum(集合名(下标):包含其属性的表达式)

将其整体看作是一个数，最终的结果是数！

冒号前面的部分是作为循环变量的，不能为未知数，比如：

!在上例中新增集合的属性，但不在data块中赋值;
stu/1..32/:stuprice;
!不能作为循环变量;
@for(stu(j):stuprice(j)=@sum(goods(i):x(i,j)*price(i)));
!原报错语句不记得是不是这样写了，当时希望实现这个功能的时候确实是报错了的;
!报错explain的翻译说是循环变量不能为未知数（原话不记得了）;