PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (210)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (37)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Medium Entry average rating: No information on entry rating
linear programming (Topic)

A linear programming problem, or LP, is a problem of optimizing a given linear objective function over some polyhedron. The standard maximization LP, sometimes called the primal problem, is

maximize  $\displaystyle c^Tx\ $    
s.t.  $\displaystyle Ax\le b$ (P)
  $\displaystyle x\ge 0$    

Here $ c^Tx$ is the objective function and the remaining conditions define the polyhedron which is the feasible region over which the objective function is to be optimized. The dual of % latex2html id marker 186 $ ({\ref{eq:primal}})$ is the LP
minimize  $\displaystyle y^Tb\ $    
s.t.  $\displaystyle y^TA\ge c^T$ (D)
  $\displaystyle y\ge 0$    

The linear constraints for a linear programming problems define a convex polyhedron, called the feasible region for the problem. The weak duality theorem states that if $ \hat{x}$ is feasible (i.e. lies in the feasible region) for % latex2html id marker 193 $ (\ref{eq:primal})$ and $ \hat{y}$ is feasible for % latex2html id marker 197 $ (\ref{eq:dual})$, then $ c^T\hat{x}\le\hat{y}^Tb$. This follows readily from the above:

$\displaystyle c^T\hat{x}\le(\hat{y}^TA)\hat{x}=\hat{y}^T(A\hat{x})\le y^Tb.$
The strong duality theorem states that if both LPs are feasible, then the two objective functions have the same optimal value. As a consequence, if either LP has unbounded objective function value, the other must be infeasible. It is also possible for both LP to be infeasible.

The simplex method of G. B. Dantzig is the algorithm most commonly used to solve LPs; in practice it runs in polynomial time, but the worst-case running time is exponential. Two polynomial-time algorithms for solving LPs are the ellipsoid method of L. G. Khachian and the interior-point method of N. Karmarkar.

Bibliography

1
Chvátal, V., Linear programming, W. H. Freeman and Company, 1983.
2
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and C. Stein, Introduction to algorithms, MIT Press, 2001.
3
Korte, B. and J. Vygen, Combinatorial optimization: theory and algorithms, Springer-Verlag, 2002.



"linear programming" is owned by mathcam. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

Other names:  LP
Also defines:  linear programming problem, objective function, feasible region, feasible
Keywords:  linear programming
Log in to rate this entry.
(view current ratings)

Cross-references: ellipsoid, polynomial-time, running, polynomial time, algorithm, consequence, duality, convex polyhedron, primal, polyhedron
There are 13 references to this entry.

This is version 9 of linear programming, born on 2003-06-16, modified 2006-10-13.
Object id is 4369, canonical name is LinearProgrammingProblem.
Accessed 11142 times total.

Classification:
AMS MSC: 90C05 (Operations research, mathematical programming :: Mathematical programming :: Linear programming)
Pending Errata and Addenda
None.
[ View all 4 ]
Discussion
Style: Expand: Order:
forum policy
Algorithm by PARASHAR on 2008-01-04 00:55:57
I need an urgent help on below mentioned problem. I need an algorithm to find out the best possible move.

Game of Tic-Tack-Toe is a well-known game. It is a simple board with 9 squares arranged as a three by three matrix. There are two players. One of them ticks the squares and the other crosses the squares. The aim of the two players is to place their symbol (tick or cross) on three consecutive squares, either horizontal, vertical or diagonal. The player who places his symbol in three consecutive squares wins the game. The players place their symbol on the board by taking turns. One symbol at a time. You have to place your symbol on an empty square. Initially (at the start of the game) all the squares are empty. Who makes the first move of the game is decided by the two players themselves. There is no rule governing this aspect of the game.

This problem is to find your best move, given a position of this board.
[ reply | up ]
Interact
post | correct | update request | add example | add (any)