[go: up one dir, main page]
Scribd
Upload
6 views4 pages

Theoretical Side of Linear Programming

Linear programming, pioneered by George B. Dantzig in 1947, is a mathematical technique used to optimize resource allocation in various fields by maximizing profit or minimizing cost under certain constraints. Key characteristics include a clearly defined objective function, linear relationships, and non-negativity of variables. Applications range from agriculture and military to production management and transportation, with advantages in logical decision-making and resource allocation, though it has limitations in handling non-linear problems and uncertainty.

Uploaded by

sangeethfrancis1
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views4 pages

Theoretical Side of Linear Programming

Linear programming, pioneered by George B. Dantzig in 1947, is a mathematical technique used to optimize resource allocation in various fields by maximizing profit or minimizing cost under certain constraints. Key characteristics include a clearly defined objective function, linear relationships, and non-negativity of variables. Applications range from agriculture and military to production management and transportation, with advantages in logical decision-making and resource allocation, though it has limitations in handling non-linear problems and uncertainty.

Uploaded by

sangeethfrancis1
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Meaning of Linear Programming

George B Dantzig is recognized as the pioneer of linear programming. In 1947 he


published the first paper on simplex method. Since 1947, many other researchers joined him
in developing and exploring new applications of linear programming. Now Linear
programming problem is being applied to many areas of human activity. Its application has
increased with the development of computer technology.
Linear programming may be defined as a method of determining an optimum programme
of independent activities in view of available resources. The objective of Linear
Programming Problem is to maximize profit or minimize cost, as the case may be subject
to number of limitations known as constraints.
Linear programming is widely used mathematical modelling technique, which is
developed to help decision makers in planning and decision making as far as resource
allocation is concerned. It is a technique for choosing the best alternatives from a set of
feasible alternatives, in situation in which the objective function as well as constraints can be
expressed as linear mathematical functions.

Properties
Any linear programming model (problem) must have the following properties:
(a) The relationship between variables and constraints must be linear.
(b) The model must have an objective function.
(c) The model must have structural constraints.
(d) The model must have non-negativity constraint.

Characteristics of Linear Programming

All linear programming problems must have following five characteristics:

1. Objective function:
There must be clearly defined objec-tive which can be stated in quantitative way. In business
problems the objective is generally profit maximization or cost minimization.
2. Constraints:
All constraints (limitations) regarding resources should be fully spelt out in mathematical
form.
3. Non-negativity:
The value of variables must be zero or positive and not negative. For example, in the case of
production, the manager can decide about any particular product number in positive or
minimum zero, not the negative.
4. Linearity:
The relationships between variables must be linear. Linear means proportional relationship
between two ‘or more variable, i.e., the degree of variables should be maximum one.
5. Finiteness:
The number of inputs and outputs need to be finite. In the case of infinite factors, to compute
feasible solution is not possible.

1
Objectives of Linear programming
Linear programming is a quantitative tool for optimal allocation of limited resources among
competing activities. The objective of linear programming is maximization of profit or
minimization of cost.

Assumptions
1. It is assumed that the decision maker here is completely certain (i.e., deterministic
conditions) regarding all aspects of the situation, i.e., availability of resources, profit
contribution of the products, technology, courses of action and their consequences etc.
2. It is assumed that the relationship between variables in the problem and the
resources available i.e., constraints of the problem exhibit linearity. This assumption
is very useful as it simplifies modelling of the problem.
3. We assume here fixed technology. Fixed technology refers to the fact that the
production requirements are fixed during the planning period and will not change in
the period.
4. It is assumed that the profit contribution of a product remains constant,
irrespective of level of production and sales.
5. It is assumed that the decision variables are continuous. It means that the companies
manufacture products in fractional units. For example, company manufactures 2.5
vehicles, 3.2 barrels of oil etc. This is referred to as the assumption of divisibility.
6. It is assumed that only one decision is required for the planning period. This
condition shows that the linear programming model is a static model, which implies
that the linear programming problem is a single stage decision problem.
7. All variables are restricted to non-negative values (i.e., their numerical value will be
≥ 0).

Application of Linear Programming


1. Agriculture application
Linear programming can be applied in agriculture planning. Example; allocation of limited
resources such as acreage, labour, water supply, working capital etc. in a way so as to
maximize net revenue.
2. Military application
It includes the problem of selecting weapons system against the enemy.
3. Production management
a. Product mix: A company can produce different products each of which
requires the use of limited production resources. The management wants to
determine the quantity of each product to be produced, knowing the
managerial contribution and the amount of resources to be used. In this case
the objective function may be maximization of the total profit or minimization
of loss subject to certain constraints.
b. Production planning: This deals with the determination of the minimum cost
of production over the planning period.
4. Portfolio selection
2
This involves the selection of specific investment activity among several activities. The
objective function is to find the allocation which maximizes the expected return.
5. Profit planning
It involves the maximization of profit margin from investment in plant facilities and
equipment, cash in hand etc.
6. Physical distribution
It determines the most economical and efficient manner of allocating manufacturing plants
and distribution centres for physical distribution.
7. Job evaluation
Selection of suitable person for a specified job and evaluation of a job in organization has
been done with the help of Linear programming technique.
8. Capital Investment
The problem is to find the allocation to which maximize the total return when a fixed amount
of capital is allocated to a number of activities.
9. Transportation Problem
Using transportation technique of linear programming we can determine the distribution
system that will minimize total shipping cost from several warehouses to various market
locations.
10. Assignment Transportation Problems
The problem of assigning the given number of personnel to different jobs can be tackled with
the help of assignment model. The objective of may be to minimize the total time taken or
total cost.

Formulation of Mathematical Model to Linear Programming Program


Formulation of Linear Programming model involves the following steps.
1. Identification of the problem and setting up of objectives.
2. Establish the interrelationship between the variables of the situation.
3. Identification of alternative variables
4. Specification of constraints.
5. Summarizing the problem in a mathematical form.

Advantages of Linear Programming


 LP makes logical thinking and provides better insight into business problems.
 Manager can select the best solution with the help of LP by evaluating the cost and
profit of various alternatives.
 LP provides an information base for optimum alloca-tion of scarce resources.
 LP assists in making adjustments according to changing conditions.
 LP helps in solving multi-dimensional problems.

Limitations of Linear Programming


 This technique could not solve the problems in which variables cannot be stated
quantitatively.

3
 LP technique cannot solve the business problems of non-linear nature.
 The factor of uncertainty is not considered in this technique.
 This technique is highly mathematical and complicated.
 If the numbers of variables or constrains involved in LP problems are quite large, then
using costly electronic computers become essential, which can be operated, only by
trained personnel.
 Under this technique to explain clearly the objective function is difficult.

How to Formulate Mathematical Model to LPP (Linear Programming Problems)

The following steps are applied in this process.

Step 1:
Identify the objectives as maximisation or minimisation.
Step 2:
Mention the objectives quantitatively and express it as a linear function of variable, known as
objective function. It should be expressed in ‘Z’
Step 3:
Identify the constraints which are conditions stipulated in the problem. Constraints are
expressed in the form of linear inequalities or equations.
If your objectives are maximise, then your constraints function most probably shows
the symbol of ‘≤’
If your objectives are minimize, then your constraints function most probably shows the
symbol of ‘≥’

Step 4:
In addition to the above constraints, the non negative condition such as X 1 ≥ 0, X2 ≥ 0

Graphical method
The business problems involving two variables can be easily solved by drawing the graph for
various constraints. Following are the steps in graphical solution of linear programming
problem (LPP):

1. Formulate LPP by writing the objective function (generally maximize profit or


minimise losses) and the constraints.
2. Constraints are changed into equalities.
3. Plot the constraints on the graph. (If the constraints symbol is ≤, the shade will
be downward or towards left side or below the line, and If the constraints
symbol is ≥, the shade will be upward or towards right side or above the line)
4. Identify the feasible region and ascertain their coordinates.
5. Test which point is most profitable.

You might also like