Ein Problem aus der Stahlindustrie

Zusammenfassung

Ein reales Problem aus der Stahlindustrie wird als mathematische Frage formuliert. Das in der Praxis verwendete Lösungsverfahren wird als Satz vorgeschlagen und begründet. Ein Beweis steht aus.

Inhalt

1 Einführung
*
2 Formulierung des mathematischen Problems *
3 Erster Algorithmus *
4 Versuch eines Satzes *
5 Geometrische Darstellung (Situation 1) *
6 Geometrische Darstellung (Situation 2) *
7 Geometrische Darstellung (keine Lösung) *
8 Funktion der Schnittlänge *
9 Formulierung von Satz 1a *
10 Formulierung von Satz 1b *
11 Algorithmus 2 *
12 Zum Beweis von Satz 1 *
13 Nachwort *
  1. Einführung

    Stahl wird in Coils verkauft. Ein Coil ist ein aufgerolltes Blech, wie eine Rolle Klopapier, aber aus Stahl. Daraus stanzen und formen Automobilfirmen dann Karosserieteile.

    Bei der Bestellung geben die Kunden an, wie schwer ein Coil mindestens und höchstens sein darf. Beispiel: zwischen 2 und 3 t. Diese Beschränkungen seitens der Kunden haben z.B. damit zu tun, daß die maximale Traglast eines bestimmten Krans beim Kunden 3 t beträgt (Maximum). Das minimale Gewicht legt der Kunde nach den Gegebenheiten seiner Produktion fest, damit nicht zu häufig ein neues Coil eingesetzt werden muß. Der Wechsel kostet nämlich Zeit.
    Für den Kunden wäre es optimal, wenn alle Coils genau das Maximalgewicht hätten. Aber auch der Kunde weiß, daß die Stahlproduktion einen gewissen Spielraum erforderlich macht. Man wird gleich mehr dazu erfahren.

    Nun erfolgt die Herstellung des Stahls im Stahlwerk und in den Walzwerken nicht in so kleinen Gewichtseinheiten. Typischerweise werden im Stahl- und Walzwerk Coils mit Gewichten zwischen 20 t und 30 t erzeugt (wobei die genauen Gewichtsgrenzen von der Bauart des Stahlwerks abhängen). Die großen Coils werden vor der Lieferung an den Kunden auf die gewünschten Coilgewichte unterteilt.

    Für die Planung und Optimierung der Produktion im Stahlwerk ergibt sich die Aufgabe, Coils herzustellen, die ein ganzzahliges Vielfaches der Kundengewichte sind.

    Beispiel: Kunde bestellt Coils zwischen 2 t und 3 t. Produktionsmöglichkeit im Stahlwerk liegt zwischen 18 t und 23 t.

    Lösungen: 9 * 2 t = 18 t oder 7 * 3 t = 21 t

    Aber die Produktion im Stahlwerk hat auch ihre Toleranzen. Die theoretischen Gewichte liegen zwischen 18 t und 23 t, aber in der Praxis schwankt das Gewicht eines Abgusses um einige Tonnen nach oben oder unten. Das Intervall [ 18, 23 ] ist im Sinne der Normalverteilung nicht mehr als der 95 %-Bereich.

    Darum ist es riskant, genau das 9-fache Kundengewicht, also die 18 t anzupeilen. Sollten nur 17 t hergestellt werden, dann erhält man daraus 8 * 2 t und einen Rest von 1 t, den man dem Kunden nicht liefern darf.

    [Möglicher Einwand: Warum macht man denn nicht 7*2t+1*3t ? Antwort: Der Kunde bestellt viele Coils, insgesamt z.B. 500 t. Das ist ein Auftrag, für den nur eine Teilungsvorschrift gelten soll. Es besteht nicht die Möglichkeit jedes Coil zu wiegen und dafür eine besondere Teilungsvorschrift auszurechnen. Zumindest will man das nicht tun, denn das würde den Erzeugungsprozeß verlangsamen (evtl. hat man dafür auch nicht die Wiegemöglichkeit und die Rechnerprogramme).]

    Die Lösung 7 * 3t ist der Lösung 9 * 2t also vorzuziehen, weil sie mehr in der Mitte des produzierbaren Mengenbereichs liegt.

    Welches ist nun die optimale Vorgabe für das Erzeugungsgewicht und den Teilungsfaktor?

    Nach Meinung der Praktiker ist eine Lösung um so besser, je größer der Überlappbereich zwischen einem Vielfachen des vom Kunden vorgegebenen Gewichtsintervalls und dem Intervall für die Erzeugungsmöglichkeit des Stahlwerks ausfällt.

  2. Formulierung des mathematischen Problems

    Was ist nun das mathematische Problem?

    Gegeben seien zwei Intervalle: [a,b] und [x,y] reeller Zahlen mit 0<a<b und 0<x<y
    Gesucht ist ein keN mit l( [ka,kb]Ç [x,y] )= max!

    Bezeichnung: l(I) bezeichne die Länge des Intervalls I, berechnet in kanonischer Weise. Und für die leere Menge ist l(Æ )=0.

    Beispiel 1:

    [a.b] = [6.6 , 8.8]

    [x,y] = [ 17.1 , 20.2 ]

    Mit k=1 ist l( [1*6.6,1*8.8] Ç [ 17.1 , 20.2 ] ) = l( [6.6 , 8.8 ] Ç [ 17.1 , 20.2 ] ) = 0

    Mit k=2 ist l( [2*6.6,2*8.8] Ç [ 17.1 , 20.2 ] ) = l( [13.2 , 17.6 ] Ç [ 17.1 , 20.2 ] ) = 0.5

    Mit k=3 ist l( [3*6.6,3*8.8] Ç [ 17.1 , 20.2 ] ) = l( [19.8 , 26.6 ] Ç [ 17.1 , 20.2 ] ) = 0.4

    Mit k=4 ist l( [4*6.6,4*8.8] Ç [ 17.1 , 20.2 ] ) = l( [26.4 , 35.2 ] Ç [ 17.1 , 20.2 ] ) = 0

    Das Beispiel zeigt bereits einen einfachen (iterativen) Lösungsansatz: Beginne mit k=1 und probiere dann alle weiteren natürlichen Zahlen durch. Berechne jeweils die Schnittlänge. Das k mit maximaler Schnittlänge ist die gesuchte Lösung.

    Aber leider bricht dieses Verfahren nicht notwendig ab, bzw. wann soll man abbrechen?

     

    Beispiel 2:

    [a.b] = [6.6 , 6.7]

    [x,y] = [ 21.0 , 25.0 ]

    Mit k=1 ist l( [1*6.6, 1*6.7] Ç [ 21.0 , 25.0 ] ) = l( [6.6 , 6.7 ] Ç [ 17.1 , 20.2 ] ) = 0

    Mit k=2 ist l( [2*6.6, 2*6.7] Ç [ 21.0 , 25.0 ] ) = l( [13.2 , 13.4 ] Ç [ 17.1 , 20.2 ] ) = 0

    Mit k=3 ist l( [3*6.6, 3*6.7] Ç [ 21.0 , 25.0 ] ) = l( [19.8 , 20.1 ] Ç [ 17.1 , 20.2 ] ) = 0

    Mit k=4 ist l( [4*6.6, 4*6.7] Ç [ 21.0 , 25.0 ] ) = l( [26.4 , 26.8 ] Ç [ 17.1 , 20.2 ] ) = 0

    usw.

    Zunächst einmal fehlt eine notwendige Bedingung für die Existenz einer Lösung k mit nichtleerer Schnittmenge.

    Bezeichnungen: Mit { } bezeichne ich die kleinste ganze Zahl größer gleich.

    Mit [ ] bezeichne ich die größte ganze Zahl kleiner gleich.

    Beispiel 3: { 3.2 } = 4 und { 3 } = 3 sowie { -2.1 } = -2

    [ 3.2 ] = 3 und [ 3 ] = 3 sowie [ -2.1 ] = -3

    Notwendige Bedingung: Die Schnittmenge von zwei Intervallen [ka,kb] und [x,y] ist nicht leer, wenn ka<=y und kb>=x.

  3. Erster Algorithmus

    Mit der Notwendigen Bedingung kann man eine Lösung mit folgendem Algorithmus bestimmen:

    Algorithmus 1:

    1. Wähle n := { x/b} und setze k := 0 und lS := 0
    2. Wenn n > y/a gehe zum Ende.
    3. Bestimme die Länge ln der Schnittmenge von [na,nb] und [x,y]>
    4. Wenn ln > lS setze lS := ln und k:= n
    5. Setze n := n + 1 und gehe zu (2).
    6. Ende: Wenn k := 0 und lS := 0, dann gibt es keine Lösung. Sonst ist der optimale Faktor k und die zugehörige Schnittlänge lS gefunden.

    Vom praktischen Standpunkt ist dieser Algorithmus schon ausreichend, denn in der Praxis werden jeweils nur wenige Iterationen nötig sein.

    Aber es gibt auch ("höchstwahrscheinlich") ein Lösungsverfahren mit nur einem Schritt.

  4. Versuch eines Satzes
  5. Satz 1: k = { (x+y-a)/(a+b) } realisiert das Maximum, wenn x/b <= k <= y/a
    Ansonsten (wenn k>y/a oder k<x/b) ist die Schnittmenge für alle k leer.

    Beispiel 4: Mit den Zahlen aus Beispiel 1 erhält man x/b = 1.94318.... und y/a = 3.06..
    Ganzzahlige Lösungen sind also k= 2 und k = 3.

    Um Satz 1 zu begründen, werde ich das Problem graphisch darstellen.

  6. Geometrische Darstellung (Situation 1)
  7. Abbildung 1

    In Abbildung 1 sind die Intervalle [ a, b ] und [ x, y ] eingezeichnet. Die Multiplikation des Intervalls [ a, b ] mit beliebigen keN ergibt anschaulich eine sich öffnende Schere aus den Geraden ak und bk. Der blau schraffierte Bereich zeigt die Schnittmenge zwischen [ka,kb] und [x,y]. Die Länge des Schnittbereichs entspricht dem vertikalen Abstand zwischen der x-Geraden und der y-Geraden innerhalb des schraffierten Bereichs.

    Die 4 Ecken des schraffierten Vierecks haben die Koordinaten (x/b,x), (y/b,y), (x/a,x) und (y/a,y).

    Durch andere Lage von a, b und/oder x,y ergibt sich (leider) eine andere mögliche Reihenfolge der 4 Eckpunkte, nämlich: x/b < x/a < y/b < </a.

  8. Geometrische Darstellung (Situation 2)
  9. Abbildung 2

    In Abbildung 1 ist die Schnittlänge zwischen y/b und x/a maximal, nämlich gleich y-x.

    In Abbildung 2 ist die Schnittlänge genau bei y/b maximal, denn die Steigung der Geraden ka ist kleiner als die der Geraden kb, und das bedeutet, daß links von y/b die Schnittlänge schneller fällt.

    Bei dieser Überlegung ist die Ganzzahligkeit noch unberücksichtigt.

    Eine ganzzahlige Lösung gibt es in der Situation der Abbildung 1 genau dann, wenn das Intervall [y/b,x/a] eine ganze Zahl enthält. In der Situation der Abbildung 2 gibt es nur dann eine ganzzahlige Lösung für den (theoretischen) Maximalwert, wenn zufällig y/b eine ganze Zahl ist. Wenn nun aber y/b keine ganze Zahl ist, dann muß eine ganze Zahl in der Nähe gesucht werden. Aufgrund der Steigungen der Geraden ka und kb kommen nur die Werte [y/b] und {y/b} in Betracht, also die größte ganze Zahl kleiner gleich y/b und die kleinste ganze Zahl größer gleich y/b.

  10. Geometrische Darstellung (keine Lösung)
  11. Allerdings muß dann wenigstens einer der Werte [y/b] und {y/b} einen Bildpunkt innerhalb der Schere haben. Die folgende Abbildung 3 zeigt eine Situation ohne Lösung:

    Abbildung 3

    Hier liegen a und b zu nah beieinander. Eine Kundenbestellung mit so engem Lieferspielraum für das Coilgewicht ist ein Unglück für das Stahlunternehmen, denn entweder akzeptiert man diese Vorgaben und produziert teilweise für den Schrott oder man versucht durch Rücksprache mit dem Kunden diesem einen größeren Lieferspielraum abzugewinnen.

  12. Funktion der Schnittlänge
  13. Mit einer Fallunterscheidung gelingt es, die unterschiedlichen Schnittlängen lS zu beschreiben (für alle Situationen):

    Für Abbildung 1:

    Und lS als Graph:

    Abbildung 4: Schnittlänge lS (rote Kurve)

    Für Abbildung 2:

    Und der Graph:

    Abbildung 5: Schnittlänge lS (rote Kurve)

    In beiden Fällen ist lS eine stückweise lineare Funktion.

    In beiden Fällen liegt die beste rationale Lösung bei y/b. Genauer: im ersten Fall gibt es mehrere Lösungen, die das Maximum y-x realisieren, aber y/b ist eine davon, nämlich die kleinste darunter. Die Wahl von y/b als Lösung entspricht auch den Anforderungen der Produktion im Stahlwerk, denn wenn mehrere Lösungen existieren, dann wird die kleinste bevorzugt (weil man dann weniger Teilungsvorgänge durchführen muß).

    Die Lösung y/b ist i.d.R. nicht ganzzahlig.Wenden wir uns jetzt dem Problem zu, ein ganzzahliges k mit optimalen Eigenschaften zu bestimmen. Wenn y/b nicht ganzzahlig ist, dann liegen rechts und links davon zwei ganze Zahlen. Eine davon wird die Lösung sein. Wir müssen entscheiden, wann man die optimale ganzzahlige Lösung rechts bzw. links von y/b findet.

  14. Formulierung von Satz 1a
  15. In Abbildung 1 verlängere ich die steilen Geraden nach oben und erhalte einen Schnittpunkt, der zwischen y/b und x/a liegt. Den Lotpunkt von diesem Schnittpunkt auf die Ordinate nenne ich P.

    Abbildung 6: lS

    Berechne nun die Koordinaten von P durch Gleichsetzen der beiden Geradengleichungen:

    bk-x = -ak+y => k = (x+y) / (a+b)

    Auch (x+y)/(a+b) ist eine optimale rationale Lösung. Entweder ist die größte ganze Zahl kleiner gleich (x+y)/(a+b) oder die kleinste ganze Zahl größer gleich (x+y)/(a+b) eine ganzzahlige optimale Lösung. Wenn man von P eine Einheit nach rechts geht, dann wird lS‘ um a kleiner. Geht man eine Einheit nach links, wird lS um b kleiner. Bezeichne nun mit dr und dl den Abstand von P zur rechten bzw. linken ganzen Zahl. Wenn dr *a < dl *b, dann ist es besser nach rechts zu gehen, denn man verliert weniger, als wenn man nach links ginge. Nach Konstruktion ist dr = 1- dl. Untersuchen wir die Gleichheit von dr *a = dl *b

    => (1-dl) *a = dl *b

    => dl = a / (a+b)

    Wenn also der Abstand von P zur nächst größeren ganzen Zahl kleiner a / (a+b) ist, dann gehe man nach rechts, sonst nach links.

    Diesen Sachverhalt kann man in die Formel k = (x+y) / (a+b) direkt einbauen.

    Nämlich: k* = { (x+y) / (a+b) - a / (a+b) } ist die optimale Lösung.

    Satz 1a (Unterfall von Satz 1):
    Wenn y/b <= x/a, dann realisiert k* = { (x+y-a) / (a+b) } das Maximum,
    sofern x/b <= k* <= y/a.
    Ansonsten (wenn k* > y/a oder k*<x/b) ist die Schnittmenge für alle keN leer.

    Begehe ich aber nicht einen Fehler, wenn ich hier lS’statt lS optimiere?

    Nein, denn lS‘ war nur eine Hilfsgröße, mit der entschieden werden konnte, ob man nach rechts oder links zur nächsten ganzen Zahl gehen muß. Die Entscheidung hängt vom Verhältnis der Zahlen a und b (als Steigungen von Geraden) ab. Wenn man mehr als a/(a+b) nach rechts gehen muß, dann ist die dadurch verursachte Abnahme der Schnittlänge größer als wenn man nach links gegangen wäre. Sollte man sich im flachen Bereich der Kurve befinden, dann ist es gleich, ob man nach links oder nach rechts geht.

    Der Punkt P teilt das senkrechte Geradenstück genau im Verhältnis b : a. Darum befindet man sich auch dann noch über dem flachen Geradenstück, wenn man von P aus um a/(a+b) nach links geht.

  16. Formulierung von Satz 1b
  17. Nun zur Situation 2 (Aus Abbildung 2). Hier ist x/a < y/b.

    Abbildung 7

    Satz 1b (Unterfall von Satz 1):
    Wenn x/a <= y/b, dann realisiert k* = { (x+y-a) / (a+b) } das Maximum,
    sofern x/b <= k* <= y/a.
    Ansonsten (wenn k* > y/a oder k* < x/b) ist die Schnittmenge für alle keN leer.

    Genau wie im ersten Fall konstruiere ich den Schnittpunkt der beiden Geraden bk-x und –ak+y. Das Lot auf die Ordinate ergibt P. P hat die oben bereits angegebenen Koordinaten ((x+y)/(a+b),0).

    Die Steigung des mittleren Geradenstücks ist nun aber nicht 0, sondern (b-a). Was ändert sich dadurch. Eigentlich nichts, denn auch oben schon hatten wir lS‘ statt lS betrachtet.

    Seien wie oben dr und dl die horizontalen Abstände von P zu den benachbarten ganzen Zahlen.

    Nach Konstruktion ist dr = 1- dl. Untersuchen wir die Gleichheit von dr *a = dl *b

    => (1-dl) *a = dl *b

    => dl = a / (a+b)

    Wenn also der Abstand von P zur nächst größeren ganzen Zahl kleiner a / (a+b) ist, dann gehe man nach rechts, sonst nach links.

    Beispiel 5: Die Berechnung liefert bisher immer das richtige Ergebnis.

    Abbildung 8

    Die optimale Lösung ist der Punkt rechts von P. Der Wert von (x+y-a)/(a+b) ist 4.036. Folglich ist k* = 5.

  18. Algorithmus 2

    Aus den bisher vorgestellten Überlegungen ergibt sich der

    Algorithmus 2:

    1. Berechne k := { (x+y-a) / (a+b) } und pruefo := y/a und pruefu := x/b
    2. Wenn pruefu <= k <= pruefo, dann ist k die optimale ganzzahlige Lösung.
      Ansonsten gibt es keine Lösung.
      Ende.

    Soweit die Begründung für die Berechnungsvorschrift aus Satz 1.

    An dieser Stelle bin ich voller Überzeugung, aber der Beweis steht noch aus. Das Verfahren nach Algorithmus 2 wird seit einigen Jahren in einem Stahlunternehmen angewendet. Bisher gibt es keine Klagen.

  19. Zum Beweis von Satz 1

    Satz 1 ist äquivalent zu Satz 1a und Satz 1b.

    Zeige zuerst Satz 1a.

    Satz 1a (Unterfall von Satz 1):
    Wenn y/b <= x/a, dann realisiert k* = { (x+y-a) / (a+b) } das Maximum,
    sofern x/b <= k* <= y/a.
    Ansonsten (wenn k* > y/a oder k* < x/b) ist die Schnittmenge für alle keN leer.

    1. Auf die Bedingung x/b <= k* <= y/a kann nicht verzichtet werden.
      Ein Beispiel: [ a, b ] = [ 3, 3.9 ], [ x, y ] = [ 4, 5 ]. Es ergibt sich k* = { 0.89.. } = 1, aber 1 ist kleiner als x/b = 1.02...
      Ein Beispiel für den Fall, daß k*>= x/b und k* >= y/a suche ich noch.
    2. Nächster Beweisteil: Wenn k* nicht zwischen x/b und y/a liegt, dann liegt auch keine andere ganze Zahl in diesem Intervall, sprich:
      Wenn k*<x/b oder k*>y/a, dann enthält das Intervall [ x/b, y/a ] keine ganze Zahl.
    3. Letzter Beweisschritt: k* ist wirklich das ganzzahlige Optimum.

    Satz 1b wäre dann auch noch zu zeigen.

  20. Nachwort

    Für Hinweise auf Fehler oder Tipps zur Vervollständigung dieser Arbeit wäre ich dankbar.


    Zurück zum Seitenanfang


    Martin Wohlgemuth für Matroids Matheplanet 11.7.2001.
    [Zeichnungen wurden mit Euklid-Dynageo erstellt.]
    Mehr von Matroid [Über Fraktale und mathematische Kunst] [Volumenberechnung eines Ringes mit konstanter Höhe] [Lösung von Extremwertaufgaben mit Differentialrechnung] [Über Fraktale und mathematische Kunst] [Über die Anzahl von Sitzordnungen am runden Tisch] [Schachbrettaufgaben]