PuLP - Linear Programming modules for Python

http://www.purplemath.com/modules/linprog.htm
http://code.google.com/p/pulp-or/wiki/OptimisationWithPuLP

http://mail.python.org/pipermail/python-announce-list/2005-May/003989.html
# Borrowed code from Jean-Sebastien, see link above ...
Example script:
--------------------------------------------------
from pulp import *

prob = LpProblem("test1", LpMinimize)

# Variables
x = LpVariable("x", 0, 4)
y = LpVariable("y", -1, 1)
z = LpVariable("z", 0)

# Objective
prob += x + 4*y + 9*z

# Constraints
prob += x+y <= 5
prob += x+z >= 10
prob += -y+z == 7

GLPK().solve(prob)

# Solution
for v in prob.variables():
print v.name, "=", v.varValue

print "objective=", value(prob.objective)
--------------------------------------------------
http://www.gnu.org/software/glpk/glpk.html

Linear programming is good for maximization or minimization problems or solving Sudoku puzzles! (http://130.216.209.237/engsci392/pulp/SudokuAsAnLP)

Works by incorporating linear equations ie y = mx + b (objective function) and a bunch of constraints eg 3*x - y <= 3 or something
works like magic!

As for applications, one example is with Punyakanok et al. '04 where he applies it to optimizing the best set of argument labels in semantic role labeling (SRL)
http://l2r.cs.uiuc.edu/~danr/Papers/PRYZ04.pdf