[PYTHON] Méthode de programmation linéaire par méthode de marqueur de voiture

Problème de planification linéaire

Un problème de planification linéaire est un problème dans lequel la fonction objectif et les conditions de contrainte sont exprimées sous une forme linéaire, et le vecteur $ {\ bf x} $ est minimisé comme indiqué ci-dessous.

\min {\bf c}^T{\bf x}
\\subject \ \ {\bf A}{\bf x}\le {\bf b}

Ici, si la dimension de $ {\ bf x} $ est $ n $ et le nombre de contraintes est $ m $, alors $ {\ bf x}, {\ bf c}, {\ bf b} $ sont des vecteurs de dimension $ n $. , $ {\ bf A} $ est une matrice de $ m \ fois n $.

Méthode de marqueur de voiture

[Méthode unique] comme solution au problème de programmation linéaire (http://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%B3%E3%83%97%E3%83%AC%E3% 83% 83% E3% 82% AF% E3% 82% B9% E6% B3% 95) existe depuis longtemps, mais elle est inefficace pour les problèmes à grande échelle, et la méthode du point interne introduite ici est C'est utilisé. La méthode du marqueur de voiture est assez célèbre pour la méthode du point interne en programmation linéaire. Cet algorithme est souvent mentionné dans les brevets du monde logiciel, et on dit que c'est un bel algorithme qui peut être écrit très simplement en code. Ce qui suit est une fonction de la méthode de marqueur de voiture écrite en python.

#!/usr/bin/python
#coding:utf-8
import numpy as np

def karmarkar_method(x, c, amat, b,
                     gamma=1.0, eps=1.0e-3, nloop=30):
    """
Résolution des problèmes de programmation linéaire avec la méthode Karmarkar
    object  min z = c^T * x
    subject Ax <= b
    """
    for n in range(nloop):
        vk = b - amat * x
        gmat = amat.T * np.diag(1.0 / np.square(vk.A1)) * amat
        d = np.linalg.pinv(gmat) * c
        if np.linalg.norm(d) < eps:
            break
        hv = -amat * d
        if np.max(hv) <= 0:
            print "Unbounded!"
            x = None
            break
        alpha = gamma * np.min(vk[hv > 0] / hv[hv > 0])
        x -= alpha * d
        yield x
    #return x


if __name__ == "__main__":
    c = np.matrix([[-1.0],
                   [-1.0]])
    amat = np.matrix([[1.0, 1.0],
                      [1.0, -1.0]])
    b = np.matrix([[0.5],
                   [1.0]])
    #dessin
    from pylab import *
    ax = subplot(111, aspect='equal')
    x = np.arange(-3.0, 3.01, 0.15)
    y = np.arange(-3.0, 3.01, 0.15)
    X,Y = meshgrid(x, y)
    t = np.arange(-3.0, 3.01, 0.15)
    func = lambda x, y : c[0, 0] * x + c[1, 0] * y
    const = [lambda x : -amat[0, 0] / amat[0, 1] * x + b[0, 0] / amat[0, 1],
             lambda x : -amat[1, 0] / amat[1, 1] * x + b[1, 0] / amat[1, 1]]
    Z = func(X, Y)
    s = [const[i](t)foriinrange(2)]
    pcolor(X, Y, Z)
    for i in range(2):
        ax.plot(t, s[i], 'k')
    for x in karmarkar_method(np.matrix([[-2.0], [-2.0]]), c, amat, b, gamma=0.5, eps=1.0e-3, nloop=30):
        print x
        ax.plot([x[0,0]], [x[1,0]],'ro')
        axis([-3, 3, -3, 3])
    show()

Cette fois, non seulement la valeur minimale mais aussi la progression sont renvoyées pour le dessin. La figure ci-dessous montre comment la valeur s'approche de la valeur minimale.

Vous pouvez voir que la zone bleue montre la zone où la fonction objectif devient plus petite, et le point rouge pointe dans la direction bleue et s'arrête avant la ligne de contrainte. Actuellement, la méthode du point interne est également utilisée pour les problèmes de planification quadratique et les problèmes de planification non linéaire, mais la méthode de marqueur de voiture est un algorithme qui peut être considéré comme un précurseur de cela.