다기준 의사결정 > 목표계획법(Goal Programming)

여러개의 다른 목표를 동시에 고려해야하는 최적화 문제를 해결하기 위한 최적화 기법입니다. 일반적인 선형계획법이 하나의 목적함수를 최적화하는 대신에 목표계획법에서는 어려 목표들을 동시에 달성하거나, 목표 달성 수준의 편차를 최소화하는데 초점을 맞추는 방법론입니다.

목표계획법은 의사결정자로부터 각 기준에 대한 목표치를 제공받고 여러 기준들의 중요도 순서도 의사결정자로부터 제공받습니다. 그리고 이것들을 모두 반영하여 선형계획법으로 문제를 해결합니다.

일반적인 선형계획법과 가장 다른 부분이 목적함수에 대한 우선순위가 있다는 것입니다. 만약 목적 X와 목적 Y가 있다고 했을때 목적 X가 중요하다면 목적 X를 달성하는 최적해를 일차적으로 찾고 이를 반영하여 목적 Y를 달성하는 최적해를 찾습니다. 이와 같이 중요도에 따라 순차적으로 선형계획법을 해결하면서 목적에 가장 부합하는 최적해를 도출하게 됩니다.

방법을 다시 정리해보면 다음과 같습니다. 아래와 같은 방법을 사용하면 다중목표를 선형계획법으로 반영할 수 있습니다.

1. 목적함수 X를 가진 선형계획법 해결 
2. 목적함수 Y를 가진 선형계획법 해결(-> 1단계에서 얻은 최적해를 제약조건으로 활용)

예시문제를 통해 좀 더 상세히 봐보겠습니다.(Gemini 도움을 받아 예시문제 생성해보았습니다.)

목표수준을 봐보면 목표1에서는 d-를 최소화하는 것이 중요합니다. 왜냐하면 d-가 크다는 것은 x_a와 x_b를 통해 얻은 이익이 부족해서 d-로 채웠다는 것이기 때문에 d-를 최소화 해야만 생상한 제품으로 이익을 최대화 할 수 있습니다.(목표1에서 d+는 0) 목표2, 3도 같은 로직으로 이해할 수 있습니다.

예를들어 목표3에서 d+가 커진다는 것은 x_b가 많아진다는 것이고 이것은 과다생산을 뜻해 목표에 부합하지 않습니다.

이제 위 문제를 코드를 활용해서 해결해보겠습니다.

먼저 의사결정변수는 아래와 같이 입력합니다.

from ortools.linear_solver import pywraplp



## define solver
solver = pywraplp.Solver.CreateSolver('GLOP')

## define decision variable
x_A = solver.NumVar(0, solver.infinity(), 'x_A')
x_B = solver.NumVar(0, solver.infinity(), 'x_B')

d1_minus = solver.NumVar(0, solver.infinity(), 'd1_minus') # 이익 미달
d1_plus = solver.NumVar(0, solver.infinity(), 'd1_plus')   # 이익 초과

d2_minus = solver.NumVar(0, solver.infinity(), 'd2_minus') # 제품 A 미달
d2_plus = solver.NumVar(0, solver.infinity(), 'd2_plus')   # 제품 A 초과

d3_minus = solver.NumVar(0, solver.infinity(), 'd3_minus') # 제품 B 미달
d3_plus = solver.NumVar(0, solver.infinity(), 'd3_plus')   # 제품 B 초과

제약조건은 꼭 지켜야하는 제약조건과 목표제약조건으로 나뉩니다.

## define constraints
solver.Add(2 * x_A + 3 * x_B <= 40, 'Time_Constraint') # 생산 시간
solver.Add(4 * x_A + 2 * x_B <= 60, 'Material_Constraint') # 원자재

# 목표 제약 조건 (편차 변수 포함)
# 목표 1: 이익 800 달성
solver.Add(30 * x_A + 50 * x_B + d1_minus - d1_plus == 800, 'Goal1_Profit')
# 목표 2: 제품 A 10개 생산
solver.Add(x_A + d2_minus - d2_plus == 10, 'Goal2_ProdA')
# 목표 3: 제품 B 5개 생산 (이하 선호)
solver.Add(x_B + d3_minus - d3_plus == 5, 'Goal3_ProdB')

그다음 목표1이 최적해를 찾으면 목표1에 대한 최적해를 제약조건으로 넣고, 목표2에 대해서 최적해를 찾고 그다음 목표2에 대한 최적해를 제약조건으로 해서 목표3에 대해서 해결합니다.

 # --- Step 1: P1 목표 (이익 미달 d1_minus) 최소화 ---
print("--- Step 1: Minimize d1_minus (Profit Shortfall) ---")
solver.Minimize(d1_minus)
status1 = solver.Solve()

## invoke the solver
status = solver.Solve()

if status1 == pywraplp.Solver.OPTIMAL:
    min_d1_minus_val = solver.Objective().Value()
    print(f"Optimal d1_minus for P1: {min_d1_minus_val:.2f}")

    # P1의 최적 값을 다음 단계의 제약 조건으로 추가
    solver.Add(d1_minus == min_d1_minus_val, 'P1_Fixed')
    
    # --- Step 2: P2 목표 (제품 A 미달 d2_minus) 최소화 ---
    print("\n--- Step 2: Minimize d2_minus (Product A Shortfall) ---")
    solver.Minimize(d2_minus) # 목적 함수 변경
    status2 = solver.Solve()

    if status2 == pywraplp.Solver.OPTIMAL:
        min_d2_minus_val = solver.Objective().Value()
        print(f"Optimal d2_minus for P2: {min_d2_minus_val:.2f}")

        # P2의 최적 값을 다음 단계의 제약 조건으로 추가
        solver.Add(d2_minus == min_d2_minus_val, 'P2_Fixed')

        # --- Step 3: P3 목표 (제품 B 초과 d3_plus) 최소화 ---
        print("\n--- Step 3: Minimize d3_plus (Product B Overproduction) ---")
        solver.Minimize(d3_plus) # 목적 함수 변경
        status3 = solver.Solve()

        if status3 == pywraplp.Solver.OPTIMAL:
            min_d3_plus_val = solver.Objective().Value()
            print(f"Optimal d3_plus for P3: {min_d3_plus_val:.2f}")

            print("\n--- Final Solution ---")
            print(f"Product A (x_A): {x_A.solution_value():.5f}")
            print(f"Product B (x_B): {x_B.solution_value():.5f}")
            print(f"Final d1_minus (Profit Shortfall): {d1_minus.solution_value():.5f}")
            print(f"Final d1_plus (Profit Surplus): {d1_plus.solution_value():.5f}")
            print(f"Final d2_minus (Product A Shortfall): {d2_minus.solution_value():.5f}")
            print(f"Final d2_plus (Product A Surplus): {d2_plus.solution_value():.5f}")
            print(f"Final d3_minus (Product B Shortfall): {d3_minus.solution_value():.5f}")
            print(f"Final d3_plus (Product B Surplus): {d3_plus.solution_value():.5f}")

            # 실제 이익 및 자원 사용량 계산
            actual_profit = 30 * x_A.solution_value() + 50 * x_B.solution_value()
            print(f"Actual Profit: {actual_profit:.5f}")
            actual_prod_time = 2 * x_A.solution_value() + 3 * x_B.solution_value()
            print(f"Actual Production Time: {actual_prod_time:.5f} / 40")
            actual_raw_material = 4 * x_A.solution_value() + 2 * x_B.solution_value()
            print(f"Actual Raw Material: {actual_raw_material:.5f} / 60")

        else:
            print("Step 3: No optimal solution found.")
    else:
        print("Step 2: No optimal solution found.")
else:
    print("Step 1: No optimal solution found.")
    
    
    """
    --- Step 1: Minimize d1_minus (Profit Shortfall) ---
Optimal d1_minus for P1: 133.33

--- Step 2: Minimize d2_minus (Product A Shortfall) ---
Optimal d2_minus for P2: 10.00

--- Step 3: Minimize d3_plus (Product B Overproduction) ---
Optimal d3_plus for P3: 8.33

--- Final Solution ---
Product A (x_A): 0.00000
Product B (x_B): 13.33333
Final d1_minus (Profit Shortfall): 133.33333
Final d1_plus (Profit Surplus): 0.00000
Final d2_minus (Product A Shortfall): 10.00000
Final d2_plus (Product A Surplus): 0.00000
Final d3_minus (Product B Shortfall): 0.00000
Final d3_plus (Product B Surplus): 8.33333
Actual Profit: 666.66667
Actual Production Time: 40.00000 / 40
Actual Raw Material: 26.66667 / 60

"""

 

결과를 해석해보면 x_B를 13.33333 생산(임의로 만든예시라서 값이 소수점을 나타냄) 합니다. 그러면 목표1에서 제시한 Profit 수준은 133정도 미달하게됩니다. 이는 생산시간 제약조건에 막힌 결과입니다.

그 다음에는 목표1에 나온 d1_minus를 제약조건으로 해서 목표2를 계산합니다. 즉 목표1부터 최대한 맞추고 목표2를 맞추는 개념입니다.

이와 같이 목표계획법을 이용하면 여러가지 목표를 우선순위에 맞춰 반영할 수 있는 모형을 만들수 있습니다.