In dieser Woche befassen wir uns mit der Theorie und den Anwendungen der Dualität der linearen Programmierung. Wir stellen die Eigenschaften von primären-dualen Paaren vor, darunter schwache Dualität, starke Dualität, komplementäre Lockerheit und wie man eine duale optimale Lösung konstruiert, wenn man eine primäre optimale Lösung hat. Wir stellen auch eine wichtige Anwendung der Dualität der linearen Programmierung vor: Die Verwendung von Schattenpreisen zur Bestimmung der kritischsten Einschränkung in einem linearen Programm.

In den vergangenen zwei Wochen haben wir uns mit der Simplex-Methode und der Dualität beschäftigt. Darüber hinaus wird in dieser Vorlesung die duale Simplex-Methode besprochen. Wir wenden sie auf ein wichtiges Problem der Sensitivitätsanalyse an: die Bewertung eines linearen Programmierungsmodells mit einer neuen Einschränkung. Ein lineares Programmierungsmodell mit einer neuen Variable wird ebenfalls besprochen.

In dieser Vorlesung stellen wir Netzwerkflussmodelle vor, die häufig für Entscheidungen in den Bereichen Transport, Logistik, Lagerhaltung, Projektmanagement usw. verwendet werden. Zunächst stellen wir das Minimum Cost Network Flow (MCNF)-Modell vor und zeigen, dass es die Verallgemeinerung vieler bekannter Modelle ist, darunter Zuweisung, Transport, Umschlag, maximaler Fluss und kürzester Weg. Wir beweisen auch eine ganz besondere Eigenschaft von MCNF, die totale Unimodularität, und zeigen, wie sie lineare Programmierung und ganzzahlige Programmierung miteinander verbindet.

In der letzten Lektion dieses Kurses stellen wir einen Fall von NEC Taiwan vor, einem Anbieter von IT- und Netzwerklösungen einschließlich Cloud Computing, KI, IoT usw. Da der Unterhalt all seiner Service-Hubs zu kostspielig ist, plant das Unternehmen, die Standorte der Hubs neu zu ordnen und die Anzahl der Mitarbeiter in jedem Hub neu zu verteilen. Es wird ein Algorithmus zur Lösung des Standortproblems von NEC Taiwan vorgestellt.

In dieser Woche untersuchen wir nichtlineare Programme mit Nebenbedingungen. Wir stellen zwei wichtige Werkzeuge vor, die Lagrangesche Relaxation und die KKT-Bedingung, um nichtlineare Programme mit Nebenbedingungen zu lösen. Wir sehen auch, dass die Dualität der linearen Programmierung ein Spezialfall der Lagrangeschen Dualität ist.

In dieser Woche stellen wir zwei bekannte Modelle vor, die durch Anwendung der mathematischen Eigenschaften, die wir eingeführt haben, konstruiert wurden. Zunächst formulieren wir ein einfaches lineares Regressionsproblem als nichtlineares Programm und leiten die geschlossene Regressionsformel ab. Zweitens stellen wir die Support-Vektor-Maschine, eines der bekanntesten Klassifizierungsmodelle, aus der Perspektive der Dualität vor.

In der letzten Woche lassen wir die vorgestellten Themen Revue passieren und machen einige abschließende Bemerkungen. Außerdem geben wir einige Lernhinweise für weiterführende Studien.