Description
Linear and integer programming are indispensable tools for optimizing complex systems and helping decisions across many application fields such as logistics, finance, manufacturing, and scheduling. This book introduces Linear Programming and Integer Programming with clear and straightforward explanations. It combines essential theory and practical applications, with focus on ease of understanding. Students in different fields like management, engineering, statistics, operations research, and economics can learn linear programming techniques through examples and coding exercises.
Dr James K C is currently working as a Professor in the Department of Statistics, Cochin University of Science and Technology. With over 34 years of experience, he has taught a wide range of courses spanning Engineering, Management, Statistics, and Data Science. In addition to his extensive teaching and research career, he has authored six books to date.
Contents
Acknowledgment
Preface
Common Mathematical Symbols in LP/IPxvi
Set Theory Symbols in Optimizationxvii
1. The Linear Programming Problem1
1.1. Introduction1
1.2. Linear Programming2
1.3. Linear Programming Problem: Components3
1.4. Steps in a Linear Programming Study4
1.5. Types of Linear Programming Models5
1.6. Advantages and Limitations7
1.7. Application Areas9
1.8. Recent LP/ILP Applications in Emerging Technologies11
1.9. Case Study: Optimizing Chilean Soccer League Scheduling with Operations Research(Alarcón et al., 2017)12
1.10. Case Study: ICRON Drives Supply Chain Optimization and Profitability at Vestel (https://www.gurobi.com/case_studies/icron-supply-chain-optimization/)13
1.11. Exercises14
1.12. References16
2. Formulation of Linear Programming Problem17
2.1. Introduction17
2.2. Formulation Example: A Product Mix Problem18
2.3. General Format19
2.4. Standard Form22
2.5. Canonical Form25
2.6. Common Assumptions of Linear Programming26
2.7. Formulation Examples26
2.8. Supply-demand Transportation Problem27
2.9. Diet Problem28
2.10. Cutting Stock Problem30
2.11. Production Planning Problem32
2.12. Employ Scheduling Problem35
2.13. Optimal Allocation of Advertisements37
2.14. The Product Mix Problem38
2.15. The Blending Problem39
2.16. Common Confusions in Formulation40
2.17. Exercises42
2.18. References45
3. Solution Methods for LP Problems47
3.1. Introduction47
3.2. Graphical Method47
3.3. Example: Graphical Solution for a Minimization Problem51
3.4. Simplex Method52
3.5. Step-by-step Overview of the Simplex Method55
3.6. Artificial Variables60
3.7. Big M and Two-Phase Methods61
3.8. Degenerate Solutions65
3.9. Duality Concept in Linear Programming65
3.10. Shadow Prices67
3.11. Sensitivity Analysis68
3.12. Parametric Programming68
3.13. The Revised Simplex Method68
3.14. Computer Implementation of the Simplex Method68
3.15. Interior Point Methods69
3.16. Cases Where Millions of Variables Occurs in Formulations70
3.17. Exercises72
3.18. References74
4. Transportation and Flow Problems77
4.1. Introduction77
4.2. Network Flow Problems78
4.3. Transportation Problem78
4.4. Assignment Problem98
4.5. Transshipment Problems107
4.6. Case Study:Â Minimization of Costs in a Network Model for Recycling Paper Products(Rasmussen, 2010)109
4.7. Shortest Route Problem112
4.8. Maximal Flow Problem117
4.9. Software for Transportation and Assignment Problems126
4.10. Exercises127
4.11. References132
5. Software for Solving LP133
5.1. Introduction133
5.2. LINGO and What’s Best!134
5.3. Free LP solvers136
5.4. Google OR-Tools138
5.5. COIN-OR (Computational Infrastructure for Operations Research)142
5.6. AMPL142
5.7. GAMS143
5.8. Using Python143
5.9. Use of PuLp Library148
5.10. CVXOPT149
5.11. Gurobi for Python151
5.12. NetworkX153
5.13 Exercises154
5.14. References154
6. Integer Linear Programming157
6.1. Introduction157
6.2. Types of Variables158
6.3. Formulation Examples159
6.4. Project Selection Problem (Binary Variables)160
6.5. The Set Covering Problem161
6.6. Discussion: Set Cover Model-based Optimum Location of Electric Vehicle Charging Stations (Vansola, and Shukla, 2022)163
6.7. Cargo Loading Problem165
6.8. Job Sequencing Problems167
6.9. Facility Location170
6.10. Bin Packing Problem172
6.11. Knapsack Problem174
6.12. Network Flow Problems175
6.13. Graph Coloring Problem175
6.14. Exercises175
6.15. References177
7. Integer Programming Solution Methods179
7.1. Introduction179
7.2. Graphical Method179
7.3. Branch and Bound Method182
7.4. Mixed Integer Programming (MIP)186
7.5. Exercises 187
7.6. References189
8. Traveling Salesman Problem (TSP)191
8.1. Introduction191
8.2. Applications of the Traveling Salesman Problem192
8.3. Formulation as Integer Programming Problem193
8.4. Subtours195
8.5. Example: Cities in Kerala197
8.6. Solution Methods201
8.7. Heuristic Methods for TSP202
8.8. Getting Routes on a Map205
8.9. The Vehicle Routing Problem (VRP)206
8.10. Vehicle Routing Problem Spreadsheet Solver (VRP Spreadsheet Solver)209
8.11. Exercises209
8.12. References213
9. Project Scheduling215
9.1. Introduction215
9.2. Critical Path Method (CPM)216
9.3. Linear Programming (LP) Formulation for Project Scheduling218
9.4. AOA Network Analysis: Forward Pass, Backward Pass, and Critical Path221
9.5. Project Crashing226
9.6. Resource Leveling232
9.7. Resource Smoothing233
9.8. PERT (Program Evaluation and Review Technique)234
9.9. Example: Project Scheduling with Uncertain Activity Times 236
9.10. Exercises238
9.11. References240
10. Goal Programming241
10.1. Introduction241
10.2. Goal Programming Approaches242
10.3. Example: Non-preemptive Approach243
10.4. Example – Sequential Preemptive Goal Programming247
10.5. Exercises250
10.6. References251
11. Introduction to Python and Exercises253
11.1. Introduction to Python253
11.2. Installing Python253
11.3. Using Python254
11.4. IDEs (Integrated Development Environments)254
11.5. Pandas Library261
11.6. Linear Programming (LP) and Integer Linear Programming (ILP) Libraries262
11.7. Preparing Code to Solve LP, ILP263
11.8. Practice Exercises Using Python264
11.9. References303
12. Supplement: Tutorial on Using Excel for Solving LP305
12.1. Introduction305
12.2. Step-by-step Guide on How to Use Excel to Solve LP Problems305
12.3. Sensitivity Analysis306
12.4. Example308
12.5. Integer or Mixed-Integer Linear Programming (MILP) Problems in
Excel Solver313
12.6. Advantages and Limitations316
12.7. References317
Reviews
There are no reviews yet.