Linear programming is a nonstatistical mathematical technique whereby

the maximization or minimization of a linear expresion of variables, call

the objective function, is determined in the presence of known or assumed

restrictions, call constraint.

In essence, it’s a procedure for solving the problems in which there

are more variables than simultaneous equations in which the variables are

expressed.

No probability or statistics are needed to study linear programming.

The mathematics involved in linear programming is relatively easy to

understand and to manipulate in contrast to calculus. Linear equations and

inequations form the mathematical skeleton around which linear programming

is built.

A linear function called the object function is to be maximized or

minimized in some sense, like optimzed. Most real world problems have many

possible solutions. The purpose of optimization is to choose from among

many possible solutions the “best” possible solutions. Some example of

“best” are highest profit, lowest cost, largest sales, lowest production

time, etc.

The optimization of the objective functions take place in teh presence

of known or assumed restriction. The technical term constraints is used to

describe the restrictions present in linear programming problem. The

constraints are expressed mathemically as inequalities. In a practical

real-world situation, the constraints are generated by the presence of

limited resources or commodities such as capital manpower and raw material.

Mathematically, inequations can be converted to equations by the

introduction of slack variables.

Linear programming can be dated from the year 1947 when G.B. Dantzing

evolved an efficent technique call the Simplex Method, for solving linear

programming problems. The following decades, the rapid development of both

the theory and applications of linear programming which were aided by the

simultaneous introduction of the electronic computers. One of the first

probelm to be solved by the simplex method was Stigler’s diet problem

(1945). Here is the diet problem

??????????????????????????????????????????????????????????????????

ProteinFatCarbohydrateCost

??????????????????????????????????????????????????????????????????

100g bread 4052052.2p

100g cheese60 3806012p

Minimal daily requirement300 790 1350

The problem is determine how much bread and cheese Mrs. Jones

should buy each day in order to minimize the cost of the diet, whilst

fulfilling the calorie requirements. Suppose shy buys x’ * 100g of

cheese and x” * 100g of cheese, then the mathematical problem, known

as a linear programme is as follows.

Minimizez=2.2x’ + 12x”(Cost Of Diet)

Subject To 40x’ + 60x” ; or = 300 (At least 300 cal of protein)

5x’ + 380x” > or = 790 (At least 790 cal of fat)

205x’ + 60x” ; or = 1350 (At least 1350 cal of carbo.)

x’ > or = 0, x2 > = 0(quantites must be non-negative)

The easiest and most illustrative method of solving problems in two

unknowns is the graphical method. The value of x’ and x” satisfying 40x’

+ 60x” > or = 300 lies in the upper half-plane bounded by the straight

line 40x’ + 60x” = 300, so the x’ and x” satistying all the above

inequalities lie in the intersection of their respective half – plane.

Interger Solutions

Provided the supplies and demands are positive intergers, the matrix

minimum method always leads to and optimal solution with integer values as

the method only involves operations on integers which results in integers.

Obviously a non-integer optimal solution would be useless.

Uniqueness

It can happen that two or more differnet allocations of ships between

ports give rise to thesame minimum cost. However, if v’=u’