Linear Optimization

Debark University
College of Natural and Computational Science
Department of Mathematics

By: Dereje Tigabu (MSc.)

March 21, 2023

 Contents

1 Linear Programming Models of Practical Problems 1

1.1 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Structure of Linear Programming Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 General structure of LP Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Assumptions of Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.3 Advantages of Using Linear Programming . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.4 Limitations of Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Formulation of Linear Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 GEOMETRIC METHODS 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Terminology for Solution of Linear Programming . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Graphical Solution Methods of LP Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.1 Extreme Point Solution Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.2 Iso-profit (Cost) Function Line Method . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Special Cases in Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4.1 Alternative (or Multiple) Optimal Solutions . . . . . . . . . . . . . . . . . . . . . . 15
2.4.2 Unbounded Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.3 Infeasible Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.4 Redundancy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Convex Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.6 Polyhedral Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

i
Linear Optimization March 21, 2023

2.7 Extreme Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.8 Corner Point Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3 SIMPLEX METHOD 29
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Linear Programs in Standard Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 Basic Feasible Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4 Fundamental Theorem of Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5 Algebra of the Simplex Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.6 The simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.7 Degeneracy and Finiteness of Simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 47
3.8 Finding a Starting Basic Feasible Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.8.1 Two -phase method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.8.2 Big - M method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.9 Some Complications and Their Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.9.1 Unrestricted variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.9.2 Tie for entering basic variable (key column) . . . . . . . . . . . . . . . . . . . . . . 60
3.9.3 Tie for leaving basic variable (key row) – degeneracy . . . . . . . . . . . . . . . . . 61
3.10 Types of Linear Programming Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.10.1 Alternative (multiple) optimal solutions . . . . . . . . . . . . . . . . . . . . . . . . 62
3.10.2 Unbounded solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.10.3 Infeasible solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4 Duality Theory and Further Variation of Simplex Method 67

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2 Dual Linear Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.3 Duality Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.4 Dual –Simplex Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.4.1 Computational Procedure of Dual Simplex Method . . . . . . . . . . . . . . . . . . 77
4.5 The Primal-Dual simplex Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

5 Sensitivity Analysis 83
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2 Variation of coefficients of objective function C T . . . . . . . . . . . . . . . . . . . . . . . . 85
5.3 Variation of vector requirement b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

c Dereje T. (MSc.) ii
Linear Optimization March 21, 2023

5.4 Variation of constraints(matrix coefficients A) . . . . . . . . . . . . . . . . . . . . . . . . . 88

5.5 Addition of a Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.6 Addition of a new constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

6 Transportation Problem 96
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.2 LP Formulation Transportation Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.3 Determination of an initial basic feasible solution . . . . . . . . . . . . . . . . . . . . . . . 99
6.3.1 North West Corner Method(NWCM) . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.3.2 Least cost method or Matrix minima method(LCM) . . . . . . . . . . . . . . . . . . 101
6.3.3 Row / Column Minima method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.3.4 Vogel’s approximation method (VAM) . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.4 Optimality conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.4.1 Modified Distribution Method (MODI) . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.5 Unbalanced transportation problems and their solutions . . . . . . . . . . . . . . . . . . . . 110
6.6 Degenerate transportation problems and their solutions . . . . . . . . . . . . . . . . . . . . 112
6.7 Direct Solution Method of Transportation Problem(Optional) . . . . . . . . . . . . . . . . 115

7 Review Exercise 117

References 121

c Dereje T. (MSc.) iii

 Linear Programming Models of Practical Problems
1
1.1 Linear Programming

1.1.1 Introduction

Optimization is the task of finding one or more solutions which correspond to optimizing one or more
specified objectives and which satisfy all constraints. That is,the process of finding an extreme value
(maximum or minimum) of a quantity (normally called a function) is known as optimization. For example,
maximizing profit and minimizing cost.
Linear programming (LP) is a branch of Mathematics which deals with modeling a decision
problem and subsequently solving it by mathematical techniques. The problem is presented in a form of a
linear function which is to be optimized (i.e maximized or minimized) subject to a set of linear constraints.
The function to be optimized is known as the objective function.
In a decision-making environment, model formulation is important because it represents the essence
of business decision problem. The term formulation is used to mean the process of converting the verbal
description and numerical data into mathematical expressions which represents the relevant relationship
among decision factors, objectives and restriction on the use of resources. LP is defined as a mathematical
modeling technique useful for economic allocation of ’scare’ or ’limited’ resources, such as labour, material,
machine, time, warehouse, space, capital, energy etc., to several competing activities, such as products,
services, jobs, new equipment, project, etc., on the basis of a given criterion of optimality.
Linear programming is a method of obtaining an optimal solution or program (say, product mix in
a production problem), when we have limited resources. LP model is used for optimum allocation of scarce
or limited resources to competing products or activities under the assumptions of certainty, linearity, fixed
technology, and constant profit per unit. The linear programming method is a technique for choosing the
best alternative from a set of feasible alternatives, in situations in which the objective function as well as
the constraints can be expressed as linear mathematical functions.
The phrase scare resources means resources that are not in infinite in availability during the planning
period. The criterion of optimality, generally is either performance, return on investment, profit, cost,
utility, time, distance, etc.
Linear programming is concerned with the optimization (minimization or maximization) of a linear
function while satisfying a set of linear equality and/or inequality constraints or restrictions.
The word linear refers to linear relationship among variables in a model. Thus, a given change in one

1
Linear Optimization March 21, 2023

variable will always cause a resulting proportional change in another variable. For example, doubling the
investment on a certain project will exactly double the rate of return.
The word programming refers to modeling and solving a problem mathematically that involve the
economic allocation of limited resources by choosing a particular course of action or strategy among various
alternative strategies to achieve the desired objective. Many management decisions involve trying to make
the most effective use of an organization’s resources. Resources typically include machinery, labor, money,
time, warehouse, space, or raw materials. Resources may be used to produce products (such as machinery,
furniture, food, or clothing) or services (such as schedules for shipping and production, advertising policies,
or investment decisions).
LP is a widely used mathematical technique designed to help managers in planning and decision mak-
ing relative to resource allocation. Despite the name, linear programming, and the more general category
of techniques called “mathematical programming”, have very little to do with computer programming.
Computer programming has, however, played an important role in the advancement and use of LP to
solve real-life LP problems.

What is Linear programming problem (LPP)?

An LPP is a problem of minimizing or maximizing a linear function in the presence of linear
constraints of the inequality and / or the equality type.
LPP is an optimization problem for which we do the following:

1. We attempt to maximize (or minimize) a linear function of the decision variables. The function
that is to be maximized or minimized is called objective function.

2. The values of decision variables must satisfy a set of constraints. Each constraint must be a
linear equation or linear inequality.

3. A sign restriction is associated with each variable. for any variable xi , the sign restriction
specifies either that xi must be nonnegative (xi > 0) or that xi may be unrestricted in sign.

1.2 Structure of Linear Programming Model

1.2.1 General structure of LP Model

The general structure of LP model consists of three basic elements or components.

1. Decision variables (activities). We need to evaluate various alternatives (course of action) for
arriving at the optimal value of objective function. Obviously, if there are no alternatives to select
from, we would no need LP. The evaluation of various alternatives is guided by the nature of objective
function and availability of resources. For this , we pursue certain activities(also called decision
variable) usually denoted by x1 , x2 , ..., xn . The value of these activities represent the extent to which
each of these is performed. For example, in a product-mix manufacturing, the management may use
LP to decide how many units of each of the product to manufacture by using its limited resources
such as personnel, machinery, money, material,etc.
The value of certain variables may or may not be under the decision maker’s control. If values
are under the the control of decision maker, then such variables are said to be controllable variable
otherwise uncontrollable. These decision variable, usually interrelated in terms of consumption

c Dereje T. (MSc.) 2
Linear Optimization March 21, 2023

of limited resources, requires simultaneous solutions. In an LP model all decision variables are
continuous, controllable and non-negative. that is x1 ≥ 0, x2 ≥ 0, ..., xn ≥ 0.

2. The objective function. The objective (goal) function of each LP problem is expressed in terms
of decision variables to optimize the criterion of optimality(also called measure-of-performance such
as profit, cost, revenue, distance etc. In its general form, it is represented as:
Optimize (Maximize or Minimize ) Z = c1 x1 + c2 x2 + ... + cn xn .
where Z is the measure-of-performance variable, which is the function of x1 , x2 , ..., xn . Quanti-
ties c1 , c2 , ..., cn are parameters that represent the contribution of a unit of the respective variable
x1 , x2 , ..., xn to the measure-of-performance Z. The optimal value of the given objective function is
obtained by the graphical method or simplex method.

3. The constraints. There are always certain limitations (or constraints) on the use of resources,
eg. labour, machine, raw material, space, money, etc. , that limit the degree to which an objective
can be achieved. Such constrains must be expressed as linear equalities or inequalities in terms of
decision variables. The solution of an LP model must satisfy these constraints.

The combination of objective function and its constraints is termed as linear programming problem.

1.2.2 Assumptions of Linear Programming

The following six basic assumptions are necessary for all linear programming models.

1. Certainty. In all LP models, it is assumed, that all model parameters such as availability of
resources, profit (or cost)contribution of a unit of decision variable and consumption of resources by
a unit of decision variable must be known and may be constant. In some cases, these may be either
random variables represented by a known distribution (general or may statistical) or may tend to
change, then the given problem can be solved by stochastic LP model or parametric programming.
That is, the various parameters, namely, the objective function’s coefficients, the coefficients of the
inequality/equality constraints and the constraint (resource) values are known with certainty. The
model assumes that the responses to the values of the variables are exactly equal to the responses
represented by the coefficients.

2. Divisibility (or Continuity). The solution values of decision variables are allowed to assume
continuous values. For instance, it is possible to produce 6.254 thousands gallons of a solvent in
chemical company, so these variables are divisible. But in contrast, it is not desirable to produce
2.5 machines. Such variables are not divisible and therefore must be assigned integer values. Hence,
if any of the variables can assume only integer values or limited to discrete number of values. LP
models is no longer applicable, but an integer programming model may be applied to get the desired
values.

3. Additivity. The value of the objective function and the total amount of each resources used (or
supplied), must be equal to the sum of the respective individual contributions ( profit or cost)by
decision variables. For example, the total profit earned from the sale of two products A and B must
be equal to the sum of the profits earned separately from A and B. similarly , the amount of a
resource consumed for producing A and B must be equal to the sum of resources used for A and B
individually.

4. Linearity (or Proportionality). The amount of each resource used (or supplied) and its contri-
bution to the profit (or cost) in the objective function must be proportional to the value of each

c Dereje T. (MSc.) 3
Linear Optimization March 21, 2023

decision variable. For example,if one unit of a product is assumed to contribute birr 10 towards
profit, then the total contribution would be equal to 10x1 , where x1 is the number of units of the
product. Or if production of one unit of a product uses 5 hours of a particular resource, then making
3 units of that product uses 3 × 5 = 15 hours of that resource.
Linearity also requires that the effects of the value of each variable on the values of the objective
function and the constraints are additive. In other words, there can be no interactions between
the effects of different activities; i.e., the level of activity x1 should not affect the costs or benefits
associated with the level of activity x2 .
These assumptions indicate that the objective function and all the constraints must be characterized
by linear relationship among in LP model. Further, it is also assumed that the LP model is completely
deterministic, having no probabilistic (stochastic) elements.

5. Finiteness: an optimum solution cannot be computed in the situation where there are infinite
number of alternative activities and recourses restriction

6. Optimality: in LP the maximum profit solution or the minimum cost solution always occurs at the
corner point of the set of feasible solutions.

1.2.3 Advantages of Using Linear Programming

Following are certain advantages of using linear programming technique:

1. Linear programming technique helps decision-makers to use their productive resources effectively.

2. Linear programming technique improves the quality of decisions. The decision-making approach of
the user of this technique becomes more objective and less subjective.

3. Linear programming technique helps to arrive at optimal solution of a decision problem by taking
into account constraints on the use of resources. For example, saying that so many units of any
product may be produced does not mean that all units can be sold.

4. Linear programming approach for solving decision problem highlight bottlenecks in the production
processes. For example, when a bottleneck occurs, machine cannot produce sufficient number of
units of a product to meet demand. Also, machines may remain idle

1.2.4 Limitations of Linear Programming

In spite of having many advantages and wide areas of applications, there are some limitations associated
with this technique. These are as follows:

1. Linear programming assumes linear relationships among decision variables. However, in real-life
problems, decision variables, neither in the objective function nor in the constraints are linearly
related.

2. While solving an LP model there is no guarantee that decision variables will get integer value. For
example, how many men/machines would be required to perform a particular job, a non-integer
valued solution will be meaningless. Rounding off the solution to the nearest integer will not yield
an optimal solution.

3. The linear programming model does not take into consideration the effect of time and uncertainty.

c Dereje T. (MSc.) 4
Linear Optimization March 21, 2023

4. Parameters in the model are assumed to be constant but in real-life situations, they are frequently
neither known nor constant.

5. Linear programming deals with only single objective, whereas in real-life situations a decision problem
may have conflicting and multiple objectives

1.3 Formulation of Linear Programming Problems

Mathematically, the general linear programming problem (LPP) may be stated as:

Maximize or Minimize Z = c1 x1 + c2 x2 + ... + cn xn .

Subject to a11 x1 + a12 x2 + ... + a1n xn (≤=≥)b1
a21 x1 + a22 x2 + ... + a2n xn (≤=≥)b2 (1)
.
.
.
am1 x1 + am2 x2 + ... + amn xn (≤=≥)bm
x1 , x2 , ..., xn ≥ 0

Where

1. The function Z is the objective function.

2. x1 , x2 , ..., xn are the decision variables.

3. The expression (≤, =, ≥) means that each constraint may take any one of the three signs.

4. cj (j = 1, ..., n) represents the per unit cost or profit to the j th variable.

5. bi (i = 1, ..., m) is the requirement or availability of the ith constraint.

6. x1 , x2 , ..., xn ≥ 0 is the set of non-negative restriction on the LPP. In real life problems negative
decision variables have no valid meaning.

In formulating the LPP as a mathematical model we shall follow the following five
steps.

1. Find the key decision to be made from the study of the problems, i.e., problem definition.

2. Identify the decision variables and assign symbols to them (eg x, y, z, ... ) . These decision
variables are those quantities whose values we wish to determine.

3. Identify the objective function and express it in terms of the decision variables.

4. Identify the set of constraints or restrictions in the problem and express them as a linear
equations or inequalities which are linear functions of unknown variables.

5. Add the non-negativity condition.

c Dereje T. (MSc.) 5
Linear Optimization March 21, 2023

Example 1.1. A company makes tables in two models; secretarial model and standard model. Each
standard model requires 2 hrs in wood working and 3 hrs in finishing. Each secretarial model requires 3 hrs
in wood working and 5 hrs in finishing. The company has a total of 240 working hrs available in the wood
working department and a total of 390 working hrs available in the finishing department in each week. A
profit of birr 20 is made on each standard model and birr 50 on each secretarial model. Assuming that all
models are sold, formulate the LP model.
Solution:

STEP 1: Problem definition

To determine the number of two types of tables that can be produced and sold per week so as to maximize
the weekly profit given the restriction (constraints).
STEP 2: Variable representation
Let x1 be the number of standard models to be produced and sold.
Let x2 be the number of secretarial models to be produced and sold.
STEP 3: Developing the objective function
The objective is to maximize profit x1 contributes birr 20 to profit and x2 contributes birr 50 to profit.
Thus, Maximize: 20x1 + 50x2 is the objective function.
STEP 4: Constraint identification / system constraints/

2x1 + 3x2 ≤ 240 (wood working)

3x1 + 5x2 ≤ 390 (finishing)
x1 , x2 ≥ 0 (non negativity constraints)
The given data can be organized as follows:

Department Standard tables (x1 ) Secretarial tables (x2 ) [Link](limit)

Wood working 2 3 240
Finishing 3 5 390
Profit 20 50
In summary, the mathematical model for the table problem is:

Max. Profit π = 20x1 + 50x2

Subject to:
2x1 + 3x2 ≤ 240
3x1 + 5x2 ≤ 390
x1 , x2 ≥ 0.
Thus, LP model is formulated.

Exercises

1. An electronic firm produces three types of switching devices. Each type involves a two step assembly
operation. The assembly times are shown below in the following tables:

Models Assembly time per unit (minutes)

Station 1 Station 2
Model A 2.5 3
Model B 1.8 1.6
Model C 2 2.2

c Dereje T. (MSc.) 6
Linear Optimization March 21, 2023

Each station has a daily working time of 7.5 hrs. The manager wants to obtain the greatest possible
profit during the next five working days. Model A yields a profit of birr 8.25 per unit, Model B a
profit of birr 7.5 per unit and Model C a profit of birr 7.8 per unit. Assume that the firm can sell all
its products. During this time, but, it must fill outstanding order for 20 units of each model type.
Formulate the LP model of this problem.

2. (Diet problem): My diet requires that all the food I eat come from one of the four “basic food
groups” (chocolate cake, ice cream, soda, and cheesecake). At present, the following four foods are
available for consumption: brownies, chocolate ice cream, cola, and pineapple cheesecake. Each
brownie costs 50 cents, each scoop of chocolate ice cream costs 20 cents, each bottle of cola costs 30
cents, and each piece of pineapple cheesecake costs 80 cents. Each day, I must ingest at least 500 calo-
ries, 6 oz of chocolate, 10 oz of sugar, and 8 oz of fat. The nutritional content per unit of each food is
Calories Chocolate Sugar Fat
Brownie 400 3 ounce 2 ounce 2 ounce
shown in the following table. Chocolate ice cream (1 scoop) 200 2 2 4
Cola (1 bottle) 150 0 4 1
Pineapple cheesecake (1piece) 500 0 4 5
Formulate a linear programming model that can be used to satisfy my daily nutritional requirements
at minimum costs.

3. Suppose a particular Ford plant can build Escorts at the rate of one per minute, Explorer at the rate
of one every 2 minutes, and Lincoln Navigators at the rate of one every 3 minutes. The vehicles get
25, 15, and 10 miles per gallon, respectively, and Congress mandates that the average fuel economy
of vehicles produced be at least 18 miles per gallon. Ford loses $1000 on each Escort, but makes a
profit of $5000 on each Explorer and $15, 000 on each Navigator and the maximum profit this Ford
plant can make in one 8-hour day. Based on the given information formulate the LP model of this
problem.

4. Green Farm uses at least 800 kg of special feed daily. The special feed is a mixture of corn and
soybean meal with the following compositions:

Feedstuff Protein Fiber Cost ($ per kg)

Corn 0.09 0.02 0.30
Soybean meal 0.60 0.06 0.90
The dietary requirements of the total feed stipulate at least 30% protein and at most 5% fiber.
Green Farm wishes to determine the daily minimum-cost feed mix. Formulate the problem as an LP
problem.

Types of Optimization Problems

Optimization problems can be divided into the following broad categories depending on the type of decision
variables, objective function(s), and constraints.

• Linear programming (LP): The objective function and constraints are linear. The decision vari-
ables involved are scalar and continuous.

• Nonlinear programming (NLP): The objective function and/or constraints are nonlinear. The
decision variables are scalar and continuous.

c Dereje T. (MSc.) 7
Linear Optimization March 21, 2023

• Integer programming (IP): The decision variables are scalars and integers.

• Mixed integer linear programming (MILP): The objective function and constraints are linear.
The decision variables are scalar; some of them are integers whereas others are continuous variables.

• Mixed integer nonlinear programming (MINLP): A nonlinear programming problem involving

integer as well as continuous decision variables.

• Discrete optimization: Problems involving discrete (integer) decision variables. This includes IP,
MILP, and MINLPs.

• Optimal control : The decision variables are vectors.

• Stochastic programming or stochastic optimization: Also termed optimization under uncer-

tainty. In these problems, the objective function and/or the constraints have uncertain (random)
variables. Often involves the above categories as subcategories.

• Multiobjective optimization: Problems involving more than one objective. Often involves the
above categories as subcategories.

c Dereje T. (MSc.) 8
 GEOMETRIC METHODS
2
2.1 Introduction
An optimal as well as a feasible solution to an LP problem is obtained by choosing one set of values from
several possible values of decision variables x1 , x2 , ..., xn , that satisfies the given constraints simultaneously
and also provides an optimal (maximum or minimum) value of the given objective function.
For LP problems that have only two variables, it is possible that the entire set of feasible solutions
can be displayed graphically by plotting linear constraints on a graph paper in order to locate the best
(optimal) solution. The technique used to identify the optimal solution is called the graphical solution
method (approach or technique) for an LP problem with two variables.
Since most real-world problems have more than two decision variables, such problems cannot be solved
graphically. However, graphical approach provides understanding of solving an LP problem algebraically,
involving more than two variables.
In this chapter, we shall discuss the following two graphical solution methods (or approaches):

1. Extreme point solution method

2. Iso-profit (cost) function line method

to find the optimal solution to an LP problem.

2.2 Terminology for Solution of Linear Programming

• Solution: the set of values of decision variables w/c satisfies the constraints of an LPP is said to
constitute solution to the LPP.

• A feasible solution: is a solution for which all the constraints are satisfied.

• A corner point feasible solution (CPF): is a feasible solution that lies at a corner point.

• An infeasible solution: is a solution for which at least one constraint and nonnegativity condition
of an LP problem simultaneously is violated.

9
Linear Optimization March 21, 2023

• Basic solution for a set of m simultaneously equation in n variables (n > m), a solution obtained
by setting (n-m) variables equal to zero and solving for remaining m equations in n variables is called
basic solution.
• The (n-m) variables whose value did not appear in this solution are non-basic variables and the
remaining m variables are called basic variables
• Basic feasible solution: A feasible solution to an LPP which is also the basic solution is called
the basic feasible solution, that is, all basic variables assume non-negative value.
• Basic feasible solutions are two types
– Degenerate : A BFS is called degenerate if value of at least one basic variable is zero.
– Non-degenerate: A BFS is called non-degenerate if values all m basic variables are non-zero
and positive
• The feasible region is the collection of all feasible solution.
• An Optimal solution is a feasible solution that has the most favorable value of the objective
function. (it is always one of the CPF solution.
• The most favorable value is the largest (smallest) value if the objective function is to be maximized
(minimized).
• Optimum basic feasible solution: A basic feasible solution that optimizes (maximizes or min-
imizes) the objective function value of the given LP problem is called an optimum basic feasible
solution.
• Unbounded solution: A solution that can increase or decrease infinitely the value of the objective
function of the LP problem is called an unbounded solution.

2.3 Graphical Solution Methods of LP Problem

2.3.1 Extreme Point Solution Method

In this method, the coordinates of all corner (or extreme) points of the feasible region (space or area) are
determined and then value of the objective function at each of these points is computed and compared.
The coordinates of an extreme point where the optimal (maximum or minimum) value of the objective
function is found represent solution of the given LP problem. The steps of the method are summarized as
follows:

Step 1: Formulate the linear programming problem.

Step 2: Graph the feasible region and find the corner points. The coordinates of the corner points
can be obtained by either inspection or by solving the two equations of the lines intersecting
at that point.

Step 3: Make a table listing the value of the objective function at each corner point.

Step 4: Determine the optimal solution from the table in step 3. If the problem is of maximization
(minimization) type, the solution corresponding to the largest (smallest) value of the objective
function is the optimal solution of the LPP.

c Dereje T. (MSc.) 10
Linear Optimization March 21, 2023

Example 2.1. Use the graphical method to solve the following LP problem.
Maximize Z = 15x1 + 10x2
subject to the constraints

(i) 4x1 + 6x2 ≤ 360,

(ii) 3x1 + 0x2 ≤ 180,
(iii) 0x1 + 5x2 ≤ 200
and x1 , x2 ≥ 0.

Solution

1. The given LP problem is already in mathematical form.

2. Treat x1 as the horizontal axis and x2 as the vertical axis. Plot each constraint on the graph by
treating it as a linear equation and it is then that the appropriate inequality conditions will be used
to mark the area of feasible solutions.
Consider the first constraint 4x1 + 6x2 ≤ 360. Treat this as the equation 4x1 + 6x2 = 360. For this
find any two points that satisfy the equation and then draw a straight line through them. The two
points are generally the points at which the line intersects the x1 and x2 axes. For example, when
x1 = 0 we get 6x2 = 360 or x2 = 60. Similarly when x2 = 0, 4x1 = 360, x1 = 90.
These two points are then connected by a straight line as shown in [Link]. But the question is:
Where are these points satisfying 4x1 + 6x2 ≤ 360. Any point above the constraint line violates the
inequality condition. But any point below the line does not violate the constraint. Thus, the inequality
and non-negativity condition can only be satisfied by the shaded area (feasible region) as shown in
Fig. below. Similarly, the constraints 3x1 ≤ 180 and 5x2 ≤ 200 are also plotted on the graph and are

indicated by the shaded area as shown in Fig. (b).

Since all constraints have been graphed, the area which is bounded by all the constraints lines including
all the boundary points is called the feasible region (or solution space). The feasible region is shown
in Fig. (b) by the shaded area OABCD.

3. (a) Since the optimal value of the objective function occurs at one of the extreme points of the
feasible region, it is necessary to determine their coordinates. The coordinates of extreme points
of the feasible region are: O = (0, 0), A = (60, 0), B = (60, 20), C = (30, 40), D = (0, 40).
(b) Evaluate objective function value at each extreme point of the feasible region as shown in the
Table below:

c Dereje T. (MSc.) 11
Linear Optimization March 21, 2023

Extreme Point Coordinates Objective Function Value

(x1 , x2 ) Z = 15x1 + 10x2
O (0, 0) 15(0) + 10(0) = 0
A (60, 0) 15(60) + 10(0) = 900
B (60, 20) 15(60) + 10(20) = 1,100
C (30, 40) 15(30) + 10(40) = 850
D (0, 40) 15(0) + 10(40) = 400
(c) Since objective function Z is to be maximized, from Table above we conclude that maximum
value of Z = 1, 100 is achieved at the point extreme B(60, 20). Hence the optimal solution to
the given LP problem is: x1 = 60, x2 = 20 and Max Z = 1,100.

Remark 2.3.1. To determine which side of a constraint equation is in the feasible region, examine
whether the origin (0, 0) satisfies the constraints. If it does, then all points on and below the
constraint equation towards the origin are feasible points. If it does not, then all points on and above
the constraint equation away from the origin are feasible points.

Activity 1. 1. Use the graphical method to solve the following LP problem.

Maximize Z = 2x1 + x2

subject to the constraints

x1 + 2x2 ≤ 10,

x1 + x2 ≤ 6,
x1 − x2 ≤ 2,
x1 − 2x2 ≤ 1

and
x1 , x2 ≥ 0
.

2. Use the graphical method to solve the following LP problem.

Minimize Z = 3x1 + 2x2

subject to the constraints

(i)5x1 + x2 ≥ 10, (ii)x1 + x2 ≥ 6, (iii)x1 + 4x2 6= 12

and

x1 , x2 ≥ 0.

3. Use the graphical method to solve the following LP problem.

c Dereje T. (MSc.) 12
Linear Optimization March 21, 2023

Minimize Z = −x1 + 2x2

subject to the constraints
(i) − x1 + 3x2 ≤ 10, (ii)x1 + x2 ≤ 6, (iii)x1 − x2 ≤ 2
and x1 , x2 ≥ 0.
4. A firm is engaged in producing two products, A and B. Each unit of product A requires 2 kg of
raw material and 4 labor hours for processing, whereas each unit of product B requires 3 Kg of raw
material and 3 hours of labor, of the same type. Every week, the firm has an availability of 60 kg of
raw material and 96 labor hours. One unit of product A sold yields Birr 40 and one unit of product B
sold gives Birr 35 as profit. Assume that there is no marketing constraint so that all that is produced
can be sold.
(a) Formulate the linear programming model
(b) Using the graphical method, determine how many units of each of the products should be produced
per week so that the firm can earn the maximum profit? Interpret the result.
Let x1 = number of units of product A produced and x2 = number of units of product B produced.
The Linear Programming model of this problem is written as:

Max. π = 40x1 + 35x2

Subject to : 2x1 + 3x2 ≤ 60
4x1 + 3x2 ≤ 96
x1 , x2 ≥ 0
5. A manufacturer of light weight mountain tents makes two types of tents, REGULAR tent and
SUPER tent. Each REGULAR tent requires 1 labor-hour from the cutting department and
3 labor-hours from the assembly department. Each SUPER tent requires 2 labor-hours from the
cutting department and 4 labor-hours from the assembly department. The maximum labor hours
available per week in the cutting department and the assembly department are 32 and 84 respectively.
Moreover, the distributor, because of demand, will not take more than 12 SUPER tents per week.
The manufacturer sales each REGULAR tents for $160 and costs $110per tent to make, Where
as SUPER tent sales for $210 per tent and costs $130 per tent to make.
Required:
(a) Formulate the mathematical model of the problem
(b) Using the graphical method, determine how many of each tent the company should manufacture
each tent the company should manufacture each week so as to maximize its profit?
(c) What is this maximum profit assuming that all the tents manufactured in each week are sold in
that week?

Note:

1. The optimal solution is obtained at the corner point( vertex) of a feasible set.

2. If there is only one vertex in which the function is maximum/minimum, then this vertex
consitutes a unique solution to the problem.

3. If the objective function is maximized/minimized at two adjacent corner points of the feasible
set, then there are infinitely many optimal.

c Dereje T. (MSc.) 13
Linear Optimization March 21, 2023

2.3.2 Iso-profit (Cost) Function Line Method

According to this method, the optimal solution is found by using the slope of the objective function line
(or equation). An iso-profit (or cost) line is a collection of points that give solution with the same value
of objective function. By assigning various values to Z, we get different profit (cost) lines. Graphically
many such lines can be plotted parallel to each other. The steps of iso-profit (cost) function method are
as follows:

Step 1: Identify the feasible region and extreme points of the feasible region.

Step 2: Draw an iso-profit (iso-cost) line for an arbitrary but small value of the objective function
without violating any of the constraints of the given LP problem. However, it is simple to pick
a value that gives an integer value to x1 when we set x2 = 0 and vice-versa. A good choice is
to use a number that is divided by the coefficients of both variables.

Step 3: Move iso-profit (iso-cost) lines parallel in the direction of increasing (decreasing) objective
function values. The farthest iso-profit line may intersect only at one corner point of feasible
region providing a single optimal solution. Also, this line may coincide with one of the boundary
lines of the feasible area. Then at least two optimal solutions must lie on two adjoining corners
and others will lie on the boundary connecting them. However, if the iso-profit line goes on
without limit from the constraints,then an unbounded solution would exist. This usually
indicates that an error has been made in formulating the LP model.

Step 4: An extreme (corner) point touched by an iso-profit (or cost) line is considered as the optimal
solution point. The coordinates of this extreme point give the value of the objective function.

Example 2.2. Consider the LP problem

Maximize Z = 15x1 + 10x2

subject to the constraints

(i)4x1 + 6x2 ≤ 360, (ii)3x1 ≤ 180, (iii)5x2 ≤ 200

and

x1 , x2 ≥ 0.

Plot each constraint on a graph first treating it as a linear equation. Then use inequality sign of each
constraint to mark feasible solution region (shaded area) as shown in Fig. below.
A family of lines (shown by dotted lines) that represents various values of objective function is shown
in [Link]. Such lines are referred as iso-profit lines. In Fig. below, a value of Z = 300 is arbitrarily
selected. The iso-profit (objective) function equation then becomes: 15x1 + 10x2 = 300. This equation is
also plotted in the same way as other equality constraints plotted before. This line is then moved upward
until it first intersects a corner (or corners) in the feasible region (corner B). The coordinates of corner
point B can be read from the graph or can be computed as the intersection of the two linear equations.
The coordinates x1 = 60 and x2 = 0 of corner point B satisfy the given constraints and the total profit
obtained is Z = 1, 100.

c Dereje T. (MSc.) 14
Linear Optimization March 21, 2023

2.4 Special Cases in Linear Programming

2.4.1 Alternative (or Multiple) Optimal Solutions

We have seen that the optimal solution of any linear programming problem occurs at an extreme point
of the feasible region and that the solution is unique, i.e. no other solution yields the same value of
the objective function. However, in certain cases, a given LP problem may have more than one solution
yielding the same optimal objective function value. Each of such optimal solutions is termed as alternative
optimal solution.

There are two conditions that should be satisfied for an alternative optimal solution to exist:

i. The slope of the objective function should be the same as that of the constraint forming the
boundary of the feasible solutions region, and

ii. The constraint should form a boundary on the feasible region in the direction of optimal move-
ment of the objective function. In other words, the constraint should be an active constraint.

Remark 2.4.1. The constraint is said to be active (binding or tight), if at the point of optimality,
the left-hand side of a constraint equals the right-hand side. In other words, an equality constraint
is always active, and inequality constraint may or may not be active.

Geometrically, an active constraint is one that passes through one of the extreme points of the feasible
solution space.
Example 2.3. Use the graphical method to solve the following LP problem.

Maximize Z = 10x1 + 6x2

subject to the constraints

(i)5x1 + 3x2 ≤ 30, (ii)x1 + 2x2 ≤ 18

c Dereje T. (MSc.) 15
Linear Optimization March 21, 2023

and

x1 , x2 ≥ 0.

Solution The constraints are plotted on a graph by first treating these as equations and then their inequality
signs are used to identify feasible region (shaded area) as shown in [Link]. The extreme points of the
region are O, A, B and C Since objective function (iso-profit line) is parallel to the line BC (first constraint

:5x1 + 3x2 = 30), which also falls on the boundary of the feasible region. Thus, as the iso-profit line moves
away from the origin,it coincides with the line BC of the constraint equation line that falls on the boundary
of the feasible region. This implies that an optimal solution of LP problem can be obtained at any point
between B and C including extreme points B and C on the same line. Therefore, several combinations of
values of x1 and x2 give the same value of objective function.
The value of variables x1 and x2 obtained at extreme points B and C should only be considered to
establish that the solution to an LP problem will always lie at an extreme point of the feasible region.
The value of objective function at each of the extreme points is shown in Table below.

Extreme Point Coordinates Objective Function Value

(x1 , x2 ) Z = 10x1 + 6x2
O (0, 0) 10(0) + 6(0) = 0
A (0, 9) 10(0) + 6(9) = 54
B (6/7, 60/7) 10(6/7) + 6(60/7) = 60
C (6, 0) 10(6) + 6(0) = 60

Since value (maximum) of objective function, Z = 60 at two different extreme points B and C is same,
therefore two alternative solutions: x1 = 6/7, x2 = 60/7 and x1 = 6, x2 = 0 exist.

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

Department Machine hours per week Maximum available hrs

Product A Product B
Cutting 3 6 900
Assembly 1 1 200
Profit per unit 8 16

c Dereje T. (MSc.) 16
Linear Optimization March 21, 2023

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:

1. Formulate the LPP of this problem.

2. Find the optimal solution.

Solution:

Let x1 = the No. of units of product A produced per week.

x2 = the No. of units of product B produced per week
(a) The LP Model of the problem is:

Max. π = 8x1 + 16x2

Subject to: 3x1 + 6x2 ≤ 900

x1 + x2 ≤ 200
x2 ≤ 125
x1 , x2 ≥ 0

Corners Coordinates Value of π = 8x1+ 16x2

A (0, 0) 0
B (0, 125) 2000
C (50, 125) 2400
D (100, 100) 2400
E (200, 0) 1600

Interpretation: Both C and D are optimal solutions. Any point on the line segment CD will also
lead to the same optimal solution. This implies that Multiple optimal solutions provide more choices for
management to reach their objectives.

c Dereje T. (MSc.) 17
Linear Optimization March 21, 2023

Remark 2.4.2. If slope of a constraint is parallel to the slope of the objective function, but it does
not fall on the boundary of the feasible region, the multiple solutions will not exist. This type of a
constraint is called redundant constraint (a constraint whose removal does not change the feasible
region.)

2.4.2 Unbounded Solution

Sometimes an LP problem may have an infinite solution. Such a solution is referred as an unbounded
solution. It happens when value of certain decision variables and the value of the objective function
(maximization case) are permitted to increase infinitely, without violating the feasibility condition.
It may be noted that there is a difference between unbounded feasible region and unbounded solution
to a LP problem. It is possible that for a particular LP problem the feasible region may be unbounded but
LP problem solution may not be unbounded, i.e. an unbounded feasible region may yield some definite
value of the objective function. In general, an unbounded LP problem solution exists due to improper
formulation of the real-life problem.
Example 2.5. Use the graphical method to solve the following LP problem: Maximize Z = 3x1 + 4x2
subject to the constraints

(i)x1 − x2 ≥ −1 (ii) − x1 + x2 ≤ 0
and
x1 , x2 ≥ 0.

Solution Plot on a graph each constraint by first treating it as a linear equation. Then use the inequality
condition of each constraint to mark the feasible region (shaded area) as shown in Fig. below.

It may be noted from [Link] that there exist an infinite number of points in the convex region for which
the value of the objective function increases as we move from the extreme point (origin), to the right. That
is, the value of variables x1 and x2 can be made arbitrarily large and accordingly the value of objective
function Z will also increase. Thus, the LP problem has an unbounded solution.
Example 2.6. Consider the following maximization problem

Max. Z = 3x1 + 2x2

S.t: x1 − x2 ≤ 1
x1 + x2 ≥ 3
x1 , x2 ≥ 0

c Dereje T. (MSc.) 18
Linear Optimization March 21, 2023

Note here that the two corners of the region are A(0, 3) and B(2, 1). The value of Max Z(A) = 6
and Max 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 im-
plies that there exits an infinite number of solutions.

2.4.3 Infeasible Solution

An infeasible solution to an LP problem arises when there is no solution that satisfies all the constraints
simultaneously. This happens when there is no unique (single) feasible region. This situation arises when
a LP model that has conflicting constraints. Any point lying outside the feasible region violates one or
more of the given constraints.

Example 2.7. Use the graphical method to solve the following LP problem:

Maximize Z = 6x1 − 4x2

subject to the constraints

(i)2x1 + 4x2 ≤ 4 (ii)4x1 + 8x2 ≥ 16

and

x1 , x2 ≥ 0

Solution The constraints are plotted on graph as usual as shown in Fig.. Since there is no unique feasible
solution space, therefore a unique set of values of variables x1 and x2 that satisfy all the constraints cannot
be determined. Hence, there is no feasible solution to this LP problem because of the conflicting constraints.

Example 2.8. Consider the following maximization problem

Max. Z = 20x1 + 30x2

c Dereje T. (MSc.) 19
Linear Optimization March 21, 2023

St: 2x1 + x2 ≤ 40
4x1 + x2 ≤ 60
x1 ≥ 30
x1 , x2 ≥ 0
Solution:

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.

2.4.4 Redundancy

A redundant constraint is one that does not affect the feasible solution region (or space) and thus redun-
dancy of any constraint does not cause any difficulty in solving an LP problem graphically. As shown in
Fig. below, constraint 8x1 + 4x2 ≥ 80 is redundant. In other words, a constraint is said to be redundant
when it may be more binding (restrictive) than another.

Remark 2.4.3. We can always convert a minimization problem into a maximization problem and
vice versa. Indeed, min f (x) = max (−f (x)) and max f (x) = min (−f (x)).

That is, to change a maximization problem to a minimization. problem, just multiply the objective
function by −1.

c Dereje T. (MSc.) 20
Linear Optimization March 21, 2023

2.5 Convex Sets

Definition 2.5.1. A point X ∈ Rn is called a convex linear combination (clc) of two points xl and
x2 , if it can be expressed as:

X = α1 x1 + α2 x2 , where α1 , α2 ≥ 0, & α1 + α2 = 1.

Geometrically speaking, convex linear combination of any points xl and x2 is a line segment joining
x1 and x2 .

Example 2.9. let Xl = (1, 2) and X2 = (3, 7). Then,

X = ( 31 )(1, 2) + ( 23 )(3, 7)) = ( 13 , 23 ) + (2, 14
3
) = ( 73 , 16
3
) is a point lying on the line joining Xl and X2 .

Definition 2.5.2. A subset S of Rn is said to be convex set if for any given two points x, y ∈ S ,
and any λ ∈ [0, 1] implies that λx + (1 − λ)y ∈ S.

Geometrically, this definition may be interpreted as the line segment joining every pair of points
x1 , x2 of S lies entirely in S for more illustration see the following figures.

c Dereje T. (MSc.) 21
Linear Optimization March 21, 2023

• By convention empty set is convex.

• Every singleton set is convex.

• A straight line is a convex set.

• A plane in R3 is also a convex set.

Example 2.10. (a) Let U 6= 0 be a linear functional and α ∈ R. Then show that

(i) The upper half space H + = {x : x ∈ Rn , U (x) ≥ α} and

(ii) The lower half space H − = {x : x ∈ Rn , U (x) ≤ α} are convex sets.
(iii) The hyper plane H = {x : x ∈ Rn , U (x) = α} is a convex set.

Proof. (i) Let x, y ∈ H + , then U (x) ≥ α&U (y) ≥ α and λ ∈ [0, 1].
Now, U (λx + (1 − λ)y) = U (λx) + U ((1 − λ)y)
= λU (x) + (1 − λ)U (y) [Since, U is a linear functional]
≥ λα + (1 − λ)α = α.
∴ λx + (1 − λ)y ∈ H + . Hence, H + is convex set.

(b) Let A be an m × n matrix and b ∈ Rn , then the set P = {x ∈ Rn , Ax ≤ b} polyhedral set is convex
set.

Proof. Let x, y ∈ P , then Ax ≤ b&Ay ≤ b and λ ∈ [0, 1]. Claim: λx + (1 − λ)y ∈ P .

Now, A(λx + (1 − λ)y) = A(λx) + A((1 − λ)y)
= λ(Ax) + (1 − λ)(Ay)
≤ λb + (1 − λ)b = b
∴ λx + (1 − λ)y ∈ P . Hence, P is a convex set.

(c) Rn is a convex set.

Proof. Let x, y ∈ Rn and λ ∈ [0, 1], where x = (x1 , x2 , ..., xn )&y = (y1 , y2 , ..., yn ).
Now λx + (1 − λ)y = λ(x1 , x2 , ..., xn ) + (1 − λ)(y1 , y2 , ..., yn )
= (λx1 , λx2 , ..., λxn ) + ((1 − λ)y1 , ...., (1 − λ)yn )
= (λx1 + (1 − λ)y1 , ..., λxn + (1 − λ)yn ).
If x1 , y1 ∈ R, then λx1 + (1 − λ)y1 ∈ R.
∴ λx + (1 − λ)y ∈ Rn . Hence, Rn is convex set.

c Dereje T. (MSc.) 22
Linear Optimization March 21, 2023

Theorem 2.5.1.

1. If S is a convex set and β is a real number, then the set

βS = {x : x = βv, v ∈ S}

is also convex.

2. If S1 and S2 are convex sets, then the set

S1 + S2 = {x : x = v1 + v2 , v1 ∈ S1 , v2 ∈ S2 }

is also convex.

3. Intersection of two convex sets is convex set.

4. The union of two or more convex sets may not be convex set.

Proof. 1. Let βv1 , βv2 ∈ βS, where v1 , v2 ∈ S. Because S is convex, we have λv1 + (1 − λ)v2 ∈ S for any
λ ∈ [0, 1]. Hence,λβv1 + (1 − λ)βv2 = β(λv1 + (1 − λ)v2 ) ∈ βS and thus βS is convex.

Proof. 2. Let v1 , v2 ∈ S1 + S2 Then, v1 = v10 + v100 , and v2 = v20 + v200 , where v10 , v20 ∈ S1 , and v100 , v200 ∈ S2 .
Because S1 and S2 are convex, for all λ ∈ [0, 1],

x1 = λv10 + (1 − λ)v20 ∈ S1

and
x2 = λv100 + (1 − λ)v200 ∈ S2
By definition of S1 + S2 , x1 + x2 ∈ S1 + S2 . Now,

λv1 + (1 − λ)v2 = λ(v10 + v100 ) + (1 − λ)(v20 + v200 )

= (λv10 + (1 − λ)v20 ) + (λv100 + (1 − λ)v200 )
= x1 + x2 ∈ S1 + S2 .

Hence, S1 + S2 is convex.

Proof. 3. Let S1 and S2 be two convex sets. We have to show that S1 ∩ S2 is a convex set. If this
intersection is empty or singleton there is nothing to prove. Let X1 and X2 be two arbitrary points in
S1 ∩ S2 . Then X1 , X2 ∈ S1 and X1 , X2 ∈ S2 . Since S1 and S2 are convex, we have λX1 + (1 − λ)X2 ∈ S1
and λX1 + (1 − λ)X2 ∈ S2 , λ ∈ [0, 1]. Thus,λX1 + (1 − λ)X2 ∈ S1 ∩ S2 . Hence S1 ∩ S2 is convex.

Proof. 4. Disprove by counter example:

As an example the sets S1 = {(x1 , 0) : x1 ∈ R} and S2 = {(0, x2 ) : x1 ∈ R} are convex in xy-plane, but
their union S1 ∪ S2 = {(x1 , 0), (0, x2 ) : x1 , x2 ∈ R} is not convex, since (2, 0), (0, 2) ∈ S1 ∪ S2 , but their clc,
( 12 )(2, 0) + ( 12 )(0, 2) = (1, 1) ∈
/ S1 ∪ S2

c Dereje T. (MSc.) 23
Linear Optimization March 21, 2023

Hyper planes and half-spaces

A hyper plane in Rn generalizes the notion of a straight line in R2 and the notion of a plane in R3 .

A hyper plane H in Rn is a set of the form {x : px = k} where p is a non zero vector in Rn and k is
a scalar, here p is called the normal or gradient to the hyper plane.

Equivalently, a hyper plane consists of all points x = {x1 , x2 , ..., xn } satisfying the equation nj=1 pj xj =
P
k. The constant k can be eliminated by referring to a fixed point x0 on the hyper plane. if x0 in H, then
px0 = k, and for any x in H , we have px = k. Up on substraction we get p(x − x0 ) = 0. In other words,
H can represented as the collection of points satisfying p(x − x0 ) = 0, where x0 is any fixed point in H.

A hyper plane divides Rn into two regions , called half-spaces. Hence, a half-space (upper) is a
collection of points of the form {x : px ≥ k}, where p is non zero vector in Rn and k is a scalar. A
half-space (lower) can be also be represented as a set of points of the form {x : px ≤ k}. The
union of the two half-space {x : px ≥ k} and {x : px ≤ k} is Rn .

2.6 Polyhedral Sets

n
The convex combination of a set of m points x1 , x2 , ..., x m in R is also a point x in the same
P m
space given by x = λ1 x1 + ... + λm xm and λi ≥ 0, ∀i and i=1 λi = 1. This point set is known as
the convex polyhedron.

Theorem 2.6.1. Let K ⊂ Rn be a convex setP xm ∈ K, then each convex combi-

and let x1 , x2 , ...,P
nation of x1 , x2 , ..., xm belongs to K, i.e., Z = i=1 λi xi ∈ K if m
m
i=1 λi = 1&λi ≥ 0, i = 1, 2, . . . m.
(Proof it using induction on n by starting n = 2)

Definition 2.6.1. (Convex hull) If X be a point set, then the convex hull of X which is denoted
by Conv(X), is the set of all convex combinations of sets of points from X. If the set X consists
of a finite number of points, then convex hull Conv(X) is called a convex polyhedron, which is a
convex set.

Definition 2.6.2. (Convex hull): The intersection of all convex sets containing set A is called
convex hull of A. It is the smallest convex
T set containing A. Or
Let A ⊆ Rn , then the set Conv(A) = {K : A ⊂ K ⊆ Rn , Kis convex set} is called convex hull of
A.

Example 2.11. If x is a point set consists of only eight vertices of a cube then Conv(X) is the whole cube
which is also a convex polyhedron.
Example 2.12. A circle with all its interior point is a convex hull because all boundary points are extreme
points which are not finite, thus a circle with all its interior points is a convex hull but not a convex
polyhedron.

c Dereje T. (MSc.) 24
Linear Optimization March 21, 2023

Example 2.13. To get a feeling for convex hulls, it is important to play around with (lots of ) examples
in the plane. Below you see a finite subset of points in the plane. To the right you have its convex hull.

Note:

1. All convex polyhedron are convex but all convex hulls may or may not be a convex polyhedron.

2. For a convex polyhedron, any point in the set can be expressed as a convex combination its
extreme points.

Polyhedral sets represent important special cases of convex sets.

A polyhedral set or a polyhedron is the intersection of a finite number of half-spaces. A bounded

polyhedral set is called a polytope.

Since a half space can be represented by inequality of the type ai x ≤ bi , then a polyhedral set can
be represented by the system ai x ≤ bi , for i = 1, 2, ..., m. Hence, a polyhedral set can be represented by
{x : Ax ≤ b} where A is m × n matrix whose ith row is ai and b is an m-vector. Since an equation can be
written as two inequalities, a polyhedral set can be represented by a finite number of linear inequalities
and/or equations. As an example consider the polyhedral set defined by the following inequalities:

−2x1 + x2 ≤ 4
x1 + x2 ≤ 3
x1 ≥ 0
x2 ≥ 0

Clearly the set is convex set. We can see a distinct difference between the first inequality and the remaining
inequalities. If the first inequality is disregarded the polyhedral set is not affected. Such an inequality is
called (geometrically) redundant or irrelevant to the polyhedral set.

2.7 Extreme Points

The notion of extreme points plays an especially important role in the theory of linear programming.

Definition 2.7.1. A point x of a convex set X is an extreme point if and only if

x = λx1 + (1 − λ)x2 , 0<λ<1

implies x1 = x2 = x, or x1 ∈
/ X, or x2 ∈/ X. In other words, there is no way to express an extreme
point x of convex set X as an interior point of a line segment where the two distinct endpoints x1
and x2 both belong to X.

c Dereje T. (MSc.) 25
Linear Optimization March 21, 2023

The Figure given below shows some examples of extreme and nonextreme points of convex sets. Note
that x1 is an extreme point of X, whereas x2 and x3 are not.

Example 2.14. The only extreme points of the convex set in Figure below are A, B, C, D, and E (verify).

Remark 2.7.1. A point x of a convex set X is not an extreme point of X if and only if

x = λx1 + (1 − λ)x2

for distinct points x1 , x2 ∈ X and λ with 0 < λ < 1.

2.8 Corner Point Theorem

Theorem 2.8.1. (Fundamental Theorem of Linear Programming)

If a linear programming problem has an optimal solution, then the optimal solution must occur at one(or
more) of the corner point.
Theorem 2.8.2. (Existence of solution theorem)
Let S be the set of feasible solutions to a general linear programming problem.

1. If S is nonempty and bounded, then an optimal solution to the problem exists and occurs at an
extreme point.
2. If S is nonempty and not bounded and if an optimal solution to the problem exists, then an optimal
solution occurs at an extreme point.
3. If S is unbounded and the coefficients of the objective function are positive, then the minimum value
of the objective function exists, but the maximum value is not finite.

c Dereje T. (MSc.) 26
Linear Optimization March 21, 2023

4. If an optimal solution to the problem does not exist, then either S is empty or S is unbounded.
5. If S is empty, then both the maximum and the minimum values of the objective function do not exist.
Example 2.15. Consider the linear programming problem

Maximize z = 120x + 100y

subject to

2x + 2y ≤ 8
5x + 3y ≤ 15
x ≥ 0, y ≥ 0 .

The convex set of all feasible solutions is shown as the shaded region in Figure below.

The extreme points of the convex set S are (0, 0), (3, 0), (0, 4), and ( 32 , 52 ). Since S is nonempty
and bounded, the objective function attains its maximum at an extreme point of S (Theorem 2.8.2). We
can find which extreme point is the optimal solution by evaluating the objective function at each extreme
point. This evaluation is shown in Table below.

Extreme point Value of objective function

(x,y) z = 120x + 100y
(0,0) 0
(3,0) 360
(0,4) 400
( 32 , 52 ) 430

The maximum value of z occurs at the extreme point ( 23 , 52 ). Thus, an optimal solution is x = 3
2
and y =
5
2
. These amounts will yield the maximum profit of $430 per day.

Some linear programming problems have no solution.

c Dereje T. (MSc.) 27
Linear Optimization March 21, 2023

Example 2.16. Consider the linear programming problem:

Maximize z = 2x + 5y
subject to
2x + 3y ≥ 12
3x + 4y ≤ 12
x ≥ 0, y ≥ 0.

The convex set of all feasible solutions consists of the points that lie in all four half-spaces defined
by the constraints. The sketch of these half-spaces in Figure below shows that there are no such points.
The set of feasible solutions is empty. This situation will arise when conflicting constraints are put on a
problem. The assumptions for the model must be changed to yield a nonempty set of feasible solutions.

c Dereje T. (MSc.) 28
 SIMPLEX METHOD
3
3.1 Introduction
Most real-life problems when formulated as an LP model have more than two variables and therefore
need a more efficient method to suggest an optimal solution for such problems. In this chapter, we shall
discuss a procedure called the simplex method for solving an LP model of such problems. This method
was developed by G B Dantzig in 1947.
The concept of simplex method is similar to the graphical method. In the graphical method, extreme points
of the feasible solution space are examined in order to search for the optimal solution that lies at one of
these points. For LP problems with several variables, we may not be able to graph the feasible region, but
the optimal solution will still lie at an extreme point of the many-sided, multidimensional figure (called
an n-dimensional polyhedron) that represents the feasible solution space. The simplex method examines
these extreme points in a systematic manner, repeating the same set of steps of the algorithm until an
optimal solution is found. It is for this reason that it is also called the iterative method.
Since the number of extreme points of the feasible solution space are finite, the method assures an im-
provement in the value of objective function as we move from one iteration (extreme point) to another and
achieve the optimal solution in a finite number of steps. The method also indicates when an unbounded
solution is reached.

Slack variables : If the constraints are in the form of ”≤”, then we add variable to the left hand
side of inequality to make equality. This variables are called slack variables.

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

Surplus variables : If the constraints are in the form of ” ≥ ” , then we subtract variables
to the left hand side of inequality to make equality. This variables are called the surplus variables.

29
Linear Optimization March 21, 2023

Remark: A surplus variable represents amount by which solution values exceed a resource. These
variables are also called negative slack variables. Surplus variables like slack variables carry a zero
coefficients in the objective function.

Conditions for Application of Simplex Method

1. The right hand side of each of the constraint bi should be non-negative. If LPP has a negative
constraint, we should convert it to positive by multiplying both sides by -1.

2. Each of the decision variables of the problem should be non-negative. If one of the choice variables
is not feasible we can’t apply the Simplex method. Therefore feasibility is the necessity condition
for application of the Simplex method.

3. The inequality constraint of resources or any other activities must be converted in to equality equa-
tions by adding slack variables (≤ type inequality) or by subtracting surplus variables (≥ type
inequality) to the left of the inequality.

3.2 Linear Programs in Standard Form

The use of the simplex method to solve an LP problem requires that the problem be converted into
standard form.

The standard form 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 of non-negative, if it is not, this should
be done by multiplying both sides of the resulting constraint by -1.

Note:(Minimization and Maximization Problems)

Another problem manipulation is to convert a maximization problem into a minimization problem
and conversely. Note that over any region, M ax(Z) = −M in(−Z). Hence, a maximization (mini-
mization) problem can be converted into a minimization (maximization) problem by multiplying the
coefficients of the objective function by -1. After the optimization of the new problem is completed,
the objective value of the old problem is -1 times the optimal objective value of the new problem.
Let Z 0 = −Z. After the Z 0 value is found, replace Z = −Z 0 .

Consider an LP model,
Max/Min Z = cT X
S.t : Ax(≤, ≥)b
xi ≥ 0
The standard form of the Linear programming problem is expressed as

Optimize(Max or Min)Z = C T X + 0S
Subject to AX ± S = b.

c Dereje T. (MSc.) 30
Linear Optimization March 21, 2023

and X, S ≥ 0.
where C = (c1 , c2 , ..., cn ) is the row vector, X = (x1 , x2 , ..., xn )T
T

b = (b1 , b2 , ..., bm )T and T

 S = (s1 , s2 , ..., sm ) are column
 vectors.
a11 a12 . . . a1n
 a21 a22 . . . a2n 
 
 . . . 
and A =   
 . . . . . . 

 . . . 
am1 am2 . . . amn
is the m × n matrix of coefficients of variables of x1 , x2 , ..., xn in the constraints.
Example 3.1. Transform the following Linear programming problem into standard form of linear pro-
gramming problem

Maximize Z = x1 − x2 + x3
Subject to x1 + x2 − 3x3 ≥ 4
2x1 − 4x2 + x3 ≥ −5
x1 + 2x2 − 2x3 ≤ 3
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

Solution:

Maximize Z = x1 − x2 + x3 + 0x4 + 0x5 + 0x6

Subject to x1 + x2 − 3x3 − x4 = 4
2x1 − 4x2 + x3 − x5 = −5
x1 + 2x2 − 2x3 + x6 = 3
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0

Since the second constraint have a negative value on the right we can multiply both side by (-1) so,

Maximize Z = x1 − x2 + x3 + 0x4 + 0x5 + 0x6

subject to x1 + x2 − 3x3 − x4 = 4
−2x1 + 4x2 − x3 + x5 = 5
x1 + 2x2 − 2x3 + x6 = 3
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0
Therefore, the above problem is standard Linear programming problem.

Variables Unrestricted In Sign

The difference of two non-negative variables is a variable unrestricted in sign. Let x1 and x2 be two non-
negative variables. The difference of these two variables is a variable x3 which is unrestricted in sign. If
x1 > x2 , then x3 > 0, if x1 < x2 , then x3 < 0 and if x1 = x2 , then x3 = 0.

Example 3.2. Write down the following linear programming problem, where the variables are non-negative
in standard LPP form

Maximize Z = 2x1 + 3x2 − x3

Subject to 4x1 + x2 + x3 ≥ 4
7x1 + 4x2 − x3 ≤ 25,
x1 , x3 ≥ 0, x2 unrestricted sign.

c Dereje T. (MSc.) 31
Linear Optimization March 21, 2023

Solution:

Maximize Z = 2x1 + 3x2 − x3

Subject to 4x1 + x2 + x3 − x4 = 4
7x1 + 4x2 − x3 + x5 = 25,
x1 , x3 , x4 , x5 ≥ 0, x2 unrestricted sign.

0 00 0 00
Since x2 is unrestricted sign, we will convert x2 by x2 = x2 − x2 , where x2 , x2 ≥ 0.

0 00
Maximize Z = 2x1 + 3x2 − 3x2 − x3
0 00
Subject to 4x1 + x2 − x2 + x3 − x4 = 4
0 00
7x1 + 4x2 − 4x2 − x3 + x5 = 25,
0 00
x1 , x3 , x4 , x5 , x2 , x2 ≥ 0,

3.3 Basic Feasible Solutions

Definition:(Basic feasible solution)

Consider the system Ax = b and x ≥ 0, where A is an m × n matrix and b is any m vector.
Suppose that the rank(A, b) = rank(A) = m. After possibly rearrangement of the columns of A,
 ] where B is an m × m invertible matrix and N is m × (n − m) matrix. The point
let A= [B, N
XB
X= , where XB = B −1 b and XN = 0 is called a basic solution of the system. If XB ≥ 0,
XN
then X is called a basic feasible solution of the system. Here B is called the basic matrix (or
simply the basis ) and N is called the non basic matrix. The components of XB are called basic
variables, and the components XN are called non basic variables. If XB > 0, then X is called a
non degenerate basic feasible solution and if at least one component of XB is zero, then X is
called a degenerate basic feasible solution.

Example 3.3. Consider the polyhedral set defined by the following inequalities.

(a)
x1 + x2 ≤ 6
x2 ≤ 3
x1 , x2 ≥ 0

(b)
x+y ≤3
2x − y ≤ 4
x, y ≥ 0

Solution: (a) By introducing the slack variables x3 and x4 , the problem is put in the following
standard format:

x1 + x2 + x3 = 6
x2 + x4 = 3

c Dereje T. (MSc.) 32
Linear Optimization March 21, 2023

x1 , x2 , x3 , x4 ≥ 0
 
1 1 1 0
Note that, the constraint matrix A = [a1 a2 a3 a4 ] =
0 1 0 1
From forgoing definition, basic feasible solutions corresponding to finding a 2 × 2 basic matrix B with
non-negative B −1 b. The following are possible ways of extracting B out of A.

 
1 1
1. B = [a1 , a2 ] =
  0 1     
x1 −1 1 −1 6 3
XB = =B b= =
 x2    0 1 3 3
x3 0
XN = =
x4 0
 
1 0
2. B = [a1 , a4 ] =
  0 1     
x1 −1 1 0 6 6
XB = =B b= =
 x4    0 1 3 3
x2 0
XN = =
x3 0
 
1 1
3. B = [a2 , a3 ] =
  1 0     
x2 −1 0 1 6 3
XB = =B b= =
 x3    1 −1 3 3
x1 0
XN = =
x4 0
 
1 0
4. B = [a2 , a4 ] =
  1 1     
x2 −1 1 0 6 6
XB = =B b= =
 x4    −1 1 3 −3
x1 0
XN = =
x3 0
 
1 0
5. B = [a3 , a4 ] =
  0 1     
x3 −1 1 0 6 6
XB = =B b= =
 x4    0 1 3 3
x1 0
XN = =
x2 0

Note that the points corresponding to 1, 2, 3 , 5 are basic feasible solutions. The point obtained in 4
is a basic solution, but not feasible because it violates the non-negativity restriction. In other words,
we have four basic
 feasible
 solutions.
     
3 6 0 0
 3   0   3   0 
Namely X1 =   0  , X2 =  0  , X3 =  3  , X4 =  6 
      

0 3 0 3
These points belong to R4 since after introducing the slack variables, we have four variables. These ba-
sic feasible solutions, projected in R2 that is in the (x1 , x2 ) space give rise to the following four points.

c Dereje T. (MSc.) 33
Linear Optimization March 21, 2023

       
3 6 0 0
, , , these points are precisely the extreme points of the feasible region. In this
3 0 3 0

example, the possible number of basic feasible solutions is bounded by the number of ways of extracting
two columns out of four
 columns to form the basis. therefore, the number of basic feasible solutions is less
4 4!
than or equal to = 2!(4−2)! = 6.
2
Out of these six possibilities, one point violates the non-negativity
  of B −1 b. furthermore, a1 and a3 could
1
not have been used to form a basic since a1 = a3 = are linearly dependent, and hence the matrix
  0
1 1
does not qualify as a basis. This leaves four basic feasible solutions.
0 0
(b)
x+y+z =3
2x − y + w = 4
x, y, z, w ≥ 0
 
  x  
1 1 1 0  y  = 3

2 −1 0 1  z  4
w
4


Here, 2
= 6 possible square matrix obtained from the given system.
If we select column 3 and 4 and assign zero value to the variable associated with column 1and 2,
z = 3,
w = 4. So, (0,0, 3,4) is basic
 solution  andx, yis 
non-basic variable and z and w is basic variable.
1 0 z 3 x 0
B= . XB = = and XN = =
0 1 w 4 y 0
Again take column
 1 and 2 and assign zero value to the variable associated with column 3 and 4,
1 1
B= and XB = B −1 b and follow the same fashion as above.
2 −1
 
n n!
In general, the number of basic feasible solutions is less than or equal to = m!(n−m)!
m

Example 3.4. ( Degenerate basic feasible solutions)

Consider the following system of inequalities

x1 + x2 ≤ 6
x2 ≤ 3
x1 + 2x2 ≤ 9
x1 , x2 ≥ 0

c Dereje T. (MSc.) 34
Linear Optimization March 21, 2023

Solution: After adding the slack variables x3 , x4 and x5 , we get

x1 + x2 + x3 = 6
x2 + x4 = 3
x1 + 2x2 + x5 = 9
x1 , x2 , x3 , x4 , x5 ≥ 0
 
1 1 1 0 0
A = [a1 , a2 , a3 , a4 , a5 ] =  0 1 0 1 0 
1 2 0 0 1
Let us consider the basic feasible solution for B = [a1 , a2 , a3 ]
   −1       
x1 1 1 1 6 0 −2 1 6 3
X B =  x2  =  0 1 0   3  =  0 1 0  3  =  3 
 x3   1  2 0 9 1 1 −1 9 0
x4 0
XN = =
x5 0

Note that this basic feasible solution is degenerate since the basic variable x3 = 0. Now consider the
basic feasible solution with B = [a1 , a2 , a4 ]
   −1       
x1 1 1 0 6 2 0 −1 6 3
XB =  x2  =  0 1 1   3  =  −1 0 1   3  =  3 
 x4   1  2 0 9 1 1 −1 9 0
x3 0
XN = =
x5 0
Note that these basic feasible solution give rise to the same point obtained by B = [a1 , a2 , a3 ]. Itcan
x1
be also checked the other basic feasible solution with basis B = [a1 , a2 , a5 ] is give by XB =  x2  =
  x5
3    
 3  , XN = x3 = 0
x4 0
0
Note that all the three foregoing bases represent the single extreme point or basic feasible solution
(x1 , x2 , x3 , x4 , x5 ) = (3, 3, 0, 0, 0). This basic feasible solution is degenerate since each associated basis
involves a basic variable at level zero.

3.4 Fundamental Theorem of Linear Programming

Theorem: For an arbitrary linear programming in standard form of the following are true.

i . If there is no optimal solution, then the problem is either infeasible or unbounded

ii . If a feasible solution exists, then a basic feasible solution exists
iii . If an optimal solution exists, then a basic optimal solution exists

Now, since the extreme 

points
 may be enumerated by algebraically enumerating all basic feasible solutions,
n
which are bounded by , one may think of simply listing all basic feasible solutions and picking the
m
one having the minimal objective value. This is unsatisfactory, however, for a number of reasons.

c Dereje T. (MSc.) 35
Linear Optimization March 21, 2023

 
n
• First, the number of basic feasible solutions is bounded by , which is large, even for moderate
m
values of m and n.

• Second, this simple approach does not tell us if the problem has an unbounded optimal value, which
may occur if the feasible region is unbounded.

• Last, if the feasible region is empty and if we apply the foregoing ”simple-minded procedure,” we
shall discover that the feasible region is empty, only after all possible ways of extracting m columns
out of n columns of the matrix A fail to produce a basic feasible solution, either on the grounds that
B does not have an inverse, or else that B −1 b  0.

The simplex method is a clever procedure that moves from one extreme point to another extreme
point having a better (at least not worse) objective value. It also discovers whether the feasible region is
empty and whether the optimal objective value is unbounded. In practice, the method only enumerates a
small portion of the extreme points of the feasible region. The key to this method is revealed next.

Key to the Simplex Method

The key to the simplex method lies in recognizing the optimality of a given extreme point solution based on
local considerations without having to (globally) enumerate all extreme points or basic feasible solutions.
Consider the following linear programming problem :

LP: Minimize C T X
Subject to AX = b
X≥0

B −1 b
 
where A is an m × n matrix with rank m, suppose that we have a basic feasible solution whose
0
objective value Z0 is given by
 −1   −1 
B b B b
Z0 = C T T T
= (CB , CN ) = CBT B −1 b (3.1)
0 0
 
XB
Now, let XB and XN denote the set of basic and non basic variables for the given basis and X =
XN
be an arbitrary feasible solution. Then feasibility requires that XB ≥ 0, XN ≥ 0 and that b = AX =
BXB + N XN . Multiplying by B −1 and rearranging the terms, we get

B −1 (b = BXB + N XN )
B −1 b = XB + B −1 N XN
XB = B −1 b − B −1 N XN
X
XB = B −1 b − B −1 aj xj
j∈J
X
XB = B −1 b − y j xj
j∈J

c Dereje T. (MSc.) 36
Linear Optimization March 21, 2023

X
XB = b− yj xj (3.2)
j∈J

Where b = B −1 b, yj = B −1 aj and J is the current set of the indices of the non basic variables. Noting
equation (3.1) and (3.2) and letting Z denote the objective function value. we get

Z = CT X
 
XB
= (CBT , CNT )
XN
= CBT XB + CNT XN
X X
= CBT (B −1 b − B −1 aj xj ) + cj x j
j∈J j∈J

X X
= CBT (B −1 b) − CBT B −1 aj xj + cj x j
j∈J j∈J
X X
= Z0 − zj xj + cj x j
j∈J j∈J
X
= Z0 − (zj − cj )xj
j∈J

(3.3)
Where zj = CB B −1 aj for each non basic variable
Using the foregoing transformation, the linear programming problem may be written as
X
Minimize Z = Z0 − (zj − cj )xj
j∈J

X
subject to yj xj + XB = B −1 b
j∈J

xj ≥ 0, j ∈ J, and XB ≥ 0 (3.4)

3.5 Algebra of the Simplex Method

we will now translate the geometric process in to algebra. Consider the representation of the linear
programming LP in the non basic variable space written in equality form as in equation (3.4).
If (zj − cj ) ≤ 0 for j ∈ J, then xj = 0 for j ∈ J and XB = B −1 b is optimal for the LP. otherwise, while
holding (p-1) non basic variable fixed at zero, the simplex method considers increasing the remaining
variables, say xk . Naturally we would like zk − ck to be positive and perhaps the most positive of all the
zj − cj , j ∈ J. Now fixing xj = 0 for j ∈ J − {k} we obtain from equation (3.4)that

z = z0 − (zk − ck )xk (3.5)

c Dereje T. (MSc.) 37
Linear Optimization March 21, 2023

     
xB1 b1 y1k
 xB2   b2   y2k 
     
 .   .   . 
     
 .   .   . 
     
 .   .   . 
and   xBr  =  br  −  yrk  xk (3.6)
    
     
 .   .   . 
     
 .   .   . 
     
 .   .   . 
xBm bm ymk
If yik ≤ 0, then xBi increases as xk increase and so xBi continues to be non-negative. If yik ≥ 0 then
xBi will decrease as xk increases. In order to satisfy non-negativity, xk is increase until the first point
at which some basic variable xBr drops to zero. Examining equation (3.6), it is then clear that the first
basic variable dropping to zero corresponds to the minimum of ybiki for positive yik . more precisely, we can
increase xk until
xk = ybrkr = minimum1≤i≤m { ybiki : yik > 0} (3.7)
In the absence of degeneracy, br > 0 and hence xk = ybrkr > 0, from equation (3.5) and the fact that
zk − ck > 0, it then follows z < z0 and the objective function strictly improves. As xk increases from level
0 to ybrkr , a new feasible solution obtained. Substituting xk = ybrkr in equation (3.6) gives the following point:

yik
xBi = bi − b ,i
yrk r
= 1, 2, ..., m
br
xk = yrk
(3.8)

and all other xj - variables are zero.

From equation (3.8), xBr = 0 and hence, at most m variables are positive. The corresponding columns in
A are aB1 , aB2 , ..., aBr−1 , ak , aBr+1 , ..., aBm . Note that these columns are linearly independent. since yrk 6= 0.
(Recall that if aB1 , aB1 , ..., aBm are linearly independent, and if ak replaces aBr , then the new columns are
linearly independent if and only if yrk 6= 0.
Therefore, the point given by equation (3.8) is a basic feasible solution.

Recall that a basic variable xB that first drops to zero is called a blocking variable because it
blocks the further increase of xk . Thus, xk enters the basis and xB leaves the basis.

To summarize, we have algebraically described an iteration, that is, the process of transforming from
one basis to an adjacent basis. This is done by increasing the value of a nonbasic variable xk with positive
zk −ck and adjusting the current basic variables. In the process, the variable xB drops to zero. The variable
xk hence enters the basis and xB leaves the basis. In the absence of degeneracy the objective function
value strictly decreases, and hence the basic feasible solutions generated are distinct. Because there exists
only a finite number of basic feasible solutions, the procedure would terminate in a finite number of steps.
Example:

Minimize x1 + x2
subject to x1 + 2x2 ≤ 4
x2 ≤ 1
x1 , x2 ≥ 0

Introducing the slack variables x3 and x4 to put the problem in a standard form.
This leads to the following constraint matrix A :

c Dereje T. (MSc.) 38
Linear Optimization March 21, 2023

 
1 2 1 0
A = [a1 , a2 , a3 , a4 ] =
0 1 0 1
Consider the basic feasible solution corresponding to B = [a1 , a2 ]. In other words, x1 and x2 are the basic
variables, while x3 and x4 are the nonbasic variables. The representation of the problem in this nonbasic
variable space as in Equation (3.4) with J= 3, 4 may be obtained as follows. First, compute:
 −1    
−1 1 2 1 −2 −1 1 −2
B = = , CB B = (1, 1) = (1, −1)
0 1  0 1     1 1
1 −2 1 1
Hence y3 = B −1 a3 = =
 0 1
   0  0
1 −2 0 −2
y4 = B −1 a4 = =
0 1 1   1  
1 −2 4 2
and XB = b = B −1 b = =
0  1  1 1
4
Also, z0 = CB B −1 b = (1, −1) =3
1  
1
z3 − c3 = CB B −1 a3 − c3 = (1, −1) −0=1
 0
−1 0
z4 − c4 = CB B a4 − c4 = (1, −1) − 0 = −1
1
Hence, the required representation of the problem is

Minimize 3 − x3 + x4
subject to x3 − 2x4 + x1 = 2
x4 + x2 = 1
x1 , x2 , x3 , x4 ≥ 0

Since z3 − c3 > 0, then the objective function improves by increasing x3 , the modified solution is given by
X
B = B −1 b− B−1 a3 x3 
x1 2 1
= − x3
x2 1 0
The maximum value of x3 is 2 (any larger value of x3 will force x1 to be negative). Therefore the new
basic feasible solution is
(x1 , x2 , x3 , x4 ) = (0, 1, 2, 0)
Here, x3 enters the basis and x1 leaves the basis. Note that the new point has an objective value equal to 1,
which is an improvement over the previous objective value of 3. the improvement is precisely (z3 −c3 )x3 = 2.
Remark: CB is the coefficient of the basic variable in the objective of the linear programming
Termination with an optimal solution
Consider the following problem, where A is an m × n matrix with rank m.

Minimize C T X
Subject to AX = b
X≥0

B −1 b
 
∗ ∗
Suppose that X is a basic feasible solution with basis B; that is X =
0
∗ ∗ ∗ T −1
Let Z denote the objective value at X , that is Z = CB B b. Suppose further that Zj − Cj ≤ 0, for all
non basic variables, and hence there are no non basic variables that are eligible to enter the basis. let x
be any feasible solution with objective function value z, then from equation (3.3) we have

c Dereje T. (MSc.) 39
Linear Optimization March 21, 2023

Z∗ − Z =
P
j∈J (Zj − Cj )xj (3.9)

Because Zj − Cj ≤ 0 and Xj ≥ 0 for all variables, then Z ∗ ≤ Z, and so X ∗ is an optimal basic feasible
solution, since if (Zj − Cj ) ≤ 0 for all j ∈ J, then the current basic feasible solution is optimal.
Example:

Minimize 2x1 − x2
subject to −x1 + x2 ≤ 2
2x1 + x2 ≤ 6
x1 , x2 ≥ 0

Introducing the slack variables x3 and x4 . This leads to the following constraints

−x1 + x2 + x3 = 2
2x1 + x2 + x4 = 6
x1 , x2 , x3 , x4 ≥ 0
   
−1 1 −1 −1/3 1/3
Consider the basic feasible solution with basis B = [a1 , a2 ] = andB =
2 1 2/3 1/3
−1 −1
XB = B b 
 −B  N XN      
xB1 x1 −1/3 1/3 2 −1/3 1/3 1 0 x3
= = −
xB2
  x2  2/3 1/3  6 2/3 1/3 0 1 x4
4/3 −1/3 1/3
= − x3 − x4 (3.10)
10/3 2/3 1/3
−1
Currently,
 x3 = x4 = 0, x1 = 4/3 and x2 = 10/3, note that  z3 − c3 = CB B a3 − c3 =
−1/3 1/3 1
1
(2, −1) − 0 = −4/3 0 − 0 = −4/3
2/3 1/3 0  0 
−1/3 1/3 0
z4 − c4 = CB B −1 a4 − c4 = (2, −1) − 0 = 1/3
2/3 1/3 1
Hence, the objective improves by holding x3 non- basic and introducing x4 in the basis. Then x3 is kept at
zero level, x4 is increased and x1 and x2 are modified according to equation (3.10). we see that x4 can be
increased to 4, at which x1 drops to zero. Any further increase of x4 results in violating the non-negativity
of x1 and so x1 is the blocking variable. With x4 = 4 and x3 = 0, the modified value of x1 and x2 are 0
and 2 respectively. The new basic feasible solution is

(x1 , x2 , x3 , x4 ) = (0, 2, 0, 4)

Note that a4 replaces a1 , that is x1 drop from the basic and x4 enters the basis. The new set of basic and
non basic
 variables
 and their values  are given
 as :  
xB4 x4 4 x3 0
XB = = = , XN = =
xB2 x1 2 x1 0
Moving from old to the new basic feasible solution is illustrated in figure given below, note that as x4
increases by one unit x1 decrease by 1/3 unit and x2 decrease by 1/3 unit, that is we move in the direction
(-1/3, -1/3) in the (x1 , x2 ) space. This continues until we are blocked by the non negativity restriction
x1 ≥ 0. At this point x1 drops to zero and leaves the basis.

3.6 The simplex Algorithm

The key solution concepts

c Dereje T. (MSc.) 40
Linear Optimization March 21, 2023

• Solution concept 1: The simplex method focuses on corner point feasible(CPF) solutions.

• Solution concept 2: The simplex method is an iterative algorithm(a systematic solution procedure
that keeps repeating a fixed series of steps, called an iteration, until a desired result has been obtained
) with the following structure.

• Solution concept 3 : Whenever possible, the initialization of the simplex method chooses the
origin point(all decision variables equal to zero) to be the initial CPF solution

• Solution concept 4: Given a CPF solution, it is much quicker computationally to gather infor-
mation about its adjacent CPF solutions than about other CPF solutions. Therefore, each time the
simplex method performs an iteration to move from the current CPF solution to a better one, it
always chooses a CPF solution that is adjacent to the current one.

• Solution Concept 5: After the current CPF solution is identified, the simplex method examines
each of the edges of the feasible region that emanates from this CPF solution. Each of these edges

c Dereje T. (MSc.) 41
Linear Optimization March 21, 2023

leads to an adjacent solution at the other end, but the simplex method doesn’t even take the time
to solve for adjacent CPF solutions, instead, it simply identifies the rate of improvement in Z that
would be obtained by moving along the edge. and then chooses to move along the one with largest
positive rate of improvement.

• Solution concept 6: A positive rate of improvement in Z implies that the adjacent CPF solution is
better than the current one, whereas a negative rate of improvement in Z implies that the adjacent
CPF solution is worse. Therefore, the optimality test consists simply checking whether any of the
edges give a positive rate of improvement in Z. if none do, then the current CPF solution is optimal.

The Simplex Method in Tabular Form

Steps

1. Initialization:

(a) Convert (Transform) all the constraints to equality by introducing slack, surplus, and artificial
variables as follows
Constraint type Variable to be added
≤ +slack(s)
≥ -surplus(s)+artificial(A)
= + artificial(A)

The artificial variable refers to the kind of variable which is introduced in the linear program
model to obtain the initial basic feasible solution. It is utilized for the equality constraints and
for the greater than or equal inequality constraints.
(b) Construct the initial simplex tableau
Basic variable X1 . . . Xn S1 ... Sn A1 ... An RHS
S b1
. .
. .
. .
A bm
Z Z value
2. Test for optimality :
Case 1: In maximization problem the current basic feasible solution is optimal if every element in
the last row of the simplex tableau is nonnegative
Case 2 : In minimization problem the current basic feasible solution is optimal if every element in
the last row of the simplex tableau is non positive

3. Iteration :
Step 1 : Determine the entering basic variable by selecting the variable (automatically a non basic
variable ) with the most negative value (in case of maximization)or the most positive(in case of
minimization) in the last row (Z-row). Put a box around the column below this variable, and call it
the ” pivot column”.
Step 2 : Determine the leaving basic variable by applying the minimum ratio test as following:

(a) Pick out each coefficients in the pivot column that is strictly positive
(b) Divide each of these coefficients into the right hand side entry for the same row

c Dereje T. (MSc.) 42
Linear Optimization March 21, 2023

(c) Identify the row that has the smallest of these ratios
(d) The basic variable for that row is the leaving variable, so replace that variable by the entering
variable in the basic variable column of the next simplex tableau. Put a box around this row
and call it the ”pivot row”.
Step 3: Solve for the new basic feasible solution by using elementary row operation(multiply
or divide a row by a nonzero constant, add or subtract a multiple of one row another row)to
construct a new simplex tableau, and then return the optimality test.

Example: Solve the following problem using the simplex method

Maximize z = 3x1 + 5x2

Subject to x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
x1 , x2 ≥ 0

Solution: 1. Write the standard form of the above linear programming problem.

Maximize z = 3x1 + 5x2

Subject to x1 + s1 = 4
2x2 + s2 = 12
3x1 + 2x2 + s3 = 18
x1 , x2 , s1 , s2 , s3 ≥ 0

2. Initial tableau

C 3 5 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS)
0 s1 1 0 1 0 0 4
0 s2 0 2 0 1 0 12
0 s3 3 2 0 0 1 18
Zj − Cj -3 -5 0 0 0

The basic feasible solution at the initial tableau is (0,0,4,12,18) where: x1 = 0, x2 = 0, s1 = 4, s2 =

12, s3 = 18 and z = 0. Where s1 , s2 , s3 are basic variable and x1 and x2 are non-basic variables. The
solution at the initial tableau is associated to the origin point at which all the decision variables are zero.
Optimality test: By investigating the last row of the initial tableau, we find that there are some negative
numbers. Therefore, the current solution is not optimal.
Iteration
Step 1: Determine the entering variable by selecting the variable with the most negative in the last row.
From the initial tableau, in the last row ((Zj − Cj ) row), the coefficient of X1 is -3 and the coefficient of
X2 is -5; therefore, the most negative is -5. consequently, X2 is the entering variable. X2 is surrounded by
a box and it is called the pivot column.
Step 2: Determining the leaving variable by using the minimum ratio test as follows:

c Dereje T. (MSc.) 43
Linear Optimization March 21, 2023

Figure 3.1: Flow Chart for the Simplex Algorithm

C 3 5 0 0 0
CB XB x1 x2 (Entering) s1 s2 s3 b(RHS)
0 s1 1 0 1 0 0 4
0 s2 (Leaving) 0 2 0 1 0 12
0 s3 3 2 0 0 1 18
Zj − Cj -3 -5 0 0 0
c Dereje T. (MSc.) 44
Linear Optimization March 21, 2023

Step 3: solving for the new BF solution by using the eliminatory row operations as follows:

C 3 5 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS)
0 s1 1 0 1 0 0 4
5 x2 0 1 0 1/2 0 6
0 s3 3 0 0 -1 1 6
Zj − Cj -3 0 0 5/2 0

This solution is not optimal, since there is a negative numbers in the last row.

Apply the same rules we will obtain this solution:

C 3 5 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS)
0 s1 0 0 1 1/3 -1/3 2
5 x2 0 1 0 1/2 0 6
3 x1 1 0 0 -1/3 1/3 2
Z j − Cj 0 0 0 3/2 1 36

This solution is optimal; since there is no negative solution in the last row: basic variables are x1 = 2, x2 = 6
and s1 = 2; the nonbasic variables are s2 = s3 = 0, and the optimal value Z = 36.

Example :

Minimize x1 + x2 − 4x3
subject to x1 + x2 + 2x3 ≤ 9
x1 + x2 − x3 ≤ 2
−x1 + x2 + x3 ≤ 4
x1 , x2 , x3 ≥ 0

Solution : Introducing the non- negative slack variables s1 , s2 and s3 . The problem becomes the following
:

Minimize x1 + x2 − 4x3
subject to x1 + x2 + 2x3 + s1 = 9
x1 + x2 − x3 + s 2 = 2
−x1 + x2 + x3 + s3 = 4
x1 , x2 , x3 , s1 , s2 , s3 ≥ 0

Since b ≥ 0, then we can choose our initial basis as B = [a4 , a5 , a6 ] = I3 , and we indeed have B −1 b = b ≥ 0.
This gives the following initial tableau:
Iteration 1

c Dereje T. (MSc.) 45
Linear Optimization March 21, 2023

C 1 1 -4 0 0 0 0
CB XB x1 x2 x3 s1 s2 s3 b(RHS)
0 s1 1 1 2 1 0 0 9
0 s2 1 1 -1 0 1 0 2
0 s3 -1 1 1 0 0 1 4
Zj − Cj -1 -1 4 0 0 0

The initial basic feasible solution in the above table is x1 = 0, x2 = 0, x3 = 0, but it is not optimal, since
there is positive element the last row of the simplex table (Zj − Cj ).

Identify the entering and leaving variable

Iteration 2

C 1 1 -4 0 0 0 0
CB XB x1 x2 x3 s1 s2 s3 b(RHS)
0 s1 1 1 2 1 0 0 9
0 s2 1 1 -1 0 1 0 2
0 s3 -1 1 1 0 0 1 4
Zj − Cj -1 -1 4 0 0 0

From the above simplex table s3 is the leaving variable and x3 is the entering variable.

C 1 1 -4 0 0 0 0
CB XB x1 x2 x3 s1 s2 s3 b(RHS)
0 s1 3 -1 0 1 0 -2 1
0 s2 0 2 0 0 1 1 6
-4 x3 -1 1 1 0 0 1 4
Zj − Cj 3 -5 0 0 0 -4

The initial basic feasible solution in the above table is x1 = 0, x2 = 0, x3 = 4, but it is not optimal, since
there is positive element in the last row of the simplex table (Zj − Cj ).
Iteration 3

C 1 1 -4 0 0 0 0
CB XB x1 x2 x3 s1 s2 s3 b(RHS)
0 s1 3 -1 0 1 0 -2 1
0 s2 0 2 0 0 1 1 6
-4 x3 -1 1 1 0 0 1 4
Zj − Cj 3 -5 0 0 0 -4

From the above simplex table s1 is the leaving variable and x1 is the entering variable.

c Dereje T. (MSc.) 46
Linear Optimization March 21, 2023

C 1 1 -4 0 0 0
CB XB x1 x2 x3 s1 s2 s3 b(RHS)
1 x1 1 -1/3 0 1/3 0 -2/3 1/3
0 s2 0 2 0 0 1 1 6
-4 x3 0 2/3 1 1/3 0 1/3 13/3
Zj − C j 0 -4 0 -1 0 -2

This is an optimal tableau since Zj − Cj ≤ 0 in the last row. The optimal solution is given by x1 =
1/3, x2 = 0, x3 = 13/3, with z = -17.

3.7 Degeneracy and Finiteness of Simplex Algorithm

Degeneracy: 1. only one component of basic feasible solution corresponding to the basic variable is zero.
2. at least two component of basic feasible solution corresponding to the basic variables are zero.
Example:

Maximize 5x1 + 3x2

Subject to x1 + x2 ≤ 2
5x1 + 2x2 ≤ 10
x1 + 8x2 ≤ 12
x1 , x2 ≥ 0

Solution :The standard linear programming problem for the above problem is

Maximize 5x1 + 3x2

Subject to x1 + x2 + s1 = 2
5x1 + 2x2 + s2 = 10
x1 + 8x2 + s3 = 12
x1 , x2 , s1 , s2 , s3 ≥ 0

Now we can construct the simplex tableau

C 5 3 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS)
0 s1 1 1 1 0 0 2
0 s2 5 2 0 1 0 10
0 s3 3 8 0 0 1 12
Zj − Cj -5 -3 0 0 0

The initial basic feasible solution of the LP problem is x1 = 0, x2 = 0, but it can not be an optimal
solution, since there is a negative element in the last row of the simplex table. from the above table we can
identify the entering and leaving variables, thus x1 is the entering variable and s1 is the leaving variable.

c Dereje T. (MSc.) 47
Linear Optimization March 21, 2023

C 5 3 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS)
5 x1 1 1 1 0 0 2
0 s2 5 2 0 1 0 10
0 s3 3 8 0 0 1 12
Zj − Cj -5 -3 0 0 0

By applying elementary row operation we can get the following simplex tableau

C 5 3 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS)
5 x1 1 1 1 0 0 2
0 s2 0 -3 -5 1 0 0
0 s3 0 5 -3 0 1 6
Zj − Cj 0 2 5 0 0

Thus the optimal solution is (x1 , x2 , s1 , s2 , s3 ) = (2, 0, 0, 0, 6) and the optimal value is 10, since there exist
a zero value of basic variable ,it is degenerate case of finiteness of simplex algorithm.
Infinite number of solutions
The alternative optimal solution can be obtained by considering the zj − cj row of the simplex table. That
is, zj − cj = 0 for some non-basic variable columns in the optimal simplex table.
Example

Maximize 10x1 + 20x2

subject to x1 ≤ 10
x2 ≤ 6
2x1 + 4x2 ≤ 36
x1 , x2 ≥ 0

Solution: The standard linear programming problem of the above problem is

Maximize 10x1 + 20x2

subject to x1 + s1 = 10
x2 + s 2 = 6
2x1 + 4x2 + s3 = 36
x1 , x2 , s1 , s2 , s3 ≥ 0

Now construct the simplex tableau

C 10 20 0 0 0
CB XB x1 x2 s 1 s2 s3 b(RHS)
0 s1 1 0 1 0 0 10
0 s2 0 1 0 1 0 6
0 s3 2 4 0 0 1 36
Z j − Cj -10 -20 0 0 0

c Dereje T. (MSc.) 48
Linear Optimization March 21, 2023

C 10 20 0 0 0
CB XB x 1 x2 s1 s2 s3 b(RHS)
0 s1 1 0 1 0 0 10
20 x2 0 1 0 1 0 6
0 s3 2 0 0 -4 1 12
Zj − Cj -10 0 0 20 0

C 10 20 0 0 0
CB XB x 1 x2 s1 s2 s3 b(RHS)
0 s1 1 0 1 0 0 10
20 x2 0 1 0 1 0 6
0 s3 2 0 0 -4 1 12
Zj − Cj -10 0 0 20 0

C 10 20 0 0 0
CB XB x1 x2 s 1 s2 s3 b(RHS)
0 s1 0 0 1 2 -1/2 4
20 x2 0 1 0 1 0 6
10 x1 1 0 0 -2 1/2 6
Zj − Cj 0 0 0 0 5 180

We have basic feasible solution (x1 , x2 ) = (6, 6) with optimal value z = 180. We apply a new simplex
step with Zj − Cj = 0 for a non- basic variable.

C 10 20 0 0 0
CB XB x1 x2 s 1 s2 s3 b(RHS)
0 s1 0 0 1 2 -1/2 4
20 x2 0 1 0 1 0 6
10 x1 1 0 0 -2 1/2 6
Zj − Cj 0 0 0 0 5 180

C 10 20 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS)
0 s2 0 0 1/2 1 -1/4 2
20 x2 0 1 -1/2 0 1/4 4
10 x1 1 0 1 0 0 10
Zj − Cj 0 0 0 0 5 180

Now we have another basic solution (x1 , x2 ) = (10, 4), but the optimal values remains 180.
In our case, since (x1 , x2 ) = (6, 6) and (x1 , x2 ) = (10, 4) are solutions all points of the segment
(x1 , x2 )(x1 , x2 ) = λ(6, 6) + (1 − λ)(10, 4), λ ∈ [0, 1] are solutions.

3.8 Finding a Starting Basic Feasible Solution

In certain cases, it is difficult to obtain an initial basic feasible solution of the given LP problem. Such
cases arise

c Dereje T. (MSc.) 49
Linear Optimization March 21, 2023

1. when the constraints are of the ≤ type,

n
X
aij xj ≤ bi , xj ≥ 0
j=1

and value of few right-hand side constants is negative [i.e. bi < 0]. After adding the non-negative
slack variable si (i = 1, 2, . . ., m), the initial solution so obtained will be si = −bi for a particular
resource, i. This solution is not feasible because it does not satisfy non-negativity conditions of slack
variables (i.e. si ≥ 0).

2. when the constraints are of the ≥ type,

n
X
aij xj ≥ bi , xj ≥ 0
j=1

After adding surplus (negative slack) variable si , the initial solution so obtained will be −si = bi or si = −bi
n
X
aij xj − si = bi , xj ≥ 0, si ≥ 0
j=1

This solution is not feasible because it does not satisfy non-negativity conditions of surplus variables (i.e.
si ≥ 0). In such a case, artificial variables, Ai (i = 1, 2, . . ., m) are added to get an initial basic feasible
solution. The resulting system of equations then becomes:
n
X
aij xj − si + Ai = bi
j=1

xj , si , Ai ≥ 0, i = 1, 2, ..., m
These are m simultaneous equations with (n + m + m) variables (n decision variables, m artificial variables
and m surplus variables). An initial basic feasible solution of LP problem with such constraints can be
obtained by equating (n + 2m – m) = (n + m) variables equal to zero. Thus the new solution to the
given LP problem is: Ai = bi (i = 1, 2, . . . , m), which is not the solution to the original system
of equations because the two systems of equations are not equivalent. Thus, to get back to the original
problem, artificial variables must be removed from the optimal solution. There are two methods for
removing artificial variables from the solution.

• Two-Phase Method

• Big-M Method or Method of Penalties

Remark Artificial variables have no meaning in a physical sense and are only used as a tool for
generating an initial solution to an LP problem. Before the optimal solution is reached, all artificial
variables must be dropped out from the solution mix. This is done by assigning appropriate coef-
ficients to these variables in the objective function. These variables are added to those constraints
with equality (=) and greater than or equal to (≥) sign.

c Dereje T. (MSc.) 50
Linear Optimization March 21, 2023

3.8.1 Two -phase method

In the first phase of this method, the sum of the artificial variables is minimized subject to the given
constraints in order to get a basic feasible solution of the LP problem. The second phase minimizes
the original objective function starting with the basic feasible solution obtained at the end of the first
[Link] the solution of the LP problem is completed in two phases, this method is called the two-
phase method.
Advantages of the method

• No assumptions on the original system of constraints are made, i.e. the system may be redundant,
inconsistent or not solvable in non-negative numbers.
• It is easy to obtain an initial basic feasible solution for Phase I.
• The basic feasible solution (if it exists) obtained at the end of phase I is used as initial solution for
Phase II

Steps of the Algorithm: Phase I

Step 1 If all the constraints in the given LP problem are ‘less than or equal to’ (≤) type, then Phase
II can be directly used to solve the problem. Otherwise, the necessary number of surplus and artificial
variables are added to convert constraints into equality constraints.
Step 2: Assign zero coefficient to each of the decision variables (xj ) and to the surplus variables; and
assign - 1 coefficient to each of the artificial variables. This yields the following auxiliary LP problem.

Pm
Maximize Z ∗ = i=1 (−1)Ai

subject to the constraints

m
X
aij xj + Ai = bi , i = 1, 2, ..., m
i=1

and xj , Aj ≥ 0
Step 3: Apply the simplex algorithm to solve this auxiliary LP problem. The following three cases may
arise at optimality.

(i) Max Z ∗ < 0 and at least one artificial variable is present in the basis with positive value. This means
that no feasible solution exists for the original LP problem.
(ii) Max Z ∗ = 0 and no artificial variable is present in the basis. This means that only decision
variables(xj ’s) are present in the basis and hence proceed to Phase II to obtain an optimal basic
feasible solution on the original LP problem.
(iii) Max Z ∗ = 0 and at least one artificial variable is present in the basis at zero value. This means that
a feasible solution to the auxiliary LP problem is also a feasible solution to the original LP problem.
In order to arrive at the basic feasible solution, proceed directly to Phase II or else eliminate the
artificial basic variable and then proceed to Phase II.

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

c Dereje T. (MSc.) 51
Linear Optimization March 21, 2023

Phase II: Assign actual coefficients to the variables in the objective function and zero coefficient to the
artificial variables which appear at zero value in the basis at the end of Phase I. The last simplex table of
Phase I can be used as the initial simplex table for Phase II. Then apply the usual simplex algorithm to
the modified simplex table in order to get the optimal solution to the original problem. Artificial variables
that do not appear in the basis may be removed.

Remark

1. All artificial vectors are not present in the bases which indicates that all artificial vectors at
zero level at the optimal stage, thus the solution obtained is a basic feasible solution.

2. Some artificial vectors are present in the basis and some artificial vectors are at positive level
at the optimal stage. In that case there are no feasible solution to the problem.

3. All artificial are at zero level but at least one artificial vector is present in the basis at optimal
stage. Here the solution under test is an optimal solution. Here the converted equations are
consistent but some of the constraints may be redundant. By redundancy means the system
has more than enough constraints.

Example. Solve the following Linear programming problems by using two phase method

Maximize Z = 3x1 − x2
subject to 2x1 + x2 ≥ 2
x1 + 3x2 ≤ 2
x2 ≤ 4
x1 , x2 ≥ 0

Solution:Phase I

Convert the above problem to Standard form of LPP

Maximize Z = 3x1 − x2 /Z∗ = −A1

subject to 2x1 + x2 − s1 + A1 = 2
x1 + 3x2 + s2 = 2
x2 + s 3 = 4
x1 , x2 , s1 , s2 , s3 , A1 ≥ 0

Now, we will Max Z ∗ = −A1 till zero in order to remove the variable A1 , where A1 is an artificial variable.

Maximize Z ∗ = 0x1 − 0x2 + 0s1 + 0s2 + 0s3 − 1A1

subject to 2x1 + x2 − s1 + A1 = 2
x1 + 3x2 + s2 = 2
x2 + s 3 = 4
x1 , x2 , s1 , s2 , s3 , A1 ≥ 0

c Dereje T. (MSc.) 52
Linear Optimization March 21, 2023

Cj 0 0 0 0 0 -1
CB XB x1 x2 s1 s2 s3 A1 b(RHS) Min ratio bi /yik
-1 A1 2 1 -1 0 0 1 2 1←
0 s2 1 3 0 1 0 0 2 2
0 s3 0 1 0 0 1 0 4 -
Z j − Cj ↑-2 -1 1 0 0 0 Z ∗ = −2

Cj 0 0 0 0 0 -1
CB XB x1 x2 s1 s2 s3 A1 b(RHS)
0 x1 1 1/2 -1/2 0 0 × 1
0 s2 0 5/2 1/2 1 0 × 1
0 s3 0 1 0 0 1 × 4
∗
Zj − Cj 0 0 0 0 0 × Z =0

Since all Zj − Cj = 0 and no artificial vector appears in the the basis, we proceed to phase II.
Phase II

Cj 3 -1 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS)
3 x1 1 1/2 -1/2 0 0 1
0 s2 0 5/2 1/2 1 0 1←
0 s3 0 1 0 0 1 4
Zj − Cj 0 5/2 ↑ -3/2 0 0 Z=3

Cj 3 -1 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS)
3 x1 1 3 0 1 0 2
0 s1 0 5 1 2 0 2
0 s3 0 1 0 0 1 4
Z j − Cj 0 10 0 3 0 Z=6

Since all Zj − Cj ≥ 0, optimal basic feasible solution is obtained, therefore the solution is Max
Z = 6, x1 = 2, x2 = 0.
Example

Maximize Z = 5x1 + 8x2

subject to 3x1 + 2x2 ≥ 3
x1 + 4x2 ≥ 4
x1 + x2 ≤ 5
x1 , x2 ≥ 0

Solution: The standard linear programming problem

Maximize Z = 5x1 + 8x2

subject to 3x1 + 2x2 − s1 + A1 = 3
x1 + 4x2 − s2 + A2 = 4
x 1 + x2 + s 3 = 5
x1 , x2 , s1 , s2 , s3 , A1 , A2 ≥ 0

c Dereje T. (MSc.) 53
Linear Optimization March 21, 2023

Auxiliary LPP

Maximize Z = 0x1 + 0x2 + 0s1 + 0s2 + 0s3 − A1 − A2

subject to 3x1 + 2x2 − s1 + A1 = 3
x1 + 4x2 − s2 + A2 = 4
x1 + x2 + s 3 = 5
x1 , x2 , s1 , s2 , s3 , A1 , A2 ≥ 0

Phase I

Cj 0 0 0 0 0 -1 -1
CB XB x1 x2 s1 s2 s3 A1 A2 b(RHS) min ratio bi /yik
-1 A1 3 2 -1 0 0 1 0 3 3/2
-1 A2 1 4 0 -1 0 0 1 4 1→
0 s3 1 1 0 0 1 0 0 5 5
∗
Zj − Cj -4 ↑ −6 1 1 0 0 0 Z = −7

Cj 0 0 0 0 0 -1 -1
CB XB x1 x2 s1 s2 s3 A1 A2 b(RHS) min ratio bi /yik
-1 A1 5/2 0 -1 1/2 0 1 × 1 2/5 →
0 x2 1/4 1 0 -1/4 0 0 × 1 4
0 s3 3/4 0 0 1/4 1 0 × 4 16/3
∗
Zj − Cj ↑ −5/2 0 1 -1/2 0 0 × Z = −1

Cj 0 0 0 0 0 -1 -1
CB XB x1 x2 s1 s2 s3 A1 A2 b(RHS) min ratio bi /yik
0 x1 1 0 -2/5 1/5 0 × × 2/5
0 x2 0 1 1/10 -3/10 0 × × 9/10
0 s3 0 0 3/10 1/10 1 × × 37/10
Zj − Cj 0 0 0 0 0 × × Z∗ = 0

Since all Zj − Cj ≥ 0, Maz z x = 0, and no artificial vector appears in the basis, we proceed to phase
II.
Phase II

Cj 5 8 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS) min ratio bi /yik
5 x1 1 0 -2/5 1/5 0 2/5 2→
8 x2 0 1 1/10 -3/10 0 9/10 1
0 s3 0 0 3/10 1/10 1 37/10 37
Zj − Cj 0 0 -6/5 ↑ −7/5 0 Z = 46/5

Cj 5 8 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS) min ratio bi /yik
0 s2 5 0 -2 1 0 2 -
8 x2 3/2 1 -1/2 0 0 3/2 -
0 s3 -1/2 0 1/2 0 1 7/2 7→
Zj − Cj 7 0 ↑ −4 0 0 Z = 12

c Dereje T. (MSc.) 54
Linear Optimization March 21, 2023

Cj 5 8 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS) min ratio bi /yik
0 s2 3 0 0 1 2 16
8 x2 1 1 0 0 1/2 5
0 s1 -1 0 1 0 2 7
Zj − Cj 3 0 0 0 4 Z = 40

Since all Zj − Cj ≥ 0, optimal basic feasible solution is obtained. Therefore the solution is Max
Z = 40, x1 = 0, x2 = 5.

3.8.2 Big - M method

Big-M method is another method of removing artificial variables from the basis. In this method, large
undesirable (unacceptable penalty) coefficients to artificial variables are assigned from the point of view
of the objective function. If the 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. The penalty is supposed to be
designated by - M, for a maximization problem, and + M, for a minimization problem, where M > 0.
The Big-M method for solving an LP problem can be summarized in the following steps:
Step 1: Express the LP problem in the standard form by adding slack variables, surplus variables and/or
artificial variables. Assign a zero coefficient to both slack and surplus variables. Then assign a very large
coefficient + M (minimization case) and - M (maximization case) to artificial variable in the objective
function.
Step 2: The initial basic feasible solution is obtained by assigning zero value to decision variables, x1 , x2 , ...,
etc.
Step 3: Calculate the values of zj − cj in last row of the simplex table and examine these values.

1. If all zj − cj ≤ 0, then the current basic feasible solution is optimal.

2. If for a column, k, zk − ck is most positive and all entries in this column are negative, then the
problem has an unbounded optimal solution.

3. If one or more zj −cj > 0 (minimization case), then select the variable to enter into the basis (solution
mix) with the largest positive zj − cj value (largest per unit increase in the objective function value).
This value also represents the opportunity cost of not having one unit of the variable in the solution.
That is,
zk − ck = Max{zj − cj : zj − cj > 0}

Step 4: Determine the key row and key element in the same manner as discussed in the simplex algorithm.
Step 5: Continue with the procedure to update solution at each iteration till optimal solution is obtained.

c Dereje T. (MSc.) 55
Linear Optimization March 21, 2023

Remarks At any iteration of the simplex algorithm one of the following cases may arise:

1. If at least one artificial variable is a basic variable (i.e., variable that is present in the basis)
with zero value and the coefficient it M in each zj − cj ( j = 1, 2, . . ., n) values is non-positive,
then the given LP problem has no solution. That is, the current basic feasible solution is
degenerate.

2. If at least one artificial variable is present in the basis with a positive value and the coefficients
M in each zj − cj ( j = 1, 2, . . ., n) values is non-positive, then the given LP problem has no
optimum basic feasible solution. In this case, the given LP problem has a pseudo optimum
basic feasible solution.

Example 1 :Solve the following linear programming problem by using Big-M method.

Maximize Z = −2x1 − x2
subject to 3x1 + x2 = 3
4x1 + 3x2 ≥ 6
x1 + 2x2 ≤ 4
x1 , x2 ≥ 0

Solution : The standard linear programming problem of the above LP

Maximize Z = −2x1 − x2 + 0s1 + 0s2 − M A1 − M A2

subject to 3x1 + x2 + A1 = 3
4x1 + 3x2 − s1 + A2 = 6
x1 + 2x2 + s2 = 4
x1 , x2 , s1 , s2 , A1 , A2 ≥ 0

Cj -2 -1 0 0 -M -M
CB XB x1 x2 s1 s2 A1 A2 b(RHS) min ratio bi /yik
-M A1 3 1 0 0 1 0 3 3/3 = 1 →
-M A2 4 3 -1 0 0 1 6 6/4 = 3/2
0 s2 1 2 0 1 0 0 4 4/1 = 4
Zj − Cj ↑ 2 − 7M 1-4M M 0 0 0 Z = -9M

Cj -2 -1 0 0 -M -M
CB XB x1 x2 s1 s2 A1 A2 b(RHS) min ratio bi /yik
-2 x1 1 1/3 0 0 × 0 1 1/1/3 = 3
-M A2 0 5/3 -1 0 × 1 2 2/5/3 = 6/5 →
0 s2 0 5/3 0 1 × 0 3 3/5/3 = 9/5
−5M +1
Zj − Cj 0 ↑ 3
M 0 × 0 Z = -2-2m

Cj -2 -1 0 0 -M -M
CB XB x1 x2 s1 s2 A1 A2 b(RHS) min ratio bi /yik
-2 x1 1 0 1/5 0 × × 3/5
-1 x2 0 1 -3/5 0 × × 6/5
0 s2 0 0 1 1 × × 1
Zj − Cj 0 0 1/5 0 × × Z = -12/5

c Dereje T. (MSc.) 56
Linear Optimization March 21, 2023

Since all Zj −Cj ≥ 0, optimal basic feasible is obtained. Therefore the solution is Max Z = −12/5, x1 =
3/5, x2 = 6/5

Example 2

Maximize Z = 3x1 − x2
Subject to 2x1 + x2 ≥ 2
x1 + 3x2 ≤ 3
x2 ≤ 4
x1 , x2 ≥ 0

Solution: The standard linear programming problem

Maximize Z = 3x1 − x2 + 0s1 + 0s2 + 0s3 − M A1

Subject to 2x1 + x2 − s1 + A1 = 2
x1 + 3x2 + s2 = 3
x2 + s 3 = 4
x1 , x2 , s1 , s2 , s3 , A1 ≥ 0

Cj 3 -1 0 0 0 -M
CB XB x1 x2 s1 s2 s3 A1 b(RHS) min ratio bi /yik
-M A1 2 1 -1 0 0 1 2 2/2 = 1 →
0 s2 1 3 0 1 0 0 3 3/1 = 3
0 s3 0 1 0 0 1 0 4 -
Zj − Cj ↑ −2M − 3 -M + 1 M 0 0 0 Z = -2M

Cj 3 -1 0 0 0 -M
CB XB x1 x2 s1 s2 s3 A1 b(RHS) min ratio bi /yik
3 x1 1 1/2 -1/2 0 0 × 1 -
0 s2 0 5/2 1/2 1 0 × 2 2/1/2 = 4 →
0 s3 0 1 0 0 1 × 4 -
Z j − Cj 0 5/2 ↑ −3/2 0 0 × Z=3

Cj 3 -1 0 0 0 -M
CB XB x1 x2 s1 s2 s3 A1 b(RHS) min ratio bi /yik
3 x1 1 3 0 1/2 0 × 3
0 s1 0 5 1 2 0 × 4
0 s3 0 1 0 0 1 × 4
Z j − Cj 0 10 0 3/2 0 × Z=9

Since all Zj − Cj ≥, optimal basic feasible solution is obtained. Therefore, the solution is Max
Z = 9, x1 = 3, x2 = 0.

Example 3

c Dereje T. (MSc.) 57
Linear Optimization March 21, 2023

Maximize Z = 3x1 + 2x2 + x3

subject to 2x1 + x2 + x3 = 12
3x1 + 4x2 = 11
and x1 is unrestricted, x2 , x3 ≥ 0

Solution:The standard linear programming problem

0 00
Maximize Z = 3(x1 − x1 ) + 2x2 + x3 − M A1 − M A2
0 00
subject to 2(x1 − x1 ) + x2 + x3 + A1 = 12
0 00
3(x1 − x1 ) + 4x2 + A2 = 11
0 00
x1 , x1 , x2 , x3 , A1 , A2 ≥ 0

0 00
Maximize Z = 3x1 − 3x1 + 2x2 + x3 − M A1 − M A2
0 00
subject to 2x1 − 2x1 + x2 + x3 + A1 = 12
0 00
3x1 − 3x1 + 4x2 + A2 = 11
0 00
x1 , x1 , x2 , x3 , A1 , A2 ≥ 0

Cj → 3 -3 2 1 -M -M
0 00
CB ↓ XB ↓ x1 x1 x2 x3 A1 A2 b(RHS) min ratio bi /yik
-M A1 2 -2 1 1 1 0 12 12/2 = 6
-M A2 3 -3 4 0 0 1 11 11/3 = 3.6 →
Z j − Cj → ↑ −5M − 3 5M + 3 -5M -2 -M- 1 0 0 Z = -23M

Cj → 3 -3 2 1 -M -M
0 00
CB ↓ XB ↓ x1 x1 x2 x3 A1 A2 b(RHS) min ratio bi /yik
-M A1 0 0 -5/3 1 1 × 14/3 14/3/1 = 14/3 →
0
3 x1 1 -1 4/3 0 0 × 11/3 -
−14M
Zj − Cj → 0 0 5/3M+1 ↑ −M − 1 0 × Z = 3 + 11

Cj → 3 -3 2 1 -M -M
0 00
CB ↓ XB ↓ x1 x1 x2 x3 A1 A2 b(RHS) min ratio bi /yik
1 x3 0 0 -5/3 1 × × 14/3
0
3 x1 1 -1 4/3 0 × × 11/3 -
Zj − Cj → 0 0 1/3 0 × × Z = 47/3

Since all Zj − Cj ≥ 0, optimal basic feasible solution is obtained

0 00
x1 = 11/3, x1 = 0
0 00
x1 = x1 − x1 = 11/3 − 0 = 11/3
Therefore the solution is Max Z = 47/3, x1 = 11/3, x2 = 0, x3 = 14/3.

3.9 Some Complications and Their Resolution

In this section, some of the complications that may arise in applying the simplex method for solving both
maximization and minimization LP problems and their resolution are discussed.

c Dereje T. (MSc.) 58
Linear Optimization March 21, 2023

3.9.1 Unrestricted variables

In actual practice, decision variables, xj ( j = 1, 2, . . ., n) should have non-negative values. However, in

many situations, one or more of these variables may have either positive, negative or zero value. Variables
that can assume positive, negative or zero value are called unrestricted variables. Since use of the simplex
method requires that all the decision variables must have non-negative value at each iteration, therefore
in order to convert an LP problem involving unrestricted variables into an equivalent LP problem having
only nonnegative variables, each of unrestricted variable is expressed as the difference of two non-negative
variables.
Let variable xr be unrestricted in sign. We define two new variables say x0r and x00r such that

xr = x0r − x00r ; &x0r , x00r ≥ 0

If x0r ≥ xr ” , then xr ≥ 0, but and if x0r ≤ x00r , then xr ≤ 0. Also if x0r = x00r , then xr = 0. Hence depending
on the value of x0r and x00r , the variable xr can have either positive or negative sign.
Example Use the simplex method to solve the following LP problem.

Maximize Z = 3x1 + 2x2 + x3

subject to the constraints

2x1 + 5x2 + x3 = 12,

3x1 + 4x2 = 11
and x2 , x3 ≥ 0, and x1 unrestricted.
Solution Introducing an artificial variable A1 in the second constraint of the given LP problem in order
to obtain the basis matrix as shown in Table . Since x1 is unrestricted in sign, introducing the nonnegative
variables x01 and x002 so that x1 = x01 –x001 , where x01 , x001 ≥ 0. The standard form of the LP problem now
becomes:

Maximize Z = 3(x01 − x001 ) + 2x2 + x3 − M A1

subject to the constraints

2(x01 − x001 ) + 5x2 + x3 = 12,
3(x01 − x001 ) + 4x2 + A1 = 11
and x01 , x001 , x2 , x3 , A1 ≥ 0 The initial solution is shown in Table

Cj 3 -3 2 1 -M
CB XB x01 x001 x2 x3 A1 b(RHS) Ratio
1 x3 2 -2 5 1 0 12 12/5 ←
-M A1 3 -3 4 0 1 11 11/4
zj − cj -3M-1 3M+1 ↑-4M+3 0 0

In Table above, z3 − c3 is the largest negative value, the non-basic variable x2 is chosen to enter into the
basis to replace basic variable x3 in the basis. For this, apply the following row operations:

R1 (new) → R1 (old)/5 (key element) R2 (new) → R2 (old) - 4R1 (new).

c Dereje T. (MSc.) 59
Linear Optimization March 21, 2023

to get an improved solution shown in Table below.

Cj 3 -3 2 1 -M
CB XB x01 x001 x2 x3 A1 b(RHS) Ratio
2 x2 2/5 -2/5 1 1/5 0 12/5 12/5(5/2)=6
-M A1 7/5 -7/5 0 -4/5 1 7/5 7/5(5/7)=1 ←
zj − cj ↑-7M/5-11/5 7M/5+11/5 0 4M/5-3/5 0

In Table above, as z1 − c1 in x01 -column is negative, the non-basic variable x01 is chosen to enter into the
basis to replace basic variable A1 in the basis. For this, apply the following row operations:

R2 (new) → R2 (old)(5/7)(key element); R1 (new) → R1 (old) − (2/5)R2 (new).

to get an improved solution shown in Table below.

Cj 3 -3 2 1
CB XB x01 x001 x2 x3 b(RHS) Ratio
2 x2 0 0 1 3/7 2 2/(3/7)=14/3←
3 x01 1 -1 0 -4/7 1
zj − cj 0 0 0 ↑-13/7

Further, in order to improve the solution given in Table above, the non-basic variable x3 is chosen to enter
into the basis and remove basic variable x2 from the basis. For this, apply the following row operations:

R1 (new) → R1 (old)(7/3)(key element); R2 (new) → R2 (old) + (4/7)R1 (new)

to get an improved solution given in Table below.

Cj 3 -3 2 1
CB XB x01 x001 x2 x3 b(RHS)
1 x3 0 0 7/3 1 14/3
3 x01 1 -1 4/3 0 11/3
zj − cj 0 0 13/3 0 47/3

Since in Table above all zj − cj ≤ 0, an optimal solution: x01 = 11/3 or x1 = x01 − x001 = 11/3 − 0 =
11/3; x3 = 14/3 is arrived with Max Z = 47/3.

3.9.2 Tie for entering basic variable (key column)

While solving an LP problem using simplex method two or more columns of simplex table may have same
zj − cj value (positive or negative depending upon the type of LP problem). In order to break this tie,
the selection for key column (entering variable) can be made arbitrary. However, the number of iterations
required to arrive at the optimal solution can be minimized by adopting the following rules:

(i) If there is a tie between two decision variables, then the selection can be made arbitrarily.
(ii) If there is a tie between a decision variable and a slack (or surplus) variable, then select the decision
variable to enter into basis.
(iii) If there is a tie between two slack (or surplus) variables, then the selection can be made arbitrarily

c Dereje T. (MSc.) 60
Linear Optimization March 21, 2023

3.9.3 Tie for leaving basic variable (key row) – degeneracy

While solving an LP problem a situation may arise where either the minimum ratio to identify the basic
variable to leave the basis is not unique or value of one or more basic variables in the xB becomes [Link]
causes the problem of degeneracy.
Usually, the problem of degeneracy arises due to redundant constraint, i.e. one or more of the
constraints of LP problem are not part of feasible solution space. For example, constraints such as x1 ≤
5, x2 ≤ 5 and x1 + x2 ≤ 5 in the LP problem make constraint x1 + x2 ≤ 5 unnecessary (redundant).
Degeneracy may occur at any iteration of the simplex method. In order to break the tie in the
minimum ratios, the selection can be made arbitrarily. However, the number of iterations required to
arrive at the optimal solution can be minimized by adopting the following rules.

(i) Divide the coefficients of slack variables in the simplex table where degeneracy is seen by the corre-
sponding positive numbers of the key column in the row, starting from left to right.

(ii) Compare the ratios in step (i) from left to right column wise, select the row that contains the smallest
ratio.

Remark When there is a tie between a slack and artificial variable to leave the basis, preference should
be given to the artificial variable for leaving the basis.
Example. Solve the following LP problem
Maximize Z = 3x1 + 9x2
subject to the constraints
x1 + 4x2 ≤ 8,
x1 + 2x2 ≤ 4
and x1 , x2 ≥ 0
Solution Adding slack variables s1 and s2 to the constraints, the problem can be expressed as
Maximize Z = 3x1 + 9x2 + 0s1 + 0s2
subject to the constraints
x1 + 4x2 + s1 = 8,
x1 + 2x2 + s2 = 4
and x1 , x2 , s1 , a2 ≥ 0
The initial basic feasible solution is given in Table . Since z2 − c2 = −9 is the largest negative value,
therefore, variable x2 is selected to be entered into the basis. However, both variables s1 and s2 are eligible
to leave the basis as the minimum ratio is same, i.e. 2, so there is a tie among the ratio in rows s1
and s2 .This causes the problem of degeneracy. To obtain the key row for resolving degeneracy, apply the
following procedure:

(i) Write the coefficients of the slack variables as shown in Table .

cj 3 9 0 0
CB XB x1 x2 s1 s2 b(RHS) min. ratio
0 s1 1 4 1 0 8 8/4=2
0 s2 1 2 0 1 4 4/2=2
Z j − Cj -3 ↑-9 0 0 0

c Dereje T. (MSc.) 61
Linear Optimization March 21, 2023

(ii) Dividing the coefficients of slack variables s1 and s2 by the corresponding elements in the key column
as shown below in the table.
x2 column
Row (Key Column) s1 s2
s1 4 1/4=1/4 0/4=0
s2 2 0/2=0 1/2=1/2

(iii) Comparing the ratios of Step (ii) from left to right column wise, the minimum ratio (i.e., 0/2 = 0)
occurs in the s2 -row. Thus, variable s2 is selected to leave the basis. The new solution is shown in
Table
cj 3 9 0 0
CB XB x1 x2 s1 s2 b(RHS)
0 s1 -1 0 1 -2 0
9 x2 1/2 1 0 1/2 2
Zj − Cj 3/2 0 0 9/2 18

In Table above , all Zj − Cj ≤ 0. Hence, an optimal solution is arrived at. The optimal basic feasible
solution is: x1 = 0, x2 = 2 and Max Z = 18.

3.10 Types of Linear Programming Solutions

While solving any LP problem using simplex method, at the stage of optimal solution, the following three
types of solutions may exist:

3.10.1 Alternative (multiple) optimal solutions

The zj − cj values in the simplex table indicates the contribution in the objective function value by each
unit of a variable chosen to enter into the basis. Also, an optimal solution to a maximization(minimization)
LP problem is reached when all zj − cj ≥ 0(zj − cj ≤ 0). But, if zj − cj = 0 for a non-basic variable column
in the optimal simplex table and such nonbasic variable is chosen to enter into the basis, then another
optimal solution so obtained will show no improvement in the value of objective function.
Example Solve the following LP problem.

Maximize Z = 6x1 + 4x2

subject to the constraints

2x1 + 3x2 ≤ 30,

3x1 + 2x2 ≤ 24
,
x1 + x2 ≥ 3
and
x1 , x2 ≥ 0
Solution Adding slack variables s1 , s2 , surplus variable s3 and artificial variable A1 in the constraint
set,the LP problem becomes

c Dereje T. (MSc.) 62
Linear Optimization March 21, 2023

Maximize Z = 6x1 + 4x2 + 0s1 + 0s2 + 0s3 − M A1

subject to the constraints

2x1 + 3x2 + s1 = 30,
3x1 + 2x2 + s2 = 24
,
x1 + x2 − s3 + A1 = 3
and
x1 , x2 , s1 , s2 , A1 ≥ 0

The optimal solution: x1 = 8, x2 = 0 and Max Z = 48 for this LP problem is shown in Table below.

Cj 6 4 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS) Ratio
0 s1 0 5/3 1 -2/3 0 14 42/5 ←
0 s3 0 -1/3 0 1/3 1 5
6 x1 1 2/3 0 1/3 0 8 12
zj − cj 0 ↑0 0 2 0 48

In Table above , z2 –c2 = 0 corresponds to a non-basic variable, x2 . Thus, an alternative optimal solution
can also be obtained by entering variable x2 into the basis and removing basic variable, s1 from the basis.
The new solution is shown in Table below.

Cj 6 4 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS)
4 x2 0 1 3/5 -2/5 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 − cj 0 0 0 2 0 48

The optimal solution shown in Table above is: x1 = 12/5, x2 = 42/5 and Max Z = 48. Since this optimal
solution shows no change in the value of objective function, it is an alternative solution. Once again,
z3 –c3 = 0 corresponds to non-basic variable, s1 . This again indicates that an alternative optimal solution
exists.

3.10.2 Unbounded solution

In a maximization LP problem, if zj −zj < 0(zj −cj > 0 for a minimization case) corresponds to a non-basic
variable column in simplex table, and all aij values in this column are negative, then minimum ratio to
decide basic variable to leave the basis can not be calculated. It is because negative value in denominator
would indicate the entry of a non-basic variable in the basis with a negative value (an infeasible solution).
Also,a zero value in the denominator would result in a ratio having an infinite value and would indicate
that the value of non-basic variable could be increased infinitely with any of the current basic variables
being removed from the basis.
Example Solve the following LP problem.

c Dereje T. (MSc.) 63
Linear Optimization March 21, 2023

Maximize Z = 3x1 + 5x2

subject to the constraints

x1 − 2x2 ≤ 6,
3x1 ≤ 10
,
x2 ≥ 1
and
x1 , x2 ≥ 0
Solution:Adding slack variables s1 , s2 , surplus variable s3 and artificial variable A1 in the constraint set.
Then the standard form of LP problem becomes

Maximize Z = 3x1 + 5x2 + 0s1 + 0s2 + 0s3 − M A1

subject to the constraints

x1 − 2x2 + s1 = 6,
3x1 + s2 = 10
,
x2 − s3 + A1 = 1
and
x1 , x2 , s1 , s2 , s3 , A1 ≥ 0
The initial solution to this LP problem is shown in Table below.

Cj 3 5 0 0 0 -M
CB xB x1 x2 s1 s2 s3 A1 b(RHS) min. 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 − cj -3 ↑-5-M 0 0 M 0 M

Iteration 1: Since z2 –c2 ≥ 0, non-basic variable x2 is chosen to enter into the basis in place of basic
variable A1 . The new solution is shown in Table below.

Cj 3 5 0 0 0 -M
CB xB x1 x2 s1 s2 s3 A1 b(RHS)
0 s1 1 0 1 0 -2 2 8
0 s2 1 0 0 1 0 0 10
5 x2 0 1 0 0 -1 1 1
zj − cj -3 0 0 0 -5 M+5 5

In Table above, z5 –c5 = −5 is largest negative, so variable s3 should enter into the basis. But, coefficients in
the ‘s03 column are all negative or zero. This indicates that s3 cannot be entered into the basis. However,the
value of s3 can be increased infinitely without removing any one of the basic variables. Further, since s3 is
associated with x2 in the third constraint, x2 will also be increased infinitely because it can be expressed
as x2 = 1 + s3 –A1 . Hence, the solution to the given problem is unbounded.

c Dereje T. (MSc.) 64
Linear Optimization March 21, 2023

3.10.3 Infeasible solution

If LP problem solution does not satisfy all of the constraints, then such a solution is called infeasible
solution. Also, infeasible solution occurs when all zj − cj values satisfy optimal solution condition but at
least one of artificial variables appears in the basis with a positive value. This situation may occur when
an LP model is either improperly formulated or more than two of the constraints are incompatible.
Lp models with inconsistent constraints have no feasible solution. This situation can never occur if all
the constraints are of the type ≤ with nonnegative right hand sides because the slacks provide a feasible
solution. For other types of constraints we use artificial variables. Although the artificial variables are
penalized in the objective function to force them to zero at the optimum, this ca occur only if the model
has a feasible space. Otherwise, at least one artificial variables will be positive in the optimum iteration.
Example Solve the following LP problem.

Maximize Z = 6x1 + 4x2

subject to the constraints

x1 + x2 ≤ 5,
x2 ≥ 8
and
x1 , x2 ≥ 0
Solution:Adding slack, surplus and artificial variables, the standard form of LP problem becomes

Maximize Z = 6x1 + 4x2 + 0s1 + 0s2 − M A1

subject to the constraints

x1 + x2 + s1 = 5,
x2 − s 2 + A 1 = 8
and
x1 , x2 , s1 , s2 , A1 ≥ 0
The initial solution to this LP problem is shown in Table below.

Cj 6 4 0 0 -M
CB XB x1 x2 s1 s2 A1 b(RHS) min. ratio
6 x1 1 1 1 0 0 5 5/1←
-M A1 0 1 0 -1 1 8 8/1
zj − cj 0 ↑2-M 6 M 0 30-8M

Iteration 1: Since z2 –c2 = 2 − M (≤ 0), non-basic variable x2 is chosen to enter into the basis to
replace basic variable x1 . The new solution is shown in Table below.

c Dereje T. (MSc.) 65
Linear Optimization March 21, 2023

Cj 6 4 0 0 -M
CB XB x1 x2 s1 s2 A1 b(RHS)
4 x2 1 1 1 0 0 5
-M A1 -1 0 -1 -1 1 3
zj − cj M-2 0 4+M M 0 20-3M

In table above, since all zj –cj ≥ 0, the current solution is optimal. But this solution is not feasible
for the given LP problem because values of decision variables are: x1 = 0 and x2 = 5 violates second
constraint,x2 ≥ 8. The presence of artificial variable A1 = 3 in the solution also indicates that the optimal
solution violates the second constraint (x2 ≥ 8) by 3 units.

c Dereje T. (MSc.) 66
 Duality Theory and Further Variation of Simplex Method
4
4.1 Introduction
The term ‘dual’, in general, implies two or double. In linear programming, duality implies that each linear
programming problem can be analyzed in two different ways but would have equivalent solutions. Any LP
problem (either maximization and minimization) can be stated in another equivalent form based on the
same data. The new LP problem is called dual linear programming problem or in short dual. In general,
it is immaterial which of the two problems is called primal or dual, since the dual of the dual is primal.
There is no need to solve both LP problems separately. Solving one LP problem is equivalent to
solving the other simultaneously. Thus, if the optimal solution to one is known, the optimal solution of
the other can also be read from the Zj − Cj row. In some cases, considerable computing time can be
reduced by solving the dual LP problem

4.2 Dual Linear Programs

Definition 4.2.1. 1. A linear problem is said to be written in maximization(canonical) form if

• The objective is in maximization form

• All the constraints are ≤
• All variables are nonnegative

i.e

Maximize Z = C T X
Subject to: AX ≤ b (4.1)
X≥0

2. A linear problem is said to be written in minimization(canonical) form if

• The objective is in minimization form

• All the constraints are ≥
• All variables are nonnegative

67
Linear Optimization March 21, 2023

i.e

Minimize Z = C T X
Subject to: AX ≥ b (4.2)
X≥0

Note that there are no restrictions on the signs of the coefficients aij , constant terms bi , and coeffi-
cients cj .

Example. Consider the following linear problem:

max z = x1 − 3x2 + x3
subject to
x1 + x2 + x3 ≥ 2
−x1 + 2x2 − x3 ≤ 3
x1 − x2 + 2x3 = −1
x1 , x2 , x3 ≥ 0

The problem in maximization canonical form:

max z = x1 − 3x2 + x3
subject to
−x1 − x2 − x3 ≤ −2
−x1 + 2x2 − x3 ≤ 3
x1 − x2 + 2x3 ≤ −1
−x1 + x2 − 2x3 ≤ 1
x1 , x2 , x3 ≥ 0

Example. Consider the following linear problem:

max z = x1 − x2
subject to
3x1 + 2x2 ≤ 1
x1 − 2x2 ≥ 3
x1 , x2 ≥ 0

The problem in minimization symmetric form:

min −z = −x1 + x2
subject to
−3x1 − 2x2 ≥ −1
x1 − 2x2 ≥ 3
x1 , x2 ≥ 0

Definition 4.2.2. The dual of the max problem (4.1) is the following linear programming problem:

c Dereje T. (MSc.) 68
Linear Optimization March 21, 2023

Minimize V = bT Y
Subject to: AT Y ≥ C (4.3)
Y ≥0

Thus the dual to the max problem (4.1) with m (≤) constraints and n nonnegative variables is a minimiza-
tion problem with m nonnegative variables and n(≥) constraints.

For each i, 1 ≤ i ≤ m, variable yi of the dual corresponds to the ith constraint of the max problem. The
coefficients of yi in the ith column of the constraints of (4.3) are the coefficients of the ith constraint in
(4.1). Reciprocally, for each j, 1 ≤ j ≤ n, the j th constraint in the dual corresponds to the j th variable
xj in (4.1); the coefficients of the variables in the j th constraint in the dual are the coefficients of xj in
the constraints of (4.1). Note also the interchange between the constant terms of the constraints and the
coefficients of the objective functions for the two problems.

Primal-dual correspondence

For any primal problem and the corresponding dual problem, there is a direct correspondence between the
parameters of the problems, which may be summarized as follows:

• The size of the constraint matrix A of the primal problem is m × n; there are m constraints and n
variables in it. The constraint matrix of the dual problem is the transpose of the constraint matrix
of the primal, AT , and therefore, the dual has n constraints and m variables.

• The right hand side vector b of the primal problem is the vector of cost coefficients of the dual
problem.

• The vector of cost coefficients c of the primal problem is the right hand side vector of the dual
problem.

• The number of constraints of the primal problem is equal to the number of variables of the dual
problem.

• The number of variables of the primal problem is equal to the number of constraints of the dual
problem.
Example 4.1. The linear programming problem of:

(P) Maximize Z = 6x1 + x2 + 4x3

Subject to: 3x1 + 7x2 + x3 ≤ 15
x1 − 2x2 + 3x3 ≤ 20
x1 , x2 , x3 ≥ 0

has as its dual the problem of:

(D) Minimize V = 15y1 + 20y2

Subject to: 3y1 + y2 ≥ 6

c Dereje T. (MSc.) 69
Linear Optimization March 21, 2023

7y1 − 2y2 ≥ 1
y1 + 3y2 ≥ 4
y1 , y2 ≥ 0

Note: Let the LPP be given by:

(P) Maximize Z = C T X
Subject to: AX ≥ b
X≥0

has as its dual the problem of:

(D) Minimize V = bT Y
Subject to: AT Y ≤ C = −AT w ≥ C
Y ≤ 0, w = −Y ≥ 0

Example 4.2. The linear programming problem of:

(P) Minimize Z = 12x1 + 9x2 − 2x3

Subject to: 8x1 + 3x2 + 5x3 ≥ 6
x1 − 3x3 ≥ −4
x1 , x2 , x3 ≥ 0.

we can write immediately that its dual is to:

(D) Maximize V = 6y1 − 4y2

Subject to: 8y1 + y2 ≤ 12
3y1 ≤ 9
5y1 − 3y2 ≤ −2
y1 , y2 ≥ 0.

Example 4.3. To determine the dual of the problem of:

Maximize Z = 6x1 + x2 + 4x3

Subject to: 3x1 + 7x2 + x3 ≤ 15
x1 − 2x2 + 3x3 = 20
x1 , x2 , x3 ≥ 0.

We replace the equality constraint by two inequalities and multiply the resulting (≥) inequality by (-1) to
find the equivalent problem in max form of:

Maximize Z = 6x1 + x2 + 4x3

Subject to: 3x1 + 7x2 + x3 ≤ 15
x1 − 2x2 + 3x3 ≤ 20
−x1 + 2x2 − 3x3 ≤ −20
x1 , x2 , x3 ≥ 0.

The dual problem is:

c Dereje T. (MSc.) 70
Linear Optimization March 21, 2023

Minimize V = 15y1 + 20y2 − 20y3

Subject to: 3y1 + y2 − y3 ≥ 6
7y1 − 2y2 + 2y3 ≥ 1
y1 + 3y2 − 3y3 ≥ 4
y1 , y2 , y3 ≥ 0.
Example 4.4. Consider the following linear program and its dual:

P : Minimize 6x1 + 8x2

subject to 3x1 + x2 ≥ 4
5x1 + 2x2 ≥ 7
x1 , x2 ≥ 0.
D : Maximize 4w1 + 7w2
subject to 3w1 + 5w2 ≤ 6
w1 + 2w2 ≤ 8
w1 , w2 ≥ 0.

The objective of duality in LPP is:

(a) to construct alternative algorithm.

(b) to reduce expenditure of calculation.
(c) to interprete a certain properties of linear models and their table in economy.

Standard Form of Duality

Another equivalent definition of duality may be given with the primal linear program stated in the following
standard form:

P : Minimize Z = C T X
subject to AX = b
X ≥ 0.

Then the dual linear program is defined by:

D : Maximize V = bT Y
subject to AT Y ≤ C
Y unrestricted
Example 4.5. Consider the following linear program and its dual

P : Minimize 6x1 + 8x2

subject to 3x1 + x2 − x3 = 4
5x1 + 2x2 − x4 = 7
x1 , x2 , x3 , x4 ≥ 0
D : Maximize 4w1 + 7w2
subject to 3w1 + 5w2 ≤ 6
w1 + 2w2 ≤ 8
−w1 ≤ 0
−w2 ≤ 0
w1 , w2 unrestricted.

c Dereje T. (MSc.) 71
Linear Optimization March 21, 2023

Duality. The general case

In general, many linear problems contain ≤, = or ≥ constraints. The variables may also be ≥ 0, ≤ 0 or
unrestricted in sign. In order to compute the dual of any linear problem, we should convert it to the
maximization(minimization) canonical form and derive from it the dual problem associated. However, in
practice it is possible to find immediately the associated dual problem of any given linear problem by using
the correspondences of Table 4.1.

Objective function: max ←→ Objective function: min

ith constraint is ≤ bi ←→ ith variable is ≥ 0
ith constraint is = bi ←→ ith variable is unrestricted
ith constraint is ≥ bi ←→ ith variable is ≤ 0
ith variable is ≥ 0 ←→ ith constraint is ≥ bi
ith variable is unrestricted ←→ ith constraint is =bi
ith variable is ≤ 0 ←→ ith constraint is ≤ bi

Table 4.1: Primal-dual correspondences

Consider the following linear program:

P : Minimize c1 x1 + c2 x2 + c3 x3
subject to A11 x1 + A12 x2 + A13 x3 ≥ b1
A21 x1 + A22 x2 + A23 x3 ≤ b2
A31 x1 + A32 x2 + A33 x3 = b3
x1 ≥ 0, x2 ≤ 0, x3 unrestricted.

Converting this problem to canonical form by multiplying the second set of inequalities by - 1 , writing
0 0 00
the equality constraint set equivalently as two inequalities, and substituting, x2 = −x2 , x3 = x3 − x3 , we
get:

0 0 00
P : Minimize c1 x1 − c2 x2 + c3 x3 − c3 x3
0 0 00
subject to A11 x1 − A12 x2 + A13 x3 − A13 x3 ≥ b1
0 0 00
−A21 x1 + A22 x2 − A23 x3 + A23 x3 ≥ −b2
0 0 00
A31 x1 − A32 x2 + A33 x3 − A33 x3 ≥ b3
0 0 00
−A31 x1 + A32 x2 − A33 x3 + A33 x3 ≥ −b3
0 0 00
x1 , x2 , x3 , x3 ≥ 0

0 0 00
Denoting the dual variables associated with the four constraint sets as w1 , w2 , w3 , and w3 , respectively, we
obtain the dual to this problem as follows:

0 0 00
D : Minimize b1 w1 − b2 w2 + b3 w3 − b3 w3
0 0 00
subject to A11 w1 − A21 w2 + A31 w3 − A31 w3 ≤ c1
0 0 00
−A12 w1 + A22 w2 − A32 w3 + A32 w3 ≤ −c2
0 0 00
A13 w1 − A23 w2 + A33 w3 − A33 w3 ≤ c3
0 0 00
−A13 w1 + A23 w2 − A33 w3 + A33 w3 ≤ −c3
0 0 00
w1 , w2 , w3 , w3 ≥ 0

0 0 00
Finally, using w2 = −w2 and w3 = w3 − w3 , the foregoing problem may be equivalently stated as follows:

c Dereje T. (MSc.) 72
Linear Optimization March 21, 2023

D : Maximize b1 w1 + b2 w2 + b3 w3
subject to A11 w1 + A21 w1 + A31 w3 ≤ c1
A12 w1 + A22 w2 + A32 w3 ≥ c2
A13 w1 + A23 w2 + A33 w3 = c3
w1 ≥ 0, w2 ≤ 0, w3 unrestricted.

Note how this form of the dual D relates to the original primal problem P, where w1 , w2 , and w3 are the
dual variables associated with the three sets of constraints in P; similarly, x1 , x2 , and x3 are the ”dual”
variables associated with the three sets of constraints in D. Furthermore, note that the first set of con-
straints in P were already in the required form, and hence, w1 ≥ 0 in D. The second constraint set needed
to be multiplied by -1 in order to be put in the required form, and hence, w2 ≤ 0 in D. Similarly, because of
the transformation needed on the third set of constraints in P, we obtain w3 as unrestricted in D. Likewise,
the transformations needed on the variables in P to put it in the required canonical form dictate the form
of the constraints in D. With these observations, the dual D to the problem P can now be written directly
without using the intermediate transformation steps. These results are summarized in Table given below.

Relationships Between Primal and Dual Problems

Minimization problem Maximization problem

variables

constraint
≥0 ←→ ≤
≤0 ←→ ≥
unrestricted ←→ =
constraint

≥ ←→ ≥0 variables
≤ ←→ ≤0
= ←→ unrestricted

Example 4.6. Consider the following linear program:

Maximize 8x1 + 3x2 − 2x3

subject to x1 − 6x2 + x3 ≥ 2
5x1 + 7x2 − 2x3 = −4
x1 ≤ 0, x2 ≥ 0, x3 unrestricted.

Applying the results of the table, we can immediately write down its dual:

Minimize 2w1 − 4w2

subject to w1 + 5w2 ≤ 8
−6w1 + 7w2 ≥ 3
w1 − 2w2 = −2
w1 ≤ 0, w2 unrestricted

4.3 Duality Theorems

Theorem 4.3.1. The dual of the dual is primal.

c Dereje T. (MSc.) 73
Linear Optimization March 21, 2023

Proof : Consider the primal linear programming problem

P: Maximize Z = C T X
subject to AX ≤ B, X ≥ 0

It dual Linear Programming problem becomes

D: Minimize Z ∗ = B T W
subject to AT W ≥ C, W ≥ 0 (4.4)

Equation(4.4) can be written as

D: Maximize Z ∗ = −B T W
subject to −AT W ≤ −C, W ≥ 0 (4.5)

The dual of (4.5) becomes

D∗ : Minimize z ∗∗ = −(C)T X
subject to −(AT )T X ≥ −B, X ≥ 0

Which is equivalent to

Maximize Z = C T X
Subject to AX ≤ B, X ≥ 0

Theorem 4.3.2. (Weak duality) Let x and y be any feasible solutions to the primal and dual problems,
respectively. The following inequality holds:

z = cT x ≤ bT y = G.

Proof. Since x is a feasible solution to the primal problem, Ax ≤ b and x ≥ 0 are satisfied. Since y is a
feasible solution to the dual problem, AT y ≥ c and y ≥ 0 are satisfied. Multiplying Ax ≤ b on the left by
y T , and AT y ≥ c by xT , we get:
y T Ax ≤ y T b = bT y.
xT AT y ≥ xT c = cT x.
Since xT AT y = y T Ax, the following holds:

z = cT x ≤ y T Ax ≤ bT y = G.

The weak duality theorem indicates that the maximum objective value for the primal problem is a lower
bound on the minimum objective value of the dual problem. Similarly, the minimum objective value for
the dual problem is an upper bound on the maximum objective value of the primal problem. The following
corollaries are immediate consequences of the previous theorem.

Corollary 4.3.1. If x∗ and y ∗ are feasible solutions to the primal and dual problem such that cT x∗ = bT y ∗
holds, then x∗ and y ∗ are optimal solutions to the primal and dual problems respectively.

c Dereje T. (MSc.) 74
Linear Optimization March 21, 2023

Proof. The weak duality theorem states that, for any feasible solutions x and y to the primal and
dual problem, the following holds:
cT x ≤ bT y.
Since y ∗ is a solution to the dual problem, cT x ≤ bT y ∗ holds. cT x∗ = bT y ∗ is verified, and therefore, for
any solution x to the primal problem the following holds:

cT x ≤ cT x ∗ .

We conclude that x∗ is an optimal solution to the primal problem. Similarly, since bT y ∗ = cT x∗ ≤ bT y, for
any solution y to the dual problem the following holds:

bT y ∗ ≤ bT y.

We conclude that y ∗ is an optimal solution to the dual problem.

Corollary 4.3.2. If the primal problem is feasible and unbounded, the dual problem is infeasible.

Proof. Taking into account that cT x ≤ bT y holds for any feasible solutions x and y, if the primal
objective value is unbounded, then there does not exist any solution y to the dual problem that is an
upper bound of the primal problem.
The following corollary is proved in a similar way
Corollary 4.3.3. If the dual problem is feasible and unbounded, the primal problem is infeasible.

Proof. Taking into account that cT x ≤ bT y holds for any feasible solutions x and y, if the dual
objective value is unbounded, then there does not exist any solution x to the primal problem that is a
lower bound of the dual problem.

If the primal problem is infeasible, the dual problem may be either infeasible or unbounded. Similarly,
if the dual problem is infeasible, the primal problem may be either infeasible or unbounded.
Theorem 4.3.3. (Fundamental theorem of duality:) With regard to the primal and dual linear
programming problems, exactly one of the following statements is true.

(i) both posses optimal solution X ∗ and Y ∗ with cT X ∗ = bT Y ∗

(ii) one problem has unbounded objective value, in which case the other problem must be infeasible.

(iii) both problems are infeasible.

From this theorem we see that duality is not completely symmetric. The best we can say is that
(here optimal means finite optimal, and unbounded means having unbounded objective value):

P optimal ⇔ D optimal
P unbounded ⇒ D infeasible
D unbounded ⇒ P infeasible
P infeasible ⇒ D unbounded or infeasible
D infeasible ⇒ P unbounded or infeasible

Example. Let us check Corollary above for the following primal and dual problems. In this case,
the primal is unbounded and the dual infeasible.

c Dereje T. (MSc.) 75
Linear Optimization March 21, 2023

max z = 3x1 + 2x2 min G = 2y1 + 4y2

subject to subject to
−2x1 + x2 ≤ 2 −2y1 + 2y2 ≥ 3
2x1 + x2 ≥ 4 y1 + y2 ≥ 2
x1 , x2 ≥ 0 y1 ≥ 0, y2 ≤ 0

The graphical solution shows that the primal problem is unbounded.

The feasibility region for the dual problem is empty; that is, the dual problem is infeasible

c Dereje T. (MSc.) 76
Linear Optimization March 21, 2023

4.4 Dual –Simplex Method

4.4.1 Computational Procedure of Dual Simplex Method

Introduction
Any LPP for which it is possible to find infeasible but better than optimal initial basic solution can be
solved by using dual simplex method. Such a situation can be recognized by first expressing the constraints
in ≤ form and the objective function in the maximization form. After adding slack variables, if any right
hand side element is negative and the optimality condition is satisfied then the problem can be solved
by dual simplex method. Negative element on the right hand side suggests that the corresponding slack
variable is negative. This means that the problem starts with optimal but infeasible basic solution and we
proceed towards its feasibility.

The dual simplex method is similar to the standard simplex method except that in the latter the starting
initial basic solution is feasible but not optimum while in the former it is infeasible but optimum or better
than optimum. The dual simplex method works towards feasibility while simplex method works towards
optimality.

Computational Procedure of Dual Simplex Method

The iterative procedure is as follows
Step 1: First convert the minimization LPP into maximization form, if it is given in the minimization
form.
Step 2: Convert the ≥ type inequalities of given LPP, if any, into those of ≤ type by multiplying the
corresponding constraints by -1.
Step 3 : Introduce slack variables in the constraints of the given problem and obtain an initial basic
solution.
Step 4: Test the nature of ∆Zj in the starting table

• If all ∆Zj and XB are non-negative, then an optimum basic feasible solution has been attained.

• If all ∆Zj are non-negative and at least one basic variable XB is negative, then go to step 5.

• If at least one ∆Zj is negative, the method is not appropriate.

Step 5: Select the most negative XB . The corresponding basis vector then leaves the basis set B. Let Xr
be the most negative basic variable. That is Xr = min{bi : bi < 0}
Step 6: Test the nature of Xr

• If all the row elements of Xr (aij ) are non-negative, then there does not exist any feasible solution
to the given problem.

• If at least one (aij ) is negative, then compute M ax(∆Zj /aij ), aij < 0 and determine the least negative
for incoming vector.

Step 7: Test the new iterated dual simplex table for optimality. Repeat the entire procedure until either
an optimum feasible solution has been attained in a finite number of steps.

c Dereje T. (MSc.) 77
Linear Optimization March 21, 2023

Remark 4.4.1. If optimal solution of primal exists, then CBT B −1 gives the optimal solution of the
dual. It is to be noted that B −1 is available from the optimal table below the starting basis. Since
starting basis is usually in terms of slack and surplus variable, to write B −1 we multiply by -1 to
each entry of the column in optimal table below each surplus variable.

Example 4.7. Solve the following LPP by dual simplex method.

Minimize Z = 2x1 + x2
Subject to 3x1 + x2 ≥ 3
4x1 + 3x2 ≥ 6
x1 + 2x2 ≥ 3
and x1 ≥ 0, x2 ≥ 0

Solution
Step 1: Rewrite the given problem in the form

0
Maximize Z = −2x1 − x2
Subject to −3x1 − x2 ≤ −3
−4x1 − 3x2 ≤ −6
−x1 − 2x2 ≤ −3
and x1 ≥ 0, x2 ≥ 0

Step 2: Adding slack variables to each constraint

0
Maximize Z = −2x1 − x2
Subject to −3x1 − x2 + s1 = −3
−4x1 − 3x2 + s2 = −6
−x1 − 2x2 + s3 = −3
and x1 , x2 , s1 , s2 , s3 ≥ 0

Step 3: Construct the simplex table

C -2 -1 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS)
0 s1 -3 -1 1 0 0 -3
0 s2 -4 -3 0 1 0 -6
0 s3 -1 -2 0 0 1 -3
∆Zj 2 1 0 0 0

Step 4: To find the leaving vector

Min (-3, -6, -3) = -6. Hence s2 is outgoing vector.
Step 5: To find the incoming vector
Max(∆Z1 /a21 , ∆Z2 /a22 = M ax(2/ − 4, 1/ − 3) = −1/3. So x2 is incoming vector
Step 6: The key element is -3. Proceed to next iteration.

c Dereje T. (MSc.) 78
Linear Optimization March 21, 2023

C -2 -1 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS)
0 s1 -5/3 0 1 -1/3 0 -1
-1 x2 4/3 1 0 -1/3 0 2
0 s3 5/3 0 0 -2/3 1 1
∆Zj 2/3 0 0 1/3 0

Step 7 : To find the leaving vector

Min (-1, 2, 1) = -1. Hence s1 is outgoing vector.
Step 8: To find the incoming vector
M ax(∆Z1 /a11 , ∆Z4 /a14 ) = M ax(−2/5, −1) = −2/5. So x1 is incoming vector.
Step 9: The key element is -5/3. Proceed to next iteration.

C -2 -1 0 0 0
CB XB x1 x2 s1 s2 s3 b(RHS)
-2 x1 1 0 -3/5 1/5 0 3/5
-1 x2 0 1 4/5 -3/5 0 6/5
0 s3 0 0 1 -1 1 0
∆Zj 0 0 2/5 1/5 0

Step 10: ∆Zj ≥ 0 and XB ≥ 0, therefore the optimal solution is

0
M axZ = −12/5, Z = 12/5 and x1 = 3/5, x2 = 6/5.
We have already mentioned that the solution of dual starting BFS as CbT B −l . Hence the
 is kept below 
−3/5 1/5 0
optimal solution of dual is [y1 , y2 , y3 ] = [−2, −1, 0]  4/5 −3/5 0 = [2/5.1/5, 0]. i.e simply take the
1 −1 1
values(read) frow last row Zj − Cj corresponding to slack variables in sequential ways.

In fact, for the above example the moment we get a feasible solution in the primal (RHS ≥ 0) we
can terminate even without showing that the optimality condition is satisfied. This is because the
dual simplex algorithm maintain the dual feasible always.

Example 4.8. Consider the Primal problem:

(P) Max Z = 12x1 + 8x2

Subject to: 4x1 + 2x2 ≤ 80
2x1 + 3x2 ≤ 100
5x1 + x2 ≤ 75
x1 , x2 ≥ 0.

The dual problem is:(D) Min V = 80y1 + 100y2 + 75y3

Subject to: 4y1 + 2y2 + 5y3 ≥ 12
2y1 + 3y2 + y3 ≥ 8
y1 , y2 , y3 ≥ 0.

Now, apply the fact that Min f (x) = − Max (−f (x))
Answer: Min V=300.
Theorem 4.4.1. (Strong Duality Theorem)

c Dereje T. (MSc.) 79
Linear Optimization March 21, 2023

1. If either the primal or the dual linear program has a finite optimal solution, then so does the other
and they achieve the same optimal objective value.

2. If either problem has an unbounded objective value, then the other has no feasible solution.

Proof. For the first part, without loss of generality, we can assume that the primal problem has reached
a finite optimum at a basic feasible solution X. If we utilize the simplex algorithm at X and define
BT CB
Y T = CBT B −1 , then AT Y − C = [ N T ]Y − [ C ] = r ≤ 0. therefore, Y is dual feasible. Moreover, Since X
N
is a basic feasible solution, we have

C T X = CBT XB = CBT B −1 b = Y T b = bT Y

4.5 The Primal-Dual simplex Method

Theorem 4.5.1. (Complementary Slackness): Let x be a feasible solution to the primal and y be a
feasible solution to the dual where

Maximize Z = C T X
subject to AX ≤ b (P)
X≥0
Minimize V = bT Y
subject AT Y ≥ C (D)
Y ≥0

Then x is optimal to the primal and y is optimal to the dual if and only if the condition of compli-
mentary slackness hold

( nj=1 aij xj − bi )yi = 0, for i = 1, 2, ..., m.

P

Pm and
( i=1 aji yj − ci )xj = 0, for j = 1, 2, ..., n.

i.e xT (AT y − c) = 0, y T (Ax − b) = 0

According to the foregoing equations, the product of two nonnegative factors is zero; this implies that
if one of them is not zero, then the other must be. Thus, we obtain the following conclusions, which enable
us to compute the optimal solution to one of the problems from the optimal solution to the other.

1. If a primal variable is positive, that is to say, greater than zero, then the corresponding constraint
in the dual must hold with equality.

x > 0 ⇒ AT y − c = 0.

2. If a constraint of the primal is not binding, that is to say, if the equality does not hold, then the
corresponding dual variable must be zero.

Ax < b ⇒ y = 0.

c Dereje T. (MSc.) 80
Linear Optimization March 21, 2023

3. If a dual variable is positive, that is to say, greater than zero, then the corresponding constraint in
the primal must hold with equality.

y > 0 ⇒ Ax − b = 0.

4. If a constraint of the dual is not binding, that is to say, if the equality does not hold, then the
corresponding primal variable must be zero.

AT y > c ⇒ x = 0
Example 4.9. Consider the following primal linear problem:

(p) max z = 3x1 + x2 − 2x3

subject to
x1 + 2x2 + x3 ≤ 5
2x1 − x2 + 3x3 ≤ 4
x1 , x2 , x3 ≥ 0

The optimal solution to the problem is x∗T = (13/5, 6/5, 0). The dual problem is the following:

(D) min G = 5y1 + 4y2

subject to
y1 + 2y2 ≥ 3
2y1 − y2 ≥ 1
y1 + 3y2 ≥ −2
y1 , y2 ≥ 0

Using the theorem of complementary slackness, we compute the optimal solution to the dual problem,
proceeding like this:

Primal variables Dual constraints

x∗1 = 13
5
>0 ⇒ y1∗ + 2y2∗ = 3
∗ 6
x2 = 5 > 0 ⇒ 2y1∗ − y2∗ = 1
x∗3 = 0 ⇒ y1∗ + 3y2∗ ≥ −2
Primal constraints Dual variables
13
5
+ 2 × 65 = 5 ⇒ we compute y1∗
2 × 13 5
− 65 = 4 ⇒ we compute y2∗

By solving the system of linear equations, we obtain the optimal solution to the dual problem.

y1∗ = 1, y2∗ = 1.

Example 4.10. Consider the following primal LP problem

Minimize 6x1 − 5x3

Subject to 6x1 − 3x2 + x3 = 2
3x1 + 4x2 + x3 ≤ 5
x1 − 7x2 ≤ 5
x1 ≥ 0, x2 ≤ 0, x3 unrestricted

c Dereje T. (MSc.) 81
Linear Optimization March 21, 2023

1. Write the dual of the above linear programming problem.

2. Use the Complementary Slackness theorem to check whether the solution

(x1 , x2 , x3 ) = (0, 0, 2) is optimal or not.

Solution
(a) Dual :

Maximize 2p1 + 5p2 + 5p3

Subject to 6p1 + 3p2 + p3 ≤ 6
−3p1 + 4p2 − 7p3 ≥ 0
p1 + p2 = −5
p1 unrestricted , p2 ≤ 0, p3 ≤ 0

(b) Suppose (x1 , x2 , x3 ) = (0, 0, 2) is an optimal solution. By the strong duality theorem, the dual problem
has an optimal solution (p1 , p2 , p3 ). By the complementary Slackness theorem, both (x1 , x2 , x3 ) = (0, 0, 2)
and (p1 , p2 , p3 ) must satisfy the Complementary Slackness conditions:

p1 (6x1 − 3x2 + x3 − 2) = 0
p2 (3x1 + 4x2 + x3 − 5) = 0 (4.1)
p3 (x1 − 7x2 − 5) = 0 (4.2)
x1 (6p1 + 3p2 + p3 − 6) = 0
x2 (−3p1 + 4p2 − 7p3 − 0) = 0
x3 (p1 + p2 + 5) = 0

since x3 = 2 6= 0, we have (p1 + p2 + 5) = 0. Substituting (x1 , x2 , x3 ) = (0, 0, 2) in to (5.1) and (5.2) gives
p2 = 0, p3 = 0 and p1 = −5. It remains to check that this is dual feasible, which reduces to checking the
first two dual conditions are satisfied.
6p1 + 3p2 + 3p3 = −30 < 0 and −3p1 + 4p2 − 7p3 = 15 > 0, so, p∗ = (−5, 0, 0) is dual feasible. We conclude
that the primal solution (x1 , x2 , x3 ) = (0, 0, 2) is optimal by the complementary slackness theorem.

c Dereje T. (MSc.) 82
 Sensitivity Analysis
5
5.1 Introduction
The scope of a linear programming does not end at finding the optimal solution to the linear model of a
real-life problem. Sensitivity analysis, sometimes referred to as post optimal analysis is an essential part
of the optimization techniques. Sensitivity analysis of linear programming continues with the optimal
solution to provide additional practical insight of the model. Since this analysis examines how sensitive
the optimal solution is to changes in the coefficients of the LP model, it is called sensitivity analysis.
This process is also known as post optimality analysis because it starts after the optimal solution is
found. Since we live in a dynamic world where changes occur constantly, this study of the effects on the
solution due to changes in the data of a problem is very useful.

In general, we are interested in finding the effects of the following changes on the optimal LP solution.

I. Changes in profit/unit or cost coefficients of the objective function .

II. Changes in the availability of resources or capacities of production /service centers or limits on the
demands (requirements vector or RHS of constraints)
III. Changes in resource requirements/ units of products or activities (technological coefficients of vari-
ables) in constraints.
IV. Addition of a new product or activity ( variable)
V. Addition of a new constraint.

Remark 5.1.1. When we incorporate any of the above changes in the original problem, either the
optimal table remains unchanged or the optimality criteria is disturbed or the feasibility is disturbed
or both are disturbed. To restore optimality we shall use the simplex method, while the disturbed
feasibility is restored by using the dual simplex method.

Sensitivity analysis and parametric linear programming are the two techniques that are used to evaluate
the effect on an optimal solution of any LP problem due to changes in its parameters.

• Sensitivity analysis determines the sensitivity range (both lower and upper limit) within which the
LP model parameters can vary (one at a time) without affecting the optimality of the current optional
solution.

83
Linear Optimization March 21, 2023

• Parametric analysis is the study of measuring the effect on the optimal solution of the LP model due
to changes at a time in more than one input parameters value outside the sensitivity range.

However, while sensitivity analysis provides the sensitive ranges (both lower and upper limits) within
which the LP model parameters can vary without changing the optimality of the current optimal solu-
tion; parametric linear programming provides information about changes in parameters value outside the
sensitive range, as well as to changes in more than one parameter at a time.
Thus, aim of sensitivity analysis is to determine the range (or limit) within which the LP model
parameters can change without affecting the current optimal solution. For this, instead of solving an
LP problem again with new values of parameters, the current optimal solution is considered as an initial
solution to determine the ranges, both lower and upper, within which a parameter may assume a value.
The sensitivity analysis will be discussed for linear programs of the form

Maximize z = C T X
subject to AX ≤ b
X≥0

Where X is the column vector of unknowns, C T is the row vector of the corresponding costs(cost vector):
A is the coefficient matrix of the constraints ( matrix of technological coefficients ); and b is the column
of the right hand sides of the constraints (requirements vector).
Example 5.1.

To fix our ideas, the sensitivity analysis will be exemplified through the following numerical problem.

Maximize z = 20x1 + 10x2

subject to x1 + 2x2 ≤ 40
3x1 + 2x2 ≤ 60
with x1 and x2 nonnegative

This program is put into the following standard form by introducing the slack variables.

Maximize z = 20x1 + 10x2 + 0x3 + 0x4

subject to x1 + 2x2 + x3 = 40
3x1 + 2x2 + x4 = 60
with all variables nonnegative

The solution for this problem is summarized as follows

The optimal tableau is given as follows:

C 20 10 0 0
CB XB x1 x2 x3 x4 b(RHS)
0 x3 0 4/3 1 -1/3 20
20 x1 1 2/3 0 1/3 20
Z j − Cj 0 10/3 0 20/3

Since the last row of the above tableau contains no negative elements, the optimal solution is x∗1 =
20, x∗2 = 0 , with Z ∗ = 400.
For clarity of exposition, the five types of modifications are illustrated case by case below .

c Dereje T. (MSc.) 84
Linear Optimization March 21, 2023

5.2 Variation of coefficients of objective function C T

The change in cost of variables has a direct impact on optimal criteria (Zj − Cj -row) which has its entries
as Zj − Cj = CBT B −l aj − Cj . If the optimal criteria is disturbed due to cost change, then use simplex
method to restore optimality which results in a new solution.
The two types of changes are possible:

I. Change in cost of a nonbasic variable. With the change in cost of a nonbasic variables the
relative cost of this variable is changed. Obviously, there is no change in relative cost of any other
variable. If sign of the relative cost is changed then bring this variable into the basis to get the new
optimal solution.
Let the LPP be max Z = C T X , subject to AX = b, X ≥ 0. Suppose xk is a nonbasic variable and
its cost ck is changed to ck + ∆ck , where k ∈ N , the index set of nonbasic variables. The new relative
cost of xk turns up
CBT B −1 ak − (ck + ∆ck ), k ∈ N
Since CBT is fixed and cost of all remaining variables are kept fixed, there will be no change relative
cost of any other variable. The optimal solution remains same if

CBT B −1 ak − (ck + ∆ck ) ≥ 0

otherwise the optimality is disturbed which can be restored by simplex method to find new optimal
solution.
II. Change in cost of a basic variable. With change in the cost of a basic variable all zj − cj will
change except for the basic variables.
Note that CBT B −1 can not be taken from the optimal table as CBT has changed. There will also be a
change in the objective function value.
Let cj the cost of jth basic variable is shifted to cj +∆cj , where j ∈ B, the index set of basic variables.
Then relative cost of each nonbasic variable is changed as

(CBT + ∆cj ej )yk − ck , j ∈ B, k ∈ N

where yk = B −1 ak and ck are the coordinate vector and cost of kth nonbasic variable, respectively.
To stay optimal solution as it is, we must have

CBT yk − ck + ∆cj ykj ≥ 0

This implies

zk −ck
∆cj ≥ −ykj
, for kth nonbasic variable.

Hence, we can define

zk − ck
∆cj = maxk { , ykj > 0, k ∈ N }
−ykj
zk − ck
∆cj = mink { , ykj < 0, k ∈ N }
−ykj
which ensures the variation limits in cost of jth basic variable

∆cj ≤ ∆cj ≤ ∆cj

c Dereje T. (MSc.) 85
Linear Optimization March 21, 2023

If ∆cj goes out of these limits for at least one nonbasic variable, this implies optimality is disturbed.
Calculate fresh objective function value using
(c1 , c2 , . . . , cj + ∆cj , . . . , cm )B −1 b
and apply simplex method to restore optimality which results in new optimal solution.
Example 5.2.

(a) Coefficients of the non basic variable

Let the new value of the cost coefficient corresponding to the non basic variable x2 be 15 instead of [Link]
x2 is nonbasic, then z2 − c02 = z2 − c2 + ∆c2 = 10/3 + 10 − 15 = 10/3 − 5 = −5/3, and all other zj − cj
are unaffected. Hence, x2 enters the basis in the following tableau:

C 20 15 0 0
CB XB x1 x2 x3 x4 b(RHS)
0 x3 0 4/3 1 -1/3 20
20 x1 1 2/3 0 1/3 20
Zj − Cj 0 -5/3 0 20/3

Since (Z2 − C2 ) < 0, the new solution is not optimal. The regular simplex method is used to re-optimize
the problem starting with x2 as the entering variable.
The new optimal tableau is

C 20 15 0 0
CB XB x1 x2 x3 x4 b(RHS)
15 x2 0 1 3/5 -1/4 15
20 x1 1 0 -1/2 1/2 20
Zj − Cj 0 0 5/4 25/4

The optimal solution is x∗1 = 20, x∗2 = 15, with Z ∗ = 425

(b) Coefficients of the basic variable
Let the cost coefficient of the basic variable x1 be changed from 20 to 10,
Then the simplex tableau becomes

C 10 10 0 0
CB XB x1 x2 x3 x4 b(RHS)
0 x3 0 4/3 1 -1/3 20
10 x1 1 2/3 0 1/3 20
Z j − Cj 0 -10/3 0 20/3

Since (Z2 − C2 ) < 0, the new solution is not optimal. The regular simplex method is used to re-
optimize the problem, first by starting entering x2 .
The new optimal tableau is

C 10 10 0 0
CB XB x1 x2 x3 x4 b(RHS)
10 x2 0 1 3/4 -1/4 15
10 x1 1 0 -1/2 1/2 10
Zj − Cj 0 0 5/2 5/2 250

The optimal solution is x∗1 = 10, x∗2 = 15, with Z ∗ = 250.

c Dereje T. (MSc.) 86
Linear Optimization March 21, 2023

5.3 Variation of vector requirement b

In a LPP, if the change in right hand side of the constraints is made then the solution column, B −1 b, and
the objective function value,CBT B −1 b are affected. This change corresponds to two cases.

I If all entries of the new solution column turn out to be nonnegative, then the existing table remains
optimal with the new solution and new optimal value.
Suppose right hand side entry bk of the vector b = (b1 , b2 , . . . , bm )T is shifted to (b1 , b2 , . . . , bk +
∆bk , . . . , bm )T . Then the new solution column is

XB0 = B −1 (bk + ∆bk ek )

where ek = (0, 0, . . . , 1, . . . , 0)T of has 1 at kth position.

Let B −1 = (βik )m×m . The optimal basis remains the same if

XB0 = B −1 bk + ∆bk B −1 ek ≥ 0.
   
β1k 0
 β2k  0
or Xb0 = XB + ∆bk  ..  ≥  .. 
   
 .  .
βmk 0
If B denotes the index set of basic variables, then we have

Xq + ∆bk βik ≥ 0, q ∈ B, i = 1, 2, ..., m (5.1)

Xq
gives ∆bk ≥ −βik
Obviously, we define
Xq
∆bk = M axi { , βik > 0}
−βik
Xq
∆bk = M ini { , βik < 0}
−βik
Thus, if ∆bk satisfies

∆bk ≤ ∆bk ≤ ∆bk

the same basis remains intact.
In this way the same set of basic variable with changed values according to formula (5.1) produce the
new solution and new objective value is CBT XB0 .
II The second possibility is that ∆bk is assigned beyond the above limits. Then at least one of the entry
in new B −1 b is negative,i.e., feasibility is disturbed. Restore the feasibility using the dual simplex
method to get the optimal solution of the revised problem
Example 5.3. Modification of the requirements vector b
 
−1 x3
Let the RHS of the second constraint be changed from 60 to 130. Then XB = B b becomes =
     x1
1 −1/3 40 −10/3
= Since x3 < 0, the new solution is not feasible. The dual simplex
0 1/3 130 130/3
method used to clear the infeasibility starting with the following tableau

c Dereje T. (MSc.) 87
Linear Optimization March 21, 2023

C 20 10 0 0
CB XB x1 x2 x3 x4 b(RHS)
0 x3 0 1.33 1 -0.33 -3.33
20 x1 1 0.67 0 0.33 43.33
zj − cj 0 3.33 0 6.67

The new final tableau is

C 20 10 0 0
CB XB x1 x2 x3 x4 b(RHS)
0 x4 0 -4 -3 1 10
20 x1 1 2 1 0 40
zj − cj 0 30 20 0

The optimal and feasible solution is x∗1 = 40, x∗2 = 0, with Z ∗ = 800

5.4 Variation of constraints(matrix coefficients A)

The problem becomes more complicated, when the technological coefficients of the basic variable are
considered. This is because here matrix under the starting solution changes. In this case, it may be easier
to solve the new problem than resort to the sensitivity analysis approach. Therefore our analysis is limited
to the case of the coefficients of non basic variable only.
Example 5.4. Modification of the matrix coefficients A

Let the technological coefficients of x2 be changed from (2, 2)T to (2, 1)T . Then the new technological
coefficients
 of x2 in the
 optimal
 simplex
 tableau
 of the original problem are given by
1 −1/3 2 5/3
B −1 a2 = =
0 1/3 1 1/3
Hence, the new simplex tableau becomes

C 20 10 0 0
CB XB x1 x2 x3 x4 b(RHS)
0 x3 0 5/3 1 -1/3 20
20 x1 1 1/3 0 1/3 20
zj − cj 0 -10/3 0 20/3

Since (z2 − c2 ) < 0, the new solution is not optimal. Again the regular simplex method is resorted for
re-optimization,
First by entering x2 , The new optimal tableau is

C 20 10 0 0
CB XB x1 x2 x 3 x4 b(RHS)
10 x2 0 1 3/5 -1/5 12
20 x1 1 0 -1/5 2/5 16
zj − cj 0 0 2 6

The optimal solution is x∗1 = 16, x∗2 = 12, with Z ∗ = 440.

c Dereje T. (MSc.) 88
Linear Optimization March 21, 2023

5.5 Addition of a Variables

Addition of a new variable causes addition of some column in the optimal table which may affect the
optimal criteria. Let an extra variable xn+1 with coefficient cn+1 be added in the system of original
constraint Ax = b, x ≥ 0. This in turn creates an extra column an+1 in the matrix A of coefficients. To
see the impact of this addition on the current optimal solution, we compute

yn+1 = B −1 an+1

and
zn+1 − cn+1 = cB yn+1 − cn+1
Two cases of the maximization LP model may arise:

1. If zn+1 − cn+1 ≥ 0, then xn+1 = 0, and hence current solution remains optimal.
2. If zn+1 − cn+1 < 0, then the current optimal solution can be improved upon by the introduction of
a new column an+1 into the basis to find the new optimal solution.
Example 5.5. Addition of a variable

Let a new variable xk be added to the original problem. This is accompanied by the addition to A of a
column ak = (3, 1)T and to C T of a component ck = 30. Thus the new problem becomes

Maximize z = 20x1 + 10x2 + 30xk

Subject to x1 + 2x2 + 3xk ≤ 40
3x1 + 2x2 + xk ≤ 100
With all variables non negative

Then the technological

 coefficients
  of xk  in the optimal tableau are
1 −1/3 3 8/3
B −1 ak = =
0 1/3 1 1/3
The corresponding (zk − ck ) = (8/3)(0) + (1/3)(20) − 30 = −70/3.
Thus the modified simplex tableau is given below

C 20 10 30 0 0
CB XB x1 x2 xk x3 x4 b(RHS)
0 x3 0 4/3 8/3 1 -1/3 20
20 x1 1 2/3 1/3 0 1/3 20
zj − cj 0 10/3 -70/3 0 20

Now entering the variable xk , the regular simplex tableau method is applied to obtain the following
optimal tableau.

C 20 10 30 0 0
CB XB x1 x2 xk x3 x4 b(RHS)
30 xk 0 1/2 1 3/8 -1/8 15/2
20 x1 1 1/2 0 -1/8 3/8 35/2
zj − cj 0 1/5 0 70/8 30/8

The optimal solution is x∗1 = 35/2, x∗k = 15/2, with Z ∗ = 575.

c Dereje T. (MSc.) 89
Linear Optimization March 21, 2023

5.6 Addition of a new constraint

Suppose that a new constraint is added to the problem. As discussed in the section on modifying the A
matrix, this operation is dual to that of adding a new activity. If the given optimal solution to the original
problem satisfies the added constraint, it is then obvious that this point is also an optimal solution of
the new problem (why?). If, on the other hand, this point does not satisfy the new constraint, that is, if
the constraint ”cuts away” the given optimal solution, we can use the dual simplex method to find a new
optimal solution.
If a new constraint added to the system is not active, it is called a secondary or redundant constraint, and
the optimality of the problem remains unchanged. On the other hand, if the new constraint is active, the
current optimal solution becomes infeasible.
If a new constraint is added to a LPP, then we have to make two observations:

(i) Whether the constraint to be added is satisfied by the given optimal solution, then there will be no
effect on adding this constraint;

(ii) If this constraint is not satisfied, then addition will affect the optimal solution. Addition of such a
constraint first will disturb the simplex format. When the simplex format is restored the feasibility
will get disturbed. Restore the feasibility by the dual simplex method to find the new optimal
solution.

Example 5.6. Addition of a constraint

Let us consider the case of the addition of an active constraint, 2x1 +3x2 ≥ 50 to the original problem.
The current optimal solution (x∗1 = 20, x∗2 = 0) does not satisfy the above new constraint and hence The
optimal solution becomes infeasible. Therefore, add the new constraint to the current optimal tableau.
The new slack variable is x5
The simplex tableau

C 20 10 0 0 0
CB XB x1 x2 x3 x4 x4 b(RHS)
0 x3 0 4/3 1 -1/3 0 20
20 x1 1 2/3 0 1/3 0 20
0 x5 -2 -3 0 0 1 -50
zj − cj 0 10/3 0 20/3 0

By using the row operation, the coefficient of x1 in the new constraint is made zero. The modified tableau
becomes

C 20 10 30 0 0
CB XB x1 x2 x3 x4 x5 b(RHS)
0 x3 0 4/3 1 -1/3 0 20
20 x1 1 2/3 0 1/3 0 20
0 x5 0 -5/3 0 2/3 1 -10
zj − cj 0 10/3 0 20/3 0

The dual simplex method is used to overcome the infeasibility by departing the variable x5 , the new
tableau is

c Dereje T. (MSc.) 90
Linear Optimization March 21, 2023

C 20 10 0 0 0
CB XB x1 x2 x3 x4 x5 b(RHS)
0 x3 0 0 1 1/5 4/5 12
20 x1 1 0 0 3/5 2/5 16
10 x2 0 1 0 -2/5 -3/5 6
zj − cj 0 0 0 6 2

The above tableau gives the optimal and feasible solution as x∗1 = 16, x∗2 = 6, x∗3 = 12, with Z ∗ = 380.

Example 5.7.

Suppose that we are given the LPP:

Max x0 = 2x1 + 3x2 + 4x3

Subject to: x1 + 2x2 + 3x3 ≤ 11
2x1 + 3x2 + 2x3 ≤ 10
x1 , x2 , x3 ≥ 0

with its optimal table as:

Cj 2 3 4 0 0
CB BV x1 x2 x3 s1 s2 RHS(b)
4 x3 0 1/4 1 1/2 -1/4 3
2 x1 1 5/4 0 -1/2 3/4 2
Zj 2 7/2 4 1 1/2
Zj − Cj 0 1/2 0 1 1/2

(a) Within what range the cost of xl varies so that the optimality remains unaffected.

(b Within what range the cost of x2 varies so that the optimal solution remains unaffected.

(c) Discuss the effect of changing the costs 2, 3, 4 of the decision variables xl , x2 , x3 to 1, 2, 2 respectively.

Solution: For part (a), there will be a change in relative cost of xl . Note that xl is a basic variable,
and hence, the cost of basis CBT has changed, and C T B −l (simplex multiplier) can not be taken from the
optimal table. Let cost of xl be Cl for which we have to determine the variation. The cost of basis is
(4, Cl )T . For no change in the optimal solution, we must have Zj −Cj = C T B −l Aj −Cj ≥ 0 for all nonbasic
variables. Calculate  
1/4
Z2 − C2 = (4, C1 ) − 3 ≥ 0 ⇒ C1 ≥ 8/5
5/4
 
1/2
Z4 − C4 = (4, C1 ) ≥ 0 ⇒ C1 ≤ 4
−1/2
 
−1/4
Z5 − C5 = (4, C1 ) ≥ 0 ⇒ C1 ≥ 4/3
3/4
The common value of Cl ∈ [8/5, 4] satisfies all the above three inequalities, and this is the range in which
Cl may vary without affecting the optimality.

c Dereje T. (MSc.) 91
Linear Optimization March 21, 2023

For part (b), note that x2 is a nonbasic variable. There is no change in CBT . Hence, take CBT B −l from the
table which is available below starting BFS. Hence,
 
2
Z2 − C2 = (1, 1/2) − C2 ≥ 0 ⇒ C2 ≤ 7/2
3

Thus, for C2 ∈ (−∞, 7/2], there is no change in the optimal solution.

For part (c), we observe that cost of basic and nonbasic variables have changed. We shall not calcu-
late Zj − Cj for all basic variables as these are bound to be zero in every simplex table. With the change
of the objective coefficients from 2, 3, 4 to 1, 2, 2, the new cost of the basis is CBT = (2, 1)T . Calculate new
Zj − Cj for all nonbasic variables as
 
1/4
New Z2 − C2 = (2, 1) − 2 = −1/4
5/4
 
1/2
New Z4 − C4 = (2, 1) − 0 = 1/2
−1/2
 
−1/4
New Z5 − C5 = (2, 1) − 0 = 1/4
3/4
Thus, the optimality is disturbed as the new relative cost of x2 has turned to be negative. Before proceeding
further, calculate  
3
NewZ = (2, 1) = 8.
2
After incorporating these changes in Table above, we have

Cj 1 2 2 0 0
CB BV x1 x2 x3 s1 s2 RHS(b)
2 x3 0 1/4 1 1/2 -1/4 3
1 x1 1 5/4 0 -1/2 3/4 2←
Zj 1 7/4 2 1/2 1/4
Zj − Cj 0 ↑-1/4 0 1/2 1/4

The variable x2 enters (having most negative relative cost) and xl leaves the basis (minimum ratio rule),
see Table above. Table below gives the optimal solution of the changed problem.

Cj 1 2 2 0 0
CB BV x1 x2 x3 s1 s2 RHS(b)
2 x3 -1/5 0 1 3/5 -2/5 13/5
2 x2 4/5 1 0 -2/5 3/5 8/5
Zj 6/5 2 2 2/5 2/5 42/5
Zj − Cj 1/5 0 0 2/5 2/5

The optimal solution: xl = 0, x2 = 8/5, x3 = 13/5, optimal value Z ∗ = 42/5

c Dereje T. (MSc.) 92
Linear Optimization March 21, 2023

Summary of Sensitivity Analysis (Max Problem)

Change in Effect on Current Basis Is

Initial Problem Optimal Tableau Still Optimal If:
Changing nonbasic objective Coefficient of xj in optimal Coefficient of xj in row 0 for
function coefficient cj row 0 is changed current basis is still nonnegative
Changing basic objective Entire row 0 may change Each variable still has a
function coefficient cj nonnegative coefficient in
row 0
Changing right-hand side of Right-hand side of Right-hand side of each
a constraint constraints and row 0 are constraint is still nonnegative
changed
Changing the column of Changes the coefficient for The coefficient of xj in row
a nonbasic variable xj or xj in row 0 and xj ’s 0 is still nonnegative
adding a new variable xj constraint column in
optimal tableau
* Row 0 = Zj − Cj

c Dereje T. (MSc.) 93
Linear Optimization March 21, 2023

Exercise 1.

1. Consider the following linear program

min z = 2xl + x2 − x3
s.t. xl + 2x2 + x3 ≤ 8
−xl + x2 − 2x3 ≤ 4
xl , x2 , x3 ≥ 0

Then use sensitivity analysis to answer the following questions.

(a) Find a new optimal solution if the cost coefficient of x1 is changed from 2 to 6.
(b) Find a new optimal solution if the coefficient of x2 in the first constraint is changed from 2 to
1/4.
(c) Find a new optimal solution if we add one more constraint X2 + X3 = 3.
(d) If you were to choose between increasing the right-side of the first and second constraints, which
one would you prefer? Why? What is the effect of this increase on the optimal solution of the
objective function.
(e) Suppose that a new activity x4 is proposed with a unit cost of 4 and consumption vector a4 =
(1, 2)T . Find the corresponding optimal solution.

2. Solve the LPP

max z = 2xl + 3x2

s.t. xl − x2 ≥ 21
3xl + 2x2 ≤ 5
xl , x2 ≥ 0

Use the optimal table of the above LPP and then apply the sensitivity analysis to solve

max z 0 = 2xl + 3x2 + x3

s.t. xl − x2 + x3 ≥ 1
3xl + 2x2 ≥ 5
xl + x2 + x 3 = 3
xl , x2 ≥ 0

3. Consider the following problem.

Max Z = 3x1 + x2 + 4x3 ,

s.t 6x1 + 3x2 + 5x3 ≤ 25
3x1 + 4x2 + 5x3 ≤ 20
x1 , x2 , x3 ≥ 0.

You are now to conduct sensitivity analysis by independently investigating each of the following six
changes in the original model. For each change,use the sensitivity analysis procedure to revise the
given final set of equations (in tableau form) and convert it to proper form from Gaussian elimination.
Then test this solution for feasibility and for optimality. (Do not reoptimize.)

(a) Change the right-hand side of constraint 1 to b1 = 15.

c Dereje T. (MSc.) 94
Linear Optimization March 21, 2023

(b) Change the right-hand side of constraint 2 to b2 = 5.

(c) Change the coefficient of x2 in the objective function to c2 = 4.
(d) Change the coefficient of x3 in the objective function to c3 = 3.
(e) Change the coefficient of x2 in constraint 2 to a22 = 1.
(f) Change the coefficient of x1 in constraint 1 to a11 = 10.

4. Consider the linear programming problem

Minimize Z = −x1 + x2 + 3x3

Subject to −x1 + x2 + x3 ≥ 3
x1 + 2x2 + x3 ≤ 10
x1 , x2 , x3 ≥ 0, then

(a) Find the optimal solution of the given LPP

(b) What will be the optimal solution of the given LPP
[Link] the objective function of the non basic variable x1 is changed from -1 to -3.
[Link] the RHS of the second constraint be changed from 10 to 50.
[Link] the technological coefficients of x2 be changed from (1, 2)T to (2, 2)T .
iv. If a new variable xk be added to the original problem. This is accompanied by the addition
to A of a column Bk = (3, 1)T and to C T of a component ck = 6.
v. If the constraint 2x1 + 3x2 + 4x3 ≥ 8 added to the original problem.

c Dereje T. (MSc.) 95
 Transportation Problem
6
6.1 Introduction
The basic transportation problem was developed in 1941 by F.I. Hitchaxic, however, it could be solved for
optimality as an answer to complex business problem only in 1951, when George B. Dantzing applied the
concept of linear programming in solving the transportation problems.
Transportation problem are primarily concerned with the optimal (best possible) way in which a product
produce at different factories or plants (called supply origins) can be transported to a number of ware-
houses (called demand destinations).
Transportation is a special kind of linear programming problem in which goods are transported from a
set of sources to a set of destinations subject to the supply and demand of the source and destination
respectively, such that the total cost of transportation is minimized.

The objective in a transportation problem is :- to fully satisfy the destination requirements with in the op-
erating production capacity constraints at the minimum possible [Link] the is a physical movement
of goods from the point of manufacture to find consumers through a variety of chances of distribution(whole
sellers, retailers, distributors etc.), there is a need to minimize the cost of transportation so as to increase
the profit on sales. Transportation problems arise in all such cases. its aim at providing assistance to the
top management in ascertaining how many units of a particular product should be transported from each
supply origin to each demand destinations to that the total prevailing demand for the company’s product
is satisfied, while at the same time the total transportation costs are minimized, that is the total supply
available at the plants exactly matches the total demand at the destinations. Hence, there is neither excess
supply nor excess [Link] type of problem where supply and demand are exactly equal are known
as Balanced Transportation problem.
Supply (from various sources) are written in the rows, while a column is an expression for the demand of
different warehouses. In general, if a transportation problem has m rows an n columns, then the problem
is solvable if there are exactly (m + n –1) basic variables.

Transportation Problem
The transportation problem seeks to minimize the total shipping costs of transporting goods from m ori-
gins or sources (each with a supply si ) to n destinations (each with a demand dj ), when the unit shipping
cost from source, i, to a destination, j, is cij .
A typical transportation problem contains
Inputs:
•Sources with availability
• Destinations with requirements

96
Linear Optimization March 21, 2023

• Unit cost of transportation from various sources to destinations

Objective:
• To determine schedule of transportation to minimize total transportation cost.
Simple Network Representation

6.2 LP Formulation Transportation Problem

In general, if there be m sources and n destinations with ai availability in ith source , bj requirement in j th
destination, cij is the cost of transportation from ith source to j th destination and xij the amount shipped
from origin i to destination j, then a transportation problem seeks to determine non-negative values of xij
, so as to
Pm Pn
Pxn 0 = i=i j=1 cij xij
Minimize (total transportation cost)
subject toP j=1 xij ≤ ai , for i = 1, 2, ..., m (Supply constraint)
m
i=1 xij ≥ bj , for j = 1, 2, ..., n (Demand constraint)
xij ≥ 0, for all i and j (nonnegativity constraints)

If m
P Pn
i=1 ai = j=1 bj the LPP is a balanced transportation problem, otherwise it is unbalanced. From the
above LPP, it is obvious that there are m + n constraints and mn decision variables. However, it can be
verified that out of these only m + n - 1 constraints are linearly independent, i.e., the rank of coefficient
matrix is m + n - 1. This is what follows in the next theorem.
Every transportation problem can be represented by a matrix of order m by n, called the cost matrix or
effectiveness matrix. A transportation tableau is given below. Each cell represents a shipping route (which
is an arc on the network and a decision variable in the LP formulation).

c Dereje T. (MSc.) 97
Linear Optimization March 21, 2023

To/From D1 D2 . . . Dn ai (Availability)
S1 C11 C12 . . . C1n a1
S2 C21 C22 . . . C2n a2
. . . . . .
. . . . . .
. . . . . .
Sn Cm1 Cm2 . . . Cmn Pm am P
n
bj (Requirements) b1 b2 . . . bn i=1 ai = j=1 bj

Theorem 6.2.1. In a balanced transportation problem with m sources and n destinations, only m+n-1
constraints are linearly independent.

Proof. The set of constraints of a balanced transportation with m sources and n destinations are given by
n
X
xij = ai , i = 1, 2, . . . m(row constraints) (6.1)
j=1
Xm
xij = bi , j = 1, 2, . . . n(column constraints) (6.2)
i=1

To show that m + n - 1 constraints are linearly independent, it is sufficient to verify that anyone of the m
+ n constraints can be written as linear combination of the others.
Add all the row constraints and n - 1 column constraints to have
Xm X n m
X
xij = ai (6.3)
i=1 j=1 i=1

n−1 X
X m n−1
X
xij = bj (6.4)
j=1 i=1 j=1

Subtracting (6.3) from (6.4), we get

m X
X n n−1 X
X m m
X n−1
X
xij − xij = ai − bj
i=1 j=1 j=1 i=1 i=1 j=1
Xm Xn m
X
= ai − bj + xin
i=1 j=1 i=1
Xm
= xin (balanced TP)
i=1

Thus, nth column constraint has been written as the difference of the sum of all row constraints and sum
of n - 1 column constraints, as asserted. This proves the theorem.

Remark: As a consequence of the theorem the LPP generated by a transportation model with m
sources and n destinations will have m + n - 1 basic variables and remaining (m - 1) (n - 1) nonbasic
variables. Thus, a balanced transportation with m sources and n destinations will have at most
 
mn (mn)!
=
m+n−1 (m + n − 1)!(mn − m − n + 1)!

basic feasible solutions.

c Dereje T. (MSc.) 98
Linear Optimization March 21, 2023

The transportation problem always has a finite minimum feasible solution and an optimal solution contains
m + n - 1 positive x0ij s when there are m origins and n destinations. It is degenerate if less than m + n -
1 of the x0ij s are positive.
Existence of feasible solution A necessary and sufficient condition for a feasible solution to the
transportation problems is:

Total supply = Total demand

Xm n
X
ai = bj (also called rim conditions)
i=1 j=1

Example 6.1.

A company has three production facilities S1 , S2 and S3 with production capacity of 7, 9 and 18 units
(in 100s) per week of a product, respectively. These units are to be shipped to four warehouses D1 , D2 , D3
and D4 with requirement of 5, 6, 7 and 14 units (in 100s) per week, respectively. The transportation costs
(in ETB) per unit between factories to warehouses are given in the table below:

D1 D2 D3 D4 Supply
S1 19 30 50 10 7
S2 70 30 40 60 9
S3 40 8 70 20 18
Demand 5 8 7 14 34

Formulate this transportation problem as an LP model to minimize the total transportation cost.
Model formulation Let xij = number of units of the product to be transported from a production facil-
ity i (i = 1, 2, 3) to a warehouse j ( j = 1, 2, 3, 4). The transportation problem is stated as an LP model
as follows:
Minimize Z = 19x11 + 30x12 + 50x13 + 10x14 + 70x21 + 30x22 + 40x23 + 60x24 + 40x31 + 8x32 + 70x33 + 20x34
subject to the constraints

x11 + x12 + x13 + x14 = 17

x21 + x22 + x23 + x24 = 19 (Supply)
x31 + x32 + x33 + x34 = 18
x11 + x21 + x31 = 15
x12 + x22 + x32 = 18
(Demand)
x13 + x23 + x33 = 17
x14 + x24 + x34 = 14

and xij ≥ 0 for i = 1, 2, 3 and j = 1, 2, 3, and 4.

In the above LP model, there are m × n = 3 × 4 = 12 decision variables, xij and m + n = 7 constraints,
where m are the number of rows and n are the number of columns in a general transportation table.

6.3 Determination of an initial basic feasible solution

Basic feasible solution: A feasible solution transportation problem in which allocations 0 x0ij
of a m × nP
are provided satisfying the conditions j=1 xij = ai and m
Pn
i=1 xij = bj for each i and j is said to be a basic

c Dereje T. (MSc.) 99
Linear Optimization March 21, 2023

feasible solution.
When transportation method is employed in solving a transportation problem, the very initial step that
has to be undertaken is to obtain a feasible solution satisfying demand and supply requirement. Several
methods will be used in this section to obtain this initial feasible problem. An initial basic feasible solution
to a transportation problem can be found by any one of the following methods.

1. North West Corner Method (Rule)

2. Least Cost Method or Matrix Minima method

3. Row / Column Minima Method

4. Vogel’s Approximation Method (VAM)

6.3.1 North West Corner Method(NWCM)

This is a method used to compute feasible solution of a transportation problem. In this method, the basic
variables are usually chosen from the top left corner commonly referred to as the Northwest corner. The
following steps are followed to obtain this feasible solution

1. P
Balance thePtransportation problem if not originally by adding a dummy source or destination making
m n
i=1 ai = j=1 bj with zero transportation cost in added cells.

2. Start with the cell in the upper left hand corner which is north west corner (1,1) and allocate the
maximum possible amount xij = M in(ai , bj ) in the cell (i, j), such that either the availability of the
source is exhausted or the requirement at destination Dj is satisfied or both.

(a) If b1 < a1 , if the amount required at b1 is less than the number of units available at a1 ,
set x11 = b1 , find the balance supply and demand and proceed to cell(1,2)(i.e., proceed to
horizontally).
(b) If b1 = a1 , set x11 = b1 , compute the balance supply and demand and proceed to cell(2,2)(i.e.,
proceed diagonally).
(c) If b1 > a1 , set x11 = a1 , compute the balance supply and demand and proceed to cell(2,1)(i.e.,
proceed vertically).

3. Continue in this manner, step by step, away from the north-west corner until, finally a value is
reached in the south-east corner(all the available quantity is exhausted).

Note:

i) If both a row and column are satisfied (i.e., say x11 = a1 = b1 ) simultaneously, then cross out either
row or column only but not both row and column.

ii) Cells from “crossed out” row or column can not be chosen for basis cells at a later step in the
determination of starting basic solution.

Remark. This method is independent of the cost distribution in the transportation table. Due to
this reasoning the north-west corner rule is least preferred to other methods to be discussed very
shortly for finding initial basic feasible solution of a transportation problem.

c Dereje T. (MSc.) 100

Linear Optimization March 21, 2023

Example 6.2. Use North-West Corner Method (NWCM) to find an initial basic feasible solution to the
transportation problem using data of Example 6.1.
P P
Solution: Since ai = bj = 34 the problem is a balanced TP. Hence, there exists a feasible solution.
The cell (S1 , D1 ) is the north-west corner cell in the given transportation table. The rim values for row S1
and column D1 are compared. The smaller of the two, i.e. 5, is assigned as the first allocation; otherwise
it will violate the feasibility condition. This means that 5 units of a commodity are to be transported from
source S1 to destination D1 . However, this allocation leaves a supply of 7 - 5 = 2 units of commodity at
S1 .
Move horizontally and allocate as much as possible to cell (S1 , D2 ). The rim value for row S1 is 2 and
for column D2 is 8. The smaller of the two, i.e. 2, is placed in the cell. Proceeding to row S2 , since the
demand of D1 is fulfilled. The unfulfilled demand of D2 is now 8 - 2 = 6 units. This can be fulfilled by S2
with capacity of 9 units. So 6 units are allocated to cell (S2 , D2 ). The demand of D2 is now satisfied and
a balance of 9 - 6 = 3 units remains with S2 .

D1 D2 D3 D4 Supply
S1 19 5 30 2 50 10 7
S2 70 30 6 40 3 60 9
S3 40 8 70 4 20 14 18
Demand 5 8 7 14 34

Continue to move horizontally and vertically in the same manner to make desired allocations. Once
the procedure is over, count the number of positive allocations. These allocations (occupied cells) should
be equal to m + n - l = 3 + 4 - l = 6. If yes, then solution is non-degenerate feasible solution. Otherwise
degenerate solution.
The total transportation cost of the initial solution is obtained by multiplying the quantity xij in the
occupied cells with the corresponding unit cost cij and adding all the values together. Thus, the total
transportation cost of this solution is
Total cost = 5 × 19 + 2 × 30 + 6 × 30 + 3 × 40 + 4 × 70 + 14 × 20 = 1, 015

6.3.2 Least cost method or Matrix minima method(LCM)

When least cost as a method is used to compute a basic feasible solution in a transportation problem,
choosing basic variables is usually done as the unit cost of transportation. To obtain this feasible solution,
the following steps have to be considered and followed:

1. P
Balance thePtransportation problem if not originally by adding a dummy source or destination making
m n
i=1 ai = j=1 bj with zero transportation cost in added cells.

2. Choose the cell with lowest cost and allocate the maximum feasible amount xij = M in(ai , bj ) in
the cell (i, j), such that either the availability of the source Si is exhausted or the requirement at
destination Dj is satisfied or both. If such cell of lowest cost is not unique, select the least cost cell
where we allocate more amount.
3. Adjust supply and demand across the row and column in which allocation xij has been made.
4. Repeat the process until all the available quantity is exhausted.

c Dereje T. (MSc.) 101

Linear Optimization March 21, 2023

Example 6.3. Use Least Cost Method (LCM) to find initial basic feasible solution to the transportation
problem using data of Example 6.1
P P
Solution: Since ai = bj = 34 the problem is a balanced TP. Hence, there exists a feasible solution.
The cell with lowest unit cost (i.e., 8) is (S3 , D2 ). The maximum units which can be allocated to this cell
is 8. This meets the complete demand of D2 and leave l0 units with S3 , as shown in Table below.
In the reduced table without column D2 , the next smallest unit transportation cost, is 10 in cell
(S1 , D4 ). The maximum which can be allocated to this cell is 7. This exhausts the capacity of S1 and
leaves 7 units with D4 as unsatisfied demand. This is shown in Table below.

D1 D2 D3 D4 Supply
S1 19 30 50 10 7 7
S2 70 30 40 60 9
S3 40 8 8 70 20 18
Demand 5 8 7 14 34

In Table above, the next smallest cost is 20 in cell (S3 , D4 ). The maximum units that can be allocated
to this cell is 7 units. This satisfies the entire demand of D4 and leaves 3 units with S3 , as the remaining
supply, shown in Table below.
In Table below, the next smallest unit cost cell is not unique. That is, there are two cells – (S2 , D3 )
and (S3 , D1 ) – that have the same unit transportation cost of 40. Allocate 7 units in cell (S2 , D3 ) first
because it can accommodate more units as compared to cell (S3 , D1 ). Then allocate 3 units (only supply
left with S3 ) to cell (S3 , D1 ). The remaining demand of 2 units of D1 is fulfilled from S2 . Since supply
and demand at each supply centre and demand centre is exhausted, the initial solution is arrived at, and
is shown in Table below.

D1 D2 D3 D4 Supply
S1 19 30 50 10 7 7
S2 70 2 30 40 7 60 9
S3 40 3 8 8 70 20 7 18
Demand 5 8 7 14 34

The total transportation cost of the initial solution by LCM is calculated as given below:
Total cost = 7 × 10 + 2 × 70 + 7 × 40 + 3 × 40 + 8 × 8 + 7 × 20 = 814
The total transportation cost obtained by LCM is less than the cost obtained by NWCM.

6.3.3 Row / Column Minima method

1. P
Balance thePtransportation problem if not originally by adding a dummy source or destination making
m n
i=1 ai = j=1 bj with zero transportation cost in added cells.

2. Select the smallest cost in the first row/ column of the transportation table and allocate the maximum
feasible amount xij = M in(ai , bj ) in the cell (i, j), such that either the availability of the source Si
is exhausted or the requirement at destination Dj is satisfied or both. In case of tie among the cost
, select arbitrarily. Three cases arise

c Dereje T. (MSc.) 102

Linear Optimization March 21, 2023

(a) If the capacity of the first plant/distribution center is completely exhausted/satisfied, cross off
the first row/column and proceed to the second row/column.
(b) If the requirement/capacity at jth distribution center/plant is satisfied/exhausted, cross off the
jth column/row and reconsider the first row/column with the remaining capacity/requirement.
(c) If the capacity/requirement of the first plant/distribution center as well as the requirement/-
capacity at the jth distribution center/plant are completely satisfied, cross off the row/column
as well as the jth column/row and move down(right) to the second row/column.

3. Continue the process for the resulting reduced transportation table until all the rim condition (supply
and requirement conditions) are satisfied.

Example 6.4. Use Row Minima Method (RMM) to find the initial basic feasible solution to the trans-
portation problem using the data of Example 6.1.
P P
Solution: Since ai = bj = 34 the problem is a balanced TP. Hence, there exists a feasible solution.
We first allocate to cell (1,4) in the first rowas it contains the minimum cost 10. We allocate min(7,14)=7
in this cell. This exhausts the supply capacity of plant 1 and thus the first row is crossed off.

D1 D2 D3 D4 Supply
S1 19 30 50 10 7 7
S2 70 30 40 60 9
S3 40 8 70 20 18
Demand 5 8 7 14 34

The next allocation , in the resulting reduced table is made in cell (2,2) of row 2 as it contains the minimum
cost 30 in that row. We allocate min(9,8)=8 in this cell. This exhausts the requirement condition of D2
and thus the second column is crossed off.

D1 D2 D3 D4 Supply
S1 19 30 50 10 7 7
S2 70 30 8 40 60 9
S3 40 8 70 20 18
Demand 5 8 7 14 34

The next allocation , in the resulting reduced table is made in cell (2,3) of row 2 as it contains the
minimum cost 40 in that row. We allocate min(1,7)=1 in this cell. This exhausts the supply capacity of
plant 2 and thus the second row is crossed off.

D1 D2 D3 D4 Supply
S1 19 30 50 10 7 7
S2 70 30 8 40 1 60 9
S3 40 8 70 20 18
Demand 5 8 7 14 34

The next allocation , in the resulting reduced table is made in cell (3,4) of row 3 as it contains
the minimum cost 20 in that row. We allocate min(18,7)=7 in this cell. This exhausts the requirement
condition of D4 and thus the fourth column is crossed off.

c Dereje T. (MSc.) 103

Linear Optimization March 21, 2023

D1 D2 D3 D4 Supply
S1 19 30 50 10 7 7
S2 70 30 8 40 1 60 9
S3 40 8 70 20 7 18
Demand 5 8 7 14 34

The next allocation , in the resulting reduced table is made in cell (3,1) of row 3 as it contains the
minimum cost 40 in that row. We allocate min(11,5)=5 in this [Link] exhausts the requirement condition
of D1 and thus the first column is crossed off.

D1 D2 D3 D4 Supply
S1 19 30 50 10 7 7
S2 70 30 8 40 1 60 9
S3 40 5 8 70 20 7 18
Demand 5 8 7 14 34

The next allocation , in the resulting reduced table is made in cell (3,3) of row 3 as it contains the
minimum cost 70 in that row. We allocate min(6,6)=6 in this [Link] exhausts the requirement condition
of D3 and thus the third column is crossed off. Thus, all rim conditions are met with. the resulting table
is shown below.

D1 D2 D3 D4 Supply
S1 19 30 50 10 7 7
S2 70 30 8 40 1 60 9
S3 40 5 8 70 6 20 7 18
Demand 5 8 7 14 34

The total transportation cost associated with this method is:

Total cost = 7 × 10 + 8 × 30 + 1 × 40 + 7 × 20 + 5 × 40 + 6 × 70 = 1, 110

Activity 2. Use Column Minima Method (CMM) to find the initial basic feasible solution to the trans-
portation problem using the data of Example 6.1.

6.3.4 Vogel’s approximation method (VAM)

This method tends to repeat procedures to compute a basic feasible solution of the transportation problem.
However, some steps have to be followed while carrying out such computations. These include:

1. P
Balance thePtransportation problem if not originally by adding a dummy source or destination making
m n
i=1 ai = j=1 bj with zero transportation cost in added cells.

2. For each row and column of the transportation table, write the difference between smallest and
the next to smallest cost below each column and on the right of the corresponding row. These
differences are known as [Link] difference indicates the penalty or extra cost that has to be
paid if decision-maker fails to allocate to the cell with the minimum unit transportation cost.

c Dereje T. (MSc.) 104

Linear Optimization March 21, 2023

3. Row or column having largest penalty is identified and the minimum cost cell in that particular row
or column is allocated with the largest possible amount xij = M in(ai , bj ) in the cell (i, j), such that
either the availability of the source Si is exhausted or the requirement at destination Dj is satisfied
or both.

4. Adjust supply and demand across the row and column in which allocation xij has been made. If a
row and a column are satisfied simultaneously, only one of them is crossed out and the remaining
row (column) is assigned a zero supply (demand). Any row or column with zero supply or demand
should not be used in computing future penalties.

5. Re-compute the row and column penalties for the reduced transportation table and make the allo-
cations.

6. Repeat the procedure until all the requirements are satisfied.

Rules for tie. In case of tie for largest penalty choose the lowest cost cell in all tied rows and
columns for allocation. Again, if there is a tie for the lowest cost cell, select one for allocation which
gives minimum Cij Xij.

• Transportation cost using VAM is not unique due to arbitrary choosing of penalties in case of tie.

• VAM determines an initial basic feasible solution which is very close to the optimum solution.

Example 6.5. Use Vogel’s Approximation Method (VAM) to find the initial basic feasible solution to the
transportation problem using the data of Example 6.1.
P P
Solution: Since ai = bj = 34 the problem is a balanced TP. Hence, there exists a feasible solution.
The differences (penalty costs) for each row and column have been calculated as shown in Table below.
In the first round, the maximum penalty, 22 occurs in column D2 . Thus the cell (S3 , D2 ) having the least
transportation cost is chosen for allocation. The maximum possible allocation in this cell is 8 units and it
satisfies demand in column D2 . Adjust the supply of S3 from 18 to 10 (18 - 8 = 10).

D1 D2 D3 D4 Supply Row Difference

S1 19 5 30 50 10 2 7 9 9 40 40
S2 70 30 40 7 60 2 9 10 20 20 20
S3 40 8 8 70 20 10 18 12 20 50 -
Demand 5 8 7 14 34
Column 21 22 10 10
differences 21 - 10 10
– – 10 10
– – 10 50

The new row and column penalties are calculated except column D2 because D2 ’s demand has been
satisfied. In the second round, the largest penalty, 21 appears at column D1 . Thus the cell (S1 , D1 ) having
the least transportation cost is chosen for allocating 5 units as shown in Table above. After adjusting the
supply and demand in the table, we move to the third round of penalty calculations.
In the third round, the maximum penalty 50 appears at row S3 . The maximum possible allocation of
10 units is made in cell (S3 , D4 ) that has the least transportation cost of 20 as shown in Table above.

c Dereje T. (MSc.) 105

Linear Optimization March 21, 2023

The process is continued with new allocations till a complete solution is obtained. The initial solution
using VAM is shown in Table above. The total transportation cost associated with this method is:
Total cost = 5 × 19 + 2 × 10 + 7 × 40 + 2 × 60 + 8 × 8 + 10 × 20 = 779

Remark:

1. The necessary and sufficient condition for a transportation problem with m sources, ai avail-
ability at ith source; and with n destinations, bj requirement at jth destination to have initial
basic feasible solution is that m n
X X
ai = bi .
i=1 j=1

2. A balanced transportation problem has always an optimal solution.

Exercise 2.

1. Obtain an initial basic feasible solution to the following transportation problem by Using

(a) North West Corner rule (c) Least Cost method

(b) Row Minima method (d) Vogel Approximation method

Destination
Origin 1 2 3 4 Supply
1 20 22 17 4 120
2 24 37 9 7 70
3 32 37 20 15 50
Demand 60 40 30 110

2. The ICARE company has three plants located thought a state with production capacity 50, 75 and
25 gallons. Each day firm must furnish its four retail shops R1 , R2 , R3 and R4 with at least 20, 20,
50 and 60 gallons respectively. The transformation costs (in Rs.) are given below.

Retail shop
Factory 1 2 3 4 Supply
1 3 5 7 6 50
2 2 5 8 2 75
3 3 6 9 2 25
Demand 20 20 50 60

The economic problem is to distributed the available product to different retail shops in such a way
that the total transportation cost is minimum?
3. A dairy firm has three plants located in a country. The daily milk production at each plant is as
follows:

Plant 1 : 6 million litres, Plant 2 : 1 million litres, and Plant 3 : 10 million litres

Each day, the firm must fulfil the needs of its four distribution centres. The minimum requirement
of each centre is as follows:

c Dereje T. (MSc.) 106

Linear Optimization March 21, 2023

Distribution centre 1 : 7 million litres, Distribution centre 2 : 5 million litres,

Distribution centre 3 : 3 million litres, and Distribution centre 4 : 2 million litres

Cost (in hundreds of ETB) of shipping one million litre from each plant to each distribution centre
is given in the following table:

Distribution Centre
Plants D1 D2 D3 D4
P1 2 3 11 7
P2 1 0 6 1
P3 5 8 15 9

Find the initial basic feasible solution for given problem by using following methods:

(a) North-west corner rule (c) Column minimum method

(b) Least cost method (d) Vogel’s approximation method

6.4 Optimality conditions

Once an initial basic feasible solution is obtained, the next step is to check its optimality. An optimal
solution is one where there is no other set of transportation route(allocation) that will further reduce the
total transportation cost. In this section we will discussed Modified Distribution Method(MODI) that
provide optimal solutions to the transportation problem.

6.4.1 Modified Distribution Method (MODI)

The modified distribution method, also known as MODI method or (u - v) method provides a minimum
cost solution to the transportation problem. The following are the steps involved in this method.
Steps

1. Find out the basic feasible solution of the transportation problem using any one of the four methods
discussed in the previous section.

2. Introduce dual variables corresponding to the row constraints and the column constraints. If there are
m origins and n destinations then there will be m+n dual variables. The dual variables corresponding
to the row constraints are represented by ui , i=1,2,. . . ..m where as the dual variables corresponding
to the column constraints are represented by vj , j=1,2,. . . ..n. The values of the dual variables are
calculated from the equation given below

ui + vj = cij if xij > 0

To start with, we assign a number ‘0’ to any row of column having maximum number of allocations.
If this maximum number of allocations is more than one, choose any one arbitrarily.

3. For unoccupied cells, calculate the opportunity cost by using the relationship

∆ij = cij − (ui + vj ), for all i and j.

4. Examine sign of each ∆ij

c Dereje T. (MSc.) 107

Linear Optimization March 21, 2023

(a) If ∆ij > 0, then the current basic feasible solution is optimal.
(b) If ∆ij = 0, then the current basic feasible solution will remain unaffected but an alternative
solution exists.
(c) If one or more ∆ij < 0, then an improved solution can be obtained by entering an unoccupied
cell (i, j) into the solution mix (basis). An unoccupied cell having the largest negative value of
∆ij is chosen for entering into the solution mix (new transportation schedule).

5. Construct a closed-path (or loop) for the unoccupied cell with largest negative value of ∆ij . Start
the closed path with the selected unoccupied cell and mark a plus sign (+) in this cell. Trace a path
along the rows (or columns) to an occupied cell, mark the corner with a minus sign (-) and continue
down the column (or row) to an occupied cell. Then mark the corner with plus sign (+) and minus
sign (-) alternatively. Close the path back to the selected unoccupied cell.

6. Select the smallest quantity amongst the cells marked with minus sign on the corners of closed loop.
Allocate this value to the selected unoccupied cell, add it to occupied cells marked with plus signs,
and subtract it from the occupied cells marked with minus signs.

7. Obtain a new improved solution by allocating units to the unoccupied cell according to Step 5 and
calculate the new total transportation cost.

8. Test optimality of the revised solution. The procedure terminates when all ∆ij ≥ 0 for unoccupied
cells.

Remark 6.4.1.

1. The closed-loop (path) starts and ends at the selected unoccupied cell. It consists of successive
horizontal and vertical (connected) lines whose end points must be occupied cells, except an end
point associated with entering unoccupied cell. This means that every corner element of the loop
must be an occupied cell.
It is immaterial whether the loop is traced in a clockwise or anti-clockwise direction and whether it
starts up, down, right or left (but never diagonally). However, for a given solution only one loop can
be constructed for each unoccupied cell.

2. There can only be one plus (+) sign and only one minus (–) sign in any given row or column.

3. The closed path indicates changes involved in reallocating the shipments.

Example 6.6.

Find the optimum transportation schedule and minimum total cost of transportation.

D1 D2 D3 ai
S1 10 7 8 45
S2 15 12 9 15
S3 7 8 12 40
bj 25 55 20

Solution: Since 3i=1 ai = 3j=1 bj = 100. So the given transportation problem is balanced. To find
P P
initial basic feasible solution, we apply VAM method. In this method we are to find the difference between
two least elements in each row and column.

c Dereje T. (MSc.) 108

Linear Optimization March 21, 2023

D1 D2 D3 ai Penalties
S1 10 7 40 8 5 45 1 1 1
S2 15 12 9 15 15 3 3 3
S3 7 25 8 15 12 40 1 4 -
bj 25 55 20
3 1 1
Penalties
- 1 1
- 5 1

We first take the least element cell (3,1) lies on the highest difference column where the demand is 25
units and capacity is 40 units. We choose x31 = 25, the min of these two, to convert into it basic cell, and
demand is exhausted, Neglecting that column. We again find the difference and applying the same method
to get all initial basic feasible solution. The solutions are x12 = 40, x13 = 5, x23 = 15, x31 = 25, x32 = 15.
Here the number of solutions =5= (m+n-1) = (3+3-1). This implies, the solution is non-degenerate
solution.
Optimality test:
To find the optimal solution we are applying u-v method.

D1 D2 D3 ai Penalties
S1 10 7 40 8 5 45 1 1 1
S2 15 12 9 15 15 3 3 3
S3 7 25 8 15 12 40 1 4 -
bj 25 55 20
3 1 1
Penalties

- 1 1
- 5 1

In this method we first take the basic cell (i, j) where Cij = ui + vj we choose u3 = 0,Then for the cell
(3,2) we are applying
C32 = u3 + v2 ⇒ 8 = 0 + v2 , ⇒ v2 = 8, we can use the same manner for the remaining dual variables
C31 = u3 + v1 ⇒ 7 = 0 + v1 ⇒ v1 = 7
C12 = u1 + v2 ⇒ 7 = u1 + 8 ⇒ u1 = −1
C13 = u1 + v3 ⇒ 8 = −1 + v3 ⇒ v3 = 9
C23 = u2 + v3 ⇒ 9 = u2 + 9 ⇒ u2 = 0
Next compute the opportunity cost using ∆ij = Cij − (ui + vj ) for non -basic cell (i, j)
∆11 = C11 − (u1 + v1 ) ⇒ ∆11 = 10 − (−1 + 7) ⇒ ∆11 = 4
∆21 = C21 − (u2 + v1 ) ⇒ ∆21 = 15 − (0 + 7) ⇒ ∆21 = 8
∆22 = C22 − (u2 + v2 ) ⇒ ∆22 = 12 − (0 + 8) ⇒ ∆22 = 4
∆33 = C33 − (u3 + v3 ) ⇒ ∆33 = 12 − (0 + 9) ⇒ ∆33 = 3
All ∆ij ≥ 0, therefore the given Basic feasible solution is an optimal solution.
The minimum cost of transportation = 40(7) + 5(8) + 25(7) + 15(9) + 15(8) = 750 units.
Exercise 3.

Consider a transportation problem with three sources(rows) and four demand points(columns). The
availability in the supply points are 40,50 and 60 respectively and the requirements are 20,30,30,and 50
respectively. Table below shows the unit cost of transportation.

c Dereje T. (MSc.) 109

Linear Optimization March 21, 2023

D1 D2 D3 D4 Supply
S1 4 6 8 8 40
S2 6 8 6 7 60
S3 5 7 6 8 50
Demand 20 30 50 50 150

Find the optimum transportation schedule and minimum total cost of transportation.

6.5 Unbalanced transportation problems and their solutions

In the previous section we discussed about the balanced transportation problem i.e. the total supply
(capacity) at the origins is equal to the total demand (requirement) at the destination. In this section we
are going to discuss about the unbalanced transportation problems i.e. when the total supply is not equal
to the total demand.
A transportation problem is unbalanced if Psum of supplies from different sources is not equal to sum
m Pn
of requirements in various destination. that is i=1 ai 6= j=1 bj .
To deal with an unbalanced transportation problem to obtain its BFS or the optimal solution, we first
convert this into a balanced transportation problem as follows:
Pm Pn
i If i=1 a i > j=1 bj , add a dummy destination

ii If m
P Pn
i=1 ai < j=1 bj , add a dummy source

The supply or demand at the dummy origin is equal to the symmetric difference of total supply and total
demand.
In the unbalanced transportation problem if the total supply is more than the total demand then we
introduce an additional column which will indicate the surplus supply with transportation cost zero. Simi-
larly, if the total demand is more than the total supply an additional row is introduced in the transportation
table which indicates unsatisfied demand with zero transportation cost.
Let us solve an unbalanced transportation problem as our next example.

Example 6.7.

Solve the following transportation problem, where goods are to be transported from 3 factories to 3
warehouses. Cost of transportation is given in terms of 100$ and quantity in tons.

D1 D2 D3 ai ↓
S1 2 3 3 3
S2 3 4 4 4
S3 1 5 1 5
bj → 3 4 3

Solution : Here 3i=1 ai = 12,

P P3
j=1 bj = 10, the problem is unbalanced.
Adding a dummy destination with demand 2 tons and zero transportation cost to make the problem is
balanced.

c Dereje T. (MSc.) 110

Linear Optimization March 21, 2023

D1 D2 D3 D4 ai ↓
S1 2 3 3 0 3
S2 3 4 4 0 4
S3 1 5 1 0 5
bj → 3 4 3 2

Now solving the given transportation problem by VAM in a single table by calculating Penalties and
for each row and column and assigning maximum a mount in minimum cost cell to row/column with
maximum penalty in each row.

D1 D2 D3 D4 ai ↓ Penalties
S1 2 3 3 3 0 3 2 1 1 1
S2 3 4 1 4 1 0 2 4 3 1 1 1
S3 1 3 5 1 2 0 5 1 4 4 -
bj → 3 4 3 2
1 1 2 0
Penalties

1 1 2 -
1 1 -
1 1 -

The initial basic feasible solution becomes x12 = 3, x22 = 1, x23 = 1, x34 = 2, x31 = 3, x33 = 2.
Transportation cost = 3(3) + 4(1) + 4(1) + 0(2) + 1(3) + 1(2) = 2200$
Now we can solve as balanced problem discussed as in the previous sections to find the optimal solution
of the TP.

Exercise 4.

1. Solve the following transportation problem, where goods are to be transported from 3 plants to 3
warehouses.

Plants w1 w2 w3 Supply
X 20 17 25 400
Y 10 10 20 500
Demand 400 400 500

2. A company has facilities at cities A, B and C which supply warehouses at cities D, E and F. The
monthly factory capacities are 50, 150 and 200 units, respectively. The monthly requirements are
100, 130 and 200 units, respectively. The shipping cost per unit are given in the following table.

D E F
A 2 1 4
B 3 1 2
C 5 6 7

a) Formulate the LP model for this problem.

b) Also, write dual of the above problem.
c) Use the VAM to get the starting BFS.
d) Find the optimal solution.

c Dereje T. (MSc.) 111

Linear Optimization March 21, 2023

e) Does there exist an alternative optimal solution? If it exists, then find it.
f) Is the optimal solution degenerate? If it exists, write why? Otherwise give reasons for its absence.
g) If the penalties per unit cost for the unsatisfied demand are 5, 2, 1 for the cities D, E and F, then
find the optimal solution.

6.6 Degenerate transportation problems and their solutions

In a transportation problem, if a basic feasible solution with m origins and n destinations has less than
m+ n -1 positive xij i.e. occupied cells, then the problem is said to be a degenerate transportation
problem. The degeneracy problem does not cause any serious difficulty, but it can cause computational
problem while determining the optimal minimum solution. Degeneracy can occur in the initial solution or
during some subsequent iteration.
While finding the initial basic feasible solution by any method, if a row and column are satisfied simul-
taneously (except the last allocation), we get a degenerate basic feasible solution. To get the degenerate
BFS anyone of these is assumed to be satisfied and put ’0’ for the unsatisfied. The following example (see
Table below) worked out by LCM will make the context clear.

D1 D2 D3 D4 Supply
S1 2 20 3 7 30 1 50
S2 4 1 50 5 0 8 50
S3 3 4 7 20 1 60 80
Demand 20 50 50 60 180

The degenerate BFS and cost of transportation are

x11 = 20, x13 = 30, x22 = 50, x23 = 0, x33 = 20, x34 = 60; Z = 500.

Therefore it is important to identify a degenerate problem as early as beginning and take the necessary
action to avoid any computational difficulty. The degeneracy can be identified through the following
results:
“In a transportation problem, a degenerate basic feasible solution exists if and only if some partial sum
of supply (row) is equal to a partial sum of demand (column). For example the following transportation
problem is degenerate. Because in this problem

a1 = 400 = b1
a2 + a3 = 900 = b2 + b3

w1 w3 w3 supply(ai
X 20 17 25 400
Y 10 10 20 500
Unsatisfied demand 0 0 0 400
demand(bj ) 400 400 500 1300

To resolve this degeneracy, we adopt the following steps.

c Dereje T. (MSc.) 112

Linear Optimization March 21, 2023

1. Among the empty cell, we choose an empty cell having the least cost which is of an independent
position. If this cell is more than one, choose any one arbitrarily.

2. To the cell as chosen in step (1) we allocate a small positive quantity  > 0.

The cells containing  are treated like other occupied cells and degeneracy is removed by adding one
(more) accordingly. For this modified solution, we adopt the steps involved in MODI method(Stepping
stone method) till an optimum solution is obtained.

Example 6.8. A company has three plants A, B and C, 3 warehouses X, Y, Z. The number of units
available at the plants is 60, 70, 80 and the demand at X, Y, Z are 50, 80, 80 respectively. The unit cost
of the transportation is given in the following table.

X Y Z
A 8 7 3
B 3 8 9
C 11 3 5

Find the allocation so that the total transportation cost is minimum.

Solution: The transportation table is given by:

X Y Z supply
A 8 7 3 60
B 3 8 9 70
C 11 3 5 80
Demand 50 80 80 210
P P
Since ai = bj = 210 the problem is a balanced one. Hence, there exists a feasible solution. Let us
find the initial solution by least cost method.

X Y Z supply
A 8 7 3 60
B 3 50 8 9 70
C 11 3 5 80
Demand 50 80 80 210

Here, the least cost cell is not unique, i.e., the cells (2, 1) (1, 3) and (3, 2) have the least value 3. So
choose the cell arbitrarily. Let us choose the cell (2, 1) and allocate with magnitude min. (70, 50) = 50.
This exhausts the first column. The reduced transportation table is given by

X Y Z supply
A 8 7 3 60 60
B 3 50 8 9 20 70
C 11 3 80 5 80
Demand 50 80 80 210

Continuing in this manner, we finally arrive at the initial solution which is shown in the following table:

c Dereje T. (MSc.) 113

Linear Optimization March 21, 2023

X Y Z supply
A 8 7 3 60 60
B 3 50 8 9 20 70
C 11 3 80 5 80
Demand 50 80 80 210

The number of allocated cells is 4 ¡ m + n - 1 = 5, resulting in degeneracy (Initial stage). To remove this
degeneracy we add an empty cell (3, 3) whose cost is minimum and is of independent position. Allocate
to this cell a small quantity  > 0. Hence, we have the initial solution given in the following table

X Y Z supply
A 8 7 3 60 60
B 3 50 8 9 20 70
C 11 3 80 5  80
Demand 50 80 80 210

The total number of occupied cells = 5 = m + n - 1 =5. These are also of independent position. This
solution is [Link] solution is given by
x13 = 60, x21 = 50, x23 = 20, x32 = 80, x33 = 
The total transportation cost = 3 × 60 + 3 × 50 + 9 × 20 + 3 × 80 + 5 ×  = 750 + 5 ×  = 750
To find the optimal solution We apply the steps involved in the MODI method to the previous
table. We find a set of numbers ui and vj for which ui + vj = cij is satisfied for each of the occupied cell.
To start with we assign a number 0 to the third column (i.e., v3 = 0) as it has the maximum number of
allocations. The remaining numbers are obtained as follows.

X Y Z supply ui
A 8 7 3 60 60 3
B 3 50 8 9 20 70 9
C 11 3 80 5  80 5
Demand 50 80 80 210
vj -6 -2 0

Since all ∆ij = ui + vj − cij > 0 for all nonbasic variables we have obtained an optimum solution. The
solution is given by
x13 = 60, x21 = 50, x23 = 20, x32 = 80, x33 = 
The total transportation cost = 3 × 60 + 3 × 50 + 9 × 20 + 3 × 80 + 5 ×  = 750 + 5 ×  = 750.
Exercise 5.

1. Solve the following transportation problem whose cost matrix is given below.

Destinations
A B C D Capacity
1 1 5 3 3 34
2 3 3 1 2 15
Origin 3 0 2 2 3 12
4 2 7 2 4 19
Demand 21 25 17 17 80

c Dereje T. (MSc.) 114

Linear Optimization March 21, 2023

2. A company has four warehouses and six stores. The warehouses altogether have a surplus 22 units
of a given commodity, divided among them as follows:

Warehouses: 1 2 3 4
Surplus 5 6 2 9

The six stores altogether need 22 units of the commodity. Individual requirements at stores 1,2,3,4,5,
and 6 are 4,4,6,2,4 and 2 units respectively.
Cost of shipping one unit of commodity from warehouse i to store j in ETB is given in the table
below

stores
1 2 3 4 5 6
1 9 12 9 6 9 10
2 7 3 7 7 5 5
warehouses 3 6 5 9 11 3 11
4 6 8 11 2 2 10

(a) Formulate the mathematical model for the problem.

(b) How should the products be shipped from the warehouses to the stores so that the transportation
cost is minimum?

Explain the degeneracy in transportation techniques in the context of this problem. How is degen-
eracy resolved?

6.7 Direct Solution Method of Transportation Problem(Optional)

In this section, we deal for finding an optimal solution directly. Here a much easier heuristic approach
ASM-Method is used for finding an optimal solution directly with lesser number of iterations and very
easy computations. The stepwise procedure of ASM-method is carried out as follows.

Step 1: Construct the transportation table from given transportation problem.

Step 2: Subtract each row entries of the transportation table from the respective row minimum and then
subtract each column entries of the resulting transportation table from respective column minimum.

Step 3: Now there will be at least one zero in each row and in each column in the reduced cost matrix.
Select the first zero (row-wise) occurring in the cost matrix. Suppose (i, j)th zero is selected, count
the total number of zeros (excluding the selected one) in the ith row and j th column. Now select
the next zero and count the total number of zeros in the corresponding row and column in the same
manner. Continue it for all zeros in the cost matrix.

Step 4: Now choose a zero for which the number of zeros counted in step 3 is minimum and supply
maximum possible amount to that cell. If tie occurs for some zeros in step 3 then choose a (k, l)th
zero breaking tie such that the total sum of all the elements in the k th row and lth column is maximum.
Allocate maximum possible amount to that cell.

Step 5: After performing step 4, delete the row or column for further calculation where the supply from
a given source is depleted or the demand for a given destination is satisfied.

c Dereje T. (MSc.) 115

Linear Optimization March 21, 2023

Step 6: Check whether the resultant matrix possesses at least one zero in each row and in each column.
If not,repeat step 2, otherwise goto step 7.

Step 7: Repeat step 3 to step 6 until and unless all the demands are satisfied and all the supplies are
exhausted.

Example 6.9. Consider the following cost minimizing transportation problem with three origins and four
destinations.

D1 D2 D3 D4 Supply
S1 13 18 30 8 8
S2 55 20 25 40 10
S3 30 6 50 10 11
Demand 4 7 6 12 29 (Total)

Solution: By applying ASM-Method allocations are obtained as follows:

D1 D2 D3 D4 Supply
S1 13 4 18 30 8 4 8
S2 55 20 4 25 6 40 10
S3 30 6 3 50 10 8 11
Demand 4 7 6 12 29 (Total)

The total cost associated with these allocations is 412.

c Dereje T. (MSc.) 116

 Review Exercise
7
1. Use Gaussian elimination to solve the following system linear equations.

2x2 + x3 = −8
x1 − 2x2 − 3x3 = 0
−x1 + x2 + 2x3 = 3

2. Consider the problem : Minimize cx subject to Ax ≥ b, x ≥ 0. Suppose that one component of the
vectors b, say bi , is increase by one unit to bi + 1

(a) What happens to the feasible region?

(b) What happens to the optimal solution?

3. Which of the following sets are convex and which are not?

(a) {(x1 , x2 ) : x21 + x22 ≤ 1}.

(b) {x : Ax = b}: where A is an m × n matrix and b is m-vector.
(c) {x : Ax ≤ b, x ≥ 0}, where A is an m × n matrix and b is m-vectors.
     
1 1 −1
(d) {x : x = λ1  0  + λ2  2  + λ3  2  , λ1 + λ2 + λ3 = 1, λ1 , λ2 , λ3 ≥ 0}
0 1 3
(e) {(x1 , x2 ) : x1 + 2x2 ≤ 1, x1 − 2x2 ≤ 2}
(f) {(x1 , x2 ) : −x2 − 3x1 = 0}
(g) {(x1 , x2 , x3 ) : x2 ≥ x21 , x1 + 2x2 + x3 ≤ 4}
(h) {(x1 , x2 ) : 0 ≤ x21 + x22 ≤ 4}

4. Formulate the following Linear programming problem

(a) The Top Speed Bicycle Co. manufactures and markets a line of 10-speed bicycles nationwide.
The firm has final assembly plants in two cities in which labor costs are low, New Orleans and
Omaha. Its three major warehouses are located near the larger market areas of New York,
Chicago, and Los Angeles. The sales requirements for next year at the New York warehouse
are 10000 bicycles, at the Chicago warehouse 8000 bicycles, and at the Los Angeles warehouse

117
Linear Optimization March 21, 2023

15000 bicycles. The factory capacity at each location is limited. New Orleans can assemble
and ship 20000 bicycles; the Omaha plant can produce 15000 bicycles per year. The cost of
shipping one bicycle from each factory to each warehouse differs, and these unit shipping costs
are:
New York Chicago Los Angeles
New Orleans $2 3 5
Omaha 3 1 4
The company wishes to develop a shipping schedule that will minimize its total annual trans-
portation cost.
(b) A machine component requires a drill machine operation followed by welding and assembly into
a larger subassembly. Two versions of the component are produced: one for ordinary service
and other for heavy-duty operation. A single unit of the ordinary design requires 10 min of drill
machine time, 5 min of seam welding, and 15 min for assembly. The profit for each unit is $100.
Each heavy-duty unit requires 5 min of screw machine time, 15 min for welding and 5 min for
assembly. The profit for each unit is $150. The total capacity of the machine shop is 1500 min;
that of the welding shop is 1000 min; that of assembly is 2000 min. What is the optimum mix
between ordinary service and heavy-duty components to maximize the total profit?

5. Solve the following linear programming problems(LPP) by using graphical method.

(a) Maximize Z = 3x1 + 2x2

Subject to x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 8
x1 , x2 ≥ 0
(b) Maximize Z = 3x1 + 5x2
Subject to x1 ≤ 4
x1 , x2 ≥ 0
(c) Minimize Z = 5x1 + 2x2
Subject to 2x1 + 5x2 ≥ 1
4x1 − x2 ≥ 12
x 1 + x2 ≥ 4
x1 , x2 ≥ 0
(d) Maximize Z = 5x1 + 2x2
Subject to 4x1 + 3x2 ≤ 12
2x1 + x2 ≥ 12
x1 , x2 ≥ 0

6. Show that C is a convex Cone if and only if x and y ∈ C imply that λx + µy ∈ C for all λ ≥ 0 and
µ≥0

7. Find all extreme points of the following polyhedral sets: X = {(x1 , x2 , x3 ) : x1 −x2 +x3 ≤ 1, x1 −2x2 ≤
4, x2 , x3 ≥ 0}. Does X have any recession direction? why?

8. Without sketching the feasible region find the vertices of for the system
−x1 + x2 ≤ 1
2x1 + x2 ≤ 2
x1 , x2 ≥ 0

c Dereje T. (MSc.) 118

Linear Optimization March 21, 2023

9. The system Ax = b, x ≥ 0 is given by

x1 + x2 − 8x3 + 3x4 = 2
−x1 + x2 + x3 − 2x4 = 2, then find

(a) a nonbasic feasible solution.

(b) a basic solution which is not feasible.

10. If S1 and S2 are convex sets in Rn , then the set S1 ± S2 = {x1 + x2 : x1 ∈ S1 , x2 ∈ S2 } is convex.

11. Find the convex hull of the following sets

(a) {(1, 1), (1, 2), (2, 0), (0, −1)}

(b) {(x1 , x2 ), x21 + x22 = 1}
(c) {(x1 , x2 ), x21 + x22 > 4}
(d) {(0, 0), (1, 0), (0, 1), (1, 1)}

12. Using algebraic method solve the given LPP.

(a) Minimize −x1 − 3x2 (b) Minimize −x1 − 3x2

subject to x1 − 2x2 ≤ 4 subject to 2x1 + 3x2 ≤ 6
−x1 + x2 ≤ 3 −x1 + x2 ≤ 1
x1 , x2 ≥ 0 x1 , x2 ≥ 0∆

13. Use the simplex method to solve the following linear programming problem.

(a) Maximize z = 3x1 + 5x2 + 4x3 3x1 + 2x2 ≤ 24

Subject to 2x1 + 3x2 ≤ 8 x1 + x2 ≥ 3 , x1 , x2 ≥ 0
2x2 + 5x3 ≤ 10
3x1 + 2x2 + 4x3 ≤ 15 (d) Minimize z = x1 + x2 − 4x3
x1 , x2 , x3 ≥ 0 Subject to x1 + x2 + 2x3 ≤ 9
x1 + x2 − x3 ≤ 2
(b) Maximize z = 4x1 + 3x2
−x1 + x2 + x3 ≤ 4
Subject to 2x1 + x2 ≤ 1000
x1 , x2 , x3 ≥ 0
x1 + 5x2 ≤ 400
x2 ≤ 700 (e) Maximize Z = 6x1 + 4x2
x1 , x2 , x3 ≥ 0 Subject to x1 + x2 ≤ 5
(c) Maximize z = 6x1 + 4x2 x2 ≤ 8
Subject to 2x1 + 3x2 ≤ 30 x1 , x2 ≥ 0

14. Avoiding big M-method or two phase method find the optimal solution of the following LPP by
simplex method

max z = xl + x2 + x3 + x4 + x5
s.t. 3x1 + 2x2 + x3 = 1
5x1 + x2 + x3 + x4 = 2
2x1 + 5x2 + x3 + x5 = 4
xl , x2 , x3 , x4 , x5 ≥ 0

15. Solve the following linear programming problems by using the two-phase simplex method

c Dereje T. (MSc.) 119

Linear Optimization March 21, 2023

(a) Minimize −3x1 + 4x2 (c) Minimize Z = x1 − 2x2 − 3x1

subject to x1 + x2 ≤ 4 Subject to −2x1 + 3x2 + 3x3 = 2
2x1 + 3x2 ≥ 18 2x1 + 3x2 + 4x3 = 1
x1 , x2 ≥ 0∆ x1 , x2 , x3 ≥ 0
(b) Minimize Z = x1 + x2 (d) max z = 4xl + x2
Subject to 2x1 + 4x2 ≥ 4 [Link] − x2 ≤ 1
x1 + 7x2 ≥ 7 −2xl + x2 ≤ 2
x1 , x2 ≥ 0 xl , x2 ≥ 0.

16. Use the penalty (Big-M) Method to solve the following linear programming problems

(a) Minimize Z = 5x1 + 3x2 (c) Maximize z = 3x1 + 2x2 + x3

Subject to 2x − 1 + 4x2 ≤ 2 Subject to 2x1 + 5x2 + x3 = 128
2x1 + 2x2 = 10 3x1 + 4x2 = 10
5x1 + 2x2 ≥ 10 x2 , x3 ≥ 0,
x1 , x2 ≥ 0 x1 unrestricted
(b) Maximize Z = x1 + 2x2 + 3x3 − x4
Subject to x1 + 2x2 + 3x3 = 15 (d) Minimize −x1 − x2
2x1 + x2 + 5x3 = 20 subject to x1 − x2 ≥ 1
x1 + 2x2 + x3 + x4 = 10 −x1 + x2 ≥ 1
x1 , x2 , x3 , x4 ≥ 0 x1 , x2 ≥ 0.

17. Solve the following linear program by both the two-phase method and the big-M method:

Minimize −x1 − 2x2 + x3

subject to X1 + 2x2 + x3 ≥ 4
2x1 − x3 ≥ 3
x2 + x3 ≤ 2
x1 , x2 , x3 ≥ 0.

18. A trucking company owns three types of trucks: type I, type II, and type III. These trucks are
equipped to haul three different types of machines per load according to the following chart:

TRUCK TYPE
I II II
Machine A 1 1 1
Machine B 0 1 2
Machine C 2 1 1

Trucks of type I, II, and III cost $500, $600, and $1000 per trip, [Link] are interested in
finding how many trucks of each type should be sent to haul 12 machines of type A, 10 machines of
type B, and 16 machines of type C. Formulate the problem and then solve it by the simplex method.
(This is an integer programming problem; you may ignore the integrality requirements.)

19. Determine the dual of the following primal linear programming problems

(a) Maximize Zx = 2x1 + 5x2 + 6x3 x1 − 5x2 + 3x3 ≤ 1

Subject to 5x1 + 6x2 − x3 ≤ 3 −3x1 − 3x2 + 7x3 ≤ 6
−2x1 + x2 + 4x3 ≤ 4 x1 , x2 , x3 ≥ 0

c Dereje T. (MSc.) 120

Linear Optimization March 21, 2023

(b) Maximize Zx = 2x1 + 3x2 + x3 x1 , x2 ≥ 0 and x3 is unrestricted

Subject to 4x1 + 3x2 + x3 = 6 (e) Minimize Z = 3x1 + x2 + 0x3 + 0x4 + M x5 +
x1 + 2x2 + 5x3 = 4 M x6
x1 , x2 , x3 ≥ 0 Subject to x1 + x2 − x3 + +x5 = 7
(c) Maximize Zx = 8x1 + 3x2 2x1 + 3x2 − x4 + x6 = 8
Subject to x1 − 6x2 ≥ 2 with all variables non-negative
5x1 + 7x2 = −4 (f) Maximize Z = 4x1 + 6x2 + 3x3
x1 , x2 ≥ 0 Subject to x1 + 2x2 + 3x3 ≤ 6
(d) Minimize Zx = 2x1 + 3x2 + 4x3 4x1 + 3x2 + x3 ≤ 8
Subject to 2x1 + 3x2 + 5x3 ≥ 2 2x1 − 3x2 + 5x3 ≤ 12
3x1 + x2 + 7x3 = 3 with all variables are unre-
x1 + 4x2 + 6x3 ≤ 5 stricted

20. Solve the following linear programming problems by using dual simplex method

(a) Minimize Z = 80u1 + 100u2 + 75u3 x1 + 2x2 ≥ 4

Subject to 4u1 + 2u2 + 5u3 ≥ 12 x1 , x2 ≥ 0
2u1 + 3u2 + u3 ≥ 8 (d) Maximize Z = −4x1 − 3x2
u1 , u2 , u3 ≥ 0 Subject to x1 + x2 ≥ 2
(b) Minimize Z = 3x1 + x2 x1 + 2x2 ≥ 8
Subject to x1 + x2 ≥ 1 x1 , x2 ≥ 0
2x1 + 3x2 ≥ 8 (e) Maximize Z = 5x1 + x2 + 3x3 + 2x4
x1 , x2 ≥ 0 Subject to 2x1 + 3x2 + 6x3 + x4 ≥ 6
(c) Minimize Z = 5x1 + 2x2 6x1 + 3x2 + 5x3 + 3x4 ≥ 8
Subject to 6x1 + x2 ≥ 6 3x1 + 6x2 + x3 + 3x4 ≥ 4
4x1 + 3x2 ≥ 12 x1 , x2 , x3 , x4 ≥ 0

21. Prove that if X is any feasible solution to the linear program Z = M in{C T X : AX ≥ B, X ≥ 0}
and if W is any feasible solution to the linear program Z = M ax{B T W : AT W ≤ C, W ≥ 0},
then C T X ≥ B T W .

c Dereje T. (MSc.) 121

 References

1. Bazaraa, M. S., Jarvis, J. J., and Sherali, H. D. (2011). Linear programming and network flows.
John Wiley and Sons.

2. Hamdy Taha(2007). Operations Research: an introduction 8th edition.

3. J K SHARMA(2017). Operations Research Theory and Applications 6th Edition

4. Bertsimas, D. and Tsitsiklis, J. N. (1997). Introduction to linear optimization (Vol. 6, pp. 479-
530).Belmont, MA: Athena Scientific.

5. Chvatal, V., & Chvatal, V. (1983). Linear programming. Macmillan.

6. Kapoor, V. K. (2006). Operations research: techniques for management. Sultan Chand.

7. Metei, A. J., & Jain, V. (2019). Optimization Using Linear Programming. Stylus Publishing, LLC.

8. Padberg, M. (2013). Linear optimization and extensions (Vol. 12). Springer Science & Business
Media.

9. Vanderbei, R. J. (2015). Linear programming. Heidelberg: Springer.

10. Winston, W. L., & Goldberg, J. B. (2004). Operations research: applications and algorithms (Vol.
3).Belmont: Thomson Brooks/Cole.

122