Linear optimization: Formulation and graphical solution of a LP 3
Inhaltsverzeichnis
Introduction
Linear optimization is one of the main proceedings to solve linear programming problems and is used as a tool to make optimal decisions in complex production scheduling.
Field of application
This method was first mentioned in 1939 and was then used by the military to optimize military operations. Today it is represented in almost every optimization process (for example in product manufacturing to achieve the greatest profit). Furthermore linear optimization is also used in “game theory” to determine the optimum of mixed strategies. In addition it is used in the food industry in order to achieve an ideal balance of nutrients when at the same time the cost should be as low as possible. There are many other fields of application. Especially in economy, technology and management linear optimization is a very important tool to achieve the highest possible efficiency. With this method it is possible to calculate maxima and minima of a linear objective function considering the restrictions which are given by linear inequalities and equations. The maxima usually represent profit (of the company), while the minima represent the cost.
Mathematical formulation
We’re looking for an optimal solution, that fulfills specific linear restrictions:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): a_1x_1+ b_1x_2 +... + n_1x_n \leq B_1
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): a_2x_1+ b_2x_2 +... + n_2x_n \leq B_2
.
.
.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): a_nx_1+ b_nx_2 + ... + n_nx_n \leq B_n
Under these conditions, you generally want your objevtive function to be maximized:
Additionally, you assume that your decision variables are positive, that's why you have to formulate the non-negativity restriction for all of them:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1, x_2, ..., x_n\geq 0
Graphical solution
To solve a LP, you need to visualize the solution space, which is determined by the restrictions, and find the point, where the objective function is tangent to the whole solution space.
There are several steps to solve such a problem graphically:
1. Set up the objective function
2. Set up restrictions as inequations
3. Plot restrictions and objective function
4. Shift to the right/left of the objective function, until you reach the outermost tangent point of the solution space
5. Insert optimal combination in objective function
Example 1 with two variables:
We’re producing two goods ( and ) on two machines with a maximal capacity of 100h on machine 1 and 120h on machine 2. For the production, needs 4h on machine 1 and 3h on machine 2. needs 2h on machine 1 and 6h on machine 2. It costs us 3€ per piece to produce , and 2€ per piece to produce . Each of them, and , gives profit of 6€.
Now we’re in charge to find the optimal production plan to maximize the profit underneath the capacity restrictions.
Formulation of the given problem:
Objective function :
(DB) :
Restrictions:
(1) : Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 4x_1 + 2x_2 \leq 100
(2) : Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 3x_1 + 6x_2 \leq 120
Non-negativity restriction:
(3) : Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1,x_2 \geq 0
To visualize the solution space, the linear restrictions have to be drawn in a graph that represents the producing amounts of and .
Inside of this, every combination of and is feasible, but we are looking for an optimal solution. Therefore, we need to draw in the objective function and slide it parallely, until it is tangent to the solution space. This is the point of optimal solution, it shows the combination of and that brings the maximal profit:
The graphical solution brings out the following amounts of production:
According to our objective function, we have an optimal solution with a profit of 100€ per piece.
Special cases
In addition to that general example, there are special cases, that can easily be reduced to the standard problem and be solved with the same procedure.
4.1 Upper / lower bounds
Our example can be extended by an additional restricition that consists of a reverse inequality, different from the others: Restriction (4): The amount of has at least to be 5 pieces.
(4) : Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_2 \geq 5
This limits the solution space as presented in the following graph:
The only difference to the other restrictions is, that this one limits our solution space with a lower bound. The general form consists of upper bounds, but the way of solution is still the same. Draw in the objective function and slide it parallely until it is tangent to the modified solution space:
This restriction limits our solution space, but doesn’t change our optimal solution.
.
To make it more clear, our example gets extended by one more restriction.
Restriction (5): The amount of is limited to 8. (upper bound)
(5) : Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1 \leq 8
The solution space gets limited again and as the graph shows, the point where the objective function is tangent to it changed here. Under these conditions, the optimal production plan consists of the following amounts.
.
4.2. Minimization / Maximization
As mentioned above, the objective function is generally wanted to be maximized, as far as it represents any profit. However, sometimes it represents values that are wanted to be minimized like time or costs. In this case, the method of minimization is very similar to the method of maximization. There are restrictions that create a solution space by focussing on lower bounds. If there are no upper bounds, it is feasible that the solution space is infinite. To keep the restriction from example 1, they are simply adapted to the minimization problem in this case.
Objective function:
(c) :
Restrictions:
(1) : Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 4x_1 +2x_2 \geq 100
(2) : Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 3x_1 + 6x_2 \geq 120
(4) : Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_2\geq 5
Non-negativity restriction:
(3) : Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1, x_2\geq 0
Draw in the objective function and slide it parallely until it is tangent to the solution space. The optimal solution here brings a optimal amount of.
.
4.3. More than 2 decision variables
The problem can be formulated mathematically with as much decision variables as wanted, without any problems (see mathematical formulation). The graphical solution comes to its limits by trying to solve the linear programm in three dimensions. The more complex the problem is, the more unclear the visualization gets. The line of action is similar to the general problem with two decision variables. The solution space gets created by planes of the restrictions and the three-dimensional objective function has to be shifted parallelly. It goes along with the standard problem, but is more difficult to solve graphically.
Sources
- Script Operations Research TU Kaiserslautern, SS2013, Prof. Dr. Oliver Wendt
-http://www.enzyklopaedie-der-wirtschaftsinformatik.de, Stand:27.06.2013
-Script Operations Research TU München, SS2011, Prof. Dr. Martin Moog
