Python에서 Google ortools를 사용한 선형 정수 프로그래밍

Python의 Google ortools 모듈에 대한 다른 여러 게시물에서 이미 아래 설명 된 선형 최적화 문제를 해결했습니다. 모든 최적화 변수가 연속 솔루션 공간에서 나오기 때문에 문제는 연속 문제입니다.

비슷한 문제를 생각할 수 있지만 정수 최적화 변수가 있습니다. 이는 문제를 정수 최적화 문제로 만들 것입니다 (이산 솔루션 공간 사용). 문제를 다시 설명하고 모든 최적화 변수가 정수임을 나타내는 수학적 진술을 추가했습니다.

Python의 ortools를 사용하여이 문제를 해결하는 워크 플로는 이전 게시물에서 소개 한 워크 플로와 매우 유사합니다.

ortools.linear_solver에서 pywraplp를 가져 오는 것으로 시작합니다.

from ortools.linear_solver import pywraplp

다음으로 솔버 인스턴스를 만들고 참조 핸들러에 대한 참조를 저장합니다. 이번에는 GLOP 대신 CBC 솔버를 사용합니다.

solver = pywraplp.Solver.CreateSolver('linear_programming_examples', 'CBC')

이제 관련 최적화 변수를 선언해야합니다. 이 예에서 최적화 변수는 x, y 및 z이며이를 선언 할 때 물질적 문제 설명에 따라 하한과 상한을 정의합니다. 또한 NumVar () 생성자 대신 IntVar () 생성자를 사용하여 최적화 변수를 정수로 선언합니다.

# 하한이 0이고 상한이없는 변수 x 선언-정수 (IntVar)
x = solver.IntVar(0, solver.infinity(), "x")
# 하한이 0이고 상한이없는 변수 y를 선언합니다. 정수입니다 (IntVar).
y = solver.IntVar(0, solver.infinity(), "y")
# 하한이 0이고 상한이없는 변수 z를 선언합니다. 정수입니다 (IntVar).
z = solver.IntVar(0, solver.infinity(), "z")

이제 워크 플로는 연속 문제가 포함 된 가장 최근 게시물과 동일합니다. 솔버에 목적 함수와 제약 조건을 추가하여 문제를 모델링합니다.

# 최대화 문제로 선언하고 목적 함수 정의
solver.Maximize(x+2*y+3*z)
# 제약 추가
solver.Add(2*x+y+z <= 20)
solver.Add(x+y+z <= 15)
solver.Add(x-y-z >= 0)
<ortools.linear_solver.pywraplp.Constraint; proxy of <Swig Object of type 'operations_research::MPConstraint *' at 0x000001D4F116CFC0> >

모델을 완성한 후 이제 문제를 해결할 수 있습니다.

solver.Solve()
0

x에 대한 최적의 솔루션은 다음과 같습니다.

print("x_opt: ", x.solution_value())
x_opt:  7.0

y에 대한 최적의 솔루션은 다음과 같습니다.

print("y_opt: ", y.solution_value())
y_opt:  0.0

z에 대한 최적의 솔루션은 다음과 같습니다.

print("z_opt: ", z.solution_value())
z_opt:  6.0

최적의 목적 함수 값은 다음과 같습니다.

print("optimal value: " + str(x.solution_value()+2*y.solution_value()+3*z.solution_value()))
optimal value: 25.0

보시다시피 최적의 값은 정수입니다. 또한 이산 솔루션 공간에있는 변수의 추가 제약이 목적을 최대화 할 수있는 가능성의 범위를 제한하기 때문에 최적의 목적 함수 값이 감소한 것을 볼 수 있습니다. 연속적인 경우 최적의 결과는 26.66이었습니다. 이제 최적의 결과는 25.0입니다.

Leave a Reply

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 항목은 *(으)로 표시합니다

이 사이트는 스팸을 줄이는 아키스밋을 사용합니다. 댓글이 어떻게 처리되는지 알아보십시오.

Close

메타