Linear optimization: Mathematical formulations of problems presented in the course 2

Introduction

Linear optimization deals with the optimization of linear goal functions considering certain restrictions. One can either maximize or minimize a goal function.

Standard Form

The standard form consists of three parts which can be described as:

• Goal function (to maximize/minimize):

$f(x_{1},x_{2})=c_{1}x{_{1}}+c_{2}x_{2}$

• Restrictions:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): a_{11} x_1 + a_{12} x_2 \leq b_1

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): a_{21} x_1 + a_{22} x_2 \leq b_2

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): a_{31} x_1 + a_{32} x_2 \leq b_3

• Non-negative variables:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1 \geq 0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_2 \geq 0

The problem can be solved in two ways:

1) Graphically, if the function is dependent on two variables.

2) With Simplex-Algorithm, if the function is dependent on multiple variables.

Example of Linear Optimization

A company makes two products. Both products have to run through three production units.

1) Machine A

2) Machine B

3) Machine C

	Phone	Fax machine
Marginal return	5 mu/unit	8 mu/unit	Capacity
Machine A	1 h/unit	3 h/unit	90
Machine B	2 h/unit	5 h/unit	160
Machine C	1 h/unit	2 h/unit	75

Goal: Maximize the marginal return!

The solution:

• Goal function: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 5x_1 + 8x_2 \rightarrow max!

• Restrictions:

 1) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1 + 3x_2 \leq 90

 2) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2x_1 + 5x_2 \leq 160

 3) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1 + 2x_2 \leq 75

• Non-negative variables: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1,x_2 \geq 0

The problem can be solved graphically. The first step is to create the goal function and the restrictions. To draw the problem the goal function has to be set zero. The inequations in the restrictions have to be replaced with equations. The cuts of the plotted restrictions create a limited area, the so called admissible range. The goal function is shifted parallelly upwards until the admissible range is still tangented to it. This last touch point of the goal function with the admissible range is the optimal point, its coordinates are the searched values $x_{1}$ and $x_{2}$.

This leads to:

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

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow

$x_{1}$ = 75; $x_{2}$ = 0

Example of simplex algorithm

The other method to solve linear optimization problems is the simplex algorithm. It solves a problem after finitely many steps or determines its insolubility.

Structure of a simplex tableau:

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

Structure variables: $x_{j}$

Slack variables: $y_{i}$

Goal function coefficients: $c_{j}$

Elements of the right side: $b_{i}$

Phases of the simplex:

 Phase 0: Blocked variables
 Phase 0’: Free variables
 Phase 1: Infeasible initial solution
 Phase 2: Optimization

The same example from above is now described as a simplex-algorithm:

Iteration 1:

	$x_{1}$	$x_{2}$
z	-5	-8	0
$y_{1}$	1	3	90
$y_{2}$	2	5	110
$y_{3}$	1	2	75

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow

Choice of the pivot-column: Column with the biggest absolutely negative goal function coefficient. In this case “-8”.

Iteration 2:

	$x_{1}$	$x_{2}$
z	-5	-8	0
$y_{1}$	1	3 (30)	90
$y_{2}$	2	5 (32)	110
$y_{3}$	1	2 (37,5)	75

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow

Choice of the pivot-row: The values of the right side are divided by the value of the pivot-column.

Then choice of the smallest positive quotient. In this case “30”.

Iteration 3:

	$x_{1}$	$x_{2}$
z	-5	-8	0
$y_{1}$	1	3	90
$y_{2}$	2	5	160
$y_{3}$	1	2	75

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow

Choice of the pivot-element: Intersection of pivot-column and pivot-row. In this case “3”.

Iteration 4:

	$x_{1}$	$y_{1}$
z
$x_{2}$	${\tfrac {1}{3}}$	${\tfrac {1}{3}}$	30
$y_{2}$		Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\tfrac{5}{3}
$y_{3}$		Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\tfrac{2}{3}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow

Switch of Non-Basis-Variable and Basis-Variable: In this case “$x_{2}$” and “$y_{1}$”.

Iteration 5:

	$x_{1}$	$y_{1}$
z	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\tfrac{7}{3}	${\tfrac {8}{3}}$	240
$x_{2}$	${\tfrac {1}{3}}$ (90)	${\tfrac {1}{3}}$	30
$y_{2}$	${\tfrac {1}{3}}$ (30)	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\tfrac{5}{3}	10
$y_{3}$	${\tfrac {1}{3}}$ (45)	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\tfrac{2}{3}	15

Iteration 5 is not the optimal solution because the goal function has a negative coefficient. In order to become the optimal solution we have to keep on this algorithm until the goal function is positive.

The optimal solution is:

	$x_{2}$	$y_{3}$
z	2	5	375
$y_{2}$	1	-2	10
$x_{1}$	2	1	75
$y_{1}$	1	-1	15

The goal function coefficients are Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \geq

0 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow
Optimal!

The right side coefficients are Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \geq

0 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow
Feasible!

$x_{1}$ = 75 and $x_{2}$ = 0

Residual capacities: $y_{1}$ = 15; $y_{2}$ = 10; Bottleneck: $y_{3}$ = 0

Marginal return: 375 money units

Sources

http://de.wikipedia.org/wiki/Lineare_Optimierung

http://www.ee.ucla.edu/~vandenbe/103/lectures/lp.pdf

http://www.numerik.mathematik.uni-mainz.de/didaktikseminar/Gruppe7/lineareoptimierung.htm