カーマーカー法による線形計画法 - Qiita

ここで${\bf x}$の次元を$n$、制約数を$m$とすると、${\bf x},{\bf c}, {\bf b}$は$n$次元ベクトル、${\bf A}$は$m \times n$の行列です。 カーマーカー法 線形計画問題の解法として単体法というものが古くからあるのですが、大規模な問題では効率が悪く、そちらでは今回紹介する内点法が用いられています。 線形計画における内点法では、カーマーカー法というアルゴリズムがかなり有名です。このアルゴリズムはソフトウェア界の特許の話でもよく出てくる話で、コードにしてもとてもシンプルに書けて、美しいアルゴリズムだと言われています。 以下がpythonで記述したカーマーカー法の関数です。 # !/usr/bin/python # coding:utf-8 import numpy as np def karmarkar_method(x, c, amat,