Simplex 단일 형 알고리즘 python 구현
11229 단어 알고리즘
알고리즘 은 선형 계획 문 제 를 포함 하 는 표준 형식의 설명 을 주어진 다음 에 이 선형 계획 문 제 를 풀 수 있다.예 를 들 어 어떤 pro. txt 파일 의 내용 은 다음 과 같다.
6 3 3 -1 1 -2 0 0 2 1 0 1 1 0 -1 3 0 -3 0 1 -3 4 12 -7 7 -2 -1 -6 0
알고리즘 을 실행 한 후 결과 얻 기:
x_1 = 0.000000,x_2 = 0.000000,x_3 = 0.000000,x_4 = 1.500000,x_5 = 2.500000,x_6 = 16.500000 objective value is : -16.500000 1-th line constraint value is : -3.000000 2-th line constraint value is : 4.000000 3-th line constraint value is : 12.000000
코드 는 다음 과 같 습 니 다:
#encoding=utf-8
__author__ = 'ysg'
import numpy as np #python lib
class Simplex():
def __init__(self):
self._A = "" #
self._b = "" #
self._c = '' #
self._B = '' #
self.row = 0 #
def solve(self, filename):
# ,
#
# b
# c
# ( )
A = []
b = []
c = []
with open(filename,'r') as f:
self.var = int(f.readline())
self.row = int(f.readline())
for i in range(self.row):
x =map(int, f.readline().strip().split(' '))
A.append(x)
b=(map(int, list(f.readline().split(' '))))
c=(map(int, list(f.readline().split(' '))))
self._A = np.array(A, dtype=float)
self._b = np.array(b, dtype=float)
self._c = np.array(c, dtype=float)
# self._A = np.array([[3,-1,1,-2,0,0],[2,1,0,1,1,0],[-1,3,0,-3,0,1]],dtype=float)
# self._b = np.array([-3,4,12],dtype=float)
# self._c = np.array([-7, 7, -2, -1, -6, 0],dtype=float)
self._B = list()
self.row = len(self._b)
self.var = len(self._c)
(x,obj) = self.Simplex(self._A,self._b,self._c)
self.pprint(x,obj,A)
def pprint(self,x,obj,A):
px = ['x_%d = %f'%(i+1,x[i]) for i in range(len(x))]
print ','.join(px)
print ('objective value is : %f'% obj)
print '------------------------------'
for i in range(len(A)):
print '%d-th line constraint value is : %f' % (i+1, x.dot(A[i]))
#
def InitializeSimplex(self,A,b):
b_min, min_pos = (np.min(b), np.argmin(b)) # bi
# bi
if (b_min < 0):
for i in range(self.row):
if i != min_pos:
A[i] = A[i] - A[min_pos]
b[i] = b[i] - b[min_pos]
A[min_pos] = A[min_pos]*-1
b[min_pos] = b[min_pos]*-1
#
slacks = np.eye(self.row)
A = np.concatenate((A,slacks),axis=1)
c = np.concatenate((np.zeros(self.var),np.ones(self.row)),axis=1)
# , b
new_B = [i + self.var for i in range(self.row)]
#
obj = np.sum(b)
c = c[new_B].reshape(1,-1).dot(A) - c
c = c[0]
#entering basis
e= np.argmax(c)
while c[e] > 0:
theta = []
for i in range(len(b)):
if A[i][e] > 0:
theta.append(b[i]/A[i][e])
else:
theta.append(float("inf"))
l = np.argmin(np.array(theta))
if theta[l] == float('inf'):
print 'unbounded'
return False
(new_B, A, b, c, obj) = self._PIVOT(new_B, A, b, c, obj, l , e)
e = np.argmax(c)
# ,
for mb in new_B:
if mb >= self.var:
row = mb-self.var
i = 0
while A[row][i] == 0 and i < self.var:
i+=1
(new_B, A, b, c, obj) = self._PIVOT(new_B,A,b,c,obj,new_B.index(mb),i)
return (new_B, A[:,0:self.var], b)
#
def Simplex(self,A,b,c):
B = ''
(B, A ,b) = self.InitializeSimplex(A,b)
#
obj = np.dot(c[B],b)
c = np.dot(c[B].reshape(1,-1), A) - c
c = c[0]
# entering basis
e = np.argmax(c)
# , 0,
while c[e] > 0:
theta = []
for i in range(len(b)):
if A[i][e] > 0:
theta.append(b[i] / A[i][e])
else:
theta.append(float("inf"))
l = np.argmin(np.array(theta))
if theta[l] == float('inf'):
print 'unbounded'
return False
(B, A, b, c, obj) = self._PIVOT(B, A, b, c, obj, l, e)
e = np.argmax(c)
x = self._CalculateX(B,A,b,c)
return (x,obj)
#
def _CalculateX(self,B,A,b,c):
x = np.zeros(self.var,dtype=float)
x[B] = b
return x
#
def _PIVOT(self,B,A,b,c,z,l,e):
# main element is a_le
# l represents leaving basis
# e represents entering basis
main_elem = A[l][e]
#scaling the l-th line
A[l] = A[l]/main_elem
b[l] = b[l]/main_elem
#change e-th column to unit array
for i in range(self.row):
if i != l:
b[i] = b[i] - A[i][e] * b[l]
A[i] = A[i] - A[i][e] * A[l]
#update objective value
z -= b[l]*c[e]
c = c - c[e] * A[l]
# change the basis
B[l] = e
return (B, A, b, c, z)
s = Simplex()
s.solve('pro.txt')
주석 차이 가 많 지 않 고 비교적 명확 하 게 쓰 여 있어 위의 이론 지식 링크 를 참고 할 수 있다.
아저씨, 돌아 가세 요.
잘못 이 있 으 면 지적 을 환영 합 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.