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

Aktuelle Version vom 7. Juli 2013, 09:43 Uhr

LP: 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 (${\displaystyle =}$) 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}}$)

LP: 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).

LP: Mathematical Formulation

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

1) Target function (a.k.a Objective function)

Assume that you want to find out how much of your products x${\displaystyle _{j}}$ you have to use (each!) to maximise your total Profit. Then you have to create your target function first:

Max! P ${\displaystyle =}$ ∑${\displaystyle _{j}}$ (( e${\displaystyle _{j}}$ – c${\displaystyle _{j}}$ ) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): *

x${\displaystyle _{j}}$ ) - c${\displaystyle _{f}}$  ${\displaystyle =}$  ∑${\displaystyle _{j}}$  ( p${\displaystyle _{j}}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): *
x${\displaystyle _{j}}$ ) - c${\displaystyle _{f}}$

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 x${\displaystyle _{j}}$(Now stands in front or in the back of the sentence). 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 ${\displaystyle _{j}}$ = 1,...,n (Determines the number of items which are included als variables in the model) Example: x${\displaystyle _{1}}$ and x${\displaystyle _{2}}$ (${\displaystyle _{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

c${\displaystyle _{f}}$ = 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:

∑${\displaystyle _{j}}$ a${\displaystyle _{i}}$${\displaystyle _{j}}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): *

x${\displaystyle _{j}}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \leq
b${\displaystyle _{i}}$

Note: If you want to solve the LP with Simplex, only equations are allowed. Therefore you just have to add the slack-variable y${\displaystyle _{i}}$ and to replace the Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \leq

or Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \geq
with an ${\displaystyle =}$. The slack-variables y${\displaystyle _{i}}$ will later describe your unused capacity or your left in stock items. Then you get:

y${\displaystyle _{i}}$ + ∑${\displaystyle _{j}}$ a${\displaystyle _{i}}$${\displaystyle _{j}}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): *

x${\displaystyle _{j}}$ ${\displaystyle =}$ b${\displaystyle _{i}}$ 

index ${\displaystyle _{j}}$ = 1,...,n (as before)

index ${\displaystyle _{i}}$ = 1,...,n (Determines the number of capacity restrictions in the model) Example: b${\displaystyle _{1}}$, b${\displaystyle _{2}}$ and b${\displaystyle _{3}}$ (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.(In the last step would sound better) 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:

∑${\displaystyle _{j}}$ x${\displaystyle _{j}}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \geq

0

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

∑${\displaystyle _{i}}$ y${\displaystyle _{i}}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \geq

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 x${\displaystyle _{j}}$ or capacity b${\displaystyle _{i}}$ in your production. Then your have to add the restriction(s):

x${\displaystyle _{i}}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \geq

"minimal number to produce/sale"

or

b${\displaystyle _{i}}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \geq

"minimal number to use"

Further, sometimes your sold/produced items x${\displaystyle _{i}}$ consist of other pre-products. Let's say that you product x${\displaystyle _{i}}$ consists of m parts of pre-product x${\displaystyle _{a}}$ and of n parts of pre-product x${\displaystyle _{b}}$. Then you have to add the equation:

x${\displaystyle _{i}}$ ${\displaystyle =}$ m Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): *

x${\displaystyle _{a}}$ + n * x${\displaystyle _{b}}$

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

LP: Example 1

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

You have the following restrictions:

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

Budget: 78.000 €

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

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

objective function: ${\displaystyle Max!Z:2x_{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 78.000 €. 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  ${\displaystyle 120m^{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.): \rightarrow
the maximal area you can use for product ${\displaystyle x_{1}}$ is  ${\displaystyle 40m^{2}}$

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

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

LP: Example 2

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

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

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

objective function: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Max! Z: (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

LP: Next steps

The LP can be solved now by different ways:

1) graphically

2) with Simplex Algorithm

In the following articles you can see how these 2 principles work.

TSP: Travelling Salesman Problem

The travelling salesman problem (TSP) or travelling salesperson problem asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? The TSP is important in operations research and theoretical computer science. The transportation problem is further a special case of the MaxFlow problem. The optimum transport mapping of a homogeneous good x has to be determined. There are supply-places i which offer a range of ai units of product x, and j demand places with a demand of bj units, keeping in mind that always the rule “supply = demand” has to be true. (ai and bi should be formatted as you did before) Now the task is to distribute the transport of the offer amounts to the demand locations so that transport costs cij are minimal. sounds like german sentence structure (Now the task is to transport the offer amounts to the demand locations under minimal transport costs cij.)

Example: To explain this a little clearer, let us take a simplified example, that the city of Hamburg needed 3 new park benches for pedestrian paths along the lake. The XY Company, which produces the park benches, has offices in Bremen, Munich and Kaiserslautern, where the identical benches would be provided. Let's say that the distance from our current postition to Bremen is the shortest one. Than it quickly becomes clear that the transport of Bremen would be the cheapest because the removal is shorter by a multiple than the other branches. However, the transport costs may be based in real problems of many factors, and not only on the distance.

TSP: Mathematical Formulation

a_i : amount of supply at supply-destination i (i=1,...,m)
b_j : amount of demand at demand-destination j (j=1,...,n)
c_ij : costs of transportation for each unit from supply-destination i to demand-destination j
x_ij : amount of stuff which hast o be transported from i to j

  
Min! K = ∑i ∑j cijxij
      
 ∑j xij = ai  for all i
      
 ∑i xij = bj  for all j
             
    xij ≥ 0   for all i,j
      
A feasible solution only exists, if:
            
  ∑i ai = ∑j bj

AP: Assignment Problem

The assignment Problem (AP) is a special case of the TSP where all supply and demand quantities are equal to one (1st formula). Furthermore, there are as many places for supply as for demand available (2nd formula). The solution is to find the cost optimal distribution of the quantities.

AP: Mathematical Formulation

These special formulas have to be added to the original TSP-Problem:

a${\displaystyle _{i}}$ = 1  ; b${\displaystyle _{j}}$ = 1

∑_i = ∑_j

Sources

http://www.techfak.uni-bielefeld.de/ags/wbski/lehre/digiSA/WS0304/IntAlg/Folien/lp-slides.pdf

http://de.wikipedia.org/wiki/Lineare_Optimierung

http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

https://bisor.wiwi.uni-kl.de/orwiki/

Authors: Julian Dörrenbächer and Pascal Rübel