EnglishCommencer

Le programme linéaire : forme standard et dualité

Le programme linéaire à plusieurs variables : mise sous forme standard avec des variables d'écart, programme dual et prix d'une ressource, variables entières et relaxation, et l'usage d'un solveur.

  • 29 cartes
  • 5 thèmes
  • Gratuit
Réviser ce deck

Le programme, thème par thème

Le poids de chaque thème suit celui que lui donne l'examen.

  1. Notions
  2. Questions
  3. Ranger et relier
  4. Les chiffres
  5. Mises en situation

Quelques cartes du deck

  • Forme standard d'un programme linéaire : de quoi s'agit-il ?

    Voir la réponse

    Écriture où toutes les contraintes sont des égalités, de second membre positif ou nul, et où toutes les variables sont positives ou nulles.

    On y arrive en ajoutant une variable à chaque inégalité. Le simplexe part de cette écriture, car des égalités se traitent par des opérations sur les lignes d'un tableau.

  • Ce script cherche à maximiser le profit 30x + 20y sous 2x + y ≤ 100 et x + y ≤ 80. Il rend x = 0 et y = 0, soit un profit nul. Quelle est la cause ?

    ```python
    from scipy.optimize import linprog

    res = linprog(c=[30, 20], A_ub=[[2, 1], [1, 1]], b_ub=[100, 80])
    print(res.x, res.fun)
    # [0. 0.] 0.0
    `

    • linprog minimise : il faut passer c=[-30, -20] et lire le profit dans -res.fun
    • Il manque bounds=(0, None), sans quoi les variables sont forcées à 0 et linprog renvoie le point nul
    • b_ub doit contenir des valeurs négatives, car linprog lit les contraintes sous la forme ≥
    • A_ub doit être transposée avant l'appel : linprog attend une variable par ligne
    Voir la réponse

    linprog minimise : il faut passer c=[-30, -20] et lire le profit dans -res.fun

    linprog minimise toujours c @ x. Avec c = [30, 20] et x, y ≥ 0, le minimum est en (0, 0). Les bornes par défaut sont déjà (0, None). Avec c = [-30, -20], on obtient x = 20, y = 60 et res.fun = -1800.0 : le profit est 1 800.

  • Un programme linéaire optimise un objectif linéaire sous des contraintes … ; si la région admissible est bornée, l'optimum est atteint en un ….

    Voir la réponse

    Un programme linéaire optimise un objectif linéaire sous des contraintes linéaires ; si la région admissible est bornée, l'optimum est atteint en un sommet.

    Objectif et contraintes sont des combinaisons linéaires des variables, d'où une région en polyèdre dont l'objectif atteint son extremum en un coin.

  • Variable d'écart : de quoi s'agit-il ?

    Voir la réponse

    Variable positive ou nulle ajoutée au premier membre d'une contrainte ≤ pour la changer en égalité ; elle mesure la quantité de ressource inutilisée.

    2x + y ≤ 100 devient 2x + y + e1 = 100. Avec x = 10 et y = 20, e1 = 60 : il reste 60 unités. Avec x = 20 et y = 60, e1 = 0 : la ressource est saturée.

Réviser ce deck