解一类运输生产问题修正的松驰型分枝定界算法

数学季刊 ›› 2010, Vol. 25 ›› Issue (1): 52-59.

解一类运输生产问题修正的松驰型分枝定界算法

1. Science College, China Three Gorges University2. College of Mathematics and Computer Science, Wuhan University

收稿日期:2007-11-08 出版日期:2010-03-30 发布日期:2023-06-09
作者简介:DU Ting-song(1969- ), male, native of Lichuan, Hubei, an associate professor of China Three Gorges University, M.S.D., engages in optimization theory and algorithm and numerical simulation.
基金资助:
Supported by the National Natural Science Foundation of China(10726016)； Supported by the Hubei Province Natural Science Foundation Project(T200809； D200613002)；

Relaxation-strategy-based Modification Branch-and-Bound Algorithm for Solving a Class of Transportation-production Problems

1. Science College, China Three Gorges University2. College of Mathematics and Computer Science, Wuhan University

Received:2007-11-08 Online:2010-03-30 Published:2023-06-09
About author:DU Ting-song(1969- ), male, native of Lichuan, Hubei, an associate professor of China Three Gorges University, M.S.D., engages in optimization theory and algorithm and numerical simulation.
Supported by:
Supported by the National Natural Science Foundation of China(10726016)； Supported by the Hubei Province Natural Science Foundation Project(T200809； D200613002)；

摘要/Abstract

摘要： In this paper, a new algorithm relaxation-strategy-based modification branch-and-bound algorithm is developed for a type of solving the minimum cost transportation production problem with concave production costs. The major improvement of the proposed new method is that modification algorithm reinforces the bounding operation using a Lagrangian relaxation, which is a concave minimization but obtains a tighter bound than the usual linear programming relaxation. Some computational results are included. Computation results indicate that the algorithm can solve fairly large scale problems.

关键词: branch-and-bound algorithm, transportation-production problem, Lagrangian
relaxation

Abstract: In this paper, a new algorithm relaxation-strategy-based modification branch-and-bound algorithm is developed for a type of solving the minimum cost transportation production problem with concave production costs. The major improvement of the proposed new method is that modification algorithm reinforces the bounding operation using a Lagrangian relaxation, which is a concave minimization but obtains a tighter bound than the usual linear programming relaxation. Some computational results are included. Computation results indicate that the algorithm can solve fairly large scale problems.

Key words: branch-and-bound algorithm, transportation-production problem, Lagrangian
relaxation

中图分类号:

O221.2

杜廷松, 费浦生, 蹇继贵. 解一类运输生产问题修正的松驰型分枝定界算法[J]. 数学季刊, 2010, 25(1): 52-59.

DU Ting-song, FEI Pu-sheng, JIAN Ji-gui. Relaxation-strategy-based Modification Branch-and-Bound Algorithm for Solving a Class of Transportation-production Problems [J]. Chinese Quarterly Journal of Mathematics, 2010, 25(1): 52-59.

[1]	赵克全, 陈哲, 杨新民. 强伪不变凸性和强伪不变单调性的等价性[J]. 数学季刊, 2011, 26(4): 608-612.
[2]	孙清滢, 桑兆阳, 田凤婷. 求解无约束非线性规化问题的一个新的重开始三项共轭梯度算法的收敛性[J]. 数学季刊, 2011, 26(1): 69-76.
[3]	张和平, 叶留青. 不等式约束最优化问题的可行SQP下降算法及其收敛性[J]. 数学季刊, 2009, 24(3): 469-474.
[4]	朱冬梅, 王治国. 拟单调问题的讨论[J]. 数学季刊, 2006, 21(3): 461-464.
[5]	尚有林, 李晓燕. 无约束全局优化的一个可调参数的填充函数[J]. 数学季刊, 2004, 19(3): 232-239.
[6]	曹丽华, 孙清滢. 结合修正Curry-Altman步长搜索一个新的共轭梯度算法的收敛性[J]. 数学季刊, 2004, 19(2): 198-204.