Dans l'optimisation, pour le problème d'origine (problème principal), [Double problème](https://ja.wikipedia.org/wiki/%E5%8F%8C%E5%AF%BE%E5%95%8F Vous pouvez penser à% E9% A1% 8C).
Le double problème a les propriétés importantes suivantes:
--Si l'un ou l'autre a la solution optimale, les deux ont la solution optimale et les valeurs optimales correspondent. «Le double problème du double problème est le problème principal.
Voici quelques exemples de problèmes principaux et doubles.
| Problème principal | Double problème | |
| $ \min{~ c^T x} $ | $ \max{~ b^T y} $ | |
| $ A x \ge b $ | $ A^T y \le c $ | |
| $ x \ge 0 $ | $ y \ge 0 $ |
J'ai créé un package Python3 (dual) qui vous permet de comprendre le double problème de divers problèmes principaux, je vais donc les présenter.
bash
pip install dual
Regardons un exemple.
bash
python -m dual << EOF
min c^T x
A x >= b
x >= 0
EOF
>>>
max b^T y
A^T y <= c
y >= 0
C'est juste.
Face à un double problème, cela devient le problème principal.
bash
python -m dual << EOF
max b^T y
A^T y <= c
y >= 0
EOF
>>>
min c^T x
A x >= b
x >= 0
Si vous modifiez l'inégalité de la condition de contrainte en une égalité, y devient une variable libre.
bash
python -m dual << EOF
min c^T x
A x = b
x >= 0
EOF
>>>
max b^T y
A^T y <= c
Si x est une variable libre, les contraintes du problème dual sont égales.
bash
python -m dual << EOF
min c^T x
A x >= b
EOF
>>>
max b^T y
A^T y = c
y >= 0
Rendons les choses un peu compliquées.
bash
python -m dual << EOF
min c^T x + d^T z
A x - P z >= b
Q z <= f
x >= 0
EOF
>>>
max b^T y - f^T w
A^T y <= c
- P^T y - Q^T w = d
y >= 0
w >= 0
Si vous donnez un double problème de la même manière, il reviendra au problème principal.
bash
python -m dual << EOF
max b^T y - f^T w
A^T y <= c
- P^T y - Q^T w = d
y >= 0
w >= 0
EOF
>>>
min c^T x + d^T z
-Q z >= -f
A x - P z >= b
x >= 0
Vous pouvez facilement le faire avec Jupyter [^ 1]. Importez comme préparation.
jupyter_notebook
import dual
Je vais essayer.
jupyter_notebook
%%dual
min c^T x
A x >= b
x >= 0
>>>
max b^T y
A^T y <= c
y >= 0
c'est tout
[^ 1]: J'utilise la technique de l'astuce de Jupyter 2.
Recommended Posts