# Course:MATH340/Archive/2010-2011/921

Faculty of Science
Department of Mathematics
Course Archive 2010-2011
MATH 340 / 921
Introduction to Linear Programming
Instructor: Tom Meyerovitch
email
Office: West Mall Annex, Room 107
Class schedule: Tue Thu Fri<br\>14:00 - 16:00
Classroom: LSK 201
Office hours: Mon 14:00 - 16:00
Fri 16:00 - 17:00
Course pages

## Terms

linear function ${\displaystyle f(x_{1},\cdots ,x_{n})=c_{1}x_{1}+\cdots +c_{n}x_{n}=\sum _{i=1}^{n}c_{i}x_{i}~}$

linear inequality ${\displaystyle f(x_{1},\cdots ,x_{n})\leq b,f(x_{1},\cdots ,x_{n})\geq b~}$

linear equation ${\displaystyle f(x_{1},\cdots ,x_{n})=b~}$

standard form of LP problem

maximize ${\displaystyle \sum _{i=1}^{m}c_{i}x_{i}~}$

subject to

{\displaystyle {\begin{alignedat}{1}\sum _{i=1}^{m}a_{ji}x_{i}\leq b_{j}(j=1,2,\cdots ,n)\\x_{i}\geq 0(i=1,2,\cdots ,m)\\\end{alignedat}}~}

objective function of LP is ${\displaystyle \sum _{i=1}^{m}c_{i}x_{i}~}$

feasible solutions of LP are ${\displaystyle x_{1},\cdots ,x_{m}~}$

optimal solution maximizing or minimizing the objective function and the value of the objective function at an optimal solution is an optimal value

infeasible LP is the one without a feasible solution, i.e. the polytope defined by the equalities and inequalities is the empty set.

unbounded LP is the one that it's corresponding polytope is unbounded.

Note: optimal values occur at the vertices of the polytope, i.e. at the extremal points or at points at infinity.

slack variables of the inequality ${\displaystyle f(x)\leq b~}$ is ${\displaystyle y=b-f(x)~}$ and the old variables ${\displaystyle x=(x_{1},\cdots ,x_{m})~}$ are called decision variables.