实验10 整数规划.doc

实验10_整数规划实验10整数规划
化学工程系化32
坂井优（日本留学生） 2013080091
【实验目的】
1、练习建立实际问题的整数规划模型。
2、掌握用LINGO软件求解整数规划问题。
【实验内容】
-6：
某公司指派n个员工到n个城市工作（每个城市单独一人），希望使所花费的总电话费尽可能少。n个员工两两之间每个月通话的时间表示在下面的矩阵的上三角部分（因为通话的时间矩阵是对称的，没有必要写出下三角部分），n个城市两两之间通话费率表示在下面矩阵的下三角部分（同样道理，因为通话的费率矩阵是对称的，没有必要写出上三角部分）。试求解该二次指派问题（如果你的软件解不了这么大规模的问题，那就只考虑最前面的若干员工和城市）。
【模型建立】
设通话的时间矩阵为Q，第i行第j列元素为，i，j=1,2,3，...，10，表示i、j两员工的通话时间；通话的费率矩阵为R，第i行第j列元素为，i，j=1,2,3，...，10，表示i、j两地间的通话费率。
不妨设第i个员工在第个城市工作，令10阶方阵X中的元素满足：
，i，j=1,2，…,10
则显然该方阵的元素之间之间满足：
下面计算员工花费的电话费用的总和。假如第i个员工在第k个城市工作，且第j个员工在第l个城市工作，则总费用应包含这一项；假如第i个员工不在第k个城市工作，或第j个员工不在第l个城市工作，则总费用中应不包含这一项。
由上文可知，当第i个员工在第k个城市工作，且第j个员工在第l个城市工作时，有，即。当第i个员工不在第k个城市工作，或第j个员工不在第l个城市工作时，或，即。以上的分析中i，j，k，l=1,2，...，10。
因此，员工所花费的总电话费用为：
本题只需求其最小值。
以上即为本题的数学模型。
【程序设计与结果分析】
用LINGO编写程序如下：
MODEL:
SETS:
row/1..10/:;
matrix(row,row):Q,R,X;
ENDSETS
DATA:
Q=0 5 3 7 9 3 9 2 9 0
5 0 7 8 3 2 3 3 5 7
3 7 0 9 3 5 3 3 9 3
7 8 9 0 8 4 1 8 0 4
9 3 3 8 0 8 8 7 5 9
3 2 5 4 8 0 4 8 0 3
9 3 3 1 8 4 0 7 9 5
2 3 3 8 7 8 7 0 5 5
9 5 9 0 5 0 9 5 0 5
0 7 3 4 9 3 5 5 5 0;
R=0 7 4 6 8 8 8 6 6 5
7 0 8 2 6 5 6 8 3 6
4 8 0 10 4 4 7 2 6 7
6 2 10 0 6 6 9 3 2 6
8 6 4 6 0 6 4 8 8 6
8 5 4 6 6 0 3 8 3 2
8 6 7 9 4 3 0 6 7 8
6 8 2 3 8 8 6 0 8 8
6 3 6 2 8 3 7 8 0 9
5 6 7 6 6 2 8 8 9 0;
ENDDATA
***@FOR(row(i):***@SUM(row(j):X(i,j))=1);
***@FOR(r