## You are here

Homelinear programming

## Primary tabs

# linear programming

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^{T}x$ | ||

s.t. | $\displaystyle Ax\leq b\tag{P}$ | ||

$\displaystyle x\geq 0$ |

Here $c^{T}x$ 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 $({\ref{eq:primal}})$ is the LP

minimize | $\displaystyle y^{T}b$ | ||

s.t. | $\displaystyle y^{T}A\geq c^{T}\tag{D}$ | ||

$\displaystyle y\geq 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
$(\ref{eq:primal})$ and $\hat{y}$ is feasible for $(\ref{eq:dual})$,
then $c^{T}\hat{x}\leq\hat{y}^{T}b$. This follows readily from the above:

$c^{T}\hat{x}\leq(\hat{y}^{T}A)\hat{x}=\hat{y}^{T}(A\hat{x})\leq y^{T}b.$ |

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.

# References

- 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.

## Mathematics Subject Classification

90C05*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Corrections

feasible region by CWoo ✓

also defines by CWoo ✓

spelling by Mathprof ✓

## Comments

## Algorithm

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.

## Re: Algorithm

Tic tac toe is a simple game.

The computer can enumerate ALL variants. Just enumerate all variants.

--

Victor Porton - http://www.mathematics21.org

* Algebraic General Topology and Math Synthesis

* 21 Century Math Method (post axiomatic math logic)

* Category Theory - new concepts

## Re: Algorithm

Victor is right that tic-tac-toe is a simple game and all the games can be enumerated, but there are still a lot of games. There actually is a little bit of math hidden in this that is fun to work out. (I made a chart once so I'm speaking from my own experience.) I wanted to do it without computers, it is more fun that way and teaches you something.

Moreover, it shows you how you might tackle a problem too big for brute force computer searches.

Things to keep in mind:

1. First choose a good way to encode a game with numbers. For instance, using 0,1,2 symbols in a 3 x 3 grid tell you have an upper bound of 3^9=19683 games. Clearly a computer can handle this but I've played tic-tac-tao and know the "best move" without having memorized all 19683 options. So there really is a simple algorithm hidden in there.

2. Many games are essentially equivalent because you can change the orientation and see that they are just permutations of one another. Taking this into account reduces the variablity. So try to right down an equivalence relation between two games. It is surprising how few combinations emerge after this.

3. I discovered it was easier to start from the end of the game and decode the ways I could get to that state. That is, there are many paths to get to the same conclusion but there really aren't that many final games. This is what thinking like math is like of course, work backwards. This meant I only had to consider games that could happen. (many "games" you can encode by a grid wont be actual games.)

4. Finally, if you play this game enough you soon realize that the best play always leads to a tie game. That is, it does not matter who starts, if both players play to win then they reach a tie. So one way to think of studying JUST the best plays is to start from the end of a tie game and remove plays until you see the pattern. (it turns out that in many cases there isn't just one "best" play but all you need is "one" best play to create an algorithm.)

In the end, instead of enumerating all possible plays, a huge number to humans, you only ONE way to make the best play to reach any one of the very few tie games. This is a human sized problem.