$Title Graphen-Zerlegung
$Ontext

Vorlesung: Modellierung und Planung von Logistiksystemen
Abschnitt: 3.3 Konfigurationsplanung bei Zentrenfertigung
Problemstellung: Zerlegung eines Graphen in vorgegebene Anzahl an Teilgraphen so, dass Summe der Kantengewichte zwischen Teilgraphen minimal
Quelle: Tafeluebung zur Vorlesung, Aufgabe 12

 - Data -

Author: Christoph Schwindt
Date: 15/12/2019

$Offtext

sets
   i  Maschinen / i1-1, i1-2, i2, i3, i4-1, i4-2, i5-1, i5-2, i6-1, i6-2 /
   j  Produkte / j1, j2, j3, j4, j5-1, j5-2, j6 /
   p  Teilgraphen / p1*p3 / ;

alias (h,i) ;

table
   a(i,j)  Maschinen-Produkt-Matrix
          j1     j2      j4      j5-2    j5-1    j6      j3
   i2     1      1       1       1       1
   i3     1      1       1
   i5-2   1      1               1       1
   i4-2   1                      1       1       1
   i6-2   1                      1               1       1
   i1-2   1                                      1       1
   i6-1                  1               1
   i4-1                  1                               1
   i1-1                  1
   i5-1                  1                                   ;

sets
   f(h,i,j)  Maschinenfolgen / i1-2.i2.j1, i2.i3.j1, i3.i4-2.j1, i4-2.i5-2.j1, i5-2.i6-2.j1,
                               i2.i3.j2, i3.i5-2.j2,
                               i1-1.i2.j4, i2.i3.j4, i3.i4-1.j4, i4-1.i5-1.j4, i5-1.i6-1.j4,
                               i2.i4-2.j5-2, i4-2.i5-2.j5-2, i5-2.i6-2.j5-2,
                               i2.i4-2.j5-1, i4-2.i5-2.j5-1, i5-2.i6-1.j5-1,
                               i1-2.i4-2.j6, i4-2.i6-2.j6,
                               i1-2.i4-1.j3, i4-1.i6-2.j3 / ;

parameters
   d(j)    Nachfrage nach Produkt j / j1 4, j2 1, j3 4, j4 9, j5-1 1, j5-2 1, j6 6 /
   r(h,i)  Gewicht der Kante h-i ;

   r(h,i)$(ord(h)<ord(i)) = sum(j$(f(h,i,j) or f(i,h,j)), d(j)) ;

scalar
   mPrime  Maximale Anzahl an Knoten pro Teilgraph / 4 / ;

display r;