Linear Programming theory

Assistant Professor Krung Sinapiromsaran, Ph. D.
17 November 2017

Agenda

  • Optimization
  • Nonlinear/linear programming
  • Practical optimization
  • Polyhedral theory
  • Simplex method
  • Contact me

Optimization

Optimization

optimization = problem of determining the best solution under restriction or constraints along the objective direction (function)

http://seoexpresso.com/seo-homepage-optimization/

Optimization Theory

Optimization tree

http://www.wu.ece.ufl.edu/optimization/optimization.html

Nonlinear and Linear programming

  • Nonlinear programming problem \[ \begin{array}{ll} \min \mbox{ or } \max & f(x) \\ \mbox{subject to} & g(x) \leq 0 \\ & h(x) = 0 \\ & x \in X\end{array} \]

Linear programming problem \[ \begin{array}{ll} \min \mbox{ or } \max & c^T x \\ \mbox{subject to} & A x = b \\ & x \geq 0\end{array} \]

Practical optimization

  • Solving nonlinear or linear programming problem requires strong mathematical concept.

  • Practically, a user needs more simple approach. There is a need for mathematical programming language.

GLPK

Polyhedral theory

Polyhedral in 2D

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

Polyhedral in 3D

Feasible region

Feasible region

http://www.leda-tutorial.org/en/official

Simplex method

Simplex method in 2D

Simplex method in 2D and 3D

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

Simplex method in 3D

Contact me