Файл:Karmarkar.svg

#!/usr/bin/env python # -*- кодировка: utf-8 -*- # # Скрипт на Python для иллюстрации сходимости алгоритма Кармаркара для # задачи линейного программирования. # # http://en.wikipedia.org/wiki/Karmarkar%27s_algorithm # # Алгоритм Кармаркара — это алгоритм, представленный Нарендрой Кармаркаром в 1984 году # для решения задач линейного программирования. Это был первый достаточно эффективный # алгоритм, решающий эти задачи за полиномиальное время. # # Алгоритм Кармаркара относится к классу методов внутренних точек: # текущее предположение для решения не следует границе допустимого # множества, как в симплекс-методе, а перемещается по внутренней части допустимой # области, улучшая приближение оптимального решения на определенную # долю с каждой итерацией и сходясь к оптимальному решению с # рациональными данными. # # Гийом Жакно # 2015-05-03 # CC-BY-SAимпортировать  numpy  как  np импортировать  matplotlib из  matplotlib.pyplot  импортировать  figure ,  show ,  rc ,  gridclass  ProblemInstance ( ) :  def  __init __ ( self ) :  n  =  2  m  =  11  self.A = np.zeros ( ( m , n ) ) self.B = np.zeros ( ( m , 1 ) ) self.C = np.array ( [ [ 1 ] , [ 1 ] ] ) self.A [ : , 1 ] = 1 для i в диапазоне ( 11 ) : p = 0,1 * i self.A [ i , 0 ] = 2,0 * p self.B [ i , 0 ] = p * p + 1,0​                          класс  KarmarkarAlgorithm ( ) :  def  __init __ ( self , A , B , C )  : self.maxIterations = 100 self.A = np.copy ( A ) self.B = np.copy ( B ) self.C = np.copy ( C ) self.n = len ( C ) self.m = len ( B ) self.AT = A.transpose ( ) self.XT = None​​​​​​​​​​​​​​​​​​​                        def  isConvergeCriteronSatisfied ( self ,  epsilon  =  1e-8 ):  если  np . size ( self . XT , 1 ) < 2 :  вернуть  False  если  np . linalg . norm ( self . XT [:, - 1 ] - self . XT [:, - 2 ], 2 )  <  epsilon :  вернуть  True def  resolve ( self ,  X0 = None ) :  # Проверка не выполняется  для неограниченной задачи , если  X0  равно  None :  X0  =  np.zeros ( ( self.n , 1 ) ) k = 0 X = np.copy ( X0 ) self.XT = np.copy ( X0 ) gamma = 0.5 for _ in range ( self.maxIterations ) : if self.isConvergeCriteronSatisfied ( ) : break V = self.B - np.dot ( self.A , X ) VM2 = np.linalg.matrix_power ( np.diagflat ( V ) , - 2 ) hx = np .​​​​​​​​​​​​ dot ( np.linalg.matrix_power ( np.dot ( np.dot ( self.AT , VM2 ) , self.A ) , - 1 ) , self.C ) hv = - np.dot ( self.A , hx ) coeff = np.infty для p в диапазоне ( self.m ) : если hv [ p , 0 ] < 0 : coeff = np.min ( ( coeff , -V [ p , 0 ] / hv [ p , 0​​​​​​​​​​​​​​​​​​​​                                           ]))  альфа  =  гамма  *  коэфф  X  +=  альфа * hx  self . XT  =  np . конкатенация (( self . XT , X ), ось = 1 ) def  makePlot ( self , outputFilename  =  r 'Karmarkar.svg' ,  xs =- 0.05 ,  xe =+ 1.05 ):  rc ( 'grid' ,  linewidth  =  1 ,  linestyle  =  '-' ,  color  =  '#a0a0a0' )  rc ( 'xtick' ,  labelsize  =  15 )  rc ( 'ytick' ,  labelsize  =  15 )  rc ( 'font' , ** { 'family' : 'serif' , 'serif' :[ 'Palatino' ], 'size' : 15 })  rc ( 'text' ,  usetex = True ) fig  =  figure (  ) ax  =  fig.add_axes ( [ 0.12 , 0.12 , 0.76 , 0.76 ] ) grid ( True ) ylimMin = - 0.05 ylimMax = + 1.05 xsOri = xs xeOri = xe для i в диапазоне ( np.size ( self.A , 0 ) ) : xs = xsOri xe = xeOri a = - self.A [ i , 0 ] /self.A [ i , 1 ] b = + self.B [ i , 0 ] / self .​​​​​​​​ A [ i , 1 ] ys = a * xs + b ye = a * xe + b if ys > ylimMax : ys = ylimMax xs = ( ylimMax - b ) / a if ye < ylimMin : ye = ylimMin xe = ( ylimMin - b ) / a ax . сюжет ([ xs , xe ], [ ys , ye ], \ lw = 1 , ls = '--' , цвет = 'b' ) ax . set_xlim (( xs , xe )) ax . сюжет ( self . XT [ 0 ,:], self . XT [ 1 ,:], \                                                                    lw  =  1 ,  ls  =  '-' ,  цвет  =  'r' , маркер  =  '  .' ) ax.plot  ( self.XT [ 0 , -1 ] , self.XT [ 1 , -1 ] , \ lw = 1 , ls = '-' , цвет = ' r' , маркер = ' o' ) ax.set_xlim ( ( ylimMin , ylimMax ) ) ax.set_ylim ( ( ylimMin , ylimMax )) ax.set_aspect ( ' равно ' ) ax.set_xlabel ( ' $ x_1 $ ' , поворот = 0 ) ax.set_ylabel ( ' $ x_2 $ ' , поворот = 0 ) ax . set_title ( r '$\max x_1+x_2\textrm{ st }2px_1+x_2\le p^2+1\textrm{, }\forall p \in [0.0,0.1,...,1.0]$' , размер шрифта = 15 ) рис . savefig ( имя_выводимого_файла ) рис . show ()                         если  __name__  ==  " __main__ " :  p  =  ProblemInstance ( )  k  =  KarmarkarAlgorithm ( p.A , p.B , p.C ) k.solve ( X0 = np.zeros ( ( 2,1 ) ) ) k.makePlot ( outputFilename = r ' Karmarkar.svg ' , xs = - 0.05 , xe = + 1.05 )​​​​