선형 프로그래밍 : 모델, 제약, 응용 분야의 정의 - 수학 - 2025

선형 프로그래밍 수학적 방법 되고 최적화 (최대화 또는 최소화 적절하게) 그 변수를 제한하는 기능을 사용, 같은 만큼 함수 및 제약 선형 종속 변수이다.

일반적으로 최적화되는 기능은 투입, 노동 또는 기계가 제한된 제조업체의 이익과 같은 실제 상황을 모델링합니다.

그림 1. 선형 프로그래밍은 수익을 최적화하는 데 널리 사용됩니다. 출처 : Piqsels.

가장 간단한 경우 중 하나는 결정 변수라고하는 두 개의 변수에만 의존하는 선형 함수가 최대화되는 경우입니다. 다음과 같은 형식 일 수 있습니다.

Z = k ₁ x + k ₂ y

k ₁ 및 k ₂ 상수로. 이 함수를 목적 함수라고합니다. 물론 연구에 두 가지 이상의 변수가 필요한 상황이 더 복잡합니다.

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +…

또한 제약은 x와 y에서 똑같이 선형 인 방정식 또는 부등식 시스템에 의해 수학적으로 모델링됩니다.

이 시스템의 솔루션 세트를 실행 가능 솔루션 또는 실행 가능 포인트라고합니다. 그리고 실현 가능한 지점 중에는 목적 함수를 최적화하는 적어도 하나가 있습니다.

선형 계획법은 제 2 차 세계 대전 직후 미국의 물리학 자이자 수학자 인 George Dantzig (1914-2005)와 러시아의 수학자이자 경제학자 인 Leonid Kantorovich (1912-1986)에 의해 독립적으로 개발되었습니다.

심플 렉스 방법으로 알려진 문제 해결 방법은 미 공군, 버클리 대학 및 스탠포드 대학에서 근무한 Dantzig의 아이디어입니다.

그림 2. 수학자 George Dantzig (왼쪽)와 Leonid Kantorovich (오른쪽). 출처 : F. Zapata.

선형 프로그래밍 모델

실제 상황에 적합한 선형 계획법 모델을 설정하는 데 필요한 요소는 다음과 같습니다.

-목표 기능

-결정 변수

-제한

목적 함수에서 달성하려는 것을 정의합니다. 예를 들어, 특정 제품의 제조로 인한 수익을 극대화하려고한다고 가정 해보십시오. 그런 다음 제품이 판매되는 가격에 따라 "수익"기능이 설정됩니다.

수학적 용어로이 함수는 합계 표기법을 사용하여 축약하여 표현할 수 있습니다.

Z = ∑k _i x _i

이 방정식에서 k _i 는 계수이고 x _i 는 결정 변수입니다.

결정 변수는 통제권이있는 시스템의 요소이며 그 값은 양의 실수입니다. 제안 된 예에서 결정 변수는 최대 이익을 얻기 위해 제조 할 각 제품의 수량입니다.

마지막으로 결정 변수 측면에서 선형 방정식 또는 부등식 인 제약 조건이 있습니다. 그들은 문제에 대한 한계를 설명하는데, 이는 예를 들어 제조에 사용 가능한 원료의 양이 될 수 있으며 알려져 있습니다.

제한 유형

j = 1부터 j = M까지 여러 가지 제한이있을 수 있습니다. 수학적으로 제한은 세 가지 유형입니다.

1. A _j = ∑ a _ij . x _나는
2. B _j ≥ ∑ b _ij . x _나는
3. C _j ≤ ∑ c _ij . x _나는

첫 번째 제한은 선형 방정식 유형이며 알려진 값 A _j 를 준수해야 함을 의미합니다.

나머지 두 가지 제한은 선형 부등식이며 , 기호가 ≤ 인 경우 나타나는 기호가 ≥ (크거나 같음)이거나 존중되거나 초과되지 않을 때 알려진 값 B _j 및 C _j 가 존중되거나 초과 될 수 있음을 의미합니다. (작거나 같음).

모델 예

응용 분야는 경영학에서 영양에 이르기까지 매우 다양하지만 그 방법을 이해하기 위해 두 가지 변수가있는 실제 상황의 간단한 모델을 아래에 제안합니다.

현지 제과점은 블랙 포레스트 케이크와 새 크리 판틴 케이크의 두 가지 특산품으로 유명합니다.

준비 과정에서 계란과 설탕이 필요합니다. 검은 숲의 경우 계란 9 개와 설탕 500g이 필요하고 새 크리 판틴의 경우 계란 8 개와 설탕 800g이 필요합니다. 각각의 판매 가격은 $ 8 및 $ 10입니다.

문제는 : 제과점이 10kg의 설탕과 144 개의 계란을 가지고 있다는 것을 알면서 수익을 극대화하기 위해 각 종류의 케이크를 몇 개 만들어야 하는가?

결정 변수

의사 결정 변수는 "x"및 "y"이며 실제 값을 사용합니다.

-x : 블랙 포레스트 케이크의 수

-y : sacripantine 유형 케이크.

제한

제한은 케이크의 수가 양수이고이를 준비 할 수있는 원료의 양이 제한되어 있다는 사실에 의해 주어집니다.

따라서 수학적 형식에서 이러한 제한은 다음과 같은 형식을 취합니다.

1. x ≥ 0
2. 및 ≥0
3. 9 배 + 8 년 ≤ 144
4. 0.5 x + 0.8y ≤ 10

제약 조건 1과 2는 이전에 노출 된 부정성이 아닌 조건을 구성하며 제기 된 모든 불평등은 선형입니다. 제한 사항 3과 4에는 초과해서는 안되는 값이 있습니다 : 계란 144 개와 설탕 10kg.

목적 기능

마지막으로 목적 함수는 "x"양의 블랙 포레스트 케이크와 "y"양의 sacripantine을 제조 할 때 얻는 이익입니다. 만든 케이크의 수량에 가격을 곱하고 각 유형에 추가하여 만들어집니다. G (x, y)라고 부르는 선형 함수입니다.

G = 8x + 10 년

솔루션 방법

다양한 솔루션 방법론에는 그래픽 방법, 심플 렉스 알고리즘 및 내부 포인트 방법이 포함됩니다.

-그래픽 또는 기하학적 방법

이전 섹션의 것과 같은 두 개의 변수 문제가있는 경우 제약 조건은 xy 평면의 다각형 영역 (실행 가능 영역 또는 실행 가능 영역이라고 함)을 결정합니다.

그림 3. 최적화 문제의 솔루션이 발견되는 실행 가능 영역. 출처 : Wikimedia Commons.

이 영역은 제한의 부등식에서 얻은 선인 제한선을 사용하여 구성되며 등호 기호로만 작동합니다.

이익을 최적화하려는 제과점의 경우 제약 조건은 다음과 같습니다.

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0.5 x + 0.8y = 10

이 선으로 둘러싸인 영역의 모든 점은 가능한 솔루션이므로 무한히 많은 점이 있습니다. 실행 가능 영역이 비어있는 것으로 판명 된 경우를 제외하고 제기 된 문제에 해결책이 없습니다.

다행히 생과자 문제의 경우 실행 가능 영역이 비어 있지 않습니다. 아래에 있습니다.

그림 4. 생과자 문제의 실현 가능한 영역. 게인이 0 인 선은 원점을 교차합니다. 출처 : F. Zapata with Geogebra.

존재하는 경우 최적의 솔루션은 목적 함수의 도움으로 찾을 수 있습니다. 예를 들어 최대 이익 G를 찾으려고 할 때 iso-profit 라인이라고하는 다음 라인이 있습니다.

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

이 선을 사용하여 주어진 이득 G를 제공하는 모든 쌍 (x, y)을 얻습니다. 따라서 G 값에 따라 선군이 있지만 모두 동일한 기울기 -k ₁ / k ₂ 를 갖기 때문에 다음과 같습니다. 평행선.

최적의 솔루션

이제 선형 문제의 최적 솔루션은 항상 실행 가능한 영역의 극단 또는 꼭지점이라는 것을 알 수 있습니다. 그래서:

원점에 가장 가까운 선이 실현 가능 영역과 공통된 전체 세그먼트를 가지고 있으면 무한한 솔루션이 있다고합니다. 이 경우는 iso-profit 라인의 기울기가 지역을 제한하는 다른 라인의 기울기와 같을 때 발생합니다.

페이스트리의 경우 후보 정점은 A, B 및 C입니다.

-Dantzig의 단순 방법

그래픽 또는 기하학적 방법은 두 가지 변수에 적용 할 수 있습니다. 그러나 변수가 3 개인 경우 더 복잡하고 많은 수의 변수에 사용할 수 없습니다.

두 개 이상의 변수가있는 문제를 다룰 때 목적 함수를 최적화하기위한 일련의 알고리즘으로 구성된 단순 방법이 사용됩니다. 계산을 수행하기 위해 종종 행렬과 간단한 산술이 사용됩니다.

단순 방법은 실행 가능한 솔루션을 선택하고 이것이 최적인지 확인하는 것으로 시작됩니다. 그렇다면 우리는 이미 문제를 해결했지만 그렇지 않은 경우 최적화에 더 가까운 솔루션을 계속 추구합니다. 솔루션이 존재하는 경우 알고리즘은 몇 번의 시도로이를 찾습니다.

응용

선형 및 비선형 프로그래밍은 필요한 시간을 최소화하려는 경우와 같이 시간에 따라 측정 할 수 있기 때문에 비용을 줄이고 이익을 늘리는 측면에서 최상의 결정을 내리기 위해 많은 분야에 적용됩니다. 일련의 작업을 수행합니다.

다음은 몇 가지 필드입니다.

-마케팅에서 특정 제품을 광고하기위한 미디어 (소셜 네트워크, 텔레비전, 언론 등)의 최상의 조합을 찾는 데 사용됩니다.

-회사 또는 공장의 직원에게 적절한 작업을 할당하거나 그들에게 일정을 잡습니다.

-가장 영양가가 높은 식품을 선택하고 축산 및 가금류 산업에서 가장 저렴한 비용으로.

해결 된 운동

- 연습 1

이전 섹션에서 제기 한 선형 계획법 모델을 그래픽으로 해결합니다.

해결책

문제에 지정된 제한 시스템에 의해 결정된 값 집합을 그래프로 표시해야합니다.

1. x ≥ 0
2. 및 ≥0
3. 9 배 + 8 년 ≤ 144
4. 0.5 x + 0.8y ≤ 10

부등식 1과 2로 주어진 영역은 데카르트 평면의 1 사분면에 해당합니다. 부등식 3과 4와 관련하여 제한선을 찾는 것으로 시작합니다.

9x + 8y = 144

0.5 x + 0.8y = 10 → 5x + 8y = 100

실현 가능 영역은 꼭지점이 A, B, C, D 인 사각형입니다.

최소 이익은 0이므로 라인 8x + 10y = 0은 하한이고 등가 이익 라인의 기울기는 -8/10 =-0.8입니다.

이 값은 다른 제한선의 기울기와 다르며 실행 가능 영역이 제한되어 있으므로 고유 한 솔루션이 존재합니다.

그림 5. 실행 가능 영역과 해당 영역의 꼭지점 중 하나에서 솔루션 점 C를 보여주는 연습 1의 그래픽 솔루션. 출처 : F. Zapata.

이 솔루션은 좌표가 다음과 같은 점 A, B 또는 C를 통과하는 경사 선 -0.8에 해당합니다.

A (11; 5.625)

B (0; 12.5)

C (16, 0)

최적의 솔루션

이러한 각 점에 대해 G 값을 계산합니다.

- (11; 5.625) : G = 8 × 11 + 10 × 5.625 = 144.25

-(0; ​​12.5) : G _B = 8 x 0 + 10 x 12.5 = 125

-(16, 0) : G _C = 8 x 16 + 10 x 0 = 128

가장 높은 수익은 11 개의 블랙 포레스트 케이크와 5,625 개의 새 크리 판틴 케이크를 생산하는 것입니다. 이 솔루션은 소프트웨어를 통해 찾은 솔루션과 일치합니다.

-연습 2

선형 계획법에서 최적화를위한 Simplex 알고리즘을 통합하는 Excel 또는 LibreOffice Calc와 같은 대부분의 스프레드 시트에서 사용할 수있는 Solver 함수를 사용하여 이전 연습의 결과를 확인합니다.

해결책

그림 6. 연습 1에서 Libre Office Calc 스프레드 시트까지의 솔루션 세부 사항. 출처 : F. Zapata.

그림 7. 연습 1에서 Libre Office Calc 스프레드 시트까지의 솔루션 세부 사항. 출처 : F. Zapata.

참고 문헌

1. 훌륭한. 선형 프로그래밍. 출처 : brilliant.org.
2. Eppen, G. 2000. 행정 과학에있는 운영 연구. 5 일. 판. 프렌 티스 홀.
3. Haeussler, E. 1992. 관리 및 경제학을위한 수학. 2 위. 판. Grupo Editorial Iberoamericana.
4. Hiru.eus. 선형 프로그래밍. 출처 : hiru.eus.
5. Wikipedia. 선형 프로그래밍. 출처 : es. wikipedia.org.