Dans cette semaine, nous étudions la théorie et les applications de la dualité de la programmation linéaire. Nous introduisons les propriétés que possèdent les paires primal-dual, y compris la dualité faible, la dualité forte, le relâchement complémentaire, et la façon de construire une solution optimale duale à partir d'une solution optimale primale. Nous présentons également une application importante de la dualité de la programmation linéaire : L'utilisation des prix fictifs pour déterminer la contrainte la plus critique dans un programme linéaire.

Au cours des deux dernières semaines, nous avons étudié la méthode du simplexe et la dualité. En plus de ces deux méthodes, la méthode du double simplexe est abordée dans ce cours. Nous l'appliquons à une question importante de l'analyse de sensibilité : l'évaluation d'un modèle de programmation linéaire avec une nouvelle contrainte. Un modèle de programmation linéaire avec une nouvelle variable est également abordé.

Dans cet exposé, nous présentons les modèles de flux de réseau, qui sont largement utilisés pour prendre des décisions en matière de transport, de logistique, d'inventaire, de gestion de projet, etc. Nous introduisons tout d'abord le modèle de flux de réseau à coût minimum (MCNF) et montrons qu'il s'agit d'une généralisation de nombreux modèles célèbres, notamment l'affectation, le transport, le transbordement, le flux maximum et le chemin le plus court. Nous prouvons également une propriété très spéciale du MCNF, l'unimodularité totale, et nous expliquons comment elle relie la programmation linéaire et la programmation en nombres entiers.

Pour la dernière leçon de ce cours, nous vous présentons le cas de NEC Taïwan, qui fournit des solutions informatiques et de réseau, notamment pour le cloud computing, l'IA, l'IoT, etc. Comme l'entretien de tous ses hubs de service est trop coûteux, ils prévoient de réorganiser les emplacements des hubs et de réaffecter le nombre d'employés dans chaque hub. Un algorithme est inclus pour résoudre le problème de localisation des installations auquel est confronté NEC Taïwan.

Dans cette semaine, nous étudions les programmes non linéaires avec contraintes. Nous introduisons deux outils majeurs, la relaxation lagrangienne et la condition de KKT, pour résoudre les programmes non linéaires avec contraintes. Nous verrons également comment la dualité de programmation linéaire est un cas particulier de la dualité lagrangienne.

Cette semaine, nous présentons deux modèles bien connus construits en appliquant les propriétés mathématiques que nous avons introduites. Tout d'abord, nous formulons un problème de régression linéaire simple sous la forme d'un programme non linéaire et nous dérivons la formule de régression de forme fermée. Ensuite, nous présentons la machine support-vecteur, l'un des modèles de classification les plus célèbres, du point de vue de la dualité.

Au cours de la dernière semaine, nous passons en revue les sujets que nous avons introduits et nous formulons quelques remarques finales. Nous proposons également quelques pistes d'apprentissage pour les études avancées.