Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Optimierung mit verschiedenen Faktoren
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Optimierung mit verschiedenen Faktoren
SC4LEup
Junior Letzter Besuch: im letzten Monat
Dabei seit: 23.09.2020
Mitteilungen: 8
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-09-23


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6603
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-09-24


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SC4LEup
Junior Letzter Besuch: im letzten Monat
Dabei seit: 23.09.2020
Mitteilungen: 8
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-10-24


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6603
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-10-25


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SC4LEup
Junior Letzter Besuch: im letzten Monat
Dabei seit: 23.09.2020
Mitteilungen: 8
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-11-02 21:33


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.

 



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SC4LEup
Junior Letzter Besuch: im letzten Monat
Dabei seit: 23.09.2020
Mitteilungen: 8
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-11-03 13:55


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6403
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-11-03 14:02


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6603
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-11-03 23:53


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SC4LEup
Junior Letzter Besuch: im letzten Monat
Dabei seit: 23.09.2020
Mitteilungen: 8
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2020-11-05 20:03


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?






Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SC4LEup
Junior Letzter Besuch: im letzten Monat
Dabei seit: 23.09.2020
Mitteilungen: 8
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2020-11-05 20:13


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1543
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2020-11-08 00:33


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SC4LEup
Junior Letzter Besuch: im letzten Monat
Dabei seit: 23.09.2020
Mitteilungen: 8
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2020-11-13 13:39


Hallo Dellastelle,

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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1543
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2020-11-13 19:33


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 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]