双対問題
線型計画問題は、目的関数と制約条件が全て線型性を有する最適化問題である。
主問題では、目的関数は n 個の変数を線型に組み合わせたものである。m 個の制約条件があり、それぞれが n 個の変数の線型な組合せの上限を定めている。問題は、制約条件を満たしつつ、目的関数の値を最小化する変数の値の組合せを求めることである。解は n 個の値のベクトル(リスト)であり、それらの値を目的関数に入力することで最小値が得られる。
双対問題では、目的関数は m 個の値の線型な組合せであり、これらは主問題の m 個の制約条件(上限値)それぞれに対応している。n 個の双対制約条件(dual constraints)があり、それぞれが m 個の双対変数(dual variables)の線型な組合せの下限を定めている。この場合、目的関数の値を最大化する双対変数の値の組合せを求める。