问题
将如下一组数字从大到小排序。
{10, 20, -32, 177, 0, -11.5, 19, 7, 6.2, -6.28, -2.71, 44}
解决办法
建立数学模型，给出各个数字的次序值。
模型
设x[i]为第i个数的次序值。根据排序规则有如下约束：
x[i] <= x[j] -1 | i=1,...,n; j=1,...,n; i<>j; d[i] >d[j]
希望次序值从1开始，最大不超过数字的总数：
x[i] >= 1 | i=1,...,n
x[i] <= n | i=1,...,n
不需要目标：
max 0
最终模型为
max 0
subject to
x[i] <= x[j] -1 | i=1,...,n; j=1,...,n; i<>j; d[i] >d[j]
x[i] >= 1 | i=1,...,n
x[i] <= n | i=1,...,n
where
n is a number
d is a set
x[i] is a variable of nonnegative integer| i=1,...,n
data_relation
n=_$(d)
data
d={10, 20, -32, 177, 0, -11.5, 19, 7, 6.2, -6.28, -2.71, 44}
求解
+Leapms>load
Current directory is "ROOT".
.........
sort.leap
.........
please input the filename:sort
================================================================
1: max 0
2: subject to
3: x[i] <= x[j] -1 | i=1,...,n; j=1,...,n; i<>j; d[i] >d[j]
4: x[i] >= 1 | i=1,...,n
5: x[i] <= n | i=1,...,n
6: where
7: n is a number
8: d is a set
9: x[i] is a variable of nonnegative integer| i=1,...,n
10: data_relation
11: n=_$(d)
12: data
13: d={10, 20, -32, 177, 0, -11.5, 19, 7, 6.2, -6.28, -2.71, 44}
================================================================
>>end of the file.
Parsing model:
1D
2R
3V
4O
5C
6S
7End.
..................................
number of variables=12
number of constraints=90
..................................
+Leapms>mip
relexed_solution=0; number_of_nodes_branched=0; memindex=(2,2)
The Problem is solved to optimal as an MIP.
找到整数规划的最优解.非零变量值和最优目标值如下：
.........
x1* =5
x2* =3
x3* =12
x4* =1
x5* =8
x6* =11
x7* =4
x8* =6
x9* =7
x10* =10
x11* =9
x12* =2
.........
Objective*=0
.........
+Leapms>
对上述结果进行解释，x1*=5即第一个数放在第5位， x2*=3即第2个数放在 第2位，或者说12数字的次序数分别为5，3，12，1，8，11，4，6，7，10，9，2。