Sect. 5: integer linear programs (ILP)

Video in TIB AV-Portal: Sect. 5: integer linear programs (ILP)

Formal Metadata

Title
Sect. 5: integer linear programs (ILP)
Title of Series
Part Number
6
Number of Parts
12
Author
License
CC Attribution - 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 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
2014
Language
German

Content Metadata

Subject Area
Abstract
Algorithmische Optimierungssprachen wie OPL und Eclipse Modellierung innerhalb eines restriktiven Modellierungsrahmens (zum Beispiel lineare Optimierung oder ganzzahlige lineare Optimierung) Modellierung als kombinatorische Optimierungsprobleme (z.B. Netzwerkflussprobleme, Färbungsprobleme, Wegeprobleme) Komplexe Fallbeispiele aus der Praxis. Zum Beispiel: Modellierung der Fahrplanauskunft im Bahnverkehr Modellierung der Steuerung von Fertigungsrobotern deterministisches und stochastisches Scheduling
Loading...
Algorithm Scientific modelling Computer program Umrechnung Laufzeit Linear programming Set (mathematics) Atomic nucleus Mathematical model Subset Programmer (hardware) Mathematics Sheaf (mathematics) Theorem Integer
Kante Computer programming Algorithm Constraint (mathematics) Mathematisches Zeichen Insertion loss Zielfunktion Cryptanalysis Theory Programmer (hardware) Mathematics Ganzzahlige lineare Optimierung Differential equation Physikalisches Phänomen Constraint (mathematics) Slide rule View (database) Computer program Linear programming Modeling language Set (mathematics) Computer Computer programming Zielfunktion Mathematics Word Positional notation Algebra Film editing Systems <München> Sheaf (mathematics) Military operation Revision control Computer science Software framework Integer
Greatest element Constraint (mathematics) Equivalence relation Continuous function Affine space Variable (mathematics) Mathematics Solution set Logic Vector graphics Kompakte Menge Rule of inference Addition Constraint (mathematics) Constraint (mathematics) Raum <Mathematik> Maximum (disambiguation) Computer program Mathematical analysis Linear programming Set (mathematics) Variable (mathematics) Exclusive or Algebra Function (mathematics) output Coefficient Integer Form (programming)
Rule of inference Execution unit Version <Informatik> Constraint (mathematics) Computer program Linear programming Equivalence relation Affine space Variable (mathematics) Exclusive or Equivalence relation Algebra Function (mathematics) Logic Integer Form (programming)
Implikation Rule of inference Table (information) Slide rule Constraint (mathematics) Software developer Computer program Linear programming Propositional formula Truth table Sequence Structural equation modeling Logic Scalar potential INTUITION <Benutzeroberfläche> Table (information) Propositional calculus Integer
Predicate (grammar) SOKRATES <Bibliotheksinformationssystem> Computer program Logic Linear programming Set (mathematics) Term (mathematics) Predicate (grammar) Integer Rounding
Implikation Addition Curve Complex analysis Zahl Slide rule Computer program Curve Linear programming Propositional formula Set (mathematics) Lace Prime number Number Permutation Mathematics Positional notation Integer factorization Integer Chain rule
Point (geometry) Kante Polygon Diagonal Aktion <Informatik> Berührung <Mathematik> Infinity Distance Inequality (mathematics) Total S.A. Dreiecksungleichung Mathematics Plane (geometry) Summation output Length Point (geometry) Moment (mathematics) Computer program Linear programming Feasibility study Square Axiom TOUR <Programm> Plane (geometry) Sierpinski triangle Travelling salesman problem Function (mathematics) output Display Optimum Integer
Shortest path problem Direction (geometry) Maxima and minima Infinity Dreiecksungleichung Mathematics Plane (geometry) Matrix (mathematics) Object (grammar) Hausdorff dimension Spacetime Robot Point (geometry) Computer program Internet service provider Linear programming Distance Plane (geometry) Position Travelling salesman problem System programming Object (grammar) Integer Euklidischer Raum Factorization
Geometry Point (geometry) Metric system Point (geometry) Computer program Curve Curve Linear programming Instance (computer science) Semantics (computer science) Distance Shape (magazine) Distance Mathematics Plane (geometry) output Integer Euklidischer Raum
Stress (mechanics) Slide rule Version <Informatik> Aktion <Informatik> Point (geometry) Computer program Linear programming Permutation Distance Permutation Mathematics Sign (mathematics) Matrix (mathematics) Plane (geometry) Travelling salesman problem Revision control output output Length Integer Pairwise comparison Euklidischer Raum
Euclidean vector Robot Execution unit Sampling (statistics) Component-based software engineering Type theory Whiteboard Maize output Robot Execution unit Slide rule Information Typ Moment (mathematics) Computer program Linear programming Permutation Component-based software engineering Mathematics Sign (mathematics) Latent heat Angle Travelling salesman problem Social class Integer
Kante Execution unit Typ Computer program Linear programming Sampling (statistics) Force Component-based software engineering Component-based software engineering Travelling salesman problem Summation Length Integer Absolute value
Execution unit Algorithm Euclidean vector Constraint (mathematics) Computer program Linear programming Component-based software engineering Type theory Whiteboard Travelling salesman problem Software framework Vertex (graph theory) Integer
Kante Point (geometry) Shortest path problem Product (category theory) Computer program Desire path Linear programming Zielfunktion Set (mathematics) EXCEL Semantics (computer science) Term (mathematics) Variable (mathematics) Process modeling Variable (mathematics) Permutation Mathematics Zusammenhang <Mathematik> Travelling salesman problem Cost curve Summation Integer
Kante Noten <Programm> Constraint (mathematics) Complementarity Computer program Linear programming Feasibility study Lösung <Mathematik> Set (mathematics) Inequality (mathematics) Airfoil Subset Computer file Physical quantity TOUR <Programm> Hausdorff space Calculation Word Energie Plane (geometry) Solution set Strich <Typographie> Partition of a set Integer
Slide rule Solution set Constraint (mathematics) Computer program Feasibility study Linear programming Integer Order of magnitude
so ein ganz neues Thema das wir bisher noch gar nicht betrachtet haben wir gehen in gewisser Weise wieder zurück einen anfangen wo wir ja alle möglichen Problemstellungen in OBL modelliert haben hier machen wir so das ähnliches allerdings mit einem sehr viel eingeschränkteren Modelle das IEP P oder Image der Abfolge Mind heißt das ist im Grunde eine ein mathematisches Modell wir betreuen wir benutzen Mathematik hier nicht um zu berechnen Umrechnung selber durchzuführen oder Theoreme aufzustellen und zu beweisen sondern wir benutzen Mathematik als Modellierung Sprache wir könnten da alles was wir Ihnen in diesem Kapitel machen auch in OPL ausdrückten dieses mathematische Modell ist eine Teilmenge der Sprache OBL nur dann werden wir halt mathematische sind benutzen weil es einfach in diesem Kontext praktischer ist warum machen wir das warum versuchen wir jetzt verschiedene Problemstellungen in einer einen eingeschränkten Modelle die Modellierung Sprache deutlich eingeschränkt gegenüber OPL zu formulieren einfach deshalb aus 2 Gründen 1. wollte eine sehr sehr Einsicht reich ist wenn wir feststellen dass sich eine Vielzahl verschiedener Problemstellung denn man es gar nicht unbedingt einen gesehen hat sich in so einer sehr sehr eingeschränkten mathematischen Sprache darstellen lassen korrekt abbilden lassen aber andererseits auch wir haben ja in der Algorithmik immer einen gewissen Kompromiss je allgemeiner die das Problem des formulierte sie oder die allgemeine die Modellierung Sprache ist ich in diesem Kontext und so umso schwieriger wird das Algorithmen zu bauen die mit mit dem Problemstellungen die wir in dieser Sprache modellieren tatsächlich effizient klarkommen hier eingeschränkter die sprachlichen Möglichkeiten sind umso eher ist es möglich die Problemstellung dann auch wirklich sehr sehr effizient zu lösen und es ist eine Zeit seit mindestens seit ja und das sie also 5 Sicherung bekannt dass ich Problemstellungen dieser Art über die wir sprechen werden ganzzahlige wenn Programme dass diese Art von war damals Problemstellungen sich vergleichsweise sehr gut sehr effizient lösen lassen dazu gibt es einen seit ungefähr nur 50 einen Riesenhaufen an Literatur Tausend Abertausende Papiere die sich damit beschäftigen wie diese Methoden weiterentwickelt werden können wie sie angewandt werden können auf immer neue Problemstellungen und so weiter und so fort also es macht Sinn wenn man hat viel gewonnen der Mann ein gegebenes Problem das man lösen will wenn man das Modellieren kann als ein ganzzahliges Zehnjahresprogramm weil es eben dann sehr viel weil weil man dann eben eine ganze Menge Werkzeuge zur Hand hat das kennen Sie auch von einer Sorge dass sie Plex Sedlex was er zur Kenntnis genommen haben ist schlicht und einfach eine Lösung für linear Programme beziehungsweise ganzzahlig linear Programme das ist der Kern von Al Lork und da das ist auch das was wirklich die halbwegs vernünftige Laufzeiten bringt ja ohne ohne diese ohne diese ganze Technologie die wir hier aus der Mathematik zur Verfügung haben würde ein überhaupt nichts reißen können gut worum geht das was ist
ein Ende der Lehre Programm oder das indische Länder Programme nicht vielleicht vorne weg Erben der Begriff ab vor man endlich ist eingeführt worden zu einer Zeit als noch niemand an das Programmieren von Computern gedacht hat also die man aus allen Theorien vielleicht sein seinem man hat den Begriff im ohne diesen Kontext gewählt das geht heute würde man das sicherlich nicht mehr pro Probe mindern weil es einfach nicht programmieren in unserem Sinne ist sondern ein 7 Jahresprogramm ist einfach eine linear führen wir kommen noch darauf was genau damit gemeint ist eine sie Jahre Beschreibung eines Problems also ihnen Bild letztendlich wenn man so will inbegriffen der 7 Jahren Algebra im mit denen mit den Operation mit den Ausdrucksmitteln den aus den Ländern Algebra vertraut sind und mehr nicht ja also verwechseln Sie das Wort pro wenn man hier nicht mit ihren Gebrauch des Wortes gut das ist das was ich hier vorne weg eingangs gesagt hat aber der Titel Folie generell also so als als Grundtendenz gilt natürlich nicht in jedem Einzelfall aber generell je allgemeiner Erlöser ist umso weniger effizient wird der sein können die ALDI also die allgemeiner letztendlich die Modellierung Sprache ist die ein böser versteht umso weniger Effizienz keiner sein dass ich denke das ist offensichtlich dass dieser Zielkonflikt die Saatfeld aufgestellt und wenn ja wie gesagt seit ungefähr 19 50 weiß man das leere Tor so Programmierung da setzt er dass das ein Fall ist den man sehr gut handhaben kann das hat seine Wurzeln übrigens im Zweiten Weltkrieg bei solchen Fragen wie zum Beispiel die bei den Alliierten auf auf deren auf deren Seite hat das seine Wurzeln mindestens dort bei solchen Fragen wie sie wollen U-Boote in der schön sie wollen sie wollen Frachter von amerikanischen zu britischen und später dann nach französischen Häfen über den Atlantik schicken sie haben eine gewisse Anzahl von Hilfen zur Auswahl eine gewisse Anzahl von Hilfen auf andern Seite zur Auswahl und Sie wollen die Gefahr von o Bot-Attacken minimieren jede von jedem Hafen an der amerikanischen Ostküste zu jedem Hafen an der europäischen Westküste also an der von der Alliierten gehaltenen Teilen der aber nach europäischen dass Christa haben Sie dann eine Kante deren Gewicht sozusagen die U Boot Angriffs Wahrscheinlichkeit ist und dann wollen sie eine möglichst gute Zuordnung finnische für von Ostküste der USA an die an die Westküste Europas zu gut zu schicken so dass die die gesamte Wahrscheinlichkeit für U-Boot Verluste möglichst gering ist solche Problemstellungen darin haben hat das Ganze was ich jetzt erzähle sein Ausgang gefunden da darin hat ein Teilgebiet im Schnitt zwischen Mathematik Informatik und Wirtschaftswissenschaften seinen Ausgangspunkt gefunden wenn Sie in dem Fach was mit Wirtschaft machen wenn sie es vielleicht kenne es heißt aber ich ins Research also Planung von Operationen Planung von Unternehmungen von Unternehmen alles über Alter raus um mathematische prallte Planungsprobleme geht Ablaufplanung in Fabriken Planung von Projekten was wischen betrachtet haben gehört auch dazu gut und das habe ich auch eben schon einen Titel vorher angedeutet dass es auch einiges trative gute Übung ist wenn Sie nicht diesen reichhaltige diese reichhaltigen Ausdrucksmöglichkeiten von OBL zur Verfügung haben sondern nur eine noch deutlich eingeschränkter Ausdrucksmöglichkeit zu sehen das Mandat immer noch eine ganze Menge machen kann so was ist
ein ganzzahliges länger Jahresprogramm wie gesagt wir werden Mathematik eben hier anders sind als sie das in ihrem Mathematik Veranstaltungen überwiegend kennen gelernt haben nämlich zur Modellierung dass Sie kennen das natürlich auch Mathematik zur Modellierung herzunehmen Differentialgleichung Systeme um irgendwelche physikalischen Phänomene zu beschreiben und so weiter und so fort hier werden sie 1 1 1 Möglichkeit dazu kennen lernen die Sie vermutlich noch nicht anders vorgesehen und zum ist nicht in den Pflichtveranstaltungen so was heißt das wir haben immer eine Zielfunktion und wir haben Nebenbedingungen und hier wird jetzt gesagt ganzzahlige linear Optimierung bedeutet dass sowohl die Zielfunktion als auch den mit den finden ja sein müssen und das wird versprochen und dieses versprochen wird auch gehalten dass das auf der nächsten Folie gesagt wird was das genau bedeutet nur noch mal was ihm auch gesagt hatte wir werden nicht OBL Notation entfernen obwohl man das genauso gut machen könnte sondern mathematische Notation die wir hoffentlich noch einigermaßen vertraut ist aus ihrem Mathematik Veranstaltungen so was
ist eigentlich ist das etwas ganz einfaches affinen liegen ja eine Funktion hier FMX ist auf vielen im Jahr wenn sie im Chor im allgemeinsten Fall so aussieht das heißt 1 die Variablen ja nur die nächsten Weierbach sie das nur die X Variablen sind die aber es sind das was Sie aus der Mathematik kennen als Koeffizienten also letztendlich sind das sind das eben trotz also die er die sind in Porz diesen gegeben die Echse sollen berechnet werden lassen die Unbekannten und was hier steht in allgemeinster Form ist die unbekannten dürfen nur so auftreten wie es hier zu sehen ist eine unbekannte kann multipliziert seien mit einem Input mit einem festen Wert mit einer konstanten und die dürfen aufsummiert werden und dann darf noch ein weiterer Termin dazukommen ein weiterer so meint der auch feste konstant ist mehr nicht was nicht zum Beispiel sein darf ist X von 1 multipliziert mit X von 2 oder I X von 1 geteilt durch x von 2 minus geht natürlich auch das heißt der Kunde sind es negativ aber mal oder durch geht nicht 2 hoch x geht nicht also die die weil die die Variablen dürfen nicht anders erscheinen als in dieser Form sie dort noch keine Wurzeln davon nehmen von einer Variablen und so weiter und sofort also nur sehr eingeschränkte Form eben das was Sie aus der in einer Bar kennen wenn sie da zum Beispiel die der Gleichungssysteme betrachte es ist exakt dieselbe Form letztendlich was hier steht ist ein Vektor a multipliziert Gala wurde bisher mit einem Vektor x und wenn ja Jahren den bedingt affinen linear statt nur linear weil solche zusätzlichen Summanden erlaubt sind so wie hier deshalb hatte ich da meistens wenn man die Bedingungen immer noch länger aber ich mache hier lieber den Unterschied weil sie mehr oder weniger versteht man normalerweise den Jahren eine weitaus eingeschränktere es nämlich ohne solche Summanden so war die die Nebenbedingungen müssen auf der linken und auf der rechten Seite genau so aussehen wie jetzt diese Funktion hier dass die war war haben die unbekannten X nur in dieser Form auftreten dürfen multipliziert mit einem festen wert und das Ganze zusammenaddiert und es darf kleiner gleich gleich oder größer gleich zwischen der linken und der rechten Seite stehen das ist kein kleiner und kein größer da steht mag vielleicht überraschen hat aber erst am ist aber erst einmal in der Praxis keine keine keine Einschränkung und hat aber einen einen wichtigen Grund dessen Grundlage sie aus der Analysis kennen gelernt haben müssten sie wissen wir das genau auf einer kompakten Menge nehmen stetige Funktion ihr Maximum und dem Minimum an deshalb nimmt man genau das darauf wollte ich hinaus danke deshalb da beziehungsweise für den von ihnen die ich meinte man sich für Mathematik okay also sieht die aber diejenigen die Meyer Watch Mathematik studieren haben zumindest mal eine vereinfachte Form dieses allgemein aus Sorge gesehen wie zum Beispiel dem eindimensionalen auf einem abgeschlossenen Intervall also alles was größer gleich dem linken wird alles auf kleiner gleich dem rechten wert erst den rechten Grenzwert ist wenn du wenn sie darauf stetige Funktion haben dann in die auch ihr Maximum und dem Minimum an und das das sich beliebig auch beliebig hochdimensionale Mengen er weiter nicht nur in der Weise wie sie das zu Recht gesagt haben und der Begriff den sie verwendet haben kompakt ist in den Mengen in denen in den Räumen von dem wir reden gleichbedeutend mit beschränkt und abgeschlossen abgeschlossen im im Sinne dass der Rand der Menge mit dabei ist ja wenn Sie hier klar ein kleiner gleich haben dann ist der Rand des Lösungsraum Raums mit dabei wenn ich daran dass das was gleich wusste wo die beiden linke oder rechte Seite gleich sehen wenn sich in kleiner haben dann ist der Rand nicht dabei aber auf dem Rhein könnte das Maximum oder Minimum sein und dann ist es irgendwie auch witzlos möglichst nah an den Rand zu gehen um die um den Wert zu approximieren den man mit kleiner gleich in der Lösung Menge drin gehabt hatte und wie gesagt Praxis interessierte man sich nun eigentlich nur Vorfälle wo hier wo man die kleine gleich größere gleich schreiben kann so dass keine Einschränkung ist gut so
fangen wir an mit ein paar kleinen Fingerübungen sehr kleine Fingerübung haben Sie vielleicht nur Mathematik sehr früh auch schon in der Mathematik von sehr früh auch schon gesehen wir haben X und Y R 2 Variablen die Booch sind also Werte 0 und 1 haben können nur gleich vor 1 gleicht Flug und dann können Sie so die einfachen logischen Bedingungen natürlich schon von vornherein durch linear Bedingungen ausdrücken wenn Sie in das das logische er Unternehmen X Ernst y dann können Sie es natürlich durch den Saal durch einen Satz von 2 Bedingungen ausdrücken nämlich X gleich 1 und Y gleich 1 sie am also 2 Bedingungen die 7 Jahre sind aber halt in einer sehr einfachen Form dar also wir werden sehr häufig
sie die Situation haben das dass wir diese allgemeine Form gar nicht gar nicht haben sondern eine sehr viel einfachere Version dieser allgemeinen Form sie können auch wenn
sie unbedingt Spaß und so was haben können Sie auch X und Y die und Dung als einen Bedingung dass eine Bedingung schreiben nämlich das X plus Y gleich 2 ist wenn X und Y 0 1 variabel sind dann ist die Bedingung X plus Y gleich 2 gleichbedeutend damit dass beide 1 zu 1 das logischerweise dieser für sich bei Fingerübung inklusiv oder können Sie als schreiben als X plus Y größer gleich 1 offensichtlich exklusiv oder können Sie schreiben als X plus Y gleich 1 und logische Äquivalenz das also X war es genau dann wenn entflohen war es einfach durch die Gleichheit ja das sind alles sehr einfache Beispiele sie extrem einfache Beispiele für affinen Jahre Bedingungen so logische
Implikationen kennen Sie auch die aus der Aussagenlogik die Wahrheitstabelle wenn wir hier für X und Y alle 4 Varianten hernehmen alle 4 Ausprägungen dann wissen Sie Sie die Tabelle der logischen Implikation so aus und das können
diese Tabelle können wir erweitern hier noch mal die Tabelle eben von der letzten Folie alle 4 Varianten von X und Y Tabelle der logischen Implikation und wenn ich X kleiner gleich y daneben setzte dann sehen Sie dass dieselbe Tabelle das heißt logische Implikation können Sie einfach durch die längere Bedingung X kleiner gleich y ausdrückt interessanter period den ich hier einfach mal Sie sehen dass neugierige neben fragen was hat man am Rand und wie sagt man im Deutschen nehmt Frage passt nicht in Frage also wissen was ich meine warum ist eigentlich die Tabelle so und nicht anders definiert die für für die logische Implikation ich meine hier im Fall dass x gleich 1 ist ist es logisch nicht wenn es war aber es falsch ist dann sollte dann 0 rauskommen und wecken wenn beide Wahnsinn sollte oder eines rauskommen aber wenn X 0 ist kann man doch gar nicht Aussagen über y nicht eigentlich müsste man doch hier sagen und definiert was man natürlich in der zweiwertigen Logik nicht kann man hat sich dafür entschieden hier also einzusetzen wo man sich nicht dafür Infineon 0 einzusetzen oder oder sonst irgendwie war also ich weiß nicht wie es Ihnen ging aber als ich das zum 1. Mal gesehen haben kann mir das sehr merkwürdig vor ich verstehe ich habe natürlich damals schon verstanden zweiwertige Logik kann man jetzt keinen dritten wird mit Semantik ist mir doch egal reinsetzen aber wenn die Entwickler wenn die Prämisse falsch ist ist es ist alles sehr vollkommen wurscht also warum warum stehen hier einzelne also in welche Leute müssen sich ja was dabei gedacht haben bitte die dass es ist richtig dass die dass die Gewinne er dass man an die ist die Indikation äquivalent ist nicht X oder Y aber das ist eine Folge dieser Setzung die Sie hier auf dieser Folie sehen keine Ursache oder also wenn Sie das als als Grundherr nehmen wir das Umzüge Schloss oder also warum auf oder andersrum gefragt warum sollte man die Implikation ausgerechnet so definieren dass nie das Äquivalent zu nicht X oder Y er sie die Frage mit der natürlich wenn sind durch die sind schon zu mehreren Semestern daran gewöhnt okay der wenn es wenn es 0 wäre wäre es das Gleiche wie ernst ja und ja aber passt nicht so richtig das ist richtig aber aber wenn wir haben ja hier viele verschiedene Varianten was sich hier hin setzen könnten ja natürlich so ist definiert ja sind Sie sicher wenn es nicht vorgesehen hatten das ist auch so definieren würden wir können gerne mal an was was ich Sekundarstufe gehen Leute aus einer Matte angeht also Schüler aus Jammertal geht und ihn die Frage stellen war also diese beiden fahren wegstreichen Fragen stellen was würden würde die da einfüllen glauben Sie dass die alle da 2 1 einsetzen würden Sprache können Sie Ihre Intuition die Sie da jetzt als Argument Herrn im und wie von Hand wenn er natürlich ich sicher würde es kann nicht falsch sein Jahr was sagen die anderen also meines 8. gibt es eine gute pragmatische Begründung dafür warum es so definiert wird und nicht anders und das will ich jetzt auf den nächsten die für das 4 Folien ganz kurz darin dass man sich nicht also Sie müssen sich alles klar werden Definitionen sind nicht richtig oder falsch oder so etwas sondern sie sind dann pragmatisch gewählt sie werden so gewählt dass Haus das sie hoffentlich gut verwendbar sind Intuition spielt insofern wieder eine Rolle wenn eine Definition gegen die allgemeine in die Intuition getroffen wird wenn ein Begriff gegen die allgemeine Intuitionen getroffen wird wie sie auch häufig im im Juni in im im juristischen Bereich der Fall ist dann sagt das Potential für Verwirrung das heißt also man sollte der Intuition natürlich aus pragmatischen Gründen wieder Folgen aber es gibt glaube ich noch stärker pragmatische Gründe als ihre Intuition denn bis jetzt sind Sie der einzige hier im Raum der sich zu dieser Intuition bekannt hat so ein einfaches Beispiel also
ich bitte um Entschuldigung das sehe ich dass ich so ein primitives Beispiel immer aber sie haben Sie schon mal sehr mitbekommt im warmen der Philosoph oder jene logischen Probe deutlich wenn immer einfacher Beispiel Wohnung vor gelungen so von wegen Sokrates ist ein Mensch also stabilen so weiter kennen sie ich bitte auch jung Beschuldigungen Sie das jetzt erst Schäferhund als natürlicher Paddock und ich schrieb dort weiß ich nicht wie das da reingekommen ist also denken Sie Sie bitte hier an eine Schäfer und muss ich korrigieren ist auch egal um welche unter dem Bundes ist egal für das Argument so wenn man die Menge aller Hunde D für Talk und wir betrachten 2 Prädikate ein Prädikat ist dass der Hund ein Schäferhund ist und der zweite das zweite Prädikat ist dass der Hund Katzen bereist seit dem Herrn Professor Kassen Wasser haben sollte glaube ich sollte ich das Modell das Beispiel müssen oben bestreiten ich bitte Herrn Katzen Weise hiermit um Entschuldigung so also für alle x aus der Runde Menge aus aus der Wunde heilt sozusagen wenn von Avonex gilt wenn X ein Schäferhund ist dann gilt auch B von beißt Katzen ja das ist alle alle Schäferhunde beißen Katzen übersetzt in einfachen prädikatenlogischen Ausdruck nichts Neues für Sie richtig so die
Indikation sollte natürlich eine gewisse Eigenschaft erfüllen sie sollte die Eigenschaft erfüllen dass dieser Ausdruck genau dann wahr ist wenn der Ausdruck ohne mehr Quandt war für jedes einzelne für jeden einzelnen und wahr ist na ich offensichtlich das heißt wann immer und wann immer die Prämisse falsch ist weil ich habe es hier noch mal anders
formuliert wenn wir wenn wir nur endlich viele Hunde haben ich gehe mal davon aus dass uns am Ende der so nur endlich viele Hunde gibt dann soll dieser Ausdruck denken wir diesen Ausdruck umformulieren das wäre das Sohn sowohl mit Implikation natürlich haben dass das Geld dass wir das dass wir diese diesen Ausdruck auch in Nummer nummerieren können ja dass wir hier dazwischen also dass wir hier jeden einzeln Hund einsetzen können und dass die alle damit ernst verknüpfen und dafür damit damit dass genau dann wahr ist wenn alle Schäferhunde kratzen beißen muss gelten für die für die Glieder in dieser Kette wo das kein Schäferhund ist muss der neutrale wird der Addition eingesetzt werden und neutrale der derart wird der Addition ist die 1 unabhängig davon was jetzt was jetzt mit der Konklusion ist und das ist denke ich ein sehr starkes Argument dafür warum man die wie bei der Indikation im Falle dass die Prämisse falsch ist die Implikation als man seht damit es hier an diesen Stellen die Indikation die Eigenschaften hat die man natürlicherweise haben möchte ja das kennen Sie über woanders auch denken denken Sie sich in einer schönes Beispiel sind Primzahlen ist die 1. Primzahl oder nicht 1 Abstimmung machen weil wir demokratischen China die also blind ist wer es dafür dass sie also Primzahl ist dagegen okay es deutliche Mehrheit warum nicht ich meine das macht doch den Begriff komplizierter ja man muss sagen eine Primzahl ist eine Frage die die nur durch sich selbst und durch 1 Tag ist außer dir 1 warum warum definiert man Primzahlen so dass das komplizierte dass die Definition komplizierter wird eigentlich es gibt ja so etwas wie eine Begriffs Ökonomie in der Mathematik und in der Wissenschaft allgemein zum es in gewissen Bereichen der Wissenschaft das man Begriffe einfach hält möglichst einfach hält auch im aus pragmatischen intuitiven Gründe warum um macht man sie komplizierte ich weiß es nicht wer sich zuerst gemalt habe ich glaube sie ja und macht doch nichts ist wenn sie dieselbe Zahl ist aber aber was wäre denn das wäre dann so schlecht daran wenn man gesagt ok die also ohne Primzahlen wenn man sagt man Prinz sind alle Zahlen die durch 1 und durch sich selbst teilbar sind wer das Essen Weltuntergang also wir gut natürlich macht es einen Unterschied weil weil es dieselbe Zahl ist aber ich meine solche Grenzfälle damit lädt die Mathematik über denen sich nur einen Grenzfall die gerade seine Kurve versuchen Sie das mal wie man auf der Straße zu erklären dass in der Mathematik die geladene Kurse ist in haben Sie wollen glaube ich der ist sich immer weiter Primfaktorzerlegung es ein gutes Beispiel die Primfaktorzerlegung dank kommt die Begriffs Ökonomie so sagen hinten um wieder rein dass man solche Aussagen einfacher treffen kann dass man das überhaupt die Aussage treffen kann die Primfaktorzerlegung ist eindeutig ich denke das ist das ist nicht ohne wesentliche Gründe gewesen warum man sich entschieden hat die also ich kenne immer mal dass die Historie der Mathematik nicht und insbesondere nicht die Frage warum man die D 1 aus dem Primzahl irgendwann rausgeschmissen hat aber ich denke dass das ein wesentlicher Grund war jetzt weiß ich es haben sich noch mehr Leute gemeldet wollen sie noch ein weiterer dazu oder ein anderes Beispiel ist 2 hoch 1 ist 2 2 auf 2 ist 4 und so weiter und so fort das ganz offensichtlich wenn man die Kette Favorit 2 Wochen 0 kann man erst mal nicht als 2 mal 2 mal 2 oder sowas darstellen aber aber es passt genau in die Kette reihen das 2 Euro 0 1 ist oder in sie Fakultät 0 Fakultät ist 1 verkohltes ist 1 2 verkohlt tät das ist zwar bei 3 Fakultät des 6 und so weiter von warum ist worum es 0 Fakultät 1 das wenn Sie nicht das in der Mathematik gesehen haben glaube ich ja und was hat dividieren mit mit der mit der Fakultät zu tun okay soll es ist ein Problem weiter bitte ja die Anzahl der Permutationen so okay die okay n Fakultät ist die Anzahl der Permutationen einer in der mehr den man mir das es nur gute Begründung dafür pragmatische Begründung dass sie 0 Permutation einer 0 man den Menge haben aber die müssen sie für die sich vorzustellen aber bitte ja das ist sicherlich auch ein guter pragmatischer Grund n über k das passt wunderbar wenn wenn er wenn die Fakultät von 0 1 ist ja dann das passt wunderbar in Pascalsche Dreieck und so weiter rein es gibt ein tiefer liegenden Grund das können sie aber nur wissen wenn sie jedes mal irgendwie mit und der komplexen Funktionentheorie gesehen haben ich die Fakultät zahlen also gute 2 verklärt und so weiter werden durch eine gewisse in der Mathematik sehr wichtige Funktion namens Klammerfunktion schön sagen namens Funktion interpoliert mit dem mit dem Korrektur Wert plus 1 dabei ist es egal und und die Wärme die sie in der wenn man das fortsetzen wenn man sich anguckt was eine was an der Stelle 0 ist dann kommt genau das Fakultät 1 raus als interpolieren der wert gut also nur nur dieser Ausflug war nur ein eigentlich dazu da um vielleicht noch mal ein bisschen das bist du ins Bewusstsein zu bringen was die Natur von Definitionen ist und was die Zielsetzung bei Definition ist Definition werden pragmatisch definiert hoffentlich nach pragmatischen Gesichtspunkten der Haupt Gesichtspunkt ist das ist zusammenpasst das ist das ist das erfüllt was was es soll natürlich dann kommen was andere R Aspekte Pacman Aspekte eben hinzu dass es möglichst nicht der allgemeine Intuition zuwiderlaufen sollte aber sie sehen an dem Beispiele in der Mathematik das die Kurven Spitzer nein das die geraden Spezialfall der Kurve ist dass ich die Mathematik und wie auch andere Wissenschaften nicht immer um die allgemeine Intuition Schwert sondern der gerne auch mal denken Sie nur an die Definition des Begriffs Alkohol in der Chemie als Beispiel so jetzt gehen wir
wieder zurück also das wäre die Erklärung das wäre eine pragmatische Erklärung sicherlich nicht die einzig mögliche darum warum für die Integration 1 1 der Indikation wird 1 zuordnet wenn die Prämisse falsch ist so jetzt comma
zum wichtigen Thema das das alles nur Fingerübungen pro bedeute schon Natur jetzt comma zu unserer 1. echten Problem was wir modellieren wir nur 2 Fallbeispiele hier betrachten wir nur reinschnuppern aber diese beiden Fallbeispiele sind so gewählt dass sie eigentlich nach meinem Verständnis schon alles Wesentliche dabei sehen was es zu dem Thema zu sagen gibt zu dass sie aus also sollten sie an anderer Stelle mal mit diesem Thema in Berührung kommen dass sie dann entsprechen das Handwerkszeug dazu haben so und Sie kennen das TSP oder nicht können Sie das das Handlungsreisenden Problem hieß früher treffen längst Herz mehr ein Problem heißt heute treffe Lengsfelds passen Problemen aber ändert sich nichts an der Problemstellung sie haben in der einfachsten intuitiven Form haben Sie als Input eine gewisse Anzahl von Punkten in der Ebene man man kann das Display natürlich auch allgemeiner fassen werden wir auch tun aber aber erst einmal des die die einfachste Form ist sie haben sie haben ein paar Punkte der Ebene gegeben und sie wollen einen geschlossenen zyklischen streckten zurück auf diesen Punkten hier bei dem die länger die Gesamtlänge minimal hat was ist die Gesamtlänge für jede Kante nehmen sie in der einfachsten Form die euklidische Distanz in der Ebene und die Summe der Karte General ist die Summe der Kantenlängen gleich die Länge der Tour logisch der kann singen Länge der Tour kennen sie von Christel Wege Problem und ähnlichem vielleicht meine Frage vorweg bevor wir in dieser reingehen lässt sich etwas darüber aussagen ob diese auch wenn wenn die Kantenlängen euklidische sind also tatsächlich die Länge in unserm landläufigen Sinne wer sie was immer aus sagen ob diese rund optimal ist oder nicht also optimal im Sinne von minimale Gesamtlänge war dieses in ne bezog sich das auf die Frage auf die Aussage ob sich etwa auf die Frage lässt sich etwas aussagen oder und mit sich darauf Optimalität Umwelt Moment wo es 16 16 von was von 16 6 12 zu 11 und dann weiter und warum würden Sie das so sagen Pi mal Daumen sie haben aber sie waren gute Sorge da bitte die Weinkannen kreuzen sich offensichtlich und war und warum sagt denn das was ok schon muss das vielleicht in Meineid an ich stimme Ihnen zu wenn Sie sich jetzt irgendeine Vieregg betrachten ja ich versuche mein kleines bisschen exzentrisch zu machen damit es nicht damit es nicht denn der Spezialfall eines Quadrates wird so mit den beiden Diagonalen jetzt haben wir hier aber die CD die die 4 sollten Ihnen und ich unterteile hier schon mal ein Mittelpunkt am Treffpunkt der beiden Diagonalen E 1 E 2 F 1 F 2 können das Lesen wenn ich sitzen sie zu weit hinten so und wenn ich jetzt wenn ich jetzt hier zum Beispiel Rundtour habe auf diesen 4 Knoten nur eine eine die sich hier schneidet er will sich nur mal überlegen die wie man das am besten hier kommen wir rein und hier kommen wir raus so jetzt haben wir einerseits die Rundtour die sich überschneidet das hat die Länge E 1 plus E 2 plus C plus 11 2 los F 1 und die andere die sich nicht überschneidet das hat die Länge B plus CI-Plus des ja das sind genau die beiden Fälle um die es hier geht es gilt aber wegen der 3 Jungs Ungleichung kleiner gleich ihr 1 plus F mehr aber interessiert mich jetzt gar nicht als Entschuldigung wie kleiner gleich E 1 Plus 11 2 und was Sommer hier des kleiner gleich E 2 L und F 1 und dann sehen sie schon das CE taucht in beiden wenn in beiden Seen auf hebt sich also weg das B ist kleiner gleich E 1 hier und F 2 hier und das des ist kleiner gleich E 2 hier und F 1 hier das heißt also diese in diese zweite Länge kann nur kleiner sein als die größere als die andere länger und da es sich um nicht entartete Dreiecke handelt sondern um echte 3 gehandelt können sogar nicht kleiner einsetzen und damit ist klar beide euklidischen also die Länge gleich dem Abstand der beiden Endpunkte aktiv Abstand in der Ebene das gilt natürlich für jede Armee Metrik sie ändern sich aus der Mathematik was eine Metrik ist ja sofern die Kanten ich habe alles was ich verwendet habe letztendlich waren die Axiome der Metrik insbesondere die Dreiecksungleichung und solange diese Aktion gelte die Kantenlängen die Eigenschaften einer Metrik haben so lange ist das auf jeden Fall gegeben das dass sich den nicht Kreuz dass sich die nicht kurz das werde sich kreuzen dann ist es auf jeden Fall nicht optimal so dass für überfällig aber müssen zurück ich so gut
so das ist so haben wir bisher das TSP gesehen
was wie gesagt Handlungsreisen Problemen die intuitive Vorstellung dahinter ist dass man Handlungsreisender verschiedene Städte abklappert und versucht die Fahrzeiten dazwischen zu minimieren das ist natürlich keine realistische Anwendung das würde kein Mensch machen so in der Form vielleicht heutzutage wieder beim Flottenmanagement oder was weiß ganz sicher ein Flottenmanagement ja wenn ein wenn wenn ein einzelner LKW verschiedener stellen anzufahren hat dann ist die Fahrzeit die die Gesamtfahrzeit natürlich ein nicht unwesentlicher Faktor für die Effizienz spielt aber auch in anderen Situationen noch alle denken Sie an Fahrstraßen nehmen automatische ja wir haben Laufbänder im in der Fabrik wo wo sie wo sie ein Roboterarm haben der verschiedene der an einem Werkstück zum Beispiel in einer Auto Charasse sowie verschiedene Punkte anlaufen muss unter Wasser sich Schweißarbeiten oder blöd der beim oder vielleicht auch nicht weniger um da irgendwelche solche Arbeiten zu verrichten da ist es natürlich wesentlich das sehr dass er die verschiedenen Punkte die Zeit die er braucht um von einem Baum zum andern kommen zu kommen global minimiert und auch tatsächliche geschlossen Rundtour weil wenn er fertig ist soll er so schnell wie möglich in seine Ruhe Position wieder damit so schnell wie möglich dann das nächste Werkstück kommen kann
so Oh das kann man natürlich ganz einfach generalisierend dass wir nicht Punkte in der Ebene hernehmen sondern irgendwelche Objekte die uns völlig und die uns nicht interessieren was das eigentlich ist und dass wir irgendetwas kannst Matrix Herrn immer zwischen je 2 dieser in Objekte von einem zum anderen gibt es eine Distanz gewissen Distanz Werte gegeben ist muss nicht symmetrisch seien also die Distanz von von Objekt begehrt muss nicht identisch sein zu Distanz von Objekt wird noch ich ist kann sie auch von kürzeste Pfade Betrachtungen ja ich habe das Beispiel genannt die Fahrzeit mit dem Fahrrad in den Alpen das ist auf manchen Wegen die Fahrzeit in die an der Einrichtung deutlich anders als die Fahrzeit in die eine Richtung die geschätzte Fahrzeit und so ist es natürlich hier potenziell auch es eine echte Verallgemeinerung hier ist also Beispiel des wenn wir sie haben es wenn wir davon ausgehen dass die Eltern in einer Richtung gleich in eine Richtung ist ist ist keine Metrik sondern ich kann das natürlich so setzen dass die Dreiecksungleichung beliebig verletzt ja das ist eine echte Verallgemeinerung von metrischen Setzungen zum
Beispiel was damit natürlich K fragt also da überdeckt System würde das war dem Deutschen mit einbezogen ist mit mit modelliert ist das ist wenn Sie wenn Sie Fahrt das Tanzen haben mit Stoff von Straßen Vorrechte Straßen dann sind das natürlich nicht genau die in die euklidischen Abstände der vom Anfang und vom Ende der Straße ja insbesondere wenn sie auf ihrem Weg noch irgendwelche Hindernisse umgehen müssen oder wenn sie sich ganz von der Geometrie lösen und beispielsweise Fahrzeit geschätzte Fahrzeit mehr nehmen oder auch ich hatte das Beispiel mit Autokorso W das ist zwar immer noch eine Oberfläche die Autokameras sowie aber nicht mehr Ebene ja also das ist natürlich alles damit erledigt sie müssen einmal zwischen je 2 Punkten zwischen je 2 Punkten wurde Roboterarm hin soll die Distanz berechnen vielleicht müssen Sie nicht mal für jedes Paar ja vielleicht gibt es ja genug Paare die so weit auseinander sind dass sie von vornherein wissen die brauchen Sie gar nicht zu berücksichtigen aber so so es ist mein 1. Näherung für jedes Paar von Punkten oder Roboterarmeen solle müssen Sie einmal vorweg die Distanz bestimmen und das reicht als Input damit haben Sie den gesamten Input definiert für das die SPD oder Manhattan Metrik hier das ist über
das was in der Mathematik ist dass die L 1 Metrik sie sehen dann an diesem Bild das woher der Name Manhattan Metrik kommt ich weiß nicht wie es Ihnen geht aber auch wenn ich es noch nicht so oft in jeder Kurve nicht sehr sehr einfach sich dort zurechtzufinden im Verhältnis beispielsweise zudem viel kleinere Stadt Städtchen Darmstadt das hat natürlich seine spezifischen Grund so die
ursprüngliche Version die wir eben hat mit dem Punkt in der Innen- und der kritischen Distanz ist natürlich Spezialfrage indem wir diese euklidische Distanzen hernehmen und in die Matrix Paten und Überraschung diesem speziellen Fall nennt man auch daher euklidische das TSB wenn die wenn die Distanz Werte die Bedingungen die Aktion meiner Mädrich erfüllen den als mittelfristiges Bild habe ich jetzt hier nicht aufgeschrieben sage ich nur dazu und insbesondere wenn es period in der Ebene sind und die Distanz der Punkte als kann länger genommen wird dann heißt es deutlich dass die SPD
so jetzt gehen wir zu unserm eigentlichen period das weiß eigentlich niemand so mehr der weniger nur Einführung kommen wir zu einer mathematischen Formulierung den Input haben schon geklärt ja in voller Allgemeinheit ist die Distanz Matrix die wir raus kann in die wieder reinkriegen als Import ja also die Dimension der Matrix ist mit Garage Mord ist also nur eine Dimension und die Matrix selber und wir könnten den Output eine Möglichkeit eine sehr kompakte Möglichkeit den Output zu beschreiben ist eine Bernotats zu sagen wir wollen eine Permutation der Punkte sprich endet benutzt Permutationen man ganz das N die diesen Ausdruck minimiert was ist dieser Ausdruck weil die Distanz Matrix und das hier von Sigma in das Sigma E-Plus 1 ist eben die kannte die Länge der kannte die Distanz von den Knoten der in der Permutation an jeder Stelle stets bis zu den Knoten den der Pomotat sondern E-Plus 1. Stelle stellt ganz einfach es gibt noch muss man natürlich noch dran denken dass dann der es ist ein geschlossener Züge das heißt also von den in wir müssen auch noch zusätzlich die Länge mit hinein in die Distanz von den Knoten der letzter Stelle steht bis wieder zurück zu den Knoten der an 1. Stelle steht so könnte es man modellieren hat bloß ein Nachteil ist alles mögliche nur nicht erfinden die ja wenn sie wenn Sie Permutation als als Werte da drin haben das passt mir oder meiner Schema von was wir in was wir vorhin eingeführt haben es lässt sich auch nicht irgendwie meines Wissens und mit Sicherheit auch ohne mein Wissen garantiert nicht irgendwie abbilden als affine Jahre Funktion so ich verstehe es bloß
kann nicht irgendwas muss von den Folien ach so ne das ist das ist schon die ganze vor ganze Formulierung aber noch keine Kalender keine bis keine Formulierung wie wir sie gebrauchen können als ihre P trotzdem ist die Folie vielleicht ich einem idealen Platz diesen bis hin zu ein paar Folien zu früh über
zwischendurch jetzt muss ich nochmal um arrangieren weil zwischendurch jetzt noch ein Beispiel aus der Praxis komme dass ich zeige Ihnen das hier
an dieser Zeichnung dass es tatsächlich aus der Praxis meiner Arbeitsgruppe eine Kooperation mit einer Tochterfirma von Philips in Einthoven und da geht es um folgendes sie haben sie haben hier eine PC Platine was hiermit mit bohrt bezeichnest dies noch nackt da also nix drauf erst einmal so die Komponenten die sind hier ja hier drinnen sie müssen sich vorstellen das ist so das kennen Sie hier da drin dass das ist ein Magazin das sind die von der für jeden Typ Frieden Komponenten die bisschen eigenes mal Magazin sein eigener Feder und die werden durch Feder drin immer hochgetrieben das heißt wenn wenn der Roboter eine Komponente weggenommen hat für die nächste nachgerückt so dass also die nächste zugreifende Delphi darf Komponente und zu platzieren 4 L Komponente immer an derselben Stelle ist so was passiert der Roboter haben um eine komme Komponente zu platzieren geht erst mal zu dem Gefieder zu dieser Stelle hin von den Komponenten wo kommt denn von den der Typ dazu zu platzierenden zieren ist da ab die er vor die drin sind biegt die auf und zwar geht das mit minder Pipette so in dem Moment wenn er auf die Kommunen der gekommen ist mit der Pipette wird die Luft raus gesorgt so das Bakom entsteht oder kann die Komponente hochnehmen so oder geht aber noch nicht direkt zum Wort sondern der Roboterarm GRG erst durch seine Kamera durch und zwar zurück zur Kalibrierung das heißt also der Roboterarm hat hat die hat die Komponenten im immer so ein klein bisschen vor ruckelt hochgenommen aber sie muss natürlich exakt platziert sein die darf nicht vorge- platziert werden um mehr über die Kamera geht und dann zum Wort geht in der Zeit wo zum Wort geht wird berechnet um wie viel wie viele sich der Roboter am in den nächsten in Kandidaten und dem Winkel leicht verändern muss um diese vor Augen wieder auszugleichen diese Information ist dann hier da entsprechend positioniert sich der Roboter am geht runter frage um wird wieder gefüllt mit Luft geht wieder hoch und die Komponente ist dort platziert wo sie hingehört ja also das Konstrukt jetzt ist es aber so dass nicht jede Komponente mit jeder Pipette zusammen passt das heißt also es kann schon mal passieren nachdem der Robert eine Komponente platziert hat und der jetzt eine Komponente abmontieren sollen platzieren soll die eine andere Pipette benötigt das er zunächst einmal dann zur Austausch einer gehen muss dort die jetzige Pipette an I vom eigens vorgesehenen Platz ablegt wo sie hingehört dann zu der andern Gebete geht die aufnimmt und dann erst zu der neuen Komponente und das ist natürlich zyklisch diese diese Operation das passiert ein paar Tausend Mal bis alle Komponenten platziert sind in der Realität es gibt mehrere solche Einheiten nebeneinander und das Bord durchläuft mehrere davon und die einzelnen die einzelnen Einheiten Plätzchen immer nur bestimmte Komponenten und demnächst einer platzierten wieder andere Kommunen so weit aber für unsere Zwecke reicht das eine Kur eine solch einer so betrachten sowohl die Frage ist folgende an Sie das sieht ja so ein bisschen TSP man sich aus nicht immer umgehen und platzieren Feder die Kamera platzieren File Exchange vielen nett ne Exchange Ex-Champion wieder Kamera Platz platzieren und so weiter immer so zu nicht zu sehr sind die ist es ist keines da die Frage bitte sie müssen period mehrfach anlaufen er genau wenn diese dieser die mir im Gesicht vorhersehen es ist ein Teil des Outputs die Informationen unter wann Sie hierzu Ex-Champion wird kommen es nicht das ist der Punkt an dieser Stelle haben also aber der Hauptpunkt sie sich erst einmal Sie müssen wir immer wieder an 7 Stellen vorbei an der Kamera vorbei an dem an dieser Stellen gehen mit einem vieler wäre meiner beim TSB geben Claude nur einmal durchläuft heißt das also dass es kein Testspiel ist obwohl es im Abschnitt über bestellt ja bitte bitte das ist so Sie meinen dass man dass man nicht eine Kamera eingibt sondern sondern so viele Kameras wie man potentielle drüberläuft
ja sie haben abwägen sie haben Abhängigkeiten und das auch noch ohne Komplikationen drin sie geht erst zur Kamera und dann zur Platzierung genau es ist ja ja es ist dem TSP nicht nur war dass man solche Abhängigkeiten hat dass man zu 1. Kammer geht und dann zur Platzierung also es verdichtet sich immer wieder Verdacht dass es keine es sehe ich das richtig weder ach so Sie wollen hier vor der Kamera 6 Schälchen mit ein kleinen wird haben wer die Maschinenbauer werden nicht bereit sein 0 um ihn ihres so für Probleme zu lösen hier das Design des ganzen Einheit anders zu gestalten wobei sich auch kleine Beträge summieren hätte nennt ja ja also was wir brauchen und was sie vollzogen haben ist ein Perspektivwechsel dass wir insbesondere bei der Frage was eigentlich die Knoten sein sollen in einem solchen und was dann gemäß dem sprechen was und die kann eigentlich sein sollen dass wir sagen ich würde Vorschlag nicht von den Kommunen zu sprechen sondern er von den Erziehungsaufgaben zu sprechen jede Platz Jungs Aufgabe ist die Knoten ja also eine Komponente von dem Typ dorthin zu platzieren dieser vorgegebenen welche Komponente wohin platziert werden soll eine Komponente von dem die dorthin zu platzieren ist eine Erziehungsaufgabe ist ein Knoten eine komme würden davon Typ in von dem Typ deuten zu platzieren ist ein Platz Jungs Aufgabe und dazwischen gibt es eine Kante weil zwischen je 2 Knoten eine Kartennummer Nummer geht was ist die Länge dieser kannte der stellen sich vor Sie sind Sie haben jetzt die eine Komponente hier platziert ja sie ist wieder frei wie der Roboterarm es wieder frei was Neues zu machen dann wissen Sie was von die dann wissen sie ganz genau wie der Weg aussieht bisher die nächste Komponente die die an und hat sie uns Aufgabe erledigt hat nämlich ein muss je nachdem also wenn die Pipette dieselbe ist dann muss dahin gehend zu der um die neue diesen Weg denn sie wissen genau hier liegt das ist nämlich von dieser diese Erziehungsaufgabe beinhaltet auch Kollegen Daten auf der Platine das heißt wir wissen ganz genau welchen Weg hier wir hier hin zu tun haben zu dem zu dem Feder in den Kommunen wird diesen Typ drin sind dann wissen wir was als nächstes was hier für einen Weg ist das ist übrigens das habe ich auch ausgelassen das in der bleibt ich bei der Kamera stehen noch mehr Komplikationen denn der fährt über die Kamera auch über also in zum schönen Bogen also wir freilich nicht nicht die hier in jedem Sinne nicht länger eine nicht in ihre Bewegung sowohl was Beschleunigung und Abbremsen angeht als auch was was die Wegstrecke denn die Cover angeht ist nicht linear aber dass wenn wir die Kantenlängen wäre über mir das als eine Kante auffassen hier bis zu dem Punkt wo wo dieser Erziehungsaufgabe erledigt ist dann machen das ist uns egal wir berechnen einmal vorab was uns das an an Zeit kostet diese Bewegungen auszuführen und dass die Summe von dem eines und die Länge der Kanther genauso wenn wir zu Austausch einer gehen müssten ja wir das wissen wir ja weil wenn für eine 1 mit kannte wissen wir das auch wird aus solch einer gehen müssen oder nicht weil es kann weil die also Closet sind Erziehungsaufgaben und zu der Erziehungsaufgabe gehört auch der Typ lekom Komponente und wenn wir den Typ der Komponenten haben für für die beiden Knoten dann wissen wir auch ob zwischendurch erbitterten Wechsel notwendig ist dann wissen wir also auch ob wir als ob wir noch in die brechen ob ob der Weg den wir gehen müssen ob wir wieder noch zuerst den Weg zur Austausch Einheit eine bestimmte Stelle wir wissen auch an welche Stelle er den machen müssen diesen Weg wir wissen an welchen Stelle wir hier drin gehen müssen um die neue Gebete aufzugreifen und wir wissen von hier aus wie der Weg aussieht und hier wieder zum wiederzukommen kommen wir wenn wir diesen Perspektivenwechsel vollziehen und die Platzierung so Aufgaben zu Knoten machen und der Gesamt weg vom Ende einer Platzierung so Aufgabe bis zum Ende der nächsten Erziehungsaufgabe als Kräfte länger leben dann ist das und bei also erst dann wurde ein aus den
Gründen die Sie genannt haben 2. Antwort das
Jahr aus den Gründen die wir jetzt noch zusätzlich erarbeitet haben vielleicht noch hier also das ist das was sie steht sind das ist genau das was wir es arbeitet gesagt haben brauche ich immer durch aber hier die Bober muss noch interessante das ein schönes Beispiel für nicht Mitteldistanz werde den wenn ich zuerst Erziehungsaufgabe und dann wird sie uns Aufgabe B danach gleich danach erledige kommt natürlich nur andere Fahrstrecke andere Fahrzeuge raus also nicht S und danach mache so es
ist natürlich nicht die ganze Geschichte aber es ist natürlich nicht nur ein TSB sondern es gibt Zusatzbedingungen es geht gibt es für das klingt dass bestimmte Kommunen vor einer platziert werden müssen und und so weiter und solche bedingt passt natürlich nicht mehr in ihnen ins Rahmenwerk vom in die Problemstellung rein und was man da die interessante Frage für Forschungen Algorithmik ist beziehungsweise das war schon viel geleistet worden ist im Laufe der Jahrzehnte es gibt unheimlich viel Literatur zu Algorithmen für das TSB oder zu Algorithmen die auch für das die SPD verwendbar sind falls es da es falls sie dazu im Interesse haben lade ich Sie gern im nächsten Semester zur Vorlesung Optimierungsalgorithmen ein wo das TSB eines unserer Arbeitssphäre ist was ich immer wieder gerne als Beispiel Herrn immer um die fehlende algorithmischen Ansätze zu diskutieren ja wie Karte welche der Ansätze die so gibt für ist oder eben auch neben anderen Problem stellen auch fürs TSB 1 an wenn da welche davon kann man gut übertragen auf den Fall dass es noch zusätzliche sei in dem Bedingungen gibt wie diese das ist aber etwas was wir hier nicht mehr diskutieren können diese veranschlagen die sind im 1. so
jetzt aber ohne Gnade endlich zur Mathematik wir werden das heute nicht ganz schaffen wir es da doch eine ganze Menge zu sagen gibt so wir haben eben gesehen der naheliegender Ansatz die Lösung als eine Permutation der Punkte zu beschreiben ist zwar schön bündig und auch für mathematisch aber leider nicht linear nicht auf ihren linear also müssen wir ein bisschen Arbeit reinstecken um einen anderen Ansatz her zu kriegen wir tatsächlich affinen linear ist eine andere Modellierung her zu kriegen und das machen wir auf eine Art und Weise ähnlich dem was sie auch schon gesehen haben zum Beispiel als wir kürzeste Pfade als OBL Modell eingeführt haben für jede potenzielle Kanzler also für jedes Paar von 2 Punkten finden 0 1 variabler einen mit der Bedeutung diese Variable für die 2 Punkte ist 1 genau dann wenn die Kante von dem 1. period zum zweiten Punkt in der Rundtour drin ist so was haben Sie schon gesehen im Zusammenhang mit Christen Faden das dort auch dass wir das genauso modelliert haben er der Wert für eine Kante ist 1 genau bedeutet dass diese Kante im Pfad drin ist in dem Fall den wir berechnen so die Zielfunktion ist damit sofort erledigt wenn ist genau dasselbe was wir auch schon in anderen Fällen unter anderem kürzeste Pfade gesehen haben wie die Zielfunktion dann aussieht also die macht uns keine Kopfschmerzen seine nehme mit denen sein die uns Kopfschmerzen machen dafür sorgen dass das dass das Ergebniss einer Rundtour ist und nicht irgendwas so wir summieren über alle echten kannten also wir lassen den Fall einer Kante von einem Knoten zu sich selbst natürlich aus und was müssen wir summieren na ja die x-Werte 7 0 oder 1 und 2 1 genau darum wenn diese kannte darunter drin ist das heißt also das kennen wir haben schon mehrfach gesehen dieses Produkts aus die er dann XII hat das ist 0 wenn die Karte nicht drin ist und es gleich die J wenn die Karte drin ist was wir also effektiv 4 aufsummieren sind die die Werte die Distanz Werte derjenigen kannten die in der runter drin sind ja damit es die Kostenfunktion ist die Funktion dieser minimieren wollen mit nicht allzu viel Probleme nach schon modelliert
jetzt comma zu den Bedingungen wir machen uns klar so ähnlich wie bei wie bei Pfaden bei Christen fahren von A nach B aber doch ein bisschen anders haben sind in diese Situation haben wir hier bei dem bei uns am kürzesten wahre Problem haben wir für jeden zwischen Know und sie ändern sich für den Ausgangs- Knoten das soll der Fahrt genau einer rausgehen bekannt haben für den eingangs Klon wenn sie gluten- sollte der Pfad genau eine eingehende kann da haben und für jeden zwischen Knoten wenn der zwischen den und dem Fahrer drin ist heißt es genau einer reingehen und genau eine ausgehende und wenn der zwischen nicht im Fahrtwind ist heißt es genau 0 reingehe genauen 0 rausgehen der das war die Logik wie wir das kürzeste Pfade Problem modelliert haben hier ist es viel einfacher wir wollen dir jeden einzeln Knoten genau einmal erwischen in der Rundtour das heißt wir Nasenbluten gilt genau eine eingehende genau daraus kannte und das haben wir schon mehrfach gesehen wie man sowas modellieren kann hier wir summieren hier über alle aus den Knoten I herausgebenden kann also eine allg war ein Quartier Infizierung über die Knoten i und wir summieren hier über alle rausgehe aus ihrer ausgehenden Kanten da die Excel 0 1 Werte sind und die Forderung dieser Bedingung ist dass die Summe 1 ist wieder dieselbe Logik wie wir sie schon hatten eine Summe von 0 1 werden soll gleich 1 zu 1 das bedeutet das kann nur funktionieren wenn genau eine dieser 0 ein 2. 1 und alle anderen 0 sind und dass wir für freigegebene kann Hamas damit nicht so richtig nicht sonst würde die wäre die Überschriften bisschen merkwürdig sonst würde hier nicht fürchteten sondern alte melde ist der Eltern stellen was damit hätten so Sie wollten sagen genau hier so was
zum Beispiel Jahr wendig man die Knoten so in der Ebene platziert sind und wenn wir wieder der kritischen Distanz der Einfachheit halber nehmen dann ist das hier sicherlich eine bessere Lösung als eine Rundtour über diese Knoten eine mit mir im mit mit kleinerer Gesang Gesamtlänge und diese und ist nicht ausgeschlossen denn für jeden als einzige Bedingung bisher haben wir für jeden einzelnen Knoten das genau eine kann der Reingewinn genau eine kann daraus Geld ja und diese Bedingung ist erfüllt können also nichts dagegen sagen wir müssen also noch an unserem Modell arbeiten wir müssen noch kucken wir müssen noch Bedingungen einfügen die 2 Eigenschaften erfüllen die 1. Eigenschaft die diese Bedingung erfüllen müssen ist dass Sie solche Bilder ausschließen und was wir nicht vergessen dürfen die zweite Eigenschaft das keine Rundtour ausgeschlossen wird durch die Bedingung dass keine Rundtour aus der Lösungsmenge rausfliegt denn es könnte ja auch wenn nur eine Rundtour rausfliegt es könnte ja geradezu zufällig die optimale gewesen also das ist die Aufgabe um um das Problem jetzt nach Hause zu bringen zusätzliche Bedingungen die dafür sorgen dass solche sub Touren nicht mehr möglich sind aber die die trotzdem auf seiner Seite keine echten Rundtouren aus schließen so das ist die
1. einfache Möglichkeit wie man das machen kann ja nehmen wir uns dieses Bild wieder ja das ist dasselbe Bild wie eben auf der letzten Folie und sie sehen schon ich kann hier irgendwo zwischen 2 solchen sub Touren kann ich einfach mal die Grenze ziehen und sagen also auf der einen Seite ist meine Menge S und alles auf der anderen Seite ist eben es Komplement aber ich habe den die kann sich jede zum mich jetzt auch hier ziehen können also irgendwo so dass jede Soutou entweder zu er ganz zu S oder ganz nichts es gehört irgendwie habe ich das sehen können so und für jede solcher Zerlegung in einer Menge S und eine Menge S Kompliment der Knoten also Knoten viele solche Zerlegung führen wir eine Bedingung 1 die fordert dass mindestens eine Kante von mache es quer geht die diese Bedingungen zu formulieren es ganz einfach hier hier steht schon Jahr mindestens 1 1 i Ort es ihr zunächst wird größer gleich 1 mindestens eines dieser Werte muss 1 sein was für Werte sind das das sind Werte wo das die aus der Menge es ist und das wird aus der Menge es könne ja wenn wir für jede Art Teilmenge die nicht mehr ist und die auch nicht die gesamte Menge ist sondern die das wirklich schön die Knoten in 2 echte Mengen echte Teilmengen separiert wenn wir für jede von ihnen diese Bedingung reinhauen dann kann dieses Bild nicht mehr entstehen ein solches Bild und deren keine Rundtour rausgeschmissen da natürlich gilt bei einer Rundtour für jede Teilmenge wieder Zerlegung das von der einen Seite in die andere sollte mindestens eine kann das sein aus Ihrer Hamas damit gelöst also wir damit fertig habe ich den Mund zu voll genommen dass sie gesagt habe das wird uns Kopfschmerzen bereiten bitte ja es müsste nicht ihre Songs von der Kommune die der einer verbunden sein sondern wenn sie die die Bedienung bei der dass die Menge so dass Quelle ist die sagt nur von irgend einen Knoten längst von einer dritten längst zu einem der 7 Knoten rechts muss es eine Kante geben potenziell mehr aber mindestens eine und wenn Sie sich hier irgendeine Rundtour vorstellen die über diese 10 Knoten geht egal wie die aussieht egal ob die dass die schöne Rundtour ist ja einmal so um oder Kraut und Rüben oder sonst wie sie werden garantiert immer eine Kante haben die von dieser Menge in diese Gesamtmenge übergeht von diesen 3 Knoten auf diese 7 Knoten also Sie haben damit keine runter ausgeschlossen nicht das war zu viel verlangt sie könnten da sie wären keine also Sie machen es für jedes ist was man so was hier in diesem Bild es gibt 3 wieso 3 wieso 3 verschiede- man erst dass ich nicht ich sehe entweder Interpretation entweder 2 oder 4 also 2 Striche die man so ziehen kann und je nachdem es auf der linken Seite also auf der rechten Seite sind 4 verschiedene Fälle ich weiß nicht wie Sie auf 3 kommen bedenken Sie das beide S und es quer nicht leer sein dürfen dann ist natürlich schlecht wenn er so dass Fehler sein dürfen ein Knoten aus einer leeren Menge in einer Art eine Kante aus aus einer sehen Blutmenge in eine andere Kücken Menge zeigen zu lassen dürfte die Lösungsmenge mehr machen aber das vom würde nicht gefordert wird nur echte zerlegte echte Zerlegung gefordert also ich denke schon ich bin mir sicher dass diese Bedingungen hier keine runter ausschließt bei jeder Rundtour wenn Sie da irgendwie die Gluten Menge in 2 echte Teilmengen separieren echte Teilmenge ist wichtig dann muss es irgendwo eine kann doch der und will gegen die von der einen echten Teilmenge die Anrechte übergeht und mehr würde nicht so gefordert bitte was ist denn eine äußere suppt einer also so durch den sie vor wir vermisse sich so schönes Beispiel so wir haben ein abstraktes Beispiel wo es gar keiner Kirche gibt wie definieren sollen dann die also Soto war 10 Reise zwischen beiden äußeren der Nein stimmt jetzt jetzt verstehe verstehe ich wie Sie auf 3 gekommen sind auch wenn Sie es mir nicht erklären konnten oder vielleicht ist es so was musste ich keine zum Beispiel auch diese 4 Knoten als eine Menge es ja lassen Sie sich ja also inzwischen gehört gehört der folgende Spruch zu mein Lieblingssprüchen ein Bild liegt mehr als Tausend Worte sie werden verstehen dass ich und meine Frau meine eigene Folien sind die mich zu diesem Spruch verleiten ja lassen Sie sich nicht so sehr von dem Bild verleiten auch auch auch diese Wege kann die Menge beziehungsweise auch diese 6 und Noten könne man ja es wir die alle ihre Zerlegung in nicht echte Teilmengen nämlich Dateien Entschuldigung wird ja durchlaufen also ich denke mit ein bisschen Kontemplation werden sie auch mehr zustimmen es ist damit keine und tun ausgeschlossen sind aber sämtliche so Tour Bilder sowie dieses Jahr ausgeschlossen wenn sie so und super Bild haben dann werden sie hat es entsprechend und schon haben Sie eine bedingt gefunden die von diesem Bild verletzt Ort und eben umgekehrt dass keine Rundtouren ausgeschlossen sind ergibt sich da aus ist aber es noch mal meine Frage sind Sie jetzt damit zufrieden fragen freilich mal so wenn Sie das ist gut was da steht auf dieser Folie sie haben sich auch einmal er habe sie glaube ich das gemeldet wer was ihre unsere ja wie Ungleichung Semstern es wurden sehr viele also 2 hoch N minus der beiden Fälle dass es länger und es Quelle ist die beiden Fälle noch abgezogen aber bis auf diese Zweifel sind zwar auch n vielmehr er das das kennen Sie was ist 2 hoch 10 ungefähr tausende sie also ungefähr Tausend also 22 eine Million was ist 32 eine Milliarde ja sehen Sie wissen das also wir brauchen das nicht mehr wie Energie D 2 durchzuexerzieren Stade ja das sollte ein stören ja eine exponentielle Anzahl von Bedingungen ist ein Grund zu sagen wir sind noch nicht fertig Ja weil sie allein schon das Problem haben dass sie auch bei sehr kleinen Größen bei sehr sehr kleinen Größen das oder gar nicht im Rechner reinkriegen von Lösungen comma gar nicht zu sprechen also müssen wir müssen aber reinstecken aber ich vielleicht
noch hier diese eine neugieriger Seiten Nebenfrage warum nicht gleich ein viel größer gleich 1 und dem Grund habe ich hier schon die Antwort gegeben so dass die da nicht drüber nachdenken können weiß ich jetzt nicht warum ich das gemacht habe aber wenn hier gleich stehen würde größer gleich wer tatsächlich die Lösungsmenge sämtliche Rundtouren wären ausgeschlossen durch diese bitte diesen Satz von Bedingungen warum weil wenn sich junge Rundtour ja also wenn wir von einer ordentlich großen Größenordnung sprechen ja bei 3 Knoten dann glaube wir so nichts passieren aber bei bei ausreichend vielen wurden kann man das natürlich in der Umwelt jederzeit einen so sehen sich die sowohl durch ihr und sie ziehen die Grenze zwischen S und Square so das E zweimal durch die Rundtour durch Geld ja dann haben Sie von der Sache ist wer diese kannte und gleichzeitig noch diese kann der wenn sie nicht größer gleich haben sondern nur gleich 1 ist damit ist dann durch diese so durch die Bedingungen die zu diesem es gehört diese runter ausgeschlossen es geht also nicht also müssen wir hier großer gleich neben mir eine kleine Unterschied dann gleich kleiner Unterschied ein Bild und schon wird aus der richtige Lösungsmenge eine Lehre Lösungswege oder umgekehrt je nachdem wo man das bitte gibt ja also wir müssen noch was tun um zu einer befriedigenden Lösung zu kommen das schaffen wir aber zeitlich heute nicht mehr das macht doch keinen Sinn dass jetzt anzufangen deshalb möchte ich Sie wissen die eigentlich mit der Zeit auch mal wieder um welches Sie hier entlassen und ihnen noch einmal eine schöne verkürzte Woche wünschen für Küsse Studienwoche ändern sich daran das am Donnerstag Feiertag ist und etwas mit und leider habe ich keine der Veranstaltung am Donnerstag okay gut bis nächste Woche
Loading...
Feedback

Timings

  657 ms - page object

Version

AV-Portal 3.21.3 (19e43a18c8aa08bcbdf3e35b975c18acb737c630)
hidden