弱双対定理
最大化
$ \sum^n_{j=1}c_jx_j
制約条件
$ \sum^n_{j=1}a_{ij}x_j \le b_i, \quad i = 1,\dots,m
非負条件
$ x_j \ge 0, \quad j = 1, \dots, n
$ Pと、$ Pの双対問題$ Dに対して、$ (x_1, \dots, x_n)と$ (y_1, \dots, y_m)がそれぞれの実行可能解ならば、以下の不等式が成り立つ $ \sum^n_{j=1} c_jx_j \le \sum^m_{i=1} b_iy_i .
https://scrapbox.io/files/6673bdbc603780001c617f8b.jpg