##
**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.

N

**Linear function**f(x

_{1, }x

_{2, …, }x

_{N }) is a function in form f(x

_{1, }x

_{2, …, }x

_{N}) = å a

_{i}x

_{i}

_{ }i=1

**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.
EmoticonEmoticon