109 lines
5.9 KiB
Plaintext
109 lines
5.9 KiB
Plaintext
ÜÜÜÜÜÜÜÜÜÜÜÜÜ ÜÜÜ ÜÜÜÜ
|
|
ÜÛÛÛÛÛÛÛÛßÛßßßßßÛÛÜ ÜÜßßßßÜÜÜÜ ÜÛÜ ÜÛÛÛÛÛÛÛÛÜÜÜÜÜÛßß ßÛÛ
|
|
ßÛÛÛÛÛÛÛÛÛÛÛÛÛÛÜ ßÛÛ ÜÛÛÛÜÛÛÜÜÜ ßÛÛÛÛÜ ßÛÛÛÛÛÛÛÜÛÛÜÜÜÛÛÝ Ûß
|
|
ßßßÛÛÛÛÛÛÛÛÛÛÜ ÞÝ ÛÛÛÛÛÛÛÛÛÛÛßßÛÜÞÛÛÛ ÛÛÛÛÛÜ ßßÛÛÛÞß
|
|
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.
|