개요

선형 프로그래밍(linear programming)은 최적화 문제를 해결하는 수학적인 방법 중 하나입니다. 선형 프로그래밍은 선형 함수의 최댓값 또는 최솟값을 찾는 문제를 다루며, 강한 쌍대 정리(strong duality theorem)는 선형 프로그래밍에서 중요한 이론 중 하나입니다. 이번 블로그에서는 파이썬을 사용하여 선형 프로그래밍의 강한 쌍대 정리를 증명해 보겠습니다.

강한 쌍대 정리란?

강한 쌍대 정리는 선형 프로그래밍의 기본 이론 중 하나로, 원문서에서는 다음과 같이 설명되어 있습니다.

선형 프로그래밍 문제의 원시 문제(primal problem)과 쌍대 문제(dual problem) 중 하나가 최적해를 가지면 다른 문제도 최적해를 가지며, 두 최적해의 값은 같다.

즉, 원시 문제와 쌍대 문제 중 하나의 최적해를 찾으면, 다른 문제도 최적해를 가지게 되며, 두 최적해의 값은 항상 같다는 것을 의미합니다. 이 정리는 선형 프로그래밍 문제를 풀 때 유용하게 활용될 수 있습니다.

파이썬으로 증명하기

이제 파이썬을 사용하여 강한 쌍대 정리를 증명해보겠습니다. 파이썬에서는 선형 프로그래밍 문제를 푸는 데에 유용한 scipy 라이브러리의 linprog() 함수를 활용할 수 있습니다.

먼저, 필요한 라이브러리를 임포트합니다.

import numpy as np
from scipy.optimize import linprog

원시 문제와 쌍대 문제의 목적 함수와 제약 조건을 설정합니다. 예를 들어, 다음과 같은 원시 문제를 고려해 봅시다.

• 원시 문제 목적 함수: minimize -2x1 + 3x2
• 제약 조건:
  • 2x1 + x2 <= 4
  • x1 + 3x2 >= 3
  • x1, x2 >= 0

이를 파이썬 코드로 표현하면 다음과 같습니다.

c = np.array([-2, 3])
A_ub = np.array([[2, 1]])
b_ub = np.array([4])
A_eq = np.array([[-1, -3]])
b_eq = np.array([-3])

강한 쌍대 정리를 증명하기 위해 원시 문제와 쌍대 문제를 각각 linprog() 함수에 적용하여 최적해를 구하고, 각 최적해의 값이 같은지 확인합니다.

res_primal = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq)
res_dual = linprog(-b_ub, A_ub=-A_ub.T, b_eq=-A_eq.T, c=-c)

if res_primal.success and res_dual.success:
    if np.isclose(res_primal.fun, -res_dual.fun):
        print("강한 쌍대 정리가 증명되었습니다.")
else:
    print("최적해를 찾을 수 없습니다.")

위의 코드를 실행하면, 원시 문제와 쌍대 문제의 최적해 값이 일치하는지 확인할 수 있습니다. 최적해 값이 일치하면 “강한 쌍대 정리가 증명되었습니다.”라는 메시지가 출력되며, 최적해 값을 찾을 수 없는 경우 “최적해를 찾을 수 없습니다.”라는 메시지가 출력됩니다.

결론

이번 블로그에서는 파이썬을 사용하여 선형 프로그래밍의 강한 쌍대 정리를 증명하는 방법을 알아보았습니다. 강한 쌍대 정리는 선형 프로그래밍 문제를 풀 때 매우 유용한 이론으로, 파이썬의 scipy 라이브러리를 활용하여 손쉽게 확인할 수 있습니다. 선형 프로그래밍을 다루는 경우 강한 쌍대 정리를 기억하고 활용하여 문제를 효율적으로 해결해보세요.

#파이썬 #선형프로그래밍