선형 계획법에 대한 부드러운 소개

먼저 선형 방정식에 대해 이야기합시다. 선형 방정식은 변수로 구성되며 유일한 제한은 각 변수가 1의 거듭제곱을 가질 수 있다는 것입니다. 즉, 2 이상의 거듭제곱을 가진 변수는 있을 수 없습니다.

작성자의 이미지

선형 프로그래밍은 두 부분으로 구성됩니다. 목적 함수는 선형 방정식과 제약 조건 집합입니다. 목적 함수 또는 선형 방정식은 최대화되거나 최소화되어야 합니다.

예: 서점에 3가지 유형의 책(물리, 화학 및 생물학)이 있다고 가정합니다. 물리학 책은 10\$, 화학은 5\$, 생물학은 2\$의 수익을 냅니다. 총 이익에 대한 방정식을 작성하려면 다음과 같을 것입니다.

작성자의 이미지

위 방정식을 최대화해야 합니다. 지금은 제약 조건이 없으므로 변수 값에 상한이 없습니다. 그러나 실생활에서는 제약이 있을 것입니다. 위의 예에서 제약 조건은 서점에 보유하고 있는 책의 수가 될 수 있습니다. 책 판매자에게 물리학 책 5권, 화학 책 3권, 생물학 책 10권이 있다면 문제는 아래와 같습니다.

작성자의 이미지

위의 경우는 간단한 경우이며 Python을 사용하지 않고도 해결할 수 있습니다. 그러나 실제 세계에서 문제의 공식화는 본질적으로 매우 복잡합니다. 다음 장에서 이들 중 일부를 살펴보겠습니다.

선형 프로그래밍의 일부 응용 프로그램은 다음과 같습니다.

공급망

일정 문제

배달 경로 문제

제조 문제

다이어트 계획 최적화

제작기획

교통수단

문제가 복잡해질수록 솔버의 도움 없이는 문제를 해결하기가 더 어려워집니다. 솔버는 기본적으로 문제 공식(변수, 목표 및 제약 조건)을 입력으로 받아들이고 솔루션을 반환하는 소프트웨어입니다.

PuLP은 Python으로 작성된 오픈 소스 소프트웨어입니다. 서점 문제와 같은 문제를 공식화하는 데 도움이 됩니다. 무료이며 무료 오픈 소스 솔버도 지원합니다. PuLP에 대한 소개는 아래 내 기사를 참조하십시오.

Basic Linear Programming in Python with PuLP

Python을 사용하여 실행 가능한 영역 플로팅

In some cases a linear problem doesn’t have an objective function, it simply has a set of constraints, and the solution which satisfies all the constraints is required.

이미지는 here에서 가져온 것입니다.

일련의 제약 조건이 주어지면 실현 가능한 영역은 솔루션 공간 또는 모든 제약 조건을 충족하는 값 집합입니다. 위의 그림에서 다양한 선은 자동차 A(X축) 및 자동차 B(Y축)와 관련된 제약 조건이며 녹색 음영 영역은 실행 가능한 영역입니다. 녹색 음영 영역 내의 모든 좌표(예: (1,2), (2,2) 등)는 모든 제약 조건을 충족합니다.

다음 제약 조건 집합을 고려하십시오.

작성자의 이미지

위의 제약 조건에 대해 실현 가능한 영역을 플로팅해 보겠습니다. 먼저 NumPy와 matplotlib를 설치합니다.

pip3 install numpy, matplotlib

Below is the code for plotting the

x = np.linspace(0, 50, 1000)
y = np.linspace(0, 50, 1000)

'''
Draw Vertical Line
'''
plt.axvline(10, color='b', label=r'X <=10')
plt.axvline(0, color='b', label=r'X >=0')

'''
Draw Horizontal Line
'''
plt.axhline(2, color='r', label='Y >= 2') 
plt.axhline(10, color='r', label='Y <= 10') 

'''
X+Y>=12
'''
plt.plot(x, 12-x, label='X+Y>=12',color='b')

'''
X+Y<=15
'''
plt.plot(x, 15-x, label=r'X+Y<=15',color='yellow') # constraint 4

plt.xlim((0, 20))
plt.ylim((0, 20))
plt.show()

이것은 줄거리

플롯된 라인

Matplotlib가 실행 가능한 영역을 계산하게 하기

다음 코드는 위의 가능한 영역을 계산합니다.

x,y = np.meshgrid(np.linspace(0, 50, 1000),np.linspace(0, 50, 1000))
plt.imshow( 
        (
            (x>=0)&(x<=10)&(y>=2)&(y<=15-x)&(y>=12-x)&(y<=10)
        ).astype(int) , 
        extent=(0,50,0,50),
        origin="lower", 
        cmap="Reds", 
        alpha = 0.3);

선을 그리기 전에 이것을 입력해야 합니다. 이렇게 하면 실행 가능한 영역 위에 선이 그려집니다. 이 방법은 this stack overflow answer에서 가져온 것입니다.

아래는 가능한 지역입니다.

가능한 지역 플롯

이 실현 가능 영역의 모든 점은 모든 제약 조건을 충족합니다.

결론

이 기사가 선형 프로그래밍에 대한 좋은 소개가 되었기를 바랍니다.

선형 프로그래밍과 관련된 다음 기사를 확인할 수 있습니다.

Basic Linear Programming in Python with PuLP

How To Solve A Sudoku Puzzle Using Python And Linear Programming

How to Balance Chemical Equations in Python using Constraint Optimization (PuLP)




, 에 연결합니다.

내 글이 마음에 들고 나를 지원하고 싶다면 내 Referral link를 사용하여 미디엄 멤버십에 가입하는 것을 고려하십시오. 페이월 뒤에 있는 모든 기사에 액세스할 수 있습니다. 내 추천을 사용하면 추가 비용 없이 월간 구독의 일부를 받을 수 있습니다.