【数学建模算法】（番外4）解决规划问题的神器——Lingo（下）

2019-08-06 本文已影响14人热爱学习的高老板

今天我们将用几个综合实例来实践Lingo。

例1 求解非线性方程组
$\left\{\begin{array}{l}{x^{2}+y^{2}=1} \\ {2 x^{2}+x+y^{2}+y=4}\end{array}\right.$

规划问题本来就是给出优化条件和限制条件，之后得出满足条件的自变量的过程。那么它自然可以解决非线性方程问题，那么只需给出一个可以增加运算速度定一个初始点，再给出限制条件，就可以解出来了。

model:
INIT:
x=1;y=1;
ENDINIT
x^2+y^2=2;
2*x^2+x+y^2+y=4;
end

输出结果

Variable           Value
X       0.4543344
Y        1.339246

Row    Slack or Surplus
1      -0.3647994E-06
2      -0.7985587E-06

例2 （装配线平衡模型）一条装配线含有一系列的工作站，在最终产品的加工过程中每个工作站执行一种或几种特定的任务。装配线周期是指所有工作站完成分配给它们各自的任务所花费时间中的最大值。平衡装配线的目标是为每个工作站分配加工任务，尽可能使每个工作站执行相同数量的任务，其最终标准是装配线周期最短。不适当
的平衡装配线将会产生瓶颈——有较少任务的工作站将被迫等待其前面分配了较多任务的工作站。
问题会因为众多任务间存在优先关系而变得更复杂，任务的分配必须服从这种优先关系。
这个模型的目标是最小化装配线周期。有 2 类约束：
① 要保证每件任务只能也必须分配至一个工作站来加工；
② 要保证满足任务间的所有优先关系。

任务	A	B	C	D	E
时间	45	11	9	50	15
F	G	H	I	J	K
12	12	12	12	8	9

下面是任务流程图。

任务流程图

编写Lingo程序：

MODEL:
!装配线平衡模型;
SETS:
!任务集合，有一个完成时间属性T;
TASK/ A B C D E F G H I J K/:T;
!人物之间的有限关系集合（A必须完成才能开始B，等等）;
PRED(TASK,TASK)/A,B B,C C,F C,G F,J G,J 
J,K D,E E,H E,I H,J I,J/;
!工作站集合;
STATION/1..4/;
TXS(TASK,STATION):X;
!X是派生集合TXS的一个属性，如果（X（I,K）=1），则表示第I个任务
交给第K个工作站完成。;
ENDSETS

DATA:
!任务A,B,C,D,E,F,G,H,I,J,K完成的时间如下;
T=45 11 9 50 15 12 12 12 12 8 9;
ENDDATA
!每一个作业只能指派给一个工作站;
@FOR(TASK(I):@SUM(STATION(K):X(I,K))=1);
!对于每一个存在优先关系的作业对来说，前者对应的工作站I必须小于后者对应的工作站J,保持先后分配关系;
@FOR(PRED(I,J):@SUM(STATION(K):X(I,K)-X(J,K))>=0);
!对于每一个工作站来说，其花费时间必须不大于装配线周期;
@FOR(STATION(K): @SUM(TXS(I,K):T(I)*X(I,K))<=CYCTIME);
!目标函数是最小化转配线周期;
MIN = CYCTIME;
!指定 X(I,J) 为 0/1 变量;

例3 旅行售货员问题（又称货郎担问题，Traveling Salesman Problem）
有一个推销员，从城市 1 出发，要遍访城市 2，3，…， n 各一次，最后返回城市 1。已知从城市 $i$ 到 $j$ 的旅费为 $c_{i j}$ ，问他应按怎样的次序访问这些城市，使得总旅费最少。

可以用多种方法把 TSP 表示成整数规划模型。这里介绍的一种建立模型的方法，是把该问题的每个解（不一定是最优的）看作是一次“巡回”。

引入0-1整数变量。
$x_{i j}=\left\{\begin{array}{l}{1} ，巡回路线是从i到j,且i \ne j\\ {0}，其他情况\end{array}\right.$
其目标是为了让 $\sum_{i=j} c_{i j} x_{i j}$ 最小
这里有两个明显的必须满足的条件：
1.访问城市 $i$ 后必须要有一个即将访问的确切城市；
2.访问城市 $j$ 前必须要有一个刚刚访问过的确切城市。
用下面的两组约束分别实现上面的两个条件。
$\begin{array}{l}{\sum_{j=1}^{n} x_{i j}=1, \quad i=1,2, \cdots, n} \\ {\sum_{i=1}^{n} x_{i j}=1, \quad j=1,2, \cdots, n}\end{array}$
到此我们得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于
TSP 来说并不充分，仅仅是必要条件。
例如对如下的情形，它显然不是TSP问题的解。

两个子巡回
于是我们可以在原模型上添加附加约束条件：

于是整个问题变成一个混合型整数线性规划问题。

代码实现

model:
sets:
city / 1.. 5/: u;
link( city, city):
dist, ! 距离矩阵;
x;
endsets
n=@size(city);
data: !距离矩阵，它并不需要是对称的;
dist=@qrand(1); !随机产生，这里可改为你要解决的问题的数据;
enddata
!目标函数;
min=@sum(link:dist*x);
@FOR(city(K):
!进入城市 K;
@sum(city(I)| I #ne# K: x(I,K))=1;
!离开城市 K;
@sum(city(J)| J #ne# K: x(K,J))=1);
!保证不出现子圈;
@for(city(I)|I #gt# 1:@for( city( J)| J#gt#1 #and# I #ne# J:
u(I)-u(J)+n*x(I,J)<=n-1));
!限制 u 的范围以加速模型的求解，保证所加限制并不排除掉 TSP 问题的最优解;
@for(city(I) | I #gt# 1: u(I)<=n-2);
!定义 X 为 0-1 变量;
@for( link: @bin(x));
end

例4 露天矿生产的车辆安排(CMCM2003B)(国赛2003年真题)

钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。
露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于 25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多能安置一台电铲，电铲的平均装车时间为5 分钟。

石料两种：矿石和岩石
装车时间：5分钟

卸货地点（以下简称卸点）有卸矿石的矿石漏、2 个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.5% ± 1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8 小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为3 分钟。

卸点5个：矿石漏、2 个铁路倒装场，岩石漏，岩场。
卸点需要的铁含量限制：29.5% ± 1%
问题分析范围：8小时
卸车时间：3分钟
装车+卸车：8分钟

所用卡车载重量为 154 吨，平均时速 28 km/h。卡车的耗油量很大，每个班次每台车消耗近 1 吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输。

卡车信息：载重量154吨。
时速：28km/h
卡车的工作需连续，不能等待。
满载运输。

每个铲位到每个卸点的道路都是专用的宽 60 m 的双向车道，不会出现堵车现象，每段道路的里程都是已知的。
一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考下面两条原则之一：

1.总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；
2.利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。
请你就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面的实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。

某露天矿有铲位 10 个，卸点 5 个，现有铲车 7 台，卡车 20 辆。各卸点一个班次的产量要求：矿石漏 1.2 万吨、倒装场Ⅰ1.3 万吨、倒装场Ⅱ1.3 万吨、岩石漏 1.9 万吨、岩场 1.3 万吨。

铲位总数：10个
卸点：5个
铲车（能使用的铲位数）：7台
卡车总数：20辆
各个卸点的产量要求：矿石漏 1.2 万吨、倒装场Ⅰ1.3 万吨、倒装场Ⅱ1.3 万吨、岩石漏 1.9 万吨、岩场 1.3 万吨。

铲位和卸点位置二维示意图见下图，各铲位和各卸点之间的距离（公里）见下表，各铲位矿石、岩石数量(万吨)和矿石的平均铁含量也见下表。

表1 铲位与卸点之间的距离表

	铲位1	铲位2	铲位3	铲位4	铲位5
矿石漏	5.26	5.19	4.21	4.00	2.95
倒装厂1	1.90	0.99	1.90	1.13	1.27
岩厂	5.89	5.61	5.61	4.56	3.51
岩石漏	0.64	1.76	1.27	1.83	2.74
倒装厂2	4.42	3.86	3.72	3.16	2.25
	铲位6	铲位7	铲位8	铲位9	铲位10
	2.74	2.46	1.90	0.64	1.27
	2.25	1.48	2.04	3.09	3.51
	3.65	2.46	2.46	1.06	0,57
	2.60	4.21	3.72	5.05	6.10
	2.81	0.78	1.62	1.27	0.50

表2 铲位矿石，岩石数量和矿石的平均铁含量表。

	铲位1	铲位2	铲位3	铲位4	铲位5
矿石量	0.95	1.05	1.00	1.05	1.10
岩石量	1.25	1.10	1.35	1.05	1.15
铁含量	30%	28%	29%	32%	31%
	铲位6	铲位7	铲位8	铲位9	铲位10
矿石量	1.25	1.05	1.30	1.35	1.25
岩石量	1.35	1.05	1.15	1.35	1.25
铁含量	33%	32%	31%	33%	31%

铲位与卸点位置示意图

本例就原则一举例，展现完整的建模和求解过程。
各种符号及单位说明如下：
$x_{i j}$ ：从 $i$ 号铲位到 $j$ 号卸点的石料运量，单位：车·次·（最终方案所求量之一，在相应车道上的总（车·次）数）
$c_{i j}$ ：从 $i$ 号铲位到 $j$ 号卸点的距离，单位：公里
$T_{i j}$ ：从 $i$ 号铲位到 $j$ 号卸点运行一个周期所需的时间，单位：分
$A_{i j}$ ：从 $i$ 号铲位到 $j$ 号卸点最多能同时运行的卡车数，单位：辆（最终方案所求量之一，在对应车道上安排的同时运行的车数）
$B_{i j}$ ：从 $i$ 号铲位到 $j$ 号卸点，一辆车一个班次中最多可以运行的次数，单位：次
$p_{i}$ ： $i$ 号铲位的矿石铁产量乘以100
$P:\left(p_{1}, \cdots, p_{10}\right)=(30,28,29,32,31,33,32,31,33,31)$
$Q=\left(q_{1}, \cdots, q_{5}\right)=(1.2,1.3,1.3,1.9,1.3) \times 10000 / 154$ ，单位：车·次；
$c k_{i}$ ： $i$ 号铲位的铁矿石储量，单位：万吨
$c y_{i}$ ： $i$ 号铲位的岩石储量，单位：万吨
$f_{i}$ ：描述第 $i$ 号铲位是否使用0-1变量，
$f_{i}$ = $\left\{\begin{array}{l}{1}，使用i号铲位 \\ {0}，不使用i号\end{array}\right.$

分析所有的目标函数和限制条件：
目标函数：

卡车运行总距离最少
$\min \sum_{i=1}^{10} \sum_{j=1}^{5} 154 c_{i j} \cdot x_{i j}$

限制条件：

1.电铲能力限制（装车时间5分，每个电铲最多能装60*8/5=96辆车）
$\sum_{j=1}^{5} x_{i j} \leq 96 f_{i}, \quad i=1, \cdots, 10$

2.卸车能力限制（卸车时间3分，每个卸点最多能卸60*8/3=160辆车）
$\sum_{i=1}^{10} x_{i j} \leq 160, \quad j=1, \cdots, 5$

3.各铲位矿石储量限制（从各个铲位运出的矿石不能大于储量）
$\begin{array}{l}{x_{i 1}+x_{i 2}+x_{i 5} \leq c k_{i} \times 10000 / 154} \\ {x_{i 3}+x_{i 4} \leq c y_{i} \times 10000 / 154}\end{array} \}, i=1, \cdots, 10$

4.需求量限制（各个卸点卸下的矿石要大于需求量）
$\sum_{i=1}^{10} x_{i j} \geq q_{j}, \quad j=1, \cdots, 5$

5.品位因数限制（矿石纯度要求29.5% ± 1%）
$\begin{array}{l}{\sum_{i=1}^{10} x_{i j} \times\left(p_{i}-30.5\right) \leq 0} \\ {\sum_{i=1}^{10} x_{i j}\left(p_{i}-28.5\right) \geq 0}\end{array} \}, \quad j=1,2,5$

6.卡车总数限制（20）
$\sum_{i=1}^{10} \sum_{j=1}^{j} \frac{x_{i j}}{B_{i j}} \leq 20$

7.电铲启用数限制（7）
$\sum_{i=1}^{10} f_{i} \leq 7$

于是可以建立如下模型：
$\min \sum_{i=1}^{10} \sum_{j=1}^{5} 154 c_{i j} \cdot x_{i j}$
$\sum_{j=1}^{5} x_{i j} \leq 96 f_{i}, \quad i=1, \cdots, 10$
$\sum_{i=1}^{10} x_{i j} \leq 160, \quad j=1, \cdots, 5$
$\begin{array}{l}{x_{i 1}+x_{i 2}+x_{i 5} \leq c k_{i} \times 10000 / 154} \\ {x_{i 3}+x_{i 4} \leq c y_{i} \times 10000 / 154}\end{array} \}, i=1, \cdots, 10$
$\sum_{i=1}^{10} x_{i j} \geq q_{j}, \quad j=1, \cdots, 5$
$\begin{array}{l}{\sum_{i=1}^{10} x_{i j} \times\left(p_{i}-30.5\right) \leq 0} \\ {\sum_{i=1}^{10} x_{i j}\left(p_{i}-28.5\right) \geq 0}\end{array} \}, \quad j=1,2,5$
$\sum_{i=1}^{10} \sum_{j=1}^{j} \frac{x_{i j}}{B_{i j}} \leq 20$
$\sum_{i=1}^{10} f_{i} \leq 7$
$x_{i j}为整数，i=1, \cdots, 10, \quad j=1, \cdots, 5$
$f_{i}为0-1变量，i=1,...,10$

程序如下：

model:
title CUMCM-2003B;
sets:
cai / 1..10 /:p,cy,ck,f;
xie / 1 .. 5 /:q;
link(cai,xie):a,b,c,t,x;
endsets
data:
v=28;
p=30 28 29 32 31 33 32 31 33 31;
q= 1.2 1.3 1.3 1.9 1.3 ;
c=5.2600 1.9000 5.8900 0.6400 4.4200
5.1900 0.9900 5.6100 1.7600 3.8600
4.2100 1.9000 5.6100 1.2700 3.7200
4.0000 1.1300 4.5600 1.8300 3.1600
2.9500 1.2700 3.5100 2.7400 2.2500
2.7400 2.2500 3.6500 2.6000 2.8100
2.4600 1.4800 2.4600 4.2100 0.7800
1.9000 2.0400 2.4600 3.7200 1.6200
0.6400 3.0900 1.0600 5.0500 1.2700
1.2700 3.5100 0.5700 6.1000 0.5000;
cy = 1.25 1.10 1.35 1.05 1.15 1.35 1.05 1.15 1.35 1.25;
ck = 0.95 1.05 1.00 1.05 1.10 1.25 1.05 1.30 1.35 1.25;
enddata
!下面一行是代表卡车数量约束，先计算除每条线路的运行周期（单位：分钟）
a是运行在当条道路上的总卡车限制数。
b是1辆车1个班次中最多可以运行的次数。
@for(link:t=120*c/v+8;a=@floor(t/5);b=@floor((485-5*a)/t));
min=@sum( link:x*154*c); !目标函数;
@for (link: x<=a*b); !道路能力约束;
@for (cai(i): @sum(xie(j):x(i,j))<=f(i)*96); !电铲能力约束;
@for (xie(j):@sum(cai(i):x(i,j))<=160); !卸点能力约束;
!以下是铲位储量约束;
@for (cai(i): x(i,1)+x(i,2)+x(i,5)<=ck(i)*10000/154);
@for (cai(i): x(i,3)+x(i,4)<=cy(i)*10000/154);
!产量任务约束;
@for (xie(j) : @sum(cai(i):x(i,j)) >= q(j)*10000/154);
@sum(cai(i): x(i,1)*(p(i)-30.5) )<=0; !铁含量约束;
@sum(cai(i): x(i,2)*(p(i)-30.5) )<=0;
@sum(cai(i): x(i,5)*(p(i)-30.5) )<=0;
@sum(cai(i): x(i,1)*(p(i)-28.5) )>=0;
@sum(cai(i): x(i,2)*(p(i)-28.5) )>=0;
@sum(cai(i): x(i,5)*(p(i)-28.5) )>=0;
@sum(link:x/b)<=20; !车辆能力约束;
@sum(cai: f)<=7; !电铲数量约束;
@for(link : @gin(x)); !整数约束;
@for(cai: @bin(f)); !0－1变量约束;
end

【数学建模算法】（番外4）解决规划问题的神器——Lingo（下）

猜你喜欢

热点阅读