[PYTHON] Lineare Programmiermethode nach Automarkierungsmethode

Lineares Planungsproblem

Ein lineares Planungsproblem ist ein Problem, bei dem sowohl die Zielfunktion als auch die Randbedingungen in einer linearen Form ausgedrückt werden und der Vektor $ {\ bf x} $ wie unten gezeigt minimiert wird.

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

Wenn die Dimension von $ {\ bf x} $ $ n $ ist und die Anzahl der Einschränkungen $ m $ ist, dann sind $ {\ bf x}, {\ bf c}, {\ bf b} $ $ n $ Dimensionsvektoren , $ {\ bf A} $ ist eine Matrix von $ m \ times n $.

Automarkierungsmethode

[Einzelmethode](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) gibt es schon lange, aber es ist ineffizient für große Probleme, und die hier eingeführte interne Punktmethode ist Es ist benutzt. Die Automarkierungsmethode ist bekannt für die interne Punktmethode in der linearen Planung. Dieser Algorithmus wird oft in den Patenten der Software-Welt erwähnt, und es wird gesagt, dass es ein schöner Algorithmus ist, der sehr einfach in Code geschrieben werden kann. Das Folgende ist eine Funktion der in Python geschriebenen Automarkierungsmethode.

#!/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):
    """
Lösen linearer Programmierprobleme mit der Karmarkar-Methode
    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]])
    #Zeichnung
    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()

Dieses Mal wird nicht nur der Mindestwert, sondern auch der Fortschritt zum Zeichnen zurückgegeben. Die folgende Abbildung zeigt, wie sich der Wert dem Mindestwert nähert.

Sie können sehen, dass der blaue Bereich den Bereich anzeigt, in dem die Zielfunktion kleiner wird, und der rote Punkt in die blaue Richtung zeigt und vor der Begrenzungslinie stoppt. Gegenwärtig wird die interne Punktmethode auch für sekundäre Planungsprobleme und nichtlineare Planungsprobleme verwendet, aber die Automarkierungsmethode ist ein Algorithmus, der als Vorläufer dafür bezeichnet werden kann.