Merken

Anwendungen von Totaler Unimodularität: Hermitesche Normalform

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
im Ohr höre ich ja das war ein wir herzlich
willkommen zur heutigen Vorlesungen wir haben uns sehr am Montag unterhalten einmal über die endlich Schwierigkeit vor ganzzahligen Programm und das ist als Konsequenz hat dass wir uns andere Methoden überlegen müssen oder bei den Methoden die wir entwickeln werden im Laufe der Vorlesung 2 Dinge beachten müssen entweder wir und wir wollen die Qualität erhalten also wirklich beweisbare optimale Lösungen bekommen aber dann haben wir den Nachteil dass man eventuell über des exponentielle Laufzeit in Kauf nehmen müssen oder umgekehrt wenn wir auf schnelle Laufzeit uns das wichtigste Kriterium sozusagen ist dann kann es eben sein dass wir die Qualität vernachlässigen müssen spricht vielleicht darauf verzichten müssen die optimale finden und genau diese 2 Aspekte wenn morgen aber der Vorlesung genau uns anschauen und die haben dann Arbeits angefangen der letzten Stund zu seiner vielleicht gibt es auch Fälle wo man Glück hat und dieser über das CAS gar nicht eintreten kann und damals letzte mal angefangen zu diskutieren das hat uns auf den Begriff der total ohne Modularität geführt was letztendlich aus der Kramer steht Eigenschaften über die zugrunde liegende Matrix die uns immer garantiert dass nicht die Lösung ganzzahlige ist und damals letzte Mal die wichtigen Sätze dazu bewiesen und an den der Satz von Hoffmann Kuss Karl auf die beiden die dieses Konzept auch zurück und wir wollen uns heute zwar noch 2 anderen Anwendungsfelder dazu anschauen und dann überlegen brauchen wir das wirklich in dieser Art ist ja wie wir das formuliert haben alles als sozusagen die Bedingungen die Madrid oder reicht uns nicht auch sozusagen das finde konkret der rechte Seite wir brauchen wir wenn man es von Anwendungs sich uns überlegen ist ja sozusagen wir müssen da nicht irgendwie Eigenschaft haben nicht alle beliebigen rechten Seiten Geld sondern es reicht sozusagen wie die eine konkrete ich jetzt anschauen will und es wird uns auf ein neues Konzept der totalen dualen Illegalität und da die Vorbereitung dazu vermutlich heut schon machen aber zu den Begrifflichkeiten formuliert dann erst nächste Woche kommen jetzt erst mal noch Fragen zu dem was wir am Montag diskutiert haben gut denn ist nicht der Fall anschauen und vielleicht 2 Anwendungsfelder an bis 1 ist aus so beide sind Stück aus der Graphentheorie die wenn man so möchte dass eines mehr für Grafen dass alle 4 ungerichtete die Gedichte der des letzte immer schon angedeutet er wollen heute nochmal ein diese klassischen setzte der kombinatorischen Optimierung oder Graben der die Beweise bist Max floh MiniCard Theorien man sagt dieses dieser Satz noch nichts ich gut schon ne Handvoll oder 2 Hände voll und das auch noch mal anschauen was es im Graben der die heißen dann so zu sagen was des is dat in Madrid Sprache heißt so wie wir das es heute aber beweisen wollen also 2 Anwendungsbeispiele also das 1. des Max Flomen den wo gerade was sagt dieses aus wir schauen uns mal folgende Situation an indem man beliebigen Grad Wärme und ohne Quellen haben verschiedene Knoten ich war irgendwas sondern in ein ganz kleines Beispiel wir machen hier Überkapazitäten sowas von irgendwelche Kapazitäten auf diese würden darauf was wir zu wollen ist wir wollen möglichst viel Fluss von erst nach The schicken Jahren also das hier soll die Quelle sein dass hier die Senke und das hier diese Zahlen hier ist sein Kapazitäten ja also viele bekannte C von A oder E für E aus EE an und die Frage ist jetzt wir wollen jetzt einfach überlegen wie viel kann ich jetzt was heißt es ein Fluss Wasser sinnvollen Fluss schicken das heißt wir
wollen ich sage es mal eine Einheit entlang von einem weg von erst nach The schicken und möglichst viel von erst nach die transportieren wird das heißt unzulässige Fluss es folgendes also wenn das mein Graph ist hier die gleich vor Ort ,komma das ist ne Abbildung X der geht von den Kranken nach +plus mit folgenden Eigenschaften einmal er muss die Kapazitäten einhalten ja ich darf über eine kann den nie mehr schicken als die Kapazität zulässt und das 2. was ich habe ist wenn ich was in Knoten rein stieg dann soll es auch wieder raus fließen also Summe über alles was außen Knoten rausgeht Delta +plus von V XE Nina aus so man was in ein Knoten einfließt XE soll immer gleich 0 sein ja und das für alle V ungleich es und das heißt wenn in 1. was losschicken das dann soll es auch ankommen also ist sozusagen das bald zu Ende und das Leitungssystem hat keine Lex ja es geht unterwegs ist verloren so dass wenn man unzulässigen Fluss nein so was maximieren wollen es möglichst viel aus es raus schicken wir also Maximiliane wenn wir das gleiche hierfür es anschauen -minus das was in 1. reinläuft wobei man die Kanten denn es laufen gegebenfalls auch weglassen und das ist das maximale Fluss ok so was man vielleicht in was man sich jetzt natürlich in Frage stellen kann ist sozusagen wie der Fluss kann ich den maximal doch schicken mehr doch so Netzwerk und er da kommt da kommt ein sozusagen die sozusagen was was es nehmen kann es einmal so Weise möglich obere Schranke für diesen Wert kann ich diesen Wert hier würden die abschätzen doch ein Konstrukt oder eine Zahl von oben ja wenig optimieren will ist er immer und das ist die Frage die wir uns in der Einführung gestellt haben wie Beweis sich Optimalität ja und wenn Sie sich erinnern Bands Blitzverfahren hat uns immer oder beim bei linearen Programm gibt's es immer das duale lineare Programm dazu was uns jetzt echt den beweist Optimalität liefert damit habe ein ein Zertifikat Zusagen Wahnsinn Mann Norman sind wir optimal zuletzt haben wir hier natürlich das können wir ich halte es durchaus mal als als auch nicht es gibt sowohl kontinierlich als auch ganz Variante also wir können uns auch hier statt Z anstatt ab Lust z +plus denken was ist sozusagen wie kann nicht abschätzen wie kann ich beweisen wenige Lösung ab dass die möglichst gut ist und dazu brauchen Emerson Konstrukt was uns von oben das beschränkt und dann sagt uns ein Satz in dem Fall zum Beispiel das starke Dualität der Satz die beiden sind immer gleich so was ist jetzt hier wenn man einmal mehr werden gleich das Argument auch benutzen das aus der Linearen Programmierung Canvas wären Argumente zu diesem Fall wenn jetzt dreimal dessen in im Grafen Sprache anschauen was ist offensichtlich obere Schranken wie viel Fluss kann ich den maximal heraus schicken auf diese S ja das Theorien kennen wo oben steht da schon was Marx floh den Charakteren also das muss wo es Mitschnitten zu tun haben kann also wenn ich mir das anschaue versuche ich und kann ich der Welt wollen die diese Zahl nicht denn mein Graph in 2 Teile ja ich schneiden irgendwo Durach zum Beispiel hier ja und zwar so dass der es auf der einen Seite liegt und der die auf der anderen und jetzt sehe ich einfach die Kapazitäten die die von der 1. Seite zu T Seite laufen ja und offensichtlich kann ich nicht mehr Fluss rüberschicken
als diese Kapazität ja in dem Fall die 5 ich weiß also von Hause aus schon hier in diesem konkreten Beispiel der Fluss hier kann nie größer sein als 5 soll das hab ich natürlich nur ein Schnitt angekuckt es gilt offensichtlich für jeden Schnitt ja also was ich jetzt machen kann ist damit wieder ne neue Aufgabenstellung indem mir eine Aufteilung des Grafen in 2 Teile so dass der es auf der einen Seite liegt der die auf der anderen dessen Kapazität die Summe der Kapazitäten die vom 1. teilen Täter laufen möglichst klein ist das ist minimale Schnitt Problem und wir sehen hier es gibt einen besseren offensichtlich zum Beispiel Linie ja der hat eine Kapazität 4 Jahre und wir wissen sofort also der maximal Flusses immer kleiner gleich diesen Schnitten und wenn wir jetzt wenn wir jetzt im Fluss finden der genau diesen Wert hat dann sind wir fertig mehr also in dem Fall ging es zum Beispiel ja wir können hier 2 Einheiten hier oben rum fließen lassen ja jeweils nur 2 und 2 hier unten ja dann hätte dieses Ding hier den Wert 4 ja und wir haben auch um besseren gefunden mit Wert 4 und damit gilt Gleichheit Gewissen ist kann nicht besser gehen oder und dieses Marxloh man Kategorien sagt wer die Aussage sich nun dem Beispiel wichtig nicht immer gelegt das heißt der maximale Fluss in Sohn Graph =ist gleich immer den minimalen Schnitt so gegen die Grafen Algorithmen oder in Informatik in gaben in Grundzügen war das glaub ich auch ab und zu behandelt gehört haben man gibt es gibt die kombinatorischen beweist dies zu machen überhaupt mit dem die Wege was wir jetzt hier ein instrumentalen zur Führung haben diese totale ohne Modularität bestens das auf direktem Wege über Matrizen Zusagen beweisen und das ist das was wir was wir jetzt kurz anschauen wollten so wir können dessen ein bisschen modifizieren mir meine kleine Modifikationen hier in dem wir um dessen bis sind von der Formalität der einfacher zu gestalten führen jene rückwärts wo kann ein wenn es nicht schon gibt ja von p nach S ja dann können wir nämlich hier anstatt den hier einfach maximiere XTS schreiben und hier oben müssen wir diese 2 Ausnahmen nicht machen wir bei den Hammer Fluss warten +plus erhalten neben Knoten alles was weiß fließt fließt auch raus und wir wollen sozusagen alles was davon von es nach D geschickt haben schicken über diesen neuen Bogen zurück ja und das ist das was man maximieren wurde also eine leichte Transformation von dem Problem damit mit wenigem unterscheiden müssen einer Ausnahme S und T beziehen sich in der Zielfunktion meine sehr einfach strukturierte Zielfunktion da also es immer noch dasselbe Problem dar deutsche aber was hat es bei Rock mit uns zu tun mit unser total Modularität ja wenn wir das jetzt noch mal neu schreiben das steht hier maximiere XTS ich schreite mal in Matrix vom A x gleich 0 ja und 0 kleiner gleich x kleiner gleich 10 zum was ist dieses aber das hat mir letzte letzte Stunde schon kennen gelernt wir dieses nichts anderes als die Knoten kannten Inzidenz Matrix Knoten könnten Inzidenz Matrix der von der Rissener dies total ohne modular waren oder zumindest war es eine Übung beweisen können so das heißt wir wissen dieses dieses Polyeder hier was doch dieses System beschrieben wird ist ganzzahlig die Ecken der zusehen ganzzahliges heißt wir kriegen hier automatisch ganzzahlige weg Lösungen ja das heißt wir brauchen ja gar nicht Z +plus schreiben sagen es macht keinen Unterschied aber +plus oder C +plus beging automatisch ganzzahlige IT-Lösungen ja und das 2. was wir noch dazu wissen ist das nach dem wenn er total im als auch die transponierte ohne modular bilden sich die gleiche Auto dran und also die gleiche Aussage auch für das duale ja und beide werde müssen Gleise und damit müssen beide auf von ganz zeigen .punkt angenommen werden dass er mal hier mal gemerkt zusammengefasst in der Folgerungen 2 19 gut da fällt mir ein bei der Gelegenheit ich würde das letzte Mal nach der Folgerung noch auf dem Client wie das letzte Mal aufmerksam gemacht soll ich dann gleich noch was sie vergessen hatte zu sagen also sehr an eine ganzzahlige Matrix an ist total Uni modulare genau dann den soll kommt es Primaria maximiere c't iX A X gleich B X größer gleich 0 so das Wissen außen Dualität Satz ist ja das gleiche zu minimiere BTZ +plus gute y unter der Rahmenbedingung erzählt +plus y größer gleich C und y größer gleich 0 genau dann wenn beide ganzzahlige Lösungen haben genau dann wenn Marx und den ganzzahlige ob die Wahl Lösungen haben das ist bisschen gequetscht werden also nochmal was war das Argument total Loyola ist dann das letzte Mal kann zeigt impliziert dass dieses Ding ganzzahlige ist Mehr wir wissen hier steckt er steckt der Dualität Satz der Linearen Programmierung drin dass ein geniales Programm das ist das duale lineare Programm dazu die Gleichheit gegen außen Dualität Satz das jene ganzzahlige Lösungen kriegen aus Modularität ja dass das duale Aue ganzzahlige Lösung war Klinge aus dem das wenn total und im Modul leisten auch transponiert und wenn ich die Einheitsmatrix dran hängen bleibt die total ohne Modularität erhalten das letzte Mal
uns angeschaut so und das können wir jetzt sozusagen direkt diese Situation wenn wir jetzt auf unser Beispiel hier an wir schauen uns das anvisierten es ganz konkret aus also Satz 2 20 maximale Fluss 2 G gerichtet 10 sein könnten Kapazitäten C Element das Plus für E aus E dann gilt der Wert eines maximalen Flusses ist gleich der Kapazität weil der Wert eines man Einschnittes n wo gut wenden das eigentlich direkt auf diese Folgerung an so wissen dass er es es also nach Folgerungen der rechts oben stehen haben 2 19 und das Schreiben des kleinen der speziellen Form Max X es oder Randbedingungen A x gleich 0 x größer gleich 0 =ist gleich minimiere transponiert y unter der Bedingung dass ATZ +plus y größer gleich die der 1. Einheitsvektor ist und y größer gleich 0 haben ganzzahlige optimale Lösungen wenn Altix Quelle Z Quelle und y qué werde ja so was steht jetzt hier also hier steht er der Wähler Eismax Warenflusses es ist aber auch dass die würden richtig interpretieren dass es tatsächlich den Wert eines minimal steht es entspricht zu schauen uns mal den Bedingungen an die angelesen sich diese Nebenbedingungen an also schau mal es steht die Omaner Tafel das als die Knoten kannten Inzidenz Matrix ja die Zahlen sind die Knoten gespalten sind die Kanten zu machen wir schauen uns transformiert an in aber sowieso mir 10 die Zeilen die Knoten die Kanten und gespaltene Knoten sollte so noch mal gucken was steht in jeder Spalte in jeder Spalte steht wenn sie den stimmt weiß wie bekannte hier Trendence sozusagen mit plus 1 wenn sie aus dem Knoten rausgebe -minus 1 Knoten rein geht es heiß in jeder Spalte von Ar hier genau 1 +plus 1 1 -minus 1 das heißt jeder Zeile von transformiert steht genau 1 +plus 1 1 -minus 1 also da haben wir schon mal der 1. heißt die die Struktur sieht so aus also aber also die die Bedingungen hier von transformiert z +plus y größer gleich ECS das sehe einmal alles Z klären plus -minus ZVO Quelle +plus YUV quer ist größer gleich ja 0 Files Frau ungleich DTS ist und das ganze Ding hier ist für den Fall TS größer gleich 1 für diesen Fall um also den sie darum dass genau das geschrieben ist an der rechten Seite steht er an einer Stelle 1 unseres über 1 0 ist wie genau die 1 an an der kann an den Bogen TS so also soll das interpretieren so was können wir jetzt hier für Aussagen machen wir diese Lösung mit schauen uns nur so mal denen was man eigentlich alles gelernt haben konnte ganz schön wieder können Aussagen über diese Variablen diese y System das sozusagen diese schlug Variablen jede zukommen sozusagen so dass Einheitsmatrix mal y steht der hier was können über diese Aussage den TS hier machen müssen und dass er den Ansatz von komplementären Schlupf wer erinnert sich an diesen was hat der ausgesagt der Beziehungen gesetzt von Lösungen das prima Jahren Programms mit Lösungen das purer linearen Programm ist 100 Aussagen darüber gemacht wo man von man wie man optimale Sohn charakterisieren kann und kommen in der das Lob der Name schon sagt es kann nie gleichzeitig an war auf beiden Seiten Schlupf geben soll das heißt wir bisher im dualen gibt es zu jeder Ungleichung viele umgangen prima eingibst der Variablen und umgekehrt wieder Variablen prima Beziehungen Dual so dieses y ja gehört und solche aus vergessen also ich könnte noch kleiner leicht sie dazu dieses y gehört genau zu diesem wie dem X kleiner gleich 10 ja das heißt wie die Ungarn die wir hier haben gibt es die zugehörige y ab so jetzt sagt der Schlupf Satz ohne der Schlupf entweder das X ja ist hiermit Gleichheit erfüllt also Ende des XE gleich CE oder des y da ist gleich 0 es kann ihren beiden Stellen Schlupf geben es kann nicht gleichzeitig bis y positiv sein und gleichzeitig jedes x dem C sein ja das ist Optimalität ich wenn ich mich so hier und da bewegen könnte dann bewege ich mich auch dann kann nicht optimal sein wird sein
sozusagen anschaulich gesprochen es seit ich muss entweder dort oder dort an die Grenze gestoßen sein so wird schauen das mal anders ist die Grenze von diesen XTS da mal keine Kapazität vorgegeben wird diese Kapazität von dieser Variable hier CTS ja die haben am Anfang auf weiblich plus unendlich gesetzt weil man ja nicht wissen was ist der maximale Fluss der zurückfließt das heißt die oder im Computer gar ich mir sehr große Zahl hier angeben zum Beispiel die Summe aller Kapazitäten +plus 1 also als unendlich kann man hier zum Beispiel schreiben Summe aller CE er oder sie +plus 1 ja die Zahl wird sicherlich nie erreicht werden das heißt dieses x das XTS dazu ist sicherlich kleiner als das CTS ja und aus dem Satz vom kommen mit den Schlupf folgt damit dass die komplementär war dazu an der Grenze seines also ist und wie es gleich 0 also Satz vom komplementären Schlupf liefert das Y PS quer gleich 0 ist so ist heißt wenn jetzt die letzte hier umschreiben man daraus folgt CTS ist größer gleich 1 plus CR Square an sollen jetzt packen wir hin das packen in in eine Kloten Menge W wie definieren wir jetzt als alle Knoten die mindestens denen
werden mindestens so groß ist wie der mit der von den Tee ja einen 7 sofort das P es sind wegen dass es es nicht den Weg an aufgrund dieser Beziehung an also haben also nicht mit es sind auf der Suche nach zum Schnitt ja aber der es und die brennt ja und dazu ausrechnen was dessen Kapazität ist Mehr dessen Kapazität ist folgende es war uns noch diese Beziehung an Na aus der Beziehung hier oben folgt das bis Y quer VW musst größer gleich 1 sein ja warum wir hier steht sozusagen der eine ist auf der einen Seite der Samen mindestens um der ewige so mindestens 1 größer als der bis Z quer also mindestens 1 größer als das Z ug quer da muss das höchste UVB wer mindestens ne 1 hatte ja das heißt die die duale Zielfunktion die steht hier daraus folgt y qué wäre er ist mindestens also Entschuldigung ist damit ein ungeschriebenes werden 10 für die dass er die Kapazitäten der Beschuldigung der y quer ist die ist mindestens so groß wie eine UV in dem Schnitt CDU-Frau du sollst wissen aber dass hier Gleichheit gilt das heißt der maximale Fluss ist mindestens so groß wie dieser Schnitt aber er kann ja nicht größer sein es ganz schon festgestellt maximal ist ja Oberstein Gysi der Schnitt das heißt die beiden werde müsse übereinstimmenden daraus folgt während der maximale Fluss ist mindestens so groß wie der SC Schnitt wie aber wir wissen aus unseren Vorüberlegungen ist aus den vor Überlegungen steht hier auch eine höchstens Mo und dabei muss Gleichheit gelten kann zu und damit haben wir auf diesem Weg sozusagen bewiesen dass der maximale Fluss gleicht einem Einschnitt ist und was mir zusätzlich Geschenke liegen sozusagen wenn die Daten ganzzahlig sind entgegen automatisch ganzzahlige Lösungen x Krebs-Füllung will und das haben auch hier ausgenutzt Mehr an diesen Stellen weil das immer mindestens Abstand einsam ist auch mindestens 1 und weniger an Kunst sein ganzzahlig sind dann haben wir hier sozusagen diese kombinatorische Echallens nachgewiesen gut das ist so eine Delle der großen Beispiele sozusagen die total und modular singen kann es gibt im Gegensatz zu ändern in der Graphentheorie wäre total ohne modulare Matrizen charakterisiert und der sagt im Wesentlichen wenn Matrix Zuteilungen modular ist dann muss aus dem Netzwerk Matrix entstehen also aus dem Grafen im Wesentlichen den Knoten kann wenn sie denn Matrix sein es gibt 3 4 kleine Ausnahmen sozusagen von der Größenordnungen wie es denn gewollt 7 oder in der Art aber letztendlich lässt sich ist auf diese Ausnahmen jede Matrix so zusammensetzen die total ohne modulare das heißt wenn man jetzt wieder aus Anwendungskontext schaut wenn nicht mehr Netzstruktur dahinter ist ist es praktisch unwahrscheinlich dass die Matrix total ohne modular ist das zeigt auch das 2. Beispiel lassen uns anschauen dann nicht den für den gerichteten Falles komme ich auch genau aus Matrixstruktur er und das sind die Partie des Grafen wo so habe ich die Hoffnung die wenig indische das letzte Mal da lassen wir auch da bleibt aber nicht zu wunderbar gibt's nur in wenn ich zumindest letzte Mann gebracht werden den kann ich da lassen aber der immer mit ist ja ob ja also 2 der Anwendungsbereich sind die Partie des Grafen wer weiß nicht was in die Partie der Graph ist auch eine Handvoll wer kann von denen die nicht die Handlung um den andern entstehen wir die Partie Check der schon im Namen Partition das teilen also man kann stylen wie mit 2 also man kann Graph G als die Partie geht falls Frau sich zerlegen lässt in 2 Teile V 1 und V 2 vor 1 gestellten V 2 leer mit der Eigenschaft dass es sozusagen die Teilmenge es aller Kranken alle UV mit kann Frau aus aus V 1 und Frau aus vor und zwar in dem was heißt das also wir können unsere Grafensohn darstelle haben in werden mit Klasse von 2 Knoten man ihres Vereins jedes V 2 und alle kannten es gibt die laufen nur zwischen diesen beiden in Ihnen Herr ja das verbittert es gibt netten Satz in der Grafen der zu Bipa Tim Graph nicht was wir sehen ist ist oder die Platine Strukturen da können keine ungeraden Kreise aufträten werde das als ungerader Kreysig möcht Tiere im Kreis basteln ja wir sehen sozusagen ich auf die eine oder an der Seite gehen wenn ich damit ich im Kreis machen kann warum da könnten einige er muss sich um an den Ausgangspunkt zurück Kopf zu kommen muss ich immer gerade auf 7 herlaufen an den Kreis zu schließen ich Überlauf hab immer eine ungerade Anzahl an aber wenn ich jetzt im Kreis basteln will dann Bram musste in eine gerade
Anzahl von Knoten hat er vom Krankenhaus wer alles offensichtlich wenn geht die Partie geht es er dann folgt es existiert kein ungerader klar ist nur es gibt es eben Satz an wollen als der beweisen es geht auch umgekehrt also wenn ich weiß in den Grafen es keine keine ungerader Kreis reden dann finde ich immer eine Aufteilung in 2 solche Kloten in das alle kannten jeder zwischen laufen soll bei der schwer zu zeigen was man nicht macht ist man fängt einfach an einen Knoten an und läuft los machte die Versuche der und jeden ungeraden man schaut sich einfach ist an jedem 2. jemand findet packt man auf die gleiche Seite und in den ungeraden auf die andere Seite nachdem man ungerader Kreis auftauchen muss geht es genau auf ja und das macht man mit allen Knoten müssen sozusagen ist ein wenn erwischte damit alle oder wenn's unzusammenhängendes nimmt man noch ein immer noch nicht erwischt hat und kann es so mit aufteilen und das geht gut war kein ungerader Kreis ist drin ist das was ich hier im Graben gegeben wo ich weiß kann ungerader Kreis endlich auf die Art und Weise die Sie die Partitionen so was alles ist das vielleicht nur ein bisschen als ist Nachgang zu zu Grafen und Algorithmen was uns jetzt eben anschauen wollen ist genau auf die Gerichte begraben Sieg an Knoten kranken oder kannten und Inzidenz Matrix also es sei G Frau ,komma E umgedichtet und ja die Kranken Knoten Inzidenz Matrix also wieder Beispiele damit ihr sowas haben 2 3 n wenn wir alles durch ja dann machen wir es eben im Matrix auf jede Kante aber 5 Stück 1 2 und 3 4 5 dann haben wir 1 2 3 4 4 Knoten so dass man einfach eine 1 zu 1 wenn die mindern dafür wenn die Kante so zeige beim Club mindern verbindet als kann der 1 verbindet Knoten 1 und 2 ich kannte 2 verbindet 2 und 4 3 2 und 3 4 1 und 3 und 5 3 und 4. keine zum interessante Fragestellung gesetzt wenn uns von von diesen von die von diesem Madrid 10 die das zugehörige Leder anschauen werde also interessantes Polyeder ist das folgende P reicht die Menge alle x mit AIX kleiner gleich wie ja und diese Knoten Kappe kannten würden sie den Smart warum ist es interessant dass es schon allein interessant für den Fall dass sich jeder einzeln schon also weniger Stadt-Immobilien eines hinschreiben was für Probleme haben einen nicht danken was steht denn hier schon was es noch mal an da habe ich so und was steht denn hier in dem kleinen Beispiel X 1 +plus x 2 kleine gleich 1 ja x 2 +plus x 4 kleiner gleich 1 und so weiter oder allgemein die bekannte hab ich jetzt jene Bedingungen die sagt X +plus x v kleiner gleich 1 für alle UV im EG das ist das was hier steht zu den erinnern diese Randbedingungen was wenn 1. Vorlesungen schon angekommen ab wer was sagt diese mit nem
zusätzlich noch die Variablen sollen 0 1 der dickste also X UV aus 0 1 so sagt dann XU +plus x v kleiner gleich 1 ich dafür xes ein von dem wenig kann der habe ich höchstens 1 von den beiden nehmen so war wie sieht dann zulässige Lösung von dem Problem aus Wasser was heißt es in der braven sprachen mit zulässige Lösung von X kleiner gleich 1 was heißt es hier nennt sich dieses Konstrukt stabile Menge an also wenn Zweig jeweils 2 Knoten Breinig bindende benachbart sind es sehr stabile Mengen Craven also Lösungen hier sind gleich stabile Mengen jetzt weiß man auch das aber nicht gemacht das kann man nachweisen dass stabile Mengenproblem finden eine maximale stabile Menge in einem Grafen bis auch unendlich schweres Problem ja das heißt allgemein über diesen Polyeder zu optimieren ist ein per schweres Problem trotzdem gibt es vielleicht interessante Teilstrukturen ja die sozusagen er das vielleicht doch polynomial hinbekommen und die Teilstrukturen die das tun 10 genau die Kanten Knoten Inzidenz Matrizen nie zu die Partie dem Grafen gehören in dem Fall also ja für jede beliebige rechte Seite man kann sogar noch charakterisieren nur für die ich mir nie die rechte Seite 1 steht es führt dann auf perfekte Grafen so weil Burmester einsteigen gegraben tigungen charakterisieren kann man sozusagen unter welchen Bedingungen er hat dieses Polly immer ganzzahlige Lösungen ja und das kann man machen das 4. auf perfekte Grafen gibt es in Berlin Satz der sagt ja deshalb genau dann ganzzahlige Lösungen wenn keine ungeraden Kreise stecken oder deren Komplement also man muss nicht nur die ungeraden Kreise ausschließen The sondern auch noch Komplimente von ungeraden klar ist ja und natürlich kontrahiert also sagen wenn sie nicht als alles als nie nur als Teil geraffter steckt hat das vielleicht nur mal an der für diejenigen die schon bisschen Craven die gehört haben also der Gesindes an der Verknüpfung zu Grafen theoretischen Fragestellungen gut es war uns das aber hier anschauen also das eine was merkt er erst mal feststellen wollen und das ist dann in Beispiel formulierte schauen und Übung an wenn so ungerader Kreis drinsteckt dann dann verlieren wir ganzzahlig kalt das ist das Beispiel 2 21 sei wir eine Frau ,komma E 10 Kreis dann gilt sehen in Mehr Inzidenz Vektor von Frau von 10 Cäsar Inzidenz Vektor von Frau von C reisen sie denn es wird doch noch mal ist 1 genau dann wenn der Knoten in der Menge ist um 0 sonst und sie wird dann wird dann gilt noch die Tafel 0 wir werden das gilt für
das für Marx c't iX 0 kleiner gleich x kleiner gleich 1 und XII oder X O +plus x v kleine gleich 1 US-Firmen 1. das X E Stern gleichen halb für die ist mit den US USA aus diesen Kreis um 0 sonst wenn nicht aus dem Kreis ist ist optimale Lösung von diesem Programm hier von Sternen und das 2. ist X Stern ist keine konvex Kombination von stabilen Mengen mehr das schauen Übung an ist mehr ganz der Wiederholung von der Linearen Programmierung ,komma leicht mit mit Argumenten der Linearen Programmierung lösen soll das heißt wir wissen wir jetzt wir unsere Ziele waren totalen Modularität wir wollen ganzzahlig keine haben ja was wir sehr müssen ungerade Kreise ausschließen kann so und und was jetzt zeigen wollen dass sie mal diesem Beispiel wenn wir uns auf die Partie begraben beschränken dann die genau totale ohne Modalitäten und dann wissen man auch dass dann das zugehörige lineare Programm was hier steht ganz zeigt ist ja das ist der folgende Satz Satz 2 22 ist zur Teilung des modularen genau dann werden dedicated des war ich das Carrell Charakter des das doch nicht wann dieses da rechts um immer ganzzahlige ist ja sondern das ist nur der Einschränkungen zu wir leisten muss das zugehörige geht die Partie zu wie kann man dieses Polier rechts oben ganzzahliges das führt uns auf diese perfekten Grafen und dieser Satz zu zeigen dass dieses Polyeder ganzer ist genau dann wenn keine ungeraden Greise den Komplement darin enthalten sind wissen wie gesagt der erst vor paar Jahren 2 3 Jahren bewiesen wurde die Vermutung dass zu beweisen war 30 Jahre offen und das ist wie gesagt vor 2 3 Jahren ist bewiesen worden dass es dort auch diese Charakterisierung Getier beschränken uns auf diesen diesen "anführungszeichen einfachen Fall wer so also wie eine Dichtung haben wir ja schon also wenn ich das also wenn das Ding total ohne modular ist und dann dann muss geht die Partie zu am also die eine Dichtung also wenn total und modular ist dann wissen wir dass dieses Programm ganzzahlige ist dann ist mir das P die Menge aller x a x kleiner gleich B oder gleich ich nur mit dem Fall als kleine gleich 1 x größer gleich 0 es ganzzahlig nur angenommen das denn wenn nicht die Partie mit ja angenommen wir nicht debattiert es mit dieser Aussage hier das ist die Partie was sie Umstieg genau dann wenn keine ungerader Kreis drin ist das heißt daraus folgt es existierten ungerader gereist ja und dann folge dem Beispiel das mir nur was stehen wir auf der linken Seite folgt mit Beispielen 2 1 20 es existiert der gebrochen hätte ja und dass ein Widerspruch einerseits wissen außer total Realität es ganz heißer Seeweges ganz eigenes nicht die debattiert wäre hätten eine gebrochene Ecke und das kann nicht sein das eine die einfache Richtungen zwar die umgekehrte Richtung bis ein bisschen knifflig und da gibt es aber eine nette Beweise die die wir die wir hier mal so spielen wollen nämlich was man gerne macht ist in der ganz zeigen Optimierungen wir müssen jetzt zeigen dass wenn es ihn gab ganzzahlig ist das um das zu zeigen dass es total ohne modulares wie diese etwa lehnt er ab zu zeigen dass dieses Polyeder ganzzahlig ist ja so wie zeigt man ganz Heiligkeit von Politikern da gibt es verschiedene Techniken das zu tun eine wollen uns mal anschauen was man macht es wann würden ein man eh wieder mal löst die bis die lineare Programmierung sehr lax Junge vergiss die Ganzheitlichkeit löst das lineare Programm ja wenn man Glück hat ist es ganzzahlige wird dieses Glück hat man häufig nicht was man dann gerne macht bis 900 einfach ja man die gebrochenen Werte und rundete auf oder ab und wer es geschickt macht Gegner man vielleicht den ganzzahlige Lösung mit denselben Wert und dann weiß man auch sozusagen das und insbesondere 0 1 Fall das weil dann die Ecken 10 immer gar ist gehören außerdem ganzzahlige müssen das sozusagen ganzzahlige kann sein so diese runden Augen ab und als gleich zulässig klappt auch leider nicht immer und was man dann und zwar Ende nächstes Element Wasser reinkommt was man gerne macht das man macht zufällig man hundertmal zufällig auch zu fällig ab wie Schwierigkeit er selber wann Sommer auf und ab und welchen Wert zum Beispiel hab typischerweise mehr hier auch heute kann so werde von halt auch solches Inhalt auf eine solch abrunden soll 0 Komma 6 auf oder abrunden ja was passiert wenn ich auf runde das sehen wir hier an dem Beispiel wenn ich eine eigene aufrundet erkannte sein ich bin wirklich unzulässig das heißt sie mussten an der den zugehörigen dem Partner Knoten aber und damit wieder zulässig bleibt an und genau diese Spielchen schauen uns jetzt mal an und wenn man es geschickt machen unseren kleinen Zufall Streuer reinbringen denn wenn wir sehen dass wir damit automatisch diese ganz Ehrlichkeit beweisen kann und dieses spielen mit dem Zufall sage ich mal oder mit Erwartungswerten bis 1 in das wird häufig gerne eingesetzt wenn man später auch noch mal sehen wo man das geschieht über einsetzen kann um dann gewisse gant alle Ganzheitlichkeit Aussagen oder aber auch diese Garantien von Lösungen nachweisen zu können also wenn wir lösen meiner zierung also wir lösen löste Max c't iX A X kleiner gleich B x größer gleich 0 und sei ich Stern eine optimale Lösung
so wird kostet uns da draußen wie gesagt X Stern es erstmal außen er noch n muss nicht ganzzahlig sein Glück konnte ihren Sitz daraus der ganzzahlige Lösungen als mein ganzzahligen legt zeigen danach dass der auch zulässig ist in der Mehr das Aufrunden falls E aus der 1. Teil der BR der Tradition ist man aus der 1. Mängel und XI Stern -minus x ich dann abgerundet größer gleichen gewissen Wert ist ja und so seine Zufallsvariable Zufallsvariable aus 0 1 hören und wir tun das bei so einer halben die aber wird mit einmaligen so fest wir unten auch auf wenn es aus der 2. Menges aus V 2 und die Differenz aber dann größer ist als 1 -minus u wir und in allen anderen Fällen und nur ab danke so jetzt müssen wir nachweisen erst mal nachweisen das ist ne zulässige Lösung ist also ganz zeige sie offensichtlich die Frage ist nur für die uns X kleiner gleich B .punkt also schauen uns das mal an ich war es mal den 1. Fall an also sei kl mit kannte so wir schauen wir unterscheiden 3 Fälle der 1. Wahl wenn ich das wenn ich mir die ab wenn ich mir die abgerundeten werde anschau und da kommt gleich schon die rechte Seite raus wenn wir kucken K L und auf der rechten Seite steht dann ein i ja das sei die Idee Zeile von das Unternehmen wie die Jungs Matrix was kann ich in dem Fall sagen da wenn man die abgerundeten werde schon gleich den Wert ergeben ja dann muss dann müssen wir ohne die Abrundung was ja auch schon das PEI ergeben haben wenn das EEG Steinmeier zulässig dass weit zulässige Lösung wenn die abgerundeten der des BDI Schaller geben da muss auch auch bis x Stern selber gleich den XK sein also dar so wissen wir das Ding =ist gleich x gar Stern und des is gleichen XL sterben ja aber von dem muss man ja dass dieses zulässig ist ja also das heißt wenn ich gibt beiden werde der Runde dann ist es offensichtlich zu lässig nun also der Fall ist einfach der 2. Fall der auch es ist wenn beide Werte kleiner gleich B -minus 1 sind also wenn ich das abrunden kleine gleich wir -minus 2 sind so dass sich auch in Ordnung es das Schlimmste was uns passieren kann ist dass ich zweimal auf ohne die werde aber mit immer noch kleiner gleich i ja so der einzigen das an der Fall es wäre wenn die beiden gleich aber Berlin -minus 1 n so wenn dem so ist ja dann folgt aber das was man Luft haben alles XK Stern -minus x Stern abgerundet Mehr +plus des XL stellen -minus des XL Stern abgerundet muss kleiner gleich 1 sein warum ist dem so bis XK stand muss das XL Steine sehr kleiner gleicht dem W und die beiden zusammen sind wie ewiges Eis wird es auch heute der kommt leider gleich 1 das kann so das heißt ich weiß so und jetzt kommt mir ist aber noch mal was hier rechts steht es aber es gab geschickt so gewählt werden das wäre in dem Fall nie beide gleichzeitig aufrunden ja warum also entweder wenn dieses Ding mir daher gleich ist schauen wir und mir den auf also wir würden den 1. aufrunden wenn diese Differenz größer gleich dem ist das aber diese hier der eine als 1 -minus u kleiner gleich 1 wenn es um das es heiß würden dann in sonst fallen nehmen oder umgekehrt wenn das Ding größer als 1 -minus so ist ja und wir würden wenn ich sie stand auf und dann wird man dann ist parallel dazu der hier ich kleiner als dem würden dann auf ja das heißt daraus folgt also nur maximal ja maximal K oder L werden aufgerundet ja und daraus folgt natürlich dann das des ZK +plus des ZL wieder kleiner gleich dem W i s alles heißt es der selber ist zulässig also erfüllt AZ kleiner gleicht dem des solche aus noch die Zielfunktion an und jetzt machen wir es nochmal dieses probabilistische Argument und schauen uns an wie oft und den auch was die Wahrscheinlichkeit dass man auf rund was die Wahrscheinlichkeit dass man abrunden zur schauen wir uns mal an also wie die Wahrscheinlichkeit das ZK gleicht dem auf wert ist wer das ist ja lieber scheint es ist leicht es war scheint die die Wahrscheinlichkeit das ist kleiner gleich diesen Wert ist dass er gleich die Wahrscheinlichkeit das Na ja gleich XKR stand -minus XKR Stern abgerundet ist so nachdem es mir gleich verteilte Zufallsvariablen ist die Wahrscheinlichkeit dass es gerne gleich diesen Wert ist =ist gleich diesen Wert also es XK Stern mir Six gar Stern abgerundet und das gilt für den Fall falls K aus dieser Menge V 1 ist da haben wir den Fall analog also soll ich vielleicht ja schon allenfalls Chaos vor allem wenn so für andern Fall für Chaos war 2. zeigt man ganz genau gleich wer kriegt man ebenfalls heraus dass die pro die Wahrscheinlichkeit das des ZK aufgerundet ist auch wieder genau dieser Wert ist das Argument es genau das
Gleiche wenn wenn nützt mir gleich verteilt super Service auch 1 gesunde gleich verteile gleichverteilt zu vor 2 Jahren mein 2. Argument mit nur mit der 2. Zeile die hier stehen wer also insgesamt ging es sozusagen heraus die Wahrscheinlichkeit ja das sich auf runde ist genau diese hier wer den der gebrochene Anteil dieser Variablen ok sollen jetzt schauen uns in die Zielfunktion dazu an der und sich dann seine Zusagen C Stein ist die währt also sagen und so geschah es mal so zischt sei gleich c't iX Stern von dem Wissen das sicherlich dass das größer ist als als der optimale IP wert wäre C IP und warum ist dieser werde immer größer gleich also hier sicher DLP Relax ierung und hier alle die Forderung dass das ganze Zahl ist noch zusätzlich X ganz zahlen wir oben wenn ich zusätzlich vor dass sie werde ganz heißen Marianne zusätzlich Einschränkung wenn er die sagte schon der Lachs sämtliche Galaxie Bedingungen das sie ob die wir hier über eine größere Menge als hier hier ist es EEG Stern X aus einer Woche n und hier ist es x aus der doch n ja wir größere Menge optimieren muss natürlich sozusagen optimal wird auch mindestens so groß sein so von dem wissen war dass der optimale ganzzahlige optimal Wert ist die jährlich das sei des immer zu lässig ja das Normalste Zufallsvariable genommen die Bilder mal raus den Erwartungswert bilden also is sicherlich größer gleich dem Erwartungswert unser ich nenne es mal heuristische Lösung vor ja mit aber der peration gelöst und alles einfach heuristisch auf und abgerundet in Abhängigkeit von diesen und dieser Zufallsvariable so wenn wir das haben es schauen einfach anders ist der Wert von dieser lösen die hagern ausgerechnet der Welt ist ja mindestens mal ich alle Abgrund also eh Frau werden XII Stern der +plus so und jetzt kommt die Wahrscheinlichkeit dass wir die an dass wir sie aufräumten I aus VCI mal die Wahrscheinlichkeit eben das sich auf runde während das zb gleich XI stören aufgerundet es an so und dieser letzte Teil 1 dieser letzte Teil des American ausgerechnet das ist das gleiche wie bleibt alles gleich wird das Ding hier ist ja nichts anderes als XI Stern -minus XI Stern abgerundet ok so wir das jetzt anschauen und fliegt es genau raus und dann bleibt er stehen gleich Summe der CX nicht stören die aus Frau und das ist nix anderes als unser Ziel stellen ja und das ist so nicht zum Schacht uns Argument das kennen sicherlich auf schon häufig hier steht größer gleich hier steht links und rechts ist ergibt sich dann das heißt dieser Wert muss schon gar wegen der der ganz ein optimales und haben das heißt in dem auch die heuristisch bestimmen muss auch schon den ganzzahligen optimale dann das heißt sie haben tatsächliche ganzzahlige optimales und können auf die Art und Weise finden Sie höher also Essen nette Beweise die immer so Sozialauswahl aus Erzählung ganz Heiligkeit gewinnt eine Anlagen die wir damit auch noch schlagen ist wenn man noch mal zurück gucken was in aller 1. Vorlesung für Beispiele gebracht haben er was und Personaleinsatz Problem uns angeschaut werden sicher können wir eine Menge von so und wir haben Menge von Jobs und wir möchten dass jeder Person einen Job bekommt und damals hatte ich mir gesagt ist es wie Ganzjahresprogramm aus ist aber eigentlich Programm aber warum ist dem so mit der Zauber die Methode
entwickelt dass dem tatsächlich so ist die Frage sie sie war das ein also das klassische ich sag ich mal Personaleinsatzplanung ich hab ne Menge von Mitarbeitern Menge von Jobs wer macht welchen Job ist Eichen ein Problemen des gehen genau hier raus zwar nur noch uns anschauen wo hat oder Cops das alle werden hat sich normales Zuordnungsproblemen sie letzte Folgerungen dazu das Zuordnungsproblemen ich hab n Mitarbeiter .punkt auf un Jobs oder wenn Jobs dann machen wir ja auch Jobs erst mal Pet Shops mit gleich P und jeder soll einen Job machen da hat man damals formuliert XI hat war die Variablen aus 0 1 als ob Mitarbeiter I Shop J doch führt .punkt hat mir dieser Randbedingungen wir wollten die Kosten minimieren und minimiere zum inszeniert Exilort und wir haben gesagt jeder Mitarbeiter den Job und jeder Job braucht Mitarbeiter das war das Zuordnungsproblemen und warum ist es ganzzahlig also hier so formuliert als ganzzahliger als Bedingungen ist die Frage da ehrlich gesagt die Ganzheitlichkeit können und schenken aber es reicht hier was a +plus eigentlich warum können wir das tun damals alles zusammen dafür das müssen was muss nachweisen dass überhaupt in Zusammenhang mit dem was wir halt gemacht haben 1. steht in direktem Zusammenhang wenn wir uns das Problem einfach mal hin malen wollen wie wir das machen dass er sozusagen als Knoten auffassen wir hier aber die Mitarbeiter ja mal die die Jobs war und wir haben es praktisch kannte jede und jeden Mitarbeiter zu ihren Job um hohe so aber wir haben natürlich was hier nicht da ist so was ja oder sowas ne keiner keine Person zu Person zuordnen auch keine Jobs zu Jobs und unwürdige Mitarbeiter zu Jobs das heißt wenn wir das Ding als dem Grafen aufmalen das Ding ist die Partie ja und das hier ist nichts anderes als die kannten Kurorten Inzidenz Struktur von diesen Dingen die Knoten kannten Incident schon und ja jeden Knoten habe eine Bedingung war wie aus einem und sehr viel J aus P und jetzt die Maschinerie an also GSP Parted genau dann wenn die Matrix dazu total ohne modular also dass diese neben diesmal wird es total ohne modular nahe wird uns Umsatz das letzte Mal bewiesen haben das zugehörige des ganzzahlig das heißt wir können hier oft das 0 1 verzichten ok gut so weit totale und Modularität gibt es da noch nachfragen für BenQ Themenkomplex so wie gesagt was wir
bislang eher gemacht haben ist uns das angeschaut wir haben jetzt sozusagen vollständig charakterisiert man es ganz eige Programm Mehr ganzzahlige Lösung hat unabhängig von der Zielfunktion oder weg von der rechten Seite war das aber für alle rechten Seiten egal welche wiedergeben und es war auch egal für welche Zielfunktion weil wir immer die Aussage haben dann ist das zugehörige Polyeder ganzzahlig das Sezieren zur sein die uns auch noch egal ob die Funktion gar nicht es sei egal wo das ist unser den allgemein also heute wieder nett wenn der Prags ist aber nicht so weil meistens Hammer wir konkret der rechte Seite und konkret die Funktion und die Frage können wir dieses Konzept letzten Stück verfeinern so dass wir das ist sein auch für spezielle Rechte Seiten die Ganzheitlichkeit von machen können und auf diese die wollen uns jetzt begeben da müssen allerdings noch ein bisschen daran arbeiten das würde sich auf total dualen Legalität und um das zu machen ,komma noch ein paar müsse es ein paar Hausaufgaben erledigen wissen sowas kennen lernen wenn er damit Normalform wir müssen sowas kennen lernen wegen des Geredes Analogon zum Farkas Lehmann dass wir uns anschauen also es war Gast der Mehr wir können sich noch schwach erinnern aus der Einführung es ist Farkas aber es gibt einen ähnlichen Aussage für ganzzahlige pro Programme oder Apps ganz ab Leitungssysteme Ganzheitlichkeit Anforderung und dass wir uns jetzt sozusagen in dieser und der nächsten Stunde arbeiten und das ist ein ganz zentrales leer Maui ähnlich wie das Farkas im Mini in konnte die jährlichen Fall wird dies auch im ganzzahlig heitsfall werden häufig verwendet und das war uns aber arbeiten ist ist unter den Unterkapitel Mitchell Normalform 2 3 D damit Fische die Frage die sich uns stellt ist wie ich mir das hier wenn wir uns so man an der 1 Index Verfahren Erlös dieses Problem auch mit der machen Matrix Manipulation nur also die Erreichung System zum Lösen ganz konkret außerdem Erziehung können Sie der eskalierenden wegen vielfachen agierende viel falls einer Zeile 10 anderen brauchen sozusagen seine Preis Gestalt zu kriegen und damit sozusagen die die Lösung zu identifizieren wenn wir jetzt im Bereich der ganzzahligen Welt sind und was sowas einig auch tun werden wir haben gleichen System X gleicht wie ein Ei wollen wir so was weniger aus Elimination des wäre ideal für wenn 1 gleicht der machen daraus immer zu Klima Ganzheitlichkeit aus so das Problem lösen wird daraus kann man so nicht machen weil sowieso alle wird irgendwo geteilt und mit vielfachen beziehen und so weiter so dass dort in der Regel rationale 1 Ende rauskommen es lässt sich auch nicht vermeiden so was wir aber gerne hätten es sozusagen der hier Operation kann ich den erlauben die mir ganz Heiligkeit erhalten also Frage ist ich hab es ist dem ich schaue mir die zu wie ganzzahligen zulässige Lösung eines manipuliert ich des System das möchte ich wissen welches manipuliert hat es danach die Menge der zulässigen ganzzahlige Lösung dieselbe wie im Ausgangs System Mary Operation gar nicht erlauben das zu tun ja und dies ist für uns auf diesen Begriff der elementaren Zeilen und Spalten Operation oder auch ohne modularen Zeilen Spalten Operationen so uns in da vorstellen wie Allah in die uns das erlauben was macht ganz Heiligkeit nicht kaputt das kaputtmachen zu in der Regel immer sowas wie teilnehmen wenn ich doch 2 Teile wird aus nur 1 Inhalt ist schlecht also sowas wie vitalen seit bisschen aufpassen aber was können wir machen also ganz elementar ist ich kann zum Beispiel tauschen kann Tauschen von Ceylon Sport auf Spalten tut nix zu Sache ist eine egal in welcher Reihenfolge ich das aufschreiben ich kann es tut allen weh sozusagen was auch von einer Zeile auf andere drauf zu addieren ja wenn ich nur die Zeile selber drauf addieren wenn es vorher ganzzahlige weiß auch danach wieder ganz sein so und das 3. was ich eigentlich tun kann das kalendarische mit eigentlich wirklich ja so ich da wenn dann nur mit ganzen Zahlen eskalieren ich wieder ganz alles als sei es ein was sie einen erlauben dafür sie plus und minus 1 skalieren ja wir wir beliebigen ganzen Zahlen ja das am Ende zieht denen ich mir eine Zeile auf 1 drauf war dir ja einige Zeit ist er wird aber die habe ist dass sozusagen mit 2 multipliziert das heißt das Axiom muss ich mir extra fordern ja also es heißt Althammer würdigt die elementaren Operation zusammen so die diese nennt man elementare Operation ob Operation und dann schau mal Männer die ausführen was kann man denn maximal rauskriegen und das Wasser maximal rauskriegen können ist man damit ja mal vor Jahren die Definition schauen uns gleich noch andern aber die Begriffe schon das nächste Mal ist die Definition 2 24 die Folgen Operationen heißen um die modulare oder auch elementare Spalten beziehungsweise 2 Operationen das Erste was ich erlaubt ist Vertauschung von 2 Jahren zweier Zeilen beziehungsweise spalten Multiplikation mit minus 1 mit plus minus 1 plus 1 macht endlich ich 10 Additionen Additionen 1 Hischam es ist dann doch dazu ganzzahligen vielfachen einer Zeile oder Spalte auf eine andere einer Zeile oder Spalte zu einer anderen andere Zeile oder Spalte so dass sie die einzigen 3 lieber haben wie gesagt dieses gibt hier können auch nur ohne ganzzahliges Vielfaches an dir agiert in dem Mehr dieser Multiplikation und wiederholtes Anwenden dieser Addition von einer Zeile auf sich selber wird man damit auch im kommen ab wie gut die Aussage sich dieser Mitchell Normalform es ist aber wie 2 A eine Matrix mit vollem Zeilen mehr ist in Abidjan Normalformen ist damit schon einmal vor zur aber so aussieht das von der Form B ,komma 0 es regulär nicht
negativ und eine untere Dreiecks Matrix und nicht Ergativ und der unter der Dreiecks Matrix und jeder Zeile für nahezu jede Zeile also B I I ist echt größer als alle Einträge in der Zeile J 4 J kleine ihn also in in jeder Zeile gibt es einen App genau ein maximal Eintrag das sitzt genau auf der wir wollen erhalten wenn das heißt in Nähe wir eine untere Dreiecks Matrix des heißen das Ding sieht so aus ja wir die ap diagonal Elemente und jedes dieser ist größer als jeweils die in die in der Zeit des stecken der das Thema schon dass man die Richtung gingen auch bei daraus machten und man hat nur mit Dreiecks Gestalt haben und dann kann man auf die Art und Weise die rechte Seite hat doch für Platz 1 setzen sich Lösungen arbeiten die Frage ist sozusagen wird eigentlich steht hier man sich nicht viel was anderes als das was er bei Garaus auch kann ist die Frage schafft man das denn so Struktur zu belegen nur mit diesen elementaren Operation Krieger des tatsächlichen und Märklin des tatsächlichen aber das schauen wir uns nächste Woche dann an das schon
Quelle <Physik>
Matrizenmultiplikation
Extrempunkt
Laufzeit
Kombinatorische Optimierung
Physikalische Theorie
Zahl
Computeranimation
Gradient
Kapazität <Mathematik>
Lösung <Mathematik>
Arbeit <Physik>
Graphentheorie
Matrix <Mathematik>
Matrizenmultiplikation
Formation <Mathematik>
Fluss <Mathematik>
Optimum
Kante
Inzidenzalgebra
Ganzzahlige Lösung
Physikalische Theorie
Dualität
Linie
Uniforme Struktur
Vorlesung/Konferenz
Zielfunktion
Ganzzahlige Matrix
Parametersystem
Polyeder
Obere Schranke
Graph
Kategorie <Mathematik>
Abbildung <Physik>
Charakter <Topologie>
Hausdorff-Raum
Zahl
Maßeinheit
Kapazität <Mathematik>
Summe
Lösung <Mathematik>
Lineare Optimierung
Schnitt <Mathematik>
Ecke
Nebenbedingung
Matrizenmultiplikation
Aussage <Mathematik>
Fluss <Mathematik>
Optimum
Kante
Randbedingung <Mathematik>
Inzidenzalgebra
Transformierte
Zahl
Computeranimation
Kapazität <Mathematik>
Summe
Lösung <Mathematik>
Variable
Ungleichung
Menge
Vorlesung/Konferenz
Kreis
Matrix <Mathematik>
Polyeder
Matrizenmultiplikation
Graph
Klasse <Mathematik>
Randbedingung <Mathematik>
Kante
Inzidenzalgebra
Partitionsfunktion
Ganzzahlige Lösung
Kapazität <Mathematik>
Teilmenge
Menge
Vorlesung/Konferenz
Zielfunktion
Größenordnung
Schnitt <Mathematik>
Graphentheorie
Struktur <Mathematik>
Parametersystem
Kreis
Komplementarität
Matrix <Mathematik>
Polyeder
Aussage <Mathematik>
Kante
Inzidenzalgebra
Vektor
Ganzzahlige Lösung
Richtung
Lösung <Mathematik>
Erwartungswert
Variable
Menge
Globale Optimierung
Ganze Abschließung
Lineare Optimierung
Vorlesung/Konferenz
Ecke
Matrizenmultiplikation
Ganzzahlige Lösung
Summe
Erwartungswert
Variable
Menge
Zufallsvariable
Ganze Zahl
Rundung
Schnittmenge
Vorlesung/Konferenz
Zielfunktion
Normalvektor
Addition
Folge <Mathematik>
Zusammenhang <Mathematik>
Matrizenmultiplikation
Polyeder
Gruppoid
Verweildauer
Randbedingung <Mathematik>
Inzidenzalgebra
Ganzzahlige Lösung
Multiplikation
Variable
Menge
Ganze Zahl
Normalform
Ganze Abschließung
Vorlesung/Konferenz
Zielfunktion
Axiom
Sierpinski-Dichtung
Lösung <Mathematik>
Matrizenmultiplikation
Vorlesung/Konferenz
Richtung

Metadaten

Formale Metadaten

Titel Anwendungen von Totaler Unimodularität: Hermitesche Normalform
Alternativer Titel Anwendungen von Totaler Unimodularitaet: Hermitesche Normalform
Serientitel Diskrete Optimierung (Optimierung II)
Teil 07
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/31771
Herausgeber Technische Universität Darmstadt
Erscheinungsjahr 2009
Sprache Deutsch

Inhaltliche Metadaten

Fachgebiet Mathematik

Ähnliche Filme

Loading...