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

A Summary/Recap of some of the problems solved in the tutorial document above.

1. Feed is manufactured for cattle, sheep, and chickens. This is done by mixing the following main ingredients: corn, limestone, soybeans, and fish meal. These ingredients
contain the following nutrients: vitamins, protein, calcium, and crude fat. The contents of the nutrients in each kilogram of the ingredients are given in a table. It is required to produce 10, 6, 8 (metric) tons of cattle feed, sheep feed, and chicken feed. Amount of the ingredients available are namely, 6 tons of corn, 10 tons of limestone, 4
tons of soybeans, and 5 tons of fish meal. The price per kilogram of these ingredients is respectively 0.20, 0.12, 0.24 and 0.12. You are provided with another table containing the minimal and maximal units of the various nutrients that are permitted is summarized for a kilogram of the cattle feed, the sheep feed, and the chicken feed. Formulate into a linear programming model so that the total cost is minimized.

2. The company operates three plants, namely A, B, and C. The capacities (in thousands of square feet) and unit manufacturing costs (in rupees per thousand square feet) of these
plants are provided in a table T1. The product is distributed within 3 marketing regions. Their requirements (in thousands of square feet) are given in another table T2. The transportation costs (in rupees) per thousand square feet from plants to marketing regions are given in another table t3.  Formulate a linear programming problem to determine the quantities the company should transport from each plant to each marketing region in order to minimize the total manufacturing and transportation cost for the year.

3. Two types of devices are to be produced from device 3. Device 1 requires 9 hours of labor and 10 feet of rubber material. The unit profit from Device 1 is Rs. 325. To produce
one device 2, 6 hours of labor and 21 feet of rubber material is required. The unit profit from device 2 is Rs. 400. There are a total of 200 devices 3, 1600 hours of labor, and
3000 feet of rubber material available. If the profit is to be maximized, then formulate the above as a linear programming problem.

4. A steel manufacturer produces three sizes of beams: small, medium and large. These beams can be produced on any one of the three machine types: A, B, and C. The length in
feet of the beams that can be produced on the machines per hour are summarized in a table. The hourly operating costs of the machines are Rs. 50, 30 and 25 respectively and each machine can be used up to 20 hrs per week. Assume that 1000, 700, 650 feet of beams of different sizes are required weekly. Formulate linear program for this machine scheduling problem.

Identifying the decision variables, constraints, objective functions are the key steps over here. 

5. You are given a table containing quantities of gasoline, kerosene and jet fuel are produced per barrel of each type of oil (light and heavy crude oil). The cost per barrel of light and heavy crude oil is 10 and 8 respectively. It is required to deliver 500000 barrels of gasoline, 300000 barrels of kerosene and 450000 barrels of jet fuel. Formulate a linear program to find the number of barrels of crude oil and minimizes the total cost.

6. Consider an iron roll from which sheets of same length but different widths have to be 
cut. Let the iron roll be 15cm wide and following sizes should be made from it.
• 7 cm = 286 numbers
• 6 cm = 112 numbers
• 5 cm = 345 numbers
• 4 cm = 209 numbers
Only one dimension cutting is allowed. Formulate a LP such that wastage of the material 
is minimized.

7. A 
Game theory problem: two manufacturers A and B are competitors for the same product. Each wants to maximize their market share and adopt 2 strategies. The gain or pay-off for A when A adopts i and B adopts strategy j is given by aij. A 2×2 matrix would like
(4 −2

−1 6 ). 
During a given time period T, both A and B have to mix their strategies. If A plays strategy 1, then B would play strategy 2 to gain, which A does not want. Each therefore wants to mix their strategies so that they gain maximum (or the other loses maximum). So, for time period T, what is the proportion that A plays strategy 1 and 2. Assume A and B are equally intelligent.

8. Consider the following problem

    Max x1 – x2
    Subject to –x1 + 2x2 ≤ 0
    -3x1 + x2 ≥ -3 and 
x1, x2 ≥ 0

    a) Sketch the feasible region
    b) Solve the problem geometrically

9. 
Find the basic feasible solutions of the following LP.

    Max x1 + x2
    Subject to –x1 ≤ 1 and 20x1 + x2 ≤ 100 and x1, x2 ≥ 0

10. Solve the following problem using simplex method.

    Min –x1-3x2
    Subject to 2x1 + 3x2 ≤ 6, -x1 + x2 ≤ 1 and x1, x2 ≥ 0

11. Solve the following problem using simplex tableau format:

    Minimize x1 + x2 – 4x3

    Subject to x1 + x2 + 2x3 ≤ 9

    x1 + x2 – x3 ≤ 2

    -x1 + x2 + x3 ≤ 4

    x1, x2, x3 ≥ 0

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