算法高级教程1Introduction.pptVIP

* General linear programs Given a set of real numbers a1, a2, ..., an and a set of variables x1, x2,..., xn, a linear function f on those variables is defined by linear equality: linear inequalities: and * Linear constraints equalities or linear equalities. Formally a linear-programming problem is the problem of either minimizing or maximizing a linear function subject to a finite set of linear constraints. Minimization linear program Maximization linear program * Example * Standard forms Given n real numbers c1, c2, ..., cn; m real numbers b1, b2, ..., bm; and mn real numbers aij for i = 1, 2, ..., m and j = 1, 2, ..., n. We wish to find n real numbers x1, x2,..., xn that Subject to * Feasible solution Infeasible solution Objective value Optimal solution Optimal objective value Unbounded * Example * Slack forms * Example Standard forms Slack forms * The simplex algorithm The simplex algorithm takes as input a linear program and returns an optimal solution. It starts at some vertex of the simplex and performs a sequence of iterations. In each iteration, it moves along an edge of the simplex from a current vertex to a neighboring vertex whose objective value is no smaller than that of the current vertex (and usually is larger.) * The simplex algorithm terminates when it reaches a local maximum, which is a vertex from which all neighboring vertices have a smaller objective value. Because the feasible region is convex and the objective function is linear, this local optimum is actually a global optimum. * Integer Programming (IP) Integer Programming is simply Linear Programming with an added condition: All variables must be integers Many problems can be stated as Integer Programs. For example, the Vertex Cover problem can be stated as an integer programming problem. Given an undirected graph G = (V, E), find a minimum subset V of V such that if (u, v)∈E, then u∈V or v ∈V (or both). * Suppose that we associate