Introduction to Mathematical Programming. Part I

This textbook is intended for students of technical and economic universities. It is a result of my teaching of mathematical programming, optimization methods and operations research to students of Czestochowa University of Technology, including Erasmus+ Program students, for over ten years. This is the first part of a planned series (an intended series), limited to the presentation of issues related to linear programming. The second part will focus on non-linear programming problems. The textbook is divided into five main chapters. Chapter 1 is a reminder of some mathematical topics (the basics of linear algebra and systems of linear equations) that will help the readers understand the material discussed. Chapter 2 considers linear programming problems from its standard form to practical, highly common, with various examples of applications at the intersection of technology and economics. In chapter 3, the transportation problem with applications will be considered. Chapter 4 deals with a special kind of linear programing, so-called integer programming. And finally, Chapter 5 shows how the Maple package can be used to solve any linear programming problems.

INTRODUCTION CHAPTER 1. REVIEW OF LINEAR ALGEBRA 1.1. Matrices. Matrix operation 1.2. Systems of linear equations. Methods of solution CHAPER 2. LINEAR PROGRAMMING 2.1. Basic concepts and notation 2.2. Linear programming problem formulation 2.3. Graphical solutions to linear problems 2.4. The Simplex Method 2.4.1. Introduction to the Simplex Method – the algebraic approach 2.4.2. The Simplex Algorithm – step by step 2.4.3. The Big M – method 2.5. Duality theory 2.5.1. Formulating the dual LP 2.5.2. The dual theorems 2.5.3. Economic interpretation of dual variables 2.6. Sensitivity analysis 2.6.1. Sensitivity to an objective coefficients 2.6.2. Sensitivity to constraint bounds 2.7. Special cases of linear programming problems CHAPTER 3. TRANSPORTATION PROBLEM 3.1. Transportation problem – mathematical model formulating 3.1.1. Basic definitions 3.2. Initial basic feasible solution 3.2.1. Northwest Corner Method 3.2.2. Minimum Cost Method 3.2.3. Vogel’s approximation method 3.3. Optimal solution for transportation problem 3.4. Standard application of transportation problem – Transshipment problems CHAPTER 4. INTEGER LINEAR PROGRAMMING 4.1. Formulating the integer linear problem 4.2. The branch and bound method 4.3. Binary and mixed integer linear problem CHAPTER 5. COMPUTER IMPLEMENTATION 5.1. An introduction to using the Maple package 5.2. Linear algebra with Maple 5.3. A step-by-step Maple implementation to solve the linear programming problems 5.3.1. The graphical solution to LP 5.3.2. The Simplex method 5.3.3. Transportation problem BIBLIOGRAPHY