ммммммммммммм                            ммм           мммм
     мллллллллплпппппллм       ммппппмммм млм  мллллллллмммммлпп плл
    пллллллллллллллм  плл   млллмллммм   пллллм плллллллмллмммллн лп
        пппллллллллллм он  лллллллллллпплмоллл    лллллм    пплллоп
Mo.iMP  мллм  плллллллнл  оллллллллл    олллл     олллллн      плп
      мллллллл  ллллллллн оллллллллн     ллл       лллллл
     млллллллн  олллллллл олллллллл       п        оллллллм   мл
    млллллллн    лллллллл  ллллллллн               оолллллллллп
   млплллллл мм  ллллллллн ллолллллн               оллллллпп
  млпллллллмллллмолллллллл ол пллллл           м   лнллллл             м
 мл оллллллллллп  ллллллллл плм  плллмм    ммлллп ол олллн         ммлл
лл   ллллллллп    ллллллллллм плм  пплллллллллп мммп ллллмммммммлллллп
 плм   млллп       пллллллллллм  ппмм ппмллпп  пллм   ппплплллллллпп
    ппппп                ппллп      ппппп        ппппппппппппп
          ARRoGANT                CoURiERS      WiTH     ESSaYS

Grade Level:       Type of Work           Subject/Topic is on:
 [ ]6-8                 [ ]Class Notes    [Linear Programming      ]
 [ ]9-10                [ ]Cliff Notes    [                        ]
 [x]11-12               [x]Essay/Report   [                        ]
 [x]College             [ ]Misc           [                        ]

 Dizzed: 07/94  # of Words:560   School:Public          State:NY   
ФФФФФФФФФ>ФФФФФФФФФ>ФФФФФФФФФ>Chop Here>ФФФФФФФФФ>ФФФФФФФФФ>ФФФФФФФФФ>ФФФФФФФФФ
     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

ФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФ
                           Protein     Fat    Carbohydrate    Cost
ФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФФ
100g bread                   40         5         205          2.2p
100g cheese                  60        380         60           12p
Minimal daily requirement   300        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.
Minimize   z=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'<c' for all x'=0

                               Degeneracy

     Degeneracy occurs in a transportation problem when a partial sum of
the supplies equals partial sum of the demans, for example when
s'+s''''=d''+d'''.  Under such circumstances, a basic feasible solution may
be obtained in which less than m+n-1 of the value x' are positive, which
results in too few equations to determine the u'=v'.  This difficulty can
be overcome by making the problem non-degenerate.