The Learning Point‎ > ‎Mathematics‎ > ‎

Operations Research - An Introductory Tutorial with Problems and Solutions - Linear Programming, Simplex, LP Geometry in 2D


The Fundamentals of Operations Research 

 

Operations Research

LP (Linear Programming) Introduction:


A linear programming problem is a problem of minimizing or maximizing a linear function in 
the presence of linear constraints of the inequality and/or the equality type.

Standard and Canonical Formats:


Standard Form - 

A linear program in which all restrictions are equalities and all variables are non-negative. The 
simplex method is designed to be applied only after the problem is put in the standard form.

Canonical Form -

The canonical form is also useful especially in exploiting duality relationships. A minimization 
problem is in canonical form if all variables are nonnegative and all the constraints are of the ≥
type. A maximization problem is in canonical format if all the variables are non-negative and all 
the constraints are of the ≤ type.

Formulation of Linear Programming Model:


1. Identify the decision variables.
2. Identify the problem constraints and express the constraints as a series of linear equations / inequalities.
3. Identify the objective functions as a linear equation, and state whether the objective is maximization or minimization.

Here are some situations in which a knowledge of OR might help, and they have been explained in greater detail in the tutorial :
  • Consider a small manufacturer making n products A1; A2; …. ; An. Each of the n products require some part of m resources R1; R2; …. ; Rm. Each unit of product Aj, j = 1; …. ; n requires aij units of Ri; i = 1;….;m. The manufacturer has bi units of resource Ri; i= 1; 2; …; m available. He makes a profit pj ; j = 1; 2;…. ; n per unit of product Aj ; j = 1;2; …..; n. The manufacturer needs to decide on number of units of each product Aj, j = 1;2; ….; n. He needs to manufacture in order to maximize his profit. How should he go about this ?
  • Consider a company making a single product. 
    The estimated demand for the product for the next four months are 1000, 800, 1200 and 
    900 respectively. Company has a regular time capacity of 800 per month and overtime 
    capacity of 200 per month. Cost of regular time production is Rs. 20 per unit. Cost of 
    overtime production is Rs. 25 per unit. Inventory holding cost is Rs. 3 per unit per month. 
    The demand has to be met every month. What should their strategy be ?

LP Geometry in two-dimensions:


Geometric procedure for solving a linear programming problem is only suitable for very small problems. It provides a great deal of insight into the linear programming problem. We will also introduce the idea of all the possible cases that may arise for a minimization problem : Unique finite optimal solution, Alternative finite optimal solution, Unbounded optimal solution, Empty feasible regions. 

Basic Feasible Solutions: In this section, the notion of basic feasible solutions will be introduced and its correspondence to extreme points of a polyhedra will be shown.

Representation theorem:


Let S = {x : Ax ≤ b, x ≥ 0} be a nonempty polyhedral set. Any point in S can be represented as a convex combination of its extreme points plus a non-negative combination of its extreme
directions. Let x1, x2, … xk denote the extreme points and d1, d2, ……., dl denote the extreme directions of the set S. Then for any x Є S there exists λ1, λ2, …. , λk and µ 1, µ 2, …, µ l such that
x = (λ1x1 + λ2x2 + … + λkxk) + (µ 1d1 + µ 2d2 + … + µ ldl) where ∑ λj = 1, λj ≥ 0, j = 1,2,…. k; µ j ≥ 0, j = 1,2,…,l.

The Simplex Method


Simplex method is used to solve the linear programming problem. The simplex method is a procedure that moves from an extreme point (basic feasible solution) to another extreme point with a better (improved) objective function value. This has been covered in detail in the tutorial document which will cover the Simplex Algorithm, the algebra behind the Simplex Algorithm and the Simplex Method in Tableau Format.


Complete Tutorial Document with Solved Problems, Plots and Examples 


 


Comments

Try out our Quizzes!