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:

$Max!C=c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}$

Additionally, you assume that your decision variables $x_{1},x_{2},...,x_{n}$ 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