Linear optimization: Formulation and graphical solution of a LP 1
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
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.
