Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Linearisierung einer Nebenbedingung
Druckversion
Druckversion
Autor
Universität/Hochschule J Linearisierung einer Nebenbedingung
Kingtom2
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.05.2019
Mitteilungen: 82
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-05-29


Hallo ich habe hier eine Nebenbedingung, die ich gerne linearisieren möchte.

\( \sum_{i=1}^{n-1} \sum_{j=1}^{n} \sum_{c\in C} c*(w_{ci}*x_{ij}^{pq}+w_{cj}*x_{ij}^{pq}) \geq 2*(1+2+...+( \sum_{i=1}^{n-1} \sum_{j=1}^{n} x_{ij}^{pq} -1)) \)

Dabei sind w und x binär und die Entscheidungsvariablen.

Ich kenne die Standardlinearisierung bei Binärvariablen in der einfachsten Form. Hier bin ich aber mit den Indizes etwas verwirrt.

Mein Vorschlag:
Setze \( z_{1} = w_{ci}*x_{ij}^{pq} \) und \( z_{2} = w_{cj}*x_{ij}^{pq} \)
Mit
\( z_{1} \leq w_{ci} \\
z_{1} \leq x_{ij}^{pq} \\
w_{ci}+x_{ij}^{pq} \leq 1 + z_{1} \\
und z_{1} \geq 0 \)
Analog für \( z_{2}\)

Ich habe aber leider das Gefühl dass das so nicht reicht.
Kann mir da jemand weiterhelfen? Es wäre mir wirklich wichtig. Danke



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kingtom2
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.05.2019
Mitteilungen: 82
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, vom Themenstarter, eingetragen 2020-05-29


Da das mit LATEX nicht so funktioniert wie geplant, hier die Bedingung als Bilddatei:




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1502
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2020-06-01


2020-05-29 16:38 - Kingtom2 im Themenstart schreibt:
Mein Vorschlag:

Setze \( w_{ci}\cdot x_{ij}^{pq} = z_{1} \) mit
\( z_{1} \leq w_{ci} \\
z_{1} \leq x_{ij}^{pq} \\
w_{ci}+x_{ij}^{pq} \leq 1 + z_{1} \\
z_{1} \geq 0 \)

Ich habe aber leider das Gefühl, dass das so nicht reicht.

Ich habe das Gefühl, dass das so reicht: 😃

Setze \( w_{ci}\cdot x_{ij}^{pq} = z_{cij}^{1pq} \) mit
\( z_{cij}^{1pq} \leq w_{ci} \\
z_{cij}^{1pq} \leq x_{ij}^{pq} \\
w_{ci}+x_{ij}^{pq} \leq 1 + z_{cij}^{1pq} \\
z_{cij}^{1pq} \geq 0 \)


-----------------
/Kyristo meu kimgei kom nhi cumgen ta Gendmogen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kingtom2
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.05.2019
Mitteilungen: 82
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2020-06-02


Hey danke für deine Antwort Goswin. 🤗

Dann war mein Ansatz ja schon mal richtig. Ich muss lediglich alle Indizes betrachten um auch wirklich alle möglichen Paarungen zu linearisieren, korrekt?

Die rechte Seite der Ungleichung kann so bleiben, da sie bereits linear ist?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1502
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-06-03


2020-06-02 19:19 - Kingtom2 in Beitrag No. 3 schreibt:
ich habe hier eine Nebenbedingung, die ich gerne linearisieren möchte.

\[
\sum_{i=1}^{n-1} \sum_{j=1}^{n} \sum_{c\in C}
  c\, (w_{ci}\cdot x_{ij}^{pq}+w_{cj}\cdot x_{ij}^{pq})
~\geq~
2\, (1+2+...+( \sum_{i=1}^{n-1} \sum_{j=1}^{n} x_{ij}^{pq} -1))
\]
Dabei sind w und x binär und die Entscheidungsvariablen.
Die rechte Seite der Ungleichung kann so bleiben, da sie bereits linear ist?

Was lässt dich daran zweifeln?

Und wenn du die Bedingungen wie folgt hinschreibst, kommst du mit weniger zusätzlichen Variablen aus:
\[
\sum_{c\in C} c\, \Big(
  \sum_{i=1}^{n-1} w_{ci}\cdot \big(\sum_{j=1}^{n} x_{ij}^{pq}\big)
  + \sum_{j=1}^{n} w_{cj}\cdot \big(\sum_{i=1}^{n-1} x_{ij}^{pq}\big)
\Big)
~\geq~
2\cdot(1+2+...+( \sum_{i=1}^{n-1} \sum_{j=1}^{n} x_{ij}^{pq} -1))
\]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kingtom2
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.05.2019
Mitteilungen: 82
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-06-03


Wie kommst du darauf, dass es weniger sind?
Es macht doch gar keinen Sinn die Summen auseinander zuziehen oder habe ich da einen Denkfehler?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1502
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-06-04


2020-06-03 18:51 - Kingtom2 in Beitrag No. 5 schreibt:
Es macht doch gar keinen Sinn die Summen auseinander zuziehen oder habe ich da einen Denkfehler?

Du hast vollkommen recht, der Denkfehler geht auf meine Kosten:
Auch wenn die \(x^{pq}_{ij}\) binär sind, dann ist ihre Summe \(\sum_{j=1}^n x^{pq}_{ij}\) längst nicht binär. Und wenn diese Summe nicht binär ist, funktioniert mein Vorschlag nicht.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kingtom2
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.05.2019
Mitteilungen: 82
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2020-06-04


Alles klar. Danke dir auf jeden Fall.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kingtom2 hat die Antworten auf ihre/seine Frage gesehen.
Kingtom2 hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  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]