Descision-Based Approaches - Branch-and-Bound

Video thumbnail (Frame 0) Video thumbnail (Frame 10442) Video thumbnail (Frame 20597) Video thumbnail (Frame 32997) Video thumbnail (Frame 37514) Video thumbnail (Frame 51277) Video thumbnail (Frame 59662) Video thumbnail (Frame 69562) Video thumbnail (Frame 78899) Video thumbnail (Frame 87156) Video thumbnail (Frame 89586) Video thumbnail (Frame 93422) Video thumbnail (Frame 98486) Video thumbnail (Frame 101244) Video thumbnail (Frame 103887) Video thumbnail (Frame 106542) Video thumbnail (Frame 115312) Video thumbnail (Frame 124082) Video thumbnail (Frame 130746) Video thumbnail (Frame 133567)
Video in TIB AV-Portal: Descision-Based Approaches - Branch-and-Bound

Formal Metadata

Title
Descision-Based Approaches - Branch-and-Bound
Title of Series
Part Number
8
Number of Parts
12
Author
License
CC Attribution - NonCommercial - ShareAlike 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this license.
Identifiers
Publisher
Release Date
2012
Language
German

Content Metadata

Subject Area
Abstract
Auf Basis analytischer Sachverhalte entwickeln wir algorithmische Ideen für Verfahren auf Graphen. Daraus entstehen zunächst generische Verfahren, welche formal bezüglich ihrer Korrektheit und Laufzeit analysiert werden. Im Anschluss daran werden in jedem Kapitel Techniken zur Verbesserung und Beschleunigung vorgestellt. Abgerundet wird der Stoffplan durch zahlreiche Modellierungs- und Anwendungsbeispiele und der (optionalen) Implementierung eines Benchmarks verschiedener algorithmischer Varianten.
Loading...
Zahl Direction (geometry) Maxima and minima Zielfunktion Inequality (mathematics) Theory Variable (mathematics) Number Matrix (mathematics) Solution set Zusammenhang <Mathematik> Ganzzahlige Lösung Mathematisches Problem Summation Linear map Gradient Polygon Set (mathematics) Binary file Variable (mathematics) Computer programming Subset Summation Linie Integer
Constraint (mathematics) Symplectic manifold Complementarity Lösung <Mathematik> Decision tree learning Bound state Solution set Network topology Partition of a set Supremum Maß <Mathematik> Arc (geometry) Linear map Fundamental theorem of algebra Feasibility study Set (mathematics) Subset Root Travelling salesman problem Network topology Ecke Vertex (graph theory) Integer Mathematical optimization Untere Schranke
Kante Link (knot theory) Constraint (mathematics) Graph (mathematics) Weight Direction (geometry) Maxima and minima Berührung <Mathematik> Lösung <Mathematik> Matching (graph theory) Zielfunktion Subset Plane (geometry) Solution set Graph (mathematics) Cloning Energy level Divisor Summation Linear map Matching (graph theory) INTEGRAL Linear programming Drop (liquid) Set (mathematics) Computer programming Zielfunktion Similarity (geometry) Subset Symmetric matrix Gaussian elimination Network topology Cost curve Configuration space Mathematical optimization Integer Untere Schranke Combinatorics
Zeitraum Direction (geometry) Lemma (mathematics) Maxima and minima Feasibility study Zielfunktion Set (mathematics) Bound state Zielfunktion Subset Solution set Vertex (graph theory) Energy level Mathematical optimization Untere Schranke
Kante Constraint (mathematics) Weight Graph (mathematics) Direction (geometry) Maxima and minima Inequality (mathematics) Integral element Number Dimension n Mathematics Solution set Graph (mathematics) Interface (chemistry) Ganzzahlige Lösung Vector graphics Divisor Summation Gebiet <Mathematik> Linear map INTEGRAL Polygon Linear programming Drop (liquid) Square Two-dimensional space Incidence algebra Computer programming Rounding Similarity (geometry) Subset Symmetric matrix Gaussian elimination Search algorithm Ecke Optimum Integer Mathematical optimization Untere Schranke Bounded set Relaxation Combinatorics
Kante Stress (mechanics) Computer programming Link (knot theory) Graph (mathematics) Model theory Constraint (mathematics) Weight Maxima and minima Kennzahl Lösung <Mathematik> Function (mathematics) Equation Inequality (mathematics) Weight Variable (mathematics) Lagrange-Methode Plane (geometry) Network topology Vector space Graph (mathematics) Vertex (graph theory) Divisor Nichtlineares Gleichungssystem Linear map Ganzzahlige Optimierung Decision theory Drop (liquid) Set (mathematics) Similarity (geometry) Subset Algebra Symmetric matrix Gaussian elimination Travelling salesman problem Function (mathematics) Network topology Equation Coefficient Mathematical optimization Combinatorics
Model theory Constraint (mathematics) Weight Graph (mathematics) Symplectic manifold Maxima and minima Propositional formula Zielfunktion Equation Variable (mathematics) Lagrange-Methode Mathematics Zusammenhang <Mathematik> Implicit function theorem Vector space Graph (mathematics) Valuation using multiples Divisor Linear map Differentiable function Decision theory Curve Drop (liquid) Similarity (geometry) Subset Symmetric matrix Gaussian elimination Function (mathematics) Mathematical optimization Combinatorics
Decision theory Model theory Constraint (mathematics) Symplectic manifold Neighbourhood (graph theory) Drop (liquid) Feasibility study Zielfunktion Zielfunktion Variable (mathematics) Boom barrier Matrix (mathematics) Function (mathematics) Vector space Vector graphics Summation Mathematical optimization Linear map
Decision theory Model theory Constraint (mathematics) Symplectic manifold Maxima and minima Drop (liquid) Feasibility study Zielfunktion Zielfunktion Variable (mathematics) Lagrange-Methode Function (mathematics) Vector space Valuation using multiples Vector graphics Mathematical optimization Linear map
Point (geometry) Kante Greatest element Decision theory Model theory Constraint (mathematics) Symplectic manifold Maxima and minima Drop (liquid) Feasibility study Set (mathematics) Function (mathematics) Zielfunktion Weight Variable (mathematics) Lagrange-Methode Solution set Function (mathematics) Vector space Valuation using multiples Summation Mathematical optimization Untere Schranke Linear map
Constraint (mathematics) Constraint (mathematics) Symplectic manifold Maxima and minima Feasibility study Infinity Zielfunktion Lagrange-Methode Orbit Function (mathematics) Network topology Vector space Mathematical optimization Untere Schranke
Greatest element Constraint (mathematics) Symplectic manifold Maxima and minima Feasibility study Junction (traffic) Numerical analysis Lagrange-Methode Number Function (mathematics) Vector space Mathematical optimization Untere Schranke
Höhe Constraint (mathematics) Direction (geometry) Symplectic manifold Maxima and minima Feasibility study Zielfunktion Mathematical structure Lagrange-Methode Function (mathematics) Vector space Differentiable function Valuation using multiples Abstieg <Mathematik> Mathematical optimization Schrittweite
Kante Computer programming Constraint (mathematics) Graph (mathematics) Direction (geometry) Symplectic manifold Complementarity Maxima and minima Function (mathematics) Lagrange-Methode Variable (mathematics) Mathematics Plane (geometry) Vector space Summation Optimization problem Feasibility study Linear programming Set (mathematics) Variable (mathematics) Zielfunktion Symmetric matrix Function (mathematics) Travelling salesman problem Abstieg <Mathematik> Quote Mathematical optimization Mathematical optimization
Kante Stress (mechanics) Constraint (mathematics) Eigenvalues and eigenvectors Graph (mathematics) Direction (geometry) Symplectic manifold Complementarity Maxima and minima Linear programming Set (mathematics) Inequality (mathematics) Variable (mathematics) Symmetric matrix Network topology Travelling salesman problem Object (grammar) Summation Length Absolute value Partition (number theory)
Graph (mathematics) Symplectic manifold Physical law Maxima and minima Linear programming Set (mathematics) Order of magnitude Variable (mathematics) Physical quantity Calculation Symmetric matrix Grand Unified Theory Network topology Travelling salesman problem Search algorithm Decimal
Multiplication Symmetric matrix Network topology Travelling salesman problem Graph (mathematics) Symplectic manifold Maxima and minima Valuation using multiples Linear programming Zielfunktion Variable (mathematics)
Symmetric matrix Network topology Travelling salesman problem Graph (mathematics) Symplectic manifold Linear programming Variable (mathematics)
genommen die also immer so sein Nachbar für den hat er in an TU-Darmstadt so hallo allerseits ich
darf Sie herzlich wie üblich begrüßen zu dieser nachtschlafenden Zeit 9 Uhr 50 so ich wollte nochmal ganz klar kurz einen Schritt zurück gehen auf eine Folie die wir glaube ich vor übersprungen haben wohl die 32 oder jedenfalls nur sehr kurz angesprochen haben weil sie noch mal wesentlich sein wird als kleine Auffrischung wesentlich sein wird für das was wir heute zu besprechen haben für einzelne Punkte so das ganze ist hier etwas kompliziert aber etwas abstrakt formuliert was zunächst einmal hier steht ist sie kennen die ja gleich Systeme aus den Ländern Algebra AX gleich B A X kleiner gleich die das ist im Prinzip dasselbe nur dass sie nicht Gleichheit und Ungleichheit haben das heißt also sie haben die Matrix aber kürzlich wie üblich ab mit der Spalten Zahl und der Zahlen Zeilenzahl allen ein bitte der weckte den Sie suchen ist x 1 bis x 1 er gut ich glaube ich muss hier die Zahlen die Spalten Zahl umtauschen denn auf der Folie ständig XM sondern X wir doch es richtig Entschuldigung die spaltete die die Zeilennummer so wie jetzt hier so dass es falsch M 1 und 1 so das ist jetzt komponentenweise kleiner gleich D 1 bis B 1 was nicht muss bedeutet als für jedes I ist Sommer aber J ja das gleich 1 bis malt XII Ort gleich E für eine E aus 1 bis klein eben nicht gleich wie so ein kleiner gleich wir werden gleich noch mal behalten Sie das 1. Mal im Kopf wir werden gleich noch mal bei uns am Standardbeispiel TSB sehen wir eine ganze Menge verschiedener Problemstellungen auf diese abstrakte Art und Weise formulieren können das ist ein wesentlicher Punkt beispielsweise auch in der Veranstaltung allegorisch Modellierung im nächsten Semester diverse Problemstellung modellieren als so ein P warum macht man das wenn man für diese abstrakte darstellt denn und wenn man ein Problem so darstellen kann dann gibt es löst mit denen man dieses Problem dann besser lösen kann als also also man kann man kann gut erwarten dass auch relativ große Problemstellungen ganz gut damit gelöst werden können mit diese auch wenn es endlich schwere Probleme sind es war da schon sehr weit so das ist ein indischer länger pro Frau gelenkt werden so heißt also das Motto wenn hier ist eingeführt worden seinerzeit Zeit als es noch keine Informatik gab als man noch nicht vom programmieren also also nicht darum gehen Programme zu schreiben so als als es darum ging oder als man Problem verstanden hat als er mathematische Problem aus der Praxis zu lösen werde WDR Variablen Werte zu finden so das kann man sich so vorstellen wie es hier rechts gezeichnet ist im zweidimensionalen also stellen sich vor dass X wäre zweidimensional N wäre gleich 2 dann können Sie sich das so vorstellen wie das hier ja recht steht jeder Ungleichung zerlegt den Gesamtraum in 2 Hälften eine heftiger zum Lösungsraum die andere Hälfte nicht so dass diese Lösung vom schrittweise so ein Kontext das Polygon wird kann von allen Seiten beschränkt sein dass die Bedingungen gerade so im Raum liegen dass sie das der Lösung von allen Seiten beschränkt ist muss aber nicht so wie Sie angedeutet es kann auch durchaus so sein werden die wenn die wenn die normalen Sektoren nicht in alle möglichen Richtungen gehen sondern weniger als 180 Grad insgesamt in einem Bereich weniger von weniger als 180 Grad sind dann öffnet sich das in eine Richtung könnte sich sogar Theorien 2 Richtung öffnen sich vorstellen sie und 2 Bedingungen die parallel zueinander sind und die eine schnelle nach und nach der Moschner der nach oben ab die Punkte hier drinnen das ist die die dritte Zeile hier wir wollen ganzzahlige Lösung haben wir wollen nicht irgendwelche beliebigen nach PLZ wertigen Lösung haben sondern ganzzahlige Lösungen das ist in der Regel in der Praxis das was man will dazu kommen wir dann auch gleich noch im Beispiel und was wir wollen das ist ja wohl nicht einfach nur irgendeine zulässige Lösung finden war schon Ende schwer alleine ist eine zulässige Lösung unter der Bedingung X kleiner gleich B x ganzzahlig zu zu finden sondern wir wollen noch ein Schritt mehr wir wollen eine Linie Zielfunktion das kennen Sie diese Formulierung aus Linien Algebra Fred transponiert X ist selbe wie Summe II gleich 1 bis n C E X X E also C 1 x x 1 plus Z 2 x x 2 plus und so weiter das heißt was sie immer optimieren wollen ist die gewichtete Summe der einzelnen Variablen hatte so das ist zunächst mal noch und ohne Zusammenhang zum Thema indem er bei dem 1. 2 stehen geblieben sind aber der Zusammenhang ich werde darauf dann heute zurückgreifen müssen ich habe seinen Anfang gestellt weil das und suchen durch aus ein bisschen kompliziert und umfangreich ist so
jetzt Versuch ich an die richtige Stelle zu wäre und hat natürlich gleich das falsche erwischt hier nein
das war es ich muss so keine Treffer
müsst ich habe vorher habe ich geschaut ob ich so finde er sagte mir wenn man keine Treffer na gut dann die versuche ich doch irgendwie da hinzukommen ich bin da nicht so weit weg
gelandet keine Ahnung warum man jetzt keine Treffer
sorgt so da wollte ich doch die vor
der mir beim letzten Mal schon gesehen worum geht es bei der ganzen Sache sie erinnern sich wir haben einen warum die nicht wie üblich so Zeichner und die Ecke in die Wurzel repräsentiert die Instanz die sie gegeben ist wir zerlegen Lösungsraum in Gedanken natürlich nicht in echt weil wir den wir sonst von mir gar nicht in echt zur Verfügung haben wir haben ja nicht in der Hand wir zerlegen ihn in dem wir einerseits eine Bedingung einfügen comma zunächst Knoten und andererseits das Komplement diese Bedingung einfügen muss nicht bin sein man kann es natürlich auch man kann natürlich auch 3 oder mehr Bedingungen einfügen die zu die zusammen den gesamten Lösungsraum ergeben also die so komplementär zueinander sind aber im Allgemeinen betrachtet man die wäre mit wäre Zerlegung ist einfacher so und wir würden natürlich ungerne den ganzen Baum durchsuchen müssen wir würden natürlich so oft wie möglich aber wenn wir einen Knoten sind sagen können es lohnt sich nicht den bauen unterhalb dieses Knotens zu durchsuchen es lohnt sich deshalb nicht weil wir von vornherein wissen das entweder das da überhaupt keine zulässige Lösung dran ist dass der Lösungsraum wenn wir diese Bedingungen zu nehmen diese Bedingung für diese kannte und diese erkannte das dann plötzlich die Bedingung über bestimmt werden und die plötzlich eines in deren Lösungsraum haben was wir wirklich erstmal nicht sehen aber den dieses räumlichen handhaben ja dass wir sagen können mehr das ist jetzt das Konzert von Brandt am Bau und wir haben schon mal irgendwo anders eine Lösung gesehen und der wissen definitif was immer es ihren zulässigen Lösung gibt es wird nicht besser sein als die hier die wir schon gesehen haben wir das wissen dann können wir ohne Beschränkung der Allgemeinheit können wir einfach ohne schlechtes Gewissen an dieser Stelle aufhören mit dem weiter runtergehen im Baum und können diesen ganzen Teil Baum abschneiden können ihn ignorieren und der macht schon beim letzten Mal betrachtet wie wir das bei Brand anbauen wissen wir haben eine obere Schranke das ist am Anfang irgendein geeignet gewählter wert aber so wie wir das 1. Mal in unserer tiefen als suche artigen Besucher zu einer Lösung kommen zu einer zulässigen Lösung kommen gibt ist das natürlich eine obere Schranke für den optimalen wird wert einer zulässigen Lösung ist eine obere Schranke für den optimalen wird der Lösung wenn wir bei Minimierungsproblem sind werden von Anfang an gesagt in diesem Abschnitt betrachten wir Minimierungsproblem mehr Maximinus Probleme sind spiegelsymmetrisch es reicht wenn das Minimierungsproblem ansehen so und auf der anderen Seite wenn es uns gelingt für diesen Teil bauen wir eine untere Schranke für die Werte für die Ziele Funktionswerte aller zulässigen Lösungen zu berechnen und wenn wir dann feststellen dass diese untere Schranke das es auf der Folie wenn wir feststellen dass diese untere Schranke für Bahr für alle zulässigen Lösungs Werner für alle zu erziehen Funktionswerte von zulässigen Lösung diesen Teil sind wenn die größer ist als die obere Schranke die wir schon haben dann wissen wir definitif wir können an dieser Stelle Schluss machen mit diesem Teil worden wir können woanders etwas suchen das ist die Grundidee von scheinbar und wie wir sie beim letzten Mal schon betrachtet haben die anderen Fälle hier sind das sind Spezialfälle wie möglich auch betrachten muss wenn untere Schranke haben die plus unendlich ist immer das rauskriegen dann wissen wir dass der gesamte Dateibaum in Sibyll also enthält keine zulässigen Lösungen weil jeder zulässige Lösung hat einen endlichen Funktionswert und wird und der kann nicht größer gleich der untere Schranke plus unendlich sein also wenn wir plus endlich rauskomme bekommen dann ist der Teil Baum erhärtet habe keine zulässige Lösung sein seine Einschränkungen seien die zugehörige Einschränkung des Lösungsraum ist die leere Menge und gut das hat mir schon betrachtet wie wir eine obere Schranke wie in der oben schon umgehen sollen müssen auch schon betrachtet jetzt kommen wir zu diesen unteren Schranken wie kriegen wir das hin für den Knoten VW werden eben auf den letzten Frühling genannt haben eine untere Schranke L von V zu bestimmen die wir testen können gegen die obere Schranke die Uhr zu bestimmen und das haben wir es mal betrachtet das es eine einfache Sache wann immer wir eine Lösung also dass die Lösung besuchen also ein Ende hat in diesen Baum die besser ist als die bisherige gespeicherte obere Schranke dann setzen wir auf den Wert dieser neue gefunden zulässig ist die Grundidee hier ja ist umschrieben mit dem Fachbegriff Relax Sedierung oder Zechen im englischen so worum geht das das haben schon betrachtet Apps wie soll ich dir zurück das habe so ich habe mich schon gewundert warum sie
es nicht mehr Erziehung weitergeht kann oder welchen die falsche Richtung gehen so das ist jetzt alles ziemlich abstrakt kommt ein zurück wir haben und
einige bleiben hier ich hatte beim letzten Mal schon ein Beispiel genannt wenn Sie beim TSB die Bedingung Relax ihren wenn Sie beim Testspiel die Bedingungen Relax zieren das die dass die Rundtour dass es eine Rundtour ist die alle Knoten fast und wenn Sie zu lassen sie Lösungsraum er weiter an um alle Gebilde wie diese das heißt also jeder Knoten ist in einer Untote in aber nicht jeder kann das in der selben unteren dann haben Sie eine Erziehung in diesem Sinne nämlich obigen Sinne sie haben oder in eine hier in diesem Sinne sie habe ich hier von diesen Punkt sie haben die Lösungsraum X durch einen erweiterten vergrößerten Lösungsraum T er ersetzt ja der der weitere lösen sondern hat auch Konfiguration wie diese die man ursprünglich Lösungsraum wichtiges natürlich nicht und sind das ist ja keine Rundtour so das heißt also wenn das ursprüngliche Problem wir wollen eine Zielfunktion minimieren beider Rundtour wissen Sie was diese Funktion ist das ist die Summe der Kanten Gerichte derjenigen kannten den unteren sind bos X ist der Lösung von dass die Menge und Touren relaxiert heißt wir haben zunächst einmal die Kostenfunktion gleich lassen also dieser zweite Fall den betrachten wir noch gleich aber wir haben den Lösungsraum erweitert so wenn wir der entscheidende Punkt ist der darauf dass wenn wir jetzt hier nicht genau betrachten aber der entscheidende Punkt ist der das das diese Problemstellung viel viel einfacher und effizienter zu lösen das ist die ursprüngliche Problemstellung so und weil dass einer der Erziehung ist weil eben die Rundtouren selber ebenfalls im Lösung kommt dann sind es ist doch alles drauf okay weil die rund selber ebenfalls noch in diesem Lösung drin sind aber noch zu sehr viel Lösungen hinzugekommen sind ist das optimale Ergebnis was wir hier raus bekommen können was vermutlich so wies gezeichnet habe dass hier tatsächlich ist ist das untere Schranke für die optimale Rundtour also es kann je nach also ich habe das jetzt hier so Solid passt das zusammen es kann zufällig tatsächlich so sein das eine Rundtour das optimale Ergebniss ist ja wenn die eng beieinander sind die 3 Punkte und wenn die 3 Punkte eine eng beieinander sind ist die und wahrscheinlich das optimale Ergebnis wenn Sie sich aber vorstellen diese kannten wären jetzt jeweils mit Kilometer eine Million Kilometer lang war sein meinen die beiden kannten wären jeweils Million Kilometer lang wäre das wäre so auseinandergetrieben ja dann wird vermutlich dass Sie die optimale Lösung zu einer im Einzelfall kann es passieren dass sie tatsächlich ich hier eine optimale Lösung bekommen oder auch nicht so wissen aber hier noch nicht fertig an dieser Stelle mit der Klärung sie sollte doch etwas vermissen bei dieser Erklärung nämlich wir haben ja noch zusätzliche Bedingungen wir haben hier die Bedingungen zum Beispiel dass irgendeine bestimmte kannte drin sein soll nach links wir können es ja vielleicht vereinbaren allerdings gezeichnet bedeutet die kannte die wir auf dieser Ebene betrachten gehört dazu die 1. kannte die wir betrachten und die immer sprechen bedeutet dieser Feier dieser bekannte gehört nicht dazu zur Lösung so dass wir also den Lösungsraum in 2 Teilmengen partitioniert haben die Linke Teilmenge gehört aber er darin sind alle zulässigen Lösung einer Rundtouren die diese kann enthalten die Rechte Teilmenge alle zulässigen Lösung diese kann nicht enthalten und sie sind schon vielleicht dabei man kann schon ne ganze Menge können abschneiden hier allein schon dadurch dass es keine das ist keine so Touren geben darf wenn wenn die 3 kannten die alle 3 ist drin sein soll eine Soto ergeben bin kann ich an dieser Stelle schon abschneiden weil eine so toll lässt sich natürlich nicht zu einer unter erweitern so dass nun immer gesagt ja meine zweite kannte und wir sagen an dieser Stelle im Baum diese keine dazu und diese Karte gehört nicht dazu das heißt was wir eigentlich haben ist nicht einfach nur die Problemstellung gegeben diese Punkte mit diesen abstellen kann wir wollen eine ein Gebilde wie dieses einen mit möglichst wenig kannten gewichten haben sondern noch ein Schritt weiter die wollen dass eine bestimmte kannte drin ist zum Beispiel weil wir sie gewesen und wir wollen wir noch mal die also eine bestimmte Karte nicht wenn es zum Beispiel Westi gewesen und darauf will ich jetzt nicht hier an dieser Stelle weiter eingehen auch mit dieser Einschränkung dass wir also nicht nur Punkte und ihre Distanzen gegeben haben sondern auch eine Liste davon kannten die drin sein müssen und alles zu können von kann die nicht drin sein dürfen auch mit dieser Einschränkung ist diese Problemstellung hier immer noch sehr effizient lösbaren werden sich vielleicht anders Mertsching Problem wo es wo die Aufgabe daran bestand eine Kantenlänge zu finden so dass jeder Knoten in mit mit maximal einer Kante in Berührung ist das ist die Idee dass es hier mehr eine Variation des Matching Problem nämlich die Forderung dass jeder kannte man jeder Knoten mit genau 2 Kanten in Berührung ist und mit ähnlichen Techniken für das Mischen Problem lässt sich auch diese Problemstellung lösen aber dass es jenseits dieser Vorlesung den anderen Frage warum haben Sie das gemacht wenn ja warum haben wir die Relation so getroffen das wir von Rundtouren zu solchen Gebilden übergegangen sind die wie er als Lösungsraum das haben wir deshalb gemacht weil diese Bedingung das ist alles ist dass alle Klonen einer Rundtour sein sollen diese Bedingung macht uns das Problem extrem komplex extrem kompliziert macht uns richtig bösen Ärger und deshalb macht es Sinn diese Bedingung zu Relax ihren und und dann hier bei jedem Knoten Verbrechen der unteren Schranke mit den einzelnen damit da eine optimale Lösung zu finden es gibt auch den anderen Vereine der es das wenn wir dann noch zu sehen der es dafür dar falls die Problematik die Komplexität der Problemstellung mich in den Bedingungen drin ist die wir beim Übergang zu Relax sie Rungg fallen lassen oder Ver oder oder auf den Aktien sondern die Komplexität kann auch in der Zielfunktion drin sein ja dass die Zielfunktion sehr unübersichtlich ist und dass wir übergehen zu einer C-Funktion die sehr viel einfacher strukturiertes und deshalb sehr viel einfacher behandelbar ist das ist hier nicht der Fall wenn die SPD die Zielfunktion ist einfach das und ich sags mal salopp einfacher geht es eigentlich gar nicht was einfach kann man nicht erwarten dass habe haben wir hier eine C-Funktion nichts gedreht sondern eine Lösungsmenge
so was wissen wir wir wissen das beinerne Verzierung ist die ob er ist der optimale jetzt der Verzierung höchstens so groß ist meine Minimierungsproblem wieder Original optimal das heißt ist eine untere Schranke vielleicht noch nochmal hier dazu zu den hat
beachten Sie hier steht die neue Zielfunktion wenn wir tatsächlich die Komplexität der Zielfunktion haben und diese durch Übergang zu einer einfacheren Zielfunktion er rausschmeißen dann damit das Ganze funktioniert es und schauen geht müssen wir natürlich fordern das wir in eine bestimmte Richtung vereinfachen nämlich so dass die neue Zielfunktion für jedes für jede Lösung für das Element das Lösungsraum höchstens so groß ist wie der alte sie Funktions- hat wenn das der
Fall ist dann ist das auf jeden Fall eine untere Schranke so auch die Problemstellung überhaupt eine zulässige Lösung zu finden ist häufig endlich schwer und wenn die Relax sie Rungg vor einfacher zu lösen ist dann ist es natürlich auch einfacher festzustellen insbesondere ob die ob der ob dieser Lösung zu kommen diese Arbeit an der Lösungsraum wer ist und wenn der auch schon der ist dann ist natürlich der Originale Lösungsraum der Teilmenge davon ist erst recht länger das heißt auch da wenn wir feststellen das ist das was ich hier angedeutet habe wenn Sie hier bei diesen Knoten hingekommen sind dass sie gesagt haben zuerst diese kann 1 die muss drin sein diese Karte 2 muss drin sein diese keine 3 muss drin sein dann wissen Sie der Lösungsraum dieses Knotens hier ist leer denn es gibt keine Möglichkeit diese Menge von 3 ausgewählten könnten zu einer Rundtour also zu sowas zu zu erweitern so noch ein letzter Punkt faltete falls wir zufällig tatsächlich als optimale Lösung so was rauskriegen und nicht so was dann haben wir sogar noch mehr Glück gehabt wenn ich das Glück gehabt dass wir tatsächlich eine untere Schranke in die Hand bekommen haben die greift wo diese Bedingung kleiner L von Frau hat sich erfüllt ist sondern wir haben sogar noch mehr wir haben tatsächlich eine optimale Lösung innerhalb dieses Zeitraums in die Hand bekommen denn wenn eine optimale Lösung der Erziehung zum Ursprungs Problem schuldig Lösungsmenge gehört dann ist sie auch optimal hier so
jetzt kommen wir hier zu und zudem nur womit ich heute angefangen habe eine Möglichkeit sie ändern sich das waren jetzt Matrizen Bedingungen habe ich das noch hier ich habe noch nichts sollte gewünscht sie ändern sich Essen zu der Lösung vom wird beschrieben durch 2 Sätze von Bedingungen der eine Satz steht hier und der zweite Satz ist dass es ganz ehrlich sein soll und diese Bedingung Ganzheitlichkeit macht das Problem sehr viel schwerer das will ich versuchen zu veranschaulicht zu skizzieren warum dieser 2. Satz dieser gerade unscheinbare Satz von Bedingungen hier so in aller Welt Bedingungen ganze Zahlen nicht reale warum das plötzlich die Problemstellung sehr viel komplizierter macht ob das ist noch nicht richtig betroffen so warum sieht das so aus ihrer Sicht an das Bild das wir eben hatten haben vielleicht das zweidimensionales Kurdin Datensystemen aus Gründen hier nicht näher erläutert muss kann ich ihn nicht mehr als 2 Dimensionen anbieten hier und sie haben die Bedingungen die vielleicht tatsächlich von allen Seiten jetzt hier diese Fläche in der Mitte zum Lösungsraum machen der Bedingungen die tatsächlich von allen Seiten Heilbronn Bräumer abschneiden so das so dass einen 1 AND eigentliche beschränktes Polygonen über komplexes Polygon übrig bleibt vielleicht nur wie sie wie könnte man sich das vorstellt im dreidimensionalen mein Lieblingsbeispiel an dem ich mir das immer vorstelle es sieht so aus so so schöner Diamant so also stellen sich vor Sie schleifen einen Edelstein die so wie man das wohl so wie man das kennt dann kommen von allen Seiten so n bisschen mal Facetten abgeschliffen dann kommt im dreidimensionalen das entsprechende aus haben dann müssen halb prangen die sie von allen Seiten abschneiden so das ist ungefähr so an Ich bin ich grundgute an diese sind auszuzeichnen so der Standard Algorithmus also in irgendeine nicht in eine irgendeine Richtung geht jetzt wir haben und eine Richtung gehen dies immer besser wird egal welche zum Beispiel in die das hängt von den Vektor C ab in welche Richtung das geht genau gesagt ist es sogar der Rektor C oder bei minus Problem das negative von 10 so dann können Sie hier schon mal grafisch eine wesentliche Erkenntnis ableiten natürlich jetzt nicht als strenge mathematische Beweis aber es gibt auch wenn man immer schon Beweis dafür dass das Optimum mindestens immer in irgendeine Ecke angenommen wird also wenn wir zum Beispiel die Richtung ist muss immer besser wird wird das Optimum in dieser Ecke angenommen kann auch je nachdem wie der wie WDR Haare wieder tragend liegt kann kann es auch zufällig gerade zu sein wenn der senkrecht zu der versierte ist dass sie die ganze Facette optimal ist aber wir wissen es ist mindestens ein period eine Ecke bei der bei der das Optimum angenommen und so und der Standard also das geht so vor dass er irgendwo anfängt mit und einer Ecke und sich dann von einer Ecke zur benachbarten er gehandelt immer in Richtung besser werden es immer in Richtung da Verbesserung der Lösung also ein ein Algorithmus der ist im Grunde ein lokaler Suchalgorithmus die Nacht meine Nachbarschaft auf den Ecken hier durch erkannte verbunden und sie geht immer in Richtung Verbesserung und man kann beweisen dass sie damit automatisch irgendwann bei der optimalen Ecke ankommen genauso hier wenn sie Pech haben fangen sie genau in der verkehrten Seite an so dass er so lange Weg haben Dienst in einem benachbarten Ecke 10 am benachbarten benachbarten benachbarten und man kann auch beweisen egal wie wenn sie nur immer in Richtung Verbesserung geben dann kommen sie irgendwann zu optimalen Ecke das funktioniert aber nur solange sie nicht der Ganzheitlichkeit noch als als bedenkt dabei haben dann können Sie so schön so mit diesem Algorithmus der nennt sich Simplex Algorithmus schreibe ich vielleicht mal dazu falls weiter interessiert in der Mathematik gibt es Lehrveranstaltungen die solche diese Thematik vertiefendes machen jetzt Informatik nicht und wenn Sie aber ganz Traurigkeit haben dann haben und dann muss da muss die Lösung einer der Punkte von diesem ganzzahlig ganz geht sein nicht und damit im Allgemeinen nicht meine Ecke so ist könnte man natürlich sagen ist doch kein Problem wir gehen zur nächsten Ecke und könnten uns da an was ist also in der Nähe einen ganzzahligen Lösungen kein Problem eine von den wird schon die optimale ganzer Lösung sein aber ganz so einfach ist es nicht wenn sich beispielsweise Folgendes vorstellen dass ich eine sehr vielleicht noch exzentrischer das Sie hier wo es optimal wird dass Sie hier eine sehr spitz zulaufende Ecke haben und alles was in der Nachbarschaft an ganzzahligen Lösungen ist ist erst einmal nicht zu trennen die nächste Reise vielleicht auch nicht drin und sie stellen sich vor Sie haben es nicht gerade sehr nützlich zweidimensional sollen sie im n-dimensionalen das heißt also Sie haben nicht 2 Quadrat Punkte darum herum sondern 2 hoch Endpunkte darum rum und entsprechend immer mehr und hier unten irgendwo ist die 1. die 1. ganzzahlige Lösung die die in im Lösungsraum drin ist dann sehen Sie schon die werden das ist nicht so einfach ja also einfach die optimale nicht ganz Lösung dieser Ecke zu finden dann in der Umgebung um zu suchen ist ein guter Lösungsansatz würde häufig gemacht funktioniert aber nicht immer bei schlecht gestellten Problem wie hier wo die wo die wo die einzelnen dar wo die einzelnen Bedingungen sehr nah beieinander liegen also sehr fast parallel zueinander sind er funktioniert nicht mehr gut so aber für uns hier ausreichend wenn die Problemstellung eine einen ihrer B ist dann können wir zur LP Relation Relaxation übergehen ich mal hier gemäß RP Relaxation übergehen indem wir die Ganzheitlichkeit Bedingungen fallen lassen das gibt uns die eine andere Sicherung die das heißt also wenn wir die lösen sich das skizziert habe mit dem Simplex Algorithmus von Ecke zu Ecke haben das gibt es eine Lösung die mit Sicherheit eine untere Schranke ist für die ursprüngliche Problemstellung denn wir haben den Lösungsraum erweitert indem wir übergegangen sind von ganzzahligen Lösungen auf beliebiger reellwertige Lösung
so 1 das Beispiel hatten wir sie sind jetzt hier noch mal der habe ich das jetzt gelöscht Ja ich meist noch mal auf das ist genau das was wir eben betrachtet hatten sie ernähren sich die SPD so wenn das weit genug weg ist ist das sicherlich die optimale Lösung chronischen und die Rundtour und die beste Runde drauf es wahrscheinlich nicht mehr die optimale Lösung ich muss mir angewöhnt nicht jedes Mal wenn ich hierher komme die die die ganzen Kreide hier rüber zu bringen so was dann übrig bleibt sie sehen plötzlich das lässt sich tatsächlich als einen ILP schreiben wir minimieren die Kosten für jede Kante haben wir eine 0 1 Viktor was heißt 0 1 das heißt X E ist kleiner gleich 1 wie Jahre Bedingung in der Ungleichung X E ist größer gleich 0 7 Jahre Ungleichung und x die ist Element Auszeit das alles 3 zusammen ist äquivalent so XII ist aus 0 1 ja das heißt also Zusagen XII ist es aus 0 1 Essig das ist eine ist er das ist Teil eines eines ihre P und die Bedienung das wir so ein Gebilde haben lässt sich sehr einfach ausdrücken was bedeutet dass nämlich das bedeutet dass jeder einzelne Knoten genau in sie den zu 2 exakt 2 Kanten ist wenn Sie diese Forderung haben die sie da sehen für jede einzelne für jeden Knoten solle die sollen die die XR die der kannten ja das vielleicht noch nicht ganz genau gesagt XII gleich 1 bedeutet natürlich die kann das drehen und XL gleich 0 bedeutet die kann das nicht retten so werden Sie jetzt die wenn Sie jetzt diese Semantik haben XE bedeutet die Kante ist eine Lösung x x X L gleich 1 ist er gleich 0 würde die kann es nicht trennen dann lässt sich die Kosten für auf wartet die Kosten einer solchen eines solchen Gebildes einfach durch Aufsummierung der einzelnen er kannten kosten von den kannten die drin sind wir und das ist ganz einfach sie ist er wir gegenüber über alle kannten und wenn eine Karte drin ist dann steht hier eine 1 das heißt deren Kosten werden mit komme mit die Summe rein und wenn eine Karte nicht findest dann steht ja 1 0 das heißt die Kosten dieser kann bekomme ich ein was im Endeffekt hier oben haben ist die Summe der Kosten aller könnten die Inder und enthalten sind so jetzt müssen sie dann das 1. jetzt müsse nun dafür sorgen dass diese 0 1 Werte für X E tatsächlich ein solches Gebilde ergeben O und sehr geben ein solches Gebilde durch diese Forderung für jeden Knoten soll gelten die Inzidenzen kannten wir summieren hier über alles zu diesem Knoten in siedendem kannten auf denen sie kannten die sind dienen kann die zu diesem Clooney sind dann sind deren x-Werte sollen sonst im Sommer 2 sein die x-Werte sind aber alles 0 1 Werte wie kann es sein dass eine Summe von Einzelheiten wieder den der 2 hat das kann nur dadurch sein dass genau 2 dieser x-Werte den wird einsam und alle anderen 0 mit anderen Worten das genau 2 Kanten die Inzidenz zu diesem Knoten sind aber in in der in diesem Gebiet enthalten sind uns und die anderen nicht und das geht wie gesagt in sehr schneller Zeit das ist sie sehen ich hier ein erstes Beispiel dafür die nach der ihre P als Sprache ist nämlich dass man solche Dinge einfach mal so scheinen schnell als Bedingung hinschreiben kann das ist der Grund warum wir uns in einer gewissen Modellierung so intensiv damit befassen weil auf der einen Seite sehr gut löse dafür gibt es auf der anderen Seite ist diese Sprache so mächtig dass diverse Problemstellung die betrachtet habe man die alle Problem stellen die wir betrachtet haben sich in guter Form in dieser Sprache schreiben lassen und damit für die mit diesem Versagen gelöst werden können so nah an
das Beispiel SPD was ist ein 1 Baum dass auch eine Platzierung von rund und sie haben weder die Knoop Gluten Menge gegeben die Punkte in der Ebene zum Beispiel müssen keine Punkte der Ebene sein können irgendwelche abstrakten Gebilde sein das haben wir ja gesprochen gehabt so gut das wäre in unserem Standardbeispiel was es immer benutzt haben die optimale Rundtour wahrscheinlich unten eines bauen das ist etwas das sie wissen was ein Baum ist im Sinne ungerichteten im Sinne von minimal sparen aber auch das ist eine ungerichtete also im Lichte der Graf des zusammenhängt und den keine Züge ja sich dunkel an dann ist die Muße G 2 1 1 Baum ist im Prinzip ein Baum der noch eine Kante mehr enthält so dass ich genau Einzüge schließt also zusammenhängt und enthält genau einen Züge das wäre beispielsweise hier könnte könnte der Züge so aus sehen und hier haben wenn wir uns ein bisschen länger machen wenn man müssen weiter weg treiben so hier ist der nächste das ist wahrscheinlich das hier der optimale 1 bauen ja wir zählen wieder die die die Kanten Gewichte auf kann Gewicht auf der Einfachheit halber die euklidischen wenn wir eine Tafel wohnt und da sie sehen das Relax Führung der die ursprüngliche Rundtour war wie jede Rundtour ist offensichtlich ein eines bauen männlichen 1 Baum Wunderlichs nix weiter dranhängt begann das vielleicht noch ein bisschen ein bisschen erweitern damit das noch mal klarer wird das nicht nur eine Sache der dranhängen muss sondern es kann zum Beispiel auch sein dass hier noch das hier noch was dranhängen so das würde dann hier aus sehen es könnte so aussehen weiterhin so und dann so wie wir das optimale wahrscheinlich so auch oder nicht optimal wäre es wahrscheinlich so so es Hamas Beispiel müssen um diese gemacht damit Sie sehen dass das nicht an einer Stelle der da irgendwas dran hängen was keiner was keine Züge enthält sondern durch das an verschiedenen Stellen da beliebige Verästelungen geben kann so jeder Rundtour das ist ein 1 Baum nämlich dann wenn hier nichts weiter dranhängen sondern alles in Züge enthalten ist alle Knoten aber nicht jeder eines Baumes eine unter das heißt wir haben eine Vereinfachung vermeine Relation Entschuldigung und wir werden das später in dem anderen Thema genau betrachten sondern hier auch nie wieder vorhersagen diese Rechte Problemstellung einen optimalen 1 Bonn zu finden es ist viel viel einfacher zu lösen als die Linke Problemstellung auch dann wieder sehr in sich wenn wir eine Liste der von Kanten haben wo wo vorgegeben ist die muss drin sein die muss drin sein die muss drin sein und wo wir eine weitere Steak von Kanten haben vorgegeben die darf nicht drin sein die darf nicht drin sein die darf nicht drin sein auch daran ist diese Problemstellung immer noch sehr effizient lösbar das werden wir aber später genau betrachten wenn wir zu den Lösungs dafür kommen wie kann man das lösen kann so jetzt sind wir weiterhin in der Welt der ja Dell in der linear und Algebra comma zu einem sehr sehr wichtigen Thema was ein bisschen wird eines der Arbeitssphäre beispielsweise auch in der nicht ganzzahligen Optimierung ist also im technischen Bereich wenn sie typischerweise mit reellwertige Kenngrößen zu tun haben und nicht unbedingt mit mit ganzzahligen Kenngrößen ja wenn Sie irgendwelche Eigenschaften an einem Bauteile beispielsweise optimieren wollen wir Wärme Koeffizienten oder was auch ich immer nur als ein einfaches Beispiel für viele viele ingenieursmäßig Anwendungen so wir haben es etwas andere Situation als Ausgangspunkt macht aber nix das ist das alles egal sein zueinander wir minimieren wieder eine länger als sie Funktionen über einen längeren Gleichungssystemen wir gleich ist immer länger und leiden System ist vollkommen wurscht ja jedes Jahr Gleichungssystemen besteht natürlich aus verlieren und Gleichungssystem bei jede Gleichung oder ein doppelt so großes sehr und welches immer sehr jede gleichen durch 2 Ungleichung einsetzen können X kleiner gleich y Exkurse welche y ergibt zusammen x gleich y und umgekehrt können Sie wir können sie auch liegen Jahre Ungleichung System in der Gleichungssysteme überführen in dem Sinne eine zu sätzliche Dummy variable jeweils führen den Unterschied von kleiner gleich auf gleich aufnimmt aber gut wir haben so eine Situation wir haben irgendwelche Dinge Angleichungen sie sich zum Beispiel
hier hat mir solche Dinge Angleichungen das ein Beispiel für die Gleichungen in seinem Kontext Optimierung und wir haben noch welche
weiteren Bedingungen zumal das unter sein soll zum Beispiel TSB mit zusätzlichen ihren Gleichung die von der Lösung darf von jedem der Mindestlohn Songs erfüllt sein müssen so ist kann man das Lösungswort wäre denkbar so was ist jetzt die Idee die wir ja die Idee ist wir schmeißen diese Bedingungen raus ja also wir
hätten jetzt hier beispielsweise diese Bedingungen rausgeschmissen wenn wir bei dem Beispiel bleiben
aber nicht ersatzlos so wie bisher ist bisher aber Bedingungen als der Fluss rausgeschmissen oder nicht ersatzlos rausgeschmissen sondern sondern relaxiert von hier nach hier aus dieser Bedingung einer zu haben wäre wenn auch komplizierte aussehende Bedienung gemacht sondern wir nehmen diese wird die bedienen die wir weggeschmissen haben raus und aus dem bedingt Satz und packten sie auf geeignete und Weise die Zielfunktion so was passiert hier also Sie sehen einen Namen morsch das ist nur relativ alt und relativ wichtige Sache ist es denn vielleicht in einer ist ist in der Mathematik schon mal begegnet der normaler Labor schlanker Bursche Multiplikatoren ja vielleicht im Zusammenhang mit dem Satz über implizite Funktionen versehen das Art seit dem Gesetz die Funktion was bitte und da nicht ist jetzt hier diesen konnte es auch nicht so wichtig also falls es sie ihn interessiert der Satz über implizite Funktionen gesagt wenn Sie eine Funktion haben in X und Y zum Beispiel sowas und die ist in jedem und Sie können die nicht auflösen nach dem y noch x weil sie zum Beispiel so und eine Kurve beschreibt ja denken Sie wieder nach X nochmal y auflösen 4 X und hier y ist er Sieg an diesen Stellen des Problemen auflösen nach y und an diesen Stellen vor dem auch nach X aber der Satz besagt wenn sie an irgend einer Stelle Differenzierbarkeit haben dann können Sie zum Beispiel sowas für Xtra plus y Vollrads gleich er die Kleist Kreis Gleichung dann können Sie einfach da differenzieren wie sie das immer gewöhnt sind nach Ex- und nur y ohne dass dies erst nach ist nach dem anderen auflösen müssen das besagte Satz über implizite Funktion sie dürfen auch dann differenzieren wenn Druck wenn Sie gar nicht wenn sie es gar nicht also Funktion ausdrücken können von einer variabel in die anderen war ab und in dem Zusammenhang falls die so ihn doch noch mal und da kommt oder falls falls sich darinnen das vielleicht doch oder Mathematik vorkommen können weiß ich jetzt nicht aber in dem Zusammenhang führt man auch in einer dieses typischerweise Landmarsch Multiplikatoren 1 weil ich weil Aussagen darüber auf dem Satz über implizite Funktionen beruhen gut aber das ist jetzt alles für uns hier und nicht weiter wesentlich das war nur ein kurzer Exkurs das ist jetzt die die neue Zielfunktion was wir hier stehen haben ich glaube es muss noch mal auseinanderfallen über das kann ich mich mal ändern bei einer Professur nur in Mathematik durch Abos Kommission war weiß Vorgabe eine Lehrprobe Viertelstunde didaktische Aufbereitung Einführung den in den Satz über implizite Funktionen und ich sage nur dazu wenn sie den Satz lesen in einem einmal dieses Buch ist dass sie das ganz anders aus als wie ich das jetzt hier versucht habe aufzubereiten also allein der Satz in dem Buch nachdem ich damals alles gelernt habe allein die Formulierung des Satzes danach hat man dann halbe Seite 1 also durch das ein gutes Thema um die die didaktischen Qualitäten eines Dozenten mal zu überprüfen vor also ursprünglich steht CTX gleich C 1 x 1 plus C 2 x 2 bloß und CMX vielleicht nochmal kurz zusammengefasst eh gleich 1 bis n für die XI so jetzt steht da was komplizierteres wenn ich das nehme CTX plus im Rahmen der transponiert aber X minus B ja es muss ich mal nachdenken ich glaube hier ist eine
und Geschicklichkeit in der vorher hier sollte nicht A X gleich B stehen sondern hier sollte tatsächlich Aix kleiner gleich B stehen auf dieser Folie hier sonst macht das nämlich weitere was ich jetzt hier sei die keinen Sinn tut mir leid ich bin ich in jeder die volle verzapft hat aber ich bin natürlich verantwortlich für die vorher wenn ich sie hier präsentieren so dann haben wir hier weiterhin dass das kürzlich mal ab CTX Plus was steht jetzt hier ich hoffe dass ich das jetzt hinkriege wir haben wir 1 x so mehr Joads gleich 1 oder E nämlich wieder E I gleich 1 bis Ende ja 1 Jordt X hier Ort minus B A 1 ja das ist die aber sie immer steht ist wir haben da I X war I 1 dieser Vektor A M E N x 1 bis x allen diese Zeilen der Matrix multipliziert mit diesem weckt er und das Ganze noch natürlich ich hiermit der recht die rechte Seite davon weggenommen halt ich habe er jetzt eh genommen dann soll ich zum zu Unterscheidung hier das nicht dass er ist ein J hinschreiben so also das Plus das selbe noch mal für 2 Summe die gleich 1 bis 1 aber es war Idee X X E minus B 2 und so weiter bis wir das Ganze nochmal bei lahmen dar haben mal Summe eh gleich 1 bis n E X X die wieder spielen die so was bedeutet das die lange dauerte steht jetzt hier nicht direkt da ist aber trotzdem so die Lander werde sind alle größer 0 keine negativen Werte größer gleich 0 aber gleich noch macht es könne weniger sind so wenn das die Bedingung ist dass das X dass die er alt ich habe ihren Fehler gemacht haben so müssen die Klammern gesetzt sein so und hier auch so wenn Sie auch finden können habe ich das verstehe macht man so ist das richtig so was bedeutet das jetzt hier das bedeutet wenn das Land der zwar größer 0 ist wenn man dieser wird hier auch größer 0 ist dann wird dann wird es bestraft ja wenn ich hier Summe I gleich 1 bis n 2 E X X die minus B 2 wenn das größer 0 ist wenn also hier Verletzung ist dann bedeutet das dieser ganze Thomas positiv positiver Thermen auf der Zielfunktion beim Minimieren bedeute Bestrafung ja sie sich dunkel sowas hatten wir schon mal dieses Muster im anderen Kontext bei Nachbarschafts basiert Suche das wir das wieder zu lassen das Bedingungen verletzt werden indem man sie einfach rausnehmen aus dem aus dem Satz den Bedingungen darum aber wir bestrafen sie wir wir sitzen wir erweitern die Zielfunktion um einen Teller der ja das in der Art der positiv ist also bestrafen ist wenn wenn dieser wenn diese Bedingung verletzt wird ja wenn wir die bedienen überfüllen Verbesserung wir uns da dabei an dieser Stelle dann das müssen wir dann mit in Kauf nehmen wir sind jetzt nicht mehr dabei an dieser Stelle das Problem wies gegeben ist zu lösen sondern sondern unter Schranken zu generieren da müssen wir hin und wieder auch mal Kompromisse schließen haben Sie voll und ganz recht
so die Behauptung bis jetzt
egal wie wir die die
Multiplikatoren jetzt definieren dass das ganze dann tatsächlich in dem Sinne Relax ist und hier sehen wir wollen wieder seit langer Zeit das böse Wort Beweise das leider so war hier verschont geblieben dieser Veranstaltung von Word beweist jetzt droht uns das wieder ein die Behauptung ist das ist egal wie wir den Vektor wählen ist
das eine sind das ist das eine ja es ist in einer Galaxie
und das passiert jetzt tatsächlich auf der Formulierung AX gleich bin ich als kleiner gleich B aber
letztendlich Funktion mit gleich B wahrscheinlich auch
so wie hier gehörst nochmal durch so für den Sektor lahmender egal was wir einsetzen wobei nicht mal positiv formuliert nicht mal positiv verlangt wird für den Viktor Lander Geld ja egal für welchen Namen da egal für wie egal was der Islam einsetzen denn auch hier halten einander fest so es die Ursprünge Zielfunktion minimiere C unter der Bedingung dass als gleich B ist und X ansonsten aus und es so dass er sich hier
das war diese Formulierung zum Beispiel denken sich groß X ist die Menge aller Rundtouren auf allen Punkten und Eis gleich Besen Zusatzbedingungen die runter zu erfüllen hat damit sie noch zulässig ist und vi minimieren wieder die Summe der Kanten Gewichte in der Rundtour so dass sie
ursprünglich her Definition wenn Sie jetzt hier rechts schauen das ist die neue Ziele Funktionen und der alte der ursprüngliche Satz von Bedingungen so wenn Alex gleich B gilt dann ist dieser Ausdruck ihren 0 egal wie viel rasche Multiplikatoren anderer definiert sind das heißt also was hier entsteht ist identisch mit dem was in den steht das selbe Minimum weil dieser Ausdruck 0 ist so das heißt der 1. Schritt ist wegen vom Ost- und Problemen zu einem neuen Problemstellungen wurden auch dieselben Bedingungen da sind die Bedingungen die immer im Hinterkopf eine Rundtour beispielsweise konstituieren plus den zusätzlichen länger an den Bedingungen betrachten aber schon die neue Zielfunktion wir stellen fest dass diese neueste Funktion auf dem ursprünglichen Lösungsmenge gleich der alten sie Funktion ist bei dieser zusätzliche so hier 0 ist weil das Eixen W gleich 0 ist wenn als gleich viel ist und jetzt gehen wir noch den den zweiten Schritt weiter wir lassen diese Bedingungen als leicht gefallen und wenn wir belegen fallen lassen das eine sehr so so wie bisher waren wir Bedingungen fallen lassen dann kann das nicht zu einer Vergrößerung der Ziele Funktionswerte führen sondern nur zu einer Verminderung damit ergibt sich egal wie die Lander Werte sind eine untere Schranke für die zulässige Lösung das Ausgangspunkt ist noch mal vielleicht ganz kurz ich habe jetzt ein bis ich Konfusion reingebracht gebe ich offen zu ich kenne es eigentlich eher in dieser Variante als kleiner gleich B wo man diese schöne Interpretation hat dass man dann bestraft es funktioniert aber auch in der Variante A X gleich B und hat offenbar den
Vorteil dass der Beweis einfacher geht gut das heißt also in der Vorbereitung auf die Prüfung nehmen Sie das was ich hier gesagt habe Herr als Idee die dahinter steckt Bestrafung von Abweichungen von von den Nebenbedingungen und nehmen Sie eher das hier diese Variation her und um das und das pure Problem und und um um ist es thematisch zu betrachten so was bedeutet das
jetzt wir wollen natürlich eine möglichst gute untere Schranke haben ja gehen noch mal ganz zurück einen Anfang muss ich allerdings jetzt wieder Platz schaffen dafür wir wollen Teil Bäume scheint es immer noch beim Thema Bahnen und immer noch den großen Baum sind jetzt hier irgendwo bei irgend einem Knoten angekommen und über und wollen nach Möglichkeit diesen Teil um abschneiden und was machen wir hier und wir wollen wir können abschneiden das ist der Knoten V im Baum wir können abschalten wenn die untere Schranke von V größer als im aktuellen der O-Ton Ober Schranke auf der optimalen Lösung drauf ist das bedeutet natürlich wir wollen die Sie hier möglich ist möglichst hoch haben wir wollen diesen wir wollen diesen wird so haben dass er möglichst hoch ist gleich möglich ist ja einen am optimalen wert mit dem Tannenbaum das in den Sachen die wir bisher betrachtet haben geht das nicht so richtig Ja der optimale eines Baumes hatte optimal 1 fertig oder die optimale das optimale Gebilde was aus mehr einen des jungen kann so tun besteht es eben das optimale Gebilde aus mehreren des sowieso schon fertig aber hier wir haben eine andere Situation wir haben
werte die lahmende aus die wir freisetzen können ist davon aber nicht darüber gesprochen wie wir diese Landes eigentlich setzen wir
wollen die natürlich so setzen da kommt jetzt hinzu so setzen dass die untere Schranke die daraus generieren dass wir das machen was auf der letzten Folie drauf stand hier die wir daraus generieren dass wir
diese Problemstellung durch diese ersetzen also genau gesagt am Ende durch diese Problemstellung wir unten dass dieser wie lange das so setzen dass dieser werde hier rauskomme dieses Minimum möglichst nah an den ursprünglichen Minimum dran ist Dame völlige Handlungsfreiheit des Landes können wir die einzelnen das können wir ja beliebig also den Zahlen werden völlige Handlungsfreiheit Sie wissen das am Regal mit Zahnpasta oder am im Supermarkt für die Handlungsfreiheit macht die Sache nicht unbedingt einfacher aber in diesem Fall schon
nämlich er mit Methoden aus der Numerischen Mathematik die numerische Mathematik haben sie ansatzweise in der Matte 3 heißt es glaube ich kennen gelernt die die von den die Informatik studieren die die man nicht Informatik okay alle die hier im Raum sind Studierende der Informatik oder Orten sich nicht ich immer nur an sich Informatik also Matte 3 und mit diesen Methoden die sie da vielleicht weil sie nicht kennen gelernt haben er kann lösen das ist wieder ein Beispiel für lokale Suche das schöne an der Sache ist das man kann zeigen dass diese Problemstellung 4
eine sehr schöne Struktur hat fast so schön wie die Strukturen die wir am Anfang bei lokaler Suche hier einer Tafel hatten fast so schön sehr an sich wir hatten bei lokaler Suche immer so sowohl diesen Fall gehabt einer konvexen differenzierbaren Funktion wer sich bestehen irgendwo vielleicht an dieser Stelle und wenn wir wissen dass die Funktion konvex ist dann gucken den gravierenden an also stellen sich das vor wir sind jetzt nicht im zweidimensionalen sondern dieser Brauch komm doch raus im vor der Tafel und Ende der Tafel das er wenigstens 3 Dimensionen zu üben und wenn ich hier den gravierenden des den oder den das negative vom Varianten die Richtung gestalten Abstiegs hier Schritt weitergehen und hier wieder Schritt weitergehen und so weiter wenn wir da vorsichtig genug sind nicht allzu hohe Schritt Schrittweiten zu machen dann kommen wir automatisch ob wir wollen oder nicht wir wollen natürlich aber wir wollen nicht willkommen bei der optimale Lösung oder sehr nach einer optimalen Lösung aus hier wenn es darum geht dieser das Rauschen
Multiplikatoren zu optimieren sieht
die Funktionen bisschen anders aus sie ist nicht so schön differenzierbar aber stückweise differenzierbar so was müssen sich jetzt also wir das müssen schwierig dass ich in 3-D vorzustellen denken Sie wieder an diese vielleicht an diesem Diamanten oder so etwas und denke stellen sich vor es gibt oder schauen Sie im Internet nach es gibt es gibt Edelsteine die so geschliffen sind dass sie wirklich aus vielen vielen vielen kleinen Facetten und wir stehen das gibt die dann vielleicht eine Wiese wie man so sich sowas vorstellen kann sondern Erziehung nur stehen dann haben Sie an dieser Stelle einen gravierenden können die Richtung gehen wenn sie an dieser Stelle gehen dann ist es war nicht der Fernseher war es ist in jeder Richtung differenzierbar das sind jetzt im 2 dem sollen nur 2 Richtungen in 3 Dinge so hochdimensionalen sind dann noch mehr sie können sie haben keine gravierenden mehr sondern das wird nennt man so gravierend ändern Sie haben sie haben in jeder Richtung die Möglichkeit zu differenzieren 1 eine Einrichtung des Abstiegs zu finden oder des Aufstiegs und können dann unter diesen auch auswählen wo es langgeht da muss muss am steilsten runter geht er also fast das die dieselbe schöne Situation wie wir sie hier prototypisch für lokale Suche hatten und damit auch wieder ganz gut handhabbar
das hat sich deshalb so gerade ihren Optimierung also keinen Begriff gravierend aus der Mathematik das ist bei einer mehr dem seine Funktion die Richtung Gesteins an ein wenn sie deren sie aber ist die Rede also eigentlich bei Minimierung immer vom negativen es gravierenden und so gravierend wenn es werden wenn wenn an einer Stelle die Funktion nicht differenzierbar ist sowie an die an diesen Stellen hier sie ist aber in jeder Richtung so abgesprochen differenzierbar dann haben sie in jeder Richtung 1 also dann dann haben sie einen so gravierenden er setzt er sich nun in der Frage der Terminologie das betrachten nicht weiter da verweise ich sie auf Mathematik Veranstaltungüber über Optimierung der wird das lang und breit ausgeführt so nimmer wieder kommen immer wieder zu Standardbeispiel es ist einfach ein wunderbares Beispiel um alles mögliche zu erklären so TSP ja wahnsinnig wir haben für jede einzelne kannte die Inder und sein könnte 1 0 1 Wert 1 0 1 Variable der schon geklärt dass das ins Modell reinpasst für für für ganze Jahr Programmierung weit Element aus 0 1 gleichbedeutend ist mit XE kleinere größer gleich 0 gleich 1 und XI ganzzahlig so und die Semantik war X gleich 1 bedeutet dass die kann der IE ist in der Rundtour drinnen ist in gleichen wird ist nicht drin haben wir auch schon geklärt dass hier also dann mit dieser Semantik der Variablen Werte E wir was hier ausgehöhlt wird ist die Summe derjenigen kannten die Kosten derjenigen kannten Diener unter drin sind war bei den in Eichstätt zu dass die C 1 kommt die Sonne und bei den einer Schäden nur ist sie nicht rein so sie können zum Beispiel ist das ist nur eine von vielen Möglichkeiten wie Sie das TSB als ganzheitlich Lierhaus Optimierungsproblem formulieren können wir haben jetzt das hier kennen Sie schon diese Bedingung kennen Sie schon nämlich das zu jeder das jeder Knoten zu genau 2 kann genau und wollen Sie denn dass das eine heute schon mal gesprochen die billigen hier unten haben auch schon geklärt hier steht noch drin die Bedingung dass wir genau n kannten haben wollen wobei ich glaube diese Bedingung ist eigentlich Redundanz die ist durch diese Bedingung schon ausreichend erzwungen also wenn diese Bedingung erfüllt ist wenn jede ihrer können so 2 kann Incident ist kann es gar nicht anders sein als das genau solche Gebilde rauskommen wie wir sie hier haben und dann ist auch automatisch 7 Knoten 7 könnten ist auch automatisch die Anzahl der Kanten die 1 und dort in diesem gebildeteren sind gleich der Anzahl der Knoten also wenn ich jetzt spontan nichts Falsches ich hier sehe dass die bedienen 3 eigentlich überflüssig da redundant also sie ist automatisch durch die Bedingungen 2 erfüllt so aber wir wollen dieses Gebilde eben nicht drin haben so ein Gebilde und dann Sommer noch zu zusätzliche Bedingung die dafür sorgen das solche Gebilde nicht ganz ernst so was steht jetzt und das sind diese Bewegung Nummer 1 die von den sagte das sind die das sind die komplizierten lassen die ärgerlichen Bedingungen so war steht jetzt hier hier steht drin erst einmal was ist die so groß ist groß ist ist vielleicht sollte man das mal auch illustrieren was wir hier und lesen muss es verstehen sie haben dann die SPD eine Menge von alle meinten die sie verbinden wollen diese nacheinander einer besuchen wollen können period in der Ebene seien Sie natürlich immer an der Taufe period in der Ebene müssen aber nicht so Sie haben jetzt einen Knoten hier der in der Reihenfolge der Quoten die Nummer 1 trägt und dieses es ist jetzt zum Beispiel könnte man das so bezeichnen das hier auf dieser Seite der Trennlinie das es steht es ist dicht mehr das heißt auf dieser Seite der Trennlinien müssen Fluten seien Sie doch welche 1 2 3 4 5 sind sogar und die Arme belebend 1 nicht Element aus es besagt dass auch das Kompliment also 1 aus es kommt der Demenz besagt dass auch es Komplement nicht mehr als ein muss nicht selber über sein darf
weil die 1 drin ist das ist das Komplement mit diesen 4 Knoten das heißt also dieses S mit diesem erst durch glauben wir das ist ein Satz von Bedingungen für jede Menge S die auf diese Art und Weise die Gesamtquote Mengen Teile Partition 2 nicht leere Teile partitioniert für jede dieser Menge es haben wir eine Bedingung drin und was hat jetzt diese Menge diese Bedingung S sie besagt was ist denn das hier wir gegenüber kannten wir summieren kannten diese man aber nicht über irgendwelche kann sondern wieso man über kannten die hier drin sind so über solche Kanten wie sich hier beispielhaft angedeutet habe noch mehr könnten ich habe sich alle kannten sein über die Kanten dieser Knoten NS-Mann danach verbinden hier sehen Sie unten I J Element aus das und diese Summe soll kleiner gleich ist Betrag was bedeutet das ich zeichne jetzt mal damit es besser sie besser klar hat sich gehört ich jetzt mal anders S ich zeige es vielleicht anders ob was mir wichtig zu zeigen dass dieses es jetzt nicht einfach einfach strukturiert rechts und links das habe habe ich hier noch so klinge gemalt aber jetzt wird es geht einfacher zu zeichnen oder Illustrativer wenn ich es doch so ein bisschen so Zeichner weil was das bedeutet ist das rufen wir auch das zum Beispiel so war es nicht erlaubt ist deren Betrag von S ist gleich 1 2 3 4 5 6 7 Anzahl der Kanten in diesem Gebilde hier die wir zugenommen haben zur Lösung 1 2 3 4 5 6 7 was unter ist und genau das wird durch diese Viren Nebenbedingungen ich diese Ungleichung ihrer verbotenen genau das das 7 SIM-Karten in dieser 7 in diesem Sinne man den erst dran sind und wenn keiner sehen können und sein dürfen dann heißt das das kann nicht sein das kann nicht passieren und das das über alle es machen dann heißt es ist kann keiner so Tour im Grab in der im Endergebnis ein jeder einzelne so Tour jeder einzelne so Picture die wir wir haben können wir induziert ein solches S und dann greife die Bedingungen sehr eine Frage ach so gute guter Hinweis diese dritte Bedingung hier meinen also Ihre Frage ist oder ich war ich wiederhole immer die Fragen weil weil sie nicht weil sie nicht ins Mikro Euro keine sprechen also die Frage ist ob diese dritte belegen nicht doch notwendig ist wenn endlich den Grafen betrachten dass wir da nicht plötzlich 2 2 Kindern eigene Züge haben ja da würde man das ist sicherlich so irgendwie sowas in die Richtung brauchen aber Sie sehen ja dass es ist hier alles und Gerichte formuliert ist nicht hundertprozentig auch allgemein formuliert hier denn Sie können ja sie können ja durchaus unterschiedliche Längen haben ja in der anderen Richtung und dann muss man das sicherlich etwas tun wir gewinnen würden ganz recht aber ich glaube hier in dieser absolut ungerichteten Sichtweise wo sie eben auch nicht immer die Möglichkeit mehr haben das ist das 2 Objekte in Einrichtungen andere Distanz haben als in anderen Richtung also einmal geht's bergauf einmal geht's bergab kostet länger Zeit kostet weniger Zeit oder so etwas da bin die habe ich dachte es trotzdem immer noch das Gefühl ich habe ich habe noch nicht gesehen warum die dritte Bedingung ich rede und ist aber sie wissen auf jeden Fall wichtiger Hinweis wenn wir über wenn wir das ganze gerichtet aufziehen könnte man natürlich auch hier machen wir da ein bisschen komplizierter dann sollte man sich noch mal überlegen ob die dritte bedienen nicht doch wichtig ist so Arbeit entscheidend ist jetzt 4 ff für das was wir jetzt sehen diese Bedingungen hier das ist genau die Bedingungen die dafür oder der Satz vor mit dem der dafür sorgt das ist keine Rundtouren gibt die nicht die 1 enthalten ja weil für jede Rundtour die nicht die 1 sind halt könnt ich so habe ich also eine S gut ist wenn man fragen was ist mit mir zu touren die die 1 enthalten ja wenn es eine Suppe gibt die 1 enthält die zum ohne weitere Sutor die die 1 nicht enthält und habe ich wieder meine ist ja wenn sie eine so Tour haben wieder mein Standardbeispiel was die Einsamkeit und das ist keine und das keine zulässige Lösung des TSP dann gibt es auch nur 2. Oktober die die 1 nicht enthält und dann können hier diese verknoten als 1. an so jetzt sehen Sie noch mal ein schönes Beispiel dafür wie mächtig ILP als Sprache ist um Optimierungsprobleme auszudrücken wie gesagt das vertiefen Werner kurdische Modellierung ist im 1. falls interessiert bitte ja mehr ok
Kunde gute Frage oder erstmal gute Beobachtung die Anzahl dieser Bedingungen ist exponentiell groß Überschlags Weise was ist ist eine exponentiell 2 hoch 100 wo stehen wir da in der Größenordnung im Dezimalsystem also bei 100 Knoten hätten wären wir hier bei größeren zwar 100 also was ist 2 hoch 10 ich habe ihn gefragt alle haben sich als Informatiker geortet also 2 hoch 10 sollte bekannt sein das ist ungefähr 1000 nämlich genau 1020 22 ist dann ungefähr was das war auch 10 Tausend ist also 10 Uhr 3 also 2 hoch 10 ist ungefähr 1000 also 10 hoch 3 frage was ihr 2 Uhr 20 so jetzt müssen Sie da irgendwie mit extrem sei Gesetz solle wird Gesetzen vertraut sein ungefähr 10 Uhr 6 soll das frage ich Sie jetzt nicht mehr sondern seit sich ein 2. 100 das ist ungefähr 10 hoch 30 dann natürlich ungemütlich nicht diese Größenordnung wenn man allein schon diese Größen und Rechner zu packen wir wieder ich von der Lösung der Dinge nur das Ganze zu und ihren also eine sehr wichtige Frage kann es überhaupt einsetzen 2 Antworten erst ein so Wort ja es gibt algorithmische Verfahren denen sich kann gerne welchen in kann denn ich ins Dienst also Spalten gehen der Regierungs- Schemata Prozeduren Algorithmen was auch immer und die fahren die ignorieren am Anfang erst einmal diese diese bitte die in diese Bedingungen sondern versuchen es dann mal hiermit wieder eine Million klarzukommen und gucken immer mal zwischendurch welche von diesen Bedingungen werden für verletzt werden sehr stark verletzt und hatten ein paar von diesen Bedingungen und Paar von diesen Bedingungen rein lesen weiter arbeiten weiter gucken dann wieder was ist mit dem Leben über rein getan haben was ist mit einer billigen wenn die auf verletzt entscheiden dann er das 7 paar von diesen Beginn dieser eingenommen haben wieder rausnehmen Sie kennen das ganze werden so war seine Sachen bei Wahllokalen Suchverfahren solche Ideen gehabt man dafür wieder andere Bedingungen rein die jetzt besonders glücklich verletzt und versuchen so Schritt für Schritt dann zum optimal Lösung zu kommen bis wir sie verstellen kann diese Bedingung wird mal verletzt es gibt solche Verfahren die auch eine Praxis also theoretischen sehr gruselig aber der Praxis senden funktionieren die sehr sehr gut 1. Antwort 2. Antwort wir sind ja hier in einem Kontext wo wir und ja gar nicht Lösung haben wollen sondern wo wir über über Unterfranken reden wir uns da sie sondern nur nochmal anders aus aber beachten Sie auch die 1. Antwort ja auch so auch wenn wir nicht in dem Bereich unterschreiben Brand bauen sind sondern wenn wir wirklich lösen wollen dann ist so eine eine Formulierung realistisch damit kann man damit können solche Löser ganz gut umgehen in dem sie eben nicht die gesamte Menge betrachten sondern immer eine sehr war kleine Auswahl dieser dieser Teil dieser Bedingungen erfahrungsgemäß reicht das um ganz gut hin zu kommen so gespielt haben was
wir sind jetzt fast fertig vielleicht nur ganz kurz noch was wir jetzt beim TSB da eigentlich machen die Nummer 5 1 X 5 aus Nummer
5 da diese Bedingung diese Bedingungen das ist genau 2 kann Incident wird wird reduziert und die wird relaxiert Schädigung dass dass es genau 2 sind das heißt wir führen die einen in die Zielfunktion wenn nehmen sie raus aus dem Satz von Bedingungen wird Schönheit Wald
diesen Satz von Bedingungen nehmen wir
her und für jeder für jeden Knoten i gleich 2 bis 1 lassen wir denn diese Bedingungen her und für das für den Knoten eines für alle Knoten die wird ein zahmes muss ich noch mal überlegen zum Glück ist jetzt die Zeit vorbei so dass ich noch mal eine Woche Zeit haben wir genau zu überlegen was sich jetzt hier eigentlich sagen wollte was aber nach anderthalb Stunden vielleicht doch ein bisschen nach dem schon seit über einer Stunde der Kaffee ist das ist doch ein bisschen schwierig wird okay also ich ja was ist jetzt genau bedeutet hier wie wir das war schon Multiplikation Multiplikator Entschuldigung lagen schon Verzierung
auf diese Problemstellungen anwenden
das betrachten wir dann beim nächsten Mal wieder in alter Frische für heute und für den Rest der Woche wenn eine schöne Zeit sieht ja sogar langsam mal wieder mit dem Wetter einigermaßen aus auch wenn es bitterlich kalt ist okay das ist mal ausgesehen ein paar Sekunden habe ich jetzt zu wenig Vorlesung gehalten
Loading...
Feedback
hidden