Linear optimization: Mathematical formulations of problems presented in the course 1: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
(→Mathematical formulations of problems presented in the course) |
(→Example:) |
||
| Zeile 1: | Zeile 1: | ||
=='''Mathematical formulations of problems presented in the course'''== | =='''Mathematical formulations of problems presented in the course'''== | ||
| − | == Example: == | + | == 1) Theoretical Characteristics of Linear Programming == |
| + | |||
| + | Linear programming (LP) is a powerful and easy-to-use tool to solve certain types of linear optimisation problems. It is widely used in Operations Research. | ||
| + | |||
| + | |||
| + | The target of the LP is to maximise (max!) or minimise (min!) a target function under well-defined restrictions. It consists both of equations (=) and inequations (> ; >= ; <= ; <) | ||
| + | |||
| + | |||
| + | Notice: The fact that only '''linear''' problems can be solved leads to the consequence that all used variables in the target function as well as in the restrictions have to be in the '''1st power'''. (Example: x^'''1''') | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | == 2) Why using Linear Programming? == | ||
| + | |||
| + | - LP is often used/needed in production planning processes. | ||
| + | |||
| + | - Many optimisation problems can be fomulated relatively easy as LP-model. | ||
| + | |||
| + | - LP is one of the most efficient tools to solve "Travelling-Salesman-Promlems" (TSP). | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | == 3) Converting a real-life problem into a LP-problem == | ||
| + | |||
| + | Now the different types of variables will be explained. How they are used you will see in the attached example. | ||
| + | |||
| + | |||
| + | Max! P = ∑j (( ej – cj ) *xj ) - kf = ∑j (( pj*xj ) | ||
| + | |||
| + | <math>\rightarrow </math>This is your target function. In this case the target "Profit (P)" has to be maximised. You can maxmimise other stuff too, e.g. the maximum amount of ressources or whatever... | ||
| + | |||
| + | |||
| + | index j = 1,...,n (Determines the number of items which are included in the model) | ||
| + | |||
| + | e = earnings of the sale of product j | ||
| + | |||
| + | c = costs to produce product j | ||
| + | |||
| + | p = e-c = profit of selling product j | ||
| + | |||
| + | x = amount of your product j | ||
| + | |||
| + | kf = fix costs (You only need this if there are existing fix costs) | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | HERE IS STILL MISSING INFO!!! | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | == 4) 1st Example: == | ||
A company makes two products (X and Y) using two machines (A and B). Each unit of X that is produced requires 50 minutes processing time on machine A and 30 minutes processing time on machine B. Each unit of Y that is produced requires 24 minutes processing time on machine A and 33 minutes processing time on machine B. | A company makes two products (X and Y) using two machines (A and B). Each unit of X that is produced requires 50 minutes processing time on machine A and 30 minutes processing time on machine B. Each unit of Y that is produced requires 24 minutes processing time on machine A and 33 minutes processing time on machine B. | ||
Version vom 19. Juni 2013, 15:26 Uhr
Inhaltsverzeichnis
Mathematical formulations of problems presented in the course
1) Theoretical Characteristics of Linear Programming
Linear programming (LP) is a powerful and easy-to-use tool to solve certain types of linear optimisation problems. It is widely used in Operations Research.
The target of the LP is to maximise (max!) or minimise (min!) a target function under well-defined restrictions. It consists both of equations (=) and inequations (> ; >= ; <= ; <)
Notice: The fact that only linear problems can be solved leads to the consequence that all used variables in the target function as well as in the restrictions have to be in the 1st power. (Example: x^1)
2) Why using Linear Programming?
- LP is often used/needed in production planning processes.
- Many optimisation problems can be fomulated relatively easy as LP-model.
- LP is one of the most efficient tools to solve "Travelling-Salesman-Promlems" (TSP).
3) Converting a real-life problem into a LP-problem
Now the different types of variables will be explained. How they are used you will see in the attached example.
Max! P = ∑j (( ej – cj ) *xj ) - kf = ∑j (( pj*xj )
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow This is your target function. In this case the target "Profit (P)" has to be maximised. You can maxmimise other stuff too, e.g. the maximum amount of ressources or whatever...
index j = 1,...,n (Determines the number of items which are included in the model)
e = earnings of the sale of product j
c = costs to produce product j
p = e-c = profit of selling product j
x = amount of your product j
kf = fix costs (You only need this if there are existing fix costs)
HERE IS STILL MISSING INFO!!!
4) 1st Example:
A company makes two products (X and Y) using two machines (A and B). Each unit of X that is produced requires 50 minutes processing time on machine A and 30 minutes processing time on machine B. Each unit of Y that is produced requires 24 minutes processing time on machine A and 33 minutes processing time on machine B.
At the start of the current week there are 30 units of X and 90 units of Y in stock. Available processing time on machine A is forecast to be 40 hours and on machine B is forecast to be 35 hours.
The demand for X in the current week is forecast to be 75 units and for Y is forecast to be 95 units. Company policy is to maximise the combined sum of the units of X and the units of Y in stock at the end of the week.
x = number of units of X produced in the current week
y = number of units of Y produced in the current week
Constraints:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 50x + 24y \leq 40*60\rightarrow
machine time A: 50 minutes per product x and 24 minutes per product y has to be lower than the capacity of 40 hours of machine A.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 30x + 33y \leq 35*60\rightarrow
machine time B: 30 minutes per product x and 33 minutes per product y has to be lower than the capacity of 35 hours of machine B.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x \geq (75 - 30)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow x \geq 45 so production of X Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \geq demand (75) - initial stock (30) , which ensures we meet demand
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y \geq 95 - 90
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow y \geq 5 so production of Y Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \geq demand (95) - initial stock (90) , which ensures we meet demand
objective function: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): max (x+30-75) + (y+90-95)
i.e. to maximise the number of units left in stock at the end of the week
