Wednesday, 9 January 2013

Linear Programming


Linear Programming

Examples of linear programming problems: single source shortest paths, maximum flow, minimum flow, multicommodity path.
For example:

A: amount of time spent on school work
B: amount of time spent on fun
C: amount of time spent on pay work
Maximize 24-A-B - C
given the constraints A+B + C £ 24, B +C ³8 and A ³ 0, B ³ 0, C ³ 0.

Linear function f(x1, x2, …,  xN ) is a function in form f(x1, x2, …,  xN) =  å aixi

Linear constraints are linear inequalities and/or linear equalities. For example, a-b £ 4. We saw them in ch.24, when we were solving the difference constraint problems.

A linear programming problem is the problem of either minimizing or maximizing a linear function subject to a set of linear constraints. The function that we are trying to maximize or minimize is called objective function. A set of any values of variables that satisfies all constraints of a linear program is called a feasible solution is. Since there are many values possible, all solutions span a feasible region.