Linear optimization: Formulation and graphical solution of a LP 3
1. 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 introduced/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.
2. 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
3. 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 (x1 and x2) on two machines with a maximal capacity of 100h on machine 1 and 120h on machine 2. For the production, x1 needs 4h on machine 1 and 3h on machine 2. X2 need 2h on machine 1 and 6h on machine 2. It costs us 3€ per piece to produce x1, and 2€ per piece to produce x2. Each of them, X1 and X2, 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 : maximize C = 3x1 + 4x2 (DB)
Restrictions:
4x1 + 2x2 <= 100 (1)
3x1 + 6x2 <= 120 (2)
Non-negativity restriction: x1,x2 >= 0 (3)
To visualize the solution space, the linear restrictions have to be drawn in a graph that represents the producing amounts of x1 an x2.
