Ungarische Methode | Beispiel 9.1

Wie du selbst schreibst muss die Zuordnung im Beispiel nur zulässig (nicht optimal) sein.
Es müssen also nur die 2 Bedingungen

1.) [Summiere über i ](x_ij)=1
und
2.)[Summiere über j] (x_ij)=1

erfüllt sein.

Daraus folgt, dass erstens die x_ij nur 0 oder 1 sein können und zweitens, dass, wenn ein konkretes x_ij=1 ist, in der i-ten Zeile und der j-ten Spalte der Zuordnungsmatrix ansonsten nichts markiert wird (nur an Position ij steht das Dreieck).

Mit anderen Worten: Wenn du durch die Zeilen der Matrix mit den c_ij gehst, steht in jeder Zeile genau ein Dreieck und genauso für die Spalten.

Jede Markierung der Matrix die obiges erfüllt hätte im Beispiel benutzt werden können.