LINEAR PROGRAMMING

Graphical Solution
 Solution of Linear Programming

• After formulation of a given situation as a linear

programming problem, one has to solve the problem for
finding the variables that optimize the objective function.

• Graphical Method for two variables

• Algebraic Algorithm (Simplex Method) for two and more

than two variables

• Optimization Software (TORA,CMMS, AMPL, Excel

Solver, etc) for two and more than two variables
 Reddy Mikks Company
• The Reddy Mikks produces both interior and exterior paints from
two raw materials, M1 and M2. The following table provides the
basic data of the problem:
Tons of raw material per ton
of Maximum daily
availability
(tons)
Exterior Paint Interior Paint
Raw material, M1 6 4 24
• ARaw Material,
market M2 restricts the
survey 1 maximum daily
2 demand of 6interior
paint
Profit pertoton2 ($1000)
tons. Additionally
5 the daily demand
4 for interior paint
cannot exceed that of exterior paint by more than 1 ton. Reddy
Mikks wants to determine the optimum (best) product mix of interior
and exterior paints that maximize the total daily profit.
• Final Formulation

• Now the complete Reddy Mikks model is written as

• Maximise z = 5x1 + 4x2
• Subject to 6x1 + 4x2 ≤ 24
• x1 + 2x2 ≤ 6
• -x1 + x2 ≤ 1
• x2 ≤ 2
• x1 ≥0
x2 ≥ 0
• Any solution that satisfies all the constraints of the model is a
feasible solution.
 Graphical Method of Solution

It includes two basic steps:

1. Determination of the solution space which define the feasible

solutions that satisfy all the constraints of the model.

2. Determination of the optimal solution from among all the

points in the feasible solution space.

• This describes for both a maximization and minimization

objective function.
• Example: Reddy Mikks Model

• Step 1 Determination of the Solution Space:

• Let the horizontal axis x1 and the vertical axis x2 represent the
exterior paint and interior paint variables respectively.

• Next, considering non negative restrictions x1 ≥ 0 and x2 ≥ 0.

• These two constraints restrict the solution space area to the first
quadrant which lie above x1 axis and right of the x2 axis.

• By replacing inequalities in the constraint we get linear equation and

then plot the resulting straight line we get the graph.
• To plot the line we need two distinct point

• Setting x1 = 0, then x2 = 0 in the equation 6x1 + 4x2 ≤ 24

• Obtained x2 = 24/4 = 6 and x1 = 24/6 = 4.

• Thus the line passes through two points (0,6) and (4,0).

• Similarly, all other points are found from rest of the constraints

• All the inequalities divide (x1, x2) plane into two half spaces

• One side satisfies the inequality and other one does not.
• Procedure for determining the feasible side is to use the origin (0, 0)
as a reference point

• e.g. the first constraint i.e. 6x1 + 4x2 ≤ 24 satisfy the point (0, 0)
which yield 6 x 0 + 4 x 0 ≤ 24.

• This means the feasible side of the constraint 6x 1 + 4x2 ≤ 24 includes

the origin is shown by arrow associated with the constraint 1.

• If origin does not satisfy the inequality the direction arrow must
point in the opposite side of (0, 0).

• Also if line happens to pass through origin, then we can choose

another reference point to effect the desire result.
• Step 2 Determination of the Optimum Solution:

• Graph provides the feasible solution space which delineated by the

line segments joining the corner point ABCDE and F.

• Any point within or on the boundary of the space ABCDEF is

feasible point as it satisfies all the constraints .

• Optimal solution identifies the direction in which the profit function

z = 5x1+4x2 increases as shown in the graph.

• It is clear that the line 5x1+4x2 passing through that point move up
parallel to itself and thus increase its value.

• One of the corner points (ABCDE and F) of the feasible region will
be optimal solution.
• Despite infinite number of feasible solutions one has to
consider a finite number of corner points to determine optimal
solution.

• Start with any corner point within the feasible region, moving
along the boundary line of feasible region to adjacent corner
point that gives the largest increase in the objective function.

• Repeat this iteration until to reaches a corner point from which

it does not pay to move to any of its adjacent corner points.

• This corner point is an optimal solution.

• This is the basis and logic of the simplex method which is

applied to the large size linear programming problems.
• Start with origin A, then two adjacent corner points are F and B.

• If move along AF to F (0,1) profit increase to 5x0 + 4x1 = 4.

• If move along AB to B (4,0) profit increases to 5x4 + 4x0 = 20.

• After move from A to B, then move from B to C (3, 3/2) profit

increase in 5x3 + 4x(3/2) = 21.

• Now move from C to D (2, 2) profit will be 5x2 + 4x2 = 18, in

this direction profit decreases, so it do not move from C to D.

• Hence, optimal solution at point C with x1 = 3 tons, x2 = 1.5 tons

of exterior and interior paint will yield a daily profit of $21000.
Corner point (x1, x2) z  
A (0,0) 0
B (4,0) 20
C (3,1.5) 21 Optimum
D (2,2) 18
E (1,2) 13
F (0,1) 4  
Example: DIET PROBLEM

• Ozark Farms uses at least 800lb of special feed daily. The

special feed is a mixture of corn and soybean meal with the
following composition:
lb per lb of feedstuff
Feedstuff Protein Fiber Costs($/lb)
Corn 0.09 0.02 0.30
Soybean meal 0.60 0.06 0.90

The dietary requirements of the special feed stipulate at least

30% protein and at most 5% fibre. Ozerk Farms wishes to
determine the daily minimum cost feed mix.
 Solution

• Feed mix consists of corn and soybean meal, the decision

variables of the model are defined as

• x1 = lb of corn in the daily mix

• x2 = lb of soybean meal in the daily mix

• Objective function is to maximize total daily cost (in $) of the

feed mix i.e. Minimize z = 0.3 x1 + 0.9 x2

• Constraints must reflect the daily amount needed and the

dietary requirements.

• Ozark Farms needs 800lb of feed a day, the associate constraint

can be expressed as x1 + x2 ≥ 800
• Protein dietary requirement constraint is developed next.

• Amount of protein included in x1 lb of corn and x2 lb of

soybean meal is (0.09 x1 + 0.6 x2) lb.

• This quantity should equal at least 30% of the total feed mix
(x1 + x2) lb.

• Thus yielding 0.09 x1 + 0.6 x2 ≥ 0.3 (x1 + x2).

• Similarly, fibre constraint is 0.02 x1 + 0.06 x2 ≤ 0.05 (x1 + x2).

• After rearranging we get the complete model

• The complete model thus becomes

• Minimise z = 0.3 x1 + 0.9 x2

• Subject to x1 + x2 ≥ 800
• 0.21 x1 – 0.3 x2 ≤ 0
• 0.03 x1 – 0.01 x2 ≥ 0
• x1 ≥ 0
• x2 ≥ 0
The graphical solution is
• In graphical solution two constraints pass through origin.

• The intersection of the line x1 + x2 ≥ 800 with the lines 0.21

x1 – 0.3 x2 ≤ 0 and 0.03 x1 – 0.01 x2 ≥ 0 and yield the
value of x1 and x2.

• Here the value of x1 = 470.6lb and x2 = 329.4lb

• These two values put in the objective function and the

associate minimum cost is found to be $ 473.64.
 Special Cases
in
Linear Programming
1. Degeneracy:

• If the solution of the linear programming is degenerate, then

the condition reveals that the model has at least one
redundant constraint that is some resource are superfluous.

• Example: Maximize z = 3x1 + 9x2

subject to x1+4x2 ≤ 8
x1 + 2x2 ≤ 4
x1, x2 ≥ 0
• Degeneracy has two implications

a. It has phenomena of cycling or circling. Simplex procedure

would repeat same sequence of iterations.
– never improving the objective value
– never terminating the computations.

b. Although differ in classifying the variables as basic and non

basic in both iterations.
– it yields identical values of all variables and objective value,

• Therefore, when degeneracy appears it should not stop the

computations at any iteration, even though it is not optimum
as the solution may be temporarily degenerate
• 2. Alternative Optima:

• When objective function is parallel to a binding constraint (a

constraint that is satisfied as an equation by the optimal
solution), the objective function will get the same optimal
value at more than one solution point, then the model has
alternative optima.

• Example: (infinity of solutions)

• Maximize z = 2x1 + 4x2
• subject to
x1 + 2x2 ≤ 5 x1 + x2 ≤ 4
x1, x2 ≥ 0
• Alternative optima can arise in any point on line segment BC as the objective
function is parallel to one of the binding constraint with same objective value z =
10.
• In practice, alternative optima are useful as they allow us to choose
from many solutions without experiencing any deterioration of
objective value.

• If the example represents a product mix situation, it may be

advantageous from the standpoint of sales competition to produce
two products rather than one.

• For instance, in this example, the solution at B shows that activity 2

only is at a positive level, whereas at C both activities are positive.

• Therefore, solution at C is recommended.

• 3. Unbounded solutions:

• In LP models, the values of the variables may be increased indefinitely without violating
any of the constraints, means the solution space is unbounded in at least one direction.

• As a result, the objective value may increase (maximization case) or decrease

(minimization case) indefinitely.

• It is due to poorly constructed model such as one or more important constraints are not
accounted for and the parameters (constants) of some constraints are not estimated
correctly.

• Example: Maximize z = 2x1 + x2

subject to x1 – x2 ≤ 10
2x1 ≤ 40
x1, x2 ≥ 0
• Solution space is unbounded in the direction of x2 and the value of z can
be increased indefinitely as shown in the figure.
4. Nonexisting (or infeasible) solutions:

• If the constraints are not satisfied simultaneously, the model has

no feasible solution.

• From the practical standpoint, an infeasible space points to the

possibility that the model is not formulated correctly.

• Maximize z = 3x1 + 2x2

subject to 2x1 + x2 ≤ 2
3xl + 4x2 ≥ 12
x1, x2 ≥0
• Figure demonstrates the infeasible solution space.