Linear optimization: Formulation and graphical solution of a LP 2

Theory

Linear optimization is one of the most important instruments in OR. It is composed of several linear equations or inequations which depict the solution space. One of the equations represents the goal function, the others are restrictions. Linear optimization is used for both maximization and minimization problems (e.g. max! profit or min! costs).

You get the goal function Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Max! P= dx_{1}+ex_{2}- c_{fix}

by inserting the profit margin d, e for each product $x_{1},x_{2}$. The goal function for a minimization problem has the form $Min!C=c_{var1}x_{1}+c_{var2}x_{2}+c_{fix}$ with $c_{var}$= variable costs and $c_{fix}$= fix costs.

The restrictions have either the form $ax_{1}+bx_{2}\leqslant c$
or $ax_{1}+bx_{2}\geqslant c$
where "a" is the amount needed to produce one unit of $x_{1}$ and "b" is the amount needed to produce $x_{2}$. "C" stands for the maximal amount available.

There is a third kind of restrictions needed, which are called non- negativity restrictions. They have either the form Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}\geq 0, x_{2}\geq 0

	or 	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}, x_{2}\geq 0

and tell you, that it is not possible that the structure variables $x_{1}$ and $x_{2}$ become negative. This is, because it is impossible to produce a negative amount of $x_{1}$ respective $x_{2}$.

Now you can start plotting everything into your solution space. The abscissa is named $x_{1}$ and the ordinate $x_{2}$. To depict the inequations in the solution space you have to change the “$\leqslant$” into a “=”. Then you can easily imagine that one x = 0 to get the intersection between the restriction and the axis. After doing this for both x you can connect the two points on the axes and plot the restriction. You repeat this for all the given restrictions.
Since all points in the valid solution space (the space embedded from all restrictions) are possible solutions you need to plot the goal function at last. It shows you the optimal solution. Considering the maximization problem you insert a random number for P so you can draw the function into your solution space. Then you move the function parallel to get iso- profit lines. Every iso- profit line shows the same amount of profit, which you can reach by various amounts of $x_{1}$ and $x_{2}$. The iso- profit line where P=0 is, is also called break- even-line. On this line profit equals costs. The maximal profit is where the iso- profit line is at its maximum.

Example Maximization

A school class has 7 drivers and a budget of 325€ and wants to transport as may people as possible on a trip. The costs to rent a car are 25€ and the costs for a bus are 55€.
$x=car;y=bus$

Explanation

Goal function: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 5x + 9y \rightarrow max

Restrictions: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x + y \leq 7
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 25x + 55y \leq 325
Non negative condition: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x; y \geq 0

Solution

First we draw a coordinate system, in this system we draw the restrictions (the black and red lines). With these two lines we have opend our solution space. In this example it is the space between the x- and y-axis and the black and red lines. In the next step we consruct an iso benefit line. This is done by setting first the x in the goalfunction to zero and after this setting y to zero and draw a line between this two points in the coordinate system (the green line). After this we have to parallel shift this line until we reach a point in the solution space, because it is a maximization problem we take the point where we can shift the iso benefit line farest on the right in the solution space. In this example it is the point 5|2, which means that the optimal solution is to take 5 busses and 2 cars to transport 55 people.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Example Minimization

A school class of 47 people (7 of them have a driving license) want to go on a trip. They have the choice between cars with 5 seats and busses with 9 seats. The costs to rent a car are 25€ and the costs for a bus are 55€.
$x=car;y=bus$

Explanation

Goal function: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 25x + 55y\rightarrow min
Restrictions: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x + y \leq 7
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 9y + 5x \geq 47
Non negative condition: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x; y \geq 0

Solution

First we draw a coordinate system, in this system we draw the restrictions (the black and red lines). With these two lines we have opend our solution space. This is the area between the two lines and the x-axis. In the next step we construct an iso benefit line. This is done by setting first the x in the goalfunction to zero and after this setting y to zero and draw a line between this two points in the coordinate system (the green line). After this we have to parallel shift this line until we reach a point in the solution space, because it is a minimization problem the point nearest to the origin of the coordinate system (the point where the red lines and the blue one meet each other). In this example it is the point 3|4, what means the optimal solution is to take 3 busses and 4 cars and have to pay 265€ for this trip.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden