[AI] Optimization (4-2)

 

선형 프로그래밍(linear programming)

 

 선형 프로그래밍은 선형 방정식(y = ax₁ + bx2 + … 형식의 방정식)을 최적화하는 문제 계열이다.

 

 선형 프로그래밍에는 다음 구성 요소가 있다.

• 최소화하려는 비용 함수: c₁x₁ + c2x2 + … + cₙxₙ. 여기서 각 xₙ는 변수이며 일부 비용 cₙ과 연관되어 있다.
• 값보다 작거나 같거나(a₁x₁ + a2x2 + … + aₙxₙ ≤ b) 이 값과 정확하게 동일한(a₁x₁ + a2x2 + … + aₙxₙ = b) 변수의 합으로 표시되는 제약 조건이다. 이 경우 xₙ는 변수이고 aₙ는 이와 관련된 일부 리소스이며 b는 이 문제에 전념할 수 있는 리소스의 양이다.
• 변수(예: 변수는 음수일 수 없음)에 대한 개별 범위의 경계는 lᵢ ≤ xᵢ ≤ uᵢ 형식이이다.

다음 예시를 봐보자.

• 두 대의 기계, X₁ 및  X₂가 있다. X₁의 실행 비용은 시간당 50달러이고,  X₂ 의 실행 비용은 시간당 80달러다. 목표는 비용을 최소화하는 것이다. 이는 비용 함수(50x₁ + 80x₂)로 공식화될 수 있다.
• X₁에는 시간당 5 단위의 노동이 필요하고, X₂ 에는 시간당 2단위의 노동이 필요하다. 지출할 노동력은 총 20 단위이다. 이는 제약 조건(5x₁ + 2x₂ ≤ 20)으로 공식화될 수 있다.
• X₁는 시간당 10단위의 생산량을 생산하고,  X₂는 시간당 12단위의 출력을 생산한다. 회사는 90 단위의 생산량이 필요하다. 이것은 또 다른 제약이다. 말 그대로 10x₁ + 12x₂ ≥ 90으로 다시 쓸 수 있다. 그러나 제약 조건은 (a₁x₁ + a₂x₂ + … + aₙxₙ ≤ b) 또는 (a₁x₁ + a₂x₂ + … + aₙxₙ = b) 형식이어야 한다. 따라서 원하는 형식의 등가 방정식을 얻기 위해 (-1)을 곱한다: 제약 조건(-10x₁) + (-12a₂x₂) ≤ -90.

선형 프로그래밍을 위한 최적화 알고리즘에는 우리가 가정하고 싶지 않은 기하학 및 선형 대수학에 대한 배경 지식이 필요하다(수학은 패스~). 대신 Simplex 및 Interior-Point와 같이 이미 존재하는 알고리즘을 사용할 수 있다.

 

다음은 Python에서 scipy 라이브러리를 사용하는 선형 프로그래밍 예제이다.

import scipy.optimize

# Objective Function: 50x_1 + 80x_2
# Constraint 1: 5x_1 + 2x_2 <= 20
# Constraint 2: -10x_1 + -12x_2 <= -90

result = scipy.optimize.linprog(
    [50, 80],  # Cost function: 50x_1 + 80x_2
    A_ub=[[5, 2], [-10, -12]],  # Coefficients for inequalities
    b_ub=[20, -90],  # Constraints for inequalities: 20 and -90
)

if result.success:
    print(f"X1: {round(result.x[0], 2)} hours")
    print(f"X2: {round(result.x[1], 2)} hours")
else:
    print("No solution")

 

지금까지 최적화에서 선형 프로그래밍 파트를 알아봤다. 다음은 최적화 마지막 파트인 제약 충족 문제를 알아보자.