Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Lineare Optimierung
Gehe zu Seite Zurück  1, 2, 3
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Lineare Optimierung
 
Autor Nachricht
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 14 Jan 2005 - 23:36:44    Titel:

Vielen Dank, nochmals, für ausführliche Erklärungen.

Zunächsteinmal muss man meinen ersten Vorschlag ablehnen, denn der ist natürlich falsch:

Gegenbsp: Minimiere 4 y - 7 x >= 0 und 4 y + 7 x - 28 bzgl. k(x,y) = y

Ränder, wie oben, wären klar 4 y - 7 x = 0 und 4 y + 7x - 28 = 0, aber die optimale Lösung x = 2, y = 2 liegt auf keinem Davon. Das liegt wohl daran, dass ich wohl ein falsches Bild von der Darstellung der Ränder hatte.

Es sieht so aus, als ob die allererste Frage immer noch offen wäre: Gibt es eine einfache syntaktisch ableitbare semi-algebraische Darstellung vom Rand?

Vermutung so weit: Es gibt eine, aber die ist nicht einfach Smile

Nun zu den Postings:

Zitat:
Ich benutze die Definition von Thomas_Da : ein schwarzer Punkt ist ein zulässtiger, ganzzahliger Punkt, mit der Eigenschaft, das mindestens einer der 2*d Nachbarn nicht zulässig ist.


Die Definition diente lediglich der Anschaaung in der Ebene. Man benötigt, wie oben angemerkt, eine "direktere" Definition.

Zitat:
in der Ebene seinen alle zulässigen Punkte gegeben durch x-y=0 ( also 2 Ungleichungen gleich zu einer Gleichung zusammen gefaßt )


Das wäre der allerschönste Fall, denn da ist man so gut wie fertig. Die software mit der ich arbeite kann solche "Zusammenfassungen" erkennen und automatisch durchführen. Für den parametrischen Fall natürlich nicht.

Zitat:
starte mit irgendeinem zulässigen, ganzzahligen Punkt; verbessere solange bis man zum "Rand" ( hier war schwarzer Punkt eine erste Charakterisierung) kommt


Für einen Informatiker (wie ich es bin) ergibt ein solcher Algorithmus durchaus Sinn. Mathematiker unter uns bekommen dabei wohl agonische Zuckungen Smile Ich suche nach einer Methode, um ein algebraisches Verfahren zu verbessern (bzw. eigentlich erst praktikabel zu ermöglichen, denn es handelt sich um weltweit erste veröffentlichte algorithmische Realisierung davon), indem man die Universalität geeignet einschränkt (Das verwendete Verfahren ist eben ein universelles Verfahren für PrA und verarbeitet das Problem zu allgemein). Daher kommen solche Heuristiken für mich leider nicht in Frage.

Zitat:
Gibt ausserdem einen sehr schönen Zusammenhang (der in der Mathematik alle paar Jahre neu entdeckt wird) zwischen den Testmengen und den Gröbner-Basen binomischer Ideale ( insbesondere kann damit der Buchberger-Algorithmus in der ganzzahligen linearen Optimierung benutzt werden).


Das hört sich sehr interessant an. Vor allem, wie man Gröbner Basen da reinbekommt. Kannst Du einen Verweis darauf geben (paper oder so)? Ich habe leider nichts gefunden.

Zitat:
Ich glaube die Behauptung ist falsch, einfach "nur" die Ungleichungen durch Gleichungen zu ersetzen


Die schwarzen Punkte waren falsch eingezeichnet. Ich poste demnächt das richtige Bild dazu Smile
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 14 Jan 2005 - 23:44:29    Titel:

Zitat:
aus der Ungleichung 3*x+5*y <= 7.5 könnte zum Beispiel bei ganzen x,y die 7.5 abgerundet werden, dieses "Ranschieben" der Hyperebenen kann ein recht mächtiges Werkzeug sein


Ich habe noch was übersehen. Ist wohl nicht ganz klar rübergekommen Sad Ich kann sowas, wie oben gar nicht eingeben in PrA. Die Sprache in der die Eingabe formuliert werden kann entspricht der Presburger Arithmetik; die Ausgabe ebenfalls. D.h. man arbeitet direkt in den ganzen Zahlen. Obige Eingabe könnte man durch:

6*x + 10*y <= 15

formuleiren, was sofort zu

3 * x + 5 * y <= 7

vereinfacht wäre. Sowas wie "ranschieben" gibt es hier nicht.

Es ist allerdings kein Grund um den Übergang ins reelle nicht zu betrachten.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 17 Jan 2005 - 00:16:06    Titel:

Für Fläche (zwei Variablen) habe ich eine Randcharakterisierung gefunden:

Der Rand von

a_1 x_1 + ... + a_n x_n <= k

scheint durch die Formel

a_1 x_1 + ... + a_n x_n <= k and a_1 x_1 + ... + a_n x_n >= k-max{a_i| 1 <= i <= n}

gegeben zu sein. Für mehr als zwei Variablen muss man das ganze noch zeigen. Leider bahnt sich dadurch schon die böse Vermutung an, dass das nichts bringt... Sad
Mirona
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 13.01.2005
Beiträge: 239

BeitragVerfasst am: 20 Jan 2005 - 15:22:18    Titel:

So, kann erst jetzt kurz antworten, bin gerade krank. Confused

Für eine Darstellung des grundlegenden Zusammenhanges zwischen Gröbner-Basen und ganzzahliger linearer Optimierung gibt es in

Titel: Some tapas of computer algebra / Arjeh M. Cohen ... (eds.)
Beteiligt: Arjeh M. Cohen
Erschienen: Berlin [u.a.] : Springer, 1999
Umfang: XIV, 352 S. : graph. Darst.
Schriftenreihe: Algorithms and computation in mathematics ; 4
Anmerkung: Literaturangaben
ISBN: 3-540-63480-0 (Pp.)

eine kleines Kapitel.

Das genannte Buch beschäftigt sich mit Anwendungen von Gröbner-Basen in verschiedensten Gebieten der Mathematik (genauer der algorithmischen Anwendung).
Es sieht den Zusammenhang also aus algebraischer Perspektive.
Wichtig könnten dort insbesondere auch die Literatur-Verweise sein, sie reichen von der orginalen Fassung des Begriffs Testmenge (Conti/Traverso, glaube 91) über eine konsequente Ausarbeitung der Zusammenhänge (Thomas in seiner Dissertation und nachfolgende Veröffentlichungen , ab 94) bis zu einigen Forschungsansätzen (Grötschel,Ziegler,Thomas,Weissmantel,... ;aus heutiger Sicht aber schon veraltet).

Eine leicht zugängliche Veröffentlichung des Zusammenhangs aus der Sicht der ganzzahligen Optimierung kenne ich nicht ( ich selbst verwende das nicht-offiziell-veröffentlichte Skript von Weissmantel/Grötschel zur Theorie der ganzzahligen linearen Optimierung, sehr lesenswert), gibt es aber bestimmt irgendwo.

Zu der Frage nach (einfach ableitbaren) Darstellungen eines Polyeders durch semi-algebraische Mengen (ich verstehe darunter nicht notwendig lineare Polynome):
Oha, das ist gerade ein Gebiet der aktuellsten Forschungen.
Ich nenne mal einige Ergebnisse :
Zum Beispiel von Berning(1998) eine konstruktive Methode jedes Polytop in der Dimension 2 als Schnitt zweier (algebraischer) Ungleichungen darzustellen.
Oder von Bosse/Grötschel(2003) eine konstruktive Methode für jedes Polyeder 2n (algebraische) Ungleichungen zu finden , welche das Polyeder beschreiben ( n=Raumdimension).

Diese Frage ist also sehr "offen". Very Happy

MfG Mirona
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 20 Jan 2005 - 16:00:35    Titel:

@Mirona:

Vielen Dank für die Verweise. Ich werde mir die Sache mal anschauen. Von meinem Betreuer habe ich Antwort im bekommen im Stil: Lass das, das für sowieso zu gar nichts, mach lieber was vernünftiges ... Naja.

Ich hätte da noch eine Frage. Hast Du für ganzzahlige (nicht-)parametrische lineare Optimierung praktische Beispiele? Unter praktisch verstehe ich relevante Größe. Nach Möglichkeit mit Lösung.

Und noch was. Hast Du eine Ahnung, wo sonst ganzzahlige Constraints auftauchen? Nicht notwendigerweise Optimierung.

Ich bin froh, wenn Du irgendwas dazu sagen kannst, denn vernünftige Beispiele sind sehr kostbar.
Mirona
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 13.01.2005
Beiträge: 239

BeitragVerfasst am: 21 Jan 2005 - 14:55:39    Titel:

Hallo algebrafreak,

was verstehst du denn unter praktischen Beispielen bzw relevanter Grösse?

MfG Mirona
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 21 Jan 2005 - 16:34:19    Titel:

Praktische Beispiele sind Aufgabenstellungen aus dem richtigen Leben. Also sowas wie hier

http://www.uni-protokolle.de/foren/viewtopic.php?t=11801&highlight=meilen

Und relevante Größe analog. D.h. z.B. bei Problem oben 20-100 Flugreisen, oder so.

Wäre nicht schlecht welche zu kennen, vor allem aber ist die Lösung interessant.

P.S. Bei dem Ansatz von oben im Thread habe ich rausbekommen, dass das exakt das selbe ist, was das QE-Verfahren tut. Der setzt im Wesentlichem Ränder ein! Es nützt auch nicht Kunstvariablen einzuführen (slack oder so), da dies eine Substitution ist und das Verfahren sie autoatisch zurücksubstituiert. Ich suche also noch ein wenig nach Mgk. Gleichungen einzuführen, aber wohl nicht besonders mit viel Hoffnung Sad
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Lineare Optimierung
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite Zurück  1, 2, 3
Seite 3 von 3

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum