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.

**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 a_{ij} units of **R**_{i}; i = 1;....;m. The manufacturer has b_{i}* i **= 1; 2; ...; m* available. He makes a profit **p**_{j. }The 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.