Linieare Optimierung?

Wissenschaft Mathematik
#1

Hallo zusammen,

ich habe da mal ein Problem, zu dem ich mal eure Hilfe benötige. Ich beschreibe es an einem Beispiel:

Gegeben sind die Produkte A, B, C. Diese Produkte werden nicht allein, sondern zusammen mit einem anderen Produkt erstellt. Dabei sind nur die Gesamtzeiten bekannt. z. B.

4 x a mit 4 x b dauert insgesamt 15 Minuten
3 x a mit 1 x b dauert insgesamt 25 Minuten
2 x b mit 1 x c dauert insgesamt 16 MInuten.

Jetzt sollen die Anteiligen Produktionszeiten der Produkte A, B, C so ermittelt werden, dass die jeweiligen gemeinsamen Zeiten möglichst gut erklärt werden. Die Zeiten, die nicht erkläret werden können, sollen also möglichst klein sein. Hoffe mal, man versteht so, was ich meine.

Bisher habe ich mir überlegt, dass man diese Fragestellung mit der linearen Optimierung Lösen kann. Dazu habe ich aber noch noch keine Idee, wie das Problem entsprechend  zu formulieren wäre.

Wäre super, wenn mir da jemand auf die Sprünge helfen kann.

Vielen Dank

power_blue

#2

Hallo power_blue,

Du kannst das ganze als lineares Gleichungssystem aufstellen und auflösen:

(1) 4a + 4b = 15 |-4b
(2) 3a + 1b = 25 |-1b
(3) 2b + 1c = 16 |-2b

(1a) 4a = 15 - 4b |:4
(2a) 3a = 25 - 1b |:3
(3a) 1c = 16 - 2b

(1b) a = 3.75 - b
(2b) a = 8 1/3 - 1/3b

(1c [1b = 2b]) 3.75 - b = 8 1/3 - 1/3b |-3.75 |+1/3b

(1d) -2/3b = 4.58333… |:-2/3

(1e) b = -6.88

Da die erste Gleichung kleiner ist als die 2te, ob wohl da mehr Variablen vorkommen, lässt sich diese Gleichung nicht Lösen. Zumindest nicht mit einer positiven Bearbeitungszeit, was aber rein von der Logik nötig ist.

Liebe Grüße
Jonas

#3

a = 10.625

(Alle allein stehende Zahlen in Minuten)

#4

Hallo Jonas,

also, erst mal Danke, für die angebotene Hilfe.

Leider funktioniert das glaube ich so nicht, weil es nach meinen Recherchen um ei Ungleichungssystem und nicht um ein Gleichungssystem handelt. Die Einzelzeiten sollen natürlich alle >0 sein, das hatte ich in meiner Frage nicht beschrieben.

Im Ergebnis muss es daruf hinauslaufen, dass sich die Summenzeiten zwar nicht exakt aber möglichst gut durch die Einzelzeiten erklären lassen. Und da bin ich bei meiner Suche auf die lineare Optimierung gestoßen.

Ich bin mir aber nicht sicher, ob ich das Problem so formulieren kann, dass es sich mit linearer Optimierung lösen lässt und wie, falls es geht, ich es in ein Simplextableau überführen kann.

Grüße

powerblue

#5

Bisher habe ich mir überlegt, dass man diese Fragestellung mit
der linearen Optimierung Lösen kann.

Das macht mich etwas stutzig. Hast Du Dir das wirklich nur überlegt, oder weißt Du das (z.B. weil die Aufgabe in diesem Zusammenhang gestellt wurde)? Prinzipiell könnte das Problem ja durchaus auch nichtlinear sein.

Dazu habe ich aber noch
noch keine Idee, wie das Problem entsprechend  zu formulieren
wäre.

Für den einfachsten Fall, dass die Gesamtzeit eine Linearkombination der Zeiten für die einzelnen Produkte ist, sieht das Problem so aus

\sum\limits_{i = 1}^n {\left( {n_{a,i} \cdot k_a + n_{b,i} \cdot k_b + n_{c,i} \cdot k_c - t_i } \right)^2 } \Rightarrow Min

Dass das man für n=3 auch ohne Optimierung lösen kann, hat Jonas ja schon vorgeführt.

#6

Aus deiner Aufgabenstellung heraus kann ich da leider kein Ungleichsystem erkennen…

#7

Moin,

die Randbedingungen hast Du, allerdings mit einem kleinen Fehler: Die 2. Zeile sollte wohl heißen

3 * a + c = 25

(sonst hätten wir einen Widerspruch von Zeile 1 auf Zeile 2).

Fehlt nur noch die Zielfunktion; zu maximieren wäre also

Z = x1 * a + x2 * b + x3 * c.

Gruß Ralf

#8

Hallo zusammen,

Danke für die bisherigen Antworten.

Ich hatte mir das mit der Linearen Optimierung überlegt, bzw. gehofft, dass es damit funktionieren würde.

Das Beispiel habe ich mir selbst überlegt, momentan habe ich noch keine Daten zum testen. Es geht darum, empirische Daten solcher Art auszuwerten. Ein solcher Widerspruch in Zeile 1 und 2 kann bei der Erhebung durchaus entstehen. Wieviel Sinn das macht, sei mal dahingestellt. Ich werden mit den Daten arbeiten müssen, die ich geliefert bekomme.

Das Probem ist, möglist „gute“ Werte für die Einzelzeiten zu ermitteln. Als gut hatte ich mal definiert, dass die Einzelzeiten die Summenzeiten möglichst gut erklären.

Für den Anfang wird es 7 Produkte geben, die in allen Möglichen Kombinationen auftreten können. Falls mehr als nur ein Produkt auftritt, habe ich nur die Summenzeit für die Gesamte erstellung. Teilweise werden sicherlich auch Produkte einzeln erstellt, aber eben nicht immer.

Falls es nicht mit liniearer Optimierung geht, hat jemand eine Idee, wie ich auf anderem Weg Einzelzeiten ermitteln kann?

Grüße

powerblue

#9

Hi,

lineare Optimierung:

  1. Hauptbedingung: Eine Formel für das aufstellen was minimal oder maximal werden soll.
  2. Nebenbedingung(en): Zusätzliche Formeln aus Planfigur, Logik, Sachzusammenhang, Zahl im Text, fertige Formel im Text.
  3. Zielfunktion: Die Formeln aus 2. so in 1. rein basteln, dass eine Funktion mit nur einer Variablen entsteht.
  4. Definitionsbereich: Wie groß klein kann die Variable aus 3. werden.
  5. lokale Extremstellen der Zielfunktion:
    a Ableitungen
    b notwendige Bedingung
    c hinreichende Bedingung
  6. Globale Extremstellen: Die y-Werte der sinnvollen Lösungen aus 5ten und der Ränder aus 4tens Berechnen und den Gewinner auswählen.
  7. Fehlende Werte die einen interessieren mit den Formeln aus 2. berechnen.
  8. Antwort

Bei Deiner Aufgabenstellung ist das Hauptproblem, dass es keine richtige Hauptbedingung gibt und die zusätzlichen Formeln die benötigte Variable „Abweichung“ nicht beinhalten.
Letzteres kann man aber leicht korrigieren.

Abweichung=x
Die erste Nebenbedingungsformel wäre dann 4a + 4b + x = 15

mit einer ordentlichen Aufgabenstellung kann ich bestimmt weiter helfen, ich hoffe aber auch so geholfen zu haben.

MFG

#10

Guten Morgen Safrael,

danke für die Antwort.

Die fehlenden Variablen in den Nebenbedingungen, die noch eingeführgt werden müssten, sind dann die Schlupfvariablen, wenn ich das mit der linearen Optimierung so richtig verstanden habe.

Das Problem der fehlden Hauptbedingung habe ich erkannt. Vielleicht kann ich das wie folgt lösen?

Wenn ich mir Daten der Produktion aus meine Beispiel ansehe, werden 7 x a, 7 x b und 1 x c in insgesamt 56 Minuten produziert.

Kann meine Hauptbedingung dann so aussehen?

|(7a + 7b + c -56) | => minimieren

Falls das möglich ist, weiß ich dann aber nicht, wie ich mit dem Betrag umgehen soll.

Was die Lösung des Problems betrifft, bin ich nich auf linearie Optimierung festgelegt. Vielleicht gibt es auch andere und bessere Möglichkeiten die Einzelzeiten zu ermitteln.

Vielen Dank soweit und Grüße

powerblue

#12

Hallo Ralf,

sehr schade, aber ich hatte schon befürchtet, dass es so nicht klappt.

Das Buch habe ich schon befunden. Allerdings würdest du mir sehr helfen, wenn du vielleicht noch einen Tipp hast, mit welchem Verfahren sich das beschriebenen Problem am besten lösen lässt. Dann könnte ich etwas gezielter suchen, bevor ich wieder anfange es mit einer Methode zu versuchen, die nicht passt.

Danke und Grüße

powerblue