Linear Programming

Linear programming deals with the optimization (maximization or minimization) of linear functions subject to linear constraints.This technique has found its applications to important areas of product mix, blending problems and diet problems.Oil refineries, chemical industries, steel industries and food processing industry are also using linear programming with considerable success. Linear programming problems involving only two variables can be effectively solved by a graphical technique which provides a pictorial representation of the solution.

Step 1: Formulate the given problem as a linear programming problem.

Step 2: Plot the given constraints as equalities on x₁-x₂ coordinate plane and determine the convex region formed by them.

Step 3: Determine the vertices of the convex region and find the value of objective function at each vertex.The vertex which gives the optimal value of the objective function gives the desired optimal solution to the problem.

Any linear programming problem involving more than two variables may be expressed as follows

Find the values of the variable x₁, x₂,............,x_n which maximize (or minimize) the objective function

Z=c₁x₁+c₂x₂+..............+c_nx_n

subject to the constraints

a₁₁x₁+a₁₂x₂+.............+a_1nx_n ≤ b₁

a₂₁x₁+a₂₂x₂+............. +a_2nx_n ≤ b₂

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

a_m1x₁+a_m2x₂+..............+a_mnx_n ≤ b_m

and meet the non negative restrictions

x₁, x₂,...........x_n ≥ 0

1 . A set of values x₁,x₂......x_n which satisfies the constraints of linear programming problem is called its solution.

2 . Any solution to a linear programming problem which satisfies the non negativity restrictions of the problem is called its feasible solution.

3. Any feasible solution which maximizes(or minimizes) the objective function of the linear programming problem is called

its optimal solution.

There are two forms of linear programming problem. They are Canonical form:

The general linear programming problem can be expressed as Maximize z=c₁x₁+c₂x₂+........c_nx_n subject to the constraints

a_i1x₁+a_i2x₂+.........a_inx_n<=bi; x₁, x₂........x_n ≥0. This form is called its canonical form and has the following characteristics:

1. objective function is of maximization type

2. all constraints are of (≤) type

3 .all variables xi are non-negative

Standard form:

Standard form has its following characteristics:

1. objective function is of maximization type

2. all constraints are expressed as equations

3. right hand side of each constraint is non negative

4. all variables are non negative

Step 1. Identify the unknowns in the given LPP. Denote then by x and y.

Step 2. Formulate the objective function in terms of x and y. be sure whether it is to be maximized or minimized.

Step 3. Translate all the constraints in the form of linear inequations.

Step 4. Solve these inequations simultaneously. Mark the common area by shaded region. This is the feasible region .

Step 5. Find the coordinates of all the vertices of the feasible region

Step 6. Find the value of the objective function at each vertex of the feasible region.

Step 7. Find the values of x and y for which the objective function z = ax + by has maximum or minimum value (as the case may be)

Below are the example problems on linear programming-

Problem 1:
Solve the following linear program maximize 5x₁ + 6x₂ subject to
x₁ + x₂ ≤ 10
x₁ - x₂ ≥ 3
5x₁ + 4x₂ ≤ 35
x₁ ≥ 0
x₂ ≥ 0

Solution:
It is plain that the maximum occurs at the intersection of
5x₁ + 4x₂ = 35 and
x₁ - x₂ = 3
Solving simultaneously, rather than by reading values off the graph, we have that
5(3 + x₂) + 4x₂ = 35
i.e. 15 + 9x₂ = 35
i.e. x₂ = ($\frac{20}{9}$) = 2.222 and
x₁ = 3 + x₂ = ($\frac{47}{9}$) = 5.222
The maximum value is 5($\frac{47}{9}$) + 6($\frac{20}{9}$) = ($\frac{355}{9}$) = 39.444

Problem 2:
A carpenter makes tables and chairs. Each table can be sold for a profit of £30 and each chair for a profit of £10. The carpenter can afford to spend up to 40 hours per week working and takes six hours to make a table and three hours to make a chair. Customer demand requires that he makes at least three times as many chairs as tables. Tables take up four times as much storage space as chairs and there is room for at most four tables each week.Formulate this problem as a linear programming problem .

Solution:
Variables
Let,
xT = number of tables made per week
xC = number of chairs made per week

Constraints total work time 6xT + 3xC ≤ 40 customer demand xC ≥ 3xT storage space
($\frac{xC}{4}$) + xT ≤ 4, all variables ≥ 0

Objective maximize 30xT + 10xC

The graphical representation of the problem is given below and from that we have that the solution lies at the intersection of
($\frac{xC}{4}$) + xT = 4 and 6xT + 3xC = 40

Solving these two equations simultaneously we get xC = 10.667, xT = 1.333 and the profit = £146.667