Maximales Gehalt < Sonstiges < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) für Interessierte  | | Datum: | 00:43 So 28.06.2009 | | Autor: | rabilein1 |
| Aufgabe | Weil die Geschäftsführung der Firma Meuchelmeuder & Söhne (Name geändert) die ewigen Gehaltsdiskussionen mit ihren Angestellten leid war, sagte sie:
Jeder Angestellte soll die Höhe seines Gehaltes selber bestimmen können. Dafür bekommt jeder eine Tabelle bestehend aus 5 mal 5 Zahlen (Je nach Funktion und Qualifikation sind die Zahlen unterschiedlich).
Man kreuze nun innerhalb von einer Minute 5 Zahlen an, wobei in jeder Zeile und in jeder Spalte nur ein Kreuz sein darf.
Das Jahresgehalt (in Euro) ergibt sich durch Multiplikation der 5 Zahlen.
Herr Meier bekam die folgende Tabelle vorgelegt (siehe unten):
Welche Zahlen sollte er ankreuzen, um auf das höchstmögliche Gehalt zu kommen?
[Dateianhang nicht öffentlich]
|
Innerhalb von einer Minute ist das kaum zu lösen. Probieren geht hier wohl über Studieren.
Oder gibt es eine Strategie, um in so kurzer Zeit die optimalen Zahlen zu erkennen?
Spontan hätte ich genommen (mit nur einer Minute Bedenkzeit):
[Dateianhang nicht öffentlich]
Aber das scheint nicht das Optimale zu sein.
Dateianhänge:
Anhang Nr. 1 (Typ: gif) [nicht öffentlich]
Anhang Nr. 2 (Typ: gif) [nicht öffentlich]
|
|
| |
|
Hallo rabilein,
es muss einmal gesagt sein: du hast ein Riesen-
Talent, interessante Fragestellungen mit mathe-
matischem Hintergrund zu stellen !
Beim vorliegenden Beispiel gibt es 5!=120
Möglichkeiten, 5 Zahlen aus dem Tableau
auszuwählen. Ich weiß aber nicht, ob es eine
effiziente Methode gibt, die direkt oder mit
viel weniger als 120 Rechnungen zum Ziel
führen würde.
LG Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:33 So 28.06.2009 | | Autor: | rabilein1 |
> du hast ein Riesen-Talent, interessante Fragestellungen
> mit mathematischem Hintergrund zu stellen !
Eigentlich hat mich die Aufgabe von Lisa hierzu inspiriert.
Da kam ja immer dasselbe raus. Zuerst dachte ich, in Lisas Aufgabe die auserwählten Zahlen nicht zu multiplizieren, sondern zu addiren.
Dann hätte es zwar unterschiedliche Resultate gegeben, aber die Aufgabe wäre trotzdem leicht lösbar gewesen.
Das Komplizierte an der Meuchelmeuder-Aufgabe ist meines Erachtens die (unordentliche) Anordnung der Zahlen.
Multiplikationen haben ja ein Gesetz ,
z.B. 6*6 > 5*7 oder 23*25 > 20*28 (die Summen sind gleich)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:59 Mo 29.06.2009 | | Autor: | rabilein1 |
> Ich weiß aber nicht, ob es eine effiziente Methode
> gibt, die direkt oder mit viel weniger
> als 120 Rechnungen zum Ziel führen würde.
Es wäre verwunderlich, wenn sich kein Mathematiker jemals mit diesem Problem beschäftigt hätte.
Wer hat denn das Simplex-Verfahren ausgeknobelt? Hier geht es doch ähnlich darum, aus allen denkbaren Möglichkeiten die optimale herauszufiltern.
Eine ganze Reihe der 120 theoretischen Möglichkeiten sind von vorne herein auszuschließen: Alle Kombinationen, die in der unteren Skizze Blau sind, kommen nicht in Frage, da sie von den Roten überboten werden.
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: gif) [nicht öffentlich]
|
|
|
| |
|
> Es wäre verwunderlich, wenn sich kein Mathematiker jemals
> mit diesem Problem beschäftigt hätte.
Gut möglich, dass dieses Thema schon irgendwo abgehan-
delt wurde - nur wüsste ich im Moment nicht, wo genau
(und unter welchen Stichworten) man suchen müsste.
> Wer hat denn das Simplex-Verfahren ausgeknobelt? Hier geht
> es doch ähnlich darum, aus allen denkbaren Möglichkeiten
> die optimale herauszufiltern.
> Eine ganze Reihe der 120 theoretischen Möglichkeiten sind
> von vorne herein auszuschließen: Alle Kombinationen, die in
> der unteren Skizze Blau sind, kommen nicht in Frage, da sie
> von den Roten überboten werden.
>
> [Dateianhang nicht öffentlich]
Beim Simplexverfahren startet man bei einer zulässigen
Ecke und sucht dann schrittweise einen Weg, entlang
dem die Zielgröße zunimmt. Vielleicht wäre ein analoges
Verfahren hier denkbar: Man starte mit einer ziemlich
beliebigen Auswahl (z.B. mit den Elementen längs der
Hauptdiagonale) und mache dann Austauschschritte in
der Art, wie du sie mit den roten und blauen Paaren
dargestellt hast: Wenn das Produkt [mm] a_{ik}*a_{jl} [/mm] von zwei
ausgewählten Elementen vom Produkt [mm] a_{il}*a_{jk} [/mm] über-
troffen wird, so entferne man [mm] a_{ik} [/mm] und [mm] a_{jl} [/mm] aus der
Auswahl und ersetze sie durch [mm] a_{il} [/mm] und [mm] a_{jk}.
[/mm]
Nach welchem System man aber die zu vergleichenden
Elementpaare auswählen soll und ob man durch solche
Austauschprozesse mit Sicherheit zur optimalen Lösung
kommt (natürlich auch bei größeren Matrizen), wäre
noch zu erforschen.
LG Al-Chw.
|
|
|
| |
|
Hallo rabilein,
ich habe noch keinesfalls eine Lösung anzubieten,
aber eine Umformulierung des Problems.
Ich nehme einmal an, dass du als (unausgespro-
chene) Voraussetzung angenommen hast, dass
alle Zahlen in der Tabelle positiv sind.
In diesem Fall könnte man alle Zahlen durch ihre
Logarithmen ersetzen. In der neuen Tabelle wäre
dann diejenige Kombination (bzw. Permutation)
mit der grössten Summe gesucht. Möglicher-
weise erleichtert es die Suche nach einer Lösung,
wenn man es "nur" mit Additionen statt mit
Multiplikationen zu tun hat.
Gruß Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:43 Mo 29.06.2009 | | Autor: | Calli |
Hi, die Zahlen lassen sich mit a = 13 wie folgt schreiben:
[mm] \pmat{a-2 & a-1 & a-5 & a-3 & a-4\\a-3 & a-2 & a-6 & a-4 & a-5\\a-4 &a-4 &a-7 & a-5 & a-6\\a-2 & a & a-4 & a-3 & a-4\\a-4 & a-2 & a-6 & a-5 & a-6}
[/mm]
Die größte Zahl wäre a5, die nächst kleinere a4(a - 1) usw.
Gemäß der Vorschrift ergibt sich:
a-2 a-1 a-5 ... ....
a-3 a-2 a-6 ... ...
a-4 a-4 a-7 ... ...
a-2 a a-4 ... ...
a-4 a-2 a-6 ... ...
und Spalte streichen !
Jetzt den gleichen bzw. nächst kleineren Faktor suchen !
Zeile und Spalte dieses Faktors streichen usw.
Ciao Calli
|
|
|
| |
|
Hallo Calli,
eine eigentliche "Vorschrift" hast du gar nicht angege-
ben, aber ich versuche deinem Gedankengang trotzdem
zu folgen. Wenn ich richtig verstanden habe, möchtest
du die größte in der Tabelle auftretende Zahl, im Beispiel
die 13, unbedingt in das Produkt einbeziehen und streichst
in der Folge die Zeile und die Spalte, in welcher diese Zahl
stand. Nachher suchst du im Rest der Tabelle wieder die
größte verbliebene Zahl, etc.
Dass dies leider nicht eine Strategie ist, die unweiger-
lich zum größtmöglichen Produkt führt, kannst du aber
schon an einem sehr einfachen Beispiel einer Tabelle
mit nur 2 Zeilen und 2 Spalten sehen:
[mm] \pmat{1&2\\3&4}
[/mm]
Die beiden überhaupt möglichen Produkte sind $\ [mm] 1*4\,=\,4$
[/mm]
und $\ [mm] 2*3\,=\,6$ [/mm] . Das zweite ist das größere, es enthält aber
nicht den allergrößten vorliegenden Faktor 4 !
LG Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:43 Di 30.06.2009 | | Autor: | Calli |
> Hallo Calli,
>...
> Dass dies leider nicht eine Strategie ist, die unweiger-
> lich zum größtmöglichen Produkt führt, kannst du aber
> schon an einem sehr einfachen Beispiel einer Tabelle
> mit nur 2 Zeilen und 2 Spalten sehen:
>
> [mm]\pmat{1&2\\3&4}[/mm]
>
> Die beiden überhaupt möglichen Produkte sind [mm]\ 1*4\,=\,4[/mm]
>
> und [mm]\ 2*3\,=\,6[/mm] . Das zweite ist das größere, es enthält
> aber
> nicht den allergrößten vorliegenden Faktor 4 !
>
> LG Al-Chwarizmi
Hallo Al-Chwarizmi,
das obige Gegenbeispiel zu meiner - zugegeben pragmatischen und nichtmathematischen - Vorgehensweise finde ich unfair (![[notok]](/images/smileys/notok.gif "[notok]") ) durch die Wahl von a11 = 1.
Bei einem pragmatischen Lösungsversuch würde man niemals einen Faktor 'Eins' berücksichtigen ! ![[happy]](/images/smileys/happy.gif "[happy]")
Ok, dass mein Ansatz nicht das maximal mögliche Gehalt ergibt, sehe ich ein.
Aber immerhin hätte ich mit meiner schnellen Methode nur 9108 € 'verschenkt'.
Ciao Calli
|
|
|
| |
|
> > Hallo Calli,
> > .....
> > Dass dies leider nicht eine Strategie ist, die
> > unweigerlich zum größtmöglichen Produkt führt,
> > kannst du aber schon an einem sehr einfachen
> > Beispiel einer Tabelle mit nur 2 Zeilen und
> > 2 Spalten sehen:
> >
> > [mm]\pmat{1&2\\3&4}[/mm]
> >
> > Die beiden überhaupt möglichen Produkte sind [mm]\ 1*4\,=\,4[/mm]
> > und [mm]\ 2*3\,=\,6[/mm] . Das zweite ist das größere, es enthält
> > aber nicht den allergrößten vorliegenden Faktor 4 !
> >
> > LG Al-Chwarizmi
>
> Hallo Al-Chwarizmi,
>
> das obige Gegenbeispiel zu meiner - zugegeben pragmatischen
> und nichtmathematischen - Vorgehensweise finde ich unfair
> () durch die Wahl von a11 = 1.
> Bei einem pragmatischen Lösungsversuch würde man
> niemals einen Faktor 'Eins' berücksichtigen !
Weshalb denn nicht ? In diesem Zusammenhang spielt
die Eins ihre "Sonderrolle" als neutrales Element der
Multiplikation gar nicht aus. Übrigens kannst du anstelle
der Matrix
[mm]\pmat{1&2\\3&4}[/mm]
gerne etwa
[mm]\pmat{6&7\\8&9}[/mm]
nehmen.
> Ok, dass mein Ansatz nicht das maximal mögliche Gehalt
> ergibt, sehe ich ein.
> Aber immerhin hätte ich mit meiner schnellen Methode nur
> 9108 € 'verschenkt'.
Bei schwierigen numerischen Problemen begnügt
man sich tatsächlich oft mit Lösungen, die nicht
optimal, sondern nur angenähert optimal sind.
> Ciao Calli
LG Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:51 Mi 01.07.2009 | | Autor: | rabilein1 |
> das obige Gegenbeispiel zu meiner - zugegeben pragmatischen
> und nichtmathematischen - Vorgehensweise finde ich unfair
> () durch die Wahl von a11 = 1.
> Bei einem pragmatischen Lösungsversuch würde man
> niemals einen Faktor 'Eins' berücksichtigen !
Es geht meines Erachtens gar nicht so sehr um den Faktor 'Eins', sondern darum, ob man den höchsten Faktor (in der Ursprungs-Aufgabe die Dreizehn) automatisch als "Bank" setzen darf, so wie Calli das "pragmatischer Weise" gemacht hat.
Genau so wie Al-Chwarizmi bin ich der Meinung, dass das nicht funktioniert.
Hat denn jemand mal die konkrete Aufgabe gelöst? (Ein Computer-Programm wird bestimmt ganz brutal-schnell die 120 Lösungs-Möglichkeiten durchrechnen können).
Ich bin nämlich nicht sicher, ob dann die "Dreizehn" überhaupt dabei ist.
Immerhin würden dann all die schönen grünen Faktoren (siehe unten) wegfallen.
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: gif) [nicht öffentlich]
|
|
|
| |
|
> > das obige Gegenbeispiel zu meiner - zugegeben pragmatischen
> > und nichtmathematischen - Vorgehensweise finde ich unfair
> > () durch die Wahl von a11 = 1.
> > Bei einem pragmatischen Lösungsversuch würde man
> > niemals einen Faktor 'Eins' berücksichtigen !
>
> Es geht meines Erachtens gar nicht so sehr um den Faktor
> 'Eins', sondern darum, ob man den höchsten Faktor (in der
> Ursprungs-Aufgabe die Dreizehn) automatisch als "Bank"
> setzen darf, so wie Calli das "pragmatischer Weise" gemacht
> hat.
>
> Genau so wie Al-Chwarizmi bin ich der Meinung, dass das
> nicht funktioniert.
>
> Hat denn jemand mal die konkrete Aufgabe gelöst?
Ja was?
Hast Du Al Chwarizmis Beitrag nicht gelesen?
Mit der ungarischen Methode hat er doch das max. Produkt herausgefunden,
und ich bin max. betrübt, weil ich mit "meiner" schlauen Methode [mm] \approx [/mm] 12000€ Jahresgehalt verschenkt hätte.
Das sieht man mal: wer mathematisch nicht auf Zack ist, bringt's zu nix...
Ich hatte mich "selbstverständlich" auch erstmal gierig auf die 13 gestürzt.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:15 Mi 01.07.2009 | | Autor: | rabilein1 |
Sorry - ich hatte die revidierte Version von Al-Chwarizmi (mit der Lösung) nicht gelesen.
Es war natürlich fiese Absicht von Herrn Meuchelmeuder, die Zahlen so zu wählen, dass die Angestellten drauf reinfallen.
Es ist wie zu Weihnachten: Das größte Paket enthält immer die meiste Luft.
|
|
|
| |
|
Hallo rabilein,
ich glaube, dass ich nun eine Webseite gefunden
habe, wo dieses Problem abgehandelt wird
(mit Summen statt Produkten, aber dies macht
ja, wie ich schon gemeldet habe, eigentlich keinen
prinzipiellen Unterschied aus. Der Link:
![[]](/images/popup.gif) Ungarische Methode
oder englisch und etwas anders:
Hungarian Algorithm
Gruß Al
|
|
|
| |
|
Hallo rabilein und alle anderen !
Ich habe mich nun über die "ungarische Methode"
schlau gemacht und sie in entsprechend abgewan-
delter Weise auf das vorliegende Beispiel angewandt.
> „Jeder Angestellte soll die Höhe seines Gehaltes selber
> bestimmen können. Dafür bekommt jeder eine Tabelle
> bestehend aus 5 mal 5 Zahlen (Je nach Funktion und
> Qualifikation sind die Zahlen unterschiedlich).
>
> Man kreuze nun innerhalb von einer Minute 5 Zahlen an,
> wobei in jeder Zeile und in jeder Spalte nur ein Kreuz sein
> darf.
> Das Jahresgehalt (in Euro) ergibt sich durch Multiplikation
> der 5 Zahlen.“
>
>
> Herr Meier bekam die folgende Tabelle vorgelegt (siehe
> unten):
> Welche Zahlen sollte er ankreuzen, um auf das
> höchstmögliche Gehalt zu kommen?
>
> [Dateianhang nicht öffentlich]
>
> Innerhalb von einer Minute ist das kaum zu lösen.
> Probieren geht hier wohl über Studieren.
>
> Oder gibt es eine Strategie, um in so kurzer Zeit die
> optimalen Zahlen zu erkennen?
>
> Spontan hätte ich genommen (mit nur einer Minute
> Bedenkzeit):
>
> [Dateianhang nicht öffentlich]
>
> Aber das scheint nicht das Optimale zu sein.
Ganz so schnell ist die "ungarische Methode" für
eine Handrechnung zwar nicht - aber sie ergibt
einen interessanten Algorithmus.
Wir gehen von der gegebenen Matrix aus:
$\ [mm] M_0=\pmat{11&12&8&10&9\\10&11&7&9&8\\9&9&6&8&7\\11&13&9&10&9\\9&11&7&8&7}$
[/mm]
Da hier Produkte maximiert werden sollen, die
Methode nach Kuhn-Munkres aber für Summen
gedacht ist, logarithmieren wir die Matrixelemente.
Ich habe den natürlichen Logarithmus genommen,
die entstandenen Werte mit 100 multipliziert und
auf ganze Zahlen gerundet. So entsteht die Matrix
$\ [mm] M_1=\pmat{240&248&208&230&220\\230&240&195&220&208\\220&220&179&208&195\\240&256&220&230&220\\220&240&195&208&195}$
[/mm]
Um aus dem Maximierungsproblem (Produkt
bzw. Summe der Logarithmen maximal) ein
Minimierungsproblem zu erhalten, stellen wir
die Matrix "auf den Kopf", indem wir jedes
Element [mm] a_{ik} [/mm] durch [mm] 256-a_{ik} [/mm] ersetzen ($\ 256$ ist
der Wert des größten Elements in [mm] M_1). [/mm]
Dies ergibt:
$\ [mm] M_2=\pmat{16&8&48&26&36\\26&16&61&36&48\\36&36&77&48&61\\16&0&36&26&36\\36&16&61&48&61}$
[/mm]
[mm] $\red{\pmat{16&0&36&26&36}}$
[/mm]
Der rot geschriebene Zeilenvektor enthält die
Spaltenminima der Matrix [mm] M_2. [/mm] Diese werden
nun von jedem Element der entsprechenden
Spalte subtrahiert.
$\ [mm] M_3=\pmat{0&8&12&0&0\\10&16&25&10&12\\20&36&41&22&25\\0&0&0&0&0\\20&16&25&22&25}\quad\blue{\pmat{0\\10\\20\\0\\16}}$
[/mm]
Im blauen Spaltenvektor stehen die Zeilen-
minima. Diese werden nun ebenso von allen
Elementen der betreffenden Zeile subtrahiert.
$\ [mm] M_4=\pmat{0&8&12&0&0\\0&6&15&0&2\\0&16&21&2&5\\0&0&0&0&0\\4&0&9&6&9}$
[/mm]
In dieser Matrix stehen nun viele Nullen. Nun
geht es darum, wenn möglich 5 dieser Nullen
auszuwählen derart, dass aus jeder Zeile und
aus jeder Spalte genau eine gewählt wird.
Enthält eine Zeile (hier z.B. die dritte und die
fünfte) oder eine Spalte (hier die dritte) nur
eine einzige Null, so muss diese natürlich aus-
gewählt und die restlichen Elemente in der
entsprechenden Zeile und der entspre-
chenden Spalte gestrichen werden:
$\ [mm] M_5=\pmat{-&-&-&0&0\\-&-&-&0&2\\ \red{0}&-&-&-&-\\-&-&\red{0}&-&-\\-&\red{0}&-&-&-}$
[/mm]
Nun muss natürlich in der zweiten Zeile die
einzig verbliebene Null und zum Schluss noch
die Null ganz rechts oben gewählt werden:
$\ [mm] M_6=\pmat{-&-&-&-&\red{0}\\-&-&-&\red{0}&-\\ \red{0}&-&-&-&-\\-&-&\red{0}&-&-\\-&\red{0}&-&-&-}$
[/mm]
Der ganze Auswahlprozess war also in diesem
Beispiel eindeutig festgelegt. Zusätzliche
Vorkehrungen, wie sie im Kuhn-Munkres-Algo-
rithmus vorgesehen sind, erübrigen sich hier.
Die nun ausgewählten Nullen stehen genau
an den Plätzen, wo in der ursprünglichen
Matrix die Elemente stehen, die man multi-
plizieren muss, um das größtmögliche Produkt
zu erhalten:
$\ [mm] M_0=\pmat{11&12&8&10&\red{9}\\10&11&7&\red{9}&8\\\red{9}&9&6&8&7\\11&13&\red{9}&10&9\\9&\red{11}&7&8&7}$
[/mm]
Maximal mögliches Produkt: $\ 9*9*9*9*11=72171$
Gruß Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:31 Mi 01.07.2009 | | Autor: | rabilein1 |
> > Man kreuze nun innerhalb von einer Minute 5 Zahlen an, ...
>... um das größtmögliche Produkt zu erhalten:
> [mm]\ M_0=\pmat{11&12&8&10&\red{9}\\10&11&7&\red{9}&8\\\red{9}&9&6&8&7\\11&13&\red{9}&10&9\\9&\red{11}&7&8&7}[/mm]
> Maximal mögliches Produkt: [mm]\ 9*9*9*9*11=72171[/mm]
Das alles erinnert mich an den Spruch einer Schülerin: "Ich wusste gar nicht, dass Mathematik so einfach ist. Und manchmal ist das sogar logisch."
Tja, eigentlich ist alles auf der Welt logisch.
Auch die Finanzkrise war vorhersehbar: Wo Hunderte von Milliarden verzockt werden, da ist am Ende nichts mehr da.
|
|
|
|
