Linear optimization: Formulation and graphical solution of a LP 1: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
Todea (Diskussion | Beiträge) (→Upper and lower bounds) |
Todea (Diskussion | Beiträge) (→Linear optimization with three or more variables) |
||
| Zeile 124: | Zeile 124: | ||
Maximization or rather minimization of a linear objective function with three or more variables, restricted by linear inequations with three or more variables. The solution space is multidimensional. | Maximization or rather minimization of a linear objective function with three or more variables, restricted by linear inequations with three or more variables. The solution space is multidimensional. | ||
| + | |||
| + | ''Example 1.3:'' | ||
| + | |||
| + | A company producing cars wants to maximize its profit. | ||
| + | |||
| + | objective function: | ||
| + | |||
| + | ::P=20x<sub>1</sub>+10x<sub>2</sub>+15x<sub>3</sub> | ||
| + | |||
| + | One car consists of the three factors x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub> which are restricted by the following conditions: | ||
| + | |||
| + | restrictions: | ||
| + | |||
| + | ::3x<sub>1</sub>+2x<sub>2</sub>+5x<sub>3</sub> <math>\leq </math> 55 | ||
| + | ::2x<sub>1</sub>+x<sub>2</sub>+x<sub>3</sub> <math>\leq </math> 26 | ||
| + | ::x<sub>1</sub>+x<sub>2</sub>+3x<sub>3</sub> <math>\leq </math> 30 | ||
| + | ::5x<sub>1</sub>+2x<sub>2</sub>+4x<sub>3</sub> <math>\leq </math> 57 | ||
| + | |||
| + | condition of non-negativity: | ||
| + | |||
| + | ::x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub> <math>\geq </math> 0 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | To solve this problem one has to add slack variables to each of the restriction to convert the inequations to equations and calculate the solution by using the simplex – algorithm (see next WIKI-entry). The graphical solution of the problem above is shown in the following picture: | ||
Version vom 24. Juni 2013, 11:36 Uhr
Inhaltsverzeichnis
Linear optimization: Formulation and graphical solution of a LP
Introduction
The linear optimization is used to solve linear programming problems. Therefore a linear objective function is optimized above an amount, which is restricted through linear equations and inequations.
Such approaches are often used in the demand management. One can use linear optimization for example for creation of production plans. Therefore one defines an amount of every product, which should be produced, to maximize the profit and minimize the costs, without violating resource restrictions. So, the objective function can be maximized or minimized depending on relevance but one has to differentiate between linear optimizations with two, three or more variables.
Linear optimization with two variables
In this case the maximization or rather minimization of an objective function works on the basis of two variables under a system of constraints, which also consist of inequalities with two variables. Thus, one get an two-dimensional solution space (x1, x2).
The mathematical formulation for general linear programming problems is composed of:
- • objective function
- • restrictions
- • condition of non negativity xj ≥ 0
Maximization
Example 1.1:
An animal feed factory produces two types of luxury animal feed. The feed C for cats and the feed D for dogs consist of the following ingredients: meat M, oats O and vegetables V. The ingredients have following amounts: M = 1500kg, O = 1200kg, V = 500kg.
Composition of the two feed sorts:
- 1kg C= 2kg M + 1kg O + 1kg V
- 1kg H= 1kg M + 1kg O
Profit per kg:
- C: 30Euro
- D: 20Euro
Assignment: Maximize the profit under the restrictions.
objective function:
- 30x1 + 20x2 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow
max!
- with x1= K und x2 = H
restrictions:
- 2x1 + x2 ≤ 1500
- x1 + x2 ≤ 1200
- x1 ≤ 500
condition of non negativity:
- x1; x2 ≥ 0
Step two: Drawing the coordinate system and chart the restrictions by calculating x1 and x2 for each of them.
Calculation:
- 2x1 + x2 ≤ 1500 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow
2*750=1500 for x1= 750, x2=0
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow
1*1500=1500 for x1=0, x2=1500
To calculate x1 and x2 for the other restrictions use the same procedure. The restriction lines build up the solution space. For maximizing the objective function the amount of the resources is limited and therefore the allowed solution space lies under the restriction lines.
(Graph 1) Step three: Drawing the budget line by choosing an arbitrary profit and solve the equation for x1 and x2 as described in step two.
(Graph 2) Step four: Parallel shift of the budget line until one reaches the last point of the solution space. This is the optimal solution of this problem, which lies usually on an intersection of restriction lines.
(Graph 3) It may occur that the ultimate intersection of the budget line and the restrictions isn’t one point but a line. In this case more than one optimal solution exists.
Minimization
It is another form of linear optimization, in which the objective function has to be minimized. The procedure for solving a minimization problem is shown in the following example.
Example 1.2
A company produces the two goods A and B in two factories. The factories are able to produce the following amount of the goods per hour:
- Good A: 10x1+20x2
- Good B: 20x1+10x2
The company receives an order of 300 units of good A and 500 units of good B. The working costs of the factory are 1000 for factory 1 and 8000 for factory 2 per hour.
Formulate the LP- problem for minimizing the total costs for the production of this order.
Step one: Mathematical formulation of the objective function and the restrictions. Objective function: min 10000x1 +8000x2
Restrictions:
- 10x1+20x2 > 300
- 20x1+10x2 >500
- x1 > 0
- x2 > 0
Step two and step three are equal to steps of the maximization. There is just one difference: The solution space at the minimization problem lies above the restrictions.
Step four: Parallel shift of the budget line until it reaches the solution space for the first time. This is the optimal solution of the problem.
Upper and lower bounds
Step one to four are equal to the steps of maximization or rather minimization. The only difference is an additional restriction concerning the maximal (upper bound) or minimal (lower bound) value of the variable x. This additional restriction constrains the solution space in two directions (up and down). The following graph shows the graphical solution of upper and lower bounds.
Linear optimization with three or more variables
Maximization or rather minimization of a linear objective function with three or more variables, restricted by linear inequations with three or more variables. The solution space is multidimensional.
Example 1.3:
A company producing cars wants to maximize its profit.
objective function:
- P=20x1+10x2+15x3
One car consists of the three factors x1, x2, x3 which are restricted by the following conditions:
restrictions:
- 3x1+2x2+5x3 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \leq
55
- 2x1+x2+x3 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \leq
26
- x1+x2+3x3 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \leq
30
- 5x1+2x2+4x3 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \leq
57
condition of non-negativity:
- x1, x2, x3 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \geq
0
To solve this problem one has to add slack variables to each of the restriction to convert the inequations to equations and calculate the solution by using the simplex – algorithm (see next WIKI-entry). The graphical solution of the problem above is shown in the following picture:
