[Kolman & Beck] Chapter 1 Introduction to Linear Programming

http://en.wikipedia.org/wiki/Linear_programming

1.1 The Linear Programming Problem

general  linear programming problem
- objective function
- constraints

standard form
canonical form

Every linear programming problem that has unconstrained variables can be solved by solving a corresponding linear programming problem in which all the variables are constrained to be nonnegative.

Every linear programming problem can be formulated as a corresponding standard linear programming problem or as a corresponding canonical linear programming problem.   (53p)

Minmization Problem as a Maximization Problem
: To minimize the objective function we could maximize its negative instead and then change the sign of the answer.

Reversing an Inequality

Changing an Equality to Inequality

Unconstrained Variables

Scaling
to make all coefficients in a linear programming problem approximately the same size

1.2 Matrix Notation

feasible solution
: a vector satisfying the constraints of a linear programming problem

optimal solution
: a feasible solution maximizing or minimizing the objective function of a linear programming



1.4

kb_ch1_4.ppt

ref.
http://en.wikipedia.org/wiki/Convex_polyhedron
http://mathworld.wolfram.com/ConvexPolyhedron.html
http://en.wikipedia.org/wiki/Extreme_point
http://en.wikipedia.org/wiki/Krein%E2%80%93Milman_theorem
http://library.wolfram.com/infocenter/MathSource/440/
http://www.ifor.math.ethz.ch/~fukuda/fukuda.html



slack & surplus variable in the siimplex algorithm
http://www-fp.mcs.anl.gov/otc/Guide/CaseStudies/simplex/standard.html