www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Sonstiges" - Maximales Gehalt
Maximales Gehalt < Sonstiges < Schule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Maximales Gehalt: Frage (für Interessierte)
Status: (Frage) für Interessierte Status 
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]
        
Bezug
Maximales Gehalt: Antwort
Status: (Antwort) fertig Status 
Datum: 01:14 So 28.06.2009
Autor: Al-Chwarizmi

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

Bezug
                
Bezug
Maximales Gehalt: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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)

                  


Bezug
                
Bezug
Maximales Gehalt: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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]
Bezug
                        
Bezug
Maximales Gehalt: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:35 Mo 29.06.2009
Autor: Al-Chwarizmi


> 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.
  

Bezug
        
Bezug
Maximales Gehalt: addieren statt multiplizieren
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:29 Mo 29.06.2009
Autor: Al-Chwarizmi

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


Bezug
                
Bezug
Maximales Gehalt: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
Maximales Gehalt: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:31 Mo 29.06.2009
Autor: Al-Chwarizmi

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
  

Bezug
                                
Bezug
Maximales Gehalt: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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]) durch die Wahl von a11 = 1.
Bei einem pragmatischen  Lösungsversuch würde man niemals einen Faktor 'Eins' berücksichtigen ! [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'.[happy]

Ciao Calli


Bezug
                                        
Bezug
Maximales Gehalt: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:39 Di 30.06.2009
Autor: Al-Chwarizmi


> > 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
> ([notok]) 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  

Bezug
                                        
Bezug
Maximales Gehalt: Pragmatische Lösung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 07:51 Mi 01.07.2009
Autor: rabilein1


> das obige Gegenbeispiel zu meiner - zugegeben pragmatischen
> und nichtmathematischen - Vorgehensweise finde ich unfair
> ([notok]) durch die Wahl von a11 = 1.
>  Bei einem pragmatischen  Lösungsversuch würde man
> niemals einen Faktor 'Eins' berücksichtigen ! [happy]

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]
Bezug
                                                
Bezug
Maximales Gehalt: Ja was?
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 08:02 Mi 01.07.2009
Autor: angela.h.b.


> > das obige Gegenbeispiel zu meiner - zugegeben pragmatischen
> > und nichtmathematischen - Vorgehensweise finde ich unfair
> > ([notok]) durch die Wahl von a11 = 1.
>  >  Bei einem pragmatischen  Lösungsversuch würde man
> > niemals einen Faktor 'Eins' berücksichtigen ! [happy]
>  
> 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

Bezug
                                                        
Bezug
Maximales Gehalt: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
        
Bezug
Maximales Gehalt: Antwort
Status: (Antwort) fertig Status 
Datum: 20:55 Mo 29.06.2009
Autor: Al-Chwarizmi

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:

        []Ungarische Methode

oder englisch und etwas anders:

        []Hungarian Algorithm


Gruß    Al


Bezug
        
Bezug
Maximales Gehalt: "Ungarische Methode"
Status: (Antwort) fertig Status 
Datum: 09:33 Di 30.06.2009
Autor: Al-Chwarizmi

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





  

Bezug
                
Bezug
Maximales Gehalt: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.  

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de