Chapter 1

LITERATURE REVIEW ON APPLICATION

OF LINEAR PROGRAMMING

INTRODUCTION

Linear programming can be viewed as part of a great revolutionary

development which has given mankind the abilitv to state general goals

and to lay out a path of detailed decisions to take in order to “best”

achieve its goals when faced with practical situations of great complexity.

Our tools for doing this are ways to formulate leal-world problems in

detailed mathematical terms (models), techniques for solving the models

(algorithms), and engines for executing the steps of algorithms

(computers and software). This ability began in 1947, shortly after World

War II, and has been keeping pace ever since with the extraordinary

growth of computing power. So rapid has been the advance in decision

science that few remember the contributions of Tie great pioneers that

started it all. Some of their names are Von Neumann, Kantorovich,

Leontief, and Koopmans.

The first two were famous mathematicians. The last three received

the Nobel Prize in economics. In the years from the time when it was first

l
proposed in 1947 by the author (in connection with the planning activities

of the military), linear programming and its many extensions have come

into wide use. In academic circles decision scientists (operations

researchers and management scientists), as well as numerical analysts,

mathematicians, and economists have written hundreds of books and an

uncountable number of articles on the subject.

Curiously, in spite of its wide applicability today to everyday

problems, it was unknown prior to 1947. This is not quite correct; there

were some isolated exceptions. Fourier (of Fourier series fame) in 1823

and the wellknown Belgian mathematician De La Vallee Poussin in 1911

each wrote a paper about it, but that was about it. Their work had as much

influence on Post-1947 developments as would finding in an Egyptian

tomb an electronic computer built in 3000 BC. Leonid Kantorovich’s

remarkable 1939 monograph on the subject was also neglected for

ideological reasons in the USSR. It was resurrected two decades later

after the major developments had already taken place in the West. An

excellent paper by Hitchcock in 1941 on the transportation problem was

also overlooked until after others in the late 1940’s and early 1950’s had

independently rediscovered its properties. What seems to characterize the

pre-1947 era was lack of any interest in trying to optimize. T. Motzkin in

his scholarly thesis written in 1936 cites only 42 papers on linear

inequality systems, none of which mentioned an objective function.

2
 The major influences of the pre-1947 era were Leontief s work on

the Input-Output Model of the Economy (1933), an important paper by

Von Neumann on Game Theory (1928), and another by him on steady

economic growth (1937).

In 1949, exactly two years from the time the Linear programming

was first conceived, the first conference (sometimes referred to as the

Zero Symposium) on mathematical programming was held at the

University of Chicago. Tjalling Koopmans, the organizer, later titled the

proceedings of the conference, Activity Analysis of Production and

Allocation. Economists like Koopmans, Kenneth Arrow, Paul Samuelson,

Leonid Hurwitz, Robert Dorfman, Nicholos Georgescu-Roegen, and

Herbert Simon; mathematicians like Albert Tucker, Harold Kuhn, and

David Gale; and Air Force types like Marshall Wood, Murray Geisler, all

made contributions.

The advent or rather the promise that the electronic computer

would exist soon, the exposure of theoretical mathematicians and

economists to real problems during the war, the interest in mechanizing

the planning process, and last but not least the availability of money for

such applied research all converged during the period 1947-1949. The

time was ripe, the research accomplished in exactly two years is, one of

the remarkable events of history. The proceedings of the conference

remains to this very day an important basic reference, a classicl

3
 The simplex method turned out to be a powerful theoretical tool for

proving theorems as well as a powerful computational tool. To prove

theorems it is essential that the algorithm include a way of avoiding

degeneracy. Therefore, much of the early research around 1950 by Alex

Orden, Philip Wolfe at the Pentagon and by J. H. Edmonson as a class

exercise in 1951 and by A. Chames in 1952 was concerned with what to

do if a degenerate solution is encountered.

In the early 1950’s many areas which we collectively call

Mathematical Programming began to emerge. These subfields grew

rapidly with linear programming playing a fundamental role in their

development. A few words will now be said about each of these.

Nonlinear Programming began around 1951 with the famous Karush-

Kuhn-Tucker Conditions which are related to the Fritz-John Conditions

(1948). In 1954, Ragnar Frisch (who later received the first Nobel prize in

economics) proposed a nonlinear interior point method for solving linear

programs. Earlier proposals such as those of Von Neumann and Motzkin

can also be viewed as interior methods.

Later in the 1960’s, G. Zoutendijk, T. Rockafellar, P. Wolfe, R.

Cottle, Fiacco and McCormick, and others developed the theory of

nonlinear programming and extended the notions of duality. Commercial

Applications were begun in 1952 by Chames, Cooper and Mellon with

their (now classical) optimal blending of petroleum products to make

4
gasoline. Applications quickly spread to other commercial areas and soon

eclipsed the military applications which started the field.

Software—The Role of Orchard-Hays. In 1954, William Orchard-

Hays of the Rand Corporation, wrote the first commercial-grade software

for solving linear programs. Many theoretical ideas such as ways to

compact the inverse, take advantage of sparsity, and guarantee numerical

stability were first implemented in his codes. As a result his software

ideas dominated the field for many decades and made commercial

applications possible. The importance of Orchard-Hays’ contributions

cannot be overstated for it stimulated the entire development of the field

and transformed linear programming and its extensions from an

interesting mathematical theory into a powerful tool that changed the way

practical planning was done.

Network Flow Theory began to evolve in the early 1950’s. Flood,

Ford and Fulkerson in 1954, Hoffman and Kuhn in 1956 developed its

connections to graph theory.

Recent research on combinatorial optimization benefited from this

early research.

Large-Scale Methods began in 1955 with the paper “Upper

Bounds, Block Triangular Systems, and Secondary Constraints.” In 1959-

60 Wolfe published papers on the Decomposition Principle. Its dual form

was discovered by Benders in 1962 and first applied to the solution of

5
mixed integer programs. It is now extensively used to solve stochastic

programs.

Stochastic Programming began in 1955 with the paper “Linear

Programming under Uncertainty” (an approach which has been greatly

extended by R. J.-B. Wets in the 1960’s and J. R. Birge in the 1980’s).

Independently, at almost the same time in 1955, E. M. L. Beale proposed

ways to solve stochastic programs. Important contributions to this field

have been made by A. Chames and W. W. Cooper in the late 1950’s

using chance constraints, i.e., constraints which hold with a stated

probability.

Stochastic programming is one of the most promising fields for

future research, one closely tied to large scale methods. One approach

that Peter Glynn and Gerd Inflanger investigated (1990), combines

Benders’ decomposition principle, with ideas based on importance

sampling and the use of parallel processors. Integer Programming began

in 1958 by R. E. Gomory.

Unlike the earlier work on the traveling salesman problem by D. R.

Fulkerson, S. M. Johnson and Dantzig, Gcmory showed how to

systematically generate the ‘cutting’ planes.

Karmarkar’s algorithm (1984) was an important improvement on

the theoretical result of Khachian that a linear program can be solved in

polynomial time. Moreover his algorithm turned out to be one which

6
could be used to solve practical linear programs. At the present time

(1990), interior algorithms are in open competition with variants of the

simplex method. It appears likely that commercial software for solving

linear programs will eventually combine pivot type moves used in the

simplex methods with interior type moves.

ORIGINS OF CERTAIN TERMS

Here are some stories about how various linear programming terms

arose. The military refer to their various plans or proposed schedules of

training, logistical supply and deployment of combat units as a program.

When it was first analyzed the Air Force planning problem and saw that it

could be formulated as a system of linear inequalities, a paper publish

entitled Programming in a Linear Structure. Note that the term ‘program’

was used for linear programs long before it was used as the set of

instructions used by a computer. In the early days, these instructions were

called codes. In the summer of 1948, Koopmans visited the Rand

Corporation. One day he took a stroll along the Santa Monica beach.

Koopmans said: “Why not shorten ‘Programming in a Linear Structure’

to ‘Linear Programming’?”

It was replied by contemporary scholars: “That’s it! From now on

that will be its name.” Later that day a talk was given at Rand, entitled

“Linear Programming”; years later Tucker shortened it to Linear

Program.

7
 The term Mathematical Programming is due to Robert Dorfinan of

Harvard, who felt as early as 1949 that the term Linear Programming was

too restrictive. The term simplex method arose out of a discussion with T.

Motzkin who felt that the approach that was in use, when viewed in the

geometry of the columns, was best described as a movement from one

simplex to a neighboring one. Mathematical programming is also

responsible for many terms which are now standard in mathematical

literature, terms like Arg Min, Arg Max, Lexico-Max, Lexico-Min. The

term dual is an old mathematical term. But surpris ingly the term primal is

new and was proposed by Tobias Dantzig around 1954 after William

Orchard-Hays stated the need for a word to cal the original problem

whose dual was such and such.

SUMMARY

Early Contributions

If one were asked to summarize the early and perhaps the most

important contributions to linear programming, I: can be answered that

they are three:

(1) Recognizing (as a result of the wartime years as a practical

program planner) that most practical planning relations could be

reformulated as a system of linear inequalities.

8
 (2) Replacing the set of ground rules for selecting good plans by an

objective function. (Ground rules at best are only a means for carrying

out the objective, not the objective itself.)

(3) Inventing the simplex method which transformed the rather

unsophisticated linear-programming model of the economy into a basic

tool for practical planning of large complex systems.

The tremendous power of the simplex method is a constant surprise

to the researcher. To solve by brute force the assignment problem would

require a solar system full of nano-second electronic computers running

from the time of the big bang until the time the universe grows cold to

scan all the permutations in order to select the one which is best. Yet it

takes only a moment to find the optimum solution using a personal

computer and standard simplex or interior method software.

In retrospect it is interesting to note that the original problem that

started the present research is still outstanding—namely the problem of

planning or scheduling dynamically over time, particularly planning

dynamically under uncertainty. If such a problem could be successfully

solved it could (eventually through better planning) contribute to the

well-being and stability of the world.

By 1990, stochastic programming has become a very exciting field

of research and application with research taking place in many countries.

This active and difficult field has already solved some important long

9
term planning problems, believe that progress depends on ideas drawn

from many fields. For example, group at Stanford is working on a

solution method, which combines the Nested Decomposition Principle,

Importance Sampling, and the use of parallel processors.

Prior to linear programming it was not practical to explicitly state

general goals and so objectives were often confused with the ground rules

for the solution. Ask a military commander what the goal is and he would

say, “The goal is to win the war.” Upon being pressed to be more explicit,

a Navy man might say, “The way to win the war s to build battleships,”

or, if he is an Air Force general, he might say, “The way to win is to build

a great fleet of bombers.” Thus the means to attair the objective becomes

the objective in itself, which in turn spawns new ground rules as to how to

go about attaining the means such as how best to go about building

bombers. These means in turn become confused wth goals.

From 1947 on, the notion of what is meant by a goal has been

adjusting to our increasing ability to solve complex problems. As we near

the end of the 20th Century, planners are becoming more and more aware

that it is possible to optimize a specific objective while, at the same time,

hedging against a great variety of unfavorable contingencies which might

happen and taking advantage of any favorable opportunity that might

arise.

10
 THERE would seem little to connect the logistic requirements of

the US military with the animal feed industry or with the human food

business. But this is the route that linear computer programming has

taken.

From their military origins linear programs are finding increasing

applications within the food industry. To some ex ent this is the result of

spillover from their extensive use in the anima' feed industry, where

companies involved in both markets have seen the value of applying

linear programs to their human food divisions.

Today linear programs from Format International are being used in

such diverse industries as sausage making, frimt juice mixing, baby

cereals and milks, health foods, soups, margarine aid tea blends.

Linear programming allows for the optimal allocation of scarce or

costly resources while still meeting all technical parameters. It is

possible, for instance, to ensure that minimum levels of protein and

carbohydrate are maintained in baby milks while simultaneously

ensuring a maximum level of certain ingredients is not exceeded. Factors

such as flavor, color and texture may be considered also.

Programs based on contained cost technology, often referred to as

least-cost, can be used to maintain quality provided safeguards are built-

in. Format formulation packages allow the technologist to insert those

recipe rules that have always been applied. Far example, it may be

11
known that if more than 20 per cent mango juice is included in a fruit

juice blend it makes the flavor of the other ingredients, but if less than 5

per cent is used it cannot be tasted. This set of parameters may then be

entered into the program.

An important feature of formulation packages is that they can

generate cost (sensitivity) data about either ingredients or constraints.

Where ingredients are concerned, data can be created for those

ingredients currently in use and, importantly, for ingredients being

considered for future use. It is possible to determine the exact price that

can be paid for textured soya flour, to compare extruded soya flour and

an exfoliated product simultaneously, and determine which is the best

buy for a particular circumstance.

By its very nature linear programming can evaluate an ingredient in

financial terms considering the following aspects: the product in which

the ingredient is to be used; the price and availability of alternative

ingredients; and the characteristics of the material being evaluated.

By using linear programming the technologist can generate

information for the buying department stating exactly how much can be

paid for an ingredient.

In large organizations recipe management is important. Besides

simply formulating recipes, modem formulation packages perform

12
several mundane tasks quickly and efficiently. These include the

following: keeping track of ingredient price changes; re-costing recipes

when new ingredient prices are introduced; and determining a breakdown

of ingredient usage.

The savings that can be made using linear programming

technology to solve blending problems are dependent on the complexity

of the blend and the tolerance within which the technologist has to work.

Savings can range from 1 per cent to well over 5 per cent of recipe cost.

On-going reformulation minimizes the effect of ingredient price

increases and enables the technologist to capitalize on the use of new or

cheaper ingredients.

Maintaining product quality is facilitated by using formulation

software. In the first instance the technologist may consider many

parameters simultaneously. This is impossible to do by hand and very

difficult to achieve if formulation is being done on a spreadsheet. In

addition, it is a simple matter to reformulate a product if the quality of an

ingredient changes.

Production of least-cost recipes as discussed thus far assumes that

all ingredients are freely available. This is hardly ever the case. A simple

price increase immediately turns a stock of cheap material into a scarce

resource. The problem is further complicated when scarce ingredients are

used in several products, in which they all have a different value.

13
 This scarce ingredient can be asked out by changing the usage in

various products. Alternatively it is possible to use a linear programming

technique across multi-product formulations.

When Format's Multi-Mix program is run all products are

formulated simultaneously, taking into consideration the ingredient price

and availability and also the total amount of product required. The

solution will result in the scarce resource being allocated across the entire

range of products so that maximum benefit is derived from its inclusion.

Experience has shown that when such a problem is run through the

Multi-Mix program solutions may be up to 1 per cent more economic

than the same recipes formulated on an individual basis.

Many manufacturing sites can handle only a limited number of

ingredients. By making judicious use of a formulation package it is

possible to make a quantitative decision as to which ingredients to

purchase. It may be possible also to show how much money could be

saved by the upgrading of facilities. It is possible to optimize the use of

mixers, dryers, packing lines and labor using linear programs.

If a company produces and delivers their product from a single site

the decision about how much of each product to manufacture at each site

is not relevant. On the other hand, if a company produces at a number of

geographically diverse sites, the decision as to which factory should be

supplying product to which client assumes great importance. By using

14
linear programming transshipment models it is possible to optimize the

cost of manufacture and delivery considering economies of scale, factory

capacity, client requirements and delivery routes simultaneously. More

complex models will consider ingredient cost and availability at the

various sites. While models of this nature are useful for optimizing an

existing business, they play an important role when decisions about

upgrading existing facilities or siting new facilities need to be made.

Linear programming is not new technology but it is newly

available to most small and medium size businesses. It is indisputable

that it has an important role to play in the future of the food industry.

When applied correctly it can lead to more consistent products at

significantly reduced cost. Further cost savings can be realized through

improved ingredients purchasing and control as well as through more

effective use of plant and transport resources. Most businesses in the

food industry could benefit from the application of linear programming.

Linear Programming is a mathematical and operations-research

technique, used in administrative and economic planning to maximize the

linear functions of a large number of variables, subject to certain

constraints. The development of high-speed electronic computers and

data-processing techniques has brought about many recent advances in

linear programming, and the technique is now widely used in industrial

and military operations. Linear programming is basically used to find a

15
set of values, chosen from a prescribed set of numbers that will maximize

or minimize a given polynomial form. The polynomial is linear. This

technique could be used in determining the extent of resource uses in Bay

Systems. This will involve finding the appropriate parameter/s for the

formulation and solution of linear inequalities ard equalities. Thus, the

resource uses in the Bay System could be optimized for the benefit of the

people and other stakeholders and also the environment.

Linear Programming (LP) the problem of maximizing a linear

objective function in n variables subject to m linear (in)equality

constraints { is the most prominent optimization problem, and efficient

methods have been devised to solve such problems in practice. The

values of n and m for which solutions can nowadays be computed, range

up to several millions for max(n;m) and several thousands for min(n;m).

The simplex method, invented by G. Dantzig 50 years ago [10], is still

among the most practical methods to solve linear programs, and state-of-

the art solvers like CPLEX implement variants of k.

Applications

One of the most widely applied methodologies.

85 % of Fortune 500 companies had used LP.

- Industrial Environments

- Corporate Planning

- Factory Planning

16
- Product Distribution

- Lease-Buy Decision

- Production Scheduling

- Inventory Control

- Workman’s Compensation

- Agriculture Environments

- Food Manufacturing

- Deport Location

- Irrigation System

- Other Environments

- Manpower Planning

- Activity Planning

- Accounting & Finance

- Administration, Education, & Politics

- Advertising and Marketing

Allocation of Financial Budgets

Capital Investment

Mathematical programming is used extensively to optimize

reservoir operations for planning and design purposes. The choice of the

techniques usually depends on the characteristics of the reservoir system,

availability of data, and type of objective function and constraints used.

The available methods include simulation, linear programming, chance-

17
constrained programming, nonlinear programming, dynamic

programming, and queuing and storage theories. The use of the LP

approach in combination with some other technique is reported in the

work of Bechard et al. (1981), Pereira and Pinto (1983), and Manitoba

Hydro (1986).

The idea of SLP emerges from the work of Grygier and Stedinger

(1985), and is based on the linearization principle introduced by Loucks

et al. (1981). The Grygier algorithm inspired the research reported in this

paper.

The increase of water demand has created a lot of problems in the

last years and the imperative need to develop water resources

management plans in the world. As groundwater represents one of the

most important resources, many of the plans are related to the

exploitation of aquifers. Numerical methods have been developed, until

now, to simulate the ground water and Linear Programming methods

have been applied to minimize the total cost of the pumped water.

Several groundwater flow models have been developed by

researchers and technical software houses during the last decades. First of

all, Schwarz (1971) presented an example of optimal groundwater

management, using Linear Programming. He had chosen a two-

dimensional rectangular grid of 25 cells, in order to represent the aquifer

system. Bear (1979) also described the combination of both management

18
and optimization problems. Me Donald & Harbaugh (1988) dealt with the

development of 3D groundwater model and solvec it through a multilevel

iterative process, based on finite differences method. Greenwald (1994)

had cooperated with Me Donald & Harbaugh anc provided optimization

techniques in conjunction with the respective sofcware support, in order

to solve the groundwater and irrigation problems.

A large number of publications also exist on the application of

Linear Programming to the management of water resources. N.K. Garg

and Abbas Ali (1997) dealt with the application Df a Linear and Integer

Programming model to Dadu canal command of Lower Indus Basin. A. A.

Psilovikos (1998) compared two optimization methods, based on Linear

and Mixed Integer Programming, combining primarily the simulation

model MODFLOW with the management one MODMAN and

optimization LINDO.

There are many other well mentioned publications, focus on

optimized operations in water management. Fcr example, Arnold H.

Lobbrecht (1994) described an optimized control strategy, under

changing objectives and dynamic boundary condition, in a rural water

management system in Netherlands. A.S. Reeve et al. (1999) analyzed

how the groundwater flow simulations are used to evaluate the

importance of three parameters on vertical flow in peat lands: regional

slope, permeability of the mineral soil and peat land topography, etc.

19
Organisation of thesis

Present study is divided into Five (5) Chapters that describe as follows:

In chapter 1 - Linear Programming is a tool to optimize decision­

making process. Taha mentioned that linear programming could be used

to solve problems which variables, constraints and objective function can

be identified. Besides solving production mix problems, linear

programming can be utilized to solve resources allocation problem. In

this Chapter an attempt is made to collect almost all literature on Linear

Programming Problem (LPP) along with its application in various fields.

At the end of Chapter construction and presentation of thesis is

given.

In Chapter 2 - linear programming is applied for Dormitory

development plan. Dormitory is a very important facility which has to be

provided by a university, colleges and residential schools for students

with multi facilities like library, bookshop, cafeteria, sport and other

facilities managed by the students. A survey of students has been

conducted to understand the required facilities and their financial ability.

Linear programming has been used to calculate number of rooms and

area of each facility which could satisfy the constraints and to obtain

optimum profit. Number of bedrooms, number of bathrooms, and area of

20
each facility, living room, dining room, common room, cafeteria, book

shop, mini market, phone booths, sport facilities, and parking space are

recommended. A dormitory is a site allocation problem in which the land

should be optimized to satisfy the students’ needs. There are some

constraints and objective functions to be met by investors. Therefore, the

site allocation problem of a dormitory could be solved by linear

programming model. In this study, the number of rooms and the area of

supporting facilities are the decision variables. The decision variables

have been selected based on the survey on the market demand of

student’s dormitory.

In Chapter 3 - The main objective of this Chapter was to develop

a separable linear programming model, considering a set of technical

factors which may influence the profit of an irrigation project. The model

presents an objective function that maximizes the net income and

specifies the range of water availability. It is assumed that yield functions

in response to water application are available for different crops and

describe very well the water-yield relationships. As it is known that water

supply is limited, the considerations about crop and irrigated area

selection must be based on crop profitability according to the effect

caused when the water needs are answered by the available water supply

during the crop cycle. The planning of an irrigation project is considered

21
optimal, according to economical values, if the results maximize the

difference between the gross income and the production costs to specific

restrictions imposed to the production system. Analyzing the relation

between gross income and costs, this problem can be rationally solved by

a mathematical programming model.

The linear programming model was developed genetically, so that,

the rational use of the available water resource could be included in an

irrigation project. Specific equations were developed and applied in the

irrigation project to get optimal solution.

In chapter 4 - Integrated study of Geographical Information

system (GIS) and Linear Programming (LP) is undertaken to find optimal

utilities of available land with minimum expenditure. Geographical

Information system is one such tool responsible for revolutionizing the

era of spatial data management. A GIS can be considered as a tool for the

integration and analysis of geographically- referenced data. Basically it is

a commercial system and lacks spatial statistics and modeling language,

which is required in applications in the field of hydrology, soil science,

forestry and land use planning. This system is found to be adjusting, these

models within itself. We have chosen to integrate the technique of linear

programming with GIS for land use planning problem. Present model is

idealized and structured representation of the part of reality and is

22
successful in forecasting the future situations. Linear Programming is

used for generating different planning scenarios, and with the help of LP

multiple relationships between the decision variables and the constraints

are interpreted.

In chapter 5 - The fuzzy set theory has been applied in many

fields, such as operations research, control theory, and management

sciences, etc. In particular, an application of this theory in decision

making problems is linear programming problems with fuzzy numbers. In

this study, a new method for solving fuzzy number linear programming

problems, by use of linear ranking function is suggested. In fact, proposed

method is similar to simplex method that was used for solving linear

programming problems in crisp environment before. Fuzzy linear

programming first formulated by Zimmermann Recently, these problems

are considered in several kinds, that is, it is possible that some

coefficients of the problem in the objective function, technical

coefficients, the right-hand side coefficients or decision making variables

be fuzzy number. In this work, we focus on the linear programming

problems with fuzzy numbers in the objective function.

At the end of the thesis ‘future scope of the study’ is discussed and

update bibliography of references is enlisted.

23