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


A Quick Look at the Contents

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 non-negative 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 


A Review of some of the examples and topics situations covered in the above tutorial

1. 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
requires aij units of Ri; i = 1;....;m. The manufacturer has bi= 1; 2; ...; m available. He makes a profit pjThe manufacturer needs to decide on number of units of each product Aj  he needs to manufacture in order to maximize his profit.  

2. 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. Demand has to be met every month. Formulate as a linear programming problem.

3. Consider a restaurant that is open seven days a week. Based on past experience, the  number of workers needed on a particular day is given to you. Every worker works five consecutive days, and then takes two days off, repeating this pattern indefinitely. How can we minimize the number of workers that staff the restaurant? We explain how to structure out the problem into (1) Decision Variable (2) Objective function (3) Constraints:

4. Popular Cases which may arise for a Linear Programming minimization problem:

Unique finite optimal solution –  (a)= bounded region, (b)= unbounded region. 

Alternative finite optimal solution –  (a)= bounded region, (b)= unbounded region. 

Unbounded optimal solution  

Empty feasible region


5. 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, ......., dldirections of the set S. Then for any x Є S there exists λ1, λ2, .... , λk and μ1, μ2, ..., μl
x = (λ1x1 + λ2x2 + ... + λkxk) + (μ1d1 + μ2d2 + ... + μldl) where ∑ λj = 1,  λj ≥ 0, j = 1,2,.... k; μj ≥ 0, j = 1,2,...,l.

6. Basic Feasible Solutions: 

In this section, the notion of basic feasible solutions will be introduced and its correspondence to extreme points of a polyhedra was be shown.
Consider the linear program with the constraints: Ax = b; x ≥ 0; Where A is an m X n matrix and b is an m vector. Let rank(A) = m (generally, rank of the matrix is the number if rows of that matrix). Let A = [B,N]; where B is m X m invertible matrix, and N is m X (n - m) matrix. Then the solution to the equations 
Ax = b; x ≥ 0; where xB = B-1b and xN = 0 is called a basic solution of the system. 
If xB ≥ 0, then x is called a basic feasible solution (BFS) of the system. 
A basic feasible solution x is called a degenerate basic feasible solution if at least one component 
of xB is zero. 

Note: 

• B is called the basis matrix. 
• Variables in xB are called basic variables. 
• Variables in xN are called non basic variables. 
• In general the possible number of basic feasible solutions is bounded by the number of ways of extracting m columns out of n columns and it is bounded by 
most BFS. Hence there are finite number of BFS. 

7. Some of the Results regarding BFS: 

• The collection of extreme points corresponds to the collection of basic feasible solutions, and both are non-empty if the feasible region is non-empty. 
• If an optimal solution exists, then an optimal extreme point exists. 
• For every extreme point there corresponds a basis and conversely for every basis there corresponds a unique basis. If an extreme point has more than one basis representing it, it is a degenerate extreme point. 

 

8. 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. We also cover, The Simplex Method in Tableau Format.
 


Comments