Linear optimization: Mathematical formulations of problems presented in the course 1

1) 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 (> ; >= ; <= ; <)

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: x^1)

2) 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).

3) 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 example.

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 ) - kf = ∑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 product j

c = costs to produce product j

p = e-c = profit of selling product j

x = amount of your product j

kf = fix costs (You only need this if there are existing fix costs)

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

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

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/in stock i

3) Optional restrictions:

For sure there could be the restrictions that you have to use at least a minimum number of xi in your production. Then your get the restriction:

xi >= "minimal number"

Further, sometimes your sold/produced items xi consist of other pre-products. Then you have to add the equation:

xi =

MISSING CONTENT HERE

1st Example

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

You have the following restrictions:

cost per $m^{2}$ [1000€/ $m^{2}$]

clubs: 9

bags: 6

contribution margin [1000 €/$m^{2}$ ]

clubs: 2

bags: 1

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

Budget: 78000 €

x = clubs

y = bags

objective function: $max2x+y$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow

the contribution margin for clubs x is 2 and for bags y 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+6y\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+y\leq 120

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

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x,y \geq 0

4) 2nd Example:

A company makes two products (X and Y) using two machines (A and B). Each unit of X that is produced requires 50 minutes processing time on machine A and 30 minutes processing time on machine B. Each unit of Y 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 X and 90 units of Y 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 X in the current week is forecast to be 75 units and for Y is forecast to be 95 units. Company policy is to maximise the combined sum of the units of X and the units of Y in stock at the end of the week.

x = number of units of X produced in the current week

y = number of units of Y produced in the current week

Restrictions:

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

machine time A: 50 minutes per product x and 24 minutes per product y 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 + 33y \leq 35*60\rightarrow

machine time B: 30 minutes per product x and 33 minutes per product y 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 \geq (75 - 30)

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

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

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow y \geq  5
so production of Y Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \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+30-75) + (y+90-95)

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