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)\le b,f(x_1,\cdots ,x_n)\ge 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{array}{r}\sum _{i=1}^m{a}_{ji}{x}_i\le b_j(j=1,2,\cdots ,n)\\ x_i\ge 0(i=1,2,\cdots ,m)\\ \end{array}$

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)\le b$ is $y=b-f(x)$ and the old variables $x=(x_1,\cdots ,x_m)$ are called decision variables.