MODIFIED SIGNOMIAL GEOMETRIC PROGRAMMING (MSGP) AND ITS APPLICATIONS

 

Wasim Akram Mandal

University of Kalyani, India

E-mail: wasim0018@gmail.com

 

Sahidul Islam

University of kalyani, India

E-mail: drsahidul.math@gmail.com

 

Submission: 25/07/2018

Accept: 29/08/2018

 

ABSTRACT

A "signomial" is a mathematical function, contains one or more independent variables. Richard J. Duffin and Elmor L. Peterson (1967) introduced the term "signomial". Signomial geometric programming (SGP) optimization technique often provides a much better mathematical result of real-world nonlinear optimization problems. In this research paper, we have proposed unconstrained and constrained signomial geometric programming (SGP) problem with positive or negative integral degree of difficulty. Here a modified form of signomial geometric programming (MSGP) has been developed and some theorems have been derived. Finally, these are illustrated by proper examples and applications.

 

Keywords: Polynomial; Constrained problem; Signomial function; Modified Signomial Geometric Programming

1.     INTRODUCTION

            Geometric programming (GP) method is a relatively new optimization method to solve a various types of non-linear programming problem. The idea of geometric programming technique was fast developed by Duffin, Peterson and Zener. Since 1960 ҆s geometric programming (GP) has been known and used in various field like as operations management, industrial engineering, structural problem etc..

            In the late 1960s and early 1970s the term “signomial” was introduced by Duffin and Peterson (1967) in their seminal joint work on general algebraic optimization. A recent introductory exposition is non-linear optimization problems. Although non-linear optimization problems with constraints and/or objectives defined by signomials are normally harder to solve than those defined by only posynimials (because unlike posynomials, signomials are not guaranteed to be globally convex).

            A signomial optimization geometric programming technique often provides a much more accurate and better mathematical representation of real-world non-linear optimization problems.

            Passy and Wilde (1967) and Blau and Wilde (1969) generalized some of the prototype concepts and theorems in order to treat signomial geometric programming problems. In 1988 general type of signomial geometric programming has been done by Charnes and Cooper, who proposed methods for approximating signomial geometric programs with prototype geometric programs. Recently Islam and Roy (2005) has been demonstrated modified geometric programming problem and its application.

            A “signomial” is a mathematical (algebraic) function of one or more independent function. “signomial” is one of the most easily thought of as an algebraic extension of multi-dimensional polynomials (posynomial) an extension that permits exponents to be arbitrary real numbers (rather than just non negative integers) while requiring the independent variables to be strictly positive .

            In this research paper we propose unconstrained / constrained signomial geometric programming (SGP) and modified form of signomial geometric programming (SGP) problem with positive or negative integral of difficulty. Modified form of signomial geometric programming has been demonstrated and some theorems have been presented here. Finally, these are illustrated by proper real type of numerical examples and applications.   

2.     SOME BASIC CONCEPTS

Monomial: The word ‘monomial’ comes from the Latin word, mono meaning only one and mial meaning term. So a monomial is an “expression in algebra that contains only one term”.  The term monomial as used in the context of geometric programming (GP) technique is similar to, but differs from the standard definition of monomial used in algebra. In mathematics a monomial can be a constant, a variable or the product of one or more constant and variables but the exponent of variables cannot have a negative or fractional. Throughout the exponent can be any real number, including fractional and negative.

            So if , , . ……………..,  denote n real positive variable, then a real valued function f of x, in the form

          F(x)

where c > 0 and is called monomial algebraic function.

Polynomial: The word ‘polynomial’ comes from the Latin word, polynomeaning many and mial meaning term. So a polynomial is an “expression in algebra that contains many terms i.e., many monomial”.

             So sum of one or more monomial function, i.e., any function of the form

          F(x)

is called polynomial function or in simply called polynomial.

Posynomial: If coefficients , then a polynomial function is called a posynomial function.

So sum of one or more monomials, i.e., any function of the form

          F(x)

where , is called posynomial function or simply posynomial.

Note 1: The term posynomial function is mean to suggest a combination of positive and polynomial function. So Positive Polynomial

Signomial: A signomial function is differs from a posynomial function in that the coefficient need not be positive. Let X is a vector of real and positive numbers.

     X

Then the signomial function has the form as follows

 

Where    absolute value of coefficient,

 sign of coefficient (+1 or ).

            Signomial functions are closed under addition, subtraction, multi-plication and scaling of basic mathematical operation.

Example 1: 

For this signomial

Table 1: Compare between monomial, polynomial and posynomial:

            Monomial

             Polynomial

Posynomial

1) Contains only one term.

2) Addition of two or more monomials is not monomial.

3) Subtraction of two or more monomials is not monomial.

4) Multiplication of two or more monomials is a monomial.

5) Division of a monomial by one or more other monomials is a monomial.

6) A monomial is of the form,

F(x)  c> 0.

7) Examples: 5, 2x, .

1) Contains one or more term.

2) Addition of two or more polynomials is polynomial.

3) Subtraction of two or more polynomials is a polynomial.

4) Multiplication of two or more polynomials is a polynomial.

5) Division of a polynomial by one or more other monomials is a polynomial.

6) A polynomial is of the form,

F(x)

7) Examples: 5, 2x+y, .

1) Contains one or more term.

2) Addition of two or more posynomials is posynomial.

3) Subtraction of two or more posynomials is not posynomial.

4) Multiplication of two or more posynomials is a posynomial.

5) Division of a posynomial by one or more other monomials is a posynomial.

6) A posynomial is of the form,

F(x)

.

7) Examples: 5, 2x+y, .

 

3.     UNCONSTRAINED PROBLEM

3.1.        Signomial geometric programming (SGP) problem:

3.1.1.   Primal program:

            A primal unconstrained signomial geometric programming (SGP) problem is of the following form

   Minimize                                                   (3.1)

   Subject to      j  1, 2,……,m.

   Where 

            Here  is absolute value of coefficient,  sign of coefficient (+1 or ) and  be any real number. It is unconstrained signomial geometric programming (SGP) problem with the degree of difficulty (DD)

3.1.2.   Dual program:

            The dual geometric programming (DGP) problem of the given primal geometric programming (GP) problem is

 Maximize                                                   (3.2)

 Subject to  ,                  

                    ,                    

 

Case I: If n>m+1, (i.e. DD>0) then the dual program (DP) presents a system of linear equations for the dual variables. Here the number of dual variables is more than the number of linear equations. Here more optimal solutions of dual variable vector exist. In order to find an optimal solution of the given dual program (DP), we need to use some algorithmic techniques.

Case II: If n< m+1, (i.e. DD<0) then the dual program (DP) presents a system of linear equations for the dual variables. Here the number of dual variables is less than the number of linear equations. In this special case generally no solution vector exists for the dual variables. However, using some special types of techniques that is Least Square (LS) or Min-Max (MM) method one can get an approximate solution for this type of problem.

            Moreover from the primal-dual relation,

                   .                                           (3.3)

            Taking logarithms in (3.3), T0 log-linear simultaneous equations are transformed as

                      ,    (i =1,2,….,n).         (3.4)

It is a system ofn linear equations in tj (=log xj) for j=1,2,...,m.

Note 2: A Weak Duality theorem say that  for any primal-feasible x and dual-feasible  but this inequality is not true of the pseudo-dual signomial geometric programming (SGP) optimization problem.

Corollary 1: When the values of  are 1, then a signomial geometric programming (SGP) problem transform to ordinary geometric programming (GP) problem.

3.1.3. Theorem: When the values of   are 1, then (x) ≥ (δ) (Primal Dual Inequality).

Proof

            The expression for (x) can be written as

(x) = .

            Here the weights are  and positive terms are 

 , ……… ,   .

            Now applying the AM GM inequality, we get

 ( )

 Or                                  [

 Or       

 Or         

                        =

                        = (δ)                       

i.e.,           (x) ≥ (δ).

            This completes the proof.                         

Example (Unconstrained SGP problem) 2:

     Min Z(x, y)  10x

     Subject to   x, y > 0.

Solution:

Assume

            Corresponding dual of the primal geometric problem is,

     Maximize v(δ)                                            (3.5)

     Subject to   ,

                        ,

                        ,                                                             (3.6)

                        ,

            From (6) . Putting the value of and  in (3.5), the corresponding optimal dual value is (δ)  7.071.

 So for primal optimal decision variables, the following equations found

            1

           

          

            Taking logarithm of each side yields equations which are linear in the logarithms of decision the primal variables

           In 10 + In x  In 7.071

           In 5 + log x + log x  In 3.535                                                 (3.7)

           In 10 + 3log x log y  In 3.535.

            From (3.7), optimal solutions are

           x

            y

And corresponding optimum value, Z(x, y)

3.2.        Modified signomial GP problem:

3.2.1.   Primal program:

            A primal unconstrained modified signomial geometric programming (SGP) problem is of the form

   Minimize    

   Subject to      j  1, 2,……,m.

            Where                                             (3.8)

            Here  is absolute value of coefficient,  sign of coefficient (+1 or ) and  be any real number. It is unconstrained signomial MGP problem with the degree of difficulty (DD)

3.2.2.   Dual program:

            Dual geometric program (GP) problem of the given primal GP problem is

   Maximize                                                                  (3.9)

   Subject to  ,   

                     ,          

                    

Case I: If nk nm+n, (i.e. DD>0) then the dual program (DP) presents a system of linear equations for the dual variables. Here the number of dual variables is greater than the number of linear equations. More solutions of dual variable vector exist. In order to find an optimal solution of dual program (DP), we need to use some algorithmic methods.

Case II: If nk<nm+n, (i.e. DD<0) then the dual program (DP) presents a system of linear equations for the dual variables. Here the number of dual variables is less than the number of linear equations. In this case generally no solution vector exists for the dual variables. However, using the Least Square (LS) or the Min-Max (MM) technique one can get an approximate solution for this non-linear system.

            Furthermore the primal-dual relation is

, .                (3.10)

Note 3: A Weak Duality theorem would say that for any primal-feasible x and dual-feasible  but this is not true of the pseudo-dual signomial geometric programming (SGP) problem.

Corollary 2: When the values of  is 1, then a modified signomial geometric programming (MSGP) problem transform to ordinary modified geometric programming problem.

3.2.3. Theorem: When  is 1, then ( ) ≥ n  (Primal- Dual Inequality).

Proof

            The expression for ( )  can be written as 

( ) = .

Here the weights are  and positive terms are   

 , ……… ,   .

Now applying AM-GM inequality, we get

 

Or     

Or              [

 

 

 Or    

                    =

i.e.,    ( ) ≥ n .       

This completes the proof. 

Example (Unconstrained MSGP problem) 3:

      Min Z(x)  10

      Subject to    , , 0.

Solution:

Assume

            Corresponding dual of the given primal problem is

     Maximize (δ)                        (3.11)

     Subject to    ,

                         ,

                         ,                                                                              (3.12)

                         ,

                         ,

                         ,

                         , ,

            From (3.12) . Putting the value of  and  in (3.11), the corresponding optimal dual value i.e.,

          (δ)

                 

So for primal decision variables, the following equations found

              1  

              

               

              1

                                                           (3.13)

             

From (3.13), optimal solutions are

              

              

Corresponding optimal value is

              Z(x)

4.     CONSTRAINED PROBLEM

4.1.        Signomial geometric programming (SGP) problem:

4.1.1.   Primal program:

            A constrained primal signomial geometric programming (SGP) programming problem is of the form

   Minimize  

   Subject to  ,   k  1, 2, ……,p

                       j  1, 2,……,m.

            Where  , and                              (4.1)

4.1.2.   Dual program:

            Dual geometric program (GP) problem of the given primal signomial program (SGP) problem is

 Maximize                                                        (4.2)

 Subject to  ,                   k

                   ,                    

                    , 

Case I: If n m+1, (i.e. DD >0), then the dual signomial program presents a system of linear equations for the dual variables. A solution vector exists for the dual signomial variables.

Case II: If n< m+1, (i.e. DD <0), In this case generally no solution vector exists for the dual signomial variables. But using Least the Square (LS) or the Min-Max (MM) method one can get an approximate solution for this system.

Furthermore the primal-dual relation is

            for i

And     for i , k                                             (4.3)

Example (Constrained SGP problem) 4:

    Min (x,y,z)

      Subject to 

                           x, y, z > 0.

Solution:

 Assume

            Corresponding dual of the given primal is

       Maximize v(δ)                                 (4.4)

       Subject to     ,

                        ,

                           ,

                           ,                                                                     (4.5)

                          

                           ,

            From (4.5), ,  and  , but

 i.e., 

            Corresponding dual of primal is

     Maximize v(δ)                  (4.6)

        Subject to     ,

                          ,

                            ,

                            ,

                                                                                          (4.7)

                            ,

            From (4.7), , , . Putting the values of and  in (4.6) the corresponding optimal dual value

 i.e., (δ)  0.349.

From the primal-dual relation

      

      

     

      

            Taking logarithm of each side yields equations which are linear in the logarithms of the primal variables

        In 2 + 2In y + 4Inz  In

         In 5 + 2log x  In

         In 2 + 2log x  2log y  In 3                                                            (4.8)

      In y + In z  In 4.

From (4.8), optimal solutions are

         

    4.2. Modified Signomial geometric programming (MSGP) programming:

4.1.3.   Primal program:

            A primal modified signomial GP programming problem is of the form

   Minimize  

   Subject to  ,   k  1, 2, ……,p

                       j  1, 2,……,m.

 Where  ,                       (4.9)

4.1.4.   Dual program:

            Dual GP problem of the given primal MSGP problem is

 Maximize                                                    (4.10)

 Subject to  ,                  

                   ,                  

                   ,                  k

                   , 

Case I: If nk m+n, (i.e. DD >0), then the dual modified signomial program presents a system of linear equations for the dual variables. A solution vector exists for the dual signomial variables.

Case II: If nk<nm+n, (i.e. DD <0), In this case generally no solution vector exists for the dual signomial variables. But using the Least Square (LS) or the Min-Max (MM) method one can get an approximate solution for this system.

Furthermore from the primal-dual relation

           , for i     

and

             for i , k                                        (4.11)

Example (Constrained MSGP problem) 5:

     Min Z(x)  10

     Subject to  

                        , , 0.

Sol.

            Taking

Here the primal problem is

      Min Z(x)  10

      Subject to  

                         , , 0.

And corresponding dual problem is

     (4.12)

Subject to

     

     

      

    

                                                                                          (4.13)

     

Approximate solutions of this system of linear equations are

          

  And 

Then the objective function is

  

                                                                                                                    (4.14)

And from primal-dual relation following system of equations gives optimal primal variables

        10

        

         

         

         

         

Solving the system of equations, optimal solutions are

         

          

and the value of objective function is Z(x)

5.     APPLICATION

5.1.        Problem (Unconstrained SGP):

            The demand (d) of an item is uniform at the rate of 10 units per month. The set-up cost ( of a production run is Rs 20, and the inventory holding cost (  is Rs 50 per item per month. If the shortages cost (  is Rs 50 per item per month, determine economic lot size (q) for one run also determine what is inventory level (s) at the beginning of each month.

            As stated, this problem can be formulated as the unconstrained SGP problem

            It is unconstrained signomial geometric programming problem. The optimal solution is  and minimum average total cost is Rs 100/month.

5.2.        Problem (Unconstrained MSGP):

            In a multi-item (n items) inventory model, demand of an item is uniform at the rate of  units per month. The set-up cost of a production run is Rs , and the inventory holding cost is Rs per item per month. If the shortages cost is Rs  per item per month, determine economic lot size ( ) for one run also determine what is inventory level ( ) at the beginning of each month.

            As stated, this problem can be formulated as the unconstrained MSGP problem

            In particular here we assume n  and input data of this problem is given below

i

1

10

20

50

50

2

15

10

125

25

 

            And the out-put value is

i

1

4.00

2.00

177.45

2

3.87

1.94

 

5.3.        Problem (Constrained SGP):

            A constrained signomial geometric programming (SGP) problem is of the following form

            It is constrained signomial geometric programming problem. The optimal solution is and minimum value is 38.322.

5.4.        Problem (Constrained SMGP):

            A constrained modified signomial geometric programming (MSGP) problem is of the following form

            It is constrained MSGP problem. In particular here we assume n  and input data of this problem is given below

i

1

-2

1

5

-2

2

-1

1

3

            And the out-put value is

i

1

0.408

0.004

18.57

16.00

69.09

2

0.716

0.006

7.663

16.00

 

6.     CONCLUSION:

            In this paper we have developed signomial geometric programming (SGP) problem with positive or negative integral degree of difficulty. Modified form of signomial geometric programming technique has been demonstrated and some theorems have been derived here. In this research paper we have developed the technique only in a crisp environment but in future research of uncertainty in fuzzy non-linear programming (NLP) model, by using different type of fuzzy numbers (fuzzy coefficients, random fuzzy number, generalized fuzzy number) such as random fuzzy number, institutional fuzzy number or adaptive fuzzy demand rate analytically should be more challenging and interesting.

REFERENCES:

WILDE, B. (1969) Generalized polynomial programming, Can. J. Chem. Eng., n. 47, p. 317–326. doi: 10.1002/cjce.5450470401.

CARLSSON, C.; FULLER, R. (2001) On Possibilistic Mean Value and Variance of Fuzzy Numbers, Fuzzy Sets and  Systems, n. 122, p. 315-326.

CARLSSON, C.; FULLER, R. (2002) Fuzzy Reasoning in Decision Making and Optimization, Physics-Verlag.

CLARK, A. J. (1992) An informal survey of multy-echelon inventory theory, Naval Research Logistics Quarterly, n. 19, p. 621-650.

DUTTA, D.; KUMAR, P. (2012) Fuzzy inventory without shortages using trapezoidal fuzzy number with sensitivity analysis, IOSR Journal of Mathematics, v. 4, n. 3, p. 32-37.

DUTTA, D.; RAO, J. R.; TIWARY, R. N. (1993) Effect of tolerance in fuzzy linear fractional programming, Fuzzy Sets and Systems, n. 55, p. 133-142.

DUFFIN, R. J.; PETERSON, E. L. (1969) Duality Theory for Geometric Programming, SIAM Jour. Of App Math., n. 14, p. 1307-1349.

DUFFIN, R. J.; PETERSON, E. L.; ZENER, C. (1967) Geometric Programming-Theory and Applications, John Wiley, New York, 1967.

HAMACHER, L. H.; ZIMMERMANN, H. J. (1978) Sensitivity Analysis in fuzzy linear Programming,  Fuzzy Sets and Systems, n. 1, p. 269-281.

ISLAM, S.; ROYT, K. (2006) A fuzzy EPQ model with flexibility and reliability consideration and demand depended unit Production cost under a space constraint: A fuzzy geometric programming approach, Applied Mathematics and Computation, v. 176, n. 2, p. 531-544.

ISLAM, S.; ROY, T. K. (2010) Multi-Objective Geometric-Programming Problem and its Application. Yugoslav Journal of Operations Research, n. 20, p. 213-227.

KOTB A. M.; HLAA. A.; FERGANCY (2011) Multi-item EOQ model with both demand-depended unit cost and varying Leadtime via Geometric Programming, Applied Mathematics, n. 2, p. 551-555.

KHUN, H. W.; TUCKER, A. W. (1951) Non-linear programming, proceeding second Berkeley symposium Mathematical Statistic and probability (ed) Nyman, J. University of California press, p. 481-492.

LIANG, Y.; ZHOU, F. (2011) A two warehouse inventory model for deteriorating items under conditionally permissible delay in Payment, Applied Mathematical Modeling, n. 35, p. 2221-2231

LIU, S. T. (2006) Posynomial Geometric-Programming with interval exponents and co-efficients, Europian Journal of Operations Research, v. 168, n. 2, p. 345-353.

MAITY, M. K. (2008) Fuzzy inventory model with two ware house under possibility measure in fuzzy goal, European Journal Operation Research, v. 188, p. 746-774.

MANDAL, W. A.; ISLAM, S. (2016) Fuzzy Inventory Model for Deteriorating Items, with Time Depended Demand, Shortages, and Fully Backlogging, Pak.j.stat.oper.res., v. XII, n.1, p. 101-109.

MANDAL, W. A.; ISLAM, S. (2016) A Fuzzy E.O.Q Model with Cost of Interest, Time DependedHolding Cost, With-out Shortages under a Space Constraint: A Fuzzy Geometric Programming and Non-Linear Programming Approach. International Journal of Research on Social and Natural Sciences, v. I, n. 1, p. 134-147.

PASEKA, A.; APPADOO, S. S.; THAVANESWARAN, A. (2011) Possibilistic moment generating functions, Applied Mathematics Letters, v. 24, n. 5, p. 630-635.

PASSY, U.; WILDE, D. J. (1967) Generalized Polynomial Optimization, SIAM Jour. Appli. Math., n. 15, p. 134-156.

PASSY, U.; WILDE, D. J. (1968) A Geometric Programming Algorithm for Solving Chemical Equilibrium, Jour. Appli. Math., n. 16, p. 363-373.