实验_整数规划.docx

实验 10 整数规划化学工程系化 32 坂井优(日本留学生) 2013080091 【实验目的】 1、练习建立实际问题的整数规划模型。 2、掌握用 LINGO 软件求解整数规划问题。【实验内容】 1. 题目 10-6 : 某公司指派 n 个员工到 n 个城市工作(每个城市单独一人) ,希望使所花费的总电话费尽可能少。n个员工两两之间每个月通话的时间表示在下面的矩阵的上三角部分(因为通话的时间矩阵是对称的,没有必要写出下三角部分),n 个城市两两之间通话费率表示在下面矩阵的下三角部分(同样道理,因为通话的费率矩阵是对称的,没有必要写出上三角部分) 。试求解该二次指派问题(如果你的软件解不了这么大规模的问题,那就只考虑最前面的若干员工和城市)。 0 5 3 7 9 3 9 2 9 0 7 0 7 8 3 2 3 3 5 7 4 8 0 9 3 5 3 3 9 3 6 2 10 0 8 4 1 8 0 4 8 6 4 6 0 8 8 7 5 9 8 5 4 6 6 0 4 8 0 3 8 6 7 9 4 3 0 7 9 5 6 8 2 3 8 8 6 0 5 5 6 3 6 2 8 3 7 8 0 5 5 6 7 6 6 2 8 8 9 0 ? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?【模型建立】设通话的时间矩阵为Q,第i行第 j列元素为 ijq ,i,j =1,2,3 , ..., 10,表示 i、 j两员工的通话时间;通话的费率矩阵为 R,第i行第 j列元素为 ijr ,i,j =1,2,3 , ..., 10,表示 i、j两地间的通话费率。不妨设第 i个员工在第 ic 个城市工作,令 10阶方阵 X中的元素 ijx 满足: 1, 0, ij i ij i x j c x j c ? ????? ???,i,j