Matrix Minimierungsproblem: Geringstes Angebot für Matrix A und B

Question

ich habe ein Problem. Ich habe eine Matrix A und eine Matrix B. Dazu habe ich ein Angebot:

$$ A = \left( \begin{matrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{matrix} \right) $$

$$ B = \left( \begin{matrix} 13 & 14 & 15 & 16 \\ 9 & 10 & 11 & 12 \\ 5 & 6 & 7 & 8 \\ 1 & 2 & 3 & 4 \end{matrix} \right) $$

$$ Angebot = \left( \begin{matrix} 1 & 2 & 3 & 4 \end{matrix} \right) $$

Diese können als Kostenmatrizen angesehen werden. Wenn ich nun das Angebot betrachte, welches (1 2 3 4) ist, kann ich mithilfe der Matrizen Kosten für A und B berechnen. Wenn wir das Angebot nun auf Matrix "A" anwenden ist die Vorgehensweise wie folgt um die Kosten zu errechnen.

Für A:

- Zuerst gehe ich in die Zeile 1 und wähle dort das zweite Element (in diesem Fall die Zahl 2 in der Kostenmatrix A)
- Danach in Zeile 2, Spalte 3 (Wert: 7) 
- Danach in Zeile 3, Spalte 4 (Wert: 12)

Danach rechnet man alle Werte zusammen: 2 + 7 + 12 = 21 für A

Für B errechnen sich somit folgende Werte: 14 + 11 + 8 = 33

Somit ergeben sich aus A und B für das Angebot (1 2 3 4) die gesamtkosten von 54 (A und B summiert)

Jetzt das Problem:

Gibt es eine Möglichkeit das beste Angebot für beide Matrizen zu erhalten um somit die geringsten Kosten zu erlangen nach oben beschriebener Vorgehensweise?

Comments

Ich musste diese Frage erneut stellen, da ich die alte nicht bearbeiten konnte.

---

Hallo Max, du suchst das beste Angebot. Bitte beschreibe, welchen Einfluss das Angebot (a b c d) auf deinen Rechenweg und somit auf die Gesamtkosten hat. Sonst ist die Aufgabe nicht lösbar.

---

@RomanGa danke für deine Antwort. Beispielsweise habe ich das Angebot = (1,2,3,4) ich rechne dieses für A und für B aus und erhalte für A=21 und für B=33, zusammen sind dies 54. Nun wähle ich das Angebot = (4,3,2,1) aus. Und erhalte für A=30 und B=18 zusammen sind dies 48. Sprich das Angebot (4,3,2,1) ist kleiner und somit besser wie das Angebot (1,2,3,4) und ich suche quasi das Beste Angebot, welches die kleinen aufsummierten Kosten hat für A und B. Sprich A + B sollen zusammen sollte minimiert werden. Dabei ist die Reihenfolge des Angebots entscheidend und es darf dabei nur jede Zahl einmal im Angebot vorkommen. Hoffe ich konnte deine Aussage beantworten, falls noch was unklar ist lass es mich bitte wissen.

Das Angebot ist so lang wie viele Spalte die Matrix hat, dabei hat jede Matrix gleich viele Spalten wie Zeilen.

---

Hallo Max, offenbar führt das Angebot (1 2 3 4) dazu, dass du in der Matrix A die Summe a12 + a23 + a34 berechnest. Das Angebot (4 3 2 1) führt dazu, dass du in der Matrix A die Summe a21 + a32 + a43 berechnest. Schön, jetzt hast du zwei Beispiele gemacht. Aus diesen erschließt sich mir aber nicht, welche Elemente für ein *beliebiges* Angebot wie z. B. (2 4 1 3) aufsummiert werden sollen. Ist vielleicht deine Berechnungsvorschrift für das Angebot (c d e f) Summe = a_cd + a_de + a_ef ?

---

@RomanGa, genau das Angebot (c, d, e, f) berechnet sich für A wie du beschrieben hast a_cd + a_de + a_ef und für B wäre es wie folgt b_cd + b_de + b_ef und A und B sollen in Summe das kleinste Angebot ergeben.

Answer 1

Es gibt mehrere optimale Angebote, z. B. (4 3 2 1) oder (4 1 2 3), und die minimalen Gesamtkosten sind 48.

Comments

Wie ist denn der Rechenweg? Oder wie kann ich so ein optimales Angebot finden? Durch ausprobieren bei einer 4x4 Matrix geht es ja noch. Ich würde gerne jedoch eine viel größeres Angebot berechnen welches 100 lang ist und sprich die Matrix A und B ist dann auch 100x100.

---

Hallo Max, leicht lösbar war die Aufgabe nur durch die spezielle Art der Matrizen. Es gilt ja Kosten = (a_cd + a_de + a_ef) + (b_cd + b_de + b_ef) = (a_cd + b_cd) + (a_de + b_de) + (a_ef + b_ef). Das heißt, du bildest die Matrix C = A + B, und rechnest dann Kosten = (c_cd + c_de + c_ef). Fällt dir bei der Matrix C etwas auf? - Mit einer *beliebigen* Matrix C wirds schwerer, ich denke mal darüber nach.

---

Auf jeden Fall müssen zuerst die Matrizen A und B zu C zusammenaddiert werden. Dann sollte der Algorithmus mit dem kleinsten c_xy beginnen. Dann käme das nächstgrößere Matrixelement dran, usw. Immer unter Beachtung, dass wir eine Permutation von (1 2 3 4 ...) haben. Die Frage ist, ob dies zwangsläufig das Optimum liefert.