[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Duality in fuzzy linear programming: a survey

  • Regular Article
  • Published:
OR Spectrum Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

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

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

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

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

  5. “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)

  6. 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.

  7. 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.

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

  9. 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.

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

References

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

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

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

    Google Scholar 

  • 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

    Google Scholar 

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

    Google Scholar 

  • 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.

    Google Scholar 

  • 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

    Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

  • 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–278

    Chapter  Google Scholar 

  • 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–341

    Chapter  Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  • 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

    Google Scholar 

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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • 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–744

    Article  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  • 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

    Google Scholar 

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

    Book  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • 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–216

    Article  Google Scholar 

  • 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

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

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

    Google Scholar 

  • 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–395

    Chapter  Google Scholar 

  • Ö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

    Google Scholar 

  • 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

    Google Scholar 

  • 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–392

    Article  Google Scholar 

  • 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–374

    Chapter  Google Scholar 

  • 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

    Google Scholar 

  • 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–429

    Chapter  Google Scholar 

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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

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

    Article  Google Scholar 

  • 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

    Google Scholar 

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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

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

    Google Scholar 

  • 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

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  • 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–251

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  • 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

    Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

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

    Book  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Management Information Systems, University of Regensburg, Universitätsstraße 31, 93053 , Regensburg, Germany

    Guido Schryen & Diana Hristova

Authors
  1. Guido Schryen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Diana Hristova
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Guido Schryen.

Appendices

Appendix A: Literature search

In our literature search, the following literature databases and journal TOCS (table of contents) were used:

  • Literature databases: INFORMS PubsOnLine, databases provided by INFORMS online (Conference Presentation Database, ACI Bibliographic Database), ACM Digital Library, IEEE Xplore, Business Source Premier, MLA International Bibliography, DigiBib of RWTH Aachen University. The logical search string was (“fuzzy” AND “duality”).

  • Journals: Operations Research, European Journal of Operational Research, Journal on Computing, IIE Transactions, OR Spectrum, INFORMS Journal on Computing, Annals of Operations Research, Mathematical Programming, Fuzzy Sets and Systems, Fuzzy Optimization and Decision Making, Fuzzy Information and Engineering

Appendix B: Fuzzy non-linear optimization

1.1 Appendix B.1 Approach of Sakawa and Yano (1994)

The papers by Lee et al. (1991) and Sakawa and Yano (1994) follow a similar idea, with the latter one being more extensive and more generally applicable. We, therefore, discuss only the second paper in this subsection. Sakawa and Yano (1994) consider large-scale multi-objective nonlinear programming problems with fuzzy goals. The primal problem in this paper looks as follows:

$$\begin{aligned} \begin{array}{l@{\quad }l} &{}\widetilde{\hbox {min}_x} f_1(x),...,\widetilde{\hbox {min}_x} f_k(x)\\ s.t. &{} g_i(x)\le 0, i=1,..,m \\ &{}h_j(x_j)\le 0,j=1,...,p \end{array} \end{aligned}$$
(Pb1)

The researchers pose additional assumptions on the functions \(f_s, g_i, h_j\). Note that this is a problem of class \(16\) in case the objectives and the constraints are linear and there is only one objective. \(\widetilde{\hbox {min}}\) is defined for each of the objective function \(f_s\) with the help of fuzzy goals. It is specified by the membership function \(\mu _s\), which is assumed to be invertible on the feasible region for \(x\).

To solve \((Pb1)\), the researchers apply the symmetric principle by Bellman and Zadeh (1970) and thus rewrite the problem as the following single-objective crisp optimization problem:

$$\begin{aligned} \begin{array}{l@{\quad }l} \min _{x,\alpha } &{}-\alpha \\ s.t.&{}f_s(x)-\mu _s^{-1}(\alpha )\le 0, s \in {1,...,k} \\ &{}g_i(x)\le 0, i=1,..,m \\ &{}x_j\in S_j,j=1,...,p\\ &{}\alpha \in [0,1] \end{array} \end{aligned}$$
(Pb1')

Here \(S_j:=\{x_j|h_j(x_j)\ge 0\}\) and \(S_j\) is assumed to be a compact and convex set.

The aim of the researchers is to use a dual decomposition method to cope with the high number of variables in \((Pb1')\), which makes the problem practically unsolvable for realistic applications. However, to apply the above method, the objective function needs to be strictly convex, which is not the case for \((Pb1')\). Sakawa and Yano (1994) thus approximate the problem \((Pb1')\) with

$$\begin{aligned} \begin{array}{l@{\quad }l} \min _{x,\alpha } &{}-\alpha +\rho \alpha ^2 \\ s.t.&{}f_s(x)-\mu _s^{-1}(\alpha )\le 0, s \in {1,...,k} \\ &{}g_i(x)\le 0, i=1,..,m \\ &{}x_j\in S_j,j=1,...,p\\ &{}\alpha \in [0,1], \end{array} \end{aligned}$$
(Pb1'')

where \(\rho \) is a very small, positive number.

The Lagrangian of \((Pb1'')\) is defined as

$$\begin{aligned} L(x,\alpha ,\lambda ,\pi )&= \sum _j\left( \sum _s\lambda _s f_{sj}(x_j)+\sum _i\pi _i g_{ij}(x_j)\right) \nonumber \\&+\left( -\alpha +\rho \alpha ^2-\sum _s\lambda _s\mu _s^{-1}(\alpha )\right) , \end{aligned}$$
(28)

where \(\lambda \) and \(\pi \) are vectors of the corresponding Lagrangian multipliers. Let be

$$\begin{aligned} \begin{array}{l@{\quad }l} w(\lambda ,\pi ):=&{}\min _{x,\alpha } L(x,\alpha ,\lambda ,\pi )\\ s.t.&{}x_j\in S_j,j=1,...,p\\ &{}\alpha \in [0,1]. \end{array} \end{aligned}$$
(29)

The crisp dual problem of \((Pb1'')\) is then

$$\begin{aligned} \begin{array}{l@{\quad }l} &{}\max _{\lambda ,\pi } w(\lambda ,\pi )\\ s.t. &{}(\lambda ,\pi )\in U, \end{array} \end{aligned}$$
(Db1)

where \(U=:\{\lambda >0, \pi >0: w(\lambda ,\pi ) \text{ exists }\}\).

Strong duality The optimal solution of problem \((Pb1'')\) coincides with the optimal solution of problem \((Db1)\).

To sum up, the idea of Sakawa and Yano (1994) is to solve the computationally complex primal problem using the simpler dual problem. The approach is quite interesting, but it concentrates mainly on solving the dual problem rather than developing a fuzzy duality theory. In addition, the dual problem is not a fuzzy problem anymore.

1.2 Appendix B.2 Approach of Wu (2003a)

Wu (2003a) considers a general fuzzy optimization problem. The primal problem in this paper is defined as

$$\begin{aligned} \begin{array}{l@{\quad }l} \widetilde{\min _x} &{}\widetilde{f(x)} \\ s.t. &{} \widetilde{g(x)} \preceq 0 \\ &{}x \in X. \end{array} \end{aligned}$$
(Pb2)

Here \(\widetilde{f}\) and \(\widetilde{g}\) are fuzzy-valued functions and \(X\) is a convex subset of the real vector space. Note that for the special case where \(\widetilde{f(x)}=\widetilde{c^t}x\) and \(\widetilde{g(x)}=\widetilde{A}x-\widetilde{b}\) the problem belongs to class \(31\). The researcher works with convex, normal fuzzy subsets of the real numbers with upper-semicontinuous membership functions and compact \(\alpha \)-cut for \(\alpha =0\).

They define \(\preceq \) using necessity indices as defined by Dubois and Prade (1983). Given two fuzzy numbers \(\widetilde{a}\) and \(\widetilde{b}\) with membership functions \(\mu _{\widetilde{a}}\) and \(\mu _{\widetilde{b}}\), the necessity index is defined as

$$\begin{aligned} \begin{array}{l@{\quad }l} &{}Nece(\widetilde{a}\succeq \widetilde{b})=\inf _u\sup _{v:u\ge v}\max \{1-\mu _{\widetilde{a}}(u),\mu _{\widetilde{b}}(v)\}\\ &{}Nece(\widetilde{a}\succ \widetilde{b})=1-\sup _{u\le v}\max \{\mu _{\widetilde{a}}(u), \mu _{\widetilde{b}}(v)\}. \end{array} \end{aligned}$$
(30)

Then it holds that

$$\begin{aligned} \widetilde{a}\succeq _{\alpha }\widetilde{b}\Leftrightarrow {\hbox {Nece}}(\widetilde{a}\succeq \widetilde{b})\ge \alpha \cap {\hbox {Nece}}(\widetilde{a}\succ \widetilde{b})\ge \alpha , \alpha \in [0,1]. \end{aligned}$$
(31)

The optimal solution for \((Pb2)\) is the feasible solution where the objective function has the lowest value according to the definition of the fuzzy comparison operator. Note that, due to the particular definition of \(\succeq _{\alpha }\), a feasible solution is always defined for a given \(\alpha \). Similarly, an optimal solution is also defined for a given \(\alpha '\), characterizing the comparison operator of the objective values, i.e. \({\widetilde{\hbox {min}^{\alpha '}}}\). Moreover, \(\alpha \) may differ from \(\alpha '\). Following the researcher, we call such a problem an \((\alpha ', \alpha )\)-\((Pb2)\) problem.

To define the dual problem to \((Pb2)\), the researcher follows the same approach as in crisp nonlinear programming. They define the fuzzy-valued Lagrangian function of an \((\alpha ', \alpha )\)-\((Pb2)\) problem as follows:

$$\begin{aligned} \widetilde{\phi (x,u)}=\widetilde{f(x)}+u^t\widetilde{g(x)}, x\in X, \end{aligned}$$
(32)

where \(u>0\). The fuzzy-valued Lagrangian dual function for a given \(\widetilde{\hbox {min}^{\beta }}\) is thus (here \(\beta \) may be equal to \(\alpha \), but does not have to)

$$\begin{aligned} \begin{array}{l} L_{\beta }(u)=\widetilde{\min ^{\beta }}_{x\in X}\widetilde{\phi (x,u)}. \end{array} \end{aligned}$$
(33)

The fuzzy dual problem is thus defined as

$$\begin{aligned} \begin{array}{l@{\quad }l} \widetilde{\max ^{\beta '}}_u &{}L_{\beta }(u)\\ s.t. &{}u\ge 0. \end{array} \end{aligned}$$
(Db2)

As the problem depends on \(\beta \) and \(\beta '\), we call it a \((\beta ', \beta )\)-\((Db2)\) problem. Note that \(\widetilde{\hbox {max}^{\beta '}}\) requires a definition that is slightly different from that of \(\widetilde{\hbox {min}^{\beta '}}\). The interested reader can consult reference Wu (2003a).

Weak duality (1) Let \(x\) and \(u\), respectively, be feasible solutions of an \((\alpha ', \alpha )\)-\((Pb2)\) and a \((\beta ', \alpha )\)-\((Db2)\) problem, where \(\beta '\) may also equal \(\alpha '\). Then, under some additional assumptions, it holds that

$$\begin{aligned} L_{\alpha }(u)\preceq _{\alpha }\widetilde{f(x)}, \alpha \ge 0.5. \end{aligned}$$
(34)

Weak duality (2) Let \(x^*\) and \(u^*\), respectively, be optimal solutions of an \((\alpha , \alpha )-(Pb2)\) and an \((\alpha , \alpha )-(Db2)\) problem. Then, under some assumptions, it holds that

$$\begin{aligned} L_{\alpha }(u^*)\preceq _{\alpha }\widetilde{f(x^*)}, \alpha \le 0.5. \end{aligned}$$
(35)

Note that weak duality (2) is a special case of weak duality (1). In addition, the researcher provides conditions for the optimality of two feasible solutions of the primal and the dual problem, respectively.

Strong duality Under some assumptions, the problems \((\alpha , \alpha )\)-\((Pb2)\) and \((\alpha , \alpha )\)-\((Db2)\) have no duality gap for \(\alpha \ge 0.5\).

To sum up, the main advantage of this approach is that it can be applied to a number of fuzzy optimization problems (satisfying the necessary assumptions) and it applies the ideas of crisp duality theory without defuzzifying the problems. However, the mathematical setup is rather complicated. In a follow-up paper Wu (2004), the researcher deals with the above problem by modifying the definition of fuzzy order and explaining the concepts with examples. Since the ideas in this paper are very similar to the one we discussed in this section, we omit its review here.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Schryen, G., Hristova, D. Duality in fuzzy linear programming: a survey. OR Spectrum 37, 1–48 (2015). https://doi.org/10.1007/s00291-013-0355-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00291-013-0355-2

Keywords

Search

Navigation