INTRODUCTION

 It is an optimization method applicable for the solution of

optimization problem where objective function and the constraints
are linear.
 It was first applied in 1930 by economist, mainly in solving resource
allocation problem During World War II, the US Air force sought
more effective procedure for allocation of resources George B.
Dantzig, a member of the US Air Force formulate general linear
problem for solving the resources allocation problem.
“A Linear Programming Problem is one that is concerned with finding the
optimal value (maximum or minimum value) of a linear function (called
objective function) of several variables (say x and y), subject to the conditions
that the variables are non-negative and satisfy a set of linear inequalities
(called linear constraints). The term linear implies that all the mathematical
relations used in the problem are linear relations while the term
programming refers to the method of determining a particular programme or
plan of action.”
ESSENTIALS OF LINEAR PROGRAMMING MODEL

For given problem situation, there are certain essential

a

conditions that need to be solved by using linear programming.

1. Limited resources : limited number of labour, material equipment and
finance

2. Objective: refers to the aim optimize (maximize the profits

to
or minimize the costs).

3. Linearity: increase in labour input will have a proportionate

increase in output.

4. Homogeneity: the products, workers'efficiency, and machines are

assumed to be identical.

5. Divisibility: it is assumed that resources and products can be

divided into fractions. (in case the fractions are not

possible, like production of one-third of a

computer, a modification of linear programming
called integer programming can be used).
 FORMULATION OF LINEAR PROGRAMMING

Formulation of linear programming is the representation of problem

situation in a mathematical form. It involves well defined decision
variables, with an objective function and set of constraints.
Objective function:

The objective of the problem is identified and converted into a suitable objective
function. The objective function represents the aim or goal of the system
(i.e., decision variables) which has to be determined from the problem.
Generally, the objective in most cases will be either to maximize resources or
profits or, to minimize the cost or time.
Constraints:
When the availability of resources surplus, there will be no problem in making
are in
decisions. But in real life, organizations normally have scarce resources within which
the job has to be performed in the most effective way. Therefore, problem situations are
within confined limits in which the optimal solution to the problem must be found.

Non-negativity constraint

Negative values of physical quantities are impossible, like producing negative number of
chairs, tables, etc., so it is necessary to include the element of non-negativity as a
constraint
 Solution
Decision variables completely describe the decisions to be made (in this case, by
Manager). Manager must decide how many corrugated and ordinary cartons should be
manufactured each week. With this in mind, he has to define:

xl be the number of corrugated boxes to be manufactured.

x2 be the number of carton boxes to be manufactured

Objective function is the function of the decision variables that the decision maker
wants to maximize (revenue or profit) or minimize (costs). Manager can concentrate on
maximizing the total weekly profit (z).
Here profit equals to (weekly revenues) - (raw material purchase cost) - (other variable costs).
Hence Manager's objective function is:
Maximize Z = 6X₂+ 4x2
Constraints show the restrictions on the values of the decision variables. Without

constraints manager could make a large profit by choosing decision variables to be very
large. Here there are three constraints:
Available machine-hours for each machine
Time consumed by each product

Sign restrictions are added if the decision variables can only assume nonnegative values
(Manager can not use negative negative number machine and time never negative number)
All these characteristics explored above give the following Linear
Programming (LP) problem

max z = 6x, + 4x2 (The Objective function)

s.t. 2x, + 3x₂ ≤ 120 (cutting timeconstraint)
2x, + X₂ ≤ 60 (pinning constraint)
X, X₂≥0 (Sign restrictions)

A value of (x,x₂) is in the feasible region if it satisfies all

the constraints and sign restrictions.

This type of linear programming can be solve by two methods

1) Graphical method
2) Simplex algorithm method
 Graphic Method

Step 1: Convert the inequality constraint as equations andfind co-ordinates ofthe line.

Step 2: Plot the lines on the graph.

(Note: If the constraint is ≥ type, then the solution zone lies away from the centre.
If the constraint is ≤ type, then solution zone is towards the centre.)

Step 3: Obtain the feasible zone.

Step 4: Find the co-ordinates of the objectivesfunction (profit line) and plot it on the graph representing it
with a dotted line.
Step 5: Locate the solution point.
(Note: If the given problem is maximization, Zmax then locate the solution point at the far
most point ofthe feasible zone from the origin and if minimization, Zmin then locate the solution at
the shortest point of the solution zone from the origin).

Step 6: Solution type

i. If the solution point is a single point on corresponding values of x1 and x2.
the line, take the
ii. If the solution point lies at the intersection of two equations, then solve for x1 and x2 using the
two equations.
iii. If the solution appears as a small line, then a multiple solution exists.
iv. If the solution has no confined boundary, the solution is said to be an unbound solution.
 CONT...

100
No. of carton boxes x,

90 100

80 90

70 BO
-
70
60

60 0,60
50
0,40) 50 \2x, + x =60
40
4
40
30
2x +3x, =120 P
30
20
20
10 (60, 0) 2x + 3x,=120
10
10 20 30 40 50 60 70-50 90 100
10 20 30 40 50 60 70-80 90 100
No. of corrugated boxes x 4
Figure 4.1: Graph Considering First Constraint Figure4.2: Graph Showing Feasible Area

The inequality constraint of the first line is

When the second constraint is drawn, you may notice that a portion of
(less than or equal to) ≤ type which means the feasible area is cut. This indicates that while considering both the
feasible solution zone lies towards the origin. constraints, the feasible region gets reduced further. Now any point in
the shaded portion will satisfy the constraint equations.

(Note: If the constraint type is ≥ then the

the objective is to maximize the profit. The point that lies at the
solution zone area lies awayfrom the origin in furthermost point of the feasible area will give the maximum
the opposite direction). Now the second profit. To locate the point, we need to plot the objective function
constraints line is drawn. (profit) line.
 Cont..

Objective function line (Profit Line)

Equate the objective function for any specific profit value Z,
Consider a Z-value of 60, i.e.,
6x1 + 4x2 = 60
Substituting x1 = o, we get x2 = 15 and
if x2 = o, then x1 = 10

Therefore, the co-ordinates for the objective function line are (0,15),
(10,0) as indicated objective function line. The objective function line
contains all possible combinations of values of xl and x2.

Therefore, we conclude that maximize profit, 15 numbers of corrugated

to
boxes and 30 numbers of carton boxes should be produced to get a
maximum profit. Substituting
X1 = 15 and x2= 30 in objective function, we get

Zmax = 6x1 + 4x2

= 6(15) +4(30)

Maximum profit: Rs. 210.00

Example Problem
Problem: All products manufactured are shipped out of the
storage area at the end of the day. Therefore, the two products
must share the total raw material, storage space, and production
time. The company wants to determine how many units
of each product to produce per day to maximize its
total income.
Solution
 The company has decided that it wants to maximize its sale
income, which depends on the number of units of product I and
II that it produces.
 Therefore, the decision variables, x1 and x2 can be the number
of units of products I and II, respectively, produced per day.
 • The object is to maximize the equation:
Z = 13x1 + 11x2
subject to the constraints on storage space, raw materials, and
production time.

• Each unit of product I requires 4 ft2 of storage space and each unit of
product II requires 5 ft2. Thus a total of 4x1 + 5x2 ft2 of storage space is
needed each day. This space must be less than or equal to the
available storage space, which is 1500 ft2. Therefore,
4X1 + 5X2  1500
• Similarly, each unit of product I and II produced requires 5 and 3 1bs,
respectively, of raw material. Hence a total of 5xl + 3x2 Ib of raw
material is used.

BCN67755
Decision and Risk Analysis Syed M. Ahmed, Ph.D.
 • This must be less than or equal to the total amount of raw material
available, which is 1575 Ib. Therefore,
5x1 + 3x2  1575
• Prouct I can be produced at the rate of 60 units per hour. Therefore, it
must take I minute or 1/60 of an hour to produce I unit. Similarly, it
requires 1/30 of an hour to produce 1 unit of product II. Hence a total of
x1/60 + x2/30 hours is required for the daily production. This quantity
must be less than or equal to the total production time available each
day. Therefore,
x1 / 60 + x2 / 30  7
or x1 + 2x2  420
• Finally, the company cannot produce a negative quantity of any
product, therefore x1 and x2 must each be greater than or equal to zero.

BCN67755
Decision and Risk Analysis Syed M. Ahmed, Ph.D.
 • The linear programming model for this example can be summarized as:

…..Eq (4)

BCN67755
Decision and Risk Analysis Syed M. Ahmed, Ph.D.
Graphical Solution to LP Problems
 Simplex Method
In practice, most problems contain more than two

variables and consequently too large to be tackled by

are
conventional means. Therefore, an algebraic technique is
used to solve large problems using Simplex Method. This
method is carried out through iterative process
systematically step by step, and finally the maximum or
minimum values of the objective function are attained.

The simplex method solves the linear programming

problem in iterations to improve the value of the objective
function. The simplex approach only yields the optimal
not
solution but also other valuable information to perform
economic and 'what if analysis.
 ADDITIONAL VARIABLES USED IN SOLVING LPP
Three types of additional variables are used in simplex method such
as,

(a) Slack variables (S,, S, S..S): Slack variables refer to the amount
of unused resources like raw materials, labour and money.

(b) Surplus variables (-S, -S, -S.-Sn): Surplus variable is the

amount of resources by which the left hand side of the equation
exceeds the minimum limit.

(c) Artificial Variables (a,, a,, a,.. ..an): Artificial variables are
temporary slack variables which are used for purposes of
calculation, and are removed later.

The above variables are used to convert the inequalities into equality
equations, as given in the Given Table below.
 Cont...

Table 5.1: Types of Additional Variables

Constraint Type Variable added Format

a Less than or equal to Add Slack Variable +S

b) Greater than or equal to 2 Subtract surplus variable and add -S+a

artificial variable

c) Equal to Add artificial variable +a

 Procedure of simplex Method
Step 1: Formulate the LP problem.

Step 2: Introduce slack /auxiliary variables.

if constraint type is s introduce + S
if constraint type is zintroduce S+ a and
-

if constraint type is = introduce a

Step 3: Find the initial basic solution.

Step 4: Establish a enter all variable coefficients. If the objective

simplex table and
function is maximization, enter the opposite sign co-efficient and if
minimization, enter without changing the sign.

Step 5: Take the most negative coefficient in the objective function, Zj to

identify the key column (the corresponding variable is the entering
variable of the next iteration table).

Step 6: Find the ratio between the solution value and the coefficient of the key
column. Enter the values in the minimum ratio column.
 Cont....

Step 7: Take the minimum positive value available in the minimum ratio
column to identify the key row. (The corresponding variable is the
leaving variable of the table).

Step 8: The intersection element of the key column and key row is the pivotal
element.

Step 9: Construct the next iteration table by eliminating the leavin variable
and introducing the entering variable.

Step 10: Convert the pivotal element as i in the next iteration table and
compute the other elements in that row accordingly. This is the
pivotal equation row (not key row).

Step 11: Other elements in the key column must be made zero. For simplicity,
form the equations as follows: Change the sign of the key column
element, multiply with pivotal equation element and add the
corresponding variable.
 Cont....

Step 12: Check the values of objective function. If there are negative
values, the solution is not an optimal one; go to step 5. Else, if all
the values are positive, optimality is reached. Non-negativity for
objective function value is not considered. Write down the values
of x1, x2,.......xi and calculate the objective function for
maximization or minimization.
Note:

(i) If there are no x1, x2 variables in the final iteration table, the
values of x1 and x2 are zero.

(ii) Neglect the sign for objective function value in thefinal iteration
table.
 Example

Previous the packaging product mix problem is solved using

simplex method.
Maximize Z = 6x, + 4x,
Subject to constraints,
2X,+3X2 ≤120 (Cutting machine) (i)
2x,+ x₂≤ 60 (Pinning machine) .(ii)
where x,, x₂ ≥o

Considering the constraint for cutting machine,

2X+ 3X ≤ 120

To convert this inequality constraint into an equation,

introduce aslack variable, S3 which represents the unused
resources. Introducing the slack variable, we have the
equation 2x+3x₂+ S 3 =120

Similarly for pinning machine, the equation is

2x,+ x₂ + S = 90
 Example cont....

If variables x1 and x2 are equated to zero,

i.e., x1 = o and x2 = o, then

S3 = 120

S4=60

This is the basic solution of the system, and variables S₂ and

S are known Variables, Sg while x, and x₂ known
as Basic
as Non-Basic Variables. If all the variables are non

negative, a basic feasible solution of a linear

programming problem is called a Basic Feasible
Solution.
 Cont....

Rewriting the constraints with slack variables gives us,

Zmax = 6x, +4x₂ + oS + oS
Subject to constraints,
2x, +3x2 + S, = 120 (i)
2x, +x₂ + SS = 60 .(ii)
where x,, x ≥ o

Which can shown in following simplex table form

Table 5.2: Co-efficients of Variables

Iteration Basic Solution X Minimun Equation

Number Variables S3 S4 Ratio
Value Kc

이 S3 120 2 3 1 이 90

S4 60 2 1 이 1 30

Z-
이 -6 -4 이 이
 Cont...

If the objective of the given problem is a maximization one, enter the

co-efficient of the objective function Zj with opposite sign as shown in
table. Take the most negative coefficient of the objective function and
that is the key column Kc. In this case, it is -6.

Find the ratio between the solution value and the key column
coefficient and enter it in the minimum ratio column.

The intersecting coefficients of the key column and key row are called
the pivotal element i.e. 2.

The variable corresponding to the key column is the entering element

of the next iteration table and the corresponding variableof the kekey
row is the leaving element of the next iteration table (In other words, x1
replaces S4 in the next iteration table. Given indicates the key column,
key row and the pivotal element.)
 Cont..

X
Iteration Basic Solution Minimun
X S3 S4 Equation
Number Variables Value Kc Ratio

0 S3 120 2 3 1 0 60

K 54 60 2 1 이 1 30

-Z 이 -6 -4 0 0

In the next iteration, enter the basic variables by eliminating the leaving variable
(i.e., key row) and introducing the entering variable (i.e., key column).

Make the pivotal element as 1 and enter the values of other elements in that row accordingly.

In this case, convert the pivotal element value 2 as 1 in the next iteration table.

For this, divide the pivotal element by 2. Similarly divide the other elements in that row by 2.
The equation is S4/2.

This row is called as Pivotal Equation Row Pе.

The other co-efficients of the key column in iteration Table 5.4 must be made as zero in the
iteration Table 5.5.
For this, a solver, Q, is formed for easy calculation.
 Cont...

Solver, Q = SB + (-K* P)
The equations for the variables in the iteration number 1 of table 8 are,

For S3 Q = Sg + (- K₂* P)
= S3 + (-2x P)
= S3 - 2P e .(i)
For - ZQ = SB + (- K * P)
= - Z + ))-6) * P)
= - Z + 6 .(ii)
Using the equations (i) and (ii) the values of S3 and -Z for the values of
Table 1 are found as shown in Table 5.4
 Cont....

Iteration Basic Solution X Minimum

K S3 S Equation
Number Variables Value Ko Ratio

0 53 120 2 3 1 이 60

K S 60 2 1 이 1 30

-2 0 -6 -4 0 0

1
K
53 60 0 2 1 -1 30 S3-2P.

P X1 30 1 0 12 60 5412
1-
-Z 100 이 이 3 -Z+6P.

Using these equations, enter the values of basic variables S and objective function Z. If
all the values in the objective function are non-negative, the solution is optimal.

Here, we have one negative value - 1. Repeat the steps to find the key row and pivotal
equation values for the iteration 2 and check for optimality.

We get New Table as below:

 Cont....

Table 5.5: Iteration Table

Iteration Basic Solution S Minimum

x X₂ S3 Equation
Number Variables Value Ratio

Ο S3 120 2 3 1 이 60

54 60 2 1 Ο 1 30

K -2 이 -6 -4 이 이

이
1
53 60 2 1 -1 30 S3-2p.
K x1 30 1 シュ 0 2 60 S4/2
Z-
Pe 100 이 -1 0 3 -Z+ 6P

2 P A5 30 0 1 2 53/2

X1 15 1 이 -
1/2 S3- Pa2
210 이 0 1/4 4 -Z+P,
5/2

The solution is,

x₁= 15 corrugated boxes are to beproduced and
x₂= 30 carton boxes are to be produced to yield a
max = Rs. 210.00
Profit, Zmx
Duality of LPP
❖ With every linear programming problem, there is associated
another linear programming problem which is called the dual
of the original (or the primal) problem.
Formulating the Dual problem

❖ Consider again the production mix problem of N. Dustrious

Company.
❖ Suppose that the company is considering leasing out the
entire production facility to another company, and it must
decide on the minimum daily rental price that will be
acceptable.
❖ This decision problem can also be formulated as a linear
programming problem.
The primal-Dual Relationship
Example on Dual LPP
❖ The primal problem can now take the following standard form:

❖ The dual of this problem can now be obtained as follows: