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.

                                                                                                                                                     N

Linear function f(x_1, x_{2, …,}  x_N ) is a function in form f(x_1, x_{2, …,}  x_N) =  å a_ix_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.