OPERATIONS RESEARCH
Chapter 1
Linear Programming Problem
Prof. Bibhas C. Giri
Department of Mathematics
Jadavpur University
Kolkata, India
Email:
, 1.0 Introduction
Linear programming (LP) is a popular tool for solving optimization problems of spe-
cial kind. In 1947, George Bernard Dantzig developed an efficient method, the simplex
algorithm, for solving linear programming problem (LPP). Since the development of
the simplex algorithm, LP has been used to solve optimization problems in industries
as diverse as banking, education, forestry, petroleum, manufacturing, and trucking.
The most common problem in these industries involves allocation of limited resources
among competing activities in the best possible (optimal) way. Real world situations
where LP can be applied are thus diverse, ranging from the allocation of production
facilities to products to the allocation of national resources to domestic needs, from
portfolio selection to the selection of shipping patterns, and so on. In this unit, we
will discuss the mathematical formulation of LPP, the graphical method for solving
two-variable LPP, and simplex algorithm, duality, dual simplex and revised simplex
methods for solving LPP of any number of variables.
Chapter 1
Linear Programming Problem
Prof. Bibhas C. Giri
Department of Mathematics
Jadavpur University
Kolkata, India
Email:
, 1.0 Introduction
Linear programming (LP) is a popular tool for solving optimization problems of spe-
cial kind. In 1947, George Bernard Dantzig developed an efficient method, the simplex
algorithm, for solving linear programming problem (LPP). Since the development of
the simplex algorithm, LP has been used to solve optimization problems in industries
as diverse as banking, education, forestry, petroleum, manufacturing, and trucking.
The most common problem in these industries involves allocation of limited resources
among competing activities in the best possible (optimal) way. Real world situations
where LP can be applied are thus diverse, ranging from the allocation of production
facilities to products to the allocation of national resources to domestic needs, from
portfolio selection to the selection of shipping patterns, and so on. In this unit, we
will discuss the mathematical formulation of LPP, the graphical method for solving
two-variable LPP, and simplex algorithm, duality, dual simplex and revised simplex
methods for solving LPP of any number of variables.
