Linear Programming Formulation & Graphical Method



LINEAR PROGRAMMING FORMULATION & GRAPHICAL METHOD

Aim: To optimally utilize the scarce resources- e.g. money, man power, machinery etc.

LP is the most popular and widely accepted deterministic technique of Mathematical programming.

The credit for its development goes to George B Dentzig in 1947.

Basic Terminology, Requirements, Assumptions of LP

The word linear stresses on directly proportional relationship among the variables while the world programming refers to the systematic procedure of solution.

Basic Requirements:

1. Decision variables and their relationship

2. Objective Function

3. Constraints

4. Alternative courses of actions

5. Non negativity restriction

6. Linearity

Basic Assumptions

1. Proportionality : The amount of each resource used and associated contribution to profit (or cost) in the OF must be proportional.

2. Divisibility: Continuous values of decision variables and resources must be permissible in obtaining optimal solution.

3. Additivity: The total profitability and the total amount of each resource utilized must be equal to sum of the respective individual amounts.

4. Certainty: All coefficients and parameters in LP model are known with certainty.

Advantages of LP

1. LP helps in attaining the optimum use of productive factors.

2. Improve the quality of decisions

3. Provides possible and practical solutions and keeps room open for modification.

4. Highlights the problem areas, bottlenecks and constraints operating upon the problem in hand.

Limitations of LP

1. Treat all relationships leaner which usually does not happen in realty.

2. Integral solution is not guaranteed.

3. Does not take into consideration the effect of time and uncertainty.

4. Sometimes, it is unable to solve large scale problems and demands for decomposition.

5. Deals with only a single objective.

Application Areas of LPP

Agriculture: Allocation of scarce resources-acreage, labour, water, capital…

Military: Various optimizations pertaining to allocation, transportation, strategies or so.

Production Management

← Product Mix

← Production Planning

← Assembly Line Balancing

← Blending Problems

← Trim Loss Prevention

Financial Management

← Portfolio Selection

← Profit Planning

Marketing Management

← Media Selection

← Traveling Salesman Problem

← Physical Distribution

Personnel Management

← Staffing Problem

← Determination of Equitable Salaries

← Job Evaluation and Selection

Formulation of a LP Model

1. Identify the decision variables and express them in algebraic symbols

2. Identify all the constraints or limitations and express as equations

3. Identify the Objective Function and express it as a linear function.

General Mathematical Formulation of LPP

Optimize (Maximize or Minimize)

Z = c1 x1 + c2 x2+…+cn xn

Subject to:

a11 x1 + a12 x2 +…+ a1n xn (= ) b1

a21 x1 + a22 x2 +…+ a2n xn (= ) b2

.

.

am1 x1 + am2 x2 +…+ amn xn (= ) bm

and x1, x2, …xn >=0

The above formulation may also be expressed with the following notations:

Optimize (Max. or Min.) z = Σ cj xj for j = 1..n,

(Objective Function)

Subject to:

Σ a ij xj (=) bi ; for j = 1 ..n, i = 1,2, …m

(Constraints)

and xj >=0 ; j= 1, 2, …, n

(Non negativity restrictions)

Some Definitions

1. Solution: pertains to the values of decision variables that satisfies constraints

2. Feasible solution: Any solution that also satisfies the non negativity restrictions

3. Basic Solution: For a set of m simultaneous equations in n unknowns (n>m), a solution obtained by setting n- m of the variables equal to zero and solving the m equation in m unknowns is called basic solution.

4. Basic Feasible solution: A feasible solution that is also basic.

5. Optimum Feasible solution: Any basic feasible solution which optimizes the objective function

6. Degenerate Solution: If one or more basic variable becomes equal to zero.

Steps for Graphical Solution

A. Corner Point Method

1. Define the problem mathematically

2. Graph by constraints by treating each inequality as equality.

3. Locate the feasible region and the corner points.

4. Find out the value of objective function at these points.

5. Find out the optimal solution and the optimal value of O.F.

B. Iso-Profit or Iso-Cost Line Method

1. Define the problem mathematically

2. Graph by constraints by treating each inequality as equality.

3. Locate the feasible region and the corner points.

4. Draw out a line having the slope of Objective Function Equation (this is called Iso-Cost / Profit Line in Minimization and Maximization problems respectively) somewhere in the middle of the feasible region

5. Move this line away from origin (in case of Maximization) or towards Origin (in case of Minimization) until it touches the extreme point of the feasible region.

6. If a single point is encountered, that reflects optimality and its coordination the solution. If Iso-Profit/ Cost line coincides with any constraint line at the extreme, then this is the case of multiple optimum solutions.

Some special cases:

1. Infeasible Solution

2. Multiple optimum solutions

3. Unbounded solution

Simplex Method of Solution of LPP

Steps:

1. Formulation of the mathematical model

2. Set up an initial solution

3. Test for Optimality (variable entry criteria)

4. Test for feasibility (variable leaving criteria)

5. Identify the key element

6. Determine the new solution

7. Revise the solution until optimization.

READY MIX PROBLEM (GRAPHICAL SOLUTION)

(Ref. : Taha, Operations Research- an introduction, Pearson Education, Ed.7)

Ready Mix Produces interior and exterior paints from two raw materials M1 & M2.

The requirement of raw material for these paints as well as their availability along with the profit per tons is being expressed in the following table:

| |Tons of Raw Material / Tons of |Maximum Availability /day (tons) |

| |Exterior Paint |Interior Paint | |

|Raw Material M1 |6 |4 |24 |

|Raw Material M2 |1 |2 |6 |

|Profit/Ton (‘000$) |5 |4 | |

Market survey indicates that the daily demand for Interior Paint can not exceed that of Exterior Paint by more than 1 ton. Also, maximum daily demand of interior paint is 2 tons.

Determine the optimal product mix that maximizes total daily profit.

Formulation:

Objective Function:

Maximize Z= 5 x1 + 4 x2

Subject to:

Constraints:

1. 6x1+4x2 = .30( x1+ x2)

.02 x1 + .06 x2 =0

Or

Min Z = .30 x1 + .90 x2

S/t

x1 + x2 >= 800

.21 x1 - .30 x2 = 0

and x1, x2 >= 0

[pic]

[pic]

[pic]

[pic]

[pic]

Linear Programming Duality & Sensitivity Analysis

Duality implies that every LPP has associated with it another LPP sharing same data. They are collectively called primal-dual problems.

Either problems can be considered as primal or dual and can be derived from each other.

Optimal feasible solutions of both can be derived from each other and have the same value.

SENSITIVITY ANALYSIS

LP Assumes Static Environment

• In LP all model parameters (e.g. Unit contribution rate (cj), the amount of available resource (bi) and the amount of resources required per unit of product (aij) are assumed to be know with certainty.

Real world situations are, however, dynamic.

Hence, it is important to the decision maker to know about the changes in parameters.

Sensitivity Analysis or post optimality analysis helps in investigating relationships between the change in model parameters and the optimum solution.

In other word, it brings an element of dynamism to the static nature of LP.

-----------------------

Primal

Optimize (Maximize)

Z = c1 x1 + c2 x2+…+cn xn

Subject to:

a11 x1 + a12 x2 +…+ a1n xn = c2

.

.

a1n y1 + a2n y2 +…+ amn ym >= cn

and y1, y2, …ym >=0

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download