Antworte auf:  Optimierung mit verschiedenen Faktoren von SC4LEup
Forum:  Numerik & Optimierung, moderiert von: matroid

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 
 


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 1593
 Beitrag No.12, eingetragen 2020-11-13 19:33    [Diesen Beitrag zitieren]

Hallo SC4LEup!

Du könntest Dir ein Beisiel aufzeichnen.
Wenn ich beispielsweise Kunden/Lieferanten/User A, B, C habe könnte ich alle mal auf 5 oder 10 setzen und dann schauen ob vernünftige Ergebnisse herauskommen.
Bei einem grafischen Beispiel ist auch eine Skizze nicht schlecht.
In einer solchen Simulation kann man beispielsweise erkennen ob die Aufgabenstellung schon sinnvoll ist, oder ob etwas fehlt!
Beispielsweise steigt die Zielfunktion wenn eine bestimmte Variable steigt?

Viele Grüße
Ronald


SC4LEup
Junior
Dabei seit: 23.09.2020
Mitteilungen: 8
 Beitrag No.11, eingetragen 2020-11-13 13:39    [Diesen Beitrag zitieren]

Hallo Dellastelle,

wie genau meinst du das?
Was wären denn die Schritte einer solchen Simulation?


Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 1593
 Beitrag No.10, eingetragen 2020-11-08 00:33    [Diesen Beitrag zitieren]

Hallo SC4LEup!

Ich weiß jetzt nicht, ob das hilfreich ist:
man könnte am Anfang statt Optimierung auch eine Simulation durchführen.
So könnte man testen, ob die Modellierung einigermaßen schlüssig ist.

Viele Grüße
Ronald


SC4LEup
Junior
Dabei seit: 23.09.2020
Mitteilungen: 8
 Beitrag No.9, eingetragen 2020-11-05 20:13    [Diesen Beitrag zitieren]

Verzeihung, mein Beitrag war eigentlich noch nicht fertig. Hier die Fortsetzung:
Das nachfolgende Bild soll darstellen, inwiefern sich die Wahl des Handelspreises auf andere Handelspreise auswirkt.



Die möglichen Handelspreise sind immer abhängig von der Entfernung der Haushalte zueinander.
Würde K1 im Beispiel auf dem Bild seinen kompletten Bedarf durch P1 decken, dann wäre es für K2 nicht mehr möglich diesen Preis anzusetzen. Folglich sind die möglichen Preise doch schon voneinader abhängig?

Vielen Dank und Liebe Grüße


SC4LEup
Junior
Dabei seit: 23.09.2020
Mitteilungen: 8
 Beitrag No.8, eingetragen 2020-11-05 20:03    [Diesen Beitrag zitieren]

Guten Abend,

dein Impuls hat mich dazu angeregt meine Interpretation der Kanten noch einmal zu überdenken.
Im nachfolgenden Bild ist oben meine alte Interpretation dargestellt. Ich glaube, dass man diese Kanten allerdings auch zu einer Kante zusammenfassen kann. Was hälst du von dem Ansatz?





Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6640
Herkunft: Niedersachsen

 Beitrag No.7, eingetragen 2020-11-03 23:53    [Diesen Beitrag zitieren]

2020-11-02 21:33 - SC4LEup in Beitrag No. 4 schreibt:
Das Transportproblem habe ich auch schon in Betracht gezogen. Ich schaue mir das die Tage noch einmal genauer an. Das Zuordnungsproblem stellt doch auch einen Spezialfall des Transportproblems dar oder?
Ja, genau.

Theoretisch können 1-3 unterschiedliche Preise zwischen einem Produzenten und einem Konsumenten möglich sein. Wenn die Handelspaare alle gefunden wurden, wird aber immer nur 1 Preis pro Handel benutzt (also theoretisch eine Kante der bis 3 möglichen Kanten gewählt).
Bei einem Greedy-Ansatz zur Lösung des Problems würde man immer den niedrigsten Preis wählen, aber ob dies auch zum globalen Maximum führt, müsste ich erst beweisen.
Wenn man zwischen einem Handelspaar den Preis B statt des Preises A benutzt, ändert sich dann für die anderen Paare irgendetwas. Spricht irgendetwas dagegen, bei einem Paar _nicht_ den geringsten Preis zu wählen.

In der Literatur sind bei Zuordnungsproblemen in bipartiten Graphen die Mengen, aus denen Elemente einander zugeordnet werden sollen immer gleich Groß (|M|=|N|). Bei mir ist |M|*0,25=|N| und eine Mehrfachzuordnung muss möglich sein.
Deswegen ja "Transportproblem" und nicht "Zuordnungsproblem".
Beim Transportproblem darf ein Lieferant mehrere Kunden beliefern und ein Kunde darf auch von mehreren Lieferanten beliefert werden. Selbst die Abnahmemengen dürfen unterschiedlich sein.


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6530
Herkunft: Milchstraße

 Beitrag No.6, eingetragen 2020-11-03 14:02    [Diesen Beitrag zitieren]

2020-11-03 13:55 - SC4LEup in Beitrag No. 5 schreibt:
Das Häkchen habe ich ausversehen gesetzt. Kann man das rückgängig machen?

Es sollte jetzt wieder weg sein


SC4LEup
Junior
Dabei seit: 23.09.2020
Mitteilungen: 8
 Beitrag No.5, eingetragen 2020-11-03 13:55    [Diesen Beitrag zitieren]

Das Häkchen habe ich ausversehen gesetzt. Kann man das rückgängig machen?


SC4LEup
Junior
Dabei seit: 23.09.2020
Mitteilungen: 8
 Beitrag No.4, eingetragen 2020-11-02 21:33    [Diesen Beitrag zitieren]

Hallo,
wie immer zuerst ein großes Danke für die Anwort!

Das Transportproblem habe ich auch schon in Betracht gezogen. Ich schaue mir das die Tage noch einmal genauer an. Das Zuordnungsproblem stellt doch auch einen Spezialfall des Transportproblems dar oder?

Die Kosten sind in Euro/Mengeneinheit, folglich proportional.

Bei der graphentheoretischen Interpretation von den unterschiedlichen möglichen Preisen bin ich mir unsicher.

Theoretisch können 1-3 unterschiedliche Preise zwischen einem Produzenten und einem Konsumenten möglich sein. Wenn die Handelspaare alle gefunden wurden, wird aber immer nur 1 Preis pro Handel benutzt (also theoretisch eine Kante der bis 3 möglichen Kanten gewählt).
Bei einem Greedy-Ansatz zur Lösung des Problems würde man immer den niedrigsten Preis wählen, aber ob dies auch zum globalen Maximum führt, müsste ich erst beweisen.

In der Literatur sind bei Zuordnungsproblemen in bipartiten Graphen die Mengen, aus denen Elemente einander zugeordnet werden sollen immer gleich Groß (|M|=|N|). Bei mir ist |M|*0,25=|N| und eine Mehrfachzuordnung muss möglich sein. Wenn Du dazu eine Idee hast, wäre ich sehr dankbar.

 


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6640
Herkunft: Niedersachsen

 Beitrag No.3, eingetragen 2020-10-25 00:34    [Diesen Beitrag zitieren]

Das klingt für mich stark nach einem sogenannten Transportproblem. Da gibt es allerdings nur eine Kante zwischen Erzeuger und Abnehmer. Ich habe aber auch noch nicht verstanden, ob das Vorhandensein von drei Kanten in Deinem Modell irgendwie notwendig ist, oder ob man eigentlich doch nur die billigste nimmt.
Sind die Transportkosten proportional zur Menge, dann handelt es sich um ein lineares Transportproblem, das wäre dann ein relativ gutmütiges Problem.

Schau Dir mal den obigen Wikipedia-Link an. Vielleicht beantwortet das schon viele Fragen. Ansonsten natürlich: Weiterfragen!

Noch ein Hinweis:
In der Regel reicht es aus, direkt hier im Faden zu antworten. Eine zusätzliche private Nachricht ist nicht nötig.
Ich kann natürlich nicht für alle sprechen, aber die Gefahr, dass ich einen Faden unbeabsichtigt aus den Augen verliere, in dem ich einmal geantwortet habe, ist nicht sehr hoch, da diese Fäden für mich hervorgehoben werden (und ich auch gezielt danach filtern kann).
Wenn sich einige Tage nichts tut, kann man dann immer noch per privater Nachricht nachfragen.


SC4LEup
Junior
Dabei seit: 23.09.2020
Mitteilungen: 8
 Beitrag No.2, eingetragen 2020-10-24 17:56    [Diesen Beitrag zitieren]

Hallo danke für deine Antwort.
Ich bin noch ganz neu hier im Forum und muss mich erstmal zurechtfinden.

Mein Problem würde ich folgendermaßen formulieren (Ich bin kein Mathematiker, deshalb könnte es hier und da etwas unsauber sein):

Es existiert eine Menge an privaten Haushalten, wobei davon manche Produzenten und andere Konsumenten sind. Es wird ein homogenes Gut gehandelt. Produzenten haben einen Überschuss, während Konsumenten einen Bedarf haben. Ein Handel ist immer nur zwischen Produzent und Konsument möglich.

Ich möchte die Gesamtkosten, die durch den Handel zwischen den Haushalten auftreten minimieren in dem ich einen Algorithmus in Python implementiere.

Als Modellierung habe ich mir bisher folgendes vorgestellt.
Sei G= (V,E) ein Graph. Wobei V die Menge der Haushalte und E die Menge der Kanten (definiert als die erreichbaren Handelspreise zwischen den Haushalten sind).
 
Jeder Produzent ist mit jedem Konsument durch 1-3 Kanten (verschiedene erreichbare Preise) verbunden. Dies ist immer abhängig von den jeweiligen Ausgangsbedingungen eines Handelspaars.

Ich verfolge grade den Ansatz, dass es sich bei meinem Problem um ein Zuordnungsproblem in einem disjunkten (Produzenten, Konsumenten) Graphen handelt.
Hierbei stoße ich allerdings auf folgendes Problem: Um den Bedarf eines Konsumenten zu befriedigen, muss eine Mehrfachzuordnung von Produzenten möglich sein. In der Literatur werden hauptsächlich 1:1 Zuordnungen beschrieben.
Aktuell bin ich deshalb auf der Suche nach einem Algorithmus, der die Produzenten und Konsumenten eineinander zuordnet und dabei die Gesamtkosten (über alle Haushalte) minimiert.
Die Kantengewichte sind alle bekannt. Ich hab dafür 3 Adjazenzmatrizen mit den jeweiligen Werten erstellt.

Ich hoffe, dass ich es jetzt ein bisschen klarer formuliert habe.

Vielen Dank schon mal im Voraus :D


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6640
Herkunft: Niedersachsen

 Beitrag No.1, eingetragen 2020-09-24 09:26    [Diesen Beitrag zitieren]

Hallo und Herzlich Willkommen auf dem Matheplaneten,

könntest Du noch etwas dazu schreiben, was Dein Ziel ist?
Möchtest Du das Problem nur irgendwie modellieren, als Problem der Klasse XY (z.B. ganzzahliges lineares Programm) modellieren, mit irgendeiner (speziellen) Software lösen, oder ...

Bis jetzt habe ich folgendes verstanden:
Ist $x$ der Zielort, so gibt es drei Funktionen $f_1, f_2$ und $f_3$, die den Rabatt in Abhängigkeit von $x$ für die drei Einsparungsmöglichkeiten angeben.
Sind die Einsparmöglichkeiten nicht miteinander kombinierbar, dann ist der bestmögliche Rabatt $\max{\{f_1(x), f_2(x), f_3(x)\}}$.
Kann man alle Einsparmöglichkeiten parallel nutzen, dann ist der Gesamtrabatt $f_1(x)+f_2(x)+f_3(x)$.
Was davon für Dich zutrifft, habe ich nicht verstanden.


SC4LEup
Junior
Dabei seit: 23.09.2020
Mitteilungen: 8
 Themenstart: 2020-09-23 19:20    [Diesen Beitrag zitieren]

Hallo in die Runde. Ich versuche grade ein Problem zu lösen, bei dem ich nicht weiterkomme. Ich beschreib es euch mal kurz.

Ich möchte den Ertrag eines Produkts durch Einsparungen optimieren, die an verschiedene Entfernungsgrenzen gebunden sind.
Die Einsparungen sind immer an bestimmte Kilometergrenzen gebunden und nicht immer miteinander kombinierbar.

Einsparmöglichkeit 1: (x1) Das Produkt ist 4 € günstiger, wenn es in einem Umkreis von 10kilometern verkauft wird.

Einsparmöglichkeit 2 (x2): Das Produkt wird, je nach Zone in die es verkauft wird 2-6 € günstiger.

Einsparmöglichkeit 3 (x3):  Das Produkt wird, je nach Zone in die es verkauft wird 3-5€ günstiger. Diese Zonen sind jedoch nicht identisch zu den Zonen von x2.


Als möglichen Ansatz habe ich mir überlegt, dass ich meinen Einsparungen maximieren möchte.

Max z = 4€*x1 + (2-6€)*x2 + (3-5€)*x3

Ich bin mir allerdings ziemlich unsicher, was ich für Restriktionen annehmen kann und wie man mit diesen unterschiedlichen Einsparmöglichkeiten in Abhängigkeit der jeweiligen Zonen umgehen kann.

Wäre sehr dankbar um Hilfe und Anregungen
:D


 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]