Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2s (2024) 1 https://internationalpubls.com A Methodology for Solving Fuzzy Linear Programming Problem as a Fuzzy Linear Complementarity Problem Jenifer D H1, R. Irene Hepzibah 2 1& 2 PG & Research Department of Mathematics,T.B.M.L. College, Porayar, Affiliated to Annamalai University Tamil Nadu, India. E-mail:1jenifer808282@gmail.com, 2ireneraj74@gmail.com Article History: Received: 20-02-2024 Revised: 22-04-2024 Accepted: 05-05-2024 Abstract: In this paper, the linear complementarity problem with Fuzzy parameters is discussed. The Linear Programming Problem can be transformed into a Linear Complementarity Problem. The Maximum Index method is used to solve the converted Linear programming problem. The maximum index method has been introduced as a potential approach for identifying a complementarity feasible solution to the Linear Complementarity Problem. The fuzzy arithmetic operations are utilized for the triangular fuzzy numbers. A real-life example has been provided to demonstrate the suggested approach. Keywords: Linear Programming Problem; Linear complementarity problem; Fuzzy Linear Complementarity Problem; Fuzzy Sets; Triangular fuzzy numbers; Maximum Index method. 1. Introduction Linear programming [15] is concerned with optimizing a function with a variable objective under the constraints of a set of linear equalities and inequalities. The objective function may pertain to earnings, expenses, capacity for production, or any other kind of effectiveness that has to be obtained in the most efficient or ideal way. Demand from the market, manufacturing procedures and equipment, space for storage, raw material availability, and other factors may all place constraints on the operation. Linear programming is a mathematical modeling technique that uses linear relationships to define requirements and achieve the best attainable result. It is a powerful tool for making decisions based on data that can increase efficiency and reduce costs. Bellman and Zadeh [1] proposed fuzzy decision- making. The LCP is one of the most commonly studied problems in mathematical programming and quadratic programming, and it has been studied and applied in a wide range of areas of operations research. In 1967, Robert L. Graves [17] put forth a principal pivoting method for LCPs. Cottle and Danzig [4] unified linear and quadratic programs, as well as bimatrix games. In 1968, Lemke et al, [2,10,16] proposed a complementarity pivoting algorithm to solve linear complementarity problems. “The LCP (q, M) of order n and q be a nx1 real vector, then LCP is to find real nx1 vector W, Z such that Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2s (2024) 2 https://internationalpubls.com A pair of variables, one of which must be zero. Each variable in the pair (Wj, Zj) is a complement to each other. This paper provides a real-life LPP that can be converted into a Linear Complementarity problem with the help of M.Laisin and J.E.Okeke [10]. K. G. Murty first proposed an Index method [9, 12]. With the reference of Nagoorgani et al, [13, 14] A Maximum Index method for solving fuzzy LCP with TFNs. The Fuzzy Complementary Pivot algorithm is carried out in this method without the use of artificial variables. This paper is structured as follows: The TFN and its associated arithmetic operations are covered in section 2. Section 3, describes the FLCP and its Algorithm along with the methods for solving it. Section 4 describes the conversion of an FLPP into an FLCP. Section 5, includes a real-life application that has been designed and developed to demonstrate how the proposed method works. Finally, section 6 concludes with some closing remarks. 2. Preliminaries This chapter presents some fundamental definitions and concepts that are extremely valuable in our work. 2.1 Triangular Fuzzy Number (TFN) A TFN Ã = (a1, a2, a3), the membership function is defined as 2.2 Arithmetic Operation of Triangular Fuzzy Number Using Function Principle: Let �̃� = (𝜌1, 𝜌2, 𝜌3) and ℭ̃ = (𝜚1, 𝜚2, 𝜚3) then [14], Addition: �̃�+ ℭ̃ = (𝜌 1 + 𝜚 1 , 𝜌 2 + 𝜚 2 , 𝜌 3 + 𝜚 3 ). Subtraction: �̃�- ℭ̃ = (𝜌 1 – 𝜚 1 , 𝜌 2 – 𝜚 2 , 𝜌 3 – 𝜚 3 ). Multiplication: �̃� × ℭ̃ = (min (𝜌 1 𝜚 1 , 𝜌 1 𝜚 3, 𝜌3 𝜚 1 , 𝜌 3 𝜚 3 ), 𝜌 2 𝜚 2, max (𝜌 1 𝜚 1 , 𝜌 1 𝜚 3, 𝜌3 𝜚 1 , 𝜌 3 𝜚 3 )). Division: �̃�/ ℭ̃ = ( 𝜌1 𝜚1 , 𝜌2 𝜚2 , 𝜌3 𝜚3 ). Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2s (2024) 3 https://internationalpubls.com 2.3 Defuzzification Let A ~ = (d1, d2, d3) be a TFN, then the fuzzy number can be defuzzified in the following manner P( A ~ ) = ( d1+ 4d2 + d3 ) / 6. 3. Fuzzy Linear Complementarity Problem (FLCP) “The parameters all the parameters are in fuzzy numbers. By replacing crisp parameters with fuzzy numbers, [8] The pair ( , )j jW Z is said to be a pair of fuzzy complementary variables”. 3.1 ALGORITHM: FUZZY LINEAR COMPLEMENTARITY PROBLEM Lemke [11] proposed a solution algorithm for Linear Complementarity problems. Murty [9, 12] suggested, using an Index method to solve LCPs. based on this concept, The Maximum Index method for solving the Fuzzy Linear Complementarity problem is developed here. Consider the FLCP (q ̃, M ̃) of order n, suppose the fuzzy matrix satisfies the conditions: There is a column vector with all strictly positive entries. Then a variant of the complementary pivot algorithm that uses no artificial variable can be applied on the FLCP (q ̃, M ̃). The original tableau for this version of the algorithm is: �̃� �̃� 𝐼 �̃� �̃� Initially set n=0, q0, M0 = q, M. If qn ≥ 0 then stop zn = 0 solves qn, Mn, that is w, z = (𝑞, 0) [13]. We assume that 𝑞 ̃ ≥ 0. Let r be such that 𝑀�̃� > 0. So, the column vector associated with �̃�𝑟 is strictly negative. The variable can play the equivalent role as the artificial variable The fuzzy complementary pivot algorithm, FLCP satisfies the condition and is known as an almost fuzzy complementary feasible basic vector. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2s (2024) 4 https://internationalpubls.com 4. Conversion of Linear Programming problem into Linear Complementarity problem.[8] A linear programming problem (LPP) can be expressed in the symmetric form (the primal problem, (Taha) [7]) as follows; Let A is a matrix of order m x n. If x/ ∈ ℝ𝑛, then the dual problem of (4.1) in symmetric form as follows; Maximize z = bTY Subject to ATY ≥ CT (4.2) Y ≥ 0 By the well-known duality theory of LPP, there exists a dual vector y/ ∈ ℝ𝑚 is an optimal solution to the problem (4.2). By introducing slack dual variable u ∈ ℝ𝑚 it follows that the constraint of (4.2) becomes; u – (ATY) = CT (4.3) We introduce the primal surplus variable v ∈ ℝ𝑛 then, the constraint of the problem (4.1) now follows; Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2s (2024) 5 https://internationalpubls.com v - AΧ = -b (4.4) We then combine the constraints of (4.3) and (4.4) in matrix form. ( 𝑢 . . 𝑣 ) - ( −𝐴𝑇Y . . 𝐴Χ ) = ( CT . . −𝑏 ) ⇒ ( 𝑢 . . 𝑣 ) - ( 0𝑋 − 𝐴𝑇𝑌 . . . 𝐴𝑋 − 0𝑌 ) = ( CT . . −𝑏 ) ( 𝑢 . . 𝑣 ) ≥ 0, ( 𝑋 . . 𝑌 ) ≥ 0 and ( 𝑢 . . 𝑣 ) 𝑇 ( 𝑋 . . 𝑌 ) = 0 ⇒ ( 𝑢 . . 𝑣 ) - ( 0 − 𝐴𝑇𝑌 . . . 𝐴𝑋 − 0 ) = ( CT . . −𝑏 ) (4.5) Conversely, ( 𝑢 . . 𝑣 ) 𝑇 ( 𝑋 . . 𝑌 ) = 0 together satisfy all the conditions of (4.5). Now considering all the vectors and matrices in (4.5) which are written in partitioned form as follows: W = ( 𝑢 . . 𝑣 ), z = ( 𝑋 . . 𝑌 ), M = ( 0 − 𝐴𝑇 . . . 𝐴𝑋 − 0) , q = ( 𝐶𝑇 . . −𝑏 ) (4.6) By solving this, we obtain a complementary feasible solution to the LCP. 5. Numerical example Delta produces both Indian and Western toilets from two raw materials M1 and M2. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2s (2024) 6 https://internationalpubls.com raw materials per ton of Availability(max/day) Indian toilets Western toilets (M1) 3 2 6 (M2) 2 1 2 Procurement cost per ton ($1000) 2 5 According to a market survey, the daily demand for Western toilets cannot be more than one ton higher than that for Indian toilets. Delta wants to determine the optimal (best) product mix of their products that minimizes the raw material procurement costs on a daily basis. The main purpose of the present research work was to apply a set of fuzzy coefficients to raw material components to reduce the error caused by the difficulty in accurately calculating each of the components. The fuzzy coefficients show the uncertainty and imprecision involved in evaluating every component while minimizing the overall raw material procurement costs. Let x1 be the number of units (tons) produced daily of Indian toilets. Let x2 be the number of units (tons) produced daily of Western toilets. Let Z be the daily total procurement cost, then Min Z = (1,2,3)Χ1 + (4,5,6)Χ2 Subject to the Constraints (2,3, 4)Χ1 + (1,2,3)Χ2 ≥ (5,6,7) (0,2,4)Χ1 + (0,1,2)Χ2 ≥ (0,2,4) Χ1, Χ2 ≥ 0 The constraints listed above could be written in a matrix form. [ (2,3,4) (1,2,3) (0,2,4) (0,1,2) ] [ 𝑥1 𝑥2 ] ≥ [ (5,6,7) (0,2,4) ] Here, A = [ (2,3,4) (1,2,3) (0,2,4) (0,1,2) ] , b = [ (5,6,7) (0,2,4) ] -AT = [ (−4,−3,−2) (−4,−2,0) (−3,−2,−1) (−3,−1,1) ] Objective constraints C = [(1,2,3) (4,5,6)] , CT = [ (1,2,3) (4,5,6) ] Now, letting M = [0 −𝐴𝑇 𝐴 0 ] , q = [𝐶 𝑇 −𝑏 ] Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2s (2024) 7 https://internationalpubls.com M = [ (0,0,0) (0,0,0) (−4,−3,−2) (−4,−2,0) (0,0,0) (0,0,0) (−3,−2,−1) (−3,−1,1) (2,3,4) (1,2,3) (0,0,0) (0,0,0) (0,2,4) (0,1,2) (0,0,0) (0,0,0) ] , q = [ (1,2,3) (4,5,6) (−7,−6,−5) (−4,−2,0) ] Therefore x1 = z1 and x2 = z2 will be an optimal solution to the given LPP. W - Mz = q, gives [ 𝑤1 𝑤2 𝑤3 𝑤4 ] - [ (0,0,0) (0,0,0) (−4,−3,−2) (−4,−2,0) (0,0,0) (0,0,0) (−3,−2,−1) (−3,−1,1) (2,3,4) (1,2,3) (0,0,0) (0,0,0) (0,2,4) (0,1,2) (0,0,0) (0,0,0) ] [ 𝑧1 𝑧2 𝑧3 𝑧4 ] = [ (1,2,3) (4,5,6) (−7,−6,−5) (−4,−2,0) ] The proposed approach is now applied to the fuzzy linear complementary problem, and the results are shown below. Bv W1 W2 W3 W4 Z1 Z2 Z3 Z4 q W1 (1,1,1) (0,0,0) (0,0,0) (0,0,0) (0,0,0) (0,0,0) (2,3,4) (1,2,3) (1,2,3) W2 (0,0,0) (1,1,1) (0,0,0) (0,0,0) (0,0,0) (0,0,0) (0,2,4) (0,1,2) (4,5,6) W3 (0,0,0) (0,0,0) (1,1,1) (0,0,0) (-4,-3,-2) (-4,-2,0) (0,0,0) (0,0,0) (-7,-6,-5) W4 (0,0,0) (0,0,0) (0,0,0) (1,1,1) (-3,-2,-1) (-3,-1,1) (0,0,0) (0,0,0) (−4,−2,0) W1 (1,1,1) (0,0,0) (0,0,0) (0,0,0) (0,0,0) (0,0,0) (2,3,4) (1,2,3) (1,2,3) W2 (0,0,0) (1,1,1) (0,0,0) (0,0,0) (0,0,0) (0,0,0) (0,2,4) (0,1,2) (4,5,6) W3 (0,0,0) (0,0,0) (1,1,1) (-2,-1.5,-1.3) (-0.7,0,2) (-2,-0.5,2) (0,0,0) (0,0,0) (-5,-3,1) Z1 (0,0,0) (0,0,0) (0,0,0) (-1,-0.5,-0.3) (1,1,1) (-1,0.5,1) (0,0,0) (0,0,0) (0,1,1.3) W1 (1,1,1) (0,0,0) (0,0,0) (0,0,0) (0,0,0) (0,0,0) (2,3,4) (1,2,3) (1,2,3) W2 (0,0,0) (1,1,1) (0,0,0) (0,0,0) (0,0,0) (0,0,0) (0,2,4) (0,1,2) (4,5,6) W4 (0,0,0) (0,0,0) (-0.8,-0.7,-0.5) (1,1,1) (-1.5,0,0.4) (-1.5,0.3,1) (0,0,0) (0,0,0) (-0.7,2,2.5) Z1 (0,0,0) (0,0,0) (-0.5,-0.3,-0.2) (0,0,0) (0,1,1.4) (0,0.7,0) (0,0,0) (0,0,0) (0.8,2,2.5) (Table 5.1) The optimal solution of the FLCP in (Table 5.1) (W1, W2, W3, W4: Z1, Z2, Z3, Z4) = ((1,2,3),(4,5,6), (-0.7,2,2.5),(0,0,0) : (0.8,2,2.5),(0,0,0),(0,0,0),(0,0,0)). Conclusion This study proposes a maximum Index method for addressing an LCP using fuzzy parameters. By using this method, the outcome is unmistakable, the computation is easy and fast. At the same time, it obtains the same result. Despite the fact that we are focusing on linear programming, this can be easily Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2s (2024) 8 https://internationalpubls.com adaptable to non-linear and multi-objective programming by incorporating fuzzy coefficients and Interval numbers. References [1] Bellman, R.E., Zadeh, L.A., Decision making in a fuzzy environment, Management Science 17(1970) 141-164. [2] Bazaraa, M.S., Sherali, H.D, and Shetty. C.M., (1979) Nonlinear Programming: Theory and Algorithms, John Wiley and Sons, Newyork. [3] Chen, S.H., Hsieh, C.H., (1999) Graded Mean Integration representation of generalized fuzzy number, Journal of Chinese Fuzzy Systems 5(2), 1-7. [4] Cottle, R.W., Dantzig, G.B., (1968) Complementarity pivot theory of mathematical programming, Linear algebra and its Applications 1, 103-125. [5] De Schutter.B, Heemels. W.P.M.H, Bemporad, A., (2002) On the equivalence of linear complementarity problems, Operations research letters, Elsevier, 30, 211-222. [6] Dubois, D., and Prade, H., (1978) Operation of Fuzzy Numbers, Internat. J.Systems Sci. 9(6), 613-626. [7] Hamdy. A. Taha, (2006) Operations Research: An introduction, eighth edition, Prentice – hall of India Private Ltd, Delhi. [8] Irene Hepzibah.R., (2021) An Algorithmic approach to fuzzy Linear Complementarity Problems, Lambert Academic Publishing, Germany. [9] Jenifer. D.H, Irene Hebzibah. R, (2023) On solving Fuzzy Linear Complementarity problem via Maximum index method, Referred Proceedings of 2nd International Conference on Emerging Trends in Science and Social science in Pattaya, Thailand. [10] Komei Fukuda, Makoto Namiki., (1994) On Extremal Behaviours of Murty’s Least Index Method, Mathematical Programming, 64, 365 – 370. [11] Laisin, M., Okeke, J.E., (2017)“Linear Complementarity problems applications to other programming problems”, COOU Journal of Physical Science 1(2), 147-156. [12] Lemke, C.E., (1968) “On complementary pivot theory”, Mathematics of the Decision Sciences, G.B.Danting and A.F.Veioff, Eds. [13] Murthy. K.G., (1997) “Linear Complementarity, Linear and Nonlinear Programming”, Internet Edition, http://www.personal.engin.umich.edu/~murty, 254-273. [14] Nagoorgani, A., Arun Kumar, C., (2012) An index method for solving the Linear Complementarity problem under fuzzy environment, Appl.Math.Sci. Vol 6, no 41-44, 2081- 2089. [15] Nagoor Gani. A, S.N. Mohamed Assarudeen, A New operation on Triangular fuzzy number for Solving linear programming problem, Applied Mathematical Sciences, Vol6, 2012, no.11, 525-532. [16] Premkumar Gupta., Hira, D.S., (2004) Operations Research, S. Chand & Company Ltd. [17] Richard W.Cottle, Jong-Shi Pang, Richard E.Stone., (2009) The Linear Complementarity Problem, SIAM. [18] Robert. L. Graves, (1967) A Principal pivoting simplex algorithm for linear and quadratic programming, operations research, 482-494. [19] Youssef Elfoutayeni, Mohamed Khaladi, (2012) Using vector divisions in solving the Linear Complementarity problem, Journal of Computational and Applied Mathematics, Elsevier, 236, 1919-1925.