Linear optimization: Formulation and graphical solution of a LP 3: Unterschied zwischen den Versionen

Version vom 29. Juni 2013, 22:45 Uhr

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:

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

Additionally, you assume that your decision variables ${\displaystyle 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