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 "=". 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)

Durch die Restriktionen werden die Begrenzungen des Modells ausgedrückt, die bei der Lösung eingehalten werden müssen. Die genutzte Kapazität einer Maschine, ausgedrückt durch das Produkt von benötigter Kapazität pro Mengeneinheit und Produktionsmenge muss kleiner sein als die Maximalkapazität. Da es sehr umständlich ist mit Ungleichungen zu rechnen, werden diese in Gleichungen überführt. Dies geschieht durch die Einführung der Schlupfvariablen, die die Leerkapazitäten der Maschinen beschreiben. Die Summe aus Leerkapazität und genutzter Kapazität einer Maschine sind dann gleich der Maximalkapazität.

4) 1st 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

Constraints:

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