Pythonでラグランジュ緩和法によるスケジューリング問題を解く

こちらがクラス

class Lagrangian_relaxation():
    def __init__(self, a):
        #適当にパラメーターを初期化、aはラグランジュ乗数の更新幅
        self.a = a
        self.x1=0
        self.x2=0
        self.h1=0
        self.h2=0
        self.f=10000000
        self.df=0
        self.F = 0
        self.z1 = 0
        self.z2 = 0
    
    def set_func(self, funcf, funch, funcx):#与えられた条件を関数として設定
        self.funcf = funcf
        self.funch = funch
        self.funcx = funcx
        
    def funcF(self):#最小化する関数の値を計算f　前回との変化量も計算df
        p_f = self.f
        self.f =  self.funcf(self.x1, self.x2)
        self.df = self.f - p_f
        return self.f, self.df
    
    def update_h(self):#制約条件式H(x)>=0の値を計算
        self.h1, self.h2 = self.funch(self.x1, self.x2)
        return self.h1, self.h2
        
    def update_Z(self):#次に使うラグランジュ乗数を決定
        self.z1 = max(self.z1 + self.a*self.h1,0)
        self.z2 = max(self.z2 + self.a*self.h2,0)
        return self.z1, self.z2
        
    def update_x(self):#この時のx1,x2を計算
        self.x1, self.x2 =  self.funcx(self.z1, self.z2)
        return self.x1, self.x2
    
    def running(self,t,th):#tは最大繰り返し関数、thは繰り返しを終了するdfの値
        for i in range(t):
            X1, X2 = self.update_x()
            H1, H2 = self.update_h()
            Z1, Z2 = self.update_Z()
            result,df =  self.funcF()
            if(abs(df) <= th):
                break
            print("x1:", X1, "x2:", X2,"h1:", H1, "h2:", H2, "z1:", Z1, "z2:", Z2, "F:", result, "df:", df)

で、関数はこんな感じで定義（ここは適宜問題に合わせて変えてください）

def funcf(x1, x2):#最小化したい関数
    return ((x1 - 1)**2 + (x2 -1)**2 +1)

def funch(x1, x2):#x1とx2の子問題
    return -x1 + 0.5 * x2, x1 + x2 -1

def funcx(z1, z2):#与えられた制約を表す関数(H(x)>=0)
    return  0.5 * (z1 - z2) + 1, -0.5 * (0.5*z1 + z2) + 1

で、ラグランジェ乗数の更新幅と関数を与えてrunしてください。

lrm = Lagrangian_relaxation(0.5)#更新幅設定
lrm.set_func(funcf, funch, funcx)#関数は設定
lrm.running(20, 0.01)#ラン！　(最大繰り返し回数、繰り返しをやめるdfの値)

こんな感じでございます。素直にやってるので効率とか考えてないです。変数の数などが違う人は多少改修して使ってください。

結果はこちら。

x1: 1.0 x2: 1.0 h1: -0.5 h2: 1.0 z1: 0 z2: 0.5 F: 1.0 df: -9999999.0
x1: 0.75 x2: 0.75 h1: -0.375 h2: 0.5 z1: 0 z2: 0.75 F: 1.125 df: 0.125
x1: 0.625 x2: 0.625 h1: -0.3125 h2: 0.25 z1: 0 z2: 0.875 F: 1.28125 df: 0.15625
x1: 0.5625 x2: 0.5625 h1: -0.28125 h2: 0.125 z1: 0 z2: 0.9375 F: 1.3828125 df: 0.1015625
x1: 0.53125 x2: 0.53125 h1: -0.265625 h2: 0.0625 z1: 0 z2: 0.96875 F: 1.439453125 df: 0.056640625
x1: 0.515625 x2: 0.515625 h1: -0.2578125 h2: 0.03125 z1: 0 z2: 0.984375 F: 1.46923828125 df: 0.02978515625
x1: 0.5078125 x2: 0.5078125 h1: -0.25390625 h2: 0.015625 z1: 0 z2: 0.9921875 F: 1.4844970703125 df: 0.0152587890625

こんな感じ出てきます。

レポート課題の助けになれば何よりです。

もし、pythonの実行環境がなくて、このページで結果をだせるようにしてほしいという人はコメントに書いてください。

それでは。