Merken

Lagrange Relaxierung

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
Eva den ich ja nur am BE so herzlich
willkommen zur heutigen Vorlesung ja Mehr Montag war Feiertag der Wurfsendungen bisschen genossen ohne diskreter Optimierung der letzte Woche soll genau vor einer Woche uns dann beschäftigt mit strukturierten und Beleidigungen die haben wir uns überlegt wie man das sozusagen nach den allgemeinen Schnittebenen er uns aber mit Methoden anschauen kann die sozusagen steht die diese Strukturen ausnutzen und nicht allgemein von der beliebigen Matrix ausgehen sondern diese Matrizen analysieren und daraus ausgehen dann wirklich qualitativ gute Ungleichungen finden und da hatten wir angefangen mit dem Rucksack Probleme haben dort die Kaperung Gleichungen kennen gelernt die genau von diesem Typ sind wir haben einfach gesagt wir nehmen uns interpretieren jede Zeile der Nebenbedingung SmartThings Matrix als ein Rucksack und schauen uns dieses Rucksack Problem an und habe dann gesehen wenn man ein bisschen Struktur ausnutzt dann ,komma auch sowas wie Grabungen Gleichungen die kann man auch dann nachweisen dass der Fassetten definieren die Umgehung sind also auch wirklich qualitativ gute und gleich in dem Sinne dass man auf die nicht verzichten kann wenn man eine vollständige Beschreibung will solche Aussagen aber bei den allgemeinen Schnittebenen bei Quartal oder auch bei como Dini erzielt dass die Ungarn die wird dort am Qualität die haben wir wissen nur immer dass sie den aktuellen .punkt abschneiden und dass man sozusagen damit Integrationsprozess haben indem er weitermachen können aber die Qualität dieser Schnitte ist offen und dieser bis heute offen also man weiß nur in wenigen Fällen waren diese Quartal Schnitte oder ,komma dichtete tatsächlich Fassetten definieren anders ist es wenn man Strukturen ausnutzen weiß es genau das da will man das genau die Strukturen so ausnutzen dass man eben nach Möglichkeit Fassetten definieren die Umgehung kriegt das Rucksack ,komma so das letzte mal angeguckt und setzte was immer dann stehen geblieben das gleiche für Peking beziehungsweise Grabenring zu machen wobei man uns gesehen haben dass der Card Zepter gegen äquivalent ist zu den stabilen Mengenproblem den Grafen und das der krawalligen eigentlich auch nix anderes ist als das stabile Mengenproblem Hypergraphen haben angefangen uns stabile Mengen Grafen bisschen anzugucken und da haben wir uns noch alle schwachen totale ohne Modularität und gesehen haben wir wegen wenn der zugrunde liegende Graph die Partie des ist dann ist die Matrix total Uni modularen damit liegen der Ganzheitlichkeit automatisch geschenkt und nach dem Graph die Partie des genau dann wenn keine ungerader Kreis drin ist gesehen dass sie sie ungeraden Kreise sozusagen die 1. Strukturen sind bei den offensichtlich was schief geht und da sah man dann genau Ungleichung entwickelt und das immer das letzte Mal stehen geblieben dem man sie ungern formuliert haben was Nation heute tun wollen ist auch nachzuweisen dass die Katze eine Facette definiert und dieses dann noch ein bisschen erweitern auf noch weitere Ungleichung was es der Polittalk betrifft das bis dahin als nochmal Fragen zum letzten Mal vor wenn das nicht der Fall ist dann würd ich eigentlich an der Stelle gerne weitermachen wenn ich wir hatten aufgehört bei dem Satz 3 28 ich werde nochmal die Ungleichung hin Satz 3 28 werden Kreis C in zum Grafen in gerader Kreis das Jahren werden die Ungleichung zum X März über alle Knoten in diesen Kreis gehen soll kleiner gleich der Kardinalität dieses Kreises 1 -minus 1 abgerundet .punkt und wir haben das letzte Mal auch noch gesehen dass mir diese Ungleichung auch lieber Comolli letztendlich bekommt in man die Kanten Ungleichungen einfach jeweils Inhalt skaliert und aufaddiert war sozusagen spezieller Kommode steht wenn man so möchte ,komma denen einfach die Idee Teile der Basis inversen aber man kann natürlich auch jede beliebige andere Skalierung sich überlegen wie viel wir ganzzahlige linke Seite liefert und der gebrochene Rechte so gingen an alternativen Comolli oder auch Quartal Schnitt wenn man so möchte also kann man die Ungleichung auch herleiten was wir jetzt eben nachweisen wollen dass ADS gültig der und definiert Facette genau für unsere als wieder eingeschränkt auf diesen Kreis für das ihrer um als Knoten nur die in diesen Kreis haben und
sie wird etwas kompliziert aus aber letztendlich heißt es man Grafen haben schauen sind ungeraden Kreise an alle kannten die beide einen Knoten in diesem Kreis haben aber das bedeutet dieses Symbolik Kiel also ist Wasser der genau dann wenn sie ein und ein Loch ist wir ja das Loch ist also machen wir mal so ein Beispiel 3 4 5 6 Bundeswehrärzten ungerader Kreis zu so was sagt jetzt die Aussage wenig ungeraden Kreis hab ich möchte eine stabile Menge stabile Menge war nochmal der Auswahl von Knoten so dass jeweils 2 nicht miteinander benachbart sind das heißt wenn ich mir jetzt ne Lösung anschau ich will mir irgendein Knoten hier aus dann heißt es die beiden nach Banknoten kann ich nicht nehmen weil die werden der Nachbar das Heisig ich muss mindestens immer ein auslassen er sei es wenn ich nehmen dann kann ich immer maximal jeden 2. nehmen und da sehen wir schon dass ist sozusagen in den neue Bedingungen gibt wenn es eben ungerade ist dann geht es eben nicht aus wenn ich hier den nehmen Ichiro muss sich ein auslassen wo sich wieder ein auslassen werden sich wieder ein aus was aber dann komme ich in Konflikt mit meinem Staat ja an das muss an einer stelle eine Lücke von 2 Knoten gehen und das genau das was hier steht wir ziehen die einst noch mehr ab das ist genau diese Lücke und zur Gültigkeit ist offensichtlich von der Ungleichung mit zeigen jetzt was selten Eigenschaft und da machen es genauso wie wir das neben diversen anderen Fall auch gemacht habe wir wir wir nehmen an also Gültigkeit das ist klar Facette für seltene Eigenschaft nur also dann machen wir genau den gleichen Ansatz wie wählen also wissen wie es um Gül Alice gültig das heißt sie definiert auf jeden Fall induziertes Seitenfläche was mir aber was wir zeigen wolle ist das maximale Seitenfläche ist wenn dem nicht so ist muss es aber ne maximale zeigen welche geben die diese Ungleichungen enthält und seine werden uns jetzt also sei seit der da seit wir transponiert X kleiner gleich Beta Facette mit dass die Menge alle x aus unserem pro Liter die jetzt genau das mit Gleichheit erfüllen also Summe XII wie aus Frau von C Platte gleich können ja auch einfach C schreiben -minus 1 das das enthalten ist in der Menge alle x aus P transponiert X gleich better war also so eine Facette muss es immer geben wer diese Menge dieses Seitenfläche die Bezeichnung war mit 11 a und die hinten mit FB das und was wir jetzt machen wollen ist wir wissen das seit Politur stabil Mengen Polito bis voll alles haben das Nest letzte mal gesagt das heißt wir wissen das Ding ist eine Facette wenn man diese hier alle diese Koeffizienten allen bestimmen können bis auf ein Skalar es vielfach ist also wenn wir nachweisen können dass zum Beispiel die B is hier alle gleich sind dann aber genau diesen Status erreicht so wie machen wir das wir konstruieren uns 2 Lösungen die hier drauf legen die möglichst wenig sich unterscheiden so wir schauen uns mal 2 solche an also einmal die 1. ist es 1 der Unternehmen die dann nochmals genau zu zeigen diese gelbe Lösungen fangen einen Knoten I ein in jedem 2. dazu also hier also S 1 sagen es sei denn der Knoten das im Skript gemacht im die I +plus 2 E-Plus 4 E-Plus +plus 6 und so weiter bis i -minus 1 wir also in dem Fall würde das so machen aber dass unser ja die 7 wäre unser dann als
Knoten ein dass wir unser S 1 niemals Quoten ein I +plus 2 e +plus 4 und so weiter bis -minus 1 alle Indizes soll immer modulo der Kreissäge gerechnet sein so und in 2. dann immer folgende dahin es 2 Unternehmer genau die gleichen I +plus 2 e +plus 4 die +plus 6 und so weiter und den letzten der war ist der i selber wenn das nicht kommen sollen bis Jürgen ungeschützt im -minus wichtig sollte vielleicht nur einer schreiben ihm -minus 3 die minus 1 und hier schreiben wir ihm -minus 3 und wie wer soll das heißt was wir hier machen ist dann die blaue Lösung in dem die 1. alle gleich wählen gehen so und jetzt haben wir hier die Wahlmöglichkeit der zwischen aber dass wir die festgelegt haben ,komma den oder den wähle wir den Wählern dann bis man jede Lücke lassen wir den will was man hier die Lücke und in dem Fall sagen wir immer denn das ist die blaue Lösung nur so viel wissen beide von diesem beide haben Kardinalität C -minus 1 halte er aber nie jeden 2. genommen haben am Schluss geht auf eine auch das heißt beide liegen in 11 aber also die Inzidenz Vektoren von hier ist ein ziemlich die S 2 sind beide Elemente von dieser Seitenflächen war mit dem Inklusion sind sie auch enthalten in diesen FPÖ die also erfüllen beide BTX gleich Peter und wenn ich die beiden voneinander abzieht wir also daraus folgt die S 1 =ist gleich Peter und der des Franz benennt die S 2 ist ebenfalls Peter über die beiden jetzt von abziehen dann sehen wir überall stehen die gleichen Indizes bis auf an einer Stelle nein das heißt bei dem wenn ich hier -minus macht dann bleibt er stehen B i -minus 1 -minus per Email ist gleich 0 das heißt p =ist gleich b ihn -minus 1 und damit müssen alle nachdem es Ibisevic gewählt war müssen alle =ist gleich sein damit ist das bis auf 1 ist Karl vielfach als genau diese Ungleichungen damit der versetzte muss gibt es da die Frage noch mal wir müssen wir Facette Bürger ist es war so dass die Einrichtungen auf also das wenn das war ist die Richtung wenn ich nun wieder alles Loch war dann ist es auch eine Facette es muss sich natürlich noch sagen das ist auch notwendige und soll es auch und gerade so noch zur zu haben ich nehme an das wäre nicht so mein Mann hier wieder 1 zu 3 3 4 und 5 das heißt jetzt angenommen hätten keinen Sohn und gerades Loch das als Wärme und ohne die Diagonale ja immer mal das mal so an wichtig war da oben damit es überhaupt
funktioniert hat das mit keiner Diagonalen drin haben 1. wer S 1 S2 keine stabilen Mengen ist immer davon ausgegangen dass es hier drin keine Diagonalen gibt wann ich noch mal mit etwas war ich war mal das Beispiel bisschen größer sein dass wir hier mal auf 9 unser werden ein Effekt nicht ganz so gut 5 sie 6 sie 8 und 9 Sohnes machen indem wir wollen alle hören wir werden die ab genau so so bemessen werden alle drin haben man ungeraden Chrysler sollen Diagonale haben begegnet mit 2 Kreisen hier ist einer wir sind 2. Namen soll wenn der ursprüngliche gereist um gerade muss einer von diesen beiden kleinen Kreisen und gerade er ja also in dem Fall ist dieser hier also zieht zwar ist und gerade ok so von dem wir wissen da schon das Wiener bewies etwas Seite also so man ihr Auszüge 2 XI kleiner gleich C 2 -minus 1 alle das Ding das war schon so was machen wir den Rest ist ging es gerade ja so was man jetzt hier machen ist also wenn man einmal diesen diese gelte dass es genau dieser gereist wir und dann immer noch es gibt er die immer noch ein paar drauf und war zwar da es ist ja gerade das heißt wir können jetzt Pärchen bilden ja bei der Kreises gerade die den erst mal weg war der gehört schon zum genauen gar ist ist ja gerade Anzahl von Knoten und die die paar einfach miteinander ja und wir dir auch noch auf ja das ist oder tionstechnische ob wenn das vernünftig hinschreibt Werner Schreiber noch sozusagen X I 1 plus X je 2 kleine gleich 1 und das machen wir für und bei I 1 I 2 Element von diesem C 2 sind ohne das C 1 ja und paarweise disjunkt und I I 1 I 2 paarweise disjunkt käme so dann haben einmal den geltenden an einem blauen über die beiden zusammen addieren wir also das war es ist dieser Teil und wenn ich die 2 zusammen als wir danke ich genau was raus was ich wollte und das ist gar nicht genau diese Summe überall II in den Gesamt Kreis kleiner gleich 10 -minus 1 halte wer warum kriege ich das hier hab ich genau wie Paare hab ich nämlich genau C 1 halbe viele waren C 1 halbe das ist gerade das kann ich einfach dazu addieren komm ich genau insgesamt auf das CMS halten ja das ist ein Widerspruch zu belegen dass das hier eine Facette Widerspruch zu was Eigenschaft ja weil wenn ich wenn ich ne ungleichen als eine Summe von 2 gültigen Ungleichungen schreiben kann dann kann es keine Facette sein unterwegs ist die 1 wenn Facetten sein und dem Fall dass es eine Facette und das ist auch der Facette immer gleich noch sehen werden ok gut ist also damit haben jetzt gezeigt also und zu so funktioniert erreicht diese Herangehensweise an diese jede wir haben angefangen an stellt in der Regel ein ganzzahliges Programmen auf also wir haben das stabile Mengenproblem das war uns Ausgangs Problem finde der maximale stabile Mengen einen Grafen dann stellt man dazu ein ganzzahliges Programm auch wenn das Ganze über Gramm in dem Fall das hat man eingangs schon gehabt ist relativ einfach ja wir wollen maximale stabile Menge XI sind unsere unsere Variablen 1 in den ich in der stabilen Menge wenn 0 nicht und die einzige Randbedingungen sind diese XII plus x J kleiner gleich 1 für alle I J n e und wir fordern natürlich dass die XI ganzzahlig sind nur das ist sozusagen das das ganze ganzzahlige Programm dazu und wenn wir jetzt Anfang LP Galaxien zu rechnen und versucht man zu analysieren ,komma ganzzahlige Lösung oder Obst einmal gesehen wäre wenn man sozusagen der zugrunde Grafen in die Partie gestern gegen automatisch Ganzheitlichkeit geschehen das war total ohne Modularität aber gesehen es geht schief sobal ungerader Kreis drin ist zwar zweimal jährlich gezeigt aber damit das auf Gebrauch mit Bedingungen was gerade Kreise betrifft nur die Amalie entwickelt soll stellt sich die Frage aber wie kann ich die überhaupt ins hab ich ja hier in diese Klasse von ungeraden Kreisen wird damit das 1. Problem was ich damit habe ich kann gar nicht alle ungeraden Kreise gleichzeitig diesen Problemen zu finden warum war ich aber hier bin ich mir die größeren dem Problem anschaut ist es allen der in der Eingabe des Grafen ich hab jede kann der eine Nebenbedingung für jeden Knoten eine Variable ist der kompakte wenn wir jetzt die Kreise dazu nehmen wir Kreise gibt es dem Grafen da kannst exponentiell Filet geben würde ich mir zum Beispiel vollständige Graph anschaue ist ist die Anzahl Kreise aussieht der Teilmenge Funkknoten bekömmlichen Kreis bilden ja also es gibt 2 hoch N viele potenziell viele Greisin zum Grafen das heißt er werde das Problem dass sich die Kreise aber sehr schön einfach strukturiert sich kann egal alle explizit auflisten von Haus aus exponentiell also Songs überlegen wie kann man dieser parieren ich muss ja gar net alle explizit auflisten waren und ich kann mir sozusagen OnDemand generieren ich würde es einfach DLP Galaxie Lounge wenn dann sozusagen der gebrochene Lösung rauskommt die die Kreis Ungleichungen verletzen war ein nur 1 bei der aufrufende sagt finden wenn der Verletzte Kreis und das interessant ist es geht in dem Fall sogar ja man kann gerade Kreisen polynomial derzeit separieren und kann nämlich auf kürzestem Wege Problem zurückführen was machen wir eventuell Übung oder steht auch hier einen Hinweis Roussos im Buch steht und kann durch geschickte Grafen Duplizierung sozusagen in um gerades Kreis Problem auf kürzeste Wege Problem zurückführen kürzeste Weg kann meinen in quadratischer Zeit bestimmen das heißt dass dabei die Jungs Probleme hierfür ist die Polen aller Zeit lösbar das lässt sich wieder die Frage stellen angenommen ich hab alle diese ungeraden Kreise separiert kann ich denn dann in eine ganzzahlige Lösungen kann es sein dass ich dann immer schon automatische ganzzahlige Lösungen Krieg oder kannst dann immer noch sein ich hab ich alles kommt wieder Unfall und der gebrochene Lösung auftreten kann könne ohne dass wir jetzt dass die gelöst haben allein von dem was er bislang wissen schließen ob ich automatisch in eine ganz eigene Lösung rauskommen muss oder nicht was ist das Argument also Missstands seiner von der Komplexitätstheorie an angewiesen stabile Mengenproblem müssen endlich schweres Problem war also für diese dieses
in Kürze der Gleise der von Problemen für die bislang keine polynomial Algorithmen bekannt sind so was angenommen da käme es immer ganzzahlige Lösungen raus dann hätten wir in Polen immer alles Verfahren warum wir lösen die LPR lag sie nun hier die Größe des linear LPs können Polynomialzeit lösen zum Beispiel der jetzigen Methode dann gegen eventuelle gebrochene Lösung da dass dabei die Jungs Problem aufrufen wird für diese ungeraden Kreise die Kammer mit den kürzesten Wege Algorithmus in Polynomialzeit löst also wir können kolonialer Zeit dass dabei die uns Probleme lösen also wissen aus der Einführung die Echallens Phonds separieren optimieren wir können also auch in polynomial Zeit über dieses LP inklusive aller Kreise optimierte ja das heißt Polen ja derzeit dieses LP gelöst und dem automatisch Ganzheitlichkeit klingelt wird damit in Polen im Jahr das Verfahren ist dieser Schluss klar Wege mal sagen wenn was so schnell oder nicht klar ist also wir können aber eine Komplexität Argumenten hier schon wissen wir schon oder so weit Überlegung machen es wird Fälle geben auch wenn ich alle exponentiell Feenkreise bei habe es kommt immer noch eine gebrochene Lösung aus so die Grafen allerdings die hier dann automatisch ne ganze Herrlichkeit liefern die nennt man die perfekt das hat damals Quartal hat die etwas mehr studierte in den siebziger Jahren unter dem Begriff der TI perfekt halt sozusagen eingeführt für Probleme das Zuge zugehörige Polit wobei die alle ungeraden Kreise zu einem automatisch ganzzahlig weg dass die nicht erreichen ist zeigt die in die nächste Klasse von Ungleichungen nämlich das sind die sogenannten klicken und gleich also ich gebe mal ein Beispiel hier also und ich schreibe es mir die Umleitung auf einen wesentlichen Beispiel dass es Ersatz 3 29 der geht zurück auf Rückkehr essen 71 und Padberg 73 es sei also sie und er von C eine Clique also nötig ist Mehr Teilmenge von Funkknoten sodass alle paarweise mindernde benachbart sind also unvollständige und der Graph sozusagen dann ist Summe I aus C XE ja muss muss als rechte Seite stehen wenn ich wirklich gehabt aus der Clique kann ich maximal ein Knoten will weil alle dann benachbart sind sie kann innerhalb der klicke auf maximal einen Knoten will also steht wie eine 1 1 ist das das ist offensichtlich gültig ist gültig und definiert Facette genau dann wenn ziehe die Clique Klägerin zählen genau dann wenn 10 maximal also wenn die Clique bezüglich Kloten Inklusion maximal so dass das nehmen auch eine Facette ist es schauen was eine Übung an kann man genau sehen beweist wie die andern Beweise Wacker geführt habe zur Sinn des anderen sehen sozusagen Frage ist ,komma nicht vom Regen in die Traufe war weil es gibt klicken einig sind die Kinder fast nix anders sie die stabilen Mengen nochmal stabile Menge er ist eine Teilmenge der Knoten die paarweise nicht benachbart sind und klicke ist die paarweise alle benachbart sind also wenn ich mir den Komplement Graph anschaue konnte man gratis ist da die gleiche Knoten man nicht mal in meine kann wenn der ursprüngliche Graph keine hat ja das ist ne stabile Menge im Orginal Graph ist Nick Clegg im komplett Windkraft Mitglied im Orginal geradeste stabile Mengen Komplimente also die ja die sind sozusagen komplementär zueinander und von dem normalen also von dem von den normalen springen graben komplementär Graph die Transformation einfach die ja nicht mal meine kannte wenn sie vorher nicht da war das heißt ob ich es es stabile Mengenproblem löst oder das Klicken Problem es einig haargenau das gleiche wenig stabilen Mengenproblem orginal Graph löse sich gegen Probleme ob komplementär Graph und umgekehrt so was ich jetzt hier hat es ich weiß ist der Facette ich brauch die also auf die kann ich auch nicht verzichten und wie dass dabei die Jungs Problem ja von denen es schwer war weil ich das stabile Mengenproblem Essen endlich schweres Problem man kann ein bisschen fein differenzieren aber sagen sie bei dir vor dem Essen bisschen und anderes Fragestellung als Optimierungsprobleme aber das Kalb an der Stelle kann man das ausdifferenzieren letztendlich steckt hinter dem sehr bei Währungsproblemen hier für klicken einig dass Optimierungsproblem bestimmen immer der maximale Clique nachdem bestimmende maximale klicke genau das äquivalente Problemes bestimmen maximal stabile Menge also demonstrieren klar ist ist so ein bisschen die Crux an ein Deal an an diesem Gleise Frage ,komma da irgendwie aus dieser Falle wieder raus und in dem Fall kann man sogar aus der Falle wieder rauskommen und zwar was man tun muss ist man schaut sich eine größere OP Klasse von Ungleichungen an man kann die Menge der Ungleichungen erweitern Zuzug so genannten auch normale der Präsentation so bleiben die will ich jetzt hat einführen was sind Sie klicken Teilmenge dieser Orte normaler Präsentation so klein dass sehr viel größere Klasse da stecken war sie viele Klassen von Ungleichungen drin und an dem auch die klicken und die kann wie dem Polen ja derzeit separieren wer in den Städten auch um gleichen denen die keine Fassetten definieren wir die definieren was selten das heißt wenn ich das Auto mal das dazu und Gleichungen Sepp parierte ein kann es mir eben passieren dass sich in von seinem nunmehr gültige um einen Krieg aber nicht unbedingt der Facette ja deswegen muss man bei diesen entledigt Fisch sich Vollständigkeit oder Resultat und der Komplexität also Taten immer aufpassen es kann durchaus sein wenn ich die Menge Vergrößerer das es dann wieder einfach wird oder umgekehrt wenn es bei der ein streng kanns auch einfach wenn das Eiweiß Argument Zusagen in der beginnende zu oder weg da bereits leicht oder schwer das geben also hier sind Beispiel sozusagen auch eine größere Menge zu gehen es plötzlich einfach und damit kann ich indirekt auch diese unklar ist aber die der Band rollen wir 1 sehr bei der für diese große um Klasse von Ungleichungen und wenn da sagt es gibt keine Verletzte mehr weil sie es gibt da keine Verletzte Clique Mehr das einzige Nachteil ist der 1. bei der der kann und liefern die keine Klick ist aber was soll es ja ich aber viel fallen weg dann weiter zu machen und wenn die alle sozusagen sehr bei der 10 weiß ich garantiert diese Klasse ist auch dabei soll es kann mal wieder die Frage stellen wer was ist denn dann ja also angenommen ich hab jetzt diese parierte er keine Zahlen immer noch gebrochene Lösungen geben ja wieder das gleiche Argument welche hier können Polonia ist bei den also wie alle ungeraden Kleiderkreisel polynomial sehr bei der alle Autor normaleres dations Ungleichung Hall in polynomial Algorithmus um über diesen Pulli tobt zurück zu optimieren und dann kann es natürlich nachdem so schwer Goblin endlich schwer es kann sehr passieren sehen das immer noch gebrauchen Lösung die Klasse von Grafen die diese Eigenschaft haben das dann automatische ganzzahlige auskommt heißen perfekte Grafen ja und das war lagen es war lange offen das Resultat das Sagen zu versuchen diese perfekten Grafen zu charakterisieren also woran kann ich erkennen was an zum perfekten graben schief geht also erfüllen alle klicken Ungleichung das ist eine Sie was ich fordert und die Vermutung war lange das die ungeraden Kreise schuld sind wir sind auch schuld Airlines erreichen nur nicht weil wir mal gesehen wenn ich komplementäres irgendwie sehr ähnliches Problem also man darf nicht die ungeraden Kreise ausschließt dann auch noch gibt die die Komplimente von ungeraden kreisen also sozusagen alle wenn ich nur eine Diagonale nehmen anstatt den Kreis zu und
dann gab es sozusagen die 1. Vermutung der dann los in den Siebzigern bewiesen die gesagt hat Na ja wenn Graph ist genau dann perfekt wenn sein Komplement perfekt ist es war aber ganz so einfach was Irmi offensichtlich schien weil sie ist wirklich die Frage stellen komplementär zueinander sind aber es war doch auch eine ganz so einfach zu beweisen und daran als ich sag ich mal ist immer die Full küssen fast also Stückweit mittragen gescheitert weil es war stückweise Lebensaufgabe das rauszukriegen vor das ist eine der großen angesehenen kombinatorischen optimierter da waren sich viele super Resultat den fünfziger sechziger Jahren entwickelt auf dem basieren die mit dem mit den Schnittebenen Verfahren Max floh er mit Karte Resultat geht alles auf Teilerfolg zurück also hat wahnsinnig viel für die kombinatorische Optimierung getan und an dem Problem war dass sich irgendwie die Zähne ausgebissen dank haben soll Jungspund Lilo was damals also der Wagen keine 20 Jahre und hat es mal schnell bewiesen also das Signal ist also dass auch hoch angesehene Mathematiker großes Plus dations Potenzial aufbringen müssen es gibt immer mal einen der dann ist eine gute Idee hat wobei immer mal einen musste sein los ist das meiner Sicht durch eine der der Pope läutet wenn nicht der Top-Mann in unserem Gebiet im momentan also die Frage die er dann in den letzten 30 40 Jahren entwickelt haben ist in Ordnung also da weiß er wirklich Jungspund sondern der hat wirklich wahnsinnig viel für dieses Gebiet auch beigetragen aber trotzdem dass sie zu zahlen auch oder den angesehenen Wissenschaftler und sein Gebiet ist es genauso dieser Mehr knackt sozusagen das Resultat haben beste 1. und Undank gibt es Frost und Frust ohne Ende bei denen die etwas länger Geld dafür gebraucht haben wo aber so was sich dann auch die Zähne ausgebissen hat oder dass dann auch ein Stück weit dann irgendwann liegen gelassen hat ist sozusagen die Charakterisierung also Gravis per die Vermutung waren Graph ist perfekt genau dann wenn er keine ungeraden Kreisen oder deren Komplimente enthält als Mino ja und als sie dann auch die Zähne ausgebissen unbedarfte gibt es einen aus meiner Sicht eine der während der großen oder dicke großen Graphentheorie Gemeinsinn Robertson und 7 Uhr also die die haben waren sich viel in der Graphentheorie an haben bewiesen die anderen sich mal den Forschungsantrag geschrieben werden wenn man sich ein halbes Jahr zurückziehen konnte oder so und anders machen unseren Uni-Vorlesung sonst was die samtigen halbes Jahr zurückgezogen noch zu ich 2 Leute dazu man versucht dieses Ding zu beweisen haben soll in dem halben Jahr leider ohne hingekriegt aber ein gutes Jahr später haben sie es dann nämlich also diesen Beweis will auf jeden Fall unterscheiden wissen zwischen alles weil infiziert aber inzwischen ist es also dass diese Vermutung des war wirklich über 30 Jahre der Vermutung sie Satz also das Projekt Rupp wenn ich hier wir könnten alle Klickens der bei dir besser ganzzahlige Lösung genau dann wenn der Graph perfekt ist und der Graph ist perfekt genau dann wenn er keine ungeraden Kreise den komplementären also da ist eine ganz nette Geschichte sozusagen aus der Verbindung Graphentheorie auch hier zur politischen Kombinatorik also dieses dieses Gebiet stabile Mengen und perfekte Grafen das fasziniert die gerade derjenige auch die politischen Kombinatorik ja schon seit Jahren Jahrzehnten und ist bei weitem noch nicht das Ende der Fahnenstange es gibt waren sich viele Bäcker und zu gleichen zu diesem Polit man nun an es gibt Blüten und Gleichungen an die an die Loch Umlagen Räder an den Netz Netz Kleidung ungleich und und und und und also es gibt Sie da schon bisschen Spaß daraus gemacht gesagt ist neu und gleiche finden guten Namen beweist was es Facette ist und wenn einem die Namen ausgehen findet man immer wieder mal noch eine Facette A und bei der Tropf an Fassetten die 4 bis zum Polit-Talk gibt ist immens groß sozusagen gut so weit vielleicht zudem zu den Schnittebenen Ansatz wie gesagt Schnittebenen also die DLP Galaxie herumzubasteln bereits im zunehmend steht eben zu generieren ist heute in der Ansatz zu lösen gemischt Anzeigeprogramme wir werden das nachher noch erweitern im nächsten Kapitel dann indem man das in in Innovation einbetten aber Schnittebenen kombiniert mit zur Innovation allen kommerziellen löse und alle Forschungsgruppe basieren auf diese Ideen er und was an Ideen sozusagen auch in den letzten 30 40 Jahren entwickelt wurde um diese Polit Truppe besser zu verstehen wie verstehe ich diese dieses diese Politiker der Politpoker am besten weiß viel investiert worden was den gerichtlichen Randbedingungen haben man kann das jetzt natürlich so ein bisschen als Mehr mathematische Spielwiese für sich ansehen das Marke richtig sein aber auf der anderen Seite hat es auch ohne praktische Relevanz weil diese Bedingungen die man hier entwickelt das sind die Bedingungen die man tatsächlich braucht wenn sie später in der Praxis ein Problem angehen ist es häufig so dass sie auch an den Projekten die wir mit mit Industriepartnern machen sehen auf den Wald vor lauter Bäumen nicht man erkennt nicht das ist der wahre kann das Problem was sind die wahren Randbedingungen die meine Optimierung treiben der Körper bei allen möglichen Randbedingungen formuliert die Wände haben doch alle gar nix mit dem Problem zu tun und wie erkenne ich was die richtigen Rahmenbedingungen sind die die optimale bestellen und dazu muss ich diese Politiker studieren und dazu muss ich die richtigen Rahmenbedingungen finden für diese Politik ja und in diese Eigenschaft zu zeigen dass er Facette ist dies sagt mir es keinen Fall gegeben ich weiß es mit Wasser des keinen Fall geben wo genau dieser Ungleichung wichtig ist also in dem Sinne gibt es unheimlich strukturelle einzig in in diese Art von Problemen auch die Denkweise wie wir dann Mathematiker eben herangehen sie ganz anders die jeder Praktiker zu ja und dann da noch ist es häufig so dass der alles was sich in der Praxis Leute auf dann Bedienkonzepte denn die eigentlich gar nicht relevant sind und den zu zeigen damit auch dass wir das Potenzial gute Lösungen zu finden zu zeigen sich damit verwehrt und da hilft es auch häufig sozusagen bisschen deren einzig zu gewinnen so wie wir das sozusagen der versuchen so weit vielleicht erst mal zu dem Ansatz über LP der Erziehung Schnittebenen es da Ihrer sei dennoch noch Fragen dazu wenn das nicht der Fall ist würde ich dann an bei den Ansatz versuchen wie kriegt man und Schranken oder der Lachs zierungen es gibt nämlich noch der sagen wird wir anlässlich Ansätze noch 2 2 weitere oder 3 weitere immer dann aber dann daher sehen das den irdene Form alle 10 an Erkelenz sind aber zumindest der Zugang ist erst mein anderer und den 2. den uns anschauen das ist Freisler Garage Platzierungen gelungen des wollen in was genau angucken was das bedeutet ob alles Kapitel 3 2 oder gar Schüler Xeon also die die ist seit ich eingangs schon mal gesagt wenn man allgemeines gar Gemisch ganz Programm haben wo liegt die Schwierigkeit in dem Problem warum und wir haben ja eine Möglichkeit die offensichtlich ist es seine die Schwierigkeit liegt an dieser ganzzahlig kalt war bei LP wenn ich keine ganz Seitwärtsbewegung hat kann ich am wollen mehr Zeit lösen man ein Film kennen gelernt also das war der Ansatz den wir jetzt verfolgt hatten wir lassen die Ganzheitlichkeit weg und versuchen die zurückzuführenden Problem überschnitt eben ja wir versuchen die Ganzheitlichkeit zu zwingen diesen Ansatz in die wir die richtigen ungleichen separieren damit wir sozusagen die optimale Ecklösungen dann automatisch ganzzahlig bekommen wir also Rückführung der Ganzheitlichkeit überschnitt eben sollte an anderer Ansatz könnte es sein zu sagen es liegt mir wirklich einer
ganzer lichkeitsbeteiligung Touristik einem würden Nebenbedingung alle ganz einfacher fallen ich hätte nur 0 1 Würfel werde kleiner gleich x sieht er gleich ein sich vor der XI aus 0 1 IP offensichtlich bis sofort ne ganzzahlige Lösung geschehen an sobald ich eine Bedingung rein setzte wenn ich mir so ein Würfel anschaue weiß die Welt noch in Ordnung er es irdene blöder Randbedingungen ein und dies eigentlich schuld das alles kaputt macht weil da wirklich erst diese gebrochen Lösung also nämlich die die bösen Randbedingungen aus die die Ganzheitlichkeit kaputtmachen er er schon bisschen kennen gelernt bei dieser damit Normalform bei dem ganzzahligen Farkas immer mehr A X gleich B X ganzzahlig lässt sich einfach lösen nur wenig X-Cooler gleich 0 da zunehmend dann wird endlich werde also es kann selbst auch andere alle Randbedingungen gegen das was schwer wird er sollen das ist der Ansatz von von La Kranich zu sagen der lass uns doch mal die schwierigen Randbedingungen wegnehmen und was da die schwierigen sind das muss man sehen dass die auch von dem Problem Beispiel aber erst mal der allgemeine Ansatz geht aus und so wird der Ansatz auch entwickelt ist wenn man einfach eine Teilmenge dieser Randbedingung und nehmen sie aus dem Problem raus was passiert wenn wir das tun wir tun das mal in die raus und löst das über den Rest soll es Scharons muss die Lösung an wenn wir Glück haben sind die Mehr rausgenommen auch erfüllt Nivelles in Ordnung wir haben die optimale Lösung gefunden in der Regel wird aber so sein dass die Lösung der gefunden haben der Reihe von diesen Bedingungen die immer ausgenommen haben verletzt sowie Kinder die wieder rein und der Einsatz von lag alles zu sagen wir bestrafen die verletzt in der Zielfunktion also ich Raub Penner sozusagen auf dieser Randbedingungen wie ich die ich eher raus genommen hat um eine Lösung hatte in die wir sozusagen dieses verletzt dann nämlich Straftaten in die Zielfunktion auf Umwegen Startern dann groß genug will dann wird er mir schon eine Lösung finden die diese Bedingungen erfüllt dass der Ansatz sollten wir das alles nur formalisieren und wenn wir das aber formalisieren es wird nein er dann ,komma naht was mit abwarten würde ein wichtiges gar zu blöd denn es können einige sich das sogar die ganzzahlige optimale Lösung finden weil ich muss ja nur die Straftaten so hoch wählen dass ist überhaupt nix bringen zu zahlen es den anderen bis hin zu verletzen es aber nicht so also man schafft es nicht auf die Art und Weise auch wieder die ganz sei dem zufrieden aber wir sind mindestens so gut wie Geld per Galaxie und alles aber nachweisen können dass mit diesen lag rascher Einsatz mindestens so gut sind wie das was wir rausgingen SLP dazu es sind also bewegen sonst irgendwo zwischen LP um ganzzahlige Lösung und es gibt in beide Richtungen wirken gut also schauen uns das mal an also allgemeine Ansatzes einfach zu sagen wir schauen uns Minimierung Scobbling sagen man in dem Fall minimiert CTX mit einem setzt unser Nebenbedingungen in 2 Teile auf einmal den 1 Teil A N 1 X kleiner gleich B 1 und A 2 X kleiner gleich B 2 wenn man so möchte ja unser Ursprungs Matrix einfach aufgeteilt in 2 Teile des gleiche 4 B auch und Teilen des so auf ja und wir bei hier unten X aus mit den in dieser Allgemeinheit lassen ein paar von den es sind ganzzahlige und Umbau von den 10 kontinuierlich so jetzt machen wir genau diesen Ansatz wir nehmen an einer größeren Rolle Salander größer gleich 0 und wir schauen uns folgende Funktionen L von Wanda es gleich das Minimum über c't iX so -minus landen da mal wie 1 -minus A 1 x Unterbelegung das X aus dem Polier P 2 ist vorbei hier 2 ist wie folgt definiert wird zwar ist die Menge aller x aus Z hoch n -minus kreuzt auch P aber 2 x kleiner gleich B 2 nur soll dieses Problem schauen wir uns an so was was sehen wir hier erst mal also minimieren über über dieser Menge P 2 da ist die Ganzheitlichkeit noch dabei war also wir lassen jetzt im Gegensatz zum vorigen Ansatz die Ganzheitlichkeit dabei wir müssen nur sozusagen diese Ungleichungen die rausgenommen und dann steht noch genau das gleiche Problem und die haben wir jetzt hier bestraft der warum hierzu zuletzt die einen angenommen ich hab ne Lösung über den Xtra über den P 2 und es verletzt Mehr eine dieser Bedingungen der dann SP 1 -minus 1 x negativ ja mit dem -minus hier als positiv wenn ich das Lander groß wäre dann besprach ich bestrafe ich meinen Jungs Probleme er also die Idee ist er das X wird hier schon wir suchen nachdem ich das hier bestrafe zu versuchen diese Bedingungen einzuhalten also diesen Teil hier größer gleich 0 zu wählen wir bei den ist größer gleich 0 will dann belohne ich sogar noch ok also dass die Idee und diese Funktion L verlangen da in Innenanlage rasch Funktion also 11 voneinander 1 wer gar Hashfunktion und Thron und und so weisen auch sofort sehen ist was hier rauskommt ist in eine untere Schranke für das hier warum es denn so also ich im Skript hat dass hier die Nummer 3 15 war also das nehmen wir mal an werden wir eine zulässige Lösung für ist sei X Klehr zulässig das alle Probleme hier 3 15 und wir schauen uns gleichzeitig ja und dazu ist der zwar des Mainz Verhältnis schauen wir uns das mal an also c't iX quer das ist sicherlich wenn ich jetzt endlich die Zielfunktion einsetzt ist sicherlich größer gleich c't X quer -minus Lander mal wie 1 -minus A 1 x quer warum wir X Käse zulässiges orginal das heißt dieses Teil hier größer gleich 0 das Land als auch größer gleich nur 70 höchstens was ab er soll jetzt hab ich aber jedes Minimum gewählt das heißt es XP aber ist sicherlich auch zulässiges P 2 es für alle beginnen also auch die P 2 also es sind zulässiger Punkte das ziehen wir also ist das hier wieder sicherlich größer gleich als wenn ich vorne das Minimum dransetzt c't iX -minus Lander mal B 1 -minus A 1 x ja und X aus P 2 ja das ist aber genau das L voneinander ab als ist es 11 einander Filmfestes Lander in eine untere Schranke für den wahren Funktionswert und so nachdem das Land da jetzt irgendwie beliebig gewählt aber fest ,komma die jetzt über diesen langen Damm optimieren also warum es gerade ein beliebiges Land wählen wir können setzt folgendes Problem anschauen maximieren es einmal Wallander und wir schauen uns das folgende Problem an ja also ist soll die Nummer 1 maximiere über alle lahmender größer gleich 0 die Elf von anderen von dem wissen auch dass es eine untere Schranke ist wird das sicherlich auch eine untere Schranke dabei wo man Filmfest das Land also gilt für alle alle können über diesen Landes maximieren also das ist sozusagen die beste unter der Schranke hier mit diesem Ansatz kriegen können und diese wie und dieses optimieren Problem heißt aber lag Gage erzielte heißt war und der mehr ja
das den Skripte die Nummer 3 17. soll es stellen sich natürlich per Fragen als ihr neues Optimierungsprobleme Börse wir wieder Max rein weisen das L Land überhaupt für ein Problem ist dass es auch wieder und Polly das ist das Programm ist nicht aber was ist das eigentlich kann man es überhaupt lösen kann das ist die eine Frage die 2. Frage angenommen wir können sie lösen haben wir haben Lander Stern Nastase jedes Maximum annimmt wie gut ist denn das er schafft nur wirklich diesen Wert hier für die optimale Lösung oder 7 Spiele sogar schlechter als LP Galaxien dass die 2. Frage und beide Fragen versuchen wir es mal zu beantworten wir fangen mit 2. an und und Thomas so als können wir das Problem lösen und schau mal wie gut wir damit sind ja nein der also der 1. Satz gibt und schon mal Auskunft über über die Qualität der Stern optimale Lösung von diesen 3 17. danke der folgende Satz es gibt aber die Nummer 3 33 L Stern 1 EL von Lander Stern ist nix anderes als das Minimum über c't iX zur A 1 X kleiner gleich B 1 und X aus da konvexen Hülle von P 2 .punkt so was steht jetzt da und schauen uns das mal an alles eine positive interessante ist schon mal bislang der Stein erfüllt tatsächlich diese Randbedingungen und erfüllt das das X aus diesem weiß konvexe Hülle davon was wir nicht haben okay was wir nicht haben ist was wir eigentlich bräuchten ist X aus der konvexen Hülle wo das A 1 x 1 ist auch da drin steckt das haben wir nicht und Unterschied also die Menge kommt wenn ich die Daten hat die kann deutlich kleiner sein als das +plus das nach außen ziehen also sorgt wir ein kleines Beispiel aber es ist wissen Sie Übungen machen müssen ja wenn man das in der Übung ist vielleicht ganz gut wenn es Übungen für Paradies daran ist an der Stelle erst mal nicht dass das also diese Menge Wasser sofort sehen also haben folgende folgende Inklusion sozusagen Minimum also die Menge aller x ja A 1 x 1 gleich B A 1 und A 2 X kleiner gleich B 2 ist sicherlich größer als diese Menge wenn die Menge aller X-A1 Xtra 1 gleich B 1 und X aus Conf P 2 aber dieser ist sicherlich wieder enthalten in die Menge alle x X aus konvexe Hülle von A 1 x kleine gleich B 1 er 2 x kleiner gleich B 2 und x aus der doch also und damit was sofort diese Inklusion das das ist das was wir es aushalten dass La Kranich hängt genau dazwischen ja die LP der Erziehung also an der Qualität der Handy die Schranke die Maus der lag Rage Erziehung ging zwischen der was die ganzzahlige Lösung betrifft und der LPG Galaxie gut also der Vorteil der Mehrwert den wir hier haben ist dass so viel dieses Preises dem Ganzheitlichkeit mit fordert ja das der Mehrwert der hier steht bei der PL Erzählungen haben wir hier nicht diese Ganzheitlichkeit Bedingungen mit Tränen in den Bereich und den ganzzahligen phasenweise für alle ok also das ist eine Folgerung daraus dass wir beweisen müssen dass das Sie also dass das hier gilt und da war uns das war wegmachen das ist auch tatsächlich Geld so dann muss man bisschen Schaufel und realisieren und hat alles was man Einführung kennen gelernt haben Exkurs ausnutzen glaubt fangen man also beweist Notruf also wir schreiben erst mal 11 von Lander man schreiben als das Minimum überall X aus P 2 so sehr gerade definiert c't iX -minus Lander aber mal wie wir 1 -minus A 1 x nur so war die Definition so nachdem eine lineare Zielfunktion haben wir können anstatt des mir (klammer auf schreiben X aus Grund spielt zwar warum lineare Zielfunktion wird immer man angenommen dass heißt konvexe will Operator Schaden an dieser Stelle nix waren so dass gilt für jedes einzelne damit wissen wir wenn SSL an der Sterne anschauen Erlander Stern ist nix anderes als das Maximum überall der Lander größer gleich 0 ja und Sohn Max mit dem Problem was wir unser Ziel eingeholt haben alle das gleiche Maximum Landtag größer gleich 0 und jetzt über Minimum überall X aus der konvexen Hülle von P 2 von dieser Zielfunktion c't iX -minus Lander mal B 1 -minus A 1 x er das unser Land ab so ist müssen wir uns Folgendes überlegen also und schauen uns mal den 1. Fall eines P 2 über die leere Menge kann ja auch passieren also wir 2 ist leer was passiert dann sollen P 2 leer ist also nicht auch kommt es beim Wechsel von der leeren Menge ist leer das heißt es Minimum hier Wellenlänge ist plus unendlich das 1. Maximum +plus 1 +plus unendlich das Erlangen sind plus unendlich wir was über und so und dann Schranke mehr ist so bei den wenn das hier der auf das Gesamtsystem hier lernen ist das Minimum auch wir Menge das heißt es steht auch E-Plus unendlich und dann ist natürlich auch unser orginal Problemlehrer ja aber wenn der Teile ist muss alles orginal Problem ist also der Fall es in Ordnung zumindest die nicht erst dann wissen wie es aus dem 1. Kapitel wir können unser P 2 wie folgt schreiben können schreiben kommen von P 2 das lässt sich streiten
aber es kommt von der Menge von Knoten kann vor 1 bis vor paar +plus kommen von wir Menge E 1 bis er nur das war unser Darstellung Polyeder kann ich darstellen als konvexe Hülle der Ecken +plus chronische Kombinationen extremalen vorausgesetzt hat Ecken kann es keine Ecken hat sind es sozusagen Elemente der jeweils minimal Seitenflächen gut also wenn ich das jetzt einsetzen was kommt denn dann daraus also was kommt für das innere Minimum hier aus also das können wir hier schreiben also das Minimum an also Minimum c't iX -minus Lander B 1 -minus A 1 x ist dann gleich entweder das ist mir so unendlich falls einer von Denen zuschlägt um also vor c't gehe ich das 1. meinen Landa da transponiert A 1 Eli kleiner 0 ist für ein Emmy am und im anderen Fall ist es genau eine diese Ecklösungen CTV J -minus Lander transponiert B 1 -minus A 1 Vj für für ein ja ok also nochmal wir minimieren hier über diese konvexe Menge und Politikers können 2 Dinge passieren wir wissen das Ding ist ungleich länger als dann kann als Output Ende herauskommt dass Dinge so unbeschränkt ja dass dieser Fall ist den beschränkt ist dann muss eine dieser extrem malen ja ein negatives Skalarprodukt habe der Zielfunktion man das ist das was hier steht also bezüglich X 1 Detail fällt weg noch oder wenn ist nicht unbeschränkt ist dann habe so wir haben endlich das Optimum da endlich optimale sowohl einer Ecke angenommen das heißt es muss eine von diesen Ecken angenommen werden ja so das heißt so ist aber diesen Einfall ein Eis Anwesen zutrifft ja wenn es für alle zu wirft also die kriegen wir jetzt das Waffen also volles überlege wolle das Maximum der auswählen Maxime alle Lande aus also werden das Maximum nicht so wählen also hier ins Minus unendlich laufen wer klar aber Klimas unterschlagen Mine soll endlich raus ja das heißt unser Maximum wird oder den Fällen seien wo es Lander hier ehemals größer gleich 0 ist mit allen extrem mal kann also ich schaff das meinen und dann sei es normal dass genau dazu ja also wir können es Eltern jetzt auch schreiben als folgendes L von Laiendarstellern ist nix anderes als Marx überladen war größer gleich 0 Minimum über J 1 bis grade sollen genau die Ecken seiner 1. CD VJ -minus Laender B 1 -minus A 1 x so und unter der Bedingung dass CC +plus lagen da transformiert A 1 sollte über einen Transfer näher dran machen Eli größer gleich 0 ist für alle so normal warum ist es genau das Gleiche also wir wollen ja dass Lander maximieren wenn angenommen angenommen diese Menge ist dieser Menge ja es gibt da keine Landers sodass das Skalarprodukt mit den extrem mal alle größer gleich 0 ist dann optimieren hier über die leere Menge ist es mir nur der leeren Menge ist -minus unendlich wer und damit Hammer genau sozusagen jedes minus unendlich genau wie wir sie oben haben im anderen Fall wenden wenn es den Lander gibt so dass das hier größer gleich 0 ist ja dann wählen wir natürlich nachdem über dem immer im Maximum wolle über anders das ja dann will man sich ein solches Land wirklich jede nicht negative des Skalarprodukt hat mit allen extrem also ist tatsächlich das Erlander von Sternen übersah man vorhin geschrieben haben wir Maximum L von Lander ist nichts anderes als einfach die Auswertung von den Laden das über diese Ecklösungen so das sein dieser Tage mir nicht der gallige Skalarprodukt extremer können solltest mal einen wird am Ende das brauche noch 2 Transformationen was wir jetzt gerne noch machen wollen ist tualisiert ok so als wolle man aktualisieren das heißt wir packen das Ding jetzt ein wenig Bewegung und schreiben hier oben hin also das ist nix anderes ich schreibe erst mal weiter und zeigen was dazu das Maximum über alle Lander größer gleich 0 und kann es da aus er wer maximieren des Etat und schauen jetzt dass diese Bedingungen eingehalten wir also ein Fahrer Etap +plus dann der transponiert B 1 -minus A 1 VJ ist kleiner gleich 10 transponiert Vj und wir haben -minus Lander transponiert a 1 e s kleiner gleich 10 transponiert II so war ist es dasselbe also die Bewegungen sind die gleichen wie die er ist nur das zählt als wenn er auf die andere Seite gebracht so was wir hier gemacht haben ist diese Bedingungen einfach runter genommen als Nebenbedingung ja schauen Sie mal wenn ich den Teil auf die andere Seite bringen wir dann habe ich als Bedingungen sozusagen État kleiner gleich diese Bedingung was hindert Funktion steht das heißt es ist genau das gleiche ich maximiere Etat ist das gleiche wie Minimum über endlich viele von diesen hier wir haben weil es etwa wird immer wenn ich das maximieren will an einen an der schwersten von diesen Randbedingungen an den an das heißt da kommt genau das Gleiche aus so und jetzt globalisieren und keine sorge für virtualisierte mit vielen Variablen als hier ein und wer da er ja wir schauen uns mal das duale an dass es über diese Jahresprogramm dann endlich viele Randbedingungen damals war ja allen die Lander und des Äthers das weniger als Programm zu dem Lernprogramm gibt es ein duales und wir wissen Stage zahlst Alpinisten Dualität Satz die beiden Werte stimmen überein das heißt wir können jetzt hier wirklich weiter schreiben das ist nix anderes als ich das 1. Mal ausführlich in Minimum C transponiert so Summe Alfa VJ
+plus Summe der da eh die ihn gleich 1 bis 11 Mehr wird gleich 1 Biskra ich hab das mal alle Bedingungen hin und dann sagen was dazu Alfa J gleich 1 -minus A 1 so alle VJ +plus Summe wird da die größer gleich -minus B 1 Summe Wahl verlobt dieser stelle ich lass mal die Indizes sind alle weg und wir alle feiert größer gleich 0 und Delta E auch größer gleich 0 kann so was aber jetzt hier gemacht also virtualisiert man nochmals wie der Randbedingung für meine Variable ein wenn die Rahmenbedingungen in ohne Ungleichungen war wird die Variable Vorzeichen beschränkt ist das dass wir hier er das denn genau weil es die Ungleichung Eisen beide Variablen vorzeigen beschränken sowas ist die Zielfunktion die Zielfunktion steht hier auf der rechten Seite war es genau das C transformierten ich hatte schon zusammengefasst die Altwerden feuert multipliziert und lieber der ist Willi ist es genau das was hier steht so und das hier welche Randbedingungen haben wir ja einmal haben wir das hier zu den Etats werde der jeweils die Alva Yards auf und zwar jeder Seemann Eintrag 1 also die Summe der Alfa Arzt muss genau diese 1 1 Ether ist nicht vorzeigen beschränkt also ging jene Gleichung ist genau diese die gehört zu den Etappen ok sollen denn die restliche ist genau das was hier steht wir wenn wir das auf den Kopf stellen also A 1 -minus A 1 mal und es kommt wie Summe der Peter ist das ist das was hier steht und hier oben die Summe der alle verjazzt feuert ist das was hier steht und und und mir ist es natürlich hier bis zum Idealfall Herz B 1 in der Zielfunktion steht eine 0 das hab ich gleich auf die andere Seite gebracht ok so und was steht jetzt hier aber das Anschauen der die Summe hier ne 1 ja was steht hier jeder steht nix anderes als konvex Kombination decken Summe der Lander J gleich Einzelhandel argloser gleich 0 ist als konvex Kombination Ecken und +plus chronische Kombination extremer ja das ist genau das was oder um Klima haben kommt P 2 ist konvex Kombination dieser Farias und chronische Kombination Ex-Firma weil hier steht eigentlich nichts anderes alles minimiere c't iX hier steht X aus Conf P 2 ja das genau das hier und wir füllen -minus A 1 x größer gleich -minus B 1 oder A 1 X kleiner gleich B 1 kenne und dass das was mir zeigen wollten also ein bisschen technisch aufwendig aber mit einmal globalisieren also mehr mit 2 Sachen verwendeten alle braune Dinge immer wieder die über die entwickelt haben einmal die haben tualisiert Stage Dualität Satz und wie werden zweimal ausgenutzt diese 2 weit darstellen von Politikern einmal über das System von Ungleichungen einmal als konvexe Hülle Opera +plus chronische will Operator gut und dabei da man mit diesen beiden Dingen eigentlich zusammen des vormals Folgerungen Shary erst mal hierhin und dann aber sozusagen diese Klassifizierung schon durchgeführt Folgerungen 3 4 und weil sich was wir haben ist das die Schranke die Maus LP Erzielung kriegen kleiner gleich ist dem Wähler Garage Erziehung und ist kleiner gleich den Wert der ganzzahligen optimale Lösungen also das aber an mit diesen Satz und diesen 2 Inklusion die wir hier haben so damit haben auf jeden Fall schon mal die Aussagen über die Qualität von diesen Lander Stern es ist nur die Frage in was denn aus es keine Liebe gut sein dass wir jetzt das superschlanke haben aber wir wissen wie wir sie außer aber auch wieder verloren was mir jetzt ab angehen wollen ist dass wir das Ding auch tatsächlich ausrechnen kann und der Methode angeben wie man es ausrechnet und einen Hinweis geben das muss sogar in kolonialer Zeit ausrechnen kann nur das machen ein bisschen später nicht an dieser Stelle dafür weil sich dann auf dem übernächste Vorlesungen wurde zum andern Zusammenhang uns dann noch mal genauer angucken nämlich dann wenn wir die Ansätze alle Ansätze wie wir uns das anschauen nochmal paarweise miteinander vergleichen der mehr also wieder das Ding aus also Berechnung von standen und wer kann hat das und ob wirkte .punkt wir man den 1. Satz dazu ist was ist dieses 11 Lande eigentlich überhaupt für eine Funktion ja und die Aussage ist 11 Anlagen da ist stückweise lineare konkav ist stückweise wir ja wird der entkommen Graph will dort wo's beschränktes also dort wo zwar vielleicht dazu schreiben dort oder Funktion oh .punkt oh beschränkt ist so ist müssen wir einer noch gucken da aber schon Stück davon wecke Besteller umgestellt also stückweise lineare weiß sie suchen stückweise ja Klima Einfahrt des Schädlings oben als die Funktion des beschränkt genau dann wenn diese Bedingung für die extremalen Geld hier oben steht gerade wenn es c't Transmit mit 1 Ei Größe gleich 0 ist genau dann wenn es nicht gallige Skalarprodukt extremalen will genau dann ist die Funktion besprechen so was ist es wenn Sie wenn das erfüllt ist dann steht darum als Minimum da steht die das denn endlich viele Jahre vom jene Funktionen c't -minus dann der ist ist mir viele Funktionen an das heißt wir unendlich viele von denen endlich viele viele Funktionen so was man das das Minimum von endlich vielen Zeugen auf die Funktion das heißt die Funktion stückweise lineare ok also folgt direkt aus ich habe es aber einen links oben vom folgt aus links oben für das was wir brauchen ist dass es das für die so aussieht und nicht so es könnte also sein oder es könnte das können wir weder das eine noch das andere sollen könnte auch sowas sein kann was wird doch zeigen wollen dass das ist diese Form hat ok
so was müssen wir dazu noch zeigen also zu zeigen ,komma Graph .punkt was wir dazu tun also wenn man 3 langen haben also Salander 3 gleich alle 1 plus 1 -minus Lander Malanda 2 zu zeigen ist 1. 11 von Land A 3 größer gleich die 1. alles als normal von 1 plus 1 bis alle formal 11 von Lander 2. also im Bild in dem er hier war es noch ins Bild wir übernehmen 2 Punkte Sommer hier soll das Land solle 11 von Land A 1 wie es irgendwo das er von Land A 2 es den ich mir irgendwie konvex kommen also die konvex Kombination von diesen beiden Punkten ja das ist das All vor das 1 wie das alpha und dann bin ich hier wenn ich irgendwo das L von Land 3 nehmen dann bin ich halt immer drüber ja das heißt konkav also hier ist dann irgendwo das 11 von Land A 3 und egal wo ich mich hier bewegt die Funktion selber ist immer oberhalb der blauen Linie kann so dass besonders danach rechnen das eigene Fleißaufgabe aber wir schauen es mal ein bisschen müssen halben Dotation arbeiten aber komm ,komma das was linke gelegen und dann Ausschluss danach ja
also fangen wir einfach allerdings an 11 von Land 3 das ist sicherlich gleich zu den Lander 3 gehört natürlich ein eine solche Ecke Frau ich mal VJ 3 er ist der Wert -minus Lander 3 transponiert mal B 1 -minus A 1 Frau Yardley ok soll das können wir jetzt schreiben wir lassen das alles wie es ist nur an dieser Stelle bislang dann 3 das Brüsseler jetzt auf so wie es da oben steht das ja nichts anders als alle Wallander 1 plus 1 -minus Alfa Wallander zwar in ja so wenn man das haben soll sortieren immer das nur ein bisschen anders dann schreiben dass man nicht als 1. mal hin das ist alle Fahr mal C transponiert VJ 3 -minus Lander 1 transponiert P 1 -minus war er ins VJ 3 +plus 1 -minus Alfa so c't Frau ihre 3 -minus Lander 2 transponiert B 1 -minus A 1 VJ so was einmal gemacht soll dies in diesen Teil hier der Name aufgedröselt also den hier einmal hier in Alfa c't 3 und 1 -minus Alphatier an und es dann einfach abgeschrieben hier steht alle ab mal Landa 1 das was hier steht und hier steht es 1 -minus alle formal bislang der 2. was hilft ok so jetzt können wir jetzt können wir eigentlich ich kürzesten bisschen ab
vielleicht wir können jetzt die einfachen größer gleich schreiben wir ich schreibe einfachen größer gleich und dafür mache ich jene einziehen und wir auch ne 1 Jahr kann ich das machen
wer das Land nach 1 2 die optimale Lösung zudem VJ 1 das heißt wenn ich bezüglich Lande 1 mit optimales an würde würde der bei Paul J 1 angenommen ich bei Feuer 3 ja also die Zielfunktion steht beim Lander 1 das ist die optimale Lösung ist feuert 1 an und das Gleiche gilt natürlich hinten ja mal in entsprechender Weise aus dem Vorjahr zwar 3 in Vorjahr zwar in DEU weil die Lander wer dessen jeweils die optimale Lösung zu binden zugehörigen Feuer 2 Sonnenlicht das Haar ab ja dann kann ich jetzt hier einfach schreiben was hier steht ist dann einfach alle Fahr mal um was hier in der Klammer steht ist nichts anders als L von Land A 1 +plus und hinten steht 1 -minus Lander und hier drinsteht 11 von Land 2 so dass genau das das mal zeigen wollten L von Land 3 ist größer gleich das was hier steht und das ist das was wir hier oben rechts um zu zeigen hatten und da einmal gezeigt dass diese Funktion genau diese Form hat er stückweise lineare und Graph und über so nur stückweise lineare konkaven Funktion das Maximum bildet dann der Stern auszurechnen das schauen wir uns dann nächste Woche an vielen Dank
Kreis
Nebenbedingung
Matrix <Mathematik>
Hypergraph
Matrizenmultiplikation
Punkt
Kreisfläche
Graph
Besprechung/Interview
Aussage <Mathematik>
Gleichungssystem
Kante
Computeranimation
Ungleichung
Ganze Abschließung
Uniforme Struktur
Diskrete Optimierung
Schnitt <Mathematik>
Struktur <Mathematik>
Kreis
Summe
Lösung <Mathematik>
Ungleichung
Menge
Koeffizient
Betafunktion
Vorlesung/Konferenz
Platte
Skalarfeld
Nebenbedingung
Kreis
Klasse <Mathematik>
Inzidenzalgebra
Ganzzahlige Lösung
Komplexitätstheorie
Richtung
Variable
Ungleichung
Wiener-Hopf-Gleichung
Ganze Abschließung
Canadian Mathematical Society
Vorlesung/Konferenz
Inklusion <Mathematik>
Auswahlaxiom
Gerade
Kreisfläche
Vektorrechnung
Physikalischer Effekt
Automat <Automatentheorie>
Randbedingung <Mathematik>
Teilmenge
Summe
Quote
Menge
Vollständiger Graph
Diagonale <Geometrie>
Mathematische Größe
Kreis
Zugbeanspruchung
Komplementarität
Große Vereinheitlichung
Klasse <Mathematik>
Besprechung/Interview
Formation <Mathematik>
Gleichungssystem
Ganzzahlige Lösung
Vollständigkeit
Ungleichung
Ganze Abschließung
Optimierung
Inklusion <Mathematik>
Tropfen
Gerade
Parametersystem
Dicke
Kreisfläche
Mathematik
Graph
Optimierungsproblem
Randbedingung <Mathematik>
Kombinatorische Optimierung
Zahl
Teilmenge
Summe
Lösung <Mathematik>
Kombinatorik
Menge
Siebzig
Graphentheorie
Normalvektor
Gebiet <Mathematik>
Diagonale <Geometrie>
Schranke <Mathematik>
Mathematische Größe
Nebenbedingung
Untere Schranke
Minimierung
Besprechung/Interview
Reihe
Konvexe Hülle
Maximum
Randbedingung <Mathematik>
Ganzzahlige Lösung
Richtung
Teilmenge
Operator
Ungleichung
Menge
Würfel
Normalform
Ganze Abschließung
Minimum
Zielfunktion
Inklusion <Mathematik>
Funktion <Mathematik>
Nebenbedingung
Zusammenhang <Mathematik>
Konvexer Körper
Berechnung
Maximum
Optimum
Dualität
Variable
Ungleichung
Operator
Vorzeichen <Mathematik>
Minimum
Vorlesung/Konferenz
Zielfunktion
Inklusion <Mathematik>
Funktion <Mathematik>
Polyeder
Graph
Aussage <Mathematik>
Konvexe Hülle
Randbedingung <Mathematik>
Gleichung
Lösung <Mathematik>
Summe
Skalarprodukt
Menge
Ecke
Konvexe Menge
Punkt
Graph
Ecke
Linie
Graph
Maximum
Vorlesung/Konferenz
Zielfunktion
Konkave Funktion

Metadaten

Formale Metadaten

Titel Lagrange Relaxierung
Serientitel Diskrete Optimierung (Optimierung II)
Teil 14
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/31788
Herausgeber Technische Universität Darmstadt
Erscheinungsjahr 2009
Sprache Deutsch

Inhaltliche Metadaten

Fachgebiet Mathematik

Ähnliche Filme

Loading...