Linear optimization: Formulation and graphical solution of a LP 4

Introduction

Linear optimization is a mathematical technique used in Operations Research to solve problems in which the objective function and the requirements are given as linear functions. This method generates, considering the constraints that are formulated as equalities or inequalities, the best outcome of the given mathematical model. The objective function includes two, three or more variables and can be either minimized or maximized.

Definition/ Formulation

objective function to maximize (or minimize): F(x₁,...,x_p) = c₁ x₁ + ... + c_p x_p

problem constraints:

a_i1 x₁ + … + a_ip x_p ≤ b_i for i = 1,...,m₁

a_i1 x₁ + ... + a_ip x_p ≥ b_i for i = m₁+1,...,m₂

a_i1 x₁ + ... + a_ip x_p = b_i for i = m₂+1,...,m

consideration of the non-negative condition: x_j ≥ 0 for all j = 1,...,p

Example

In the following part we consider only two variables. First we formulate the problem mathematically which includes the objective function and the restrictions. Then we solve it graphically.

Maximization

In the following example we want to produce clothes. Therefore we need cloth and machines. Goal is to maximize revenues.

x₁: sweat shirts

x₂: T-shirts

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

The table leads to the following model:

goal function: max F(x₁, x₂) = 40 x₁ + 30 x₂

restrictions:

• x₁ + x₂ ≤ 70 restriction 1

• 9 x₁ + 5 x₂ ≤ 450 restriction 2

• x₁ , x₂ ≥ 0 non-negative condition

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

First we draw the restrictions. They show us the maximal feasible solution set. Afterwards we draw the goal function and implement a parallel translation to get as far as possible away from the beginning. That's how we get the optimal feasible solution.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

The optimal solution is:

(x*) = (x₁* = 25, x₂* = 45)

The maximal profit is:

F (x*) = 40 • 25 + 30 • 45 = 2350 Euro

Minimization

In the following example we want to plant flowers. Therefore we need gardener and fertilizers. The costs shoud be minimal.

x₁: roses

x₂: sunflowers

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

The table leads tot he following model:

goal function: min F(x1, x2) = 2 x1 + 2 x2

restrictions:

• 8 x1 + 4 x2 ≥ 32 restriction 1

• 5 x1 + 5 x2 ≥ 25 restriction 2

• x1, x2 ≥ 0 non-negativ condition

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

As we proceeded in the example above, we first draw the restrictions. But now the feasible solution set is different to the maximation example caused by the different restriction inequations. Then we draw the goal function again and shift it downwards as far as possible. This leads to the optimal solution.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

The optimal solution is:

(x*) = (x₁* = 3, x₂* = 2)

The costs are:

F (x*) = 3 • 3 + 2 • 2 = 13 Euro