International Journal of Industrial Engineering & Production Management (2014)
May 2014, Volume 25, Number 1
pp. 31-43
http://IJIEPM.iust.ac.ir/
A Method for Finding Non-Dominated Solutions of the
Multi Objective Combinatorial Optimization Problems by
Elastic Constraints Method
M. Darrudi & R. Sadeghian
*
Maryam Darrudi, Master of Science Student at Bu Ali Sina University, Engineering Department, Industrial Engineering Group, Hamedan, Iran.
Ramin Sadeghian, Assistant Professor at Tehran Payam Noor University, Industrial Engineering Group, Tehran, Iran, [email protected],
Keywords
Multi Objective Integer
Programming (MOIP),
Multi Objective Combinatorial
Optimization (MOCO),
Elastic Constraints (EC) Method
1
ABSTRACT
In this paper, a general procedure is developed to find all nondominated solutions of the multi objective combinatorial
optimization (MOCO) problem. This procedure is based on the
elastic constraints method and applies the identification of
objective's bounds for it. The bounds of objectives are determined by
solving single objective integer programming problems. First, the
elastic constraints method is performed on a bi-objective and triobjective problem respectively, then it is developed on a general
multi objective integer programming (MOIP) problem. In this paper,
a numerical example such as tri-objective assignment problem is
presented to clear the proposed method.
© 2014 IUST Publication, IJIEPM. Vol. 25, No. 1, All Rights Reserved
*
Corresponding author. Ramin Sadeghian
Email: [email protected]
‫‪715‬‬
‫مریم دررودي و رامین صادقیان‬
‫یافتن راهحلهای مؤثر در مسائل بهینهسازی ترکیبی چندهدفه به کمک روش ‪...‬‬
‫شمــاره ‪ ،1‬جلــد ‪ ،25‬خــرداد ‪1313‬‬
‫صفحـــه ‪32-43‬‬
‫‪http://IJIEPM.iust.ac.ir/‬‬
‫‪ISSN: 2008-4870‬‬
‫یافتن راهحلهای مؤثر در مسائل بهینهسازی ترکیبی چندهدفه به کمک‬
‫روش قیود ارتجاعی‬
‫مریم دررودي و رامین صادقیان‬
‫*‬
‫چکیده‪:‬‬
‫کلمات کلیدي‬
‫‪.‬‬
‫‪ .1‬مقدمه‬
‫‪1‬‬
‫‪-ε‬‬
‫‪.‬‬
‫تاریخ وصول‪19/4/11 :‬‬
‫تاریخ تصویب‪11/4/15 :‬‬
‫مریم دررودي‪،‬‬
‫]‬
‫[‬
‫*نویسنده مسئول مقاله‪ :‬دکتر رامین صادقیان‪،‬‬
‫‪[email protected]‬‬
‫)‪Multi Objective Combinatorial Optimization (MOCO‬‬
‫‪3‬‬
‫)‪Multi Objective Integer Programming (MOIP‬‬
‫‪4 Ehrgott & Gandibleux‬‬
‫‪2‬‬
‫نشریه بین المللي مهندسي صنایع و مدیریت تولید‪ ،‬خــرداد ‪ -1313‬جلد ‪ -27‬شماره ‪1‬‬
‫‪Klein & Hannan‬‬
‫‪Sylva & Crema‬‬
‫‪Laumanns‬‬
‫‪Scalarization Technique‬‬
‫‪5‬‬
‫‪6‬‬
‫‪7‬‬
‫‪8‬‬
‫‪33‬‬
‫مریم دررودي و رامین صادقیان‬
‫یافتن راهحلهای مؤثر در مسائل بهینهسازی ترکیبی چندهدفه به کمک روش ‪...‬‬
‫‪ε‬‬
‫[‬
‫]‬
‫‪ .2‬مفاهیم و تعاریف‬
‫‪l s‬‬
‫‪ .3‬ارائه مدل پیشنهادي‬
‫‪.1‬‬
‫‪p‬‬
‫‪ε‬‬
‫‪ε‬‬
‫]‬
‫[‬
‫‪ε‬‬
‫‪ε‬‬
‫‪.2‬‬
‫‪p‬‬
‫‪p-1‬‬
‫‪j‬‬
‫]‬
‫[‬
‫‪.3‬‬
‫‪.‬‬
‫‪The Weighted Sum Method‬‬
‫‪The ε-Constraint Method‬‬
‫‪Elastic Constraints Method‬‬
‫‪Haimes‬‬
‫‪Chankong‬‬
‫‪1‬‬
‫‪2‬‬
‫‪3‬‬
‫‪4‬‬
‫‪5‬‬
‫نشریه بین المللي مهندسي صنایع و مدیریت تولید‪ ،‬خــرداد ‪ -1313‬جلد ‪ -27‬شماره ‪1‬‬
‫‪6 Ehrgott & Ryan‬‬
‫یافتن راهحلهای مؤثر در مسائل بهینهسازی ترکیبی چندهدفه به کمک روش ‪...‬‬
‫‪34‬‬
‫مریم دررودي و رامین صادقیان‬
‫اثبات‪:‬‬
‫‪ .3-1‬مسأله برنامهریزي عدد صحیح دو هدفه‪)BOIP( 1‬‬
‫‪BOIP‬‬
‫‪2‬‬
‫‪ .3-2‬مسأله برنامه ریزي عدد صحیح سه هدفه ‪TOIP‬‬
‫‪TOIP‬‬
‫قضیه (‪:)1‬‬
‫اثبات‪:‬‬
‫‪i‬‬
‫قضیه (‪:)3‬‬
‫اثبات‪:‬‬
‫‪i‬‬
‫قضیه (‪:)2‬‬
‫‪Bi-Objective Integer Programming‬‬
‫‪1‬‬
‫‪Tri-Objective Integer Programming‬‬
‫نشریه بین المللي مهندسي صنایع و مدیریت تولید‪ ،‬خــرداد ‪ -1313‬جلد ‪ -27‬شماره ‪1‬‬
‫‪2‬‬
‫‪37‬‬
‫مریم دررودي و رامین صادقیان‬
‫یافتن راهحلهای مؤثر در مسائل بهینهسازی ترکیبی چندهدفه به کمک روش ‪...‬‬
‫قضیه (‪:)4‬‬
‫‪ .3-3‬مسأله برنامهریزي عددصحیح ‪ k‬هدفه (چندهدفه)‬
‫اثبات‪:‬‬
‫‪MOIP‬‬
‫‪MOIP‬‬
‫‪k‬‬
‫قضیه (‪:)7‬‬
‫‪k‬‬
‫)‪(k-1‬‬
‫)‪(k-1‬‬
‫اثبات‪:‬‬
‫‪i‬‬
‫)‪(k-1‬‬
‫)‪(k-1‬‬
‫‪k‬‬
‫قضیه‬
‫(‪:)6‬‬
‫نشریه بین المللي مهندسي صنایع و مدیریت تولید‪ ،‬خــرداد ‪ -1313‬جلد ‪ -27‬شماره ‪1‬‬
‫یافتن راهحلهای مؤثر در مسائل بهینهسازی ترکیبی چندهدفه به کمک روش ‪...‬‬
‫‪36‬‬
‫مریم دررودي و رامین صادقیان‬
‫اثبات‪:‬‬
‫‪k‬‬
‫‪...‬‬
‫‪k‬‬
‫)‪(k-1‬‬
‫)‪(k-1‬‬
‫‪k‬‬
‫)‪(k-1‬‬
‫)‪(k-1‬‬
‫)‪(k-1‬‬
‫)‪(k-1‬‬
‫‪k‬‬
‫)‪(k-1‬‬
‫‪k‬‬
‫فرآیند ‪:‬‬
‫(‬
‫نشریه بین المللي مهندسي صنایع و مدیریت تولید‪ ،‬خــرداد ‪ -1313‬جلد ‪ -27‬شماره ‪1‬‬
‫‪k‬‬
‫‪35‬‬
‫مریم دررودي و رامین صادقیان‬
‫یافتن راهحلهای مؤثر در مسائل بهینهسازی ترکیبی چندهدفه به کمک روش ‪...‬‬
‫)‬
‫جدول ‪ .1‬حدود باالیي و پائیني توابع هدف به همراه جایگشت هر یک‬
‫‪2‬‬
‫‪4‬‬
‫‪3‬‬
‫‪5‬‬
‫‪1‬‬
‫‪3‬‬
‫‪5‬‬
‫‪1‬‬
‫‪4‬‬
‫‪2‬‬
‫‪F1 =121‬‬
‫‪5‬‬
‫‪3‬‬
‫‪3‬‬
‫‪2‬‬
‫‪4‬‬
‫‪1‬‬
‫‪1‬‬
‫‪4‬‬
‫‪2‬‬
‫‪5‬‬
‫‪F2U =395‬‬
‫‪5‬‬
‫‪2‬‬
‫‪3‬‬
‫‪5‬‬
‫‪1‬‬
‫‪4‬‬
‫‪2‬‬
‫‪3‬‬
‫‪4‬‬
‫‪1‬‬
‫‪F1U =333‬‬
‫‪L‬‬
‫‪L‬‬
‫‪F2 =131‬‬
‫‪F3U =421‬‬
‫‪F3L =111‬‬
‫جدول ‪ .2‬ضرایب تابع هدف براي مثال مسأله تخصیص‬
‫‪ .4‬مثال عددي‬
‫سههدفه‬
‫‪1‬‬
‫‪c‬‬
‫‪c2‬‬
‫‪p‬‬
‫) ‪(pAP‬‬
‫‪c3‬‬
‫‪p- objective Assignment Problem‬‬
‫نشریه بین المللي مهندسي صنایع و مدیریت تولید‪ ،‬خــرداد ‪ -1313‬جلد ‪ -27‬شماره ‪1‬‬
‫‪1‬‬
‫یافتن راهحلهای مؤثر در مسائل بهینهسازی ترکیبی چندهدفه به کمک روش ‪...‬‬
‫‪33‬‬
‫مریم دررودي و رامین صادقیان‬
‫جدول ‪ .3‬راهحلهاي موثر مساله‬
‫‪R5‬‬
‫‪R4‬‬
‫‪R3‬‬
‫‪R2‬‬
‫‪R1‬‬
‫‪F3‬‬
‫‪F2‬‬
‫‪F1‬‬
‫‪R5‬‬
‫‪R4‬‬
‫‪R3‬‬
‫‪R2‬‬
‫‪R1‬‬
‫‪F3‬‬
‫‪F2‬‬
‫‪F1‬‬
‫نشریه بین المللي مهندسي صنایع و مدیریت تولید‪ ،‬خــرداد ‪ -1313‬جلد ‪ -27‬شماره ‪1‬‬
‫یافتن راهحلهای مؤثر در مسائل بهینهسازی ترکیبی چندهدفه به کمک روش ‪...‬‬
‫‪31‬‬
‫مریم دررودي و رامین صادقیان‬
‫‪MOIP‬‬
‫‪n‬‬
‫‪ε‬‬
‫‪ .7‬بحث و نتیجهگیري‬
‫‪ε‬‬
‫‪ε‬‬
‫نشریه بین المللي مهندسي صنایع و مدیریت تولید‪ ،‬خــرداد ‪ -1313‬جلد ‪ -27‬شماره ‪1‬‬
‫یافتن راهحلهای مؤثر در مسائل بهینهسازی ترکیبی چندهدفه به کمک روش ‪...‬‬
‫‪49‬‬
‫مریم دررودي و رامین صادقیان‬
‫شکل ‪ .2‬مقایسه دو روش – محدودیت و قیود‬
‫ارتجاعي با افزایش تعداد متغیرها‬
‫‪ε‬‬
‫جدول ‪ .4‬ضرایب تابع هدف براي مسأله تخصیص سههدفه‬
‫شکل ‪ .1‬مقایسه دو روش – محدودیت و قیود‬
‫ارتجاعي با افزایش تعداد اهداف‬
‫‪4‬‬
‫‪3‬‬
‫‪2‬‬
‫‪1‬‬
‫‪7‬‬
‫‪4‬‬
‫‪5‬‬
‫‪2‬‬
‫‪7‬‬
‫‪5‬‬
‫‪3‬‬
‫‪3‬‬
‫‪2‬‬
‫‪4‬‬
‫‪8‬‬
‫‪3‬‬
‫‪5‬‬
‫‪2‬‬
‫‪5‬‬
‫‪6‬‬
‫‪4‬‬
‫‪3‬‬
‫‪2‬‬
‫‪1‬‬
‫‪2‬‬
‫‪6‬‬
‫‪3‬‬
‫‪3‬‬
‫‪3‬‬
‫‪7‬‬
‫‪3‬‬
‫‪5‬‬
‫‪4‬‬
‫‪7‬‬
‫‪2‬‬
‫‪5‬‬
‫‪5‬‬
‫‪3‬‬
‫‪6‬‬
‫‪4‬‬
‫‪4‬‬
‫‪3‬‬
‫‪2‬‬
‫‪1‬‬
‫‪3‬‬
‫‪5‬‬
‫‪2‬‬
‫‪4‬‬
‫‪3‬‬
‫‪4‬‬
‫‪3‬‬
‫‪5‬‬
‫‪2‬‬
‫‪5‬‬
‫‪3‬‬
‫‪4‬‬
‫‪3‬‬
‫‪7‬‬
‫‪4‬‬
‫‪6‬‬
‫نشریه بین المللي مهندسي صنایع و مدیریت تولید‪ ،‬خــرداد ‪ -1313‬جلد ‪ -27‬شماره ‪1‬‬
‫‪1‬‬
‫‪c‬‬
‫‪2‬‬
‫‪c‬‬
‫‪3‬‬
‫‪c‬‬
‫‪41‬‬
‫مریم دررودي و رامین صادقیان‬
‫یافتن راهحلهای مؤثر در مسائل بهینهسازی ترکیبی چندهدفه به کمک روش ‪...‬‬
‫جدول ‪ .7‬حدود باالیي و پائیني توابع هدف‬
‫‪f3U =18‬‬
‫‪f2U =21‬‬
‫‪f1U =26‬‬
‫‪f3L =13‬‬
‫‪f2L =11‬‬
‫‪f1L =9‬‬
‫‪b3 b2‬‬
‫جدول ‪ .6‬مراحل اجراي فرایند حل مثال تخصیص سه هدفه‬
‫≤ ‪b2‬‬
‫‪f3‬‬
‫‪f2‬‬
‫‪f1‬‬
‫‪b3≤16‬‬
‫≤ ‪b2‬‬
‫‪f3‬‬
‫‪f2‬‬
‫‪f1‬‬
‫‪b3≤18‬‬
‫‪21‬‬
‫‪16‬‬
‫‪13‬‬
‫‪9‬‬
‫‪4‬‬
‫‪21‬‬
‫‪16‬‬
‫‪13‬‬
‫‪9‬‬
‫‪1‬‬
‫‪infeasible‬‬
‫‪5‬‬
‫‪12‬‬
‫‪17‬‬
‫‪11‬‬
‫‪19‬‬
‫‪2‬‬
‫‪12‬‬
‫‪10‬‬
‫‪infeasible‬‬
‫‪max(f3)= 16‬‬
‫‪3‬‬
‫‪max(f3)= 17‬‬
‫≤ ‪b2‬‬
‫‪f3‬‬
‫‪f2‬‬
‫‪f1‬‬
‫‪b3≤14‬‬
‫≤ ‪b2‬‬
‫‪f3‬‬
‫‪f2‬‬
‫‪f1‬‬
‫‪b3≤15‬‬
‫‪21‬‬
‫‪14‬‬
‫‪20‬‬
‫‪14‬‬
‫‪10‬‬
‫‪21‬‬
‫‪14‬‬
‫‪20‬‬
‫‪14‬‬
‫‪6‬‬
‫‪19‬‬
‫‪14‬‬
‫‪18‬‬
‫‪18‬‬
‫‪11‬‬
‫‪19‬‬
‫‪15‬‬
‫‪18‬‬
‫‪14‬‬
‫‪7‬‬
‫‪17‬‬
‫‪14‬‬
‫‪17‬‬
‫‪20‬‬
‫‪12‬‬
‫‪17‬‬
‫‪14‬‬
‫‪17‬‬
‫‪20‬‬
‫‪8‬‬
‫‪13‬‬
‫‪16‬‬
‫‪infeasible‬‬
‫‪16‬‬
‫‪infeasible‬‬
‫‪max(f3)= 14‬‬
‫≤ ‪b2‬‬
‫‪21‬‬
‫‪f3‬‬
‫‪f2‬‬
‫‪9‬‬
‫‪max(f3)= 15‬‬
‫‪f1‬‬
‫‪infeasible‬‬
‫‪b3≤12‬‬
‫≤ ‪b2‬‬
‫‪f3‬‬
‫‪f2‬‬
‫‪f1‬‬
‫‪b3≤13‬‬
‫‪16‬‬
‫‪21‬‬
‫‪13‬‬
‫‪20‬‬
‫‪18‬‬
‫‪14‬‬
‫‪19‬‬
‫‪infeasible‬‬
‫‪max(f3)= 13‬‬
‫نشریه بین المللي مهندسي صنایع و مدیریت تولید‪ ،‬خــرداد ‪ -1313‬جلد ‪ -27‬شماره ‪1‬‬
‫‪15‬‬
42
[2]
[3]
‫مریم دررودي و رامین صادقیان‬
... ‫یافتن راهحلهای مؤثر در مسائل بهینهسازی ترکیبی چندهدفه به کمک روش‬
‫ راهحلهاي موثر مساله تخصیص سه هدفه‬.5 ‫جدول‬
Przybylski. A., Gandibleux. X., Ehrgott. M., The
Biobjective Integer Minimum Cost Flow Problem—
Incorrectness of Sedeño-Noda and GonzàlezMartin's Algorithm, Computers & Operations
Research, May 2006, Vol. 33, Issue 5, pp. 14591463.
Klein, D., Hannan, E., An Algorithm for the
Multiple Objective Integer Linear Programming
Problem, European Journal of Operational
Research, 1982, 9, 378–385.
[4]
Sylva, J., Crema, A., A Method for Finding the Set
of Non-Dominated Vectors for Multiple Objective
Integer Linear Programs, European Journal of
Operational Research, 2004, 158, pp. 46–55.
[5]
Laumanns, M., Thiele, L., Zitzler, E., An Efficient
Adaptive Parameter Variation Scheme for
Metaheuristics Based on the Epsilon-Constraint
Method. European Journal of Operational Research,
2006, 169, pp. 932–942.
[6]
Guu, S.M., Huang, N.J., Scalarization Approaches
for Set-Valued Vector Optimization Problems and
Vector
Variational
Inequalities, Journal
of
Mathematical Analysis and Applications, 15 August
2009,Volume 356, Issue 2, pp. 564-576.
[7]
Ehrgott, M., A Discussion of Scalarization
Techniques for Multiple Objective Integer
Programming, Ann Oper Res, 2006, 147:343–360.
[8]
Jiménez, B., Novo, V., Sama, M., Scalarization and
Optimality Conditions for Strict Minimizers in Multi
Objective
Optimization
Via
Contingent
Epiderivatives, Journal of Mathematical Analysis
and Applications, 15 April 2009, Volume 352, Issue
2, Pages 788-798.
[9]
Hernández, E., Rodríguez-Marín, L., Nonconvex
Scalarization in Set Optimization with Set-Valued
Maps Journal of Mathematical Analysis and
Applications, 1 January 2007, Volume 325, Issue
1, Pages 1-18.
[10]
Gutiérrez, C., Jiménez, B., Novo, V., Optimality
Conditions Via Scalarization for a New ε-Efficiency
Concept in Vector Optimization Problems,
European Journal of Operational Research, 16
February 2010,Volume 201, Issue 1, Pages 11-22.
Geoffrion, A.M., Proper Efficiency and the Theory
of Vector Maximization, Journal of Mathematical
Analysis and Applications, 1968, 22:618–630.
F2
F3
19
11
11
9
13
11
14
13
15
14
22
14
22
11
14
13
22
13
13
13
14
[ ]
K-1
K
‫مراجع‬
[1]
[11]
F1
Ehrgott, M., Gandibleux, X., Bound Sets for
Biobjective Combinatorial Optimization Problems,
Computers & Operations Research, September
2007,Vol. 34, Issue 9, pp. 2674-2694.
1 ‫ شماره‬-27 ‫ جلد‬-1313 ‫ خــرداد‬،‫نشریه بین المللي مهندسي صنایع و مدیریت تولید‬
‫مریم دررودي و رامین صادقیان‬
... ‫یافتن راهحلهای مؤثر در مسائل بهینهسازی ترکیبی چندهدفه به کمک روش‬
43
[12]
Chankong, Haimes, Y.Y., Multi objective Decision
Making Theory and Methodology, Elsevier Science,
New York, 1983.
[13]
Ehrgott, M., Ryan, D.M., Constructing Robust
Crew Schedules with Bi Criteria Optimization,
Journal of Multi-Criteria Decision Analysis, 2002,
11(3): 139–150.
[14]
Ehrgott, M., Gandibleux, X., A Survey and
Annotated Bibliography of Multi Objective
Combinatorial Optimization, OR Spektrum, 2000,
22: 425–460.
[15]
Przybylski, A., Gandibleux, X., Ehrgott, M., A Two
Phase Method for Multi-Objective Integer
Programming and its Application to the Assignment
Problem with Three Objectives, Discrete
Optimization, 2010, Vol. 7, pp. 149_165.
1 ‫ شماره‬-27 ‫ جلد‬-1313 ‫ خــرداد‬،‫نشریه بین المللي مهندسي صنایع و مدیریت تولید‬
‫یافتن راهحلهای مؤثر در مسائل بهینهسازی ترکیبی چندهدفه به کمک روش ‪...‬‬
‫مریم دررودي و رامین صادقیان‬
‫نشریه بین المللي مهندسي صنایع و مدیریت تولید‪ ،‬خــرداد ‪ -1313‬جلد ‪ -27‬شماره ‪1‬‬
‫‪44‬‬

تبدیلات لاپلاس در یک نگاه