Optimization Linear Problem Example

Linear Optimization

Linear optimization or linear programming is one of the main techniques of operations research and deals with the optimization of linear objective functions over a set constrained by linear equations and inequalities. Linear programs (LPs) can often be used to solve problems for which no specially developed solution methods are known, for example, in the planning of transportation or telecommunications networks or in production planning. Linear optimization is a special case of convex optimization and the basis of several solution methods in integer linear and nonlinear optimization. Many properties of linear programs can be interpreted as properties of polyhedra and can be modeled and proved geometrically in this way.

In a linear program (LP) a matrix A ∈ ℜ^m,n and two vectors b ∈ ℜ^m,1 and c ∈ ℜ^1,n are given. A feasible solution is a vector x ∈ ℜⁿ with non-negative entries, which satisfies the linear conditions:

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n  ≤  b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n  ≤  b₂

⋮

a_m1x₁ + a_m2x₂ + ... + a_mnx_m  ≤  b_m

The goal is to find among all feasible vectors x ∈ ℜⁿ one that maximizes the standard scalar product:

cx = c₁x₁ + c₂x₂ + ... + c_nx_n

This optimization problem in the so-called standard form (also called inequality form) is often written abbreviatively as where the constraints Ax ≤ b and x ≥ 0 are to be understood component-wise. Furthermore, there are other equivalent formulations which can be brought into this standard form by simple operations:

max{cx | Ax ≤ b , x ≥ 0}

• Minimization problem instead of maximization problem: multiplication of the objective function vector c by - 1
• Greater-than-equal constraints instead of less-than-equal constraints: Multiplication of the corresponding inequalities by - 1
• Equality conditions instead of inequality conditions: Substitution of a_ix = b_i by a_ix ≤ b_i and - a_ix ≥ - b_i
• Variables without non-negativity constraint: Substitution of x by x′ - x″ with x′ , x″ ≥ 0.

Linear optimization only deals with problems where the variables are allowed to take arbitrary real numbers. A (mixed) integer linear program where some variables are allowed to take only integer values is not a special case, but - on the contrary - a generalization. Such optimization problems are in general NP-equivalent, i.e., presumably not efficiently solvable. This case is handled by integer linear optimization.

Example - Production Planning

A company manufactures two different products, for the production of which three machines A, B, C are available. These machines have a maximum monthly runtime (capacity) of 150 hours (A), 120 hours (B) and 160 hours (C) respectively. A unit of measure (ME) of product 1 delivers a contribution margin of 240 Euro, while a ME of product 2 delivers 400 Euro. Producing one ME of product 1 requires one hour of machine A and one hour of machine B. One unit of product 2 occupies machine A for two hours, machine B for one hour and machine C for three hours. The goal is to determine production quantities that maximize the company's contribution margin without exceeding machine capacities. Fixed costs can be ignored in the optimization problem and subsequently added, since by definition they are independent of the production quantities to be determined.

Mathematical Modelling

Assume that the plant produces x1 ME of product 1 and x2 ME of product 2 per month. Then the total profit margin is

G(x₁,x₂) = 240x₁ + 400x₂.

The company would like to maximize this value. Since the machine capacities must be maintained, the constraints arise:

x₁ + 2x₂  ≤  150

x₁ + x₂  ≤  120

3x₂  ≤  160

Furthermore, since no negative production quantities are possible, x1 , x2 ≥ 0 must hold (non-negativity constraint).

Solving the Model

Now the question remains how to solve this problem. The answer is simple: with the help of the so-called simplex algorithm. In order not to make the solution too complicated, I have programmed the app LP-Solver especially for this purpose.