Merken

Einführung – Beispiele und Formulierungen

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
eine zu hohe ja heißt mln herzlich willkommen mein Name
ist Alexander Martin und Nicole Nowak wie wir beide werden die Vorlesung mit Optimierung betreuen ich mich vielleicht erst mal kurz nicht selber vorstellen ich hab vor sind der 25 Jahren glaube ich Größenordnungen selber Mathematik studiert Wirtschaftsmathematik genauer gesagt bei mir die Kombination Spaß gemacht hat Informatik Wirtschaft Wissenschaft und Mathematik in Kombination das in Augsburg damals und angefangen zu promovieren in der Zeit hat mein Doktorvater also ich probiert hab mittendrin Gesagte geht es nach Berlin gut nix als übriggeblieben als auch als Bayer mit nach Berlin zu gehen sozusagen ich hat es nicht bereut ich war dann 8 Jahre in Berlin hat dort promoviert habilitiert bis mich dann der Ruf hier nach Darmstadt alt hat das war dann 2000 sich jetzt etwas mehr als 8 Jahre an diese Universität mein Steckenpferd in der Mathematik ist genau die diskrete Optimierung also genau das was und setzen diese Vorlesung die die Grundlagen anschauen wollen was genau diskreter Optimierung ist und was man so alles machen das wenn ich vielleicht dann gleich noch ein bisschen erzählen bevor das tun wollen erst noch ein paar organisatorische Dinge klären und ich fange einfach mit dem Englisch sprachlichen 1 vergab das Anliegen sozusagen da sich die Vorlesung auf Englisch halte nun weiß ich nicht ob das jetzt wirklich von allen gewollt nur unser Vorschlag wäre hier ein Kompromiss weil insbesondere Skripte ich auch gleich noch was zu sagen sie sehen auch gerade das hier wird aufgezeichnet sogar die Vorlesung des und seine Liebe das sind Deutz zu behalten allerdings dass nur eine englischsprachige Übung anbieten dass sie diejenigen die sozusagen das englische praktizieren möchtest dann sowieso den interaktiven solle deutlich besser als in der passiven das für diejenigen die jetzt da insbesondere nicht gefragt haben sind im Moment auch noch gar nicht daran glaube ich von daher hat sich vielleicht auch schon wieder erledigt da also ist ne Handvoll also je nachdem wie gesagt die Person die mich gefragt und sind noch gar nicht da wären sie so wieder anders überlegt er hat gesagt wir klären dessen 1. Vorlesungen und wenn dann sich eine Mehrheit dafür findet dann dann bieten was sicherlich wenigstens die Einübung Menge Speichernetz alle hier geschilderten werden alles auf Englisch auf die Vorlesung zu machen hätten auch das tun können aber ich glaub so die Begeisterung die so scheint es nicht ganz so der Fall zu sein deswegen Vorschlag erst mal wir machen die eine mir machen Vorlesung Deutsch wir haben da der 4 Übungen und und ich lieferte dann auf Englisch sollte
sich jetzt wirklich niemand richtig dafür begeistern von uns kann jeder Deutsche mindestens so gut wie Englisch dann dann Switch einfach wieder auf Deutsch es dann Sonne mit n was die Übungen selber betrifft wird Nico Lumma gleich was dazu sagen vielleicht zur zur Vorlesung selber einen noch es gibt gibt es gibt sogar ein Stück weit mehr als es gibt es gibts ein halb fertiges Buch ich wurde vor Jahren schon mal darauf angesprochen ob ich nicht aus den Vorlesungen ich gehalten hat die Einführung die Optimierung der damals so ein bisschen anders ausgesehen da ich gleich noch mal drauf kommen und diese Vorlesung nicht ein Buch machen möchte ich wollte das nie tun aber Springer-Verlag hat gemeint das ist ein vernünftiges Konzept was ich hier versuche ihnen beizubringen hat könne man Buch draus machen ich hatte das den vor 3 oder 4 Jahren versprochen zu tun und hab dann auch dran gearbeitet und bin ich Dekan geworden hat gesagt namentlich bekannte Ende bin dann schreibe ich das Buch Werdegang ist leider Vizepräsident geworden und die Aufgaben werden immer mehr und ich habe es versprochen nachdem ich Vizepräsident zu Ende wenn dann hab ich ein Forschungssemester manche reicht das Buch zu Ende ist auf der andern Seite ist natürlich jetzt eine sehr gute Gelegenheit dieses Buch noch mal gemeinsam doch zu arbeiten und da möchte ich Sie einfach bitten laden Sie sich das Buch wenn
geht unter oder immer nur Teile bei dessen ständig aktualisieren bei man also auf ist hier der ist sich bereiterklärt hat auch immer sozusagen das was sich an den Neigungen maroder oder Handskizzen dann auch immer gleich mit einzustellen in das Skript sodass es durchaus Sinn macht sich immer nur Teile runterzuladen es zwischen 330 Seiten schon das Buch also das jedes Mal ein runterzuladen Ausdruckes vielleicht weniger sinnvoll insbesondere weil sich vieles daran tut aber mir wäre es natürlich recht wenn sie wirklich auch nach diesen Buchung Stückweit arbeiten weil sozusagen immer das Lesen immer das Kontrolle ist umso besser wird es natürlich am Ende ich werde immer wieder die Hinweise machen wo gerade aus dem Buch was machen also wir werden sich genau 1 zu 1 machen weil die Einführung bisschen anders ausgesehen hat als in dem Buch Bug Buch dargelegt dass das der der gesamte nichtlineare Optimierung Spieler keine Rolle des Buchs soll das Gerät Optimierung heißen und deshalb kann man die Schwerpunkte leicht verschoben das heißt wir müssen hier noch ein bisschen was nachholen was in dem Buch sozusagen bei davon im Kapitel ist aber an sich die Inhalte sind alle da sie werden auch auf der Internetseite dann ist ursprünglich Skript finden was ich zuletzt 2006 gelesen habe was mehr der weniger dem Verlauf entspricht so wie wir es uns in der Vorlesung anschauen wollen also für sich frei bei der anzugucken was Anmerkung Verbesserungen Rechtschreibfehler inhaltliche Fehler betrifft wäre es mir ganz lieb wenn sie sich an dem Buch orientieren weil das ist das was weiter aktualisiert wird und das ist das was auch ständig verbessert werden sollte im Garten haben n Thema weil sich mit der von ihnen noch im Diplom werden im Master Bereiches weil ich dachte dass unterschiedliche Dinge an bieten wenn erst mal vielleicht die Frage wer ist im Master oder in der Master sind eine Handvoll der Robert leise also über 100 schwer nehmen also nahm eine eine Onkel also das heißt Sie brauchen wir wahrscheinlich am Ende irdene Prüfung zu dieser Vorlesung aber solange der Handvoll ist dass mein Vorschlag immer nur mündlich bevor wir wenn das die meisten eher positive sich denn dort möglich ist die angenehmere Prüfung vermutlich dann wenn setzt zwar über 20 30 gewesen wären dann hätten wir dann hätten wir überlegte die schriftlich zu machen also dann und dann würde ich sagen wenn es nicht signifikant mehr werden oder sich das noch überlegen seine Prüfung zu wollen dann dann dann halt den mach mal die mündlich und mündlich heißt halt dann wann immer sie aber Lust dazu haben sozusagen müssen halt rechtzeitigen Termin ausmachen und gute Organisation von Übung Übergewicht vielleicht einfach mal Nicole das sind er wurde dazu sagt ist das ist bei sie ein pro bei war ein sein er ich weiß nicht ob Sie hat bei so weit ich weiß ich sie sie war auch die ja noch sagt er war ein nein ist es nicht was wir was wir Voraussetzung ist es wenn Sie in der Optimierung Master oder Diplomarbeit schreiben wollen weil wir relativ viel Anfragen haben was Diplomarbeiten betrifft und dann sagen wir das Minimum ist dass wenn es einer kann dieser 3 Haupt Vorlesungen optimieren 1 bis 3 erfolgreich mitgemacht haben und in das was sozusagen einen erfolgreichen Beteiligungen Übungen A Mehrheit ich habe wieder her mehr wenn ich mal ein Hefei gut ich gut eine Anmerkung kleine sehr die gesehen hier laufen 2 Kameras also die Vorlesung wird auch aufgezeichnet und auch online gestellt also wenn Sie dann Interesse haben oder dann mal nicht da sein können können Sie sich die auch jederzeit noch im Internet runterladen es wird wo er aber allerdings habe ich verstanden Größenordnung ein 2 Wochen dauern bis sozusagen der aktuelle Mitschnitt zu zahlen dann im Internet zur Verfügung steht es ist auch ein Stück weit Experiment weil die Matte mal machen ja gerne Tafel Vorträge und das steinige Herausforderung zu sein für Videoaufzeichnungen in den Tafeln Mitschrift sozial einigermaßen vernünftig wieder geben zu können deswegen gedacht dass noch mehr gewisse Nachbearbeitung sonst es dem klassische Szenen für Powerpoint Vorträgen der Vorlesung Gänsefett aus Informatik oder so dann wäre das ganze Stück weit einfach also wir versuchen mal die Tafel zu digitalisieren dass die Mathematik auch in diese Onlinewelt sozusagen Einlass bekommen und das Stückweit Versuch ich hab dieses Ding leise das Mikro funktioniert nur für die Kameras damit sie auch trotz der nebenbei noch reden können und trotzdem meine Stimme auf der auf den Tätern am Ende drauf ist ja gut ansonsten hab ich von meiner Seite erst organisatorisch nichts mehr haben Sie noch Fragen Anmerkungen bevor es inhaltliche einsteigen gut wenn dem nicht so ist dann dann würd ich einfach dann erst mal ein bisschen anfangen was das geht optimieren fand leider auch gleich dann mit ein paar Beispielen an aus meiner Wahrnehmung gut wie gesagt das ist mein Steckenpferd von daher zähle ich natürlich auch mal Stückweit mit der gewissen Begeisterung davon aber ich glaub die Begeisterung ist hat als vielseitige Ursachen wenn Sie wenn Sie mal schauen was in der Einführung bislang gehört haben wir in der 1. Vorlesung zu haben sich im Großteil mit lineare Optimierung beschäftigt das heißt Sie haben das System von linearen Nebenbedingungen und Gleichungssystemen sie eine lineare Zielfunktion und sie möchten jetzt über diesen Dingern Ungleichung sozusagen Optimallösung bestimmen wobei alle Variablen kontinierlich sein dürften was wir jetzt fordern wollen ist dass einige oder alle dieser
Variablen Ganzheitlichkeit Anforderungen haben also mehr als ersetzen X aus aber wenn doch X aus der hoch allen dass man erst mal überlegen denken das ist ja einfacher weil ich aber viel weniger Möglichkeiten 1 X aus er auch in's interviewt worden sehr viel mehr Lösungen 1 x aus der doch n dem ist aber nicht so das Problem auch im Sinne der Komplexitätstheorie wird damit ich einen schwer das Problem immer noch genauer identifizieren was das heißt es in dem Sinn polynomial Algorithmen so wie wir das zivilen Jahre Programmierer sind und dieser eine kennen gelernt habe die Methode gibt es für ganzzahlige Programme nicht na und das heißt wir müssen uns was überlegen was man stattdessen tun können um solche Probleme überhaupt lösen zu können es kann man sich natürlich fragen warum machen wir das überhaupt ist es überhaupt sinnvoll so zeigen wir zusätzliche Forderung ist aus der doch allen und ja die 1. weil man kann damit wahnsinnig viele Probleme aus der Realität mulieren dazu bald X aus der doch n haben können sie Entscheidungen modellieren ja Ja-Nein-Entscheidungen sie fordern da sich die Entscheidung setze war aller Vereins treffen Sie sich nicht setzen Sie sie auf 0 ja also dann damit haben sehr der Variable aus 0 1 sogar das ist der häufige Fall eine Anwendung vorkommt das heißt sie müssen letztendlich diskretere Ganztag Optimierungsprobleme sind kann so kann man auch Stückweit Meister von 10 Entscheidungs passiert Optimierungsprobleme zu müssen Entscheidungen treffen oder Randbedingungen wenn sie mal überlegen wie oft das in der Realität vorkommen der Praxistest im täglichen Leben treffen sich ständig Entscheidungen und welchen Randbedingungen haben im Kopf auch irgendein Ziel funktional was sie erreichen wollen in kürzester Zeit in ihrem die ihr Studium zum Beispiel zu beenden da Treffens Entscheidungen die oder die Vorlesung oder wie auch immer oder auch selbst im täglichen Leben ich auch wahr machen was und so weit also ständig werden sich solche Entscheidungen und interessanterweise ist auch dass viele die diese Bedingungen die aus der Realität kommen sich als lineare Randbedingungen formulieren lassen Kaiser darüber philosophieren warum dem so ist häufiges ist einfach so dass der Mensch an sich ist ist man sogar sehr einfach er gerne linear denkt ja also sozusagen jemanden mal als Beispiel beizubringen wie stark Exponentialfunktion wächst ja ist ja für viele gar nicht so richtig begibt begreifbar wenn Sie mal schauen wie diesem kennen Sie sicherlich das Beispiel dem Schlachtfeld Bourbon auf den auf das 1. Feld ein Reiskorn Blick auf das 2. 2. auf das 3. 4 und immer verdoppelte Reiskörner man dann am Ende hat Mehr und dann kommt irgendwie sowas raus und da Quadratkilometer Fläche 100 Meter Höhe das ist eine Zahl die kann man irgendwie nicht fassbar machen 2 64 klingt jetzt gar nicht so allzu viel aber plötzlich wenn man sozusagen billig darstellt ist sehr viel das heißt wie ich meine meine Auffassung ist würde und ist sich noch häufigen Diskussionen zu zeigen die Findung Masuch zu beschreiben oder die Randbedingungen sind sehr häufig der Natur es sei denn die Physik geht dann 3. nicht Genialitäten auf physikalische Phänomene beschreiben wollen wie die Flüsse oder kann auch oder nicht Fluss 1 Gas Gas ist doch Leitungssysteme der gleichen oder irgendwelche Strömungs Mechanik Aspekte wie zum Beispiel wie Flugzeug fliegt oder dergleichen da kommen dann aber die ,komma Statistik oder aus der Natur diese Prozesse die dann diese nicht Genialitäten enthalten aber wir wollen uns jetzt in der Vorlesung wie immer um diese diskreten also wären ganz als Calls beginnen und wie an Bedingungen dabei und unser Ziel wird immer sein Lösungen zu Methoden zu finden die global optimale Lösungen finden in der linearen Welt konnte das immer noch werden aber sehen dass dieser Aspekt wegfällt der fehlt sowohl jetzt weg der diskreten Optimierung aber einerseits aber wenn sie dann noch Interesse an einer nichtlinearen Optimierung Felder ebenso weg ja in beiden Fällen schafft man es nicht mehr mit den gängigen Methoden globale optimale Lösungen zu finden sondern legen nur lokale wird es geben kann man Stück weitergehen und auch mit Toten bereitstellen die letztendlich beweisbar gute wenn nicht sogar optimale Lösungen finden die aber dann nehmen wir das Case exponentielle Laufzeit haben und genau in diesem schied Spannungsfeld wir uns bewegen und uns auch verschiedene Methoden anschauen verschiedene Modelle Jungs Aspekte werden auch den Übungen viel modellieren ist es wichtig für Versagen wenn man später Anwendung lösen will dass man ein dieses Modell aufstellten das gar nicht so einfach und gutes Modell aufzustellen dass es auch was was bislang ein Stück weit in der Mathematik bislang auch ob etwas vernachlässigt wurde sozusagen die finnischen gewichtiges Modell ja und häufi Chapman Modelle entwickelt die nicht gut zur Anwendung gepasst haben oder gut zur Anwendung aber dafür gab es dann keine mit roten und genau dieser Dreiklang Anwendungen Modell mit roten das muss passen sozusagen um wirklich dann auch Problem in den er in der Realität lösen zu können und da werden wir später sehen wenn Sie erst mal der Marine fertig sind sie gehen dann irgendwo raus die Anwendungsfälle sind sehr vielfältig ist in den Energiebereich den Transport und Verkehr in der Logistik im Finanz Wirtschaft und und und also die treten überall auf allein wir haben zum Beispiel unsere Gruppe allein hat schon Projekte mit der Deutschen es sind mit Lufthansa mit er und Gastransport also aus den unterschiedlichen Bereichen der eben diese Probleme auf aber sie treten dann ab dort auf wo sozusagen die Spezialisten vor Ort heutigen Ingenieure sind an das Hintergrundwissen haben mit anderen Methoden ran gehen als wir das vielleicht als mal war der gewohnt sind was man dem gelangen wollen wo wir auch sofort dass ich sie mir vorlesen dann überzeugen kann dass es vernünftig mit roten sind und so und so die Probleme auf die Art und Weise anzugehen ja und was wird sozusagen diese Vorlesung machen es sozusagen Gefühl zu kriegen für diese Modellierung solche Anwendung aber auch sozusagen was in die richtigen mit roten Wangen kann ich denn welche Methode sinnvollerweise verwenden um solche Probleme lösen zu können gut dann fang würde ich sagen fangen wir einfach die wir sozusagen die 1. Serie ist also das 1. ist es sein ich fange einfach an mit Milton Einführung machen erstmal Definitionen Paar klassische Beispiele klassische diskret Optimierungsprobleme und dann werden wir ein kleiner Einschub machen gegenüber dem was in dem Buch steht nämlich werde müsse es doch ein bisschen intensiver mit Politikern beschäftigen wir haben mein iPhone schon bisschen Polyeder kennen gelernt was was Seitenfläche erst was eine Facette des aus der Ecke ist immer warm Polyeder optimiert das damals schon kennen gelernt das wird uns für die diskrete Welt der alleine nicht reichen dann müssen aber aber noch ein paar Eigenschaften auch mit roten was man Politikern alles machen kann wegen diesen Exkurs man hier an dieser Stelle noch ein bevor man dann würden die Theorie der ganzzahligen Optimierung einstellen also fangen wir an mit Kapitel 1 2 Einführung und wir fangen gleich an den der 1. Definition
im Buch des wenig ich mache immer die Kapitel dazu damit zu wissen wo es im Buch im Buch ist das sozusagen Skalpell Kapitel VII er und die Definition 7 1 weil dort gibt es natürlich vorher die Einführung in die Optimierung die 1. 6 Kapitel sind und da das dort fortlaufend nummeriert ist wenn sozusagen dort mit der Nummer die Jungs 7 an also die mich ganz zeigt Definition eines gemischt ganzzahligen Programmes also meistens spricht man nur von übernimmt man die am die englischen Bezeichnungen nix in der Chat rauben oder kurz mit also ein Deutsch spricht man meistens von von einem nebst sozusagen an also was haben aber wir haben ne wir haben ne Vektor c außen am Wochendende haben den Matrix außen an noch am Kreuz wir haben eine rechte Seite des außen 1 hoch n und wir der Zahl P die zwischen 0 und und n dann heißt es oh maximiere c't iX A X kleiner gleich B und X aus Z hoch P Golz eine Woche in -minus P Gemisch ganzzahliges Programm macht Milch ganzzahliges ich weiß was hier in ja das und Programm also das weniger deshalb Familien Umlagensystem habe man kann sich später noch überlegen hier auch nichtlineare Bedingungen zu erlauben da müssen Gemisch ganzzahliges nicht länger als Optimist Robin oder Mix in der chern Normen der Bruder des ist gerade sehr aktuelles Forschungsgebiet wie man solche gemischt Anzeige nichtlinearen Problem gelöst ist mein Verein zu zahlen die Dimitrow der nichtlinearen Optimierung diese wenn sie die Vorlesung noch hören nicht in der nicht optimieren kennenlernt mit den Methoden die wir jetzt im Rahmen der gestand seine William Programmierung kennen lernen wollen so da den paar Spezialfälle drin ist eben auch eine Dame Display auf 0 setzen und fällt der derzeit Teil weg dann sind wir in der Welt der Einführung der habe hier klassisches legen Jahresprogramm stehen und wenn dann wenn wir das P auf allen setzen dann ist der kontinuierliche Teil weg dann man ein ganzzahliges als .punkt sowie 7 des geometrische aus an dieser Stelle also das wissen auch wenn aus der Einführung Sohn Alex kleiner gleich B beschreibt immer an poli Eder kann also das typische Polly Eder meistens 5 Ecken was man so an den an die Tafel malt also man hat sozusagen das das als kleiner gleich B bestreiten Durchschnitt sozusagen endlich vieler halbe Räume ja das ist dieser Bereich besonders und wir was uns jetzt investieren sind sozusagen ganzzahlige Punkte hier den Namen also hier ist zum Beispiel hier wird dass man auf diesen Gitternetze anschaue sind das sozusagen die einzigen ganzzahligen Punkte die dort drin sind so wir haben wieder unsere Zielfunktion die Maxime immer nur dann in diese Richtung wie ist unser C und in die Dichtung optimieren wir unser uns der Probleme so und das sehen wir jetzt schon paar Schwierigkeiten die allein doch diese Ganzheitlichkeit auftreten er vorher also diese Ganzheitlichkeit nicht hatten war man der linearen Welt eine wussten aber zum Beispiel Aussage optimale Lösung würde man nicht gern genannt es war eine der 1. Aussagen die auch ich offensichtliches Wärme konvexe Menge wir optimierende lineare Funktion oder konvexen Menge muss am Rand angenommen werden vom Brandes kann mit relativ machen muss also die Optimallösung was immer nicht gegeben die optimale Lösung ist so zu aufzubereiten Netz ganz zunehmen aber schon verloren die optimale Lösung in dem Fall es ist dieser Punkt unterliegt im Innern von diesen Politiker das heißt diese Methode die mir vorher kennen in der Einführung einfach mal entlanglaufen funktionieren nicht mehr wir sonst wirklich was neues überlegen und wir sehen auch noch eine Eigenschaft ist auch noch schwierig macht ist das Problem ist nicht mehr konvex aber wenn sie unzulässig .punkt haben hier unzulässigen .punkt dass die Verbindungsgeraden nicht zulässig er .punkt wieder zwischen ist nicht zulässig das heißt wir haben wird sich nicht konvexes Optimierungsproblem und Einführung eigentlich schon gesehen Konvexität es ist der nette Eigenschaft die natürlich gerne haben will wenn man optimiert aber die hier schon mal verloren geht allein doch diese an den noch ein 2. Problem was war es also sehr ähnlich zu dem Gemisch ganzzahligen es ist sind kombinatorische Optimierungsprobleme also häufig wird so ne Vorlesung wie die auch kombinatorische Optimierung genannt weil die Verwandtschaft zurück die mich ganzzahligen das sehr nahe ist so um und wir werden aber sehen dass das noch ein bisschen allgemeines als kombinatorischer Times Probleme selber also wie sehen die aus ist die Definition 1 2 also will auch hier leben alles kombinatorische es Optimierungsproblem der angegebene Grund man nie gegebenen Grundmenge nur es soll endlich sein also bei uns in der Regel immer alles Endlichen der diskreten Welt ist alles endlich was wir auch sagen es alles langweilige wenn alles endlich ist aber noch abzählen und in das beste da ,komma noch drauf warum das Abzählen der Regel nicht ganz so einfach ist das beispiele Reiskörner die alle zu zählen ist vielleicht ein bisschen aufwendiger dann haben eine
Teilmenge I an der Potenzmenge von ihn davon von E also der bilden die Potenzmenge von ihrem denn daraus uns nicht der Menge von Teilmengen aus die Elemente .punkt in ihr heißen zulässige Punkte oder Reisen zulässigen Mengen sind denn oder Lösungen und Zielfunktion gegeben und der Funktion CD die geht von der Grundmenge nach eigenen ja mit wir definieren von F und der beliebigen Teilmenge ist nichts anderes als die Summe der einzelnen der E aus 11 C von ehe TF das ist dieser lineare Anteil daher dieses Wort lineare dass sich die Kosten findet Teilmenge ergeben sich einfach doch Aufsummieren der einst Elemente wenn man diese Eigenschaft nicht hat kann man auch ganz schwer optimieren weil ich kann der jede ja anderen Ende die diese Potenzmenge geben neben jeder Teilmengen individuelles Gewicht und wir wollen jetzt optimieren über diese Menge dieser zulässigen teilnehmen und wenn da keinen Zusammenhang zu kein funktionaler Zusammenhang zwischen den Teilmengen besteht hat uns wirklich nichts anders übrig als jedes als Element anzugucken was ist das Ventil Funktionswert und dann den besten zunehmen also deswegen macht so der diese Voraussetzungen so zu sagen dass dass die Kosten sich nie aber er bestimmen lassen aus den Einzelelementen durchaus Sinn und ist auch in der Realität häufig zur gegeben gut an das Problem das kann ja wieder maximiere Zelle von E ihr aus der Menge der zulässigen Lösungen beziehungsweise je nachdem man kann das natürlich aus Minimum schreiben dem C von E I aus der Menge der zulässige Lösung heißt linear des Kommentators Optimierungsproblem heißt linear das kombinatorische ist kann unter 3. so wie es der Zusammenhang zwischen zwischen diesen beiden Welten und es zeigt sich was wir hier was man häufigen machen kann dann wenn man da noch Beispiele sehen diese als ganzzahlige Programme formulieren was er nicht tun müssen ist sozusagen sie müssen wie sie dieselbe Menge I modellieren und was entscheiden müssen es welche Elemente dieser Grundmenge E sind Teil der Lösung was man typischerweise macht ist zu sagen ich fühle war ja aber ein XE die sagt dies 1 wenn sozusagen das Element klein e aus der Grundmenge in der Lösung enthalten ist und 0 sonst Werner heute kann man diese es gibt ihn Mängel die Menge der zulässige Lösung über lineare Ungleichung beschreiben aber dann gleich noch Beispiele sehen und zwar genau in dieser Welt nur haben wir dann eben aus den der doch B 0 1 hoch p beziehungsweise meistern 0 1 2 n gemacht wenn Ende Kardinalität dieser dieser Grundmenge is wenn man kann sogar noch einen Schritt weiter gehen und diese Probleme auch alles lineare pro Programme auf was schauen uns mal an wie das funktioniert und dann kann man sich überlegen eine lineare Programme können wir erlösen also liegt das Problem aber schauen uns das vielleicht mal an wie das geht also jedes damals Bemerkung formuliert kombinatorische Optimierungsprobleme der als lineare Programme Mehr moderiert wird wir werden so wie machen wir das wir machen aus jeder Lösungen also hier und ich habe man jedoch mehr Abkürzung wenn man man kürzt das gerne ab mit der Grund man ihn in Mengen der zulässigen Lösungen und der Zielfunktion CE am besten genau die treibt der er das 3. bestimmt eindeutigen komme aber es Optimierungsprobleme die Grundmenge immer zulässigen Lösungen und die Zielfunktion war sogar so runtergeladen und Mama folgende dann für den so genannten in sie den Zweck der ein ich gehe viele Teilmenge aus I dass man einfach so hin von 11 setzen auf 1 heißt es eh aus FS und 0 war eh nicht den FS und sie jeder aus sie jeder Menge also zulässigen Menge mach 0 1 Vektoren a hoch n e es ist anders also was wir hier machen so und jetzt übersetzt sich unser Problem mir ja ist eigentlich nichts anderes soll es können einfach setzenden mit zulässige Menge groß x ist einfach die Menge aller zulässigen Inzidenz Vektoren vor das ist jetzt eher zu die er Erzählebene Manieren Error ändern das ist eine Teilmenge des Euro n ist die Menge unser zulässigen .punkt so das heißt unser Optimierungsproblem maximiere C von E bis gehört E wer setzt sich jetzt ganz einfach in die Welt des RHN als maximiere c't iX X aus X rund so da haben wir jetzt eine modelliert das kann man am Ende der Eigenschaften hier ausnutzen nämlich was haben wir denn wir haben jetzt hier eine Menge von Punkten wir wissen sogar SX ist endlich weil wir mehr maximal Potenzmenge viele solcher zulässige Punkte das heißt es selber endlich wenn es kommt der Eigenschaft die werden die werden uns nachher noch anschauen werden wir bislang noch nicht bewiesen haben ist das wenn ich die konvexe Hülle endlich viele Punkte nehmen kommt wieder Politiker aus also kommen kann von X dessen Polyeder das wird uns noch ein bisschen Mühe kosten bis zu tun das ist zwar in der Einführung glaube ich schon erwähnt worden dass man für Poli es unterschiedliche Darstellungen gibt einmal über die äußere Beschreibung also in Form von Durchschnitt endlich wieder halb Bräune aber es gibt auch die andere die Ende der Beschreibung als Annex Kombination endlich viele Punkte +plus komische Kombination endlich viele Vektoren vom und diese Eigenschaft die müssen uns nur noch leiten dass die auch da sich immer Geld weil wir werden öfters zwischen diesen beiden Darstellungen springen um nochmals die einig sinnvoller man meist die andere sinnvoll so das heißt so und des is kommt die nächste Eigenschaft die wir haben es wird die Funktion des linear an das Ding ihres konvex ja das heißt wenn ich mir die Mehrheit Zielfunktion hat dann wird das
Optimum das wissen wir aus der letzten Vorlesung immer man angenommen das heißt dieses Ding dieses Ding können wir jetzt auch schreiben als Grünenpolitiker P b ja und wir können hier weiter schreiben das nix anderes als kommen als Max X aus Conf von X CTX und das wiederum ist nix anderes als maximiere c't iX X aus diesem pro Eder die Art dann nur zu Erinnerung der war die Menge aller ich zuerst an auch er externe gleich bin und damit sind wir genau in der linearen Welt das heißt jedes kombinatorische Optimierungsprobleme können also weniger als Problem darstellen denselben Trick mögen sie oben auch machen uns doch mal dieses Bild hier anschauen also auch in diesem allgemeinen Fall wenn in immer normale Einfachheit halber an unser Politiker hier beschränkt ist also puzzeln Politwoops sowie in diesem Bild zu die Menge der ganzzahligen Punkte die hier drin liegen auch nur endlich viele das einzige was mir ausgenutzt haben bei dieser Transformation ist das mir Endlichkeit haben der Anzahl Lösungen ja das heißt wenn wir das haben können auch konvexe Hülle bilden ja wenn wir das tun dann ging hier auch zum Teil hier und das Geld ist offensichtlich wieder ein Politiker das ist das was man noch beweisen müssen aber zumindest mal schon mal ein Bild stimmt wenn das heißt es gäbe es wieder ein Politiker und ja der Eigenschaft die Ecken in ganzzahlige Punkte und wenn wir das wissen es gemeinsame Burger es Samanthas das ist weniger das Programm das können wir alles was man Einführung gelernt haben verwenden und Simplex oder liebst wie Methode oder in Punkte wird wurden verwenden um dieses lineare Programm zu Lösungen landen wir natürlich jetzt kann man man laufen Wallander sozusagen an dieser optimalen Ecke aber dieses ja glücklicherweise ganz zeigen aber nur die konvexe Hülle der ganzzahligen Ecken mir genommen hat ok so fertig dass was mir mir Vorlesungen der begleiten wir lesen die ganz wir auf die linearen reduziert und damit ist alles erledigt oder Künste und Haken geben Reich falscher argumentiert also eine die wirklich völlig offen bleibt erst ist sie schnell hin hingemalt immer 2 und diesen netten kleinen Beispiel aber die Frage die sich wirklich stellt wie finde ich den diese gelten über jeden also wenn ich mir das so anschaue wenn ich denn die nur und wir sehen dann also dass dieses finden das haben wir ja ein Stück weit auch in der Inder in der Optimierung einer Einführung scheinen zumindest angedeutet dass es finden von solchen Ungleichungen ist dabei die Jungs Problemen ist genauso schwer wie das Orginal Optimierungsprobleme das heißt wenn das hier schwer war es auch das Finden von diesen gelben schwer das 2 das auch noch hinzukommen kann es an das sich der das finden schwer ist sondern es kann exponentiell viele oder eigentlich doppelt exponentiell viele Fielmann Fällen sogar geben von diesen Dingen also sozusagen die Anzahl der dies die man braucht ist kann man bald drastisch wuchs ein die Frage ist wie sehen solche Polyeder wohnte mention aus ist es eher so was wie Vision Kristalle mit sehr wenigen glatten Flächen und es sieht eher aus wie ne sehr Discokugel mit ganz vielen kleinen versetzt und häufig ist die Zeit ja aus diesem der Discokugel das heißt man braucht ganz viele von diesen kleinen versetzt jeden um überhaupt annähernd gut diese er sozusagen zu beschreiben also hier ist aber an also ich hier sieht's leicht aus aber das ein war der Weg dorthin aber trotzdem das ist ein interessanter Weg die wir dann auch gehen werden sozusagen wie findet man dieses Geld Collider weil das Geld wenn wir das gelbe haben ganz an ist die Welt wieder einfacher Annahme die Methoden zur Verfügung die wir brauchen und und wir werden Methoden kennen lernen die das versuchen zu mindestens 3 von diesen gelten zu beschreiben müsse vielleicht nicht vollständig beschreiben es reicht sozusagen um dies die optimale Ecke herum das gut genug zu kennen wir und wir wissen wir aus der linearen Algebra um eine Ecke zu beschreiben brauchen wir entfiele Bedingungen in demente mention allen also wenn die richtig Ende finden würde ja schon reichen aber diese richtig empfinden wenn wir sehen ist kann oder in schwer sein gut schauen wir uns vielleicht noch ein paar bevor man sozusagen einsteigen ein Stück weit in diese ihn in diese Geschichte hiermit dass es kommt es in Politiker ist und die nur von dieser einen darstellen die andere kommt das vom anschauen vielleicht noch ein paar klassische Beispiele aus dieser Welt der ganzzahligen kombinatorische Optimierung die uns die uns immer wieder begegnen werden aber sondern nur ein Problem das wir eigentlich keine so mal gucken wie das einigermaßen geht ich würde ich habe wir haben und er wird ich werde wo wir die also ein paar Beispiele ich mobil wir kommen sog das Zuordnungsproblemen und wir also nehmen wir mal an es ist in der Firma wir haben entweder bei der wir haben allen Jobs zu verteilen die Frage ist wer macht welchen Job er war bisher meine Firma seine so muss das kleine Gruppe treffen Partie vorbereiten oder sonst was genau das gleiche Problem es gibt ne Menge von Aufgaben zu erfüllen jeder soll was machen und jeder hat unterschiedliche Präferenzen was zu machen und die Frage ist wie mach ich die optimale zu und also man das 1. Mal hier einfacher sozusagen aber man kann sich das kompliziert vorstellen also Firma hat n Mitarbeiter mit Rute und n Jobs jeder jede Person kann genau einen Job ausführen kann genau 1 Tschopp
ausführenden und wir leben das sehen will aus würden sich die Kosten sozusagen wenn wieder bei der E Job J ausführt sein die Kosten sein Zielort falls das so ne Shop J ausführt so wie wie setzt man kostengünstig und Mitarbeiter ein W es ist es setzen er kostengünstig und mit der Zeit mit die Mitarbeiter am .punkt und wird gibt nun ab vereinfachte Szenario aber an sich und vom Grundproblem der schon 1 in der Realität auftreten kann ja normalerweise aber vielleicht ich genau so viele Jobs wie mit dabei der Dicke haben wir viel mehr Jobs als Mitarbeiter der und man hat hier vielleicht dann noch zusätzliche Randbedingungen dass jeder Mitarbeiter gleich viel zu tun haben soll gewisse Anforderungen dass eine der beiden gewissen Shop aus Gründen nicht durchführen kann und dergleichen mehr aber nicht das Grundproblem ist genau dieses Zuordnungsproblemen war wie Molly aber das kann ist es ein ganzzahliges Programm das müssen wir zu tun ja das Modellieren wurde dem Vorschlag für typischerweise fängt man an bei der Modellierung überlegt sich die Variablen also die Entscheidungen Indiz dies zutreffend ist so was sind die Entscheidungen die wir treffen müssen ja also wie weiß ich mit beide IT Job J zu also für sich über Jahre eine vom XI Ort um ICJ 40 auf 1 für alles Person Job J ausführt mit um 0 sonst wer sie genau die Entscheidung treffen wurde so wie sie jetzt ist Modell aus wie sie die Zielfunktion aus wenn alle ein bisschen wiederholt oder wie minimiere zum der CIA und XI hat da haben wir uns zu mir über alle I über alle Mitarbeitern denen mal die 1 bis n und J aus 1 bis in so was in der Hand Bedingungen ja wäre mir lieber jede Person kann genau einen Job ausführen das als wenig über die über die Mitarbeiter über die Jobs zu mir ich schau mal ein Mitarbeiter an der ja dann darf der genau einen Job Nummer also wenn ein Fest mit dabei I anschaulich zu mir über alle Jobs sind der genau einmal was genau so haben wir denn noch die 2. Bedingung aus Jobs Sicht jeder Job sollte sie auch nur von einem gemacht werden also habe ich hier wenig umgekehrt zu mir überall E x ihrer Art ebenfalls gleich 1 stehen ich werde ist ist ganze moderne wir doch was ja genau also XI und noch dazu schreiben das 0 1 und da haben wir jetzt ein klassisches diskretes Optimierungsproblem vom also beim 1. mal anschauen ist der Eiweißstruktur von Randbedingungen alles nur die die Matrix angucken stehen 0 1 würden nur und man hat nur gleich als Bedingungen nur und welches nur gleich 1 das klassisches grüner Trois Optimierungsprobleme werden später sehen dass wir diese Bewegung Songs und sogar Elten schenken können das ist eines von den Problemen automatisch Ganzheitlichkeit gegen 1 Erwägung automatisch Ganzheitlichkeit gelegen und wir werden später analysieren woran es liegt es wirklich genau dieser Struktur von dieser Matrix es gibt ganz wenige Ausnahmen von Matrizen die automatisch ein Ganzheitlichkeit liefern das ist eine solche ja das heißt solche solche klassischen Zuordnungsproblemen sind einfach lösbar wenn es wenn man später noch genau anschauen oder es liegt allerdings sobald eine zusätzliche Randbedingungen wird zunehmen zerstört dass diese Einfachheit wir unser Bild der nochmal anschauen wir dieses einfach hat sicher baden manifestierte das automatisch diese Ecken ganzzahlig Karten von dem Bild was wir vorher hatten zur Wahl jetzt zusätzliche Randbedingungen einnehmen dann zerstört dass mir diese Eigenschaft wir weil plötzlich ich dann an diesen Stellen der neue Ecklösungen rein die nicht mehr automatisch ganz sind und waren sozusagen zunehmend von solchen Randbedingungen die ganze Keith nicht zerstört das Scharons auch noch an aber in der Regel das sich mit einem Bilder über die zerstört gut im 2. klassisches vielleicht ich mache noch 2 klassische ist es ein Rucksack Problem das wir noch haben zum übrigen diese Art zu und so wie mir die Tränen auch heute noch in den Firmen auch wären schon mit 2 unterschiedlichen für Firmen praktisch so ein Projekt laufen zum Beispiel Servicetechniker wenn anschauen wie diese Glaszylinder rumstehen Aromate hatte bauen der Matte Bau steht zum Gas Zylinder und diese Gas Zylinder werden von Linde Gas betreut die haben Servicetechniker die regelmäßig sozusagen hier vorbeifahren und gucken ob das alles noch in Ordnung ist oder das Gas wieder beliefern und die Frage ist welcher Servicetechniker kümmert sich um welchen Kunden und allein Flüssen der Region möglichen um 5 oder 7 Servicetechniker die haben knapp 1000 Kunden die Frage ist welche Technik er bedient werden konnten und da haben 7. wirklich der wenn er in die Kosten kommen würde die Fahrtkosten nein also was kostet es dahin zu fahren die Zeit vor Ort die Rückfall und alles geht also dieses C an damals schon so ein klassisches Problem in der Realität der kommen noch andere Bedingungen dazu weil eine Mitarbeiter ist Tal kommt sobald die Bedingungen ein alle soll ungefähr gleich viel zu tun haben das das macht sofort das Ding kaputt zu wie hier oben und dass sie der gleich Auslastung hat führt genau zu Sonderbedingungen gelten doch zum Polyeder schneidet ja und dass dann auch die die Algorithmen die wir dazu braucht es schwer macht dann kann man sogar überlegen was sie auch überlegt haben so zeigen dass die Standorte der Mitarbeiter gar nicht fest sind ja bislang haben wir das so gemacht dass alle Techniker morgens in München inne Stadtmitte beginnen dann rausfahren nach Augsburg nach Rosenheim nach was weiß ich wohin und wenn einer das halbe Jahr über Mostar Mühen gereicht wenn dann gleich wieder Rosenheim raus um Zidane gleich nach großen das kann durchaus Sinn machen wir so eine Firma mit dabei umzuziehen als zu bezahlen müsst ihr Eigenheim kein günstiger sein als wenn der täglich erst nach München Minderheit werden dann wieder daraus also auch solche Überlegungen an kommen Entscheidungen Standard Probleme rein also wo ist
denn ein idealer Standort sozusagen um Kunden zu bedienen auch in Entscheidungen zweier haben also auch wieder Erweiterung von diesem Zuordnungsproblemen auch wieder und das Gerät das Problem also schauen muss das 2 der klassische an es ist es Rucksack es wir sind also wenn man ja wieder ne Firma Hitch in dieser Mann Budget Formate und Budget B und Müll im .punkt will in England Produkte investieren jedes Produkt je kostet e einhalten und erzielt gewinnt CE ja sollen welche Produkte soll die Firma investieren in welche .punkt soll die Firma so was machen wir wir moderieren wollen 1. was uns Variablen das in dem Fall ich wie oben denn wir wollen wissen entscheiden in westlichen Produkt i ja oder nein also Variablen XE 1 war der Investitionen in Produkte E um 0 sonst so wir wollen unser Gewinn maximieren das heißt wir maximieren Summe CX ne wie gleich 1 bis n dass unser Ziel Funktion und das einzige Restriktionen warmes es unser Budget einhalten müssen also Summe e x kleiner gleich BEI gleich 1 bis n ist unser einziger den Bedingungen so natürlich nur so weit vergessen dürfen auch hier wieder alle Variablen sind nur 0 oder 1 werden und denn wenn sie das klassische Rucksack Problem wird überlegt es sieht ein überhaupt nicht schwer aus das Problem wir haben wir nur eine Randbedingungen was der linearen Welt vergleichen weil sollte dass eine Übung gemacht haben Einführung eine da können Sie optimale Lösung ab ist das können Sie mit dem simplen sortieren können Sie da sozusagen sofort die optimale so angeben der linearen Welt in der ganz seines leider nicht so bei also hier das Problem dass ein schweres Problem Zähne kommen wird vom Komplexitätstheorie weshalb die an alle schon was von NP-vollständige oder ein beschweren soll gehört dem sagten der Begriff NP-Vollständigkeit noch nichts eine zweieinhalb gut also wenn ich dann später mal vielleicht 10 kleinen Exkurs machen was was NP-vollständige unendlich schwer heißt also letztendlich heißt vereinfacht sagte die gibt es bislang oder sind bislang keine gutartigen Algorithmen bekannt und einer gutartigen Algorithmus versteht man ein der Polen im Laufzeit hat also eine Eingabe der also in der Länge der Eingabe ist sozusagen polynomial und dann sollten Sie finden so Algorithmus oder zeigen dass es keinen solchen gibt zum genau für dieses Problem zum Beispiel also das gehört zu Problem denn Beschwerden Probleme soll die Laufzeit als soll den Algorithmus für das Problem einfallen der Polen Laufzeit hat eine Krise wahrscheinlich Doktortitel Zettel und den Millionen Dollar auch noch alles gehört zu diesen 7 Problem 2000 ausgekühlt wurden als die Hauptfragestellung in in der Mathematik in den in den nächsten Jahrhundert sozusagen der oder sie weisen nach dass wir dieses Problem keine geben kann und die Vermutung ist dass es vermutlich keine gibt weil schon seit 30 oder 40 Jahren war der Versuchung einzufinden keines bislang eine eingefallen aber das muss ja nix bedeutenden Fermats sattsam auch 53 Jahre die Leute und geknobelt wissen dass endlich bewiesen haben dass es nicht geht weil meine Schwierigkeiten war nachzuweisen dass das nicht geht dann ist es in der Regel immer deutlich schwerer als zu zeigen wie es geht was weiter muss ist ja nur zeigen und machen wenn das was nicht geht ist dann wird deutlich schwieriger und deswegen ist momentan schon das Gefühl an der Stelle es geht vermutlich nicht es gibt keine gutartigen Algorithmus für diese Art von Problem aber dieses dieses Problem taucht praktisch überall auch auf nein mein Budget Fragen haben sich immer immer zu wenig Geld das heißt diese Randbedingungen das nicht Knappheiten gibt anderes Haus das heißt jetzt Geld es Materialien und Rohstoffen oder was auch immer dies praktisch immer gegeben und die haben sie immer wenn sie Entscheidungen treffen und wir haben es immer unter knappen Ressourcen also brauchen wahnsinnig nix entscheiden sie alles machen können weil sie genug Kohle oder sonst was haben und dann machen Sie einfach alles war weil das heißt sobald interessantes Optimierungsproblem haben Trauer taugen solche Art von Bedingungen auch ja und wenn Sie 1 Uhr spielt Definition vom Gemisch kann sein Programm denken letztendlich steckten die auch schon drin wir bei jeder eines der Zeile einer Matrix wenn sie dies als kleiner gleich be anschauen und sich eine Zeile daraus nehmen ja dann ist es genau von diesem Typ das jeder eines Liedzeile beherbergt sozusagen als Rucksack Problem hier dann und damit ist es durchaus legitim zu fragen kann versteht ich den diesmal eine solche Randbedingung und witzige man hat bis heute nicht mal dieses Polyeder was dazu gehört es ganz zeige vollständig verstanden es gibt exponentiell tappt sogar doppelt exponentiell viele solcher Ungleichungen die allein diese Anzeige Polyeder bestrahlten um woran liegt das nein mein letztendlich geht hier sehr viel wärmer genau man hinschaut immer die Schwierigkeit kommt 3 wenn hier krumme Zahlen stehen und dann und dann stellt sich schnell die Frage so sozusagen kann ich mitkommen Zahlen sagen hier dieses PC oder wenn diese Zahl gut erreichen können das geht dann sehr schnell in Fragen der Zahlentheorie wie kann ich sozusagen gewisse Zahlen hier ganzzahlig darstellt ist ne klassische Frage dort war und dann sind sie ganz komme Zahlung große Zahl nehmen ist es durchaus nicht wenige Fragestellungen sowas beantworten zu können gut vielleicht noch ein Klassiker am Schluss das ist es selbst erging hatte stehen oder Kalorien Problem es ging parteilichen Dingen und waren also haben wieder Grundmenge The nur 1 bis n wieder eine Liste von Teilmengen er Art Teilmenge von E fährt gleich 1 bis n und wie mit jeden 11 Ort jeder er Fiat hat kosten oder träge je nachdem .punkt CJ so und jetzt
müssen wir uns mehr Auswahl finden finden der Auswahl an FJS so war es jedes Grundelemente höchstens genau oder mindestens einmal vorkommen Sorbas das Grundelemente höchstens dann spricht man von Peking genau wann spricht man von praktischen Dingen oder mindestens dann spricht man Fankrawalle in oder mindestens dann spricht man von Krawallen mindestens einmal vorkommt finde eine Auswahl also müssen wir hier die sehe die bezüglich und C optimal ist es ist sowie Modell über das wir sind mir ist da wer den Vorschlag als Grund es immer das gleiche mehrmals zum überlegen was in wir Entscheidung über fehlen wir müssen entscheiden da jeder 14 nicht wir also für meine Variable 1 jedes F J also XJ so dass wir wieder auf 1 falls 11 J gewählt um 0 sonst und das ist das eine jetzt für noch zusätzlich wenn Matrix ein die uns sagt er es sei an dem Matrix aus 0 1 hoch Kreuz allen mit ja ich nehme einfach ein die J der Spalte den Inzidenz in sie den Zweck dauern bis sich das Jahr dem Element chemischer werden also die Orte Spalte wir kürzere so Abd el ist Inzidenz weg davon F J so Visite unser Problem aus sieht unser Problem so aus dass wir minimiere ja unser Ziel Funktion ist da nix anders als C transponiert X sollen Signets bis aus höchstens 1 mitzunehmen das der Peking es sei nichts anderes als kleine gleicht dem eines legt auf der X aus 0 1 hoch ist so also dieses kleiner gleiches Peking gleich ist praktischen Dingen größer gleich ist kann man und wir nach dem man oder Max ist in der Zielfunktion einzig Hacker mit dem der könne
mein kleines beispiele zu anschauen also man haben der Grundmenge 1 2 und 3 4 ja das sei unser E wenn wir uns mal ein paar Menge aus 11 1 wenn man sogar noch 1 kleiner und nur noch 1 kleiner mach mal 11 1 1 2 11 2 2 3 und S 3 1 3 n vor wird bisher waren es muss lesen keineswegs immer bei ihnen geschah mit sowie sieht unser Matrix aus das in dem Falle 3 gereizt 3 Matrix ja ich sozusagen F 1 F 2 F 3 ich hab 3 Grundelemente 1 2 3 ich schreibe also über alle einzeln und hier drüben zu zeigen die Elemente auftauchen vor dass die Matrix und damit steht hier das Problem wir können es alle Mal ausführlich schreiben sozusagen immer maximiere C 1 x 1 +plus c 2 x 2 +plus C 3 x 3 unter der Bedingung x 1 +plus x 2 Mal den kleiner gleich Fall kleiner gleich 1 x 2 +plus x 3 kleiner gleich 1 und X 1 +plus x 3 kleine gleich ein und das Rätsel des Beispiel wo und das interessante ist also die Probleme lassen sich viele dieser Probleme kommen lassen Ingram formulieren wir Euro und ohne dich so einer Stelle schon E geschrieben als Fall aus im in Grafen Anwendungen hat Mehr weil wer hat von Ihnen ab algorithmische diskret dämmerte 7 Tage und niemand es gibt erst seit letzten so Markgrafen und Algorithmen wer wer weiß überhaupt nicht was ist wer kennt zum Beispiel keine 3 x 3 alle keine Wunder war also dann kennen Sie natürlich auch einen dieser die die Grundkonzepte hier etwa was die Frage ist was dem Problem der verbirgt sich hinter dem was man über sich hier Einigkeit geschrieben hat es gab und unter dich anschauen die mal die Grundmenge Jan indem man das sind Knoten hier 1 2 und 3 was sich hier steht x 1 x 2 dürfen nicht gleichzeitig ja wenn immer ich seine Bedingungen hab und Mann kann der bei 1 und 2 dürfen nicht gleichzeitig 2 und 3 der nicht gleichzeitig wählen und 1 und 3 darf ich nicht gleichzeitig will er das heißt ich musiziere Knoten Auswahl finden so dass diese Bedingungen erfüllt sind aber ich darf hier sagt welche ich nicht gleichzeitig nehmen darf ja das ist in der Graphentheorie das stabile Mengenproblem anders als Lösung raus sehr stabile Menge also eine mit Teilmenge der Claude zu dass keine 2 miteinander benachbart sind ja ich hier wie kannte die ich hier hab seine Bedienung aufschreibt da hab ich garantiert dass keine 2 benachbart sind und das sich dafür maximal ein Knoten wählen ja oder in größeren Zusammenhängen zu zeigen hier noch eine wäre wir immer man 4. dann eingenommen hätten wir denn zum Beispiel auch noch an also eine Teilmenge der großen Menge so die paarweise nicht benannter benachbart sind was denn eine stabile Mengen also hier ist sozusagen hier kann man zum Beispiel das stabile Mengenproblem modellieren damit kann man das Verbunds Problem modellieren das schon mal gehört am Grabmal sowie vereidigt kostengünstige Landkarten ist praktisch hier auf dem versteckt interessant denn hier sehen wir da man nicht zum Ende der Eigenschaft die beim Zuordnungsproblemen haben weil wir hier das lineare Programm lösen kommen nicht automatische ganzzahlige Lösungen aus warum nicht mal die CLR raus machen einfach Einsatz Funktion also maximieren einfach x 1 +plus x 2 +plus x 3 sie eine Lösung geben die besser als 1 das Recht gebrochen wird erlaubt alle Inhalte genau also wenig X 1 gleich X 2 gleich X 3 gleichen Halbsätze dagegen der C-Funktion
eineinhalb ja das eine offensichtliche Lösung die nicht erlaubt ist ja und damit zehnmal so zeigen dass das Polyeder was hier zugehört hatte gebrochene Ecke das Bedingungen und wie wir die findet dass wir uns auch im Laufe der Vorlesung mal überlegen wie im Fall kann man sie vielleicht sogar einfach finden was die Bedienung ist das abschneide können Sie mal überlegen aber an sich sonst hat diese Art Anwendung wird sehr häufig verwendet auch in der Modellierung gerade wenn man Randbedingungen hat dies sehr schwer mobilisierbar sind also typischerweise zum Beispiel wo das erstmalige angewandt wurde es beim Airline Kuske gelegen war also wenn Sie Ihre Airlines haben die Gruß die immer auf den Flieger sind die machen ja immer solche und die Fliegen von mir aus Frankfurt New York New York Frankfurt Frankfurt Madrid Madrid Athene hat in Frankfurt und das ist so ein 1 geht viel einer Kuh und jetzt haben sie sozusagen jeder Spalte dieser Matrix ist ein einen Flug für eine eine Flug mögliche Flug oder eines solchen Q die Anzahl Zahlen sind ja alle Flüge die Lufthansa anzubieten hat und jetzt müssen Sie einfach Ihre groß auf diese Flüge verteilen sodass natürlich ja in dem Fall haben sie diesen Gleichheit oder größer gleich auf jedem Flug mindestens eine Kuh ist manchmal ist vermeiden dass der 2. da also bis dann außer Dienst auf dem Fliegen fliegen also typischerweise modellieren sodass dann Alsen X gleich wie die Zahlen sind ihre Flüge jeder Flug muss genau einmal abgedeckt sein und die und die und Reisende Gruß müsse so organisiert sein dass genau wie im Flug einer ist der Krise Probleme mit mehreren Millionen spalten das heißt mehrere Millionen 1 Bedingungen paarhundert sein diese Probleme waren vor 20 Jahren noch sehr schwer zu lösen bis gar nicht lösbar heute sind mit Methoden zwischen so weit dass wir die praktisch sagen können sie sind einfach lösbar also auch darum ein bisschen und Hinweise geben wie weit sich die Algorithmen die Dimitrow den letzten 20 30 Jahren verbessert haben auch solche Art von Probleme zu lösen mit mehreren Millionen von Formel 1 2 Arten gut so weit vielleicht der Einführung aber an Parade sind so 3 Klassiker werden später noch ein paar andere kennen lernen wir uns ein paar richtig Anwendung dann irgendwann mal angucken wie man die vielleicht modellieren auch lösen kann aber es wurde uns ein bisschen heranarbeiten wie werden wir werden solche Probleme lösen können und dazu müssen wir weil jeder besser verstehen also vielleicht schon verstehen ohne die geht es wie ich das an meinem Beispiel schon gesehen wir werden also Grundlagen der Polier Theorie ist das Kapitel 1 2 mit in Buch ist das Kapitel 5 5 also Kapitel 5 5 in dem Buch also ganz wichtiges Konzept wird sein dass wir uns als 1. aber eines Projektion und sondern sicherlich auch schon wenn dann alles in eine Linearen Algebra gesehen was wir hier und jetzt arbeiten wollen die projiziert man Gleichungssysteme und das kann dann wieder raus und wenn wir das Ganze wiederholt was kommt dann wieder raus und so weiter und wir werden
sehen dass Projektion die poli Eigenschaft erhält zum Polyeder haben sowohl projizieren kommt dem Politiker und machte ihn viel Museen Jameson viele ältere Discokugel an die Wand projizieren ist der Schatten wieder und Vielecken ja es kommt wie Politiker auf und in der der Eigenschaft die Marlene Projektion auch hat und das ist dabei meist der
Alternative zum Fahrgast wäre sicher eine andere noch alles Farkas Slammer bei mir eine Alternative arbeiten nämlich wie kann ich der feststellen ob Umlagensystem unzulässigen .punkt oder nicht das Farkas Werner eben wie es existierten AX daher gleich B oder alternativ ein anderes Lösung System hatte hat man Umlagensystem müssen also ich kann sozusagen ist er einfach feststellt ob nun System unzulässiges oder nicht das kann ich auch mit diesen Projektions Gedanken machen warum also Umlagensystem zulässige .punkt heißt er hat das zugehörige Politikern zu lesen .punkt ja oder nein was die Idee die verfolgen wollen der ich hab hier dieses Objekt wo ich nicht weiß es Lehrer nicht dann Policies mal an die Wand ja wenn es nicht leer war musste Schatten geworfen haben also muss auch der Schatten nicht leer sein so und das wiederhole ich hier bin ich anderer Netzpolitik ist eine Kante und wie viel das gleiche Argument wenn vorher daran Schatten Weise an Kante den Schatten und es wird sich bis auf den eines simulieren .punkt runter ja man es vorher zulässig .punkt hatte muss und daher in diesen singulären .punkt der dagewesen sein und wer nicht dann kann ich das an der Stelle entscheiden also sozusagen Unzulässigkeit ein projizieren sich auf die Dimension unter war und wie man das macht man das ausrechnet dann ein Verfahren entwickeln diese vor Arzt in allen der Nation die und sozialen auch genau diesen Projektions Vorgang beschreibt mit der bestreiten sogar ein Algorithmus der die angibt wie man projeziert an und das ist das was uns jetzt arbeiten wollen es ist das 1 2 1 Projektion von Politikern und also schauen 1. Definition an 1 9 wenn man das 1. mal sehr allgemein für 2 Mengen aus auch allen 10 seine Projektions Richtungen sei nicht der 0 Vektor für ist die Menge alle x in Hama es existierten Lander aus er mit x +plus landender Inc aber aus es Projektion von S auch war entlang C ja eine Besonderheit noch also ist ha von der Bauart also genau eine Hyperebene ja dann spricht man von unten und oben an der Projektion zur heißt die Projektionen so wie sieht das aus schauen was es bleibe man Bild an weil Sie ja um eine Menge S wer hier ich bei Menge war natürlich projezieren entlang Richtung C soll ich will diese Menge es auf das Haar projiziert ja wie mache ich das ich muss einfach kucken sozusagen hier anschauen was ist fragen meine Definition ich brauch ist eine Teilmenge was wir sehen Projektionen ist mit Teilmenge von Haar also das heißt ich habe mir ein .punkt 1 x in den war und jetzt muss ich in Richtung den C laufen in die oder in die Richtung und muss das es treffen also ist für diesen Punkt machen die glauben Richtung sie und wenn ich den geeignet skalieren komm ich dazu in es an ist für diesen Punkt machen wir glauben Richtung C dann komme ich nie Ihnen es als die Projektion von dem es auf das Haar in diesem Fall der genau wie hätte in dieses kleine eckte und ja und wenn wir den besonderen Fall nehmen das wir jedes es haben und wo und das Haar ist jetzt über Ebene es wäre unser wo genau in den in die Richtung von den 10 schaut ja also wenn es die
Projektions Richtung wiesen wir schauen uns diesen Fall hier an dann ist das ja der normalen legt das C das heißt es sei genau in diese Richtung ja dann gehen wir genau Zusagen diesen das ist die Projektion und das ist das was wir da machen wolle wollen's nicht nachher für allgemeine Mengen S und Haar wir wollen's für über machen wir wollen zieht die Politiker machen wir sehen schon sozusagen letztendlich ist es eine Art Schatten Algorithmus nahm wie Policys sozusagen solche Mengen auf diese Demenzen alle Objekte und wie kann ich ich das hier kennen und das Sie kennen wie kann ich diese Gelder Menge beschreiben und wie kann man im Fall von Polly dann tatsächlich explizit beschreiben und auch explizit ausrechnen aber schauen uns dann nächste Woche an vielen Dank
Wirtschaftsmathematik
Menge
Mathematik
Momentenproblem
Besprechung/Interview
Größenordnung
Diskrete Optimierung
BAYES
Optimierung
Computeranimation
Nebenbedingung
Mathematik
Besprechung/Interview
Ausdruck <Logik>
Nichtlineare Optimierung
Variable
Ungleichung
Lineare Optimierung
Minimum
Zielfunktion
Switch <Kommunikationstechnik>
Größenordnung
Inhalt <Mathematik>
Optimierung
Matrizenmultiplikation
Punkt
Prozess <Physik>
Total <Mathematik>
Laufzeit
Physik
Konvexer Körper
Familie <Mathematik>
Fluss <Mathematik>
Exponentialfunktion
Norm <Mathematik>
Energiebereich
Computeranimation
Richtung
Komplexitätstheorie
Nichtlineare Optimierung
Strömung
Variable
Abzählen
Ganze Abschließung
Meter
Physikalisches Phänomen
Vorlesung/Konferenz
Zielfunktion
Optimierung
Diskrete Optimierung
Konvexität
Statistik
Polyeder
Endlichkeit
Mathematik
Fläche
Optimierungsproblem
Aussage <Mathematik>
Ganzzahlige Optimierung
Kombinator
Randbedingung <Mathematik>
Kombinatorische Optimierung
Vektor
Zahl
Entscheidungstheorie
Lösung <Mathematik>
Höhe
Durchschnitt <Mengenlehre>
Lineare Funktion
Ecke
Konvexe Menge
Darstellung <Mathematik>
Simplex
Punkt
Zusammenhang <Mathematik>
Lineare Ungleichung
Besprechung/Interview
Inzidenzalgebra
Stichprobenfehler
Ungleichung
Minimum
Lineare Geometrie
Zielfunktion
Optimierung
Polyeder
Endlichkeit
Vektorrechnung
Potenzmenge
Optimierungsproblem
Konvexe Hülle
Glatte Fläche
Kombinatorische Optimierung
Teilmenge
Lösung <Mathematik>
Summe
Menge
Durchschnitt <Mengenlehre>
Ecke
Mathematische Größe
Länge
Matrix <Mathematik>
Punkt
Matrizenmultiplikation
Zahlentheorie
Zylinder
Laufzeit
Fluss <Mathematik>
Komplexitätstheorie
Restriktion <Mathematik>
Variable
Ungleichung
Ganze Abschließung
Vorlesung/Konferenz
Zielfunktion
Dicke
Erweiterung
Polyeder
Mathematik
Optimierungsproblem
Randbedingung <Mathematik>
Biprodukt
Zahl
Entscheidungstheorie
Teilmenge
Summe
Ecke
Teilmenge
Variable
Zusammenhang <Mathematik>
Matrizenmultiplikation
Menge
Besprechung/Interview
Vorlesung/Konferenz
Zielfunktion
Inhalt <Mathematik>
Graphentheorie
Inzidenzalgebra
Ganzzahlige Lösung
Matrizenmultiplikation
Polyeder
Besprechung/Interview
Lineare Geometrie
Vorlesung/Konferenz
Randbedingung <Mathematik>
Zahl
Ecke
Teilmenge
Ebene
Punkt
Polyeder
Menge
Hyperebene
Besprechung/Interview
Projektion <Mathematik>
Vorlesung/Konferenz
Kante
Vektor
Polygon
Richtung
Objekt <Kategorie>
Menge
Besprechung/Interview
Projektion <Mathematik>
Richtung

Metadaten

Formale Metadaten

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

Inhaltliche Metadaten

Fachgebiet Mathematik
Abstract Der Schwerpunkt der Vorlesung „Diskrete Optimierung (Optimierung II)“ ist die Theorie und Lösung ganzzahliger und kombinatorischer Optimierungsprobleme. Es werden Schnittebenenverfahren, Augmentierungsmethoden, Approximationsalgorithmen sowie Dynamische Programmierung behandelt. Klassische Probleme der Diskreten Optimierung wie das Rucksack-Problem, das Traveling Salesman Problem oder das Setpacking Problem finden ebenfalls Beachtung.

Ähnliche Filme

Loading...