A Comparative Study Of Interior Point, Simplex And Active Set Methods For The Solution Of Linear Programming Problems.

CHAPTER ONE

INTRODUCTION

1.1 BACKGROUND OF THE STUDY

Linear Programming is a subset of Mathematical Programming that is concerned with efficient allocation of limited resources to known activities with the objective of meeting a desired goal of maximization or minimization of a function. Linear Programming determines the way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model, given some list of requirements as linear equations. Linear Programming can be applied to various fields of study - business, economics, and engineering problems. Industries that use linear programming models include transportation, energy, telecommunication and manufacturing. Linear Programming Problems are optimization problems where the objective function and constraints equations are all linear. There are different algorithms for solving Linear Programming Problems such as the Simplex algorithm, Bland’s rule, klee Minty Cube, Criss – Cross algorithm, Active Set algorithm, column generation and Interior Point Method. Linear programs are ubiquitous in many areas of applied science today. The primary reason for this is their flexibility: linear programs frame problems in optimization as a system of linear inequalities. This template is general enough to express many different problems in engineering, operations research, economics, and even combinatorics (in Mathematics). Owing to their vast applicability there has been much interest in finding efficient algorithms which find the best solutions to linear programs.