Merken

Dantzig-Wolfe Dekomposition

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
wir fangen können so das er ne inhaltlich Weidermann gern und das letzte
Mal 1. in der Verfahren hatten abgeschlossen und haben uns mit lag Rage Leitzielen beschäftigt die den Unterschied zwischen Verfahren ist dann immer die Ganzheitlichkeit spielen aus System und bedingen die Ganzheitlichkeit spielen wieder rein in die Menschen Schnittebenen erzeugen in der Hoffnung dass man am Ende dann tatsächlich ganzzahlige Lösungen finden Knackarsch geht anders vor dem einst eine Teilmenge der Randbedingungen raus ich traf diese Randbedingung bei Verletzungen in der Zielfunktion behält aber die Ganzheitlichkeit im System war und dann das nächste Mal nach das letzte Mal nachgewiesen dass immer stehen geblieben das aber man darauf der Schrank erhält die mindestens so gut ist wie DLP Galaxie rum und natürlich auch nur möglich ist so gut wie ganz zeige Lösung und das ist in der Regel im oder zwischen legte schauen uns in der Übung an das 2. Wasser festgestellt haben diese Lage Hashfunktion 11 von Land also die smarten maximieren über die Seele aber Crashs Funktion besitzen maximieren über eine stückweise lineare konkaven Funktion ja es ist 11 und Lander stückweise linearen konkav und das 1. Mal stehen geblieben ist die Frage wie kriegen messen Maximum nur stückweise lineare konkaven Funktion aus das wollen uns heute anschauen und dann noch eine weitere Bilder Galaxie rungsmöglichkeit kennen lernen die sogenannte Tante Guste Komposition also in dem Sinne mehr von der Kompositions Methoden um einher gehen wollen und auch wieder ins Dateisystem rausnehmen aber dieses Preises dem reformulieren über die Idee die wir schon hatten Politiker lassen sich entweder über Durchschnitt endlich wieder halbe Räume charakterisieren ziehen oder als konvexe Hülle der Ecken wenn den Ecken gibt und der chronischen Kombination der extremalen ja und auf diese Art und Weise der genau diese Tat beim ausnutzen sozusagen dieses ist die Ungleichung reformulieren in der andern Darstellung dann wieder ins System integrieren und schau mal was da dabei rauskommt aber mal sehen dass man im linearen Fall auf jeden Fall die Lösung wird sogar einen gewissen Fällen ganz leicht gereizt weil auch da sie selber beweisbar die ganzzahlige optimale Lösung findet gibt aber es war noch zum letzten Mal noch Fragen bis dahin das Geräusche Erziehung gibt ist gut ist nicht der Fall dank wir sind das letzte mal genau an der Stelle stecken geblieben das also die Lage rasch Funktionen so aussieht es war also vom Bilder ist das irgendwie so eine Funktion stückweise lineare konkav es war dort das Maximum bestimmen wir also was wir tun wollen es maximiere Lander größer gleich 0 dieses L von landen so also sah es wie die Frage ist über angezündet wurde finden diesen Punkt ok was würde denn normalerweise tun immer so eine Funktion haben wie die klappt es also in dem Sinne immer so aussahen haben an mir sowas hätten dann wird man ganz klassisch einfach die Ableitung bestimmen mehr und bilden können und die Ableitung gleich 0 setzen eine Dimension des in der Halle in einem variablen eine Dimension ja und dort wo die Ableitung 0 ist haben wir potenzielle Kandidaten für minimal maximal oder Sattelpunkte in dem Fall und wir wissen dass es konkav ist ja ganze dicht an der Stelle wo wenn es denn welche die Ableitungen Nullstellen hat müssen wir damit eigentlich die optimale Lösung haben und auch das des extremen gefunden haben es eindimensionale alles ist im eindimensionale Malanda jetzt im höherdimensionalen Fall haben also in unserem Fall damals viele Ungleichung relativieren dann haben wir hier natürlich ein Vektor stehen alle heißen die Ableitung gravierend dass man gar den gleich 0 setzen dann ist man die Matrix angucken und dehnt und dergleichen mehr wenn das dem sind altbekannte Sachen das eine Problem was wir jetzt hier eben haben ist dass wir die Ableitung nicht haben in unserem Fall ich genau ansehen .punkt der sehr funktional nicht ableitbar also ,komma diesen klassischen Ansatz so nicht will dass mal den gravierenden ausrechnen bei den gravierenden gibt es nicht an diesen Stellen ok weil dort die Funktion nicht differenzierbar ist da so was macht man anstatt dessen ja anstatt dessen man erweitert einfach diesen Begriff dass gerade Enten und beschäftigt sich mit so genannten Zug gravierenden also was einig die Idee dass wäre nur brauchen ist folgendes wenn ich mir das im glatten Fall anschauen wenn ich irgendwann einen .punkt bin ja dann werde ich nicht so zeigen die Ableitung das heißt es gibt mehr der gerade jenen gibt mir einige Richtungen in der ich sozusagen Richtung Maximum laufen kann der und das ist das ist ja nichts anders als der gravierend von 11 Anlagen wenn ich ihn den hätte ja soll das hab ich hier aber nicht also hier hätt ich's ändern Sonderstelle bin ja dann bin ich natürlich glatt also und
dann kann ich natürlich auch diesen Vektor bestimmen es genau das Gleiche das Problem ist dass ich genau an diesen Eckfälle und na wenn man optimiert landet Mangan anzuregen an solchen Eckfälle in der Stelle gibt es keine gerade ihren ja habe ich aber in dem Fall muss sich auch nicht unbedingt was heißt ich könnte jetzt um weiter zu laufen kann ich sowohl in die Richtung könne nicht weiterlaufen oder auch in die Richtung ja sozusagen alles was in diesem Bereich ist ist er für mich in Ordnung er als in dem Fall gibt es im größeren Bereich der für mich in Ordnung ist ja und das nennt man Zug Differenzial ok also die erfüllt natürlich dann nicht im Ableitung 2. wie Gleichheit sondern mit kleiner gleich aber als er sicher brauche sich möchte irgendwie beider machen können und er und deswegen Weidemann diesen Begriff zu dem Zug Differenzial und dann schau mal einfach wie immer ganz konkret an jedem dieser Punkte Sohn zuckte Differenzial ausrechnen können und dann das muss und auch über die Schrittlänge gibt gegangen Gedanken machen ja diejenigen die Pleite nichtlineare Optimierung gehört haben die klassischen nichtlinearen Optimierungsverfahren sehen oder eigentlich alle nichtlinear Optimierungsverfahren sind so aus man bestimmte wenn der Schritt Richtung also der Richtung und und eine Schrittlänge also man braucht und weckt und da muss man auch überlegen wie weit man läuft letztendlich alle nicht deren Optimierungsprobleme basieren auf diesen es ist d. h gut also schauen dass man also Wasser aber sei es zu differenzieren ist die nächste Definition 3 36 2 L vom einer Woche nach er konkav wird dann heißt es oh aus und eine Woche im wird er ist und .punkt Bewegung im .punkt Lander 0 Subtrahend falls 11 von Lander -minus 11 von wir weil es 11 von langer -minus 11 von Land 0 kleiner gleich transponieren Lander -minus 1 0 für alle Länder ist ok so was steht hier wenn wir ableiten könnten ja und wir würden es auf die andere Seite bringen dann wird sie mit Gleichheit genau da gar die entstehen wir also eine Münzen haben würde wenn es dann auch ja entsprechend das heißt was wir hier machen ist aus diesem Gleichheiten kleiner gleicht Segen Suppe anstatt gravierend und können und dass genau das was wir brauchen nämlich genau an dieser Stelle mir erlauben sozusagen auch Pflichten die irgendwo dazwischen liegen ja nicht genau eine dieser beiden es sind gut so und jetzt ist die Frage natürlich Art tun dieses so gravierenden also wenn wir diese haben ,komma mit den tatsächlich hier zudem zu den Lander Sternen und wenn ja wie kriegen wir überhaupt zu so gravierend aus und sorgen dann kann ein Teil davon beantwortet war der folgende Satz ist der Satz wäre 37 also einmal sei Laendern 0 aus den er hoch M 1 jetzt in dem Fall x 0 der optimale Lösung für uns Optimierungsprobleme Linzenich ich das ist man noch mal reden gucken würde 3 16 zu also das ist sozusagen die Bestimmung von 11 von Lander also es sei ich soll optimale Lösung führe Minimum c't iX -minus LÃndern 0 B 1 -minus A 1 x und X aus mit 2 ja also viel gegeben und es Lander 0 vor und dann schauen uns dieses Hey Probleme nur noch über die A 2 X kleiner gleich B zu optimieren alles genau und 11 von Lander und 2 x 0 Sone optimale sehen können aus dieser optimale
Lösung direkt direkt einen solchen so gravierend aus wenn man dann dann folgt die 0 gleich A 1 x 0 -minus B 1 ist so gravierend ok also direkt aus der App Bestimmung von El Lander Jahren die optimale Lösung die eine optimale Sixt nur den 11 von Lander 0 gesteht dass er von einer 0 bestimmen also das Ding ist ja gerade L von lagen am 0 1 genau die wird uns Lektion zu
koordinieren und das ist genau dieser Vektor der hier oben steht ja ok so das ist die die 1. Aussage lieber da stecken haben also das ist schon mal nett sozusagen mein des L von landen und des Mehr I ausrechnen unbedingt zum Nulltarif sozusagen gleichen Sub gravierenden geschenkt ist das eine bis 2. ist wenn wir sonst operieren haben also jetzt wissen wir wir haben den soll jetzt können wir die beide Richtung Maximum marschieren die Frage ist wann würde man aufhören sollen dann auch dann kann man genauso wie in dem Fall wenn es differenzierbar ist bei langen darstellen maximiert die Funktion L genau dann wenn 0 bis zu gravierend an L in Land stand also bei die 0 Datteln auftaucht ist das immer sehr dick und können auch noch beweisen die 1. Aussage ja rechnen wir einfach los das Ende mit mehr oder weniger einsetzen also 11 von anderen -minus 11 von anderen 0 so dass jetzt das einfach mal in die Definition ein also wendet die zugehörige Lösung zu den Lander sei X langen da dann ist es so c't iX LÃndern -minus Lander transponiert B 1 -minus A 1 x Lander für den 1. Teil -minus c't iX 0 namens 1. die Klammer -minus 0 transponiert B 1 -minus A 1 X 0 ok es einfach Definition eingesetzt so jetzt machen wir aus dem jetzt machen aus diesem Land das Tier in mir nein 0 weil das für mich die ich in Erinnerung also wenn wir hier immer aus diesen aus diesem anstatt diesen X LÃndern x 0 setzen dann wird das 6. größer der SX Lander ist ja das Minimum hier wir diese Funktion das heißt x Lander selber ist zu lässig und x 0 ist auch offensichtlich zulässig für x aus P 2 aber ist möglicherweise nicht die optimale Lösung bezüglich Glander also können wir sie abschätzen indem man hier jeweils sind die 0 oben schreiben wir den Rest lassen ok so und jetzt wenn wir das uns anschauen was bleibt noch stehen soll hier steht c't iX 0 wird 7 des c't iX soll wieder ab hier steht Stätten wie 1 -minus a 1 x 0 das gleiche steht dienten auch das ist genau unser GG hier -minus G ja das heißt das Ganze ist aber das schreiben ist nix anderes als gegen 0 transponiert Wallander -minus Land 0 ok also ist wirklich kein Hexenwerk was da dahinter steckt und wir haben genau diese Definition erfüllt die wir hier stehen haben da L von anderen -minus Land neues kleiner gleich gegen 0 transponiert landen das Wandern und so das ist das ist die eine Geschichte sowie 2 ist sozusagen mein können wir aufhören also genau 0 Zug Differentiale ist also zu be was soll wir dazu tun wenn es eine ist also die eine Richtung wenn Höhenzug Differenzial ist ja was steht dann da und dann steht hier 11 von Lander -minus 11 Anlagen nahe 0 ist kleiner gleich 0 transponiert es soll ja man Wilander Stern so soll es in den Schubladen ist kleiner gleich Landa -minus Lander Stern ja also wenn die Nullen Zug Differenzial ist bezüglich Lander Stern beim belaufe sich die Beziehung hier steht er noch bei Definitionen 0 transformiert das ist gleich 0 mal das heißt daraus folgt 11 Anlagen da ist kleiner gleich 11 von Laiendarstellern für alle Lander das heißt an der Stern maximiert die Funktio soll es die eine Richtung ja die andere es genau das gleiche dann nämlich die Beziehungen aus dieser Beziehung folgt natürlich das 11 von voneinander -minus 11 voneinander Stern ist kleiner gleich 0 ist nichts anderes als es kann gänzlich lustig bin ich hier Bregenz ist so ist nix anders als 0 Dransfeld Land ist dann der Stern also daraus folgt 0 bis so gravierend zu sein gut so das heißt damit haben wir jetzt aber auch schon eigentlich direkten Verfahren zur Hand ja warum also der gegen 0 der zeigt uns wenn wir uns das wiesen gegen 0 mal anschauen alles Gelder offensichtlich gegen 0 transponiert Malanda -minus Lander darstellen Wallander Standes was anderes Selander Stern -minus LÃndern 0 ja ist sicherlich größer gleich 1 EL von Laiendarstellern -minus 11 von anderen 0 und von dem Wissen 1. größer gleich 0 ist soll das heißt unser gegen 0 zeigt uns tat sich in die Richtung wollten also sie gehen alle wissen wie es in einem Punkt wissen gegen 0 zeigen die richtige Richtung und ist laufen einfach in diese Richtung ja einzige Frage noch offen ist wie weit aufmachen wer welche Schrittlänge nehme und Na ja das da gibt uns der folgende Satz dann Auskunft über bevor man den uns anschauen und schauen was vielleicht das generelle Verfahren an also wir fahren erlauben wir machen sowie lösen einfach für den Lander sei ich am Anfang dieses Problem hier was hier steht und das ist einfach über den P 2 das sind allerdings die ganz ehrlich das Bedienen dabei dann Crime daraus unser gegen 0 wenn zufällig in die 0
sozusagen die 0 die 0 ist und Größe der das kann man auch leicht erkennen an dieser Stelle nur ob sozusagen nur in dem Fall möglich wäre dann sind wir fertig wenn nicht wenden wir einfach auf Flandern des gegen 0 an agierendes drauf kriegen neue Landers ja und der die in den ganzen Prozess so das ganze Verfahren über das auf das man sich so gravierenden Verfahren also ich werd das mal zusammen Algorithmus 3 38 so gravierenden Verfahren also Input des Input-Output lassen oder in 14 Input L außen am im der Erde konkav Output Max 11 von Hollander Lander größer gleich 0 so was machen wir als 1. Welle oder andere 0 wir Landa 0 Billie weg das setze und Zulauf Index gleich 0 im Skript jetzt komisch aber es ist lang oder unten stehen es ist besser glaub ich um also wäre der Lander 0 aus Billie Weg soll das 2. es bestimme bestimme L von klar ja und 2 x K die optimale Lösung sei X K optimale Lösung dazu doch lösen von diesem Problem was hier oben haben er stets nochmal ja und dann soll es kann es kommen schon die vagen Formulierungen wir wissen in der genauen aufhören das muss man überprüfen also Zeit leider was dazu ist Stopp Kriterium erfüllt gut dann Stopp wo es würde immer so allgemein so und dann kommt der nächste Schritt so Welle geschaffen werden Landtag K +plus 1 durch Lander K +plus 1 =ist gleich das alte Land Dakar +plus genügt kam GK wobei NYC war jetzt eine noch festzulegende Schützlinge sollte Jahren Jannika also Milka außen +plus und die Schrittlänge und dann 10 den Zähler hoch 5 könne dazu K +plus 1 und das war's ok also eigentlich hinten ziemlich einfach das Verfahren damals angucken was sagen habe ich jetzt offengelassen einmal das sehen da ich gleich noch etwas dazu sagen oder der nächste Satz sagt was dazu und das 2. ist jede dieser .punkt also und sonst ist das Verfahren eigentlich festgelegt ja und weil das ist die Bestimmung von dem es ab ist klar dass es ein Gemisch seines Lehrers Programm mit den jede beliebige optimale Lösung denn damit immer den Gradienten sei es das einzige wo man wirklich noch Wellen können ist sozusagen hier an dieser Schritt Schrittlänge und so sehen noch typischerweise alle da nicht länger Optimierungsverfahren aus das sind sie interaktive Verfahren um mir die Richtung hat Lust die Länge und es gibt den 9 Punkte überprüft so die Frage ist jetzt .punkt wie wählt man diesen Lys wüst und B keine die so wählen dass sich hier ein vernünftiges gibt dem angeben kann dass ich tatsächlich immer ein am Schluss die optimale Lösung find beziehungsweise zeigen dass am Schluss tatsächlich hier bis gegen 0 der 0 Vektor ist an so kann was was ist was für Voraussetzungen müssen wir denn an dieses an dieses Menü darstellen also was sind also Vorschläge also typischerweise ist es ja so dass man am Anfang also was ist eine Wohnung .punkt war keine Ahnung sozusagen wo das Maximum liegt was wird man Anfang versuchen sozusagen nach Möglichkeit in großen Schritten möglichst nah an das Ziel zu kommen aber es irgendwo also versucht man anfangen vielleicht mit großen Schritten erst mal in die richtige Richtung zu kommen es geht zeigte in die richtige Richtung war die einzige Gefahr den man mit großen Schritten hat ist dass man vielleicht drüber hinaus schießt also wenn ich unseren Bild hier oben welche Links Anfang nicht erlauben die gelbe Licht damit bislang zu groß wäre erlaube über den Hügel über Land auf der anderen Seite am Anfang vom Prozess ist vielleicht gar nicht schlimm dann glaube ich halt formale auf die an das Seite wieder hin und her aber irgendwann soll ich natürlich mal anfangen sozusagen dieses das Überspringen des Maximums aufzuhören also muss sich kontinierlich dieses führt aber weiter reduziert und das ist das was man typischerweise macht es so zu sagen dass man sukzessive Gisela also die sich in diesem Nüs gegen 0 gehen lässt er damit das Verfahren überhaupt konvergiert also eine notwendige Voraussetzung ist dass die sind müs im Laufe der Zeit gegen 0 konvergieren es ist nicht tun kann im oszillieren war also ist eine notwendige Fahrersitz Ding stellen was muss ich noch einige Stellen muss noch eine 2. Stelle nämlich das Ding gegen 0 geht muss auch dafür sorgen dass egal wie weit ich weg bin dass ich auf jeden Fall mein Ziel ich Mehr also wenn ich alle Schrittlänge auf die da muss es mir dabei am muss sich auf jeden Fall zu Maximum kommen können also und ich weiß ja nicht wo ich am Anfang starte mein 1. Lander 0 selbst völlig willkürlich gewählt das heißt ich muss einig auch dafür sorgen dass wenn ich alle Schrittlänge auf zu mir ich garantiert ihnen kommen das heißt die Summe über alle Schritte lenken muss divergiert ja so bisschen genau die 2 Vordersitzen die man braucht ja einmal die so musste übergehen und die Folge selbst muss zu 0 konvergieren ich die 2 Voraussetzungen habe wir dann konvergiert hat sich das Verfahren an das sagt der
folgende Satz ist der Satz 3 39 also auf ist L nach oben beschränkt und gilt einmal der Linie S die von 3 =ist gleich 0 für tragen endlich und Summe der NYT K bis plus unendlich K gleich 0 bis unendlich dann folgt Lines 11 einladender K =ist gleich L von anderer Staaten für kamen gegen unendlich und das geht zurück auf Torejagd 1900 67 hat das Baby ist den Beweis schenken uns 1. dass die beiden gibt den notwendig sind wir haben uns gerade arbeite das sind auch hinreichend sind das ist sozusagen der Beweis und deswegen ist auch dem Projekt zugeschrieben ja Beispiele für solche gibt überhaupt solche folgen dieser Film und 1 ist 1 wer kennt noch einer aus und alles ist ein sehr genau also wie harmonische Reihe oder die Folge eines doch n erfüllt dieses Kriterium an also Folge 1 noch n für n gegen unendlich geht gegen 0 aber das Summe er ist doch klar das heißt er war wahrscheinlich bei Ihnen auch eine nette Übungsaufgabe Anfang das das denn tatsächlich dirigiert divergiert tatsächlich soll das ist das eine ist es natürlich dass aus theoretischer Sicht aus praktischer Sicht hilft das ehrlich gesagt nicht so wirklich weil ich meine 1. Liebe SKG nun endlich wir wollen den unendlich lange auf das Ergebnis warten zumal zumal wir ja eigentlich ein ähnliches Problem war also unser Ausgangs Problem weil dies Lösung eines Gemischs ganzzahligen linearen Programm ist auch wenn das endlich schwer ist so wisse man doch zumindest dass wir das in endlicher Zeit lösen können vorausgesetzt das Problem ist beschränkt und das habe ich ja auch vorausgesetzt ja also ,komma eigentlich vom Regen in die Traufe aus dem Endlichkeit Resultat machen und plötzlichen und Konvergenz Resultat und deswegen muss man eigentlich an dieser Stelle für deswegen gibt es hier die 1. Stopp Kriterium das heißt man muss sich Gedanken machen sozusagen waren ich diesen Prozess auf waren und das typische ist also der in der massige Verläufe anschaut Phondsanlage Funktion macht am Anfang einen schnellen Fortschritt und irgendwann dümpelte so vor sich hin haben wir diese Funktion L von Lana mal Platte dieser die steil am Anfang hoch und dann dümpelte so vor sich hin macht's immer noch ein bisschen Fortschritt aber relativ wenig und dann muss man irgendwann sagen Herr brech ich einfach ab um bei irgendwann sagen das muss man sich halt wirklich das Problem selber angucken wie gut man dann tatsächlich ist wir berechnen also so auch sagen es nicht nur Schranken also galaxy errungen werden ob ich jetzt aus letzte und so zeigen sie untere Schranke Anschluss rausbekommen hab dann ist vielleicht dann auch der Aufwand der Wert am Ende gut also die Frage ist wann wende man denn sowas gerne an oder wenn wenn es ganz konkret versum Problem stehen wer wann wird man denn erst diese Schnittebenen machen oder wanderten wir den Lage rasch machen und wenn wir jetzt sagen wir machen viel Agrarschau muss dafür entschieden welche Randbedingungen schmeißen oder raus ja das sind sozusagen zu üben brauchen sozusagen 2 Herzen in einer Brust wenn man so will weil wenig möglichst viele Randbedingungen rausnehmen er wird man dich meint das Problem des P 2 wird dann einfach ich kann ja auch der Ansatz funktioniert aber nicht alle Randbedingungen aussenden er manche einfach weil Optimierungsproblem oder ein wenig nur 0 1 2 Jahren hat er in 0 x zwischen 0 und 1 und alle Randbedingungen einst eine gleich be schmeißt sich in die Zielfunktion das unser Problem kann ich super einfach müssen würfelig aber da kann ich locker mit oder ein Zielfunktion kucken sozusagen welche positiv sind die Park ich alle die anderen wieder geht es in ich nicht mehr also nämlich nach oben Park umso leichter wird ein Mann tot meinen Teil Problemen also schmeißt alles nach oben ja ja ein weil die man schmeißt umso mehr Land um und umso mehr Land das muss ich mich kümmern dass also die Dimension des komm Grafen Optimierungsprobleme Next natürlich mit jeder mit dem nach oben gehen da und das heißt mein Verfahren ist ein überdimensionales Verfahren also hier die Landtag Gras das heißt es wird entsprechend auch länger brauchen wir also was sich zur Lösung des Tals Gewinne früher sich eventuell wieder ein oben dann sozusagen bei Migrationsprozess wenn dieses so Präsidenten Verfahren anwenden also deswegen oder im abwegiges sozusagen aber was mache ich wo oder welche Teil nämlich raus wir hier nämlich nicht draus Untreue häufiges ist auch aus der Anwendung heraus schon so dass man das Maoming klares Bild klickt wann man welche welche Bedingungen ausnimmt also möchte vielleicht noch auf 2 Beispiele kurz erwähnen und so ist Anwendungen also die 1. einig dass und wo das 1 1. mal richtig erfolgreich auch angewandt wurde war es allerdings selbst man Probleme und also der längste ist ein Problem im sagt das ist nichts was einen Felsen Problemen also haben gegebene Anzahl von Städten und dem möchten die kürzeste Rundreise doch diese steht der irgendwie finden an das ist das Drawings ist beim Problem wer kennt noch keine ganzzahlige formuliere es ganz Tagesprogramm von der Wiese ist Problem aber Hände gehen hoch gut Commons es mal an die wird man so was machen wir also und wie wird man ist allerdings erst ein Problem was Ganzjahresprogramm formulieren also werden die Städte immer machen man der Einfachheit halber während
vollständigen da also geh gleich vor Ort ,komma E vollständig es sind alle potenziellen Verbindungen darin einig der Werke Mehr als Gewicht und endlich drauf draufgeben oder ziemlich große Zahl dass Sie nicht gewählt wird so was was müssen wir Entscheidungen fällen also das 1. was für Variablen brauchen um am Schlusse Jahrmarkt Knoten i Hermann Knoten ja wir wollen letztendlich wissen zu sagen welche kannten wählen wir also brauchen wir sozusagen als Variablen Exil J ja es 1 falls ihr aus E in der Tour vom 0 sonst könne so dann dann minimieren da die uns der Zielfunktion also sei dass wir minimieren Summe c und XI hat ja aus E ja wir natürlich als Randbedingungen sicherlich gleich mal hier hierhin die müssen alle aus 0 1 sein so was noch das alleine reicht und her genau also in jedem Kloten müssen was eine Reihe heraus also Summe ich hab das mal kurz vom er hat aus Wälder von Frau XIV muss gerade 2 sein müssen das ist also für alle Frauen Hausfrau ok reicht es zusammengenommen noch her also was sie jetzt mit diesem Bedingungen allein passieren also sowas nur wenn man das meine Knotens sind ja ganze kurz Zyklen geben also ich hab zwar ihre Claude mal genau denn genau 1 rein 1 raus aber es sind halt nicht zusammenhängend das heißt man muss es jedoch diesen Zusammenhang modellieren so also wie modelliert man Zusammenhang das heißt über jeden Schnitt muss mindestens 1 drüber ich hab hier Schnitt das heißt alle kannten die hier drüberlaufen davon muss ich mindestens eine wäre ich gucken also hier alle kannten darüber an das gleiche versehen und von in einer von dem muss ich wählen wenn dass das Töten und so aus man schaut sich alle je jetzt aus der davon wie an X ist größer gleich 1 für alle wie Teilmenge von Frau und wer es es und die Hälfte wir müssen da wie dem Kalender bis es stärker machen weil ich Weise also wenn ich auf die andere Seite gehen wieder zurück ich habe eine Rundreise so ist aus der einst wir auch mit 2 machen an so brauchen wir noch etwas es muss muss eigentlich haben wollen aber Romig sehen wir dass ein wer das ist 7 genau über das über dieses Argument 1. hier ist wir wissen ja in jedem geht einer reinen geht ein raus wir ja das war sie fallen würden Knoten i an ich weiß mit der Bedienung muss einer rausgehen in ihrem anderen Knoten nachdem es mir gleich 2 ist uns wieder einer ausgehen dann soll es glaube ich so weiter muss wieder heraus das jetzt 2 Möglichkeiten entweder ich treffe ich Lauf über alle oder ich mach doch irgendwann zurück aber es aber ein Knoten vergessen es genau dort wo ich hierzu Rücklauf nein das ist und wie was offensichtlich diese Bedingungen nicht erfüllt aber nachdem die erfüllt sein muss als muss ich jeden kann mitgenommen haben das heißt ja tatsächlich Natur doch können so das ist ist tatsächlich nur ganzzahlige Formulierung für das Drawings ist mein Problem so wie jetzt schauen wir uns mal anders würde was würde Lagasch machen jetzt an dieser Stelle also ziehen wir als mal ganz konkret zum Beispiel als bietet sich jetzt gegen sie einig 2 Dinge andere hin die raus oder in diese Klasse von Bedingungen auf so wenn ich die rausnehmen ja und dann kriege ich hier oben was bitte was was kann ich hier vielen Problem ganz sei Ehrgeiz begeben so würde ich sie ja gleich 2 das ist kombinatorischen 2 Mädchen Problemen also für die englische noch nicht Grabmal Gewinn gab das Mädchen ist sozusagen ich verbinde sozusagen Knoten paarweise dessen Mädchen daher der Name der und 2 Mädchen heißt jeder Knoten ist genau mit 2 Kanten Incident das heißt 2 Mädchen normal essen Einfalls Mädchen heißt jeder Knoten es höchstens mit einer kann in und 2 Mädchen weiß genau mit 2. ok also dieses Ding hier modelliert man 2 Mädchen das lässt sich kombinatorisch sogar lösen also gibt Algorithmen der für diejenigen die sie für Grafen Algorithmen interessieren können dann das mal nachlesen auch das heißt wir gegen mich das rausschmeißt automatisch ganzzahlig kalt wir haben über diesen kombinatorische Algorithmen des einige auch die DG Verlag Arsch zu sagen nun Teil raus zu das was bleibt auch wenn ich die Ganzheitlichkeit dabei hat das sich direkt exakt lösen kann oder vielleicht sogar nicht über ihn LP Methoden sondern über kombinatorische Algorithmen und es geht in dem Fall an so Nachteil von dem Verfahren ist aber viel viel viel viel Brandbedingungen schmeiß daraus das gibt der exponentiell viele Städte für Schnitt wegen schwimmt besteht gibt es wieder eine Bedingung war Einserschnitt gibt's ein liegt die Funktion packt und sich da in dem Verfahren exponentiell viele solche Landers kontrollierten so bisschen aufwendig alles Dithmarschern gesagt möglichst viele rausschmeißen vereinfacht zwar ein Problem aber wenn man enormes Problem dann um in der Zielfunktion insbesondere beim Zug oder deren Verfahren vor es gab mal einiges an noch probieren wir schmeißen wir aus lassen wir denn was ginge denn dann
endlich im Wesentlichen aus spannendes Baum
Probleme nahmen sich erinnern über jeden Schnitt muss mindestens 1 drüber gehen noch mal hier mal mit 1 wegen Schnitt muss mindestens 1 drüber gehen das ist genau ne Formulierung für das auf spannende Bauten und blähen also Zusammenhang in einem Graben sowie gesagt damit Mode Zusammenhang in einem Grafen wir minimale Struktur die zusammenhängt ist wissen bauen er nehme Ausspanne Bäume kann man auch wieder super einfach berechnen diejenigen die Grafen Algorithmen schon mal gehört haben gibt es verschiedene G iPhone zu jeder Greedy Verfahren ja groß gerade und blieben sind die 2 die 2 Alternativen da vorgeschlagen haben aber beide Willuhn offene wie die Ideen also lässt sich's relativ einfach implementieren und man hat damit alle Export ab Enste exponentielle fielen und diesen Randbedingungen kombinatorisch erschlagen war und kann sozusagen an dieses mit den aus exponentiell viele Randbedingungen 10 und diese 0 1 bedingt kolonialer Zeit lösen so und damit und jetzt hat man nur noch viel anders nur noch an 2 Knoten viele wir haben quadratisch viele Variablen aber nur an Knoten viele Landers das heißt dieser Ansatz scheine es zumindest auf den 1. Blick deutlich vielversprechender als die an der Klasse von Uplay hochzunehmen und der Sound tatsächlich enorm gut das muss man so also es gibt Implementierungen von diesem Verfahren ein kombinatorischer den Zusammenhang hat meiner später gesehene gab schönen Fünfziger glaube nur 16 gab es von den Königen Verfahren was genau auf diese Idee beruhte wenn man den dann diese der Lektion die und dann die 1 Baum genannt was bisschen Erweiterung von ausspannen Baumes was sich im Modellieren lässt aber letztendlich mit dieser Idee kann man rein auf kombinatorischen Ebene dass solche Schranken für das Drawings ist mein Problem aus und die sind ziemlich gut also ,komma bis auf ein 2 Prozent in aller Regel bei bei den praktischen Probleme mit dieser Schranke in keiner rein kombinatorisch also da ist ein Beispiel wo agrarisch auf jeden Fall Sinn macht dann würde es noch mal vergleichen angenommen worden LP Galaxie ungelösten das ist die ganz zeigen der 1. Ansatz ja zu sagen lasst uns die ganze Calls bedienen rausschmeißen können überhaupt dieses hier lösen mit Garage Grad gesehen die polynomial den Belag Arsch und wir wissen lag Rage Abend sie kommt das der mindestens so gut ist wie DLP Galaxie also Klima hier eine zum liege die Frage wem wir denn wenigstens ich den andern Ansatz hier vor er wenigstens die Apple-Aktie ist ja ein exponentiell großes LP ich hab hier die ihr entfielen Jahre exponentiell fiel das heißt ich kann es den maximal gelöst die allerhöchstens gelöst kriegen mich nicht explizit Aldi sie auch für ein nur dann funktioniert wenn ich die alle einmal ausscheiden muss hab ich dann exponentiell großes LP und als ich dann das in linearer Zeit lösen könnte er schon verloren also ich muss das LPI lösen ohne dass sie explizit alle Ungleichung auf ist geht das gut zurück in die Einführung und Optimierung hat aber diesen Gegensatz bewiesen dass der Barriere =ist gleich optimieren das heißt wir können und was hat dieser Satz gesagt also Optimierungsproblem ist polynomial Erkelenz uns dabei die Jungs Problem das heißt ich kann über so ein Problem optimieren genau dann wenn nicht reparieren kann also muss ich erst einmal überlegen kann ich über diesen Problems reparieren es kam uns überlegen können wir das ja wir können uns nur also die ,komma explizit dazu müssen Sie nur linear viele kam auch ein Fass der bei dir überprüfen alle wenn ja vielleicht die kleine erfüllt ist was ist mit den is das nix anders als der Schnitt Bedingung ja müssen nur schauen ob so schnell gibt dessen Wert kleiner ist als 2 also was tun wir wenn wir rechnen minimal Schnitt aus eine minimale Schnitt kleiner ist als 2. gibt offensichtlich mehr Verletzte Ungleichung verletzen steht dazu wenn das Minimum größer gleich 2 ist wissen es gibt keine Verletzten schnell also haben wir damit Hausgesinde können minimal steht berechnen können wir das bei die das Problem lösen und nachdem das bei der verbliebene lösen können sagt uns der wie gesagt sie besser bei den den optimieren wir können auch über diesen in ihrem Programm optimieren obwohl es exponentiell viele Ungleichungen gibt er so minimal Schneedecke mal ausrechnen dass er uns allen den Grafen Algorithmen oder aber auch mitten in der Vorlesung die kommt der minimale Städte dazu gehörten maximaler Fluss maximal Fluss muss mir die Marder dieses total ohne modulare dagegen automatisch ganzzahlige Lösungen Geschenk drang aber damit sozusagen implizit auch in Polen wie alles Verfahren um wenigstens die LP Galaxien auszurechnen trotzdem es lag aber ich erst mal mindestens genauso gut aus also das sieht man schon an diesem konkreten beispiele das ist viele Varianten gibt und um ganz sei Hologramme zu lösen und es nicht immer nur die eine richtige gibt aber dass wir zumindest auf verschiedene oder unterschiedliche einzig den zum Problem braucht um überhaupt das beurteilen zu können was ist denn ein gutes Verfahren was nicht vielleicht noch als 2. der hier als 1. geschrieben 2. klassische Anwendung von solchen Verfahren sind 10 Madrid mit Blockstruktur ja also wenn meine Matrix aber eine mit dem Sony aus ja ich hab hier verschiedene einzelne Blöcke mit ziemlich viele ja und dann habe ich hier unten im größeren Satz von Randbedingungen der die miteinander verbindet also Beispiel mal die Kommode die floh Problem er sie am Netzwerk sie möchten von A nach B etwas transportieren Max ist maximale Fluss Problem ist so 1 aber haben nur eine Kommode die Mehr mehr also nehmen wir mal an eben diesem Block stecken Fluss kann ja es gibt hier wenn es unten und ich möchte hier möglichst viel von es nach Nachtlebens portieren ja das hab ich jetzt wie es ein sind P ein zierlicher waren es 2 unten T 2 und so weiter ja welchen SK und Entdecker ja bei ein und denselben Grafen mit gleichzeitig Güter von nach der 1. und von S 2 nach D 2 und die darf man nicht mindern da mich an zum ich muss die Kommune sondern unterscheiden aber die müssen Sie alle das gleiche Netzwerk laufen war das heißt es gibt viele bekannte der Kapazitätsbeschränkungen wie viel diese kann den maximal gleichzeitig aufnehmen kann also es sind einzeln Commodities er weiß über die Kapazität auf dem Grafen gekoppelt und dass sich diese Matrix anschaut dann hat die genauso eine Struktur so und eigentlich können wir schnell lösen ja ein Kommode die können wir lösen maximales Fluss Problem bisher mir der schnell ist das Dumme ist nur dass es die gekoppelt ist er und da bietet sich ihm genau Lage rasch an die Dinger stecken auch in die Zielfunktion dann kriegen wir hier plötzlich K unabhängige Probleme die wir alle hintereinander oder oben Parallelrechner gleichzeitig ausrechnen können war und und können damit dieses komplette eigentlich riesige Probleme muss ich mal überlegen also so nur als um Beispiel zu nennen vor 2 3 Jahren kann man es ab Werk gefragt ob es um alle Kommunen vor Probleme lösen könnten führen eineinhalb Milliarden Variablen und eine Milliarde Video das war genau von Sohn Typen an ist wenn sich die großen Distributionen sind an wie Edeka oder Rewe da müssen Sie Commodities transportieren ja das sind die Kommode dies hier Milchflaschen Brot und was sich in Eier und wir und die Tracks gab es diese Bewegung stehen ja nur beschränkte Kapazitäten haben waren und die Frage ist wie packen Sie jetzt die LKWs wollte so dass sie möglichst viel oder möglichst kostengünstig wenn es auch als Ministerin auffassen die Dinge transportieren so dass sie beim Endkunden auftauchen wenn sie mal schauen so groß wie Aldi das sonst jemand ja für Filialen die Störung stehen haben welche der organisatorische Aufwand dahinter ist und auch sozusagen
Logistikprobleme stecken letztendlich solche Probleme dahinter unsere Probleme kann man nur lösen wenn man sie die komponiert er sich haben sein wann ich ein halb Milliarden variabel und Randy den allein das Problem einzulösen waren schon mehrere Gigabyte einer Platte überhaupt und das 1 zu lesen geschweige denn dass das ihren Rahmen oder 1. einbringen um überhaupt das optimieren zu können wir da um solche Dinge also bekommen das Problem nicht lösen ich Deutschland verlieren der Stelle der zu ihr gesagt er müsse ein bisschen baden im Millionenbereich Traumas uns heute schon zu aber Milliardenbereich weit so weit Zimmer mit den den Toten dann doch noch nicht an also dass auch da damals liegt ja auf der Hand der Lack rasch Ansatz zu machen will wenn uns Sony Struktur gegeben hat gut so weit Zulage Raasch gibt es da noch gibt es da noch Fragen zu den das nicht der Fall ist schauen wir uns noch eine Variante noch 2 Varianten eigentlich an ja was sehr ähnlich sind eine ist die auf Danzig und Wulff zurück deswegen heißt sie auch Dance größte Kompositionen und wie macht eigentlich -minus die gleiche wie viel agrarisch man kann es nennen Menge von Randbedingungen raus nur packte die nicht in die Zielfunktion sondern er formulierte und steckt sie wieder in in das Problem selber nach ja also Danzig Wulff der Komposition dann also erstmal 3 dreiste tionsmethoden .punkt und 3 3 1 ist erst mal dann sehr gut es geht zurück auf ein Petra von den beiden das sind erkoren von 1900 60 Mark also wir schauen uns genau das gleiche Szenario an wie vorher an viel agrarisch also minimiere c't iX A 1 X kleiner gleich B 1 A 2 X kleiner gleich wie 2 und X aus z u n oder Zeitung was hat mir gesagt ist P ZUM ESP Kreuz und der anders rum ich jetzt hier ihr das P und die über alles er -minus P ich fange an das Problem zu erklären für P gleich 0 also wir tun erst mal so als wenn keine ganzzahligen Variablen da und schauen uns erst das Prinzip an und dann überlegen uns was geht an vor die Skifirma wird sich ganzzahlige Variablen dabei soll es aber immer also genau das Gleiche und hier in dem uns diesen Teil hier wir in dem ein Teil raus ja wir wissen ja dieser teilte sich beschert uns auch wiederum pro Lieder also wir können wir wissen wenn wir das wieder P 2 er ist die Menge aller X mit A 2 x kleiner gleich B 2 essen Polyeder der von diesen Polly jeder wissen wir wir können das Schreiben als konvexe Hülle von der Menge von eine endliche Menge von Vektoren plus einer chronischen Kombination ebenfalls für endliche Mengen an so wenn es pro lederne Ecke hat dann sind das genau die Ecken wenn es nicht 10 sei entsprechen .punkt auf dem minimalen Seitenflächen also der Einfachheit halber sagen was die konvexe Kombination decken plus die chronische Kombination der extremalen so also das heißt wenn uns das hier anschauen wollen jedes Ex was das erfüllt lässt sich so beschreiben kann also ich kann es einfach schreiben X aus B 2 kann ich schreiben X ist nix anders als Summe Lander IVE +plus Zunge je J ich vorher noch dass die Summe der Lander E gleich 1 ist damit habe ich das hier modellierte so und jetzt setzt sich das hier wieder da ein sowas Klima dann ja also hier eingesetzt folgendes minimieren zur c't wird es einfach für das dass eine Summe Lander IV E-Plus Summe New York er hat unter der Nebenbedingung A 1 soll es wieder das Gleiche hier kleiner gleich B 1 1 1 7 7 noch eingehandelt habe ist dass die Summe der Lander E gleich 1 ist nun so und und dann da und das beide müssen größer gleich 0 sein so nur dass es umschreiben es kann ein bisschen anders schreiben wer Ismail unseren ja was ist unsere neuen an den Westen den Variablen ist X ist es verschwunden unserer Jahresende zusammenbauen des Nil das und das es wird unser Variablen so das heißt wenn dass es was aus Sicht unserer Variablen schreiben das kriegen wir dann damals der Vollständigkeit halber hindern hier Summe c't war ihm Wallander I +plus Summe c't er hat malen wir hat und wir haben die Summe zur A 1 V E Malanda E +plus Summe A 1 Ei Ort mal New York zu kleiner gleich B 1 und wir haben immer noch Summe Verlangen der IG gleich 1 n so nur die beiden jetzt mal vergleichen also wir haben nix gemacht außer umformuliert bislang ok wir
unsere ob Original Problem es wenn X aus Abu en und das ist unser aller tief Mundl welches finden sie sympathischer welches von beiden würden sie versuchen zu lösen dann wäre es für die Linke sollte 1 2 das für Rechte auch zur Wahl in andere die könnten er war bis vor Nachteile für das eine oder andere wir aus die kennen wir nicht dass ich dich ja würden Sie kennen aber könnten Sie einfach bestimmen gut umgehen kann also das können behaupten Vorteil seiner rechts also bislang haben wir immer über die Seite diskutiert genannt ein optimieren nur in dieser Welt diskutiert was soll überhaupt Sinn machen es auf diese Rechte Seite zu gucken ich dich ja die haben aber jetzt erst mal gelassen erst mal bislang sind wir noch nicht also momentan wieder gesagt besser gleich 0 sein also im Moment sind wir auch hier im Hochebene also jetzt erst mal für die Diskussion ist eine rein wenn ist für immer gleich also müssen wir bis bis in die Analyse gehen was wenn angenommen werden dass es dem Simplex Verfahren lösen worden waren also wenn der Vorteil hier drüben also wir mal schauen was Internet-Trollen stellte beim Simplex Verfahren und wird dann müssen wir eigentlich der 1. Schritt ist im gleichen System lösen dieses Bild dran müssen ausrechnen bestand transponiert y aus mit AB gleich CD das bislang gleichen System lösen dann mach mal so Minimums Bildung über das Preise sehen also gucken gibt es endlich Basis Variable die kleine attraktiv sein kann also wenn das mal die reduzierten Kosten aus anschauen ob da eine noch negativ ist von den und es eine solche haben dann müssen sozusagen Basis Austausch machen dem sowie wieder dem gleichen System lösen und das Minimum und Minimums Bildung das ist eigentlich alles zusammen was es beim Simplex steht es einmal zweimal Gleichungssystem lösen ein Minimum bilden und ja das war es eigentlich nicht und das Preis eine andere Matrix mal weg da das die tollen Operationen diesen Phasen sind diese kleinen System lösen zweimal mein Gleichungssystem lösen so und wenn man überlegt sein System lösen hängt ab ein nicht im schlimmsten Fall ist es komisch oder in n hoch 2 plus Weise was gar die beste Schranke ist aber um um Gleichungssysteme zu lösen aber er ist ein Mann Normalfall außerdem er zu machen hat man dann eh noch 3 Algorithmus drin was ungeschickten war so das heißt er noch Treiber Anzahl der neben Bedingungen so und jetzt kommt 1. Vorteilen ja ganzen Packen rausgeschmissen wir leben nur noch in der 1 Welt also hier immer noch als als Randbedingungen hier man M 1 und jammern entzwei ja und dann haben wir hier Bögen reduziert auf dem M 1 +plus mir 1 wenn das heißt die Anzahl Randbedingungen haben wir je nachdem mit verwunderlich würde die gleiche Problematik immer hieraus schmales und umso kleiner wird mein System hier drüben da das heißt umso schneller wird vermutlich meint Simplex Verfahren offen neben Nachteil
allerdings sehr ich handeln hier neue Probleme ein ähnliches kann sei nicht enorm viele Zeilen und Spalten als enorm viele Spalten nur mal das einfachste Beispiel 7 der würde fühlen wenn ich hier angenommen mein M 2 werden Würfel steht nur 0 kleine X kleiner gleich 1 wie viele V ist Griechenland also würden jeder 0 1 Vektor ist 1 das heißt ich Krieg exponentiell viele VI ist also das heißt aus einige linear viel Ungleichungen Jagdlied Peripherie drüben exponentiell viele Variablen es kann aber auch Dominik Fall seiner exponentiell hier kann ich mir das Kreuz Polittalk Bancshares als Beispiel dann ist es so dass es bei uns viele viele Randbedingungen hat und aber nur heute viele linear Vielecken also das beides in beide Richtungen möglich aber in im Allgemeinen Wärme immer von dieser Formulierung ausgeht ist tendenziell schon so dann haben wir hier eine kompakte Formulierung und die Anzahl Ecken kann dann potenziell tat exponentiell wachsen Frage ist es wirklich schlimm dass die Anzahl eben exponentiell wachsen kann exponentiell an sich holen so vom Stuhl der diskreten Optimierung kombinatorische Optimierung aber ständig mit exponentiellen Größen zu tun aber für uns ist nur entscheidend ob mal über diesen exponentiellen Größen in vernünftiger Zeit optimieren können also gerade hat man sie aber lag rasch ja das stand zeigst sehr viele Schnitte aber das hat uns eine gejuckt weil mir mal steht kann man Polynomialzeit aus also können auch über diese exponentiellen Klasse von ungleichen sehr bei denen dann wieder optimieren war also erst mal die Tat Drahtseil sei das exponentiell viele gibt die wie macht uns das Leben und nicht schwer waren und deshalb steckt da drin es auch wieder ein Kern 4. vernünftige Ansatz nur weil was wir haben es hier wieder genauso machen können wir müssen ja die diese Na ja wenn nicht alle explizit auf einmal modellieren und formulieren und dann diesen LP aufstellen sondern es reicht ja wenn wir die sozusagen wieder und mahnt berechnen können der wir nochmals im Blitzverfahren gucken wo brauchen wir denn wirklich nur alle Spalten im Rahmen nur beim Preis sind am Anfang habe ich gar gar gesagt lösen gleichen System dann müssen wir die reduzierten Kosten überprüfen der nicht Basisvariante ist genau der Schritt müssen die reduzierten Kosten alleinig nicht Basis war ja wenn das sind das können hier viele sein und wir dann eine wenn dar wenn es keine Spale gibt mit nicht mit negativen reduzierten Kosten wissen wir haben die optimale Sohn gefunden und wenn man so eine geht dann immer genau die einer rein lösen wieder gleichen System 1 Basis austauscht und wieder die in das heiße brauchen wir genau an dieser einen Stelle ist beim Preis sinkt bis wir über alle Spalten gehen und wenn wir das wieder als Optimierungsproblem formulieren können was vielleicht sogar Polen mehr Zeit lösbar ist also wieder im Geschäft war und genau das funktioniert in dem Vereinen und das schauen wir uns das schauen wir uns das mal an wie das geht weil Sicherheit dazu vielleicht schon dieses Problem was wir hier haben schlage ich mein Kurzform also müssen wir das Thema stellen Stern in Kurzform lässt sich das so schreiben minimiere Omega mal Etat unter anderen Bedingungen des gleich des und des etwa soll größer gleich 0 sein ja indem er da hab ich jetzt die Lamdasonde müs versteckt und in dem die habe ich das A 1 VI und die A 1 Lj versteckt und können sollen wie schon gesagt hier im Simplex die böse die Basis Matrix hat jene Größe von M 1 +plus 1 in dem System wenn sie hier noch die Größe M 1 bis M 2 hat so wie sie jetzt das Preisen aus also schauen uns das mal an wie sieht es Preisen aus in dem in dem System hier also Preis sehen sprich Bestimmung der reduzierten Kosten ja dich bestimmt sich wie folgt dass es dann über die nicht Basis Variablen -minus Sicherheit sehen y Schlange transponiert DEN mit einem y Schlange kleiner gleich 0 und das y Schlange löst ist genau die Lösung des Gleichungssystems mit y Schlange transponiert BP Omega wird würden und das war genau der 1. für den Simplex Verfahren liebt später dann ja wo alles y ausrechnen dass der zwar dann hier ein um die reduzierten Kosten auszurechnen wenn die alle größer gleich 0 sind es müssen optimal wie soll das denn gehen wir jetzt einfach als dort weil das System ist nur Größe M 1 +plus 1 also das Klima deutlich schneller als noch hier so bleibt die Frage können wir das ja ausrechnen können entscheiden ob dieser Vektor größer gleich 0 so kleine gleiten also dass wir dazu tun denn dazu müssen einig nur über diesen ?istenie rechnen damit ,komma wie ne normale Darstellung ok also um das auszurechnen wie wir jetzt nicht diese Darstellung sei es Gelder wieder zurück und in die wir also zur Berechnung
also Zeugen eine Berechnung stünde zur Bestimmung zur Entscheidung ob dieser Vektor hier Omega n -minus y Schlangen transformiert DIN wir sei gleich 0 gilt bestimme zum minimiere das das 1. mal hin CC -minus y qué wäre A 1 x und der dann Bewegung A 2 x ist kleiner gleich B 2 X aus erhoben so warum warum reicht das schaut es mal an was passiert denn hier wenn wir das ausrechnen nein das wir mal den einfachen Fall an alles ist beschränkt werden dann Polito bestehen dann wissen wir wenn man Jahresprogramm lösen wird die auf dem alles und in einer Ecke angenommen war das heißt wenn wir dieses LP lösen kann eine optimale Sunniten Ecke gehört Na ja das muss so offen sich einer von diesen von uns allen so Mastergrad geschrieben P 2 oder mehr optimieren die genau P 2 ich konvexe Hülle der Ecken bis konische komme und alle ging automatisch Schnecke damit geschehen so ist ganz es muss jetzt nicht endlich sein bis die Nieren kann darum beschränkt sein namens unbeschränktes ist genauso E nur so und das ist ein legales Programm lineare Programme kann man Polen im Jahr Zeit lösen müssen also kann man über setzen diese Größe hier die DVI Orts und die er die er zum IV alle exponentielle Größe haben mit keinem Pollen ja Lehrzeit Einvernehmen von bestimmen und mehr brauchen werden kennt und was es noch dazu kommt dieses geniale Programme ist auch noch deutlich kleiner also dieses lineare Programm Klima deutlich schneller gelöst als das das die ganzen A 1 x kleiner gleich B 1 Bedingungen ok also und damit 1 einiges Verfahren das kann man es noch genauer auswerten also die 3 Fälle die passieren können das war tatsächlich dann ein gegen den negativen reduzierten Kosten aber das ist das ist offensichtlich dass dem so ist aber schauen wir uns mal also wird das mal aus ja also sei mit Schlange optimale Lösung an von diesem Problem so sowas kann passieren also im Moment schmoren das war Quatsch ist der 1. Fall ja es keiner seines Dennis unbeschränkt also 1. der Fall es gibt nämlich optimale Lösung sowas was gilt dann mit also mit der mit der Bedingung dass die ist dass die Zielfunktion negativ ist also c't -minus y quer A 1 X quer ist kleiner 0 so was gilt dann für unsere luziden kosten ja schauen uns dass man hier an also dieses kleine gehört zu einem VI mal X ist Ex Schlange ist ne optimale Lösung damit muss es mir optimale Ecklösungen Lösung sein und damit muss sich Schlange 1 von diesen VI sein und werden wir jetzt die reduzierten Kosten genau 4 4 dieses VI anschauen was steht dann da für diese Komponente W i -minus y quer transponiert DE .punkt is da nix anders als soll schauen sich also dass bei ihnen sei 1. dazu c't VIII -minus y transponiert A 1 VI 1 so wollen ist das der Fall schauen was es nochmal an waren unser abkürzende Schreibweise hier sollte es muss ein von diesen VIS sein wie sehen die VIS aus die sehen genauso aus wie man das steht hier 1 V und an dieser Stelle steht noch die 1 das ist die 1 was zum Lander gehört ja dass genau dieses DIE und dessen des W I die Zielfunktion ist ja nix anders als es entsprechende c't VI was hier steht wenn es genau das wir können so wir da sind Sie ausrechnen dann ging daraus dass es c't Fortini -minus y quer transponiert A 1 i -minus y quer und cm +plus M 1 +plus 1. Komponente er unter uns das hier an ich dass es falsch gemacht wo ist falsch gemacht ich kleiner 0 sondern kleiner ließen y M 1 +plus 1 Quelle was diese was dieser Lösung entspricht wobei die quer es alle Schlange sein so Entschuldigung also diese Ypsilons ja das sind natürlich genau das das Ziel belügen ja die Lösung von den Dingen wir so und damit angenommen wir haben in die optimale Lösung mit dieser Eigenschaft heißt dieses dieser Vektor ist kleiner 0 1 zum damit wäre und damit haben
wir also wir lösen das wir kriegen endlich optimale Lösung die diese Eigenschaft hat wenn sie die hat ja dann lieber sofort ein wenig Basis Variablen dem System dessen reduzierte Kosten negativ sind und die Spalte nebeneinander zu haben so und es gibt es noch den 2. und befallenen 3. und dann einmal sei vollständig analysiert nur schnell so bleibt noch bleibt nur als Überbleibsel sozusagen der 2. Fall des Dinges unbeschränkt also dieses Problem unbeschränkt hinter mir leider keine Waage gesetzt also ich weiß immer so kurz wäre rechts oben ist unbeschränkt ja dann muss zu einem Sternen gehört dazu ein J ja existiert ist ihr etwas mal ausrechnen mit c't im Minus y Schlange transponiert A 1 ich dann J =ist gleich 1 0 um also erst mal es gibt nächste mal strahlen oder nächste Male sodass sozusagen wie ich mir das anschaue die Zielfunktion ich billig verbessern kann nachdem die alle extrem mal strahlen ich in meiner Menge haben muss 1 von diesen Elliot auch diese Bedingungen so und genau dieses muss dieses sein die Spalte die dazu gehört der in unserem System sieht dann so aus also ich die negativen ich die reduzierten Kosten anschauen -minus wie K +plus 1 an dieser Stelle ist dann nix anders als CTI hat -minus y Schlange transponiert S A 1 ist steht hier an dieser Stelle 0 weil und in unserem Problem was mir zu sich hatten stand ja sozusagen das zu Melander I gleich 1 über die NYT J's hat man keine zusätzlichen Einschränkungen Mehr ja wenn wir das auflösen ist es dann CCE J -minus y Schlange transponiert A 1 Ei und das Ding jetzt echt kleiner 0 nach dieser Bedingung damit Wissen haben auch in den Fall der Spalte gefunden mit negative reduzierten Kosten und können die entsprechende zu beenden so im 3. Fall war das es da praktisch dieselbe Rechnung wie hier also der 3. Fall des Art optimale Lösungen mit genau diesen wäre was sehr recht schick größer gleich also mit c't -minus y Schlange A 1 X Schlange ist größer gleich y M 1 +plus 1 Schlange ja dann wissen wir Klaus folgt Steines optimal nur warum weil wenn weder der 1. falls noch zuletzt noch dieser Fall zutrifft dann bekam er mit dieser Aussage dass er sofort alle alle reduzierten Kosten sind nicht negativen eines Index fahren und Dualität Satz dass dieses dieses lineare Programm hier optimal Optimalität haben haben sondern muss es nochmal anschauen wenn wir uns das gesamte Verfahren nochmal anschauen wir haben einmal das ursprüngliche Problem das mal vergleichen ist wir müssen das US-Original Probleme löst immer Problem in M 1 +plus n 2 Randbedingungen dann wenn ich es jetzt Vergleich mit Danzig wohl was mach Danzig Wulff Danzig Wulff hatten Problem was nur M 1 viele Randbedingungen hat dafür aber sozusagen das Verfahren etwas teuerer ist was heißt heute jedes dieser Preis Auswertung bedarf das Lösen eines linearen Programms das Sie rechts oben an der Tafel stehen dieses lineare Programme soll wieder kleiner als das Orginal Problem ich hab nur in 2 viele Randbedingungen und so mit Hammer sozusagen unser Gesamtproblem reduziert von entweder widerständige lösen oder berechnen vom gleichen System der Größe M 1 +plus n 2 Problem des iterativen lösens der Größe M 1 und zwar und und unter dem Aspekt es mal sehen dass dies lösen von Gleichungen System der Treue der Anteil ist Mehr kann es an verschiedenen Stellen doch aus den man diesen Beckumer sie zu uns Ansatz zu wählen das zeigt sich nur das lineare Programm also bislang aber den Fall nur für lineare Programme angekuckt viele der Programme ist es nicht ganz so essenziell weil innerhalb Programme können heute oftmals sogar Minutenbereich mit mehreren Hunderttausenden Millionen von Randbedingungen gelöst werden dort noch mal zur denken der komponieren macht häufig wenig sind wobei man das in den sechziger siebziger doch häufiger gemacht hat weil damals konnte man große lineare Programme noch nicht wissen heute ist natürlich dieser Ansatz relevant wenn man ganz Bedingungen dabei haben und ob man diesen Ansatz so übertragen können auf ganz Helligkeits Bedingungen der schauen und soll am Mittwoch an vielen Dank
Matrizenmultiplikation
Punkt
Konvexe Hülle
Maximum
Randbedingung <Mathematik>
Konkave Funktion
Vektor
Ganzzahlige Lösung
Computeranimation
Richtung
Teilmenge
Elementare Zahlentheorie
Ungleichung
Ganze Abschließung
Nullstelle
Gleichgewichtspunkt <Spieltheorie>
Vorlesung/Konferenz
Durchschnitt <Mengenlehre>
Zielfunktion
Ableitung <Topologie>
Ecke
Funktion <Mathematik>
Differential
Minimum
Vorlesung/Konferenz
Vektor
Ableitung <Topologie>
Nichtlineare Optimierung
Richtung
Länge
Punkt
Welle
Maximum
Vektor
Zahl
Richtung
Null
Gradient
Summe
Index
Differential
Minimum
Vorlesung/Konferenz
Logischer Schluss
Zusammenhang <Mathematik>
Klasse <Mathematik>
Kante
Linie
Variable
Ganze Abschließung
Vorlesung/Konferenz
Zielfunktion
Untere Schranke
Wald <Graphentheorie>
Knoten <Mathematik>
Endlichkeit
Machsches Prinzip
Reihe
Optimierungsproblem
Randbedingung <Mathematik>
Zahl
Entscheidungstheorie
Teilmenge
Summe
Schnitt <Mathematik>
Platte
Aggregatzustand
Schranke <Mathematik>
Ebene
Distributionstheorie
Matrizenmultiplikation
Zusammenhang <Mathematik>
Große Vereinheitlichung
Baum <Mathematik>
Klasse <Mathematik>
Ganzzahlige Lösung
Gradient
Variable
Ungleichung
Minimum
Vorlesung/Konferenz
Zielfunktion
Optimierung
Feuchteleitung
Erweiterung
Fünfzig
Optimierungsproblem
Randbedingung <Mathematik>
p-Block
Spannender Baum
Kapazität <Mathematik>
Schnitt <Mathematik>
Schranke <Mathematik>
Nebenbedingung
Simplex
Verschlingung
Matrizenmultiplikation
Total <Mathematik>
Polyeder
Punkt
Momentenproblem
Vektorrechnung
Gruppoid
Konvexe Hülle
Gleichungssystem
Randbedingung <Mathematik>
Summe
Variable
Vollständigkeit
Menge
Endliche Menge
Minimum
Vorlesung/Konferenz
Zielfunktion
Platte
Bogen <Mathematik>
Ecke
Einfach zusammenhängender Raum
Mathematische Größe
Simplex
Momentenproblem
Klasse <Mathematik>
Berechnung
Konvexe Hülle
Optimierungsproblem
Randbedingung <Mathematik>
Kombinatorische Optimierung
Normale
Polygon
Vektor
Richtung
Variable
Ungleichung
Würfel
Vorlesung/Konferenz
Zielfunktion
Diskrete Optimierung
Ecke
Lösung <Mathematik>
Index
Variable
Menge
Seidel
Verweildauer
Vorlesung/Konferenz
Gleichungssystem
Zielfunktion
Optimum
Randbedingung <Mathematik>
Dualität

Metadaten

Formale Metadaten

Titel Dantzig-Wolfe Dekomposition
Serientitel Diskrete Optimierung (Optimierung II)
Teil 15
Anzahl der Teile 26
Autor Martin, Alexander
Lizenz CC-Namensnennung - keine kommerzielle Nutzung - Weitergabe unter gleichen Bedingungen 3.0 Deutschland:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen und nicht-kommerziellen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen und das Werk bzw. diesen Inhalt auch in veränderter Form nur unter den Bedingungen dieser Lizenz weitergeben.
DOI 10.5446/31773
Herausgeber Technische Universität Darmstadt
Erscheinungsjahr 2009
Sprache Deutsch

Inhaltliche Metadaten

Fachgebiet Mathematik

Ähnliche Filme

Loading...