METHODS OF

OPTIMIZATION

Lecture 1: Linear Programming

Learning objectives:

The learning objectives of this chapter are

• Introduction to Optimization Techniques.
• Explaining some optimization techniques.
• Introduction to Linear Programming.
• How to solve Linear-programming problems by graphical
methods, problems with n – variable and how to overcome
that.
Introduction

What is optimization?

• “To optimize is to make as perfect, effective, or functional as

possible” … Merriam-Webster dictionary.

• “In engineering domain, optimization is a collection of methods and

techniques to design and make use of engineering systems as
perfectly as possible with respect to specific parameters”

• “In industrial engineering, one typical optimization problem is in

inventory control. For this problem, we want to reduce the costs
associated with item stocking and handling in a warehouse”
Optimization problem:
• Maximizing or minimizing some function relative to some set;
often representing a range of choices available in a certain
situation. The function allows comparison of the different
choices for determining which might be “best.”
• Optimization requires the representation of the problem in a
mathematical model where the decision variables are the
parameters of the problem.

Common applications: Minimal cost, maximal profit, minimal

error, optimal design, optimal management, and variation
principles.
Mathematical Optimization:
• A mathematical optimization problem is one in which some
function is either maximized or minimized relative to a given
set of alternatives. The function to be minimized or maximized
is called the objective function and the set of alternatives is
called the feasible region

Linear programming:
• Linear programming is the name of a branch of applied
mathematics that deals with solving optimization problems of
a particular form.
• Linear programming problems consist of a linear cost function
(consisting of a certain number of variables), which is to be
minimized or maximized subject to a certain number of
constraints.
History:

• Linear programming is a relatively young mathematical

discipline dating from the invention of the simplex method by
G. B. Dantzig in 1947.

• Historically, development in linear programming is driven by

its applications in economics and management.

• Dantzig initially developed the simplex method to solve U.S.

Air Force planning problems, and planning and scheduling
problems still dominate the applications of linear
programming
Terminology:
• In general case linear programming problem can be
formulated as following:
Every linear programming problem falls into one of three
categories:

1. Infeasible. A linear programming problem is infeasible if a
feasible solution to the problem does not exist; that is, there is
no vector x for which all the constraints of the problem are
satisfied.

2. Unbounded. A linear programming problem is unbounded if
the constraints do not sufficiently restrain the cost function so
that for any given feasible solution, another feasible solution can
be found that makes a further improvement to the cost
function.

3. Has an optimal solution. Linear programming problems that
are not infeasible or unbounded have an optimal solution; that
is, the cost function has a unique minimum (or maximum) cost
function value. This does not mean that the values of the
variables that yield that optimal solution are unique, however.
Application Examples of Linear
Programming :

1. A farmer has 240 acres of land to plant. He needs to decide

how many acres of corn to plant & how many of oats. He can
make 40$ per acres profit for corn & 30$ per acres for oats.
However corn takes 2 hours of labor per acre to harvest while
oats takes 1 hour per acre. He has only 320 labors he can invest.
To maximize his profit how many acres of corn & oats should he
plant.
Solution: Let x & y be number of acres of corn & oats
respectively. Our objective in this problem is to maximize the
profit P.

Therefore, P= 40x + 30y  max

Constraints: x ≥0; y ≥0; ……… as land can't be negative

Another constraint we have how much land we can allot; we

have 240 acres of total land. So, x + y ≤ 240;

Now, we have constraints on labor also. We have 320 hours of

labor to spend. So it can be represented as 2x + y ≤ 320;
Hence, the linear equation of problem can be describes as
below:
Maximize: P= 40x+ 30y
Subject to: x + y ≤ 240;
2x + y ≤ 320;
Where with respect to problem x ≥0; y ≥0;
 2.There are two kinds of feeds: feed I & feed II, containing 3
different kinds of vital nutrients N1, N2 & N3. The table includes
the number of nutritional units per kilo for each feed & a
required minimum of nutrients

1 Kilo of the 1st nutrition cost 4 rubles & 1 kilo of the 2nd
nutrition costs 6. It is necessary to combine daily food
allowances having the smallest possible cost & satisfy
these nutritional requirements
Solution:
Let x & y be the quantities of feed I & II. The objective
function is to minimize the cost while satisfying the
nutritional requirements.
Therefore, Z (X)= 4x+ 6y  min

Constraints: From given table, daily food allowance

consists of (3x+y) units of nutrients of N1, (x+2y) units of
nutrients of N2 & (x+6y) units of nutrients of N3. The
nutrients N1, N2 & N3 must not be smaller than 9,8 & 12
correspondingly. Hence there is subject to constraints:
3x+y ≥9, x+y≥ 8 & x+6y≥12.
Hence, the linear equation of problem can be describes as
below:
Minimize Z (X)= 4x+ 6y  min

Subject to: 3x+y ≥9

x+y≥ 8
x+6y≥12

Where with respect to problem: x≥0, y≥ 0.

Standard form of Linear
Programming problem:
We say that a linear program is in standard form if the following
are all true:
• 1. Non-negativity constraints for all variables.
• 2. All remaining constraints are expressed as equality
constraints.
• 3. The right hand side vector, b, is non-negative.
The given LP not in standard form:
Why do we need to know how to convert a linear program to
standard form? What’s so special about standard form?

• The main reason that we care about standard form is that this
form is the starting point for the simplex method, which is the
primary method for solving linear programs.
• In addition, it is good practice for students to think about
transformations, which is one of the key techniques used in
mathematical modeling.
Steps to follow to convert Linear-
programming problem to standard form:

Step 1:

If the objective function is minimization, just “negate” the

objective function.

For example. “minimize –a +b subject to a-b ≤ 2, a, b ≥ 0 ” is

equivalent to “maximize a-b subject to a-b ≤ 2, a, b ≥ 0 ”.
Step 2:
Step 3:
Step 4:
Step 5:
Examples:

1.Convert the Linear-programming problem to the

standard form
Solution:
2.Convert the Linear-programming problem to the
symmetrical form

Solution:
Let us transform the constraint system by Jordan-Gauss
Method & exclude pivot variables from the objective
function.
Note: Don’t choose the coefficient of the objective
function as pivot.
Geometric Method
MANY PRACTICAL PROBLEMS involve maximizing or minimizing
a function subject to certain constraints.
For example, we may wish to maximize a profit function subject
to certain limitations on the amount of material and labor
available. Maximization or minimization problems that can be
formulated in terms of a linear objective function and
constraints in the form of linear inequalities are called linear
programming problems. In this chapter, we look at linear
programming problems involving two variables. These problems
are amenable to geometric analysis, and the method of solution
introduced here will shed much light on the basic nature of a
linear programming problem
Problem with two Variables:
Steps for Solving a Linear Programming Problem
1. Translate the problem into mathematical terms
2. Graph the feasible set described by the constraint inequalities
and finds the coordinates of all the corner points. If the region is
unbounded, determine whether it’s possible for the objective
function to obtain the desired extreme value. If not, write “no
solution”. Otherwise go to step 3.
3. Evaluate the objective function at each of the corner points.
4. Find the corner point that makes the objective function a
maximum (minimum). If there’s only one such corner point then
the value of the objective function at that point is the maximum
(minimum). If there are two adjacent corner points that
maximize (minimize) the objective function then the maximum
(minimum) value of the objective function occurs at any point
on the line segment joining the two corner points.
Examples:

1. Mike’s Famous Toy Trucks manufactures two kinds of toy

trucks—a standard model and a deluxe model. In the
manufacturing process each standard model requires 2 hours of
grinding and 2 hours of finishing, and each deluxe model needs 2
hours of grinding and 4 hours of finishing. The company has two
grinders and three finishers, each of whom works at most 40
hours per week. Each standard model toy truck brings a profit of
$3 and each deluxe model a profit of $4. Assuming that every
truck made will be sold, how many of each should be made to
maximize profits?
By simplifying each of these constraints and adding the non-negativity
constraints x ≥ 0 and y ≥ 0.

we may list all the constraints for this problem:

x + y ≤ 40
x + 2y ≤60
x≥0
y≥ 0
Figure illustrates the set of feasible points, which is bounded.
The corner points of the set of feasible points are
(0, 0) (0, 30)
(40, 0) (20, 20)
Table lists the corresponding values of the objective equation

A maximum profit is obtained if 20 standard trucks and 20 deluxe

trucks are manufactured. The maximum profit is $140.
2. Determine the graphical solution set for the following system
of linear inequalities:
2x + y=50;
x +2y = 40
x≥0
y≥0

Solution: The required solution set is unbounded region shown

in Figure
3. Determine graphically the solution set for the following system
of inequalities:
x + 2y ≤10
5x + 3y ≤ 30
x≥0
y≥ 0
Solution: The required solution set is shown in the following
figure:
Problem of n- Variables:
The graphical method is confined to two variables.
However, if the problem has standard form and satisfies
the condition n-r ≤ 2, where n is number of unknowns, & r
is rank of constraint vector system it can be solved. If
equations of a system are linear independent, then rank r
equals the number of equations m.
Example:
Solution:
Let’s check up whether the graphical method can be applied
to solve the problem. For what we find n-r=5-3=2. Hence,
method will be applied.
We can use Jordan-Gauss method to solve this problem &
pivot unknowns are excluded from the objective function.
Lecture 2: Simplex Method for
Maximization
Learning objectives:

The learning objectives of this chapter are

• The simplex Method Algorithm.

• The simplex Method - Basic & non-basic variables.
• Application of simplex method to maximization & how to
deal with minimization problems.
Introduction:

The geometric method of solving linear programming

problems presented before. The graphical method is
useful only for problems involving two decision variables
and relatively few problem constraints.

What happens when we need more decision variables and more

problem constraints?

We use an algebraic method called the simplex method,

which was developed by George B. DANTZIG (1914-
2005) in 1947 while on assignment with the U.S.
Department of the air force.
Converting a linear program to Standard
Form

Before the simplex algorithm can be applied, the linear program must be
converted into standard form where all the constraints are written as
equations (no inequalities) and all variables are nonnegative (no
unrestricted variables). This process of converting a linear program to its
standard form requires the addition of slack variable s which represents
i
the amount of the resource not used in the ith ≤constraint. Similarly,
≥constraints can be converted into standard form by subtracting excess
variable e .
i
The standard form of any linear program can then be represented by the
following linear system with n variables (including decision, slack and excess
variables) and m constraints.
Algorithm for the Simplex Method
The simplex algorithm, instead of evaluating all basic feasible solutions
(which can be prohibitive even for moderate-size problems), starts with a
basic feasible solution and moves through other basic feasible solutions
that successively improve the value of the objective function. The
algorithm terminates once the optimal value is reached. Below we
present a step-wise description of the simplex algorithm.
1. Convert the linear program into standard form.
2. Obtain a basic feasible solution from the standard form.
3. Determine if the basic feasible solution is optimal.
4. If the current basic feasible solution is not optimal, select a non-basic
variable that should become a basic variable and basic variable which
should become a non-basic variable to determine a new basic feasible
solution with an improved objective function value.
5. Use elementary row operations to solve for the new basic feasible
solution. Return to Step 3
Steps 1 and 2 of the algorithm have been previously discussed. Steps 3, 4
and 5 of the algorithm are best executed with the help of a tableau which
is simply a table with a particular format that shows a summary of the
key information regarding the linear program.
Basic and Non-basic Variables, and Basic Feasible
Solutions :
If we define,

the constraints of the standard form of a linear program can

be simply represented by a system of simultaneous equations
Ax = b .
 Basic variables are selected arbitrarily with the
restriction that there be as many basic variables as there
are equations. The remaining variables are non-basic
variables.

This system has two equations, we can select any

two of the four variables as basic variables. The
remaining two variables are then non-basic variables. A
solution found by setting the two non-basic variables
equal to 0 and solving for the two basic variables is a
basic solution. If a basic solution has no negative values,
it is a basic feasible solution.
Examples:
The Cannon Hill furniture Company produces tables and
chairs. Each table takes four hours of labor from the
carpentry department and two hours of labor from the
finishing department. Each chair requires three hours of
carpentry and one hour of finishing. During the current
week, 240 hours of carpentry time are available and 100
hours of finishing time. Each table produced gives a
profit of $70 and each chair a profit of $50. How many
chairs and tables should be made?
Resource Table s ( ) Chairs ( ) Constraints
Carpentry
4 3 240
(hrs.)
Finishing
2 1 100
(hrs.)
Unit Profit $70 $50

Objective Function: =
P 70 x1 + 50 x2

4 x1 + 3 x2 ≤ 240
Carpentry Constraint:

2 x1 + 1x2 ≤ 100
Finishing Constraint:

x1 , x2 ≥ 0
Non-negativity conditions:
The first step of the simplex method, requires that each
inequality be converted into an equality.

The standardized form

4 x1 + 3x2 + s1 + 0s2 =
240
2 x1 + x2 + 0s1 + s2 =
100
P − 70 x1 − 50 x2 − 0s1 − 0s2 =
0

Notes: All the variables are nonnegative Such a solution is called feasible.
 x1 x2 S1 S2 P RHS

4 3 1 0 0 240
2 1 0 1 0 100
-70 -50 0 0 1 0

The table represents the initial solution;

=x1 0,=
x2 0,=s1 240,=
s2 100,=P 0
The slack variables S1 and S2 form the initial solution mix. The initial
solution assumes that all avaliable hours are unused. i.e. The slack
variables takes the largest possible values.
Select the pivot column (determine which variable to
enter into the solution mix). Choose the column with
the “most negative” element in the objective function
row.

x1 x2 S1 S2 P RHS

4 3 1 0 0 240
2 1 0 1 0 100
-70 -50 0 0 1 0
 Select the pivot row (determine which variable to
replace in the solution mix). Divide the last element
in each row by the corresponding element in the
pivot column. The pivot row is the row with the
smallest non-negative result

x1 x2 S1 S2 P RHS

4 3 1 0 0 240 240 / 4 = 60
2 1 0 1 0 100 100 / 2 = 50
-70 -50 0 0 1 0
After Solving,

x1 x2 S1 S2 P RHS

4 3 1 0 0 240
R2
1 1/2 0 1/2 0 50
2
-70 -50 0 0 1 0
x1 x2 S1 S2 P RHS

0 1 1 -2 0 40 −4.R2 + R1
1 1/2 0 1/2 0 50 70.R2 + R3
0 -15 0 35 1 3500
Now repeat the steps, till we will have not
negative element in the last row.

x1 x2 S1 S2 P RHS

0 1 1 -2 0 40 40 /1 = 40

1 1/2 0 1/2 0 50 50 / 0,5 = 100

0 -15 0 35 1 3500
 x1 x2 S1 S2 P RHS

1
0 1 1 -2 0 40 − .R1 + R2
2
1 0 -1/2 3/2 0 30 15.R1 + R3
0 0 15 5 1 4100

As the last row contains no negative numbers, this

solution gives the maximum value of P.
Result:

This simplex table represents the optimal solution

to the LP problem and is interpreted as:

=x1 30,= =
x2 40, s1 0,=s2 0

and profit P=$4100.

Practice Examples:
1. Maximize: P = 3x + 4y
subject to: x + y ≤ 4
2x + y ≤ 5
x ≥ 0, y ≥ 0
2. Maximize: P = 3x1 + 5x2

Subject to: x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
x1 ≥0, x2 ≥ 0
Notes:
1. When you solve a simplex problem & find that slack variable
takes on a positive value. Basically, it because of when one of
the slack variables takes on a positive value it means that in
maximizing our objective function we stayed ”below” one of our
constraints.
For example, if u is the slack variable corresponding to a
constraint on labor hours used and the value of u is 12 in our
optimal solution, it means we have 12 remaining labor hours
available.

2. If the last row to the left of the vertical line in my simplex

table contains all zeros, then there are infinitely many solutions
to the optimization problem.
Minimization Problems:
• There are several ways to solve minimization problems. We
will see those in next chapter
Lecture  3:  Minimiza0on  
 Techniques.  
Problems  &  Ar0ficial  Variable  
 
  
Learning  objectives:  
   
The  learning  objec/ves  of  this  chapter  are  
 
•   The  simplex  Method  Algorithm  for  minimiza/on  problems  
•   Overview  of  Ar/ficial  variable  techniques  for  simplex  Method.  
•     Applica/on  of  simplex  method  to  maximiza/on  &  
minimiza/on  by  using  
                         The  Big  M  Method  or  Method  of  Penal/es.    
                         The  Two-­‐phase  Simplex  Method.  
Duality  Theorem  Concept:  
Linear  programming  problems  exist  in  pairs.  That  
is  in  linear  programming  problem,  every  
maximiza/on  problem  is  associated  with  a  
minimiza/on  problem.  Conversely,  associated  
with  every  minimiza/on  problem  is  a  
maximiza/on  problem.  Once  we  have  a  problem  
with  its  objec/ve  func/on  as  maximiza/on,  we  
can  write  by  using  duality  rela/onship  of  linear  
programming  problems,  its  minimiza/on  version.  
The  original  linear  programming  problem  is  
known  as  primal  problem,  and  the  derived  
problem  is  known  as  dual  problem  
 Thus,  the  dual  problem  uses  exactly  the  same  parameters  
as  the  primal  problem,  but  in  different  loca/ons.  To  
highlight  the  comparison,  now  look  at  these  same  two  
problems  in  matrix  nota/on  

Primal  Problem       Dual  Problem  

Minimize   Z=cx     Maximize   W=yb  
 
Subject  to   Ax≥b     Subject  to   yA≤c  
 
and     x≥0              And     y≥0  

 
 
  Primal  problem   Dual  problem  
     
  𝑎11   𝑎12   𝑎13     𝑎11   𝑏11   𝑐11  
T
A=   𝑏11   𝑏12   𝑏13   A =   𝑎12   𝑏12   𝑐12  
  𝑐11   𝑐12   𝑐13     𝑎13   𝑏13   𝑐13  
   
Minimiza0on  Problems  
 
In  Previous  Examples,  we  applied  the  simplex  method  
only  to  linear  programming  problems  in  standard  form  
where  the  objec/ve  func/on  was  to  be  maximized.  In  
this  sec/on,  we  extend  this  procedure  to  linear  
programming  problems  in  which  the  objec/ve  
func/on  is  to  be  minimized.  
 
A  minimiza/on  problem  is  in  standard  form  if  the  
objec/ve  func/on  is:  
  
Von  Neumann  Duality  Principle    
 
 
“The  objec1ve  value  w  of  a  minimiza1on  problem  
in  standard  form  has  a  minimum  value  if  and  only  
if  the  objec1ve  value  z  of  the  dual  maximiza1on  
problem  has  a  maximum  value.  Moreover,  the  
minimum  value  of  w  is  equal  to  the  maximum  
value  of  z.  “  
 
  
Solving  a  Minimiza0on  Problem  
 
    solve  this  problem  we  use  the  following  steps  
To  
Step  1.  Use  the  coefficients  and  constants  in  the  
problem  constraints  and  the  objec/ve  func/on  to  form  a  
matrix  A  with  the  coefficients  of  the  objec-­‐/ve  func/on  
in  the  last  row.  
   
Step  2.  Interchange  the  rows  and  columns  of  matrix  A  to  
form  the  matrix  AT,  the  transpose  of  A.  
   
Step  3.  Use  the  rows  of  AT  to  form  a  maximiza/on  
problem  with  ≤  problem  constraints.  
Example:  
 
1.        Minimize                              C  =  16  x1  +  9x2  +  21x3    
               subject  to          x1  +  x2  +  3x3  ≥  12    
                                                                             2x1  +  x2  +x3  ≥  16    
                                                                               x1,  x2,  x3  ≥  0  
 Solu0on:  

ORIGINAL  PROBLEM   DUAL  PROBLEM    

       
                   Minimize  C  =  16x1  +  45x2              Maximize      P  =  50y1  +  27y2  
   

             subject  to    2x1  +  5x2  ≥    50                    subject  to      2y1  +    y2  ≤  16    
                                                     x1  +  3x2  ≥    27                                                              5y1  +  3y2  ≤  45    
                                                         x1,  x2  ≥  0                                                              y1,y2  ≥  0  
       
Corner  Point   Corner  Point  
(x1,  x2)   C=  16x1+45  x2   (y1,  y2)   P=50y1+27  y2  
(0,10)   450   (0,0)   0  
(15,4)   420   (0,15)   405  
(27,0)   432   (3,10)   420  
        (8,0)   400  
Min  C=420  at  (15,4)   Max  P=420  at  (3,10)  
For  reasons  that  will  become  clear  later,  we  will  use  the  
variables  x1  and  x2  from  the  original  problem  as  the  slack  
variables  in  the  dual  problem:  
   
2y1  +y2  +  s1=16    (ini/al  system  for  the  dual  problem)  
 
5y1  +3y2+  s2=45  
 
-­‐50y1-­‐27y2+  P  =0  
Since  all  numbers  in  the  bogom  row  are  nonnega/ve,  the  solu/on  to  the  
dual  problem  is  
   
y1  =  3,      y2  =  10,    s1  =  0,      s2  =  0,      P  =  420  
   
Furthermore,  examining  the  bot-­‐tom  row  of  the  final  simplex  tableau,  we  
see  the  same  op/mal  solu/on  to  the  mini-­‐miza/on  problem  that  we  
obtained  directly  by  the  geometric  method:  
   
Min  C  =  420          at          s1  =  15,      s2  =  4  
   
This  is  not  achieved  with  mistake.  
 
 
An  op0mal  solu0on  to  a  minimiza0on  problem  always  can  be  obtained  
from  the  boPom  row  of  the  final  simplex  tableau  for  the  dual  problem.  
   
 
Note:  In  dual  problem,  we  will  choose  slack  Variable  as  solu/on.  
Example  2:  (For  Prac0ce)  
Example  3:  
A  small  petroleum  company  owns  two  refineries.  
Refinery  1  costs  $20,000  per  day  to  operate,  and  it  can  
produce  400  barrels  of  high-­‐grade  oil,  300  barrels  of  
medium-­‐grade  oil,  and  200  barrels  of  low-­‐grade  oil  each  
day.  Refinery  2  is  newer  and  more  modern.  It  costs  
$25,000  per  day  to  operate,  and  it  can  produce  300  
barrels  of  high-­‐grade  oil,  400  barrels  of  medium-­‐grade  
oil,  and  500  barrels  of  low-­‐grade  oil  each  day.  
The  company  has  orders  totaling  25,000  barrels  of  high-­‐
grade  oil,  27,000  barrels  of  medium-­‐grade  oil,  and  
30,000  barrels  of  low-­‐grade  oil.  How  many  days  should  it  
run  each  refinery  to  minimize  its  costs  and  s/ll  refine  
enough  oil  to  meet  its  orders?  
  
Arti.icial  Variables  Techniques    
  In  order  to  use  the  simplex  method,  a  BFS  is  needed.  To  remedy  
the  predicament,  ar/ficial  variables  are  created.  These  variables  
are  fic//ous  and  cannot  have  any  physical  meaning.  The  ar/ficial  
variable  technique  is  a  device  to  get  the  star/ng  basic  feasible  
solu/on,  so  that  simplex  procedure  may  be  adopted  as  usual  un/l  
the  op/mal  solu/on  is  obtained.  To  solve  such  LPP  there  are  two  
methods.  
   
•  The  Big  M  Method  or  Method  of  Penal/es.    
•  The  Two-­‐phase  Simplex  Method.  
 
Big  M  Method  
 
1.  Modify  the  constraints  so  that  the  RHS  of  each  constraint  
is  nonnega/ve.  Iden/fy  each  constraint  that  is  now  an  =  or  ≥  
constraint.  
2.  Convert  each  inequality  constraint  to  standard  form  (add  
a  slack  variable  for  ≤  constraints,  add  an  excess  variable  for  
≥  constraints).  
3.  For  each  ≥  or  =  constraint,  add  ar/ficial  variables.  Add  sign  
restric/on  a ≥  0.  
i   a  very  large  posi/ve  number.  Add  (for  each  
4.  Let  M  denote  
ar/ficial  variable)  Ma to  min  problem  objec/ve  func/ons  or  
-­‐Ma to  max  problem  i  objec/ve  func/ons.  
i   each  ar/ficial  variable  will  be  in  the  star/ng  basis,  all  
5.  Since  
ar/ficial  variables  must  be  eliminated  from  row  0  before  
beginning  the  simplex.  Remembering  M  represents  a  very  
large  number,  solve  the  transformed  problem  by  the  
simplex.  
NOTE:  If  all  ar/ficial  variables  in  the  op/mal  solu/on  equal  
zero,  the  solu/on  is  op/mal.  If  any  ar/ficial  variables  are  
posi/ve  in  the  op/mal  solu/on,  the  problem  is  infeasible.  

NOTE  :    
 
Why  we  have  to  subtract  or  add  M  from  Objec8ve  func8on?  
 
          To   prevent   an   ar/ficial   variable   from   becoming   part   of   an   op/mal  
solu/on  to  the  original  problem,  a  very  large  "penalty"  is  introduced  
into   the   objec/ve   func/on.   This   penalty   is   created   by   choosing   a  
posi/ve   constant   M   so   large   that   the   ar/ficial   variable   is   forced   to   be  
0  in  any  final  op/mal  solu/on  of  the  original  problem.  
Example:  
we  introduce  an  ar/ficial  variable  a into  the  equa/on  
involving  the  surplus  variable  s :   1  
2
For  a  system  tableau  to  be  considered  an  ini0al  simplex  
tableau,  it  must  sa/sfy  the  following  two  requirements:  
 
1.  The  requisite  number  of  basic  variables  must  be  
selectable.  Each  basic  variable  must  correspond  to  a  
column  in  the  tableau  with  exactly  one  nonzero  element.  
Different  basic  variables  must  have  the  nonzero  entries  in  
different  rows.  The  remaining  variables  are  then  selected  
as  non-­‐basic  variables.  
2.  The  basic  solu/on  found  by  seong  the  non-­‐basic  
variables  equal  to  zero  is  feasible.  
If  you  inspect  the  preliminary  tableau,  you  realize  that  the  problem  is  that    
 
s has  a  nega/ve  coefficient  in  its  column.  We  need  to  replace  s as  a  basic    
  2   2  
variable  by  something  else  with  a  posi/ve  coefficient.  We  choose  a .  
1
Example:  
Use  Big  M  method  to  solve  the  Turkey  Feed  Problem  as  given  in  
Table:  

Turkey  meal’s  Data  

From  Table,  We  can  Formulate  our  data  like  this:  
Aqer  Conver/ng  into  Standard  Form:  
Find  ini0al  basic  feasible  solu0on  
Elimina/ng  A ,A ,A from  the  first,  second  and  third  equa/ons  modified    
  1 2 3

objec/ve  func/on  can  be  wrigen  as:  

Problem,  now,  has  eight  variables  and  three  constraints.  five  of  the  
variables  have  to  be  zeroised  to  get  ini/al  basic  feasible  solu/on  to  the  
'ar/ficial  system'.  Puong,  
Since  all  z  coefficients  are  nega/ve  it  becomes  op/mal  solu/on  with  minimum  
cost    31.20.  
Hence,  the  minimum  cost  solu/on  is  to  purchase  8.4  pounds  of  brand  1  feed  
and  4.8  pounds  of  brand  2  feed  per  turkey  per  month.  
Examples  for  Prac0ce:  
Two  Phase  Method  
The  two-­‐phase  method  is  another  method  to  handle  these  
ar/ficial  variables.  Here  the  L.P.  problem  is  solved  in  two  
phases.  

PHASE  I  

In  this  phase  we  find  an  ini/al  basic  feasible  solu/on  to  the  
original  problem.  For  this  all  ar/ficial  variables  are  to  be  
driven  to  zero.  To  do  this  an  ar/ficial  (Auxiliary)  objec/ve  
func/on  (r)  is  created  which  is  the  sum  of  all  the  ar/ficial  
variables.  This  new  objec/ve  func/on  is  then  minimized,  
subject  to  the  constraints  of  the  given  (original)  problem,  
using  the  simplex  method.  At  the  end  of  phase  I,  two  cases  
arise:  
 TWO  PHASE  METHOD  :  NO  FEASIBLE  SOLUTION  
 
                           If  the  minimum  value  of  r  >  0,  and  at  least  one  ar/ficial  
variable  appears  in  the  basis  at  a  posi/ve  level,  then  the  given  
problem  has  no  feasible  solu/on  and  the  procedure  terminates.  

TWO  PHASE  METHOD:  OPTIMALITY  

 
If  the  minimum  value  of  r  =  0,  and  no  ar/ficial  variable  appears  
in  the  basis,  then  a  basic  feasible  solu/on  to  the  given  problem  
is  obtained.  The  ar/ficial  column  (s)  are  deleted  for  phase  II  
computa/ons.  
  
PHASE  II  
 
Use  the  op/mum  basic  feasible  solu/on  of  phase  I  as  a  star/ng  
solu/on  for  the  original  LPP.  Assign  the  actual  costs  to  the  variable  
in  the  objec/ve  func/on  and  a  zero  cost  to  every  ar/ficial  variable  
in  the  basis  at  zero  level.  Delete  the  ar/ficial  variable  column  from  
the  table  which  is  eliminated  from  the  basis  in  phase  I.  Apply  
simplex  method  to  the  modified  simplex  table  obtained  at  the  end  
of  phase  I  /ll  an  op/mum  basic  feasible  is  obtained  or  /ll  there  is  
an  indica/on  of  unbounded  solu/on.  
Example:  
Solu0on:  
Phase  1  
The  set  of  basic  variables  in  the  op/mal  table  of  phase  1  does  not  
contain  ar/ficial  variables.  So,  the  given  problem  has  a  feasible  
solu/on.  
Phase  2:  
The  op/mal  results  are  presented  by  x =0,  x =3.2=6/5,  x =  6.4  
and  min  z=153.6   1 2   3  
The  op/mal  results  are  presented  by  x =0,  x =3.2=6/5,  x =  6.4  
and  min  z=153.6 1 2   3  
 !
Lecture!4:!Transporta0on!
! Models!&!Op0miza0on

!
!
Learning!objectives:!
!!
The$learning$objec/ves$of$this$chapter$are$
$
•  $Introduc/on$to$Transporta/on$model$&$applica/ons.$
•  $North$west$Corner$rule$to$solve$transporta/on$problem.$
•  $Least$cost$Method$&$applica/on.$
•  $Vogel's$approxima/on$method.$
Introduction:!
A$typical$transporta/on$problem$is$shown$in$Fig.$It$deals$
with$sources$where$a$supply$of$some$commodity$is$
available$and$des/na/ons$where$the$commodity$is$
demanded.$The$classic$statement$of$the$transporta/on$
problem$uses$a$matrix$with$the$rows$represen/ng$
sources$and$columns$represen/ng$des/na/ons.$The$
algorithms$for$solving$the$problem$are$based$on$this$
matrix$representa/on.$The$costs$of$shipping$from$
sources$to$des/na/ons$are$indicated$by$the$entries$in$
the$matrix.$If$shipment$is$impossible$between$a$given$
source$and$des/na/on,$a$large$cost$of$M$is$entered.$This$
discourages$the$solu/on$from$using$such$cells.$Supplies$
and$demands$are$shown$along$the$margins$of$the$
matrix.$$
As$in$the$example,$the$classic$transporta/on$
problem$has$total$supply$equal$to$total$
demand.$

Matrix$model$of$a$transporta/on$problem$
The$network$model$of$the$transporta/on$problem$is$
shown$in$Fig.$Sources$are$iden/fied$as$the$nodes$on$the$
leK$and$des/na/ons$on$the$right.$Allowable$shipping$
links$are$shown$as$arcs,$while$disallowed$links$are$not$
included.$
!
North!West!Corner!Rule!
$
The$North!West!corner!rule!is$a$method$for$
compu/ng$a$basic$feasible$solu/on$of$a$
transporta0on!problem,$where$the$basic$variables$
are$selected$from$the$North$–$West$corner$($i.e.,$
top$leK$corner$).$$
$
$
Steps!in!North!West!Corner!Rule!$
•  Select$the$upper$leKPhand$corner$cell$of$the$transporta/on$
table$and$allocate$as$many$units$as$possible$equal$to$the$
minimum$between$available$supply$and$demand,$i.e.,$min(s1,$
d1).$$
•  Adjust$the$supply$and$demand$numbers$in$the$respec/ve$
rows$and$columns.$$
•  If$the$demand$for$the$first$cell$is$sa/sfied,$then$move$
horizontally$to$the$next$cell$in$the$second$column.$$
•  If$the$supply$for$the$first$row$is$exhausted,$then$move$down$to$
the$first$cell$in$the$second$row.$$
•  If$for$any$cell,$supply$equals$demand,$then$the$next$alloca/on$
can$be$made$in$cell$either$in$the$next$row$or$column.$$
•  Con/nue$the$process$un/l$all$supply$and$demand$values$are$
exhausted.$$
Application:!
Find$the$ini/al$basic$feasible$solu/on$of$the$following$
transporta/on$problem$using$North$–$West$Corner$Method.$
Solu/on:$
$
$
Factory$ Warehouse$ Supply$

W1$ W2$ W3$ W4$

F1$ 4$ 14$ 2$ 25$ 45$ 5$ 6/2/0$

F2$ 65$ 5$ 25$ 3$ 35$ 55$ 8/3/0$

F3$ 35$ 3$ 3$ 65$ 13$ 15$ 16/13/0$

Demand$ 4/0$ 7/5/0$ 6/3/0$ 13/0$ 30$

The$ini/al$basic$feasible$solu/on$for$the$given$problem$is:$
$

From$ To$ Units$ Cost$per$ Total$Cost$

shipped$ Unit$
F1$ W1$ 4$ 14$ 56$
F1$ W2$ 2$ 25$ 50$
F2$ W2$ 5$ 25$ 125$
F2$ W3$ 3$ 35$ 105$
F3$ W3$ 3$ 65$ 195$
F3$ W4$ 13$ 15$ 195$
726$
Practice!Example:!
Find$the$ini/al$basic$feasible$solu/on$of$the$following$
transporta/on$problem$using$North$–$West$Corner$Method$

Solu/on:$1015$
Least!Cost!Method:!
This$method$usually$provides$a$be`er$ini/al$basic$
feasible$solu/on$than$the$NorthPWest$Corner$
method$since$it$takes$into$account$the$cost$
variables$in$the$problem.$
$
!
Steps!in!Least!Cost!Method!!
!Step1: Select the cell having lowest unit cost in the entire table
and allocate the minimum of supply or demand values in that
cell.
Step2: Then eliminate the row or column in which supply or
demand is exhausted. If both the supply and demand values
are same, either of the row or column can be eliminated.
In case, the smallest unit cost is not unique, then select the
cell where maximum allocation can be made.
Step3: Repeat the process with next lowest unit cost and
continue until the entire available supply at various sources
and demand at various destinations is satisfied.
Application:!
Find$the$ini/al$basic$feasible$solu/on$of$the$following$
transporta/on$problem$using$Least$Cost$Method$
Solu0on:!!
$
$
Factory$ Warehouse$ Supply$

D1$ D2$ D3$

F1$ 2$ 7$ 4$ 5$

F2$ *$ 3$ *$ 3$ 8$ 1$ 8/0$

F3$ 5$ 4$ 7$ 7$

F4$ 1$ 6$ 2$ 14$

Demand$ 7$ 9$ 18/10$ 34$

$
$

Factory$ Warehouse$ Supply$

D1$ D2$ D3$

F1$ *$ 2$ 7$ 4$ 5$

F2$ *$ 3$ *$ 3$ 8$ 1$ 8/0$

F3$ *$ 5$ 4$ 7$ 7$

F4$ 7$ 1$ 6$ 2$ 14/7$

Demand$ 7/0$ 9$ 18/10$ 34$

$
$

Factory$ Warehouse$ Supply$

D1$ D2$ D3$

F1$ *$ 2$ 7$ 4$ 5$

F2$ *$ 3$ *$ 3$ 8$ 1$ 8/0$

F3$ *$ 5$ 4$ 7$ 7$

F4$ 7$ 1$ *$ 6$ 7$ 2$ 14/7/0$

Demand$ 7/0$ 9$ 18/10/3$ 34$

$
$

Factory$ Warehouse$ Supply$

D1$ D2$ D3$

F1$ *$ 2$ 7$ 3$ 4$ 5/2$

F2$ *$ 3$ *$ 3$ 8$ 1$ 8/0$

F3$ *$ 5$ 4$ *$ 7$ 7$

F4$ 7$ 1$ *$ 6$ 7$ 2$ 14/7/0$

Demand$ 7/0$ 9$ 18/10/3/0$ 34$

$
$

Factory$ Warehouse$ Supply$

D1$ D2$ D3$

F1$ *$ 2$ 7$ 3$ 4$ 5/2$

F2$ *$ 3$ *$ 3$ 8$ 1$ 8/0$

F3$ *$ 5$ 7$ 4$ *$ 7$ 7/0$

F4$ 7$ 1$ *$ 6$ 7$ 2$ 14/7/0$

Demand$ 7/0$ 9/2$ 18/10/3/0$ 34$

$
$

Factory$ Warehouse$ Supply$

D1$ D2$ D3$

F1$ *$ 2$ 2$ 7$ 3$ 4$ 5/2/0$

F2$ *$ 3$ *$ 3$ 8$ 1$ 8/0$

F3$ *$ 5$ 7$ 4$ *$ 7$ 7/0$

F4$ 7$ 1$ *$ 6$ 7$ 2$ 14/7/0$

Demand$ 7/0$ 9/2/0$ 18/10/3/0$ 34$

The$ini/al$basic$feasible$solu/on$for$the$given$problem$is:$
$

From$ To$ Units$ Cost$per$ Total$Cost$

shipped$ Unit$
F1$ D2$ 2$ 7$ 14$
F1$ D3$ 3$ 4$ 12$
F2$ D3$ 8$ 1$ 8$
F3$ D2$ 7$ 4$ 28$
F4$ D1$ 7$ 1$ 7$
F4$ D3$ 7$ 2$ 14$
83$
Vogel’s!Approximation!Method!
This$method$also$takes$costs$into$account$in$alloca/on.$
The$Vogel's$approxima/on$method$(VAM)$usually$
produces$an$op/mal$or$nearP$op/mal$star/ng$solu/on.$
One$study$found$that$VAM$yields$an$op/mum$solu/on$in$
80$percent$of$the$sample$problems$tested.$
Steps to solve Vogel’s Approximation method:
Step1: Calculate penalty for each row and column by taking the
difference between the two smallest unit costs. This penalty or
extra cost has to be paid if one fails to allocate the minimum
unit transportation cost.
Step2: Select the row or column with the highest penalty and
select the minimum unit cost of that row or column. Then,
allocate the minimum of supply or demand values in that cell. If
there is a tie, then select the cell where maximum allocation
could be made.
Step3: Adjust the supply and demand and eliminate the satisfied
row or column. If a row and column are satisfied
simultaneously, only of them is eliminated and the other one is
assigned a zero value. Any row or column having zero supply
or demand, can not be used in calculating future penalties.
Step4: Repeat the process until all the supply sources and
demand destinations are satisfied.
$
Application:!
Find$the$ini/al$basic$feasible$solu/on$of$the$following$transporta/on$problem$
using$VAM$(Vogel’s$Approxima/on$Method$)$.$
$
Solu/on:$
$
$
Factory$ Warehouse$ Supply$

W1$ W2$ W3$ W4$

F1$ 19$ 30$ 50$ 10$ 7$ 9$

F2$ 70$ 30$ 40$ 60$ 9$ 10$

F3$ 40$ 8$ 70$ 13$ 20$ 18$ 12$
Demand$ 5$ 8$ 7$ 14$ 34$

21$ 22$ 10$ 10$

$
$

Factory$ Warehouse$ Supply$

W1$ W2$ W3$ W4$

F1$ 19$ *$ 30$ 50$ 10$ 7$ 9$

F2$ 70$ *$ 30$ 40$ 60$ 9$ 10$

F3$ 40$ 8$ 8$ 70$ 13$ 20$ 18/10$ 12$
Demand$ 5$ 8/0$ 7$ 14$ 34$

21$ 22$ 10$ 10$

$
$

Factory$ Warehouse$ Supply$

W1$ W2$ W3$ W4$

F1$ 5$ 19$ *$ 30$ 50$ 10$ 7/2$ 9$

F2$ *$ 70$ *$ 30$ 40$ 60$ 9$ 20$

F3$ *$ 40$ 8$ 8$ 70$ 13$ 20$ 18/10$ 20$
Demand$ 5/0$ 8/0$ 7$ 14$ 34$

21$ 10$ 10$

$
$

Factory$ Warehouse$ Supply$

W1$ W2$ W3$ W4$

F1$ 5$ 19$ *$ 30$ 50$ 10$ 7/2$ 40$

F2$ *$ 70$ *$ 30$ 40$ 60$ 9$ 20$

F3$ *$ 40$ 8$ 8$ *$ 70$ 10$ 20$ 18/10/0$ 50$
Demand$ 5/0$ 8/0$ 7$ 14/4$ 34$

10$ 10$
$
$

Factory$ Warehouse$ Supply$

W1$ W2$ W3$ W4$

F1$ 5$ 19$ *$ 30$ *$ 50$ 2$ 10$ 7/2/0$ 40$

F2$ *$ 70$ *$ 30$ 40$ 60$ 9$ 20$

F3$ *$ 40$ 8$ 8$ *$ 70$ 10$ 20$ 18/10/0$

Demand$ 5/0$ 8/0$ 7$ 14/4/2$ 34$

10$ 50$
$
$

Factory$ Warehouse$ Supply$

W1$ W2$ W3$ W4$

F1$ 5$ 19$ *$ 30$ *$ 50$ 2$ 10$ 7/2/0$

F2$ *$ 70$ *$ 30$ 7$ 40$ 60$ 9/2$ 20$

F3$ *$ 40$ 8$ 8$ *$ 70$ 10$ 20$ 18/10/0$

Demand$ 5/0$ 8/0$ 7/0$ 14/4/2$ 34$

$
$

Factory$ Warehouse$ Supply$

W1$ W2$ W3$ W4$

F1$ 5$ 19$ *$ 30$ *$ 50$ 2$ 10$ 7/2/0$

F2$ *$ 70$ *$ 30$ 7$ 40$ 2$ 60$ 9/2/0$

F3$ *$ 40$ 8$ 8$ *$ 70$ 10$ 20$ 18/10/0$

Demand$ 5/0$ 8/0$ 7/0$ 14/4/2/0$ 34$

The$ini/al$basic$feasible$solu/on$for$the$given$problem$is:$
$

From$ To$ Units$ Cost$per$ Total$Cost$

shipped$ Unit$
F1$ W1$ 5$ 19$ 95$
F1$ W4$ 2$ 10$ 20$
F2$ W3$ 7$ 40$ 280$
F2$ W4$ 2$ 60$ 120$
F3$ W2$ 8$ 8$ 64$
F3$ W4$ 10$ 20$ 200$
779$
Lecture  5:  
 
Op,miza,on   Techniques  for  
Transporta,on  Model  
  
Learning  objectives:  
   
The  learning  objec/ves  of  this  chapter  are  
 
•   Introduc/on  to  Op/mality  tests  unbalanced  problems  for  
transporta/on  problem  .  
•   Stepping  Stone  Method  for  finding  op/mal  Solu/on  
•   Distributed  Modified  Problem  for  prohibited  route  problem.  
•     Degeneracy  
Optimality  Tests.  
There  are  two  tests  to  check  whether  basic  feasible  solu/on  fit  
for  op/mality  test  or  not:  
 
1.  If  there  are  m  number  of  rows  &  n  number  of  columns  then  
number  of  alloca/on  must  be  ((m+n)-­‐1)  

2.   All  alloca/ons  should  be  in  independent  posi/ons  i.e.  there  
should  not  be  able  to  make  closed  loop  from  alloca/ons.  
Which  one  Optimal  Solution?  
In  last  lecture,  we  learn  about  Northeast  corner  method,  Least  
cost  method  &    VAM  out  of  which  found  VAM  generate  more  
op/mal  solu/on  but  it’s  not  always  beLer:  

Solu/ons  method  to  get  Op/mal  solu/on:  

1. Stepping-­‐stone  method

2. Modified  distributed  method  (MODI

 Stepping  Stone  Method  
Is  the  following  an  op/mal  solu/on  for  the  transporta/on  
problem?    
If  not,  how  to  modify  it?        
Solu/on:    
 
Lecture  Handouts.  (For  beLer  understanding  solu/ons  for  
this  chapter  provided  in  lecture  Handouts)  
Modi9ied  Distribution  Method:    
Solu/on:    

Lecture  Handouts.  (For  beLer  understanding  solu/ons  for  

this  chapter  provided  in  lecture  Handouts)  
Degeneracy  

m rows + n column – 1 = the number of cells with allocations

3  + 3 - 1 = 5

It satisfied.

If failed? …… considering …..

 Total  demand  ≠  total  supply  

Note  that,  total  demand=650,  and  total  supply  =  600  

 
How  to  solve  it?  
 
We  need  to  add  a  dummy  row  and  assign  o  cost  to  each  cell  as  such    ..  
  
Extra  row,  since  Demand  >  supply  
 
Extra  Column,  since  Demand  <  supply  
Practice  Example:  Degeneracy  
References:
1. S. V. Rozhkova, O.N. Imas, “Methods of optimization",
Tomsk Polytechnic University 2004.
2. Thomas S. Ferguson, Linear Programming-A concise
Introduction.
3. James K. Strayer, Linear Programming and Applications
(1989) Springer- Verlag.
4. Linear Programming: A Geometric Approach, Willey
Publications.
5. Math 407A: Linear Optimization, Lecture 4: LP Standard
Form Math Dept., The University of Washington.
6. Mark A. Schulze, Linear Programming for Optimization,
Perceptive Scientific Instruments, Inc.
7. Optimization Methods in Management
sciences/Operation Research, Spring 2013, MIT
OpenCourseWare.
8. R. T. Rockafellar, FUNDAMENTALS OF OPTIMIZATION
2007 Lecture Notes, Dept. of Mathematics, University of
Washington.
9. Rejzlin V.i. Numerical optimization methods: manual.-
Tomsk: Publishing House of TPU, 2013-105 p.
10. Lesin, Victor V. Foundations of optimization
methods: study guide/v. Lesin, y. p. Lisovets.-3 ed. Corr.-
St.p.: LAN, 2011-342 p.
11. Attetkov Alexander Vladimirovich. Optimization
techniques: study guide/A. Attetkov, V. N. Zarubin, A. N.
Kanatnikov. - Moscow: Infra-m, 2012.-270 p.
12. Kočegurova E.A. Theory and optimization
techniques [electronic resource]: the manual.-Tomsk:
Publishing House of TPU, 2013. The access Scheme:
http://www.lib.tpu.ru/fulltext2/m/2013/m234.pdf
13. Fedunec, Nina Ivanovna. Optimization techniques:
A training manual for high schools/N. I. Fedunec, Y. V.
Chernikov; Moscow State Mining University (MSMU).-
Moscow: IZD-vo MSMU, 2009.-375 p.
14. Victor A. Goncharov. Optimization techniques
[electronic resource]: tutorial/V.A. Goncharov; National
research University, Moscow Institute of electronic
technology (ELECTRONIC TECHNOLOGY).- The access
Scheme: http://www. lib . tpu . ru / fulltext 2/ (m)
//2014 FN / fn -01. pdf
15. D.l.Horvata, V.A.Gluharev. Optimization
techniques: Tutorial and workshop. Moscow State
University (MGU).-3 ed., Corr. and additional charge. -
Moscow: Harvard Business Press, 2014. — p 367.
16. Sofieva, Julia. Conditional optimization: methods
and objectives/Y. M. Sofieva, A. M. Zirlin. -Ed. 2. -
Moscow: Librokom, 2012. -143 p.