Chapter Two: Linear Programming

2.1. Introduction to Linear Programming

Linear programming is the analysis of problems in which a linear function of a number of

variables is to be optimized (maximized or minimized) when whose variables are subject to a
number of constraints in the mathematical inequalities. It was developed by George B. Denting
in 1940.

2.2. The characteristics or the basic assumptions of linear programming

I. Decision Variable: The decision variables refer to any activities which are in
competition with other variables for limited resources. Examples of such activity
variables are: services, projects, products etc.
II. Finite Objective Functions:The single-objective optimization is one of the most
important prerequisites of linear programming. Examples of such objectives can be:
cost-minimization, sales, profits or revenue Maximization & the idle-time
minimization etc.
III. Limited Factors/Constraints: These are the different kinds of limitations on the
available resources e.g. important resources like availability of machines, number of man
hours available, production capacity and number of available markets or consumers
for finished goods are often limited even for a big organization
IV. Non-Negativity Restrictions: Since the negative valuesof (any) physical quantity has no
meaning, therefore all the variables must assume non-negative values
V. Linearity Criterion:The relationship among the various decision variables must be
directly proportional. Both the objective and the constraint, must be expressed in
terms of linear equations or inequalities. For example. If oneof the factor inputs
(resources like material, labor, plant capacity etc.) increases, then it should result
in a proportionate manner in the final output
VI. Divisibility. Variables may be assigned fractional values. i.e.; they need not
necessarily always be in whole number.
VII. Certainty. It is assumed that conditionsof certainty exist i.e.; all the relevant
parameters or coefficients in the Linear Programming model are ful1y and
completely known and that they don't change during the period. However, such an
assumption may not hold good at all times.

2.3. Linear Programming problem Formation

Linear programming is one of the most useful techniques for effective decision making. It is an
optimization approach with an emphasis on providing the optimal solution for resource
allocation. Formulating linear programming models involves the following steps:

1. Define the problem/ problems definition: to determine the no. of type 1 and type 2
products to be produced per month so as to maximize the monetary profit given the
restriction.
2. Identity the decision variables or represent unknown quantities.
* Let X1 and X2 be the monthly quantities of type 1 and type 2 products.

3. Determine the objective function: Once the variables have been identified, the objective
function can be specified. It is necessary to decide if the problem is maximization or
minimization problem and the coefficients of each decision variable.
4. Identify the constraints:
 system constraints- more than one variable
 individual constraints- one variable
 Non-negativity constraints.
Example 1:

3F furniture Ltd. manufactures two products, tables & chair. Both the products have to be
processed through two machines Ml& M2 the total machine-hours available are: 200 hours ofM 1
and 400 hours of M2 respectively.
Time in hours required for producing a chair and a table on both the machines is as follows:
Time in Hours:

Machine Table Chair

M1 7 4

M2 5 5

Profit from the Sale of table is Birr 40 and that of a chair is Birr 30.

Required: formulate the LP Problem (LPP)?

Solution
Maximize Z ¿ 40 x 1 +30 x 2

Subject to: 7 x 1+ 4 x 2 ≤ 200

5 x 1+5 x 2 ≤ 400

Further; x 1∧x 2 ≥ 0

(Since if x 1∧x 2< 0 it means that negative quantities of products are being manufactured
which has no meaning). Show each steps for the above model!

Example 2: Alpha Limited produces & sells 2 different products under the brand name black &
white. The profit per unit on these products is Birr 50 & Birr 40 respectively. Both black & white
employ the same manufacturing process which has a fixed total capacity of 50,000 man-hours.
As per the estimates of the marketing research department of Alpha Limited, there is a market
demand for maximum 8,000 units of Black & 10,000 units of white. Subject to the overall
demand, the products can be sold in any possible combination. If it takes 3 hours to produce one
unit of black & 2 hours to produce one unit of white. Formulate linear programming model?
 Solution

Maximize Z = 50x1 + 40x2

Subject: 3x1+2x2≤ 50,000

x 1 ≤ 8,000

x 2 ≤ 10,000

Further; x 1∧x 2 ≥ 0

(Since if x1, x2< 0, it means that negative Quantities of products are being manufactured

– which has no meaning)

Example 3:
Xyz transportation agency operates two types of buses namely BD-554 and BD- 544. Bus 554 is
capable of carrying 40 passengers and 30 tons of cargo whereas BD- 544 is capable of carrying
60 passengers and 15 tons of cargo. The company is contracted to carry at least 480 passengers
and 180 tons of cargo each day. If the cost per journey is birr 500 for BD- 554 and birr 600 for
BD- 544
Required: Formulate the linear programming of the model
Example 4
A candidate wishes to use a combination of radio and television advertisement in his campaign.
Research has shown that each one minute spot on television reaches 90,000 people and each one
minute spot on radio reaches 6,000. The candidates feel he must reach at least 2.16 million
people and he must buy a total of at least 80 minutes of advertisements. How many minutes of
each medium should be used to minimize costs, if television costs $500 per minute and radio
costs $100 per minute?
2.4. Method for solving LPP

There are two types of finding a solution for Linear programming problems.

 Graphic solution and

 Simplex method

2.4.1. Graphical Method of solving Linear Programming Problems

Steps in graphic solution method:-

Step I Defining the problem

Step II Plot the constraints graphically

Step IIILocate the solution space

Step IV Apply Corner Point Method

Example 1

XYZ Ltd.Co. Wishes to purchase a maximum of 3600 units of two types of product, A &
B are available in the market. Product A occupies a space of 3 cubic feet & cost Birr 9
whereas B occupies a space of 1 cubic feet & cost Birr 13 per unit. The budgetary
constraints of the company do not allow spending more than Birr 39,000. The total
availability of space in the company's good own is 6000 cubic feet. Profit margin of both
the product A & B is Birr 3 & Birr 4 respectively. Formulate the above problem as a
linear programming model and solve it by using graphical method. You are required to
ascertain the best possible combination of purchase of A & B so that the total profits are
maximized.
Solution

Objective function, MaximizeZ=3 x 1 +4 x 2

Subject to: -

x 1+ x2 ≤3600 (Maximum unites constraint)

3 x 1+ x 2 ≤6000 (Storage area constraint)

9 x 1+ 13 x 2 ≤39000 (Budgetary constraint)

x 1∧x 2 ≥ 0

(a) .Find the solution by using graphics method

Solution
 X1X1

N (Maximum unites constraint)

u 6000
m (Storage area constraint)
b
e (Budgetary constraint)
3600
r
o
f B
3000 A1
u
n
i
t
e Feasible
s region
o
O X1
f
(0, 0) C
B 3900/9
2000 3600
Number of unites of A

Step IV. Find the optimal solution by the corner point method.

At corner points (O, A, B, C), find the profit value from the objective function. Those
points which maximize the profit are the optimal point.

Corner point Coordinates Objective function Value

Optimal Maximize Z=3 x 1+ 4 x 2

solution
O (0,0) Z=0+0 0

A (0,3000) Z=0+4x3000 12,000

B (1300,2100) Z=3x1300 + 4 x2100 12,300

C (2000,0) 3 x 2000 + 0 6000

ResultThe optimal solution is:

No of units of product A=1300

No of units of product B=2100

Total profit, = 12, 300 which is the maximum

Example 2:

Suppose that a machine shop has two different types of machines; machine 1 and machine 2,
which can be used to make a single product .These machine vary in the amount of product
produced per hour, in the amount of labor used and in the cost of operation.

Assume that at least a certain amount of product must be produced and that we would like to
utilize at least the regular labor force. How much should we utilize each machine in order to
utilize total costs and still meets the requirement? The resource used, the cost and the required
hour is given in the following table.

Resource used

Machine 1 Machine 2 Minimum required hours

(X1) (X2)

Product produced/hr 20 15 100

Labor/hr 2 3 15

Operation Cost Birr25 Birr30

Solution

1. Formulation of the linear programming model

 Min. Z=25 X 1 +30 X 2
Subjectto:
20 X 1 +15 X 2 ≥100
LPP Model
2 X 1 +3 X 2 ≥15
X 1 , X 2≥0

Finding feasible region by plotting the graph

Always keep in mind two things: -

i. For ≥ constraint the feasible region will be the area, which lays above the constraint lines,
and for ≤ constraints, it will lays below the constraint lines.This would be useful in
identifying the feasible region.
ii. According to a theorem on linear programming, an optimal solution to a problem (if it
exists) is found at a corner point of the solution space.

X2
X1=0
A (0, 20/3) 2X1+3X2= 15

Feasible Region
5

B (2.5, 3.33)
X2 =0

X1
Corner 5
Coordinates Objective function C Value
(7.5, 0)

point
Minimize . Z=25 X 1 +30 X 2

A (0,20/3) Z=0+20/3×30 200

B (2.5, 3.33) Z=2.5×25+3.33x30 162.5

C (7.5, 0) Z=7.5x25+0 187.5

 Use the same stapes to find the value of B by using the simultaneous equation as
presented previously.

Result

The optimal solution is:

X1 =2.5, X2=3.33 andMinimum cost Z= 162.5

2.4.2. Special Cases in Graphics Methods

The following are the major special cases in graphics solution

 Alternative Optima
 Infeasible Solution
 Unbounded solution

a) Alternative Optimal solution

When the objective function is parallel to a binding constraint; (a constraint that is

satisfied in the equality sense by the optimal solution), the objective function will assume
the same optimal value at more than one solution point, for this reason they are called
alternative optima. Example 1 shows that normally there is infinity of such solutions.
The example also demonstrates the practical significance of encountering alternative
optima.
 Example1

Maximize z=2 x 1+ 4 x 2

Subject ¿:

x 1+2 x 2≤ 5

x 1+ x 2≤ 4

x1, x2≥0

Example 2:

The information given below is for the products A and B.

_____________________________________________________________________

Machine hours per week Maximum available

Department Product A Product B per week

_____________________________________________________________________

Cutting 3 6 900

Assembly 1 1 200
 Profit per unit Birr 8 Birr 16

_____________________________________________________________________

Assume that the company has a marketing constraint on selling products B and therefore
it can sale a maximum of 125 units of this product.

Required:

a. Formulate the LPP of this problem?

b. Find the optimal solution?

Solution: Let X1 =The Number of units’ f product A produced per week

X2= The numberof units f product B produced per week

a. The LPP Model of the problem is:

Max . Z=8 X 1 +16 X 2

Subjectto:
3 X 1 +6 X 2 ≤900
X 1 +X 2 ≤200
X 2≤125
X 1 , X 2≥0

X2 X2=0

(0, 200)
X 1 +X 2 ≤200
(0,150) C (50, 125)
B (0, 125)
D (100,100)

X1=0
 X2=125 Marketing equation

Cutting: 3X1+6X2=900

FR

X1
(200, 0) (300, 0)

Corners Coordinates Maximize Z=8 X1 + 16X2

A (0, 0) 0

B (0, 125) 2000

C (50, 125) 2400

D (100, 100) 2400

E (200, 100) 1600

Interpretation:

Both C and D are optimal solutions. Any point on the line segment CD will also lead to
the same optimal solution.

==>Multiple optimal solutions provide more choices for management to reach their
objectives.

2. Infeasible Solution

A solution is called feasible if it satisfies all the constraints and the constraints and non-
negativity condition. However, it is sometimes possible that the constraints may be
inconsistent so that there is no feasible solution to the problem. Such a situation is called
infeasibility.

Example:
 Maximize Z=20X1+30X2

Subject to:

2X1+X2< 40

4X1+X2< 60

X1 > 30 and X1, X2 > 0

Solution:

X2 X1=0
(0, 60) X1=30
4X1+X2= 60
(0, 40)

2X1+X2= 40
X2=0
X1
(15, 0) (20, 0) (30, 0)

Note: -In the above graph, there is no common point in the shaded area.

-All constraints cannot be satisfied simultaneously and there is no feasible solution

to the problem.

3. Unbounded Solution

When the value of decision variables in LP is permitted to increase infinitely without

violating the feasibility condition, then the solution is said to be unbounded .Here, the
objective function value can also be increased infinitely. However, an unbounded feasible
region may yield some definite value of the objective function.
Example:

Use the graphical method to solve the following LPP.

1. Maximize Z=3X1+4X2

Subject to:

X1-X2<-1==> -X1+X2>1 since the quantity solution is positive

-X1+X2<0

X1, X2 > 0
X2 X1-X2 =-1

X1+X2 =0

1 Unbounded Feasible region

Feasible Region

X1

2. Maximize Z=3X1+2X2

Subject to:

X1-X2<1

X1+X2≥3

X1, X2 > 0
X2

A (0,3) Unbounded
Feasible Region
X1-X2=1

B (2, 1)
X1+X2=3
Note: here that the two corners of the region are A(0,3) and .B(2,1).The value of
Maximize Z(A)=6 and Maximize Z(B)=8. But there exist number of points in the shaded
region for which the value of the objective function is more than 8.For example, the point
(10, 12) lies in the region and the function value at this point is 70 which is more than 8.

Remark: An unbounded solution does not mean that there is no solution to the given
LPP, but implies that there exits an infinite number of solutions.

Exercise 1:

Use graphical method to solve the following LPP.

1. Maximize Z=7/4X1+3/2X2 2.MaximizeZ=X1+X2

Subject to: Subject to:

8 X1+5X2 < 320 X1+X2 < 1

4X1+5X2 < 20 -3X1+X2> 3

X1 > 15 X1, X2>0

X2>10

X1, X2 > 0

Answer: No feasible solution Answer: Unbounded solution

3. Maximize Z=3X1+2X2 4. MaximizeZ=6X1-4X2

Subject to: Subject to:

 X1-X2 < 1 2X1+4X2 < 4 X1+X2> 3
4X1+8X2> 16

X1, X2>2 X1, X2 >0

Answer: Unbounded solution Answer: Infeasible solution

Exercise2.

I. Solve the following LP problems using the graphical method.

1. Maximize Z=15X1-10X2 2.MaximizeZ=2X1+X2

Subject to: Subject to:

4X1+6X2 < 360 X1+2X2 < 10

3X1+0X2< 180 X1 +X2 < 6

0X1+5X2< 280 X1 - X 2 < 2

X1, X2 >0 X1 -2X2 < 1

Answer: X1=60 ,X2 =20 X 1, X2 >0

and Maximize Z=1,100 Answer: X1=4, X2 =2
and Maximize Z=10

3. Maximize .Z=10X1+15X2 4.Min.Z=3X1+2X2

Subject to: Subject to:

2X1+X2 < 26 5X1+X2 > 10 2X1+4X2< 56

X1 +X2 > 6

-X1+X2< 5 X1 + 4 X2 > 12

X1, X2 >0 X1, X2 >0

Answer: X1=4, X2 =2 Answer:X1=1,X2=5 and Maximize Z=230

and Minimize Z=13
 II.A manufacturer produces two different models; X and Y, of the same product .The raw
materials r1 and r2 are required for production. At least 18 Kg of r1and 12 Kg of r2 must
be used daily. Almost at most 34 hours of labor are to be utilized .2Kg of r1 are needed
for each model X and 1Kg of r1 for each model Y. For each model of X and Y, 1Kg of r2
is required. It takes 3 hours to manufacture a model X and 2 hours to manufacture a
model Y. The profit realized is $50 per unit from model X and $30 per unit from model
Y. How many units of each model should be produced to maximize the profit?

Answer: 10 units of model X, 2 units of model Y and the maximum profit is $ 560.

III.A manufacturing firm produces two machine parts P1and P2 using milling and
grinding machines .The different machining times required for each part, the machining
times available on different machines and the profit on each machine part are as given
below:

____________________________________________________________________

Manufacturing time Maximum time

Required (min) available per week (minimum)

Machine P1 P2

________________________________________________________________________

Lathe 10 5 25,000

Milling Machine 4 10 2000

Grinding Machine 1 1.5 450

Profit per unit ($) $50 $100

_____________________________________________________________________

Determine the number of pieces of P1 and P2to be manufactured per week to maximize
profit.
 Answer:X1=187.5,X2=125 and Maximize Z=21,875

2.5. Simplex Method

The Simplex method is an iterative or “step by step” method or

repetitive algebraic approach that moves automatically from one basic
feasible solution to another basic feasible solution improving the
situation each time until the optimal solution is reached at.

2.5.1. Standard forms of Linear Programming (LP) problems

The use of the Simplex method to solve an LP problem requires that the problem be
converted into its standard form. The standard form of the LP problem should have the
following characteristics:
 i. All the constraints should be expressed as equations by adding slack or
surplus and/or artificial variables.
ii. The right hand side of each constraint should be made non-negative; if
it is not, this should be done by multiplying both side of the resulting
constraint by -1.
iii. The objective function should be of the maximization type.

The standard form of LP problem is expressed as follow;

Optimize (Maximize or Minimize) Z= c 1 x 1+ ¿c x 2 2+ ¿…+ c n x n+¿ 0 s +0s

1 2+ ¿ …+0s
m
¿
¿
¿ ¿

Subject to the linear constraint:

a 11 x 1 +a 12 x 2+ …+a1 n x n+ s 1=b1

a 21 x 1+ a22 x 2 +…+a 2 n x n +s 2=b 2

. .

. .

. .

a m 1 x 1+ am 2 x2 + …+amn x n+ s m=b m

And x 1 , x 2, … x n , s 1 , s 2 … , s m ≥ 0

Where c= (c 1 , c2 … , c n) the coefficient of the objective function; x= ( x 1 , x 2 … , x n) decision

variables; b= (b 1 , b2 … , bn ) the limited resource available and s= ( s1 , s 2 … , sn) slack
variables.

In matrix notation the standard form is expressed as:

Optimize (Maximize or Minimize) Z=cx+0s

Subject to the linear constraint:

Ax+ s=b

X ,s ≥0

Where c= (c 1 , c2 … , c n) is the row vector, x=(x 1 , x 2 … , x n)T , b=(b1 ,b 2 … ,b n)T , and s= (

s1 , s 2 … , sn) are column vector.

Hence, this method is used, which can solve LP problems with any number of variable or
constraints it is geared towards solving optimization problems which have constraints of
less than or equal to type.

[ ]
a11 a12 … a1 n
a21 a22 … a2 n
And
… … …
am 1 am 2 amn

The above matrix is the m ×n matrix of coefficient of variables x 1 , x 2 … , x n in

the constraints.

Remarks; three types of additional variables, namely

 Slack variable (s)

 Surplus variable (-s), and
 Artificial variable (A)

Are added in the given LP problem to convert it in to the standard form for the following
reasons:

a. These variables allow as converting inequalities in to equalities, there by

converting the LP problem in to a form that is amenable to algebraic solution.
b. These variables permit as to make a more comprehensive economic interpretation
of a final solution.
 c. Help us to get an initial feasible solution presented by the column of the identity
matrix.

Types of Extra variableCoefficient of extra Presence of extra

constrain needed variables In the objective variable in initial
t function solution mix

Max Z Min Z

Less than or A slack variable is 0 0 Yes

equal to ≤ added

Greater than A surplus variable 0 0 No

or equal to is subtracted and
-M +M Yes
(≥) artificial variable
is added

Equal to (=) Only an artificial -M +M Yes

variable is added

The summery of the extra variable to be added in the given LP problem to convert it in to
standard form is given in the following table.

Remark: a slack variable represents unused resource, either in the form of time on a
machine, labor hour, money, warehouse space or any number of such resources in various
business problems. Since variable yields no profit, therefore such variable are added to
the original objective function with zero coefficients.

A surplus variable represents amount by which solution values exceed a resource. These
variables are also called negative slack variables. Surplus variables carry a zero
coefficient in the objective function.
2.5.2. The major steps and activities to solve LP model by using Simplex method

This method utilizes the property of a LP problem of having optimal solution only at the
corner point of the feasible solution space. It systematically generates corner point
solutions & evaluates them for optimality. The method stops when an optimal solution is
found. Hence, it is an iterative (repetitive) technique.

If we get more variables & less equation, we can set extra variables equal to zero, to
obtain a system of equal variables & equal equations. Such solution is called basic
solution.

The variables having positive values in a basic feasible solution are called basic variable
while the variables which are set equal to zero, so as to define a corner point are called
non-basic variables.

Slack variables are the fictitious variables which indicate how much of a particular
resource remains unused in any solution. These variables can’t be assigned negative
values. A zero value indicates that all the resources are fully used up in the production
process.

C jColumn denotes the unit contribution margin.

C j Row is simply a statement of the projective function.

Z j Row denotes the contribution margin lost if one unit is brought into the solution.
Hence, it represents the opportunity cost. (Opportunity cost is the cost of sacrifice i.e., the
opportunity foregone by selecting a particular course of action out of a number of
different available alternatives).

C j−Z j Row denotes the Net Potential contribution or the Net unit margin
potential, per unit.
The rules used under simplex method, for solving a linear programming
problem are as follows:-
1.Convert the LP to the following form:

Convert the given problem into Standard maximization Problem i.e.

minimization problem into a maximization one (by multiplying the
objective function by -1). All variables must be non-negative. All
right hand side values must be non-negative (multiply both sides
by -1, if needed). All constraints must be in ≤ form (except the non-
negativity conditions). No strictly equality or ≥ constraints are
allowed.

2.Convert all ≤ constraints to equalities by adding a different slack

variable for each one of them.
3.Construct the initial simplex tableau with all slack variables in the
Basic Variables. The last row in the table contains the coefficient of
the objective function (rowC j).
4.Determine whether the current tableau is optimal. That is: If all the
right hand side values are non-negative (called the feasibility
condition). If all elements of the last row, that is C j rows are non-
positive (called, the optimality condition)

If the answers to both of these two questions are yes, then stop.
The current tableau contains an optimal solution. Otherwise, go to
the next step.

5.If the current BASIC VRIABLES is not optimal, determine, which non
basic variable should become a basic variable and, which basic
variable should become a non basic variable. To find the new BASIC
VRIABLES with the better objective function value, perform the
following tasks:
 Identify the entering variable: The entering variable is the
one with the largest positive C j value (In case of a tie, select
the variable that corresponds to the left most of the
columns).
Identify the outgoing variable: The outgoing variable is
the one with smallest non-negative column ratio (to find the
column ratios, divide the RHS column by the entering
variable column, wherever possible). In case of a tie select
the variable that corresponds to the upper most of the tied
rows.
Generate the new tableau
a. Select the largest value of C j−Z j row. The column, under
which this value falls, is the pivot-column.
b. Pivot-row selection rule. Find the ratio of quantity to the
corresponding pivot-column coefficient. The pivot-row
selected is the variable having the least ratio.

Remark: Rows having negative or zero coefficients in the pivot-

column are to be neglected.

c. The coefficient, which is in both, the pivot-row & the pivot

column, is called the pivot-element or pivot-number.
d. Up-dating Pivot-row. Pivot-row, also called replaced rows,
are updated as under all elements of old-row divided by
Pivot-element. Now, in the basic activities column, write
the pivot-column variable in place of the pivot-row
variable. i.e.; the pivot-row variable is to be replaced by
the pivot-column variable.
e. Up-Dating all other rows. Update all other rows by
updating the formulae.

(Old−rowelement )−¿
 Correspondingpivotrowelement ¿=(Newelement )

Up-dating Z j∧C j −Z jrows. Each Z j , is obtained as the sum of the

products of the C j column coefficients multiplied by the corresponding
coefficient in the jth column. (i.e.) the Quantity column). It is then
subtracted from C j−Z j row values to get C j−Z j values. This pivoting is to
be repeated till no positive coefficients exist in the C j−Z j row, the
optimal solution is known.

2.5.3. Simplex algorism (Maximization Case)

What is a Standard Maximization Problem?

A Standard Maximization Problem is the one that satisfies the following

four conditions

1. The Objective function is to be maximized.

2. All the inequalities are of ≤ type.

3. All right hand constants are non-negative.

4. All variables are non-negative.

Dear learners let us consider some examples to test our

understanding of the solution algorithm that has been discussed so far.

Example 1

Smart Limited manufactures two types of cement which are sold under the brand name
quick and Tuff. Each product consumes the same raw materials but in varying
proportions. The following table depicts the amount of raw materials along with thei r
respective cost.

Raw material Price Quick Tuff

 type (Birr/tone)

N 600 350 200

A 400 50 100

P 400 50 100

I 200 550 600

1000k 1000k
g g

Quick can be blended @ 1000 kg /hour where as the blending rate for Tuff is 1250
kg/hour. Their respective selling prices are Birr. 1010 & Birr 845 You may assume the
variable coststo be Birr 500 per hour of plant production time. The maximum availability
of raw materials is:

Raw Material Max available

Types (kg)

N 1000

A 300

P 250

I 1800

Formulate as a linear programming model and find out the optimal units of quick & tuff
to be produced so as to maximize the profits.

Solution

Step I List the objective & constraint equations.

 Step II Introduce the slack variables

Step III Arrange in the form of initial table.

Step IV Find out the profit-margins from given sales price.

Step V Generate solutions.

The detailed solutions are as under:

Step I List the objective & constraint equations.

Maximize Cont-margin = 150 x 1+125 x 2

Subject to: 350 x 1+200 x 2 ≤1000

50 x 1+100 x 2 ≤ 250

550 x 1+600 x 2 ≤1800

Xj ≥0 for all j

How to calculate the Profit Margin?

Late first find the time taken to manufacture 1000 kg of both types. It is required for
allocating variable production costs to finished product.

∴ 1250 kg Tuff is made in one hour.

∴ 100 kg of Tuff = 0.8 hr.

∴Variable production cost for Tuff 0.8 x 500 = Rs. 400

∴Variable production cost for Quick Rs. 500 (∴ in 1 hr. 1000 kg is made)

Particulars Revenue/sales Quick (Rs.) Tuff (Rs.)

(given) 1,010 845
(-) variable costs: Direct Mat
N– 310 120
A– 20 40
P– 110 120
I– 20 40
Sub-total 360 320
Direct paid cost 500 400
Total var. cost 860 720
Contribution margin 150 125

Remarks

1. Given cost of 1000 kg of Birr 600

Given cost of 350 kg of = Birr 210 (for Quick)

Given cost of 200 kg of Birr 120 (for Tuff) etc.

2. Contribution margin represents the profit which remains if after deducting variable costs
from sales i.e.; It covers fixed costs & net profit i.e. it fixed cost = Birr 200 X five – 100
kg of quick are sold then the net profit = 5 x 150 –200 = Rs. 550

(Fixed cost do not vary with the output)

3. All calculation has been done to obtain the contribution margin (i.e.,
profit)

Let x1 = thousands of kg of quick to be produced.

x 2 = thousands of kg of tuff to be produced.

Now, we have to find those values of x 1& x2 for which the contribution
is maximum. Here, the constraint is the availability of raw material.
Hence, the problem is formulated as;

Maximize Z= 150 x 1+125 x 2

Subject to: 350 x 1+200 x 2 ≤1000
 50 x 1+100 x 2 ≤ 250 Hence, the problem has been formulated

550 x 1+600 x 2 ≤1800

x1 , x2 ≥ 0

Step II Introduce the slack variables:

Slack Variables:

A slack variable (s) is added to the left hand side of a < constraint to
covert the constraint inequality in to equality. The value of the slack
variable shows unused resource.A slake variable emerges when the
LPP (linear programming problem) is a maximization problem.

Slack variables represent unused resource or idle capacity. Thus, they

don’t produce any product and their contribution to profit is zero.

Note:

In general, whenever there are n variables and m constraints (excluding the non-
negativity), where m is less than n (m<n), n-m variables must be set equal to zero before
the solution can be solved algebraically.

a. Basic variables are variables with non-zero solution values.

Or: basic variables are variables that are in the basic solution. Basic
variables have 0 values in the C j−Z j row.

b. Non-basic variables are variables with zero solution values.

Or: non-basic variables are variables that are out of the solution.

==>n=5 variables (x1 ,x2, s1, s2, and s3) and m=3 constraints (Labor,
machine and marketing constraints), excluding non-negativity.
Therefore, n-m=5-3=2 variables(x1 and x2) are set equal to zero in the
1st simplex tableau. These are non-basic variables. 3 Variables (s1, s2,
and s3) are basic variables (in the 1 st simplex tableau) because they
have non-zero solution values.

Converting inequalities into equalities by using slack-variable

Maximize Cont-margin = 150 x 1+125 x 2

Subject to: 350 x 1+200 x 2 + s1=1000

50 x 1+100 x 2 +s 2=250

550 x 1+600 x 2 + s3=1800

si X j≥ 0 foralliandj

Note. We have dropped: 50 x 1+100 x 2 ≤ 300 as it is already contained in 50 x 1+100 x 2 ≤ 250

Slack can’t be larger than the constant. On right hand side (RHS) (i.e.
S l=1000 , S 2=250 etc) It is to be so, and then some other variable must be
negative for equality to exist, which is not possible.

(2) Rewriting as:

Maximize Cont-margin = 150 x 1+125 x 2 +0 s 1 +0 s 2 +0 s 3

Subject to: 350 x 1+200 x 2 + s1 +0 s 2 +0 s 3=1000

50 x 1+100 x 2 +0 s 1 +s 2 +0 s 3=250

550 x 1+600 x 2 +0 s 1 +0 s 2 +s 3=1800

si∧ X j ≥ 0 foralliandj
C j(birr) Basic 15 12 0 0 0 (Birr.) Min ratio
0 5
Activiti S S S Qty. RHS/x1 Living
variable
es x1 x2 1 2 3 RHS (Pivot row)
)

0 S1 35 20 1 0 0 1000 1000/350=2.857

0 0

0 S2 50 10 0 1 0 250 250 /50=5

0
Pivot point Entering variable (Pivot Column)
0 S3 55 60 0 0 1 1800 1800/550=3.273
0 0

Zj(Rs .) 0 0 0 0 0 0

Cj−Zj 15 12 0 0 0
0 5

Pivot Column = x1 (Largest value ofCj – Zj )

Pivot row the lowest value in the min ratio column that is 2.875

∴ S1is the pivot- row

Pivot element = 350, the intersection of the pivot raw and

pivot column

Up-dating Pivot-row
 1000 350 200 0.571∧1
=2.857 , =1 , = =0.0029
350 350 350 350

nd
Make the pivot-row of 2 tableau:

Cj Basic Birr 15 125 0 0 0

Act. Qty. 0
Bir x2 S1 S S

r x1 2 3

15 x1 2.85 1 0.57 0 .00 0

0 71 14 29 0

0 S2

0 S3

(Pivot column variable in place of Pivot row variable)

S2 row is up-dated as follows:

Oldrowelement−CorrespondingPivotcolumnelement ×UpdatedcorrespondingPivotrowelement =NewS 2

Old (Corresponding Updated = New S 2

Row Pivot corresponding raw

Elemen column element Pivot row element element

t- x

250 - ( 50 x 2.8571) = 107.145

50 - (50 x 1) = 0

100 - (50 x 0.5714 = 71.43

 0- (50 x 0.0029) = -0.145

1- (50 x 0) =1

0- (50 x 0) =0

S3 row is similarly updated:

Old (Corresponding Updated = New S 2

Row Pivot corresponding raw

Elemen column element Pivot row element element

t- x

1800 - (550 x 2.8571) = 228.595

550 - (550 x 1) = 0

600 - (550 x 0.5714) = 285.73

0- (550 x 0.0029) = -1.595

0- (550 x 0) =0

1- (550 x 0) =1

Complete 2nd tableau

Cj Basic Act. Birr 15 125 0 0 0

Qty. 0
Bir x2 S1 S S

r x1 2 3
 15 x1 2.857 1 0.57 0.00 0 0
0 14 29

0 S2 107.1 0 71.4 - 1 0
45 3 0.14
5

0 S3 228.5 0 285. 1.59 0 1

95 73 5

- Zj(Birr) 428.5 15 85.7 0.43 0 0

5 0 1 5

- Cj−Zj ¿ -- 0 39.2 - 0 0
9 0.43
5

Zjiscalculatedasunder :
ZjvalueforQTYColumn=150 x 2.857+ 0 x 107.145+0 x 228.595=428.55
Forx 1=150 x 1+0 x 0+ 0 x 0=150
x 2=150 x 0.5714 +0+0=85.71
S 1=150 x 0.0029+ 0+0=0.435
S 2=0
S 3=0

Now perform Cj – Zj to get Cj – Zj row values.

The positive value of 39.29 in Cj – Zj ⇒ it is not the optimal solution

hence, once again pivoting is required.

Developing 3rd tableau

Now, pivot column x2 (Largest value of – Zj ), Pivot row = S3

Pivot element = 285.73

Updating Pivot row (S3; Old row element ÷ Pivot number)

Cj Basic Birr 15 125 0 0 0

Activities Qty. 0
Bir x2 S1 S S

r x1 2 3

15 x1 2.857 1 0.57 0.00 0 0

0 14 29

0 S2 107.1 0 71.4 - 1 0
45 3 0.14 Leaving
variable
5

0 S3 228.5 0 285. 1.59 0 1

95 73 5

- Zj(Birr) 428.5 15 85.7 0.43 0 0

5 0 1 5

- Cj−Zj ¿ -- 0 39.2 - 0 0
9 0.43
5

Entering
Completed 3rd variable
Tableau

Cj Basic Birr 15 12 0 0 0
Activities Qty. 0 5
Bir S1 S S3

r
 x1 x2 2

15 x1 2.4 1 0 0.006 0 -
0 0.002

0 S2 50 0 0 0.225 1 -0.25

12 X2 0.8 0 1 - 0 0.003
5 0.005 5
6

- Zj(Birr) 460 15 12 0.02 0 0.137

0 5 5

- Cj−Zj ¿ -- 0 0 -0.02 0 -
0.137
5

Note

(1)x 1rowisup−datedas :

2.857−¿

1−(0.5714 x 0)=1

0.5714 – (0.5714 x 1)=0

0.0029 – ( 0.5714 x – 0.0056 ) =0.006

0−(0.5714 x 0)=0

0−(0.5714 x 0.0035)=−0.002

(2)S 2 rowisup datedas :

 107.145 – (71.43 x 0.8)=50

0−(71.43 x 0)=0

71.43 – (71.43 x 1)=0

−0.145 – (71.43 x−0.0056)=0.255

1−(71.43 x 0)=1

0−(71.43 x 0.0035)=−0.25

Since no positive co-efficient exists in the C1– z 1 row, this is the

optimal solution.

X1 = 2.4X2 = 0.8

Z1= 460.

Example 2

X Ltd. Produces two products p1, p2 having profit of Rs. 4 $ Rs. 3

each p1, p2 require 4 hrs. & 2 hours of machining respectively, the

total available machining time is 10 hours. P1, p2 consume 2 units &

8/3 units of raw material respectively subject to a total of maximum 8

units. Any no. of p2 j can be produced & sold but the no. of p 1 must

not be more than 6 Formulate as a (P model &solve by the simplex

method.)

Solution
Maximise=4 x 1+3 x 2+ os 2+os 3

Subject ¿:
4 x 1+2 x 2+ s 1+0 s 2+0 s 3=10

8
2 x 1+ x 2 +0 s 1 +s 2+ 0 s 3=8 x 1 ; x 1 , x 2 ≥ 0
3

x 1+ ox 2+0 s 1+0 s 2+s 3=6

(Birr) Basic Qty. 4 3 0 0 0 Min
activities ratio
Birr x1 x2 s1 s2 s3
Qty./ x1

0 S1 10 4 2 1 0 0 10/4=
2.5

0 S2 8 2 8/3 0 1 0 8/2= 4

0 S3 6 1 0 0 0 1 6/1= 6

Zj(Birr) 0 0 0 0 0 0

Cj−Zj(Birr) 4 3 0 0 0

Pivot Column = x1 because in the Cj−Zj raw x1 have the highest value.

Pivot Row =S1 it have the lowest contribution (2.5)

Pivot Element = 4 the intersection of pivot raw and pivot column

Up-dating S2 Updating s3row Updating Zj

row raw

( )
8− 2 ×
5
2
=3 ( )
8− 2 ×
5 7
=
2 2
5
Qty.4× =10
2

2− ( 2×1 )=0 1− (1 ×1 ) =0 X1=4

8
3 ( )
1 5
− 2× =
2 3 ( 12 )=−1
0− 2 ×
1
X2=4× =2
2

( 41 )=−12
0− 2 × ( 14 )=−14
0− 1 ×
1
S1=4× =1
4

1− (2 × 0 )=1 0−( 1× 0 )=0 S2=0

0−( 2× 0 )=0 1− (1 × 0 )=1 S3=0

 Second tableau:

Cj (Birr Basic Qty. 4 3 0 0 0 Min ratio

) activities Qty./ x1
Birr x1 x2 s1 s2 s3

4 x1 5/2 1 ½ - 0 0 5/2÷1/2=
1/2 5

0 S2 3 0 5/ 1/ 1 0 3÷5/3=
4 9/5
3
0 S3 7/2 0 - 1 1 7/2÷-1/2=
1/2 -7

Zj(Birr) 10 4 2 - 1 0
1/4

Cj−Zj(Birr) 0 1 1 1 0

Pivot row = s2 the smallest value in the min ratio column (9/5). Don’t
take negative and zero value.

Updating pivot row:

3÷5/3=9/5, 0, 1, -1/2÷5/3=-3/10, 1/5÷3=3/5, 0

Up-dating x1 Updating s3row Updating Zj raw

row

(
5 1 9 8
− × =
2 2 5 5 ) 2
− (
7 −1 9 22
× =
2 5 5 ) 8 3× 9
Qty.4× +
5 5
=1

1.6
1− ( 12 ×0)=1 0− 0×− ( 1
2)=0

1 1
( )
− ×1 =0
2 2
−1 −1
2
−
2
×1 ( )
(
1 1 1 2
− × =
4 2 4 5 ) 4
−
2 (
−1 −1 −3 −2
×
4
=
5 )
0−( 12 × 35 )= −310 0− ( −12 × 35 )= 103
0− ( 12 × 0)=0 1− ( −12 ×0)=1
 3rd Tableau
Cj (Birr Basic activities Qty. 4 3 0 0 0
)
Birr x1 x2 s1 s2 s3

0 x1 8/5 1 0 - 2/5 -3/10

1/2

3 x2 9/5 0 1 ¼ - 3/5
3/10

4 S3 22/5 0 0 -2/5 3/10

Zj(Birr) 59/5 4 3 - 7/10 3/5

1/4

Cj−Zj(Birr) 0 0 1 - -3/5
7/10

There are no positive values in Cj−Zjrow, optional solution is reached.

Hence X1 = 8/5, X2 =9/5 & max. = 59/5 is the answer.

Example 3:

Solve the problem using the simplex approach

Maximize Z=300 x 1+250 x 2

Subject ¿:

2 x 1+ x 2< 40( Labor )

x 1+3 x 2<45( Machine)

x 1<12( Marketing)

x 1 , x 2> 0

Solution

Step 1 Formulate LPP Model

Step 2 Standardize the problem

i.e. Convert constraint inequality into equality form by introducing a

variable called Sack variable.
Slack Variables:

A sack variable(s) is added to the left hand side of a < constraint to

covert the constraint inequality in to equality. The value of the slack
variable shows unused resource.

A slake variable emerges when the LPP (linear programming problem) is a

maximization problem.

Slack variables represent unused resource or idle capacity. Thus, they don’t
produce any product and their contribution to profit is zero.

Slack variables are added to the objective function with zero coefficients.

Let that, s2 and s3 be unused labor, machine and marketing hours,

respectively.

Let that s1, s2, and s3 are unused labor, machine and marketing hours
respectively.

Maximize Z=300 x 1+ 250 x 2 +0 s1 +0 s 2 +0 s 3

Subject to:

2 x1 + x 2 +s 1 +0 s 2 +0 s 3=40

x 1+ 3 x 2 +0 s1 + s2 +0 s 3=45
Standard form

x 1+ 0 s 1+ 0 s 2+ s 3=12

x 1 , x 2 , s1 , s 2 , s3 >0

Step 3 Obtain the initial simplex tableau

To represent the data, the simplex method uses a table called the
simplex table or the simplex matrix.

==> In constructing the initial simplex tableau, the search for of the
optimal solution begins at the origin. Indicating that nothing can be
produced;

Thus, first assumption, No production implies that x1 =0 and x2=0

==>2 x1 + x 2 +s 1 +0 s 2 +0 s 3=40==> x 1+ 3 x 2 +0 s1 + s2 +0 s 3=45

2 ( 0 ) +0+ s 1+ 0 s 2+0 s3 =40 0+3 (0)+ 0 s 1+ s 2+ 0 s 3=45

s1=40– Unused labor hours. s 2=45 – Unused machine hrs .

 ==> x 1+ 0 s 1+ 0 s 2+ s 3=12

0+ 0 s 1+0 s2 + s3 =12

s3=12 – Unused Marketing hours.

Note:

In general, whenever there are n variables and m constraints

(excluding the non-negativity), where m is less than n (m<n), n-m
variables must be set equal to zero before the solution can be solved
algebraically.

c. Basic variables are variables with non-zero solution values.

Or: basic variables are variables that are in the basic solution. Basic
variables have 0 values in the C j−Z j row.

d. Non-basic variables are variables with zero solution values.

Or: non-basic variables are variables that are out of the solution.

==>n=5 variables (x1 ,x2, s1, s2, and s3) and m=3 constraints (Labor,
machine and marketing constraints), excluding non-negativity.

Therefore, n-m=5-3=2 variables(x1 and x2) are set equal to zero in the
1st simplex tableau. These are non-basic variables. 3 Variables (s1, s2,
and s3) are basic variables (in the 1 st simplex tableau) because they
have non-zero solution values.

Step 3 Construct the initial simplex tableau. Dear learners

alternatively you may solve LP simplex method by using the following
method (you may solve the problem by using the following table
arrangement).
 Slack variables columns
Initial simplex tableau

Solution quantity column

Real or decision variables column
Basic or Solution variable column
Profit per unit column

300 250 0 0
Cj Profit per unit
0 Row

X1 X2 S1 S2
SV Q
S3 R1

Constraint equatio
2 1 1 0
0 S1 40
0
R3
1 3 0 1 45 Gross Profit row
R2
0 S2
0
Net Profit row /Indi
1 0 0 0
0 S3 12
1

0 0 0 0
Zj 0
0

300 250 0 0
C j - Zj
0

Step 4: Choose the “incoming” or “entering” variables

Note:

The entering variable is the variable that has the most positive value in the C j−Z j row
also called as indicator row. Or the entering variable is the variable that has the highest
contribution to profit per unit.

a. X1in our case is the entering variable

b. The column associated with the entering variable is called key or pivot column
( X1columnin our case )

Step 5: Choose the “leaving “or “outgoing” variable

==> In this step, we determine the variable that will leave the solution
for X1 (or entering variable)

Note: The row with the minimum or lowest positive (non-

negative) replacement ratio shows the variable to leave the
solution.
Replacement Ratio (RR) or min ratio =
Solution Quantity (Q)
Corresponding values∈ pivot column
 Note: RR>0

 The variable leaving the solution is called leaving variable or

outgoing variable.
 The row associated with the leaving variable is called key or
pivot row (s3 columnin our case)
 The element that lies at the intersection of the pivot column and
pivot row is called pivot element(No 1 in our case)

Step 6: Repeat step 3-5 till optimum basic feasible solution is

obtained.

Or: repeat step 3-5 till no positive value occurs in the C j−Z j row.

Note:

 Divide each element of the pivot row by the pivot element to find
new values in the key or pivot row.
 Perform row operations to make all other entries for the pivot
column equal to zero.

2nd simplex tableau

300 250 0 0
Cj
0

X1 X2 S1 S2
SV Q
S3

0 1 1 0 16
0 S1 R’1=R1-2R2
-2

0 3 0 1 33
0 S2 R’2=R2-R3
-1

30 1 0 0 0 12
X1 R’3=R3
0 1

300 0 0 0
Zj 3600
300

0 250 0 0
C j - Zj
-300
 3rd simplex tableau

300 250 0 0
Cj
0

X1 X2 S1 S2
SV Q
R’’1=R’1-R’2 S3

R’’2=R2/3 0 0 1 -1/3
0 S1 5
R’’3=R’3 -5/3

25 0 1 0 1/3
X2 11
0 -1/3

30 1 0 0 0
X1 12
0 1
Since
300 250 0 250/3 all the
Zj 6350
650/3

0 0 0 -250/3
C j - Zj
- 650/3

C j−Z j< 0optimal solution is reached at.

Therefore, X1=12, X2=11, S1=5 and Max Z=6350

2.5.4. Minimization Problems

 Minimize Z with inequalities of constraints in “> “form

There are two methods to solve minimization LP problems:

1. Direct method/Big M-method/

 Using artificial variables

2. Conversion method

 Minimization by maximizing the dual

 Surplus Variable (-s):
 A variable inserted in a greater than or equal to constraint to create equality. It
represents the amount of resource usage above the minimum required usage.
 Surplus variable is subtracted from a > constraint in the process of converting
the constraint to standard form.
 Neither the slack nor the surplus is negative value. They must be positive or
zero.

Example:

1. 2x1+x2 < 40 ==>is a constraint inequality

x1= 12 and x2= 11==>2x1+x2+s= 40 ==>2(12)+11+s= 40

==>s=5 unused resource

2. 5x1+3x2 < 45

x1= 12 and x2= 11==>5x1+3x2+s= 45 ==>5(12)+3(11)+s= 45

==>s=0unused resource (No idle resource)

3. 5x1+2x2 >20
 x1= 4.5 and x2= 2==>5x1+2x2- s= 20 ==>5(4.5)+2(2)-s= 20

==>s=6 unused resource

4. 2x1+x2 >40

x1= 0 and x2= 0(No production)==> 2x1+x2- s= 40 ==>2(0)+0-s= 20

==>s=-20(This is mathematically unaccepted)

Thus, in order to avoid the mathematical contradiction, we have to add

artificial variable (A)

 Artificial variable (A):

Artificial variable is a variable that has no meaning in a physical sense but

acts as a tool to create an initial feasible LP solution.

Note:

Type of constraint To put into standard form

< --------------------------------------------- Add a slack variable

= ---------------------------------------------Add an artificial variable

> ---------------------- Subtract a surplus variable and add a slack variable

2.5.4.1. Big M-method

/Charnes Penalty Method/

The Big-M Method is a method which is used in removing artificial

variables from the basis .In this method; we assign coefficients to
artificial variables, undesirable from the objective function point of
view. If objective function Z is to be minimized, then a very large
positive price (called penalty) is assigned to each artificial variable.
Similarly, if Z is to be maximized, then a very large negative price (also
called penalty) is assigned to each of these variables.

Following are the characteristics of Big-M Method:

a. High penalty cost (or profit) is assumed as M

b. M is assigned to artificial variable A in the objective function Z.
c. Big-M method can be applied to minimization as well as
maximization problems with the following distinctions:
i. Minimization problems

-Assign +M as coefficient of artificial variable A in the

objective function Z

ii. Maximization problems:

-Here –M is assigned as coefficient of artificial variable A in the

objective function Z

d. Coefficient of S (slack/surplus) takes zero values in the objective

function Z
e. For minimization problem, the incoming variable corresponds to
the highest negative value ofC j−Z j .
f. Solution is optimal when there is no negative value of C j−Z j .
(For minimization case)

Example:

Minimize Z=25x1 +30x2

Subject to:

20x1+15x2 > 100

2x1+ 3x2 > 15

x1, x2> 0
 Solution

Step 1 Standardize the problem

Minimize Z=25x1 +30x2 +0s1+0s2 +MA1+MA2

Subject to:

20x1+15x2- s1+A1 = 100

2x1+ 3x2 –s2+A2 = 15

x1, x2 , s1, s2 ,A1 ,A2 > 0

Step 2 Initial simplex tableaus

The initial basic feasible solution is obtained by setting x 1= x2= s1=

s2=0

No production, x1= x2= s1=0==>20(0) +15(0) - 0+A1 = 100 ==> A1 =

100

x1= x2= s2=0==>0(0)+3(0) - 0+A2 =15==> A2 = 15

Initial simplex tableau

Cj 25 30 0 0 M
M

X1 X2 S1 S2 A1
SV Q RR (min ratio)
A2

20 15 -1 0 1 100/20=5
M A1 100
0
15/2=7.5
2 3 0 -1 0
M A2 15
1

115
Zj 22M18M -M -MMM
M

C j - Zj 25 -22M30- 18MMM 0 0
 X1 is entering variable because in the C j – Z j row X1 have the highest
negative value. And A1 is leaving or outgoing variable because the RR is
lowest positive in the A1 row.

Note:

Once an artificial variable has left the basis, it has served its purpose
and can therefore be removed from the simplex tableau. An artificial
variable is never considered for re-entry into the basis.

2nd Simplex Tableau

Cj 25 30 0 0
M

X1 X2 S1 S2 Q
SV
A2
R’1=R1/20
1 3/4 -1/20 0
25 X1 5
0
R’2=R2-2 R’
0 3/2 1/10 -1
M A2 5
1

125+5
Zj 25 75/4+3/2M -5/4+1/10M -MM
25 30 0 M
Cj
0
0 45/4-3/2M 5/4-1/10 MM
C j - Zj
X1 0 X2 S1
SV Q
S2

1 0 -1/10
25 X1 5/2 3rd
1/2
Simplex
0 1 1/15 - Tableau
30 X2 10/3
2/3

25 30 -1/2
Zj 162.5
-15/2

0 0 1/2 R’’1=R’1-
C j - Zj
15/2 3/4R’’2
 R’’2=R’2/3/2

C j−Z j ≥ 0==>Optimal solution is reached

X1=5/2

X2=10/3 and Minimum Z=162.5

Note:

As long as an “A” variable is available in the solution variable column,

the solution is infeasible.

Example 2. Use the penalty (Big-M) method to solve the following LPP

Min Z=5x1 +3x2

Subject to:

2x1+4x2 < 12

2x1+ 2x2 = 10

5x1+ 2x2 > 10

x1, x2> 0

Solution

Minimize Z=5x1 +3x2 +0s1+0s2 +MA1+MA2

Subject to: If no production

 2x1+4x2+s1 = 12 ==>x1 =x2=0==>s1=0 (Solution Value in the initial
simplex tableau) 2x1+2x2 +A1 =10 ==>x1 =x2=0==>A1 =15 (Solution
Value in the initial simplex tableau)

5x1+2x2 –s2 +A1=10 ==>x1=x2=s2=0==>A2=10(Solution Value in the

initial simplex tableau)

x1, x2 , s1, s2 ,A1 ,A2 > 0

Initial Simplex tableau

Cj 5 3 0 0 M
M
RR
SV X1 X2 S1 S2 A1 Q
6
A2
5
0 S1 2 4 1 0 0 12
0 2

M A1 2 2 0 0 1 10
Cj 5 3 0 0
0
M
M A2 5 2 0 -1 0 10
SV X1 X2 S1 S2 Q
1
2nd A1
Zj 7M4M 0 MMM 20 M
0 S1 0 16/5 1 2/5 8
C j - Zj 5 -7M3-
0 4M0 -M 0 0

simplex M A1 0 6/5 0 2/5 6 tableau

1

5 X1 1 2/5 0 -1/5 2
0

Zj 5M6/5M +2 0 2/5M -1 M 10+6

M

C j - Zj 0 -6/5M +1 0 -
2/5M+1 0
 3rd simplex tableau

Cj 5 3 0 0
M

X1 X2 S1 S2 RR
SV Q
A1 20

0 1 5/16 1/8
3 X2 2.5 12
0
-
0 0 -3/8 1/4
M A1 3
1

Type
0 0 -1/8 -1/4
5 X1 1
0

12.5+3
Zj 53 -3/8M +5/6 M/4-7/8 M
M

0 0 3/8M -5/6
C j - Zj
-M/4+7/8 0

equation here.
 4th Simplex tableau

5 3 0
Cj
0

X1 X2 S1
SV Q
S2

0 1 1/2
3 X2 1
0

0 0 -3/2
0 S2 12
1

0 0 -1/2
5 X1 4
0

Zj 53 -1 0 23
X1=4, X =1,
2

S1=0, 0 0 1 S2=12 and

C j - Zj
0 Minimize
Z=23

Exercise

Find the optimal solution using Simplex method

1. MinZ=10 x 1+5 x 2

Subjectto:

2 x 1+5 x 2 ≥ 150

3 x 1+ x 2≥ 120

x1, x2≥0

Ans : x 1=450/13 , x 2=210/13 andMinZ=$ 540

2. Min Z=4 x 1+5 x 2

Subject ¿:
 x 1+2 x 2> 80

3 x 1+ x 2>75

x 1 , x 2> 0

Ans : x 1=14 , x 2=33∧Min Z=$ 221

2.8.5. Special Cases in Simplex Method

1. Mixed constraints

Example

Max Z=6x1 +8x2

Subject to:

x2< 4

x1 + x2 = 9

6x1+ 2x2 >24

x1, x2> 0

 Standard form

Maximize .Z=6x1 +8x2 + 0 s1 +0 s2+ 0 s3-M A2- M A3

St:

x2+ s1 =4

x1+ x2+ A2 =9
Standard form
6x1+2x2 - s3 + A3 =24

All Variables > 0

Initial simplex tableau

 6 8 0 0 -M
Cj
-M

X1 X2 S1 S3 A2
SV Q
A3

0 1 1 0 0
0 S1 4
0

1 1 0 0 1
-M A2 9
0

6 2 0 -1 0
-M A3 4
1

-7M - 3M 0 +M
Zj 24
-M -M

7M +6 3M+8 0 -M
C j - Zj
0 0

Answer: At the 4th tableau: X1 =5, X2 =4 , S3 =14 and Maximize Z=62

Note:
For the initial basis, use artificial variables for constraints that have
them. Otherwise, use a constraint slack variable. Hence, surplus
variables will not appear in an initial solution.

2. Two incoming variables

/ Or Tie for entering variables/

In order to break this tie, the selection for the key column (entering variable) can be made
arbitrary. However; the number of solution can be minimized by adopting the following
rules:

1. If there is a tie between two decision variables, then the selection can be made
arbitrary.
2. If there is a tie between a decision variable and a slack (or surplus) variable, then
select the decision variable to enter into basis first.
3. If there is a tie between slack or surplus variable, then selection can be made
arbitrary.

3. Alternate Optimal Solutions

If a non- basic variable corresponding to which C j−Z j =0 the problem have multiple
optimal solution.

Let us solve a small example:

Example1

As before, we add slacks, and we solve by the Simplex method, using

tableau representation.

Max Z =6 x 1+ 4 x 2

Subject to: 2 x1 +3 x 2 ≤ 30

3 x 1+2 x 2 ≤ 24

x 1+ x2 ≥ 3

x 1∧x 2 ≥ 0
Write it in standard form

As before, we add slacks s1, s2 and surplus s 3∧artificial A 1, and we solve by

the simplex method, using tableau representation.

Max Z =6 x 1+ 4 x 2+0 s1 +0 s2- MA 1

Subject to: 2 x1 +3 x 2 +s 1=30

3 x 1+2 x 2 + s 2=24

x 1+ x2 + A1 =3

x 1 , x 2 , s1 , s 2 , s3 + A1 ≥ 0

The optimal solution for this LP problem is presented in the following

table

Cj 6 4 0 0 0 RHS

BV x1 x2 s1 s2 s3

0 s1 0 5/3 1 - 0 14
2/3

0 s3 0 -1/3 0 1/3 1 5

6 x1 1 2/3 0 1/3 0 8

Zj 6 4 0 2 0 48

C j−Z j 0 0 0 -2 0

The optimal solution is x1=8, x2=0, s1=14, and s3= 5 and max Z=48

But the C j−Z j row shows a value zero corresponding to a non basic variable X 2. Thus
an alternative optimal solution can also be obtained by entering variable X 2 in to the basis
and removing S1 from the basis.
 Alternative solution

Cj 6 4 0 0 0 RHS

BV x1 x2 s1 s2 s3

0 x2 0 1 3/5 -2/3 0 42/5

0 s3 0 0 1/5 1/5 1 39/5

6 x1 1 0 -2/5 3/5 0 12/5

Zj 6 4 0 2 0 48

C j−Z j 0 0 0 -2 0

The optimal solution is x1=12/5, x2=42/5, s1=0, and s3= 39/5 and max Z=48

3. Unbounded solution

In maximization LP problem, if C j−Z j >0 (C j−Z j <0 for a minimization case) for a
column not in the basis and all entries in this column are negative, then for determining
key row, we have to calculate minimum ration corresponding to each basic variable have
negative or zero value in the denominator.

Negative value in denominator cannot be considered, as it would

indicate the entry of a non basic variable in the basis with a negative
value (an infeasible solution will occur). A zero value in the
denominator would result a value of + ∞ . This implies that the entering
variable could be increased indefinitely with any of the current basic
variables being removed from the basis.

Example solve the following LP problem

Maximize Z= 3 x 1+5 x 2
 Subject to x 1−2 x2 ≤ 6

x 1 ≤ 10

x2 ≥ 1

x 1∧x 2 ≥ 0

add slack s1, s2 and surplus s 3∧artificial A 1, and we solve by the simplex
method, using tableau representation.

Maximize Z= 3 x 1+5 x 2+0 s1 +0 s2 +−MA 1

Subject to x 1−2 x2 + s1 =6

x 1 ≤ s 2=10

x 2−s 3+ A 1=1

x 1 , x 2 , s1 , s 2 , s3∧ A 1 ≥ 0

The initial solution to this problem is presented below

Cj 3 5 0 0 0 -M RHS Min
ratio
BV x1 x2 s1 s2 s3 A1

0 s1 1 -2 1 0 0 0 6 ___

0 s2 1 0 0 1 0 0 10 ___

-M A1 0 1 0 0 -1 1 1 1

Zj 0 -M 0 0 M -M 48

C j−Z j 3 5+M 0 0 -M 0

Variable X2 enter in to the basis and variable A1 leaves the basis

Cj 3 5 0 0 0 -M RHS Min
 BV x1 x2 s1 s2 s3 A1 ratio

0 s1 1 -2 1 0 0 0 6 ___

0 s2 1 0 0 1 0 0 10 ___

-M A1 0 1 0 0 -1 1 1 1

Zj 0 -M 0 0 M -M -M

C j−Z j 3 5+M 0 0 -M 0

Second table

Cj 3 5 0 0 0 -M RHS Min
ratio
BV x1 x2 s1 s2 s3 A1

0 s1 1 0 1 0 -2 2 6 ___

0 s2 1 0 0 1 0 0 10 ___

5 x2 0 1 0 0 -1 1 1 1

Zj 0 5 0 0 -5 5 5

C j−Z j 3 0 0 0 5 -M-5

Variable s3 should inter to the basis but it may be noted that coefficient
in the S3 column ar all negative or zero. This indicates that S 3 cannot
be entered in to the basis. However, the value of S 3 can be increased
infinitely without removing any one of the basic variable.

Infeasible solution
In final simplex table if at least one artificial variable appear with a
positive value, no feasible solution exists, because it is not possible to
remove such an artificial variable from the basis using the simplex
algorithm.

Example solving the following LPP

Max Z =6 x 1+ 4 x 2

Subject to: x 1+ x2 ≤5

x2≥ 8

x 1∧x 2 ≥ 0

By adding slack, surplus and artificial variable, the LPP becomes

Max Z =6 x 1+ 4 x 2+0 s1 +0 s2- MA 1

Subject to: x 1+ x2 + s1=¿

x 2 + s 2+ A 1=8

x 1 , x 2 , s1 , s 2∧ A1 ≥ 0

The second table of the solution shows

Cj 6 4 0 0 -M RHS

BV x1 x2 s1 s2 A1

4 x2 1 1 1 0 0 5

-M A1 -1 0 -1 -1 1 3

Zj 4+M 4 4+M M -M 20-3M

C j−Z j 2-M 0 -4-M -M 0

Since the C j−Z j ≤ 0 the solution is optimal. But the solution not feasible
for the given problem since it has X 1=0, X2=5 (recall that in the second
constraint X2≥ 8). The fact that artificial variable A1 =3 is in the solution
also indicates that the final solution violates the second constraint (X 2≥
8) by 3 unites.