Brauch wieder mathe hilfe :(

[Ramkhamhaeng]

Als Vorteile fallen mir spontan ein:
• Teilterme sind kompakter, insbesondere wenn die substituierte Variable mehrfach vorkommt.
• Man erkennt eine gleiche Grundstruktur in unterschiedlichen Termen leichter wieder.
• Die Schreibweise bei Stammfunktionen ist ähnlich.

[Tiramisu]

• Die Formeln sehen dadurch komplizierter aus, damit Außenstehende denken was für ein tolles Genie man ist.

[Ramkhamhaeng]

Ach Tira…

Schau dir die Formeln noch mal genau an. Die Notation der Ableitung ist da die kleinste Schwierigkeit.

[Tiramisu]

Es reicht immerhin aus, um meine Mutter zu beeindrucken.

[Ramkhamhaeng]

Das wiederum glaube ich aufs Wort

[Allmächtig]

Hallo

Ich mache gerade wieder etwas mit Linearer Programierung. Mein Problem ist, dass es etwas her ist seit ich das letzte mal den Simpexagorithmus gemacht habe und meine Skills sind etwas eingerostet, daher hier mein Problem:

Ich bringe mein Optimierungsproblem in Standartform:
max c^Tx
s.t. Ax<=b
x>=0

Jetzt stelle ich mein Simpextableu auf zusammen mit Slackvariablen s. Das sieht dann irgendwie so aus:
(I ist die Einheitsmatrix)
[A | I | 0 | b ]
[c | 0 | 1 | f ]

Jetzt fange ich bei der Basic Feasible Solution {x=0, s_i=b_i} an, und mache pivotsteps um mich von Lösung zu Lösung zu hangeln bis ich ein Maximum finde.

Soweit, alles gut. Meine Frage ist, was ist wenn ein b_i<0?
Irgendwie tritt dies bei keinem der Beispiele die ich so gefunden habe auf, und von dem vektor b wird meines wissens nach auch keine Positivität gefordert.

Stelle ich das Simpextableu gleich auf?
Ändere ich I_i von 1 zu -1, um das negative b_i zu kompensieren?
Was anderes?

Das negative b_i nicht zu beachten kommt mir Falsch vor, denn ein negatives b_i, bedeutet das meine Start Basic Feasible Solution ein negatives s_i enthät, Aber dann sind wir nicht mehr in der Standartform, da von den Slackvariablen s_i >=0 gefordert wird, genau so wie bei den regulären x_i>=0 gefordert wird. Aber 100% sicher bin ich mir gerade nicht.

Also was mache ich bei negativen b_i's?

[Ramkhamhaeng]

Hallo,

ich will mich nur um die erste Frage kümmern: Beim Simplex-Algo wird schon an den b-Vektor eine Restriktion gestellt. Er darf nur nicht-negative Einträge haben.
Allerdings kann man jedes Gleichungssystem dahingehend umformen, um das zu erreichen.

[Allmächtig]

Hmm ok, also ich würde dann folgendes tun:
a_i^T x<=b_i , b_i negativ
mit -1 mutiplizieren
-a_i^T x >=-b_i , -b_i jetzt positiv
und jetzt eine negative slackvariable addieren:
-a_i^T x -s_i = -b_i, -b_i jetzt positiv, und wir haben eine gleichung
Und diese Gleichung kann ich jetzt ins Simplextabeu einfügen, einfach mit nem -1 an der i-ten stelle der "Einheitsmatrix"

Sehe ich das jetzt richtig?

[Ramkhamhaeng]

Wenn du mit „negativer Schlupfvariable“ eine Hilfsvariable >= 0 meinst, die mit Faktor -1 in die Matrix eingefügt wird, dann sehe ich keinen Fehler in deiner Argumentation.
Ich war jetzt nur selber irritiert, und suchte eine Weile nach einem Fehler in deiner Argumentation, weil auf Wikipedia steht, dass bei neg. b-Einträgen so eine Konstruktion nicht geht. Aber das muss dann anders gemeint sein, als ich es verstanden habe.

In Gegensatz zu diesen Umformungen ist die immer vorausgesetzte Startbedingung b ≥ 0 {\displaystyle b\geq 0} b\geq 0 nur über die Lösung einer Hilfsaufgabe in einer sogenannten "Phase 1" zu erreichen; dabei ist diese Hilfsaufgabe grundsätzlich ebenso aufwändig wie die eigentliche Optimierung.

[Allmächtig]

OK, ich habe noch etwas gesucht. Das Problem ist dass ich das "-" nur "versteckt" habe, es aber immer noch da ist. Es ist keine Basic Feasible Solution was ich da habe. Um eine zu finden muss ich den Simplex Algorithmus ein mal durchführen, und dann von da aus nochmal um die beste Lösung zu finden.

http://www.mathcs.emory.edu/~cheung/.../simplex3.html

[Ramkhamhaeng]

Skandal
https://www.der-postillon.com/2015/0...ndschuler.html

[Snup]

Ich hab da mal ne Frage. Ich habe eine nach Gewichtung sortierte Liste (mit ner geraden Anzahl Elemente). Daraus möchte ich zufällige Paare bilden, wobei jedes Element nur genau einmal vorkommen darf. Jetzt kann ich mir zwei Varianten vorstellen, das auszulosen:

Die erste Variante wäre, dass ich einfach immer zwei Elemente aus dem Topf ziehe und daraus ein Paar bilde.
Die zweite Variante wäre, dass ich immer ein Element aus dem Topf ziehe und mit dem höchstgewichteten unverpaarten Element (das dann natürlich nicht mit im Topf ist) ein Paar bilde.

Meine Frage wäre jetzt, ob das im Ergebnis einen Unterschied macht. Und idealerweise auch wie ich (für beide Varianten, falls unterschiedlich) die Wahrscheinlichkeit für jede mögliche Paarung berechne.

[Gullix]

...also, sollte beides richtig sein. Also gleiche Wahrscheinlichkeit für jedes Paar, Wahrscheinlichkeit 1/(N*(N-1)). Ich würde einfach die komplette Liste zufällig anordnen, und dann sind die ersten beiden das erste Paar, die zweiten beiden das zweite Paar etc. Außer, du brauchst die Gewichte noch für irgendwas.

[BoggyB]

Sei 2n die Anzahl der Elemente. Ich gehe davon aus, dass es in einem Paar keine Rolle spielt, welches Element zuerst gezogen wurde (wenn also in einer Runde erst x und dann y gezogen wird, ist das genauso wie wenn erst y und dann x gezogen wird).

Sollen im Endeffekt alle Elemente gezogen werden? Wenn nur 2m (mit m<n) Elemente gezogen werden, hat die zweite Variante ja schon mal den signifikanten Unterschied, dass garantiert die höchstgewichteten m Elemente gezogen werden, was bei der anderen Variante nicht der Fall ist.

Auch wenn alle Elemente gezogen werden, macht es aber einen Unterschied.

1. In der ersten Variante werden alle Elemente gleich behandelt. Wenn du dir ein Element x aussuchst, ist die Wahrscheinlichkeit, mit einem anderen Element y gepaart zu werden, für jedes y also gleich groß. Konkret also 1/(2n-1) für jedes x und y (sofern x ungleich y).
2. Gucken wir uns als Beispiel mal an, was in der zweiten Variante mit dem Element höchster Gewichtung geschieht. Nennen wir dieses Element x. In der ersten Runde wird ein zufälliges Element y aus der Liste der 2n Elemente gewählt. In 2n-1 Fällen ist y != x und x wird mit dem gewählten Element y gepaart. Im letzten Fall ist y=x und x wird mit dem Element zweithöchster Ordnung gepaart. Das Element zweithöchster Ordnung hat also eine Wahrscheinlichkeit von 2/2n, mit x gepaart zu werden (es tritt in zwei Fällen auf), alle anderen Elemente haben eine Wahrscheinlichkeit von 1/2n.
   In der zweiten Variante werden also in jedem Zug bevorzugt die zwei Elemente der höchsten Gewichtung gezogen. Für jedes mögliche Paar die Wahrscheinlichkeit auszurechnen, ist wohl kompliziert (vermute ich). Man könnte problemlos ein Programm schreiben, das das macht, aber ich glaube, man kommt auf keine hübsche Formel. Auf den ersten Blick hätte ich vermutet, dass im Endeffekt gehäuft Elemente mit aufeinanderfolgender Gewichtung gepaart werden; aber auf den zweiten Blick hat man nach der ersten Runde ja "Löcher" in der Liste, sodass plötzlich Elemente aufeinander folgen, die das vorher nicht taten.

Edith meint noch, dass sie

(das dann natürlich nicht mit im Topf ist)

nicht ganz verstanden hat. Ich hab das so interpretiert, dass dieses Element danach aus dem Topf entfernt wird. Wenn das heißen soll, das das höchstgewichtete Elemente von vorneherein nicht im Topf ist, ist meine Analyse natürlich Quatsch.

Judith glaubt, dass das wohl so gemeint war, und ist geneigt, Gullix in diesem Fall zuzustimmen

Edith3 stimmt Gullix zu: Wenn das höchste Element aus dem Topf genommen wird und aus dem Resttopf ein zufälliger Partner gewählt wird, hat jedes Element die gleiche Wahrscheinlichkeit, mit dem höchsten gepaart werden, also 1/(2n-1). Gucken wir uns jetzt das Element x zweithöchster Ordnung und irgendein anderes Element y an. Ist y das Element höchster Ordnung, haben wir schon ausgerechnet, dass x und y mit Wahrscheinlichkeit 1/(2n-1) gepaart werden. Andernfalls muss, damit x und y gepaart werden, folgende Kette von Ereignissen eintreten:
- In der ersten Runde wird weder x noch y gezogen. Wahrscheinlichkeit (2n-3)/(2n-1).
- In der zweiten Runde wird y gezogen. Wahrscheinlichkeit 1/(2n-3).
(2n-3) kürzt sich weg, also hat man auch eine Wahrscheinlichkeit von 1/(2n-1). Macht man weiter mit dem Element dritthöchster Ordnung, wird es genauso weitergehen, also ist für jedes Paar (x,y) die Wahrscheinlichkeit, dass es auftaucht, 1/(2n-1). Wahrscheinlich gibt es irgendein Symmetrie-Argument, mit dem man dieses Resultat ohne Rechnung rausbekommt, ich war mir aber zunächst nicht ganz sicher

Edith4 (nach dem folgenden Post): Ok, alles Quatsch

[Snup]

...also, sollte beides richtig sein. Also gleiche Wahrscheinlichkeit für jedes Paar, Wahrscheinlichkeit 1/(N*(N-1)). Ich würde einfach die komplette Liste zufällig anordnen, und dann sind die ersten beiden das erste Paar, die zweiten beiden das zweite Paar etc. Außer, du brauchst die Gewichte noch für irgendwas.

Äh, die Gewichtung soll beim Losen selbst natürlich auch immer beachtet werden. Also es soll genau nicht die gleiche Wahrscheinlichkeit für jedes Paar entstehen.

Edit: Wahrscheinlich ist das vom Prinzip her dann dasselbe, nur dass N durch die Gesamtsumme der Gewichtungen ersetzt wird und die Wahrscheinlichkeit einer Paarung sich aus der Summe der Gewichtung der Elemente des Paares (multipliziert mit der Formel für die einfache Wahrscheinlichkeit) ergibt? Eventuell noch verdoppelt weil xy mit yx identisch sein soll?