资源分配问题的优化模型转换及其算法_黄政龙
第27卷 第2期 2007年4月
中南林业科技大学学报
Jo ur nal o f Cent ral South U niv ersit y o f Fo restr y &T echno log y V ol. 27 N o. 2A pr . 2007
文章编号:1673-923X (2007) 02-0122-04
资源分配问题的优化模型转换及其算法
黄政龙
(中南林业科技大学理学院, 湖南株洲412006)
摘 要: 对资源分配问题探讨了一般的优化模型, 以利于计算机软件处理为目的, 进行了合适的模型转换, 导出了lingo 软件一般
的解题模式, 可使这类问题的处理更方便快捷.
关键词: 数学; 运筹学; 资源分配; 模型转换; lingo 软件中图分类号: O224 文献标志码: A
Conversion of Optimized Models of Resources Allocation and Its Algorithms
HUANG Zheng -long
(S chool of S ciences, Central South University of Fores try and Tech nology, Zhuz hou 412006, Hunan, China)
Abstract :T his paper discu sses s ome op tim ized model of r esour ces allocation for the purpose of process ing compu ter s oftw ar e , making
a s uitab le model con vers ion and deriving a lingo softw are model in general ques tions. It will make it more convenient an d faster to handle s uch is sues.
Key words :mathematics; operation research; allocation of res ou rces; model convers ion; lingo s oftw are
1 问题的提出
在实际问题中, 经常会遇到要将数量一定的一种或若干种资源(如原材料, 资金, 设备, 专门人才, 电力等) 恰当地分配给若干个部门或单位, 而使效益达到最优的问题. 这种问题的数学模型对一种资源而言表面上并不是很复杂, 若设资源总量为a , 分配给n 个部门, 第i 部门的分配量记为d i , 相应的效益函数为g i (d i ) , (i =1, 2, …
n
n ; i = 1d i =a ) , 则模型可以表示为:
n
max Z =i g i d i
=1 s . t .
i =1
d i =a
n
d i ≥0, i =1, 2, …, n
但实际上由于各部门的原有基础、地理位置、市场定位、使用目的等各方面的差异, 即使给各部门提供同数量的资源, 各部门所产生的效益也是不尽相同的, 即各部门的效益函数有异. 另一方面, 上面所说的效益函数还受着资源类型、时间、市场、消费者心理等很多不确定因素的影响, 其函数关系不一定是解析式. 很可能是对特定资源某几种分配可能值关于当前时段的统计数据而常常以表格形式给出, 正是这种效益函数的非解析性及离散性使得解析计算变得困难. 一般运筹学教材上都采用动态规划的列表求解, 较一般的穷举法而言, 计算过程能得到一些简化, 但仍然存在着时间过程长, 计算量大, 特别是n 、a 至少有一个较大时更是如此. 另一方面, 效益表格的数据一旦改变, (在市场经济诸多因素的影响下这种改变是很可能而且很快的) 前后分配方案之间极少
收稿日期:2006-08-15
(, , . , , .
第2期黄政龙:资源分配问题的优化模型转换及其算法
123
有借鉴之处, 不利于及时予以调整.
为了避免上述不足, 充分利用现有应用软件的强大功效, 应是一个探索的方向.
表1 不同资源分配量在不同部门产生的效益值
2 模型的再认识与转化
对于这类实际问题, 一般的做法是先预想出几种可能的分配方案, 根据有关调查, 统计, 给出表1(表中x ij =g i (d i ) 为第i 种资源分配量在第j 部门产生的效益值).
此时问题就变成了如何在每列取一个效益值(因每个部门最后只能得到一种分配结果, 只能产生一种效益) 使这n 个效益值之和为最大, 而所取得效益值又必须满足资源总数为a 的约束.
引进0-1变量:0, 否则
及资源单位数向量
z =(0, 1, 2, …, a ) T
则可建立与实际相应的数学模型:
max M =i x ij y ij
=1j =1
a +1i =1
a +1n
Table 1 Benef it value produced in diff erent resources
f rom the dif ferent department
资源单位数i
01…a
1)
各部门产生的效益值x ij 2) 3) 1x 11x 21…x a +
1, 1
2x 12x 22…x a +1, 2
……………
n x 1n x 2n …x a +1, n
1) i =0, 1, 2, …, a ; 2) x ij =g i (d j ) ; 3) 各部门序号j =1, 2, …, n .
y ij =
1, 当给j 部门分配第i 种单位资源数时
y ij =1 (j =1, 2, …, n ) z (i ) j ij =a
(同一部门只能有一种分配资源) (给各部门分配的资源总数为a )
s . t .
a +1n
i =1j =1
y ij 为0-1变量(i =1, 2, …, a +1; j =1, 2, …, n )
这是常见的0-1规划模型. 应用Lingo 软件, 可以方便、快捷的求解.
3 示例
为了方便验证, 我们从文献[1]引进一个例子.
某公司拟将新进的先进设备5台, 分配给所属的甲、乙、丙3个工厂, 经调查得信息(见表2).
问应如何分配, 才能使公司的赢利最大?
对此, 我们只要在电脑上双击Lingo 软件, 在其命令窗口按下述方式输入[2]. sets:
R/1.. 6/:z; (建立行号集合, 派生出设备台数集合) L /1. . 3/; (建立列号集合)
表2 不同设备台数在各工厂产生的赢利值Table 2 Profit value produced by dif f erent number
equipments from in various f actories
设备台数/台
01234各厂新设备赢利/万元甲工厂037912乙工厂05101111丙工厂0461112C(R, L) :x , y; (建立双下标集合(i, j) , 派生出效益集合X 以及0-1变量集合Y) endsets data:X =
0 0 03 5 47 10 69 11 1111121311
124
中 南 林 业 科 技 大 学 学 报第27卷
z=0 1 2 3 4 5;
enddata
max =@sum(c(i, j) :X(i, j) *y(i, j) ) ; (目标函数)
@for (l(i) :
@sum (c (j , k ) k #eq #i :y (j , k ) ) =1) ; (每个工厂只取一个效益值) @sum (c (i , j ) :y (i , j ) *z (i ) ) =5; (设备总台数为5) @for (c(i, j) :@Bin(y (i, j) ) ) ; (为0-1变量) end
再点击Lingo /so lve , 立刻显示出下述结果.
Global optim al solution found at iteration: 0Objective v alue: 21. 00000
Variable Z(1) Z(2) Z (3) Z(4) Z(5) Z (6) X (1, 1) X(1, 2) X(1, 3) X (2, 1) X(2, 2) X(2, 3) X (3, 1) X (3, 2) X(3, 3) X(4, 1) X (4, 2) X(4, 3) X(5, 1) X (5, 2) X (5, 3)
Value 0. 0000001. 0000002. 0000003. 0000004. 0000005. 0000000. 0000000. 0000000. 0000003. 0000005. 0000004. 0000007. 00000010. 000006. 0000009. 00000011. 0000011. 0000012. 0000011. 0000012. 00000
Reduced Cost 0. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 000000
Variable X(6, 1) X(6, 2) X (6, 3) Y(1, 1) Y(1, 2) Y (1, 3) Y (2, 1) Y(2, 2) Y(2, 3) Y (3, 1) Y(3, 2) Y(3, 3) Y (4, 1) Y (4, 2) Y(4, 3) Y(5, 1) Y (5, 2) Y(5, 3) Y(6, 1) Y (6, 2) Y (6, 3)
Row 12345
Value 13. 0000011. 0000012. 000000. 0000000. 0000000. 0000000. 0000000. 0000001. 0000001. 0000001. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 0000000. 000000
Reduced Cost 0. 0000000. 0000000. 0000000. 0000000. 0000000. 000000-3. 000000-5. 000000-4. 000000-7. 000000-10. 00000-6. 000000-9. 000000-11. 00000-11. 00000-12. 00000-11. 00000-12. 00000-13. 00000-11. 00000-12. 00000
Dual Price 1. 0000000. 0000000. 0000000. 0000000. 000000
从显示结果来看, 只有y 31=y 32=y 33=1, 其余各为0, 即分给甲厂2台, 乙厂2台, 丙厂1台. 最大总盈利为21万元.
这与教材上的结果是一致的, 但计算却方便、快捷很多.
Slack or Surplus
21. 00000
0. 0000000. 0000000. 0000000. 000000
4 讨论
从例子的Lingo 语言输入格式可以看出, 转化后的模型对于
a, n 都大的情形也是适用的, 只要把程序中的R/1…6改为R/1…a+1, L/1…3改为L/1…n, “X=”后的数据及“后的数据按实际输入就行. 因此, 该模型具有向大型问题扩展的功能, 它仍然具有方便、快捷、准确的特Z =”
点. 这主要是利用Ling o 软件的集合运算功能以及它的容易操作的菜单式命令系统, 它不需要很多专门的语言, , ,
第2期黄政龙:资源分配问题的优化模型转换及其算法
[4～6]
125
对人工计算而言很繁杂的计算. 很多专家在这方面都已作了不少的探索, 提出了很多示例. 在应用软件迅速发展的当代, 加强对数学方法与计算软件实现之间联系的研究, 应是值得注意并且具有价值的. 本文算是一种这方面的尝试. 参考文献:
[1] 《运筹学》教材编写组. 运筹学[M ]. 北京:清华大学出版社, 1990. 216-218.
[2] 谢金星, 薛 毅. 优化建模与Lindo /Lingo 软件[M ]. 北京:清华大学出版社, 2005. 101-103. [3] 徐玖平, 胡智能. 运筹学(Ⅱ类) [M ]. 北京:科学出版社, 2004. 172-173. [4] 郝红伟. M AT LAB. 6实例教程[M ]. 北京:中国电力出版社, 2001. 376-385. [5] 叶其孝. 大学生数学建模竞赛辅导教材[M ]. 长沙:湖南教育出版社, 1998. 345-380. [6] 黄政龙. 目标规划的分解算法[J ]. 中南林学院学报, 2006, 26(5) :133-136.
[本文编校:邱德勇]
(上接第114页)
湖南:石门县壶瓶山, 黄连河, 海拔670m , 常绿阔叶林中, 2006年5月4日, 壶瓶山科考队Q -052.
分布:陕西南部、湖北西部、河南南部、山西南部. 湖南首次记录.
致谢:本文得到中南林业科技大学祁承经教授的指导, 在此深表感谢.
参考文献:
[1] 颜立红, 祁承经, 刘小雄. 中国亚热带中部藤本植物区系的基本特点[J]. 中南林学院学报, 2006, 26(4) :36-41. [2] 傅立国, 陈谭清, 朗楷永, 等. 中国高等植物(第7卷) [M ]. 青岛:青岛出版社, 2001:810.
[3] 中国科学院中国植物志编委员会. 中国植物志(第45卷第3分册) [M ]. 北京:科学出版社, 1999:23, 115. [4] 中国科学院植物研究所. 中国主要植物图说[M ]. 北京:科学出版社, 1955:682.
[5] 中国科学院中国植物志编委员会. 中国植物志(第41卷) [M ]. 北京:科学出版社, 1994:222-223. [6] 中国科学院中国植物志编委员会. 中国植物志(第63卷) [M ]. 北京:科学出版社, 1977:27-29. [7] 中国科学院植物研究所. 中国高等植物图鉴补编(第二册) [M ]. 北京:科学出版社, 1985:528.
[8] 中国科学院中国植物志编委员会. 中国植物志(第73卷第1分册) [M ]. 北京:科学出版社, 1986:116, 124, 149. [9] 中国科学院中国植物志编委员会. 中国植物志(第28卷) [M ]. 北京:科学出版社, 1980:171.
[本文编校:胡曼辉]