Optimization

93

4

Linear Programming

4.1 Introduction

Linear programming refers to an optimization problem that has the objec-

tive and the constraints as a linear function of the design variables. The con-

straints could be of an equality or inequality type or both. Mathematically, a

linear function satises the following properties:

f(x + y) = f(x) + f(y) (4.1)

f(kx) = kf(x) (4.2)

where x and y are the variables and k is a scalar. A practical linear program-

ming problem (LPP) might contain hundreds of design variables and con-

straints and thus require special solution techniques that are different from

the methods that were described in the previous chapters. A number of

applications of LPP can be found in the literature, some of which include

• An airline company would like to assign crews to different ights

in an optimal way so that total cost is minimized while covering its

entire network.

• In a portfolio optimization problem, an investor would like to know

the investment allocation to different assets that would maximize

the return.

• An oil company blends different qualities of oil to produce differ-

ent grades of gasoline, which need to be shipped to users who are

located in different places. The quantity of gasoline that can be pro-

duced is xed at a certain maximum and so is the input oil quantity.

The company would like to maximize its prot.

• A company produces a number of products and this requires a num-

ber of processes on different machines. The prot from each prod-

uct is known and the maximum time available for each machine

94 Optimization: Algorithms and Applications

is xed. The company would like to determine the manufacturing

policy that would maximize its prot.

• A government-run bus company has to cover different places in a

metro city. As a government company, it has an obligation to cover

all parts of the city, irrespective of whether a particular route is prof-

itable or not. The company would like to nd the number of routes

and allocate a number of buses for each of these routes in such a way

that it can maximize its prot.

The next section discusses the solution to LPP using the graphical method

and its limitations. The need to convert an LPP into the standard form

along with procedural details is discussed next. Basic denitions of linear

programming such as feasible solutions, basic solutions, basic feasible solu-

tions, and optimal solution are further introduced. The simplex method is

discussed in detail for solving LPPs. The degeneracy problem in the simplex

method and how it can be overcome is also discussed. The importance of

converting a primal problem into a dual problem is explained followed by

the dual-simplex method to solve such problems. In the simplex method, the

algorithm moves from one feasible point to another feasible point. For a large

LPP, this can be time consuming. As an alternate, interior point methods

move inside the feasible region to reach the optimum. The road map of this

chapter is given in Figure 4.1.

Solution with graphical method

Standard form of LPP

Simplex method

Multiple solutions

Degeneracy

Two-phase method

Dual simplex method

Interior-point method

Portfolio optimization

Basic solution

FIGURE 4.1

Road map of Chapter 4.