Top

OR Spectrum

Published in:

01-01-2015 | Regular Article

Duality in fuzzy linear programming: a survey

Authors: Guido Schryen, Diana Hristova

Published in: OR Spectrum | Issue 1/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The concepts of both duality and fuzzy uncertainty in linear programming have been theoretically analyzed and comprehensively and practically applied in an abundance of cases. Consequently, their joint application is highly appealing for both scholars and practitioners. However, the literature contributions on duality in fuzzy linear programming (FLP) are neither complete nor consistent. For example, there are no consistent concepts of weak duality and strong duality. The contributions of this survey are (1) to provide the first comprehensive overview of literature results on duality in FLP, (2) to analyze these results in terms of research gaps in FLP duality theory, and (3) to show avenues for further research. We systematically analyze duality in fuzzy linear programming along potential fuzzifications of linear programs (fuzzy classes) and along fuzzy order operators. Our results show that research on FLP duality is fragmented along both dimensions; more specifically, duality approaches and related results vary in terms of homogeneity, completeness, consistency with crisp duality, and complexity. Fuzzy linear programming is still far away from a unifying theory as we know it from crisp linear programming. We suggest further research directions, including the suggestion of comprehensive duality theories for specific fuzzy classes while dispensing with restrictive mathematical assumptions, the development of consistent duality theories for specific fuzzy order operators, and the proposition of a unifying fuzzy duality theory.

next article Lower bounds for three-dimensional multiple-bin-size bin packing problems

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Note that each linear problem can be easily transformed into the form given below.

Here, we define the dual problem by means of mathematical properties. An alternative, economic interpretation is given by (Hillier and Lieberman (2010), p. 203ff).

The researchers interpret \(x\) as production units and \(y\) as resource prices on the market.

Eventually, we can also have \(c=-\infty \), or \(a=b\), or \(c=a\), or \(b=d\), or \(d=\infty \).

“Nowadays, definition 5-3 [defining a fuzzy number with a core of one element] is very often modified. For the sake of computational efficiency and ease of data acquisition, trapezoidal membership functions are often used. [...] Strictly speaking, it [the fuzzy set with trapezoidal membership functions] is a fuzzy interval [...]” (p. 59)

Note that we define the concepts of \(\alpha \)-feasible and \(\alpha \)-satisficing solution here for the particular case to which the researchers apply duality theory. Their definition is much broader.

The researcher, too, works with the same type of fuzzy numbers as Inuiguchi et al. (2003) with the difference that the membership functions of Ramík (2005) are semistrictly quasi-concave.

The researchers define fuzzy arithmetics based on interval arithmetic and \(\alpha \)-cuts, which is equivalent to the extension principle approach.

The interested reader can refer to reference Liu et al. (1995) (p. 392, Definition 2.2) for more information on the potential basis of an \(MC^2\) problem.

Here \(R(i,j)\) is a pair of ranges for \(\gamma \) and \(\lambda \).

Abboud N, Inuiguchi M, Sakawa M, Uemura Y (December 1998) Manpower allocation using genetic annealing. Eur J Oper Res 111(2):405–420

Baykasoglu A, Goecken T (2008) A review and classification of fuzzy mathematical programs. J Intell Fuzzy Syst 19: 205–229. ISSN 1064–1246

Bector CR, Chandra S (2002) On duality in linear programming under fuzzy environment. Fuzzy Sets Syst 125(3): 317–325. ISSN 0165–0114

Bellman RE, Zadeh LA (1970) Decision-making in a fuzzy environment. Manag Sci 17(4):141–164CrossRef

Bertsimas D, Tsitsiklis JN (1997) Introduction to linear optimization, volume 6 of Athena scientific series in optimization and neural computation. Athena Scientific

Bilgen B (2010) Supply chain network modeling in a golf club industry via fuzzy linear programming approach. J Intell Fuzzy Syst Appl Eng Technol 21:243–253. ISSN 1064–1246

Cadenas Figueredo JM, Jiménez Barrionuevo F (1996) A dual approach in fuzzy linear programming. Mathware Soft Comput 3(3):383–394

Carlsson C, Fullér R (2001) On possibilistic mean value and variance of fuzzy numbers. Fuzzy Sets Syst 122(2):315–326. ISSN 0165–0114

Chanas S (1983) The use of parametric programming in fuzzy linear programming. Fuzzy Sets Syst 11(1–3): 229–241. ISSN 0165–0114

Chanas S, Kuchta D (1996) A concept of the optimal solution of the transportation problem with fuzzy cost coefficients. Fuzzy Sets Syst 82(3):299–305. ISSN 0165–0114

Chanas S, Kuchta D (1998) Fuzzy integer transportation problem. Fuzzy Sets Syst 98(3):291–298, 1998. ISSN 0165–0114

Chang N-B, Wen CG, Chen YL (1997) A fuzzy multi-objective programming approach for optimal management of the reservoir watershed. Eur J Operat Res 99(2):289–302. ISSN 0377–2217.

Chen C-K, Lin J-Mu (2001) A multi-objective fuzzy optimization for optimum dimensions design of a convective spine. Int Commun Heat Mass Transfer 28(1):67–76. ISSN 0735–1933

Chen Y-W, Tzeng G-H (2000) Fuzzy multi-objective approach to the supply chain model. Int J Fuzzy Syst 2:220–228

Cheng Ching-Hsue (1998) A new approach for ranking fuzzy numbers by distance method. Fuzzy Sets Syst 95(3):307–317CrossRef

Czyzak P (1990) Application of the ’flip’ method to farm structure optimization under uncertainty. In: Slowinski R, Teghem J (eds) Stochastic versus fuzzy approaches to multiobjective mathematical programming under uncertainty. Reidei, Dordrecht, pp 263–278CrossRef

Darzentas J (1987) On fuzzy location models. In: Kacprzyk J, Orlovski SA (eds) Optimization models using fuzzy sets and possibility theory. Reidei, Dordrecht, pp 328–341CrossRef

Dubois D, Prade H (1978) Operations on fuzzy numbers. Int J Syst Sci 9(6):613–626CrossRef

Dubois D, Prade H (1980) Fuzzy sets and systems: theory and applications. Academic Press, New York

Dubois D, Prade H (1985) A review of fuzzy set aggregation connectives. Inform Sci 36:85–121CrossRef

Dubois F, Prade H (1983) Ranking fuzzy numbers in the setting of possibility theory. Inform Sci 30(3):183–224CrossRef

Waiel F. Abd El-Wahed (2001) A multi-objective transportation problem under fuzziness. Fuzzy Sets Syst 117(1):27–33. ISSN 0165–0114.

Gordon G (n.d.) Linear programming, lagrange multipliers, and duality. http://www.cs.cmu.edu/~ggordon/lp.pdf

Gupta MM, Sanchez E (1982) Fuzzy information and decision processes. Elsevier Science Ltd, Amsterdam. ISBN 0444864911

Gupta P, Mehlawat MK (2009) Bector-chandra type duality in fuzzy linear programming with exponential membership functions. Fuzzy Sets Syst 160:3290–3308. ISSN 0165–0114

Hamacher H, Leberling H, Zimmermann HJ (1978) Sensitivity analysis in fuzzy linear programming. Fuzzy Sets Syst 1(4):269–281CrossRef

Hanuscheck R (1986) Investitionsplanung auf der Grundlage vager Daten. Wissenschaftliche Schriften, Reihe 2. Schulz-Kirchner, Idstein. ISBN 3925196196

Hashemi SM, Modarres M, Nasrabadi E, Nasrabadi MM (2006) Fully fuzzified linear programming, solution and duality. J Intell Fuzzy Syst 17(3):253–261. ISSN 10641246

Hillier FS, Lieberman GJ (2010) Introduction to operations research, 9 edn. McGraw-Hill, New York

Hsu H-M, Wang W-P (2001) Possibilistic programming in production planning of assemble-to-order environments. Fuzzy Sets Syst 119(1):59–70. ISSN 0165–0114

Inuiguchi M, Ramík J, Tanino T, Vlach M (2003) Satisficing solutions and duality in interval and fuzzy linear programming. Fuzzy Sets Syst 135:151–177. ISSN 0165–0114

Kara Y, Paksoy T, Chang C-T (2009) Binary fuzzy goal programming approach to single model straight and u-shaped assembly line balancing. Eur J Oper Res 195(2):335–347. ISSN 0377–2217

Karakas E, Koyuncu M, Erol R, Kokangul A (2010) Fuzzy programming for optimal product mix decisions based on expanded abc approach. Int J Prod Res 48(3):729–744CrossRef

Kim K, Park KS (1990) Ranking fuzzy numbers with index of optimism. Fuzzy sets Syst 35(2):143–150

Klir GJ, Yuan B (1995) Fuzzy Sets Fuzzy Logic: Theory Appl. Prentice-Hall, New Jersey

Lai KK, Li L (1999) A dynamic approach to multiple-objective resource allocation problem. Eur J Oper Res 117 (2):293–309. ISSN 0377–2217

Lai Y-J, Hwang C-L (1994) Fuzzy multiple objective decision making, methods and applications. Lecture notes in economics and mathematical systems. Springer, Berlin/HeidelbergCrossRef

Lai Y-J, Hwang Ch.-L. (1992) Fuzzy mathematical programming: methods and applications. Springer, New York

Lee Bum-il, Chung Nam-Kee, Tcha Dong-Wan (July 1991) A parallel algorithm and duality for a fuzzy multiobjective linear fractional programming problem. Comput Ind Eng 20:367–372

León T, Liern V, Vercher E (2002) Viability of infeasible portfolio selection problems: a fuzzy approach. Eur J Oper Res 139(1):178–189. ISSN 0377–2217

Leung Y (1988) Interregional equilibrium and fuzzy linear programming: 2. Environ Plan A 20(2):219–230CrossRef

Li YP, Huang GH, Guo p, Nie SL (2010) Interval-fuzzy possibilistic mixed integer linear programming for environmental management under uncertainty. Int J Environ Pollut 42(1/2/3):107–124

Liu S-T, Kao C (2004) Solving fuzzy transportation problems based on extension principle. Eur J Oper Res 153(3):661–674. ISSN 0377–2217

Liu YJ, Shi Y, Liu YH (1995) Duality of fuzzy mc2 linear programming: a constructive approach. J Math Anal Appl 194(2):389–413. ISSN 0022–247X

Mahdavi-Amiri N, Nasseri SH (2005) Duality in fuzzy variable linear programming. In: Proceedings of WEC’ 05, the fourth world enformatika conference, vol 6, pp 115–117, Istanbul, June 2005

Mahdavi-Amiri N, Nasseri SH (2006) Duality in fuzzy number linear programming by use of a certain linear ranking function. Appl Math Comput 180(1):206–216CrossRef

Mahdavi-Amiri N, Nasseri SH (2007) Duality results and a dual simplex method for linear programming problems with trapezoidal fuzzy variables. Fuzzy Sets Syst 158:1961–1978. ISSN 0165–0114

Mjelde KM (1986) Fuzzy resource allocation. Fuzzy Sets Syst 19:239–250. ISSN 0165–0114

Mondal S, Maiti M (2003) Multi-item fuzzy EOQ models using genetic algorithm. Comput Ind Eng 44(1):105–117. ISSN 0360–8352

Nasseri SH, Ebrahimnejad A, Mizuno S (2010) Duality in fuzzy linear programming with symmetric trapezoidal numbers. Appl Appl Math Int J 5(10):1467–1482

Nasseri SH, Mahdavi-Amiri N (March 2009) Some duality results on linear programming problems with symmetric fuzzy numbers. Fuzzy Inform Eng 1(1):59–66

Oder C, Rentz O (1993) Entwicklung eines auf der theorie unscharfer mengen basierenden energie-emissions-modells. In: Operations research proceedings, pp 111–118. Springer, Berlin

Östermark R (1988) Profit apportionment in concerns with mutual ownership—an application of fuzzy inequalities. Fuzzy Sets Syst 26(3):283–297. ISSN 0165–0114

Östermark R (1989) Fuzzy linear constraints in the capital asset pricing model. Fuzzy Sets Syst 30(2):93–102. ISSN 0165–0114

Owsinski JW, Zadrozny S, Kacprzyk J (1987) Analysis of water use and needs in agriculture through a fuzzy programming model. In: Kacprzyk J, Orlovski SA (eds) Optimization models using fuzzy sets and possibility theory. Reidei, Dordrecht, pp 377–395CrossRef

Özcan U, Toklu B (2009) Multiple-criteria decision-making in two-sided assembly line balancing: a goal programming and a fuzzy goal programming models. Comput Oper Res 36(6):1955–1965. ISSN 0305–0548

Peidro D, Mula J, JimTnez M, del Mar Botella M (2010) A fuzzy linear programming based approach for tactical supply chain planning in an uncertainty environment. Eur J Oper Res 205(1):65–80. ISSN 0377–2217

Peidro D, Mula J, Poler R (2010) Fuzzy linear programming for supply chain planning under uncertainty. Int J Inform Technol Decis Making 9(03):373–392CrossRef

Ramík J, Rimanek J (1987) Fuzzy parameters in optimal allocation of resources. In: Kacprzyk J, Orlovski SA (eds) Soft optimization models using fuzzy sets and possibility theory. Reidei, Dordrecht, pp 359–374CrossRef

Ramík J (2001) Soft computing: overview and recent developments in fuzzy optimization. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.94.5211&rep=rep1&type=pdf

Ramík Jaroslav (February 2005) Duality in fuzzy linear programming: some new concepts and results. Fuzzy Optim Decis Mak 4(1):25–39

Ramík J (2006) Duality in fuzzy linear programming with possibility and necessity relations. Fuzzy Sets Syst 157:1283–1302. ISSN 0165–0114

Rödder W, Zimmermann H-J (1980) Duality in fuzzy linear programming. In: Fiacco AV, Kortanek KO (eds) Extremal methods and system analysis. Springer, Berlin/New York, pp 415–429CrossRef

Rommelfanger H (1996) Fuzzy linear programming and applications. Eur J Oper Res 92(3):512–527. ISSN 0377–2217

Roy TK, Maiti M (1998) Multi-objective inventory models of deteriorating items with some constraints in a fuzzy environment. Comput Oper Res 25:1085–1095. ISSN 0305–0548

Roy TK, Maiti M (1997) A fuzzy eoq model with demand-dependent unit cost under limited storage capacity. Eur J Oper Res 99(2):425–432. ISSN 0377–2217

Sakawa M, Yano H (1994) A fuzzy dual decomposition method for large-scale multiobjective nonlinear programming problems. Fuzzy Sets Syst 67(1):19–27CrossRef

Sakawa M, Nishizaki I, Uemura Y (2001) Fuzzy programming and profit and cost allocation for a production and transportation problem. Eur J Oper Res 131(1):1–15. ISSN 0377–2217

Shih L-H (1999) Cement transportation planning via fuzzy linear programming. Int J Prod Econ 58(3):277–287. ISSN 0925–5273

Slowinski R (1987) An interactive method for multiobjective linear programming with fuzzy parameters and its application to water supply planning. In: Optimization models using fuzzy sets and possibility theory, pp 396–414. Reide, Dordrecht

Slowinski R (1986) A multicriteria fuzzy linear programming method for water supply system development planning. Fuzzy Sets Syst 19(3):217–237. ISSN 0165–0114

Sommer G, Pollatschek MA (1978) A fuzzy programming approach to an air pollution regulation problem. In: Klir GJ, Trappl R, Pichler FR (eds) Progress in cybernetics and systems research: general system methodology. Mathematical system theory, and fuzzy systems, biocybernetics and theoretical neurobiology, vol 3. Hemisphere, Washington, DC, pp 303–313

Spengler T (1992) Fuzzy-Entscheidungsmodelle für die Planung der Personalbereitstellung. In: Gaul W et al (eds) Operations research proceedings. Springer, Berlin, pp 501–508

Sun G-J, Liu Y-K, Lan Y-F (2010) Optimizing material procurement planning problem by two-stage fuzzy programming. Comput Ind Eng 58(1):97–107. ISSN 0360–8352

Tang J, Wang D, Fung RYK (2000) Fuzzy formulation for multi-product aggregate production planning. Prod Plan Control 11(7):670–676CrossRef

Trappey JFC, Liu CR, Chang TC (1988) Fuzzy non-linear programming: theory and application in manufacturing. Int J Prod Res 26:957–985CrossRef

Verdegay JL (1984) Applications of fuzzy optimization in operational research. Control Cybern 13:229–239

Verdegay JL (1984) A dual approach to solve the fuzzy linear programming problem. Fuzzy Sets Syst 14(2):131–141. ISSN 0165–0114

Verma R, Biswal MP, Biswas A (1997) Fuzzy programming technique to solve multi-objective transportation problems with some non-linear membership functions. Fuzzy Sets Syst 91(1):37–43. ISSN 0165–0114

Wagenknecht M, Hartmann K (1987) Fuzzy evaluation of pareto points and its application to hydrocracking processes. In: Kacprzyk J, Orlovski SA (eds) Optimization models using fuzzy sets and possibility theory, pp 415–431. Reidei, Dordrecht

Wang PZ, Östermark R, Alex R, Tan SH (2001) Using fuzzy bases to resolve nonlinear programming problems. Fuzzy Sets Syst 117(1):81–93. ISSN 0165–0114

Wang R-C, Liang T-F (2004) Application of fuzzy multi-objective linear programming to aggregate production planning. Comput Ind Eng 46:17–41. ISSN 0360–8352

Wiedey G, Zimmermann H-J (1978) Media selection and fuzzy linear programming. J Oper Res Soc 29(11):1071–1084. ISSN 01605682

Wolf J (1988) Lineare Fuzzy-Modelle zur Unterstützung der Investitionsentscheidung. P. Lang

Wu DD, Zhang Y, Wu D, Olson DL (2010) Fuzzy multi-objective programming for supplier selection and risk modeling: a possibility approach. Eur J Oper Res 200(3):774–787. ISSN 0377–2217

Wu H-C (2003a) Duality theory in fuzzy mathematical programming problems based on the concepts of necessity. Fuzzy Sets Syst 139(139):363–377

Wu H-C (2003b) Duality theory in fuzzy linear programming problems with fuzzy coefficients. Fuzzy Optim Decis Mak 2(1):61–73

Hsien-Chung Wu (December 2004) Duality theory in fuzzy optimization problems. Fuzzy Optim Decis Mak 3(4):345–365

Zadeh LA (1975) The concept of a linguistic variable and its application to approximate reasoning, i. Inform Sci 8:199–251CrossRef

Zadeh LA (1975) The concept of a linguistic variable and its application to approximate reasoning, ii. Inform Sci 8:301–357CrossRef

Zadeh LA (1976) The concept of a linguistic variable and its application to approximate reasoning, iii. Inform Sci 9:43–80CrossRef

Zadeh Lotfi (1965) Fuzzy sets. Inform Control 8:338–353CrossRef

Zhong Y, Shi Y (2002) Duality in fuzzy multi-criteria and multi-constraint level linear programming: a parametric approach. Fuzzy Sets Syst 132:335–346. ISSN 0165–0114

Zimmermann H-J (1976) Description and optimization of fuzzy systems. Int J Gen Syst 2(4):209–215CrossRef

Zimmermann HJ (1985) Applications of fuzzy set theory to mathematical programming. Inform Sci 36(1–2):29–58. ISSN 0020–0255

Zimmermann H-J (1986) Fuzzy sets, decision making, and expert systems. Kluwer, The Netherlands

Zimmermann H-J (1996) Fuzzy set theory—and its applications, 3rd edn. Kluwer, NorwellCrossRef

Title: Duality in fuzzy linear programming: a survey
Authors: Guido Schryen
Diana Hristova
Publication date: 01-01-2015
Publisher: Springer Berlin Heidelberg
Published in: OR Spectrum / Issue 1/2015
Print ISSN: 0171-6468
Electronic ISSN: 1436-6304
DOI: https://doi.org/10.1007/s00291-013-0355-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 1/2015

Acknowledgement to Referees

A graph partitioning strategy for solving large-scale crew scheduling problems

The dynamic replica placement problem with service levels in content delivery networks: a model and a simulated annealing heuristic

Urban public transit network optimization with flexible demand

Cyclic and non-cyclic crew rostering problems in public bus transit

Design and operation for an electric taxi fleet