UNIT – 2

Linear programing
Linear Programming (LP) are decision-making. For a manufacturing process,
a production manager has to take decisions as to what quantities and which
process
or processes are to be used so that the cost is minimum and profit is maximum.
Currently, this method is used in solving a wide range of practical business
problems.
The word ‘Linear’ means that the relationships are represented by straight lines.
The word ‘Programming’ means following a method for taking decisions
systematically. Linear programming problem may be solved using a simplified
version of the simplex technique called transportation method. A linear
programming
is a mathematical method for determining method to achieve the best outcome,
i.e., maximum profit at lowest cost. Graphical methods with a mathematical
basis
in operation research included diagram techniques, chart techniques, plot
techniques, and other forms of visualization.

Meaning of Linear Programming

Linear Programming (LP) is a major innovation since World War II in the field
of business decision-making, particularly under conditions of certainty. The
word ‘Linear’ means that the relationships are represented by straight lines,
i.e., the relationships are of the form y = a + bx and the word ‘Programming’
means taking decisions systematically. Thus, LP is a decision-making technique
under given constraints on the assumption that the relationships amongst the
variables representing different phenomena happen to be linear. In fact, Dantzig
originally called it ‘programming of interdependent activities in a linear
structure’
but later shortened it to ‘Linear Programming’. LP is generally used in solving
maximization (sales or profit maximization) or minimization (cost
minimization)
problems subject to certain assumptions. Putting in a formal way, ‘Linear
Programming is the maximization (or minimization) of a linear function of
variables subject to a constraint of linear inequalities.’ Hence, LP is a
mathematical technique designed to assist the organization in optimally
allocating
its available resources under conditions of certainty in problems of scheduling,
product-mix and so on.
Fields Where Linear Programming can be Used
(i) Agricultural applications: LP can be applied in farm management
problems as it relates to the allocation of resources such as acreage,
labour, water supply or working capital in such a way that is maximizes
net revenue.
(ii) Contract awards: Evaluation of tenders by recourse to LP guarantees
that the awards are made in the cheapest way.
(iii) Industrial applications: Applications of LP in business and industry
are of most diverse kind. Transportation problems concerning cost
minimization can be solved by this technique. The technique can also
be adopted in solving the problems of production (product-mix) and
inventory control.
Thus, LP is the most widely used technique of decision-making in business and
industry in modern times in various fields as stated above.

Basic Concepts and Notations

There are certain basic concepts and notations to be first understood for easy
adoption of the LP technique. A brief mention of such concepts is as follows:
1. Linearity: The term linearity implies straight line or proportional
relationships
among the relevant variables. Linearity in economic theory is known as
constant returns which means that if the amount of input doubles, the
corresponding output and profit are also doubled. Linearity assumption,
thus, implies that if two machines and two workers can produce twice as
much as one machine and one worker; four machines and four workers
twice as much as two machines and two workers, and so on.
2. Process and its Level: Process means the combination of particular inputs
to produce a particular output. In a process, factors of production are used
in fixed ratios, of course, depending upon technology and as such no
substitution is possible with a process. There may be many processes open
to a firm for producing a commodity and one process can be substituted for
another. There is, thus, no interference of one process with another when
two or more processes are used simultaneously. If a product can be produced
in two different ways, then there are two different processes (or activities
or decision variables) for the purpose of a linear programme.
3. Criterion Function: Criterion function is also known as objective function
which states the determinants of the quantity either to be maximized or to
be minimized. For example, revenue or profit is such a function when it is to
be maximized or cost is such a function when the problem is to minimize it.
An objective function should include all the possible activities with the revenue
(profit) or cost coefficients per unit of production or acquisition. The goal
may be either to maximize this function or to minimize this function. In
symbolic form, let ZX denote the value of the objective function at the X
level of the activities included in it. This is the total sum of individual activities
produced at a specified level. The activities are denoted as j =1, 2,..., n.
The revenue or cost coefficient of the jth activity is represented by Cj.
Thus, 2X1, implies that X units of activity j = 1 yields a profit (or loss) of C1
= 2.
4. Constraints or Inequalities: These are the limitations under which one
has to plan and decide, i.e., restrictions imposed upon decision variables.
For example, a certain machine requires one worker to be operated upon;
another machine requires at least four workers (i.e., > 4); there are at most
20 machine hours (i.e., < 20) available; the weight of the product should be
say 10 lbs and so on, are all examples of constraints or why are known as
inequalities. Inequalities like X > C (reads X is greater than C or X < C
(reads X is less than C) are termed as strict inequalities. The constraints
may be in form of weak inequalities like X C (reads X is less than or equal
to C) or X C (reads C is greater than or equal to C). Constraints may be
in the form of strict equalities like X = C (reads X is equal to C).
Let bi denote the quantity b of resource i available for use in various
production processes. The coefficient attached to resource i is the quantity
of resource i required for the production of one unit of product j.
5. Feasible Solutions: Feasible solutions are all those possible solutions which
can be worked upon under given constraints. The region comprising of all
feasible solutions is referred as Feasible Region.
6. Optimum Solution: Optimum solution is the best of the feasible solutions

Applications of Linear Programming

Linear programming problems are associated with the efficient use of allocation
of
limited resources to meet desired objectives. A solution required to solve the
linear
programming problem is termed as optimal solution. The linear programming
problems contain a very special subclass and depend on mathematical model or
description. It is evaluated using relationships and are termed as straight-line or
linear. The following are the applications of linear programming:
Transportation problem
Diet problem
Matrix games
Portfolio optimization
Crew scheduling
Linear programming problem may be solved using a simplified version of the
simplex
technique called transportation method. Because of its major application in
solving
problems involving several product sources and several destinations of
products,
this type of problem is frequently called the transportation problem. It gets its
name from its application to problems involving transporting products from
several
sources to several destinations. The formation is used to represent more general
assignment and scheduling problems as well as transportation and distribution
problems. The two common objectives of such problems are:
To minimize the cost of shipping m units to n destinations.
To maximize the profit of shipping m units to n destinations.
The goal of the diet problem is to find the cheapest combination of foods
that will satisfy all the daily nutritional requirements of a person. The problem
is
formulated as a linear program where the objective is to minimize cost and meet
constraints which require that nutritional needs be satisfied. The constraints are
used to regulate the number of calories and amounts of vitamins, minerals, fats,
sodium and cholesterol in the diet.
Game method is used to turn a matrix game into a linear programming
problem. It is based on the Min-Max theorem which suggests that each player
determines the choice of strategies on the basis of a probability distribution over
the player’s list of strategies.
The portfolio optimization template calculates the optimal capital of
investments that gives the highest return for the least risk. The unique design of
the
portfolio optimization technique helps in financial investments or business
portfolios.
The optimization analysis is applied to a portfolio of businesses to represent a
desired and beneficial framework for driving capital allocation, investment and
divestment decisions.
Crew scheduling is an important application of linear programming problem.
It helps if any airline has a problem related to a large potential crew schedules
variables. Crew scheduling models are a key to airline competitive cost
advantage
these days because crew costs are the second largest flying cost after fuel costs.

Limitations of Linear Programming Problems

Linear programming is applicable if constraints and objective functions are
linear,
but there are some limitations of this technique which are as follows:
All the uncertain factors, such as weather conditions, growth rate of industry,
etc., are not taken into consideration.
Integer values are not taken as the solution, e.g., a value is required for
fraction and the nearest integer is not taken for the optimal solution.
Linear programming technique gives those practical-valued answers that
are really not desirable with respect to linear programming problem.
It deals with one single objective in real life problem which is more limited
and the problems come with multi-objective.
In linear programming, coefficients and parameters are assumed as constants
but in realty they do not take place.
Blending is a frequently encountered problem in linear programming. For
example, if different commodities are purchased which have different
characteristics and costs, then the problem helps to decide how much of
each commodity would be purchased and blended within specified bound
so that the total purchase cost is minimized.

GRAPHICAL SOLUTION METHOD

A linear programming is a mathematical method for determining method to
achieve
the best outcome, i.e., maximum profit at lowest cost.
2.5.1 Graphic Solution
The procedure for mathematical formulation of an LPP consists of the following
steps:
Step 1: The decision variables of the problem are noted.
Step 2: The objective function to be optimized (maximized or minimized) as a
linear function of the decision variables is formulated.
Step 3: The other conditions of the problem, such as resource limitation, market
constraints, interrelations between variables, etc., are formulated as linear
inequations or equations in terms of the decision variables.
Step 4: The non-negativity constraint from the considerations is added so that
the
negative values of the decision variables do not have any valid physical
interpretation.
The objective function, the set of constraints and the non-negative constraint
together form a linear programming problem.
Some Important Definitions
1. A set of values X1, X2, ..., Xn which satisfies the constraints of the LPP is
called its solution.
2. Any solution to a LPP which satisfies the non-negativity restrictions of the
LPP is called its feasible solution.
3. Any feasible solution which optimizes (minimizes or maximizes) the
objective
function of the LPP is called its optimum solution.
4. Given a system of m linear equations with n variables (m < n), any solution
which is obtained by solving m variables keeping the remaining n – m
variables zero is called a basic solution. Such m variables are called basic
variables and the remaining variables are called non-basic variables.
5. A basic feasible solution is a basic solution which also satisfies all basic
variables are non-negative.
Basic feasible solutions are of two types:
(i) Non-Degenerate: A non-degenerate basic feasible solution is the basic
feasible solution which has exactly m positive Xi (i = 1, 2, ..., m), i.e.,
none of the basic variables is zero.
(ii) Degenerate: A basic feasible solution is said to be degenerate if one
or more basic variables are zero.
6. If the value of the objective function Z can be increased or decreased
indefinitely, such solutions are called unbounded solutions.

SIMPLEX METHOD
Simplex method is an iterative procedure for solving LPP in a finite number of
steps. This method provides an algorithm which consists of moving from one
vertex
of the region of feasible solution to another in such a manner that the value of
the
objective function at the succeeding vertex is less or more as the case may be
that
at the previous vertex. This procedure is repeated and since the number of
vertices
is finite, the method leads to an optimal vertex in a finite number of steps or
indicates
the existence of unbounded solution.
LINEAR PROGRAMMING USING ARTIFICIAL
VARIABLE
This section will consider the LPP in which constraints may also have the and =
signs after ensuring that all bi 0. In such cases, the basis matrix cannot be
obtained
as an identify matrix in the starting simplex table, therefore we introduce a new
type of variable called the artificial variable. These variables are fictitious and
cannot have any physical meaning. The artificial variable technique is merely a
device to get the starting basic feasible solution so that the simplex procedure may
be adopted as usual until the optimal solution is obtained. To solve such LPP,
there are following two methods:
(i) The Big M Method or the Method of Penalties
(ii) The Two-Phase Simplex Method

BIG M METHOD
The following steps are involved in solving an LPP using the Big M method.
Step 1: Express the problem in the standard form.
Step 2: Add non-negative artificial variables to the left side of each of the
equations corresponding to constraints of the type or =. However, the addition
of these artificial variables causes a violation of the corresponding constraints.
Therefore, we would like to get rid of these variables and not allow them to appear
in the final solution. This is achieved by assigning a very large penalty (–M for
maximization and M for minimization) in the objective function.
Step 3: Solve the modified LPP by the simplex method, until one of the
following three cases arises.
1. If no artificial variable appears in the basis and the optimality conditions are
satisfied, then the current solution is an optimal basic feasible solution.
2. If at least one artificial variable appears in the basis at the zero level and the
optimality condition is satisfied, then the current solution is an optimal basic
feasible solution (though a degenerated solution).
3. If at least one artificial variable appears in the basis at the positive level and
the optimality condition is satisfied, then the original problem has no feasible
solution. The solution satisfies the constraints but does not optimize the
objective function since it contains a very large penalty M, and is called a
pseudo-optimal solution.
Note: While applying the simplex method, whenever an artificial variable happens to leave
the basis, we drop that artificial variable and omit all the entries corresponding to its column
from the simplex table.
-------------------------- Good Luck -------------------------------