Linear optimization: Mathematical formulations of problems presented in the course 1: Unterschied zwischen den Versionen

Version vom 21. Juni 2013, 17:07 Uhr

Mathematical formulations of problems presented in the course

Theoretical Characteristics of Linear Programming

Linear programming (LP) is a powerful and easy-to-use tool to solve certain types of linear optimisation problems. It is widely used in Operations Research.

The target of the LP is to maximise (max!) or minimise (min!) a target function under well-defined restrictions. It consists both of equations (=) and inequations Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (> ; \geq  ; \leq  ; <)

Notice: The fact that only linear problems can be solved leads to the consequence that all used variables in the target function as well as in the restrictions have to be in the 1st power. (Example: ${\displaystyle x^{1}}$)

Why using Linear Programming?

- LP is often used/needed in production planning processes.

- Many optimisation problems can be fomulated relatively easy as LP-model.

- LP is one of the most efficient tools to solve "Travelling-Salesman-Promlems" (TSP).

Converting a real-life problem into a LP-problem

Now the different types of variables will be explained. How they are used you will see in the attached examples.

1) Target function:

Assume that you want to find out how much of your products xj you have to use (each!) to maximise your total profit, then you have to create your target function first:

Max! P = ∑j (( ej – cj ) *xj ) - cf = ∑j (( pj*xj )

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow

As mentioned above, this is your target function. It describes now your desire to maximise your profit with your given products xj. In this case the target "Profit (P)" has to be maximised. You can minimise or maximise other stuff too, e.g. the maximum amount of ressources to use or whatever...

index j = 1,...,n (Determines the number of items which are included als variables in the model) Example: x1 and x2 (j=1;2)

e = earnings of the sale of 1 unit of product j

c = costs to produce 1 unit of product j

p = e-c = profit of selling 1 unit of product j

x = amount of your product j

cf = fix costs (You only need this if there are existing/given fix costs in your assignment.)

2) Restrictions:

After your created your target function, you have to add the restrictions of your given problem to restrict your amount of feasible solutions.

When you have a limited capacity on your machine (or something comparable), you have to make a restriction like this:

∑j aij * xj ≤ bi

Note: If you want to solve the LP with Simplex, only equations are allowed. Therefore you just have to add the slack-variable "yi" and to replace the ">=" or "<=" with an "=". The slack-variables yi will later describe your unused capacity or your left in stock items. Then you get:

yi + ∑j aij * xj = bi

index j = 1,...,n (as before)

index i = 1,...,n (Determines the number of capacity restrictions in the model) Example: b1, b2 and b3 (i=1;2;3)

a = needed capacity to use/produce 1 unit of product j

b = maximal capacity of your machine i (or how much you have in stock)

As last step it is important to mention that you never can use or produce items with a negative amount. Only positive amounts of goods can be used to get a feasible solution.

This principle is called "Non-Negativity-Condition" (NNC)

The correct restriction is then:

∑j xj >= 0

If you want to use the simplex algorithm to solve the Problem, you additionally need the inequation:

∑i yi >= 0

For easy Problems you have now done all required functions.

3) Optional restrictions:

For sure there could be some restrictions which force you to use at least a minimum number of products xj or capacity bi in your production. Then your have to add the restriction(s):

xi >= "minimal number to produce/sale" or bi >= "minimal number to produce/sale"

Further, sometimes your sold/produced items xi consist of other pre-products. Let's say that you product xi consists of m parts of xa and of n parts of xb. Then you have to add the equation:

xi = m * xa + n * xb

Now all possible functions we've learned in the course were presented above and will further be shown in 2 different examples.

1st Example

The Golf AG has an area of 120 ${\displaystyle m^{2}}$ to present their two products (golf clubs and golf bags).

You have the following restrictions:

cost per ${\displaystyle m^{2}}$ [1000 ${\displaystyle {\frac {euro}{m^{2}}}}$]

clubs: 9

bags: 6

contribution margin [1000 ${\displaystyle {\frac {euro}{m^{2}}}}$]

clubs: 2

bags: 1

Maximal area for bags: 40 ${\displaystyle m^{2}}$

Budget: 78.000 €

${\displaystyle x_{1}}$ = clubs

${\displaystyle x_{2}}$ = bags

objective function: ${\displaystyle max2x_{1}+x_{2}}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow

the contribution margin for clubs ${\displaystyle x_{1}}$ is 2 and for bags ${\displaystyle x_{2}}$ it is 1 and you want to maximize contribution margin.

Restrictions:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 9x_{1}+6x_{2}\leq 780

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow
your budget is 78000 €. So your cost have to be lower than that. The costs for clubs is 9 and for bags it is 6.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}+x_{2}\leq 120

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow
the maximal area you have to present your products is 120 ${\displaystyle m^{2}}$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}\leq 40

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

2nd Example:

A company makes two products (${\displaystyle X_{1}}$ and ${\displaystyle X_{2}}$) using two machines (A and B). Each unit of ${\displaystyle X_{1}}$ that is produced requires 50 minutes processing time on machine A and 30 minutes processing time on machine B. Each unit of ${\displaystyle X_{2}}$ that is produced requires 24 minutes processing time on machine A and 33 minutes processing time on machine B.

At the start of the current week there are 30 units of ${\displaystyle X_{1}}$ and 90 units of ${\displaystyle X_{2}}$ in stock. Available processing time on machine A is forecast to be 40 hours and on machine B is forecast to be 35 hours.

The demand for ${\displaystyle X_{1}}$ in the current week is forecast to be 75 units and for ${\displaystyle X_{2}}$ is forecast to be 95 units. Company policy is to maximise the combined sum of the units of ${\displaystyle X_{1}}$ and the units of ${\displaystyle X_{2}}$ in stock at the end of the week.

${\displaystyle x_{1}}$ = number of units of ${\displaystyle X_{1}}$ produced in the current week

${\displaystyle x_{2}}$ = number of units of ${\displaystyle X_{2}}$ produced in the current week

Restrictions:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 50x_1 + 24x_2 \leq 40*60\rightarrow

machine time A: 50 minutes per product ${\displaystyle X_{1}}$ and 24 minutes per product ${\displaystyle X_{2}}$ has to be lower than the capacity of 40 hours of machine A. 

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 30x_1 + 33x_2 \leq 35*60\rightarrow

machine time B: 30 minutes per product  ${\displaystyle X_{1}}$ and 33 minutes per product ${\displaystyle X_{2}}$ has to be lower than the capacity of 35 hours of machine B. 

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1 \geq (75 - 30)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow x_1 \geq  45
so production of Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1 \geq
 demand (75) - initial stock (30)  , which ensures we meet demand

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_2 \geq 95 - 90

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow x_2 \geq  5
so production of Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_2 \geq 
demand (95) - initial stock (90)  , which ensures we meet demand

objective function: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): max (x_1+30-75) + (x_2+90-95)

i.e. to maximise the number of units left in stock at the end of the week