선형 프로그래밍 선형 함수의 최적해를 찾는 데 사용되는 수학적 개념입니다. 이 방법은 주어진 함수를 최적화하기 위해 간단한 가정을 사용합니다. 선형 프로그래밍은 거대한 실제 응용 프로그램을 가지고 있으며 다양한 유형의 문제를 해결하는 데 사용됩니다.

선형 프로그래밍은 운송 산업, 제조 산업, 운송 산업, 통신 등과 같은 다양한 산업에서 사용됩니다.

선형 프로그래밍이라는 용어는 선형과 프로그래밍이라는 두 단어로 구성됩니다. 선형이라는 단어는 문제에 사용되는 다양한 유형의 1차 변수 간의 관계를 나타내고 프로그래밍이라는 단어는 이러한 문제를 해결하기 위한 단계별 절차를 알려줍니다.

이번 글에서는 선형 계획법과 그 예, 공식, 기타 개념에 대해 자세히 알아봅니다.

내용의 테이블

• 선형 프로그래밍이란 무엇입니까?
• 선형 프로그래밍의 구성요소
• 선형 계획법 예
• 선형 프로그래밍 문제
• 선형 계획법 문제의 유형
• 선형 계획법 공식
• 선형 계획법 문제를 해결하는 방법?
• 선형 프로그래밍 방법
• 선형 계획법 심플렉스 방법
• 선형 프로그래밍 그래픽 방법
• 선형 프로그래밍 응용
• 선형 계획법의 중요성
• 선형 계획법의 최신 응용
• 운영 연구의 선형 프로그래밍
• 단순 방법

선형 프로그래밍이란 무엇입니까?

선형 프로그래밍 또는 선형 최적화 주어진 문제에 대한 최적의 솔루션을 찾는 데 도움이 되는 기술인 경우, 최적 솔루션은 주어진 특정 문제에 대해 가능한 최상의 결과를 제공하는 솔루션입니다.

간단히 말해서, 가능한 최선의 방법으로 어떤 일을 수행하는 방법을 찾는 방법입니다. 제한된 리소스를 사용하여 리소스를 최적으로 활용하고 최소 비용, 최대 마진 또는 최소 시간과 같은 특정 목표에서 최상의 결과를 달성해야 합니다.

특정 제약 조건이 적용되는 변수의 최상의 값을 검색해야 하는 상황에서는 선형 계획법 문제를 사용합니다. 이러한 상황은 일반적인 미적분학 및 수치 기법으로는 처리할 수 없습니다.

선형 프로그래밍 정의

선형 프로그래밍은 특정 시나리오를 최적화하는 데 사용되는 기술입니다. 선형 프로그래밍을 사용하면 주어진 상황에서 가능한 최상의 결과를 얻을 수 있습니다. 최적의 결과를 생성하는 방식으로 사용 가능한 모든 리소스를 사용합니다.

선형 프로그래밍의 구성요소

선형 계획법(LP) 문제의 기본 구성 요소는 다음과 같습니다.

• 결정 변수: 최적의 솔루션을 얻기 위해 결정하려는 변수입니다.
• 목적 함수: M 달성하려는 목표를 나타내는 수학적 방정식
• 제약: 의사결정 변수가 따라야 하는 제한사항입니다.
• 비음성 제한사항: 일부에서는 실제 시나리오에서는 의사결정 변수가 음수일 수 없습니다.

선형 계획법의 추가 특성

• 유한성: LP 문제의 결정 변수와 제약 조건의 수는 유한합니다.
• 선형성: 목적 함수와 모든 제약 조건은 결정 변수의 선형 함수여야 합니다. . 이는 변수의 정도가 1이어야 함을 의미합니다.

선형 계획법 예

아래에 설명된 예제를 통해 선형 계획법이 적용되는 상황을 이해할 수 있습니다.

배달원이 하루에 8개의 패킷을 도시의 여러 위치로 배달해야 한다고 가정해 보겠습니다. 그는 A에서 모든 패킷을 선택하여 이를 P, Q, R, S, T, U, V 및 W 지점으로 전달해야 합니다. 두 패킷 사이의 거리는 아래 이미지에 표시된 선으로 표시됩니다. 배달원이 따라가는 최단 경로는 선형 계획법의 개념을 사용하여 계산됩니다.

nfa 예

선형 프로그래밍 문제

선형 프로그래밍 문제(LPP) 함수에 대한 최적의 값 솔루션을 찾기 위해 선형 함수를 최적화하는 작업이 포함됩니다. 최적값은 최대값 또는 최소값일 수 있습니다.

LPP에서는 선형 함수가 호출됩니다. 목적 함수. 목적 함수는 조건이 적용되고 다음을 충족해야 하는 여러 변수를 가질 수 있습니다. 선형 제약조건 .

선형 계획법 문제의 유형

선형 계획법 문제(LPP)에는 다양한 문제가 있지만 이 기사에서는 세 가지 주요 선형 계획법 문제를 다루겠습니다.

제조 문제

제조 문제는 각 제품에 고정된 인력, 기계 시간, 원자재가 필요한 경우 이익을 극대화하기 위해 생산하거나 판매해야 하는 단위 수를 다루는 문제입니다.

다이어트 문제

이는 식품의 가용성과 가격에 따라 최소 비용을 얻기 위해 식단에 포함할 다양한 종류의 성분 수를 계산하는 데 사용됩니다.

교통 문제

서로 다른 위치에 있는 공장/공장에서 서로 다른 시장으로 제품을 운송하는 가장 저렴한 방법을 찾기 위해 운송 일정을 결정하는 데 사용됩니다.

선형 계획법 공식

선형 계획법 문제는 다음과 같이 구성됩니다.

• 결정 변수
• 목적 함수
• 제약
• 음수가 아닌 제한

결정 변수 선형 계획법 문제의 출력을 결정하고 최종 솔루션을 나타내는 변수 x 및 y입니다.

그만큼 목적함수 일반적으로 Z로 표시되는 는 최종 솔루션을 얻기 위해 주어진 조건에 따라 최적화되어야 하는 선형 함수입니다.

그만큼 제한 값을 제한하는 의사결정 변수에 부과되는 것을 제약이라고 합니다.

이제 선형 계획법 문제의 일반 공식은 다음과 같습니다.

목적 함수 : Z = 도끼 + 에 의해

제약: cx + dy ≥ e, px + qy ≤ r

음수가 아닌 제한사항: x ≥ 0, y ≥ 0

위의 조건에서 x와 y는 의사결정 변수입니다.

선형 계획법 문제를 해결하는 방법?

선형 계획법 문제를 해결하기 전에 먼저 표준 매개변수에 따라 문제를 공식화해야 합니다. 선형 계획법 문제를 해결하는 단계는 다음과 같습니다.

1 단계: 문제의 결정 변수를 표시하십시오.

2 단계: 문제의 목적 함수를 구축하고 함수를 최소화해야 하는지 또는 최대화해야 하는지 확인합니다.

3단계: 선형 문제의 모든 제약 조건을 적어보세요.

4단계: 의사결정 변수에 음수가 아닌 제한이 있는지 확인하십시오.

5단계: 이제 일반적으로 단순 방법이나 그래픽 방법을 사용하는 방법을 사용하여 선형 프로그래밍 문제를 해결합니다.

선형 프로그래밍 방법

선형 계획법 문제를 해결하기 위해 다양한 방법을 사용합니다. 가장 일반적으로 사용되는 두 가지 방법은 다음과 같습니다.

• 단순 방법
• 그래픽 방법

이 글에서 이 두 가지 방법에 대해 자세히 알아보겠습니다.

선형 계획법 심플렉스 방법

선형 계획법 문제를 해결하는 가장 일반적인 방법 중 하나는 단순 방법입니다. 이 방법에서는 최적의 해가 나올 때까지 특정 조건 'n'을 여러 번 반복합니다.

단순법을 사용하여 선형 계획법 문제를 해결하는 데 필요한 단계는 다음과 같습니다.

1 단계: 주어진 제약 조건을 기반으로 선형 계획법 문제를 공식화합니다.

2 단계: 필요한 경우 각 부등식에 여유 변수를 추가하여 주어진 모든 부등식을 선형 계획법 문제의 방정식 또는 등식으로 변환합니다.

3단계: 초기 심플렉스 테이블을 구성합니다. 각 제약 방정식을 행으로 표현하고 맨 아래 행에 목적 함수를 작성합니다. 이렇게 얻은 테이블을 Simplex 테이블이라고 합니다.

4단계: 맨 아래 행에서 가장 큰 음수 항목을 식별합니다. 가장 높은 음수 항목이 있는 요소의 열을 피벗 열이라고 합니다.

5단계: 맨 아래 행의 항목을 제외하고 가장 오른쪽 열의 항목을 해당 피벗 열의 항목으로 나눕니다. 이제 가장 적은 항목을 포함하는 행을 피벗 행이라고 합니다. 피벗 요소는 피벗 행과 피벗 열의 교차점으로 얻습니다.

6단계: 행렬 연산을 사용하고 피벗 요소를 사용하여 피벗 열의 모든 항목을 0으로 만듭니다.

7단계: 맨 아래 행에 음수가 아닌 항목이 있는지 확인하고, 맨 아래 행에 음수 항목이 없으면 프로세스를 종료하고, 그렇지 않으면 4단계부터 프로세스를 다시 시작합니다.

8단계: 이렇게 얻은 최종 심플렉스 테이블은 문제에 대한 해결책을 제공합니다.

선형 프로그래밍 그래픽 방법

그래픽 방법은 선형 프로그래밍 문제를 해결하는 데 사용되는 Simplex 방법과 다른 방법입니다. 이름에서 알 수 있듯이 이 방법은 그래프를 사용하여 주어진 선형 프로그래밍 문제를 해결합니다. 이는 선형 프로그래밍 문제를 해결하는 가장 좋은 방법이며 단순 방법보다 노력이 덜 필요합니다.

이 방법을 사용하는 동안 우리는 주어진 선형 계획법 문제에서 제약을 받는 모든 부등식을 플로팅합니다. 주어진 LPP의 모든 부등식이 XY 그래프에 표시되자마자 모든 부등식의 공통 영역이 최적의 솔루션을 제공합니다. 실현 가능 영역의 모든 꼭지점을 계산하고 모든 해당 지점의 목적 함수 값을 계산한 다음 이 값을 비교하여 LPP의 최적 솔루션을 얻습니다.

예: 제약 조건이 다음과 같을 때 z = 6x + 9y의 최대값과 최소값을 찾습니다.

• 2x + 3년 ≤ 12
• x와 y ≥ 0
• x + y ≤ 5

해결책:

1 단계 : 먼저 부등식을 정규 방정식으로 변환합니다. 따라서 방정식은 2x+3y = 0, x = 0, y = 0 및 x + y = 5가 됩니다.

2 단계 : 2x + 3y 및 x + y = 5가 x축과 y축을 자르는 점을 찾습니다. x축의 교차점을 찾으려면 해당 방정식에 y = 0을 넣고 점을 찾으세요. 마찬가지로 y축 교차점의 경우 해당 방정식에 x = 0을 넣습니다.

3단계 : x축과 y축을 자르는 두 개의 선을 그립니다. 우리는 두 축이 (3,2)에서 서로 잘리는 것을 발견했습니다.

4단계 : x ≥ 0 및 y ≥ 0의 경우 두 부등식을 모두 따른다는 것을 알 수 있습니다. 따라서 영역에는 두 개의 축과 원점을 포함하는 두 선으로 둘러싸인 영역이 포함됩니다. 표시된 영역은 아래 그림에 나와 있습니다.

5단계 : 각 점의 Z와 최대값 및 최소값을 찾습니다.

좌표	Z = 6x + 9y
(0.5)	Z = 45
(0.4)	Z = 36
(5.0)	Z = 30
(6.0)	Z = 36
(3.2)	Z = 36

따라서 Z = 6x + 9y는 (0,5)에서 최대값이고 (5,0)에서 최소값임을 알 수 있습니다.

선형 프로그래밍 응용

선형 계획법은 다양한 분야에 응용됩니다. 문제의 모든 제약조건이 주어졌을 때 프로세스의 최소 비용을 찾는 데 사용됩니다. 차량 등의 운송 비용을 최적화하는데 사용됩니다. 선형 프로그래밍의 다양한 응용 분야는 다음과 같습니다.

엔지니어링 산업

엔지니어링 산업에서는 선형 프로그래밍을 사용하여 설계 및 제조 문제를 해결하고 주어진 조건에서 최대 결과를 얻습니다.

제조 산업

제조 산업에서는 선형 계획법을 사용하여 기업의 이익을 극대화하고 제조 비용을 절감합니다.

에너지 산업

에너지 회사는 선형 프로그래밍을 사용하여 생산 출력을 최적화합니다.

운송 산업

선형 프로그래밍은 운송 산업에서도 운송 비용을 최소화하는 경로를 찾는 데 사용됩니다.

선형 계획법의 중요성

선형 프로그래밍은 다양한 산업 분야에서 매우 중요하며, 다양한 제약 조건에 따라 입력 값을 최소화하면서 출력 값을 최대화합니다.

LP는 문제를 해결하는 동안 여러 조건이 있고 문제의 출력을 최적화해야 할 때 적용 가능성이 높습니다. 즉, 주어진 조건에 따라 최소값 또는 최대값을 찾아야 합니다.

더 읽어보기,

• 선형 부등식
• 선형부등식의 대수적 해법

선형 프로그래밍 문제

문제 1: A 회사는 두 가지 유형의 제품을 제조하고 판매하며, 각 단위 a와 b의 생산 비용은 각각 200루피와 150루피입니다. 각 제품 단위는 20루피의 이윤을 얻고, 제품 b의 각 단위는 판매 시 15루피의 이윤을 얻습니다. . 회사는 A와 B의 월별 수요를 해당 월의 전체 생산예산 중 최대 수확 단위가 될 것으로 추정하고 50,000루피로 설정했습니다. 그리고 ㄴ?

해결책:

x = A 유형의 단위 수

y = 유형 B의 단위 수

Z 최대화 = 40x + 50y

제약 조건이 적용됨

3x + y ≤ 9

x + 2y ≤ 8

문자열 배열 C 프로그래밍

그리고 x, y ≥ 0

방정식을 고려하십시오.

3x + y = 9

엑스 = 3

와이 = 0

그리고 x + 2y = 8

엑스 = 8

와이 = 0

이제 4개의 점(정점)에서 Z 값을 평가하여 Z의 최대 값을 결정할 수 있습니다.

정점	Z = 40x + 50y
(0, 0)	Z = 40 × 0 + 50 × 0 = 루피. 0
(3, 0)	Z = 40 × 3 + 50 × 0 = 루피. 120
(0, 4)	Z = 40 × 0 + 50 × 4 = 루피. 200
(23)	Z = 40 × 2 + 50 × 3 = 루피. 230

최대 이익, Z = Rs. 230

∴ A타입 유닛 수는 2개, B타입 유닛 수는 3개입니다.

문제 2: Z = 3x + 4y를 최대화합니다.

x + y ≤ 450, 2x + y ≤ 600 및 x, y ≤ 0이라는 제약 조건이 적용됩니다.

해결책:

우리는 주어진 것에서

제약조건(1)

X + Y = 450

x = 0, ⇒ 0 + y = 450 ⇒ y = 450

y = 0, ⇒ x + 0 = 450 ⇒ x = 450

에서, 제약조건(2)

2x + y = 600

x = 0, ⇒ 0 + y = 600 ⇒ y = 600

y = 0, ⇒ 2x + 0 = 600 ⇒ x = 300

이제 우리는 Z = 3x + 4y 좌표의 점을 갖게 되었습니다.

따라서 좌표 x = 0 및 y = 450에서 최적 솔루션 최대값 Z = 1800입니다. 그래프는 아래와 같습니다.

선형 계획법의 최신 응용

강력한 수학적 기법인 선형 프로그래밍은 다양한 산업 분야의 최적화 문제를 해결하는 데 사용됩니다. 다음은 몇 가지 최신 응용 프로그램입니다.

• 공급망 최적화 : 선형 프로그래밍은 기업이 공급망에서 비용을 최소화하고 효율성을 극대화하는 데 도움이 됩니다. 가장 비용 효율적인 운송 경로, 창고 운영 및 재고 관리 전략을 결정하는 데 사용됩니다.
• 에너지 관리 : 에너지 부문에서는 에너지 생산 방법의 혼합을 최적화하기 위해 선형 계획법이 활용됩니다. 여기에는 수요를 충족하는 동시에 비용과 환경 영향을 줄이기 위해 전통적인 에너지원과 재생 가능한 에너지원의 균형이 포함됩니다.
• 통신 네트워크 설계 : 선형 프로그래밍은 효율적인 통신 네트워크 설계에 도움이 됩니다. 대역폭을 할당하고, 네트워크 레이아웃을 설계하고, 데이터 흐름을 최적화하여 저렴한 비용으로 고속 통신을 보장하는 데 도움이 됩니다.
• 재무 계획 : 기업 및 재무 분석가는 포트폴리오 최적화, 위험 관리 및 자본 예산 책정을 위해 선형 프로그래밍을 사용합니다. 이는 위험을 최소화하면서 수익을 극대화하는 투자 결정을 내리는 데 도움이 됩니다.
• 헬스케어 물류 : 헬스케어에서는 병상, 의료진, 장비 등 자원 배분을 최적화하기 위해 선형 프로그래밍을 적용합니다. 이는 환자 치료를 개선하고 대기 시간을 줄이며 비용을 효과적으로 관리하는 데 매우 중요합니다.
• 제조 공정 최적화 : 선형 프로그래밍은 인력, 자재, 기계 가용성과 같은 제약 조건을 고려하여 제조 시설 내 여러 제품에 대한 최적의 생산 수준을 결정하는 데 사용됩니다.
• 농업계획 : 농부와 농업 계획자는 선형 프로그래밍을 사용하여 작물 선택, 토지 이용 및 자원 할당을 결정하여 자원을 보존하는 동시에 수확량과 이익을 극대화합니다.
• 항공사 승무원 스케줄링 : 항공사는 선형 프로그래밍을 사용하여 효율적으로 승무원 일정을 계획하고 규정을 준수하여 항공편에 인력을 배치하고 운영 비용을 최소화합니다.

이러한 응용 프로그램은 다양한 분야의 복잡한 최적화 문제를 해결하는 선형 계획법의 다양성과 강력함을 보여주며 오늘날의 데이터 중심 세계에서의 관련성을 보여줍니다.

운영 연구의 선형 프로그래밍

• 핵심 도구 : 선형 프로그래밍은 자원 최적화를 위한 운영 연구의 기본 도구입니다.
• 의사결정 : 자원 배분, 이익 극대화, 비용 최소화와 관련하여 최선의 결정을 내리는 데 도움이 됩니다.
• 폭넓은 응용 : 물류, 제조, 금융, 헬스케어 등 다양한 분야에서 복잡한 문제 해결을 위해 활용됩니다.
• 실제 문제 모델링 : 실제 문제를 수학적 모델로 변환하여 가장 효율적인 솔루션을 찾습니다.

단순 방법

• 최적화 알고리즘 : 심플렉스 방법(Simplex Method)은 선형 부등식에 대한 최적의 솔루션을 찾기 위해 선형 프로그래밍에 사용되는 강력한 알고리즘입니다.
• 단계별 접근 방식 : 제약조건에 의해 정의된 실현 가능 영역의 가장자리를 탐색하여 최적의 솔루션을 향해 반복적으로 이동합니다.
• 능률 : 대규모 선형 계획법 문제를 효율적으로 해결하는 것으로 알려져 있습니다.
• 다재 : 다이어트 플래닝, 네트워크 플로우, 생산 스케줄링 등 다양한 영역에 적용 가능해 활용도가 높습니다.

선형 계획법 – FAQ

선형 프로그래밍이란 무엇입니까?

선형 계획법은 다양한 제약 조건이 있는 주어진 선형 문제를 최적화하는 데 사용되는 수학적 개념입니다. 선형 프로그래밍을 사용하여 주어진 문제의 최적 출력을 얻습니다.

선형 계획법 문제란 무엇입니까?

선형 프로그래밍 문제(LPP)는 주어진 조건에 대한 최적의 솔루션을 제공하는 문제입니다.

선형 프로그래밍 공식이란 무엇입니까?

일반 선형 계획법 공식은 다음과 같습니다.

• 목적 함수: Z = ax + by
• 제약 조건: px + qy ≤ r, sx + ty ≤ u
• 음이 아닌 제한: x ≥ 0, y ≥ 0

선형 프로그래밍에는 어떤 유형이 있나요?

다양한 유형의 선형 프로그래밍 방법은 다음과 같습니다.

• Simplex 방법에 의한 선형 계획법
• R 방법에 의한 선형 프로그래밍
• 그래픽 방식에 의한 선형 프로그래밍

선형 프로그래밍의 요구 사항은 무엇입니까?

선형 계획법 문제의 다양한 요구 사항은 다음과 같습니다.

• 선형성
• 목적 함수
• 제약
• 비부정성

선형 계획법의 장점은 무엇입니까?

선형 프로그래밍의 다양한 장점은 다음과 같습니다.

• 주어진 선형 문제에 대한 최적의 솔루션을 제공합니다.
• 사용하기 쉽고 항상 일관된 결과를 제공합니다.
• 이는 이익을 극대화하고 투입 비용을 줄이는 데 도움이 됩니다.