Mathguru – Help – Practical problem on linear programming.

Solved Example > No. SE 5

Practical problem on linear programming.

Post to:

Explanation:

Linear programming

Linear programming (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships. Linear programming is a specific case of mathematical programming (mathematical optimization).

More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. It's feasible region is a convex polyhedron, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine function defined on this polyhedron. A linear programming algorithm finds a point in the polyhedron where this function has the smallest (or largest) value if such point exists.

Linear programs are problems that can be expressed in canonical form:

$Description: \begin{align} & \text{maximize} && \mathbf{c}^\top \mathbf{x}\\ & \text{subject to} && A \mathbf{x} \leq \mathbf{b} \\ & \text{and} && \mathbf{x} \ge \mathbf{0} \end{align}$

where x represents the vector of variables (to be determined), c and b are vectors of (known) coefficients and A is a (known) matrix of coefficients. The expression to be maximized or minimized is called the objective function (c^Tx in this case). The equations Ax ≤ b are the constraints which specify a convex polytope over which the objective function is to be optimized. (In this context, two vectors are comparable when every entry in one is less-than or equal-to the corresponding entry in the other. Otherwise, they are incomparable.)

Linear programming can be applied to various fields of study. It is used most extensively in business and economics, but can also be utilized for some engineering problems. Industries that use linear programming models include transportation, energy, telecommunications, and manufacturing. It has proved useful in modeling diverse types of problems in planning, routing, scheduling, assignment, and design.

Standard form

Standard form is the usual and most intuitive form of describing a linear programming problem. It consists of the following four parts:

• A linear function to be maximized

e.g. $Description: \max_{x_{1},x_{2}} f(x_{1},x_{2}) = c_1 x_1 + c_2 x_2$

• Problem constraints of the following form

e.g.

$Description: \begin{matrix} a_{11} x_1 + a_{12} x_2 &\leq b_1 \\ a_{21} x_1 + a_{22} x_2 &\leq b_2 \\ a_{31} x_1 + a_{32} x_2 &\leq b_3 \\ \end{matrix}$

• Non-negative variables

e.g.

$Description: \begin{matrix} x_1 \geq 0 \\ x_2 \geq 0 \end{matrix}$

• Non-negative right hand side constants

$Description: b_i \geq 0,\; i=1,2,3$

The problem is usually expressed in matrix form, and then becomes:

$Description: \max \{ c^T x \;|\; 0 \leq A x \leq b \and x \geq 0 \}$

Other forms, such as minimization problems, problems with constraints on alternative forms, as well as problems involving negative variables can always be rewritten into an equivalent problem in standard form.

(Our solved example in mathguru.com uses this concept)

http://en.wikipedia.org/wiki/Linear_programming

The above explanation is copied from Wikipedia, the free encyclopedia and is remixed as allowed under the Creative Commons Attribution- ShareAlike 3.0 Unported License.