Linear Programming is a mathematical technique used to allocate scarce resources in an optimal way to minimize the costs or to maximize the revenue and thus, Linear Programming helps the farmers, managers, entrepreneurs, scientists and planners to solve the complex field problems to find the best possible solutions. Although Linear Programming is an easier technique, the real-world problems are very complex that the objective function and/or constraint equations are not always linear and hence, finding an optimal solution using Linear Programming is not feasible. In such cases, Non-Linear Programming techniques are used to provide reasonably realistic representations of real-world problems, so as to find optimal solutions for such problems. In spite of many advantages, Non-Linear Programming techniques are difficult to learn and understand. Also, reading materials on Non-Linear Programming techniques are only less than adequate to describe the techniques in simple ways that can better be understood by the potential users. This book on “Non-Linear Programming: An Introduction” has been written in an easy and uncomplicated way that can facilitate effortless learning of the techniques, by being able to help the readers to have a better understanding of how Non-Linear Programming can help to formulate a real world problem as a Non-Linear Programming problem and to solve the same effectively and interpret the results clearly.
Dr. M.Thirunavukkarasu is currently the Professor and Head, Dept. of Livestock Business Management, Madras Veterinary College, Tamil Nadu Veterinary and Animal Sciences University (TANUVAS), Chennai, Tamil Nadu (India). He graduated from Madras Veterinary College in the year 1986, did his post-graduation in Agricultural Economics from Tamil Nadu Agricultural University (1987-90), Coimbatore and Doctorate in Animal Husbandry Economics (1993-96) at TANUVAS, Chennai. He joined the TANUVAS, Chennai in 1989 as Assistant Professor and was promoted as Associate Professor in 1997. He was elevated as the Professor of Animal Husbandry Statistics and Computer Applications in 2000. Considering his eminent achievements in education, research, extension, administration and institution building, he was then raised up as the Professor (Higher Grade) in 2011. His laudable accomplishments have also enabled him to hold the coveted posts of the Controller of Examinations, TANUVAS during 2012-15 and the Dean, Veterinary College and Research Institute, Tirunelveli (2016-18), besides holding the post of the Registrar, TANUVAS for a brief period from April to August, 2018. He underwent advanced training programmes on Livestock Economics and Planning and Quantitative Methods in Livestock Health and Production at the University of Reading, UK, in 1998 and training on Instructional Technology–eLearning guidelines, standards and protocols at Michigan State University, USA in 2009. He has also visited Uganda and Malawi for research and consultancy works. He has published more than 110 research papers in International and National journals, organised 3 presented more than 65 research papers (including 5 lead/invited papers) in International and National Conferences/ Seminars, edited 11 books and authored 16 books, teaching manuals and booklets. He has been bestowed with 19 awards including the Best PG Student Award, Best Teacher Award. Best Scientist Award and Lifetime Achievement Award in his professional career spanning more than 32 years. He has implemented 21 Research Projects, funded by National and International agencies including ICAR, NAIP, FAO, USDA, GoI, GoTN, AWBI, etc. He has started four new post-graduate programmes – MVSc, MFSc and MSc in Biostatistics (2011-12) and PG Diploma in Animal Health Economics (2019-20). He has contributed significantly in the areas of Livestock Economics, Animal Health Economics, Bio-statistics, IT Applications in Animal Sciences and Development of e-Courses for Veterinary Education. Aboutthe Author v We, in real life, face a number of situations in which we need to make some decisions to optimize our output. The expected output may be income, revenue, pleasure and any other outcome that we may wish to achieve. It means that the key problem in our life is planning to allocate our resources which are already limited (or scarce) to get the best possible output/outcome. It is more so in production activities in a farm, a firm, a business or an entrepreneurial activity. On one hand, the farmers or the business managers aim to maximize their output, income, or profit and on the other, they intend to minimize the cost of production, ultimately aspiring to achieve the best possible outcome with the available scarce resources. Linear programming is a method of allocating limited resources to harvest the best output. This tool is now being used successfully as a decision-making aid in many production activities, industries and service organizations. Programming is a mathematical technique to allocate scarce resources - men, materials, machines and money - in the best possible (optimal) way, so that the costs are minimized or the outputs are maximized. Linear programming helps the farmers, managers, entrepreneurs, scientists and planners to solve these complex problems so as to find the best solutions. Though finding optimal solutions for field problems using Linear Programming tool is easier, mostly and unfortunately, the real-world problems are so complex that the relationships between the decision variables are not always linear and hence, finding the best possible answers using Linear Programming is not feasible always. Non-Linear Programming technique, however, can provide reasonably realistic representations of many real-world problems and can help to find optimal solutions for such problems. In spite of their inherent advantages, use of Non-Linear programming techniques are not that extensive by the planners for the reasons that the techniques themselves are difficult to learn and understand and that there are no adequate reading materials which explain the techniques in simple ways that can better be understood by the potential users. Hence, this book on “Non-Linear Programming: An Introduction” has been written in an easy and uncomplicated way that can facilitate effortless learning of the techniques. I am sure that this book will help the Preface vii readers to have a better understanding of how Non-Linear Programming can help to formulate a real world problem as a Non-linear Programming problem and to solve the same effectively and interpret the results clearly.
1. Linear Programming – A Recap ................................................... 1
1.1 History ............................................................................................ 1
1.2 Applications ................................................................................... 2
1.3 Advantages of Linear Programming......................................... 2
1.4 Disadvantages of Linear Programming .................................... 3
1.5 Components of a Linear Programming Problem .................... 3
1.6 Formulating a Linear Programming Problem – An Example ............................................... 4
1.7 General form of the Linear Programming Problem ............... 6
1.8 Solving Linear Programming Problems .................................... 7
1.8.1 Steps in Graphical Method of finding solution to Linear Programming Problem ....................... 8
1.8.2 Finding the best possible value (Optimal solution point) for Objective Function ....... 10
1.8.3 Simplex method of solution of Linear Programming Problems ............................... 15
1.8.4 Properties or characteristics of simplex procedure... 17
1.8.5 Properties of the Tableau ............................ 19
1.8.6 Initial Basic Feasible Solution Tableau ........................ 20
1.8.7 Criterion for selection of non-basic variable to become basic variable............................... 20
1.9 Interpretation of Results Obtained Through Simplex Algorithm ................................ 24
1.10 Minimization Problems ................................. 25
1.11 Duality in Linear Programming ............................................... 28
2. Non-Linear Programming ............................................................ 35
2.1 Example – A Case of Water Resources Planning .................. 37
2.2 Problem Classification................................................................ 37
2.3 Substitution Method................................................................... 39
2.4 Elimination by Addition Method ............................................ 40
2.5 Using Substitution and Elimination Methods for Optimization of Non-Linear Equations ................... 41
2.6 Method of Lagrange Multipliers .............................................. 44
2.7 Meaning of Lagrange Multiplier (l)........................................ 46
2.8 Karush-Kuhn-Tucker Theory for Solving Non-Linear Programming ............................. 47
3. Quadratic Programming ............................................................... 49
3.1 Applications of Quadratic Functions ....................................... 50
3.2 Quadratic Programming Problems .......................................... 51
3.3 General Format of Quadratic Programming Optimization Problem ............................ 51
3.4 Problem Formulation ................................................................. 52
3.5 Solution Strategies ...................................................................... 53
3.6 Numerical Example .................................................................... 53
3.7 Other Applications ...................................................................... 55
3.8 Solving Quadratic Programming Problems............................ 56
3.9 Different Forms of Quadratic Function .................................. 57
3.10 Graphing Quadratic Function ................................................... 59
4. Dynamic Programming ................................................................. 61
4.1 Recursion ...................................................................................... 61
4.2 How Dynamic Programming is Efficient? .............................. 62
4.3 Basic Concepts ............................................................................. 62
4.3.1 Tabulation vs Memoization ............................................ 62
4.3.2 Optimal Substructure Property ...................................... 64
4.4 How to solve a DP Problem? .................................................... 65
4.4.1 Steps to solve a DP problem ........................................... 65
4.4.2 Do tabulation (memoization) ......................................... 67
4.5 Solving DP Problems using FAST Method............................. 68
4.6 Bellman’s Principle of Optimality ............................................ 69
4.7 Issues/Difficulties in DP ............................................................ 70
5. Integer Programming .................................................................... 73
5.1 Applications ................................................................................. 73
5.2 Capital budgeting – An example of integer programme ..... 75
5.3 Solving IP ..................................................................................... 77
5.4 General purpose optimal solution algorithm......................... 78
5.3.1 Enumeration ...................................................................... 78
5.3.2 Branch and bound (tree search)..................................... 79
5.5 General purpose heuristic solution algorithms ..................... 82
5.6 Special purpose optimal solution algorithms ......................... 82
5.7 Special purpose heuristic solution algorithms ....................... 83
6. Separable Programming ............................................................... 85
6.1 General Format of Separable Programming Optimization Problem .......... 85
6.2 Summary....................................................................................... 90
6.3 Example for Finding Solution ................................................... 91
6.4 Non-Linear Programming Example ........................................ 93
7. Game Theory................................................................................... 97
7.1 Importance of Game Theory..................................................... 98
7.2 Terms used in Game Theory .................................................... 98
7.3 Principles of Game Theory........................................................ 99
7.4 Essential Features of Game Theory......................................... 99
7.5 Game Theory Framework ......................................................... 99
7.6 Applications of Game Theory................................................. 100
7.7 Theoretical Framework of Game Theory............................. 100
7.8 Components of a Game ........................................................... 104
7.9 Examples of Game Theory ...................................................... 105
7.10 Types of Game Strategy .......................................................... 107
7.11 Nash Equilibrium ..................................................................... 109
7.12 Uses of Game Theory .............................................................. 109
7.13 Linear Programming Solution for Matrix Games ............... 110
7.14 Limitations of Game Theory.................................................. 112
8. Simulation Techniques ...............................................................113
8.1 Meaning of Simulation .......................................................113
8.2 How Simulation Works? ....................................................113
8.3 Advantages of Simulation..................................................113
8.4 Limitations of Simulation ...................................................115
8.5 Types of Simulation .............................................................115
8.6 Examples of Simulation ......................................................116
8.7 Simulation Techniques and Components Required for Simulation ..................................120
8.8 Modelling ..............................................................................120
8.9 Techniques in Simulation Model Design .........................121
8.10 Techniques in Execution of Simulation Models .............124
8.11 Automobile Manufacturing Model – An Example of Simulation ........................125
References and Resources for Further Reading ..................12
