Linear optimization: Formulation and graphical solution of a LP 1

Linear optimization: Formulation and graphical solution of a LP

Introduction

The linear optimization is used to solve linear programming problems. Therefore a linear objective function is optimized above an amount, which is restricted through linear equations and inequations.

Such approaches are often used in the demand management. One can use linear optimization for example for creation of production plans. Therefore one defines an amount of every product, which should be produced, to maximize the profit and minimize the costs, without violating resource restrictions. So, the objective function can be maximized or minimized depending on relevance but one has to differentiate between linear optimizations with two, three or more variables.

Linear optimization with two variables

In this case the maximization or rather minimization of an objective function works on the basis of two variables under a system of constraints, which also consist of inequalities with two variables. Thus, one get an two-dimensional solution space (x1, x2).

The mathematical formulation for general linear programming problems is composed of:

• objective function
• restrictions
• condition of non negativity xj ≥ 0

Maximization

Example 1.1:

An animal feed factory produces two types of luxury animal feed. The feed C for cats and the feed D for dogs consist of the following ingredients: meat M, oats O and vegetables V. The ingredients have following amounts: M = 1500kg, O = 1200kg, V = 500kg.

Composition of the two feed sorts:

1kg C= 2kg M + 1kg O + 1kg V
1kg H= 1kg M + 1kg O

Profit per kg:

C: 30Euro
D: 20Euro

Assignment: Maximize the profit under the restrictions.

Step one: Mathematical formulation of the objective function and restrictions

objective function:

30x1 + 20x2 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („<p>Während der HTTP-Anfrage ist ein Fehler aufgetreten: 404 Not Found

</p>“) von Server „http://mathoid.testme.wmflabs.org“:): \rightarrow

max!

with x1= K und x2 = H

restrictions:

2x1 + x2 ≤ 1500
x1 + x2 ≤ 1200
x1 ≤ 500

condition of non negativity:

x1; x2 ≥ 0

Step two: Drawing the coordinate system and chart the restrictions by calculating x1 and x2 for each of them.

Calculation:

2x1 + x2 ≤ 1500 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („<p>Während der HTTP-Anfrage ist ein Fehler aufgetreten: 404 Not Found

</p>“) von Server „http://mathoid.testme.wmflabs.org“:): \rightarrow

2*750=1500 for x1= 750, x2=0

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („<p>Während der HTTP-Anfrage ist ein Fehler aufgetreten: 404 Not Found

</p>“) von Server „http://mathoid.testme.wmflabs.org“:): \rightarrow 1*1500=1500 for x1=0, x2=1500

To calculate x1 and x2 for the other restrictions use the same procedure. The restriction lines build up the solution space. For maximizing the objective function the amount of the resources is limited and therefore the allowed solution space lies under the restriction lines.

Step three: Drawing the budget line by choosing an arbitrary profit and solve the equation for x1 and x2 as described in step two.

Step four: Parallel shift of the budget line until one reaches the last point of the solution space. This is the optimal solution of this problem, which lies usually on an intersection of restriction lines.

It may occur that the ultimate intersection of the budget line and the restrictions isn’t one point but a line. In this case more than one optimal solution exists.

Minimization

It is another form of linear optimization, in which the objective function has to be minimized. The procedure for solving a minimization problem is shown in the following example.

Example 1.2

A company produces two goods A and B in two factories. The factories are able to produce the following amount of the goods per hour:

Good A: 10x1+20x2
Good B: 20x1+10x2

The company receives an order of 300 units of good A and 500 units of good B. The working costs of the factory are 1000 for factory 1 and 8000 for factory 2 per hour.

Formulate the LP- problem for minimizing the total costs for the production of this order.

Step one: Mathematical formulation of the objective function and the restrictions. Objective function: min 10000x1 +8000x2

Restrictions:

10x1+20x2 > 300
20x1+10x2 >500
x1 > 0
x2 > 0

Step two and step three are equal to steps of the maximization. There is just one difference: The solution space at the minimization problem lies above the restrictions.

Step four: Parallel shift of the budget line until it reaches the solution space for the first time. This is the optimal solution of the problem.

Upper and lower bounds

Step one to four are equal to the steps of maximization or rather minimization. The only difference is an additional restriction concerning the maximal (upper bound) or minimal (lower bound) value of the variable x. This additional restriction constrains the solution space in two directions (up and down). The following graph shows the graphical solution of upper and lower bounds.

Linear optimization with three or more variables

Maximization or rather minimization of a linear objective function with three or more variables, restricted by linear inequations with three or more variables. The solution space is multidimensional.

Example 1.3:

A company producing cars wants to maximize its profit.

objective function:

P=20x1+10x2+15x3

One car consists of the three factors x1, x2, x3 which are restricted by the following conditions:

restrictions:

3x1+2x2+5x3 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („<p>Während der HTTP-Anfrage ist ein Fehler aufgetreten: 404 Not Found

</p>“) von Server „http://mathoid.testme.wmflabs.org“:): \leq

 55

2x1+x2+x3 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („<p>Während der HTTP-Anfrage ist ein Fehler aufgetreten: 404 Not Found

</p>“) von Server „http://mathoid.testme.wmflabs.org“:): \leq

26

x1+x2+3x3 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („<p>Während der HTTP-Anfrage ist ein Fehler aufgetreten: 404 Not Found

</p>“) von Server „http://mathoid.testme.wmflabs.org“:): \leq

30

5x1+2x2+4x3 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („<p>Während der HTTP-Anfrage ist ein Fehler aufgetreten: 404 Not Found

</p>“) von Server „http://mathoid.testme.wmflabs.org“:): \leq

57


condition of non-negativity:

x1, x2, x3 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („<p>Während der HTTP-Anfrage ist ein Fehler aufgetreten: 404 Not Found

</p>“) von Server „http://mathoid.testme.wmflabs.org“:): \geq

0


To solve this problem one has to add slack variables to each of the restriction to convert the inequations to equations and calculate the solution by using the simplex – algorithm (see next WIKI-entry). The graphical solution of the problem above is shown in the following picture:

The optimal solution is P= 268, when x1=1,8 ; x2=20,8 and x3=1,6 which is marked by point I in the graphical solution. The values of the slack variables are s1=0, s2=0,s3=2,6 and s4=0. One gets the values out of the simplex tableau.

Literature

Skript "Operations Research"

Gert, Heinrich, Operations Research, München 2007