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
	Assignments Site map Syllabus

Terms

linear function $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 $f(x_{1},\cdots ,x_{n})\leq b,f(x_{1},\cdots ,x_{n})\geq b~$

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

standard form of LP problem

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

subject to

${\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 $\sum _{i=1}^{m}c_{i}x_{i}~$

feasible solutions of LP are $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 $f(x)\leq b~$ is $y=b-f(x)~$ and the old variables $x=(x_{1},\cdots ,x_{m})~$ are called decision variables.