선형 계획법 문제, 솔루션 및 응용 [예제 포함]

데이터 과학에는 많은 응용 프로그램이 있으며 그 중 가장 두드러진 것 중 하나는 최적화입니다. 우리 모두는 최적화에 집중하는 경향이 있습니다. 최적화는 제한된 리소스로 가장 원하는 결과를 얻는 데 중점을 둡니다.

모든 종류의 최적화 문제가 있으며 일부는 작고 일부는 매우 복잡합니다. 그것들을 진행하는 동안 선형 계획법 문제라고 하는 특정 범주를 찾을 수 있습니다. 이 기사에서 우리는 그것들이 무엇이며 어떻게 작업할 수 있는지 논의했습니다.

당신이 오렌지나 사과 또는 이 둘의 특정 조합을 살 수 있는 과일 판매자라고 가정해 봅시다. 그러나 예산이 INR 5,000에 불과하고 30개의 가방만 저장할 수 있습니다. 이제 가장 높은 수익을 내는 방식으로 구매해야 합니다.

이제 오렌지 한 봉지의 가격은 INR 500이고 사과 한 봉지의 가격은 INR 750입니다. 오렌지 한 봉지를 판매하여 INR 100, 사과 한 봉지를 판매하여 INR 200를 만들 수 있습니다.

이 문제에는 다양한 가능성이 있습니다. 오렌지만 구매하기로 선택할 수 있지만 창고에 10개의 봉지만 있고 수익은 INR 1000이 됩니다. 마찬가지로 사과만 구매하여 INR 1500을 수익으로 만들기로 선택할 수 있습니다. 두 가지를 조합하여 구입할 수도 있습니다.

이러한 문제를 선형 계획법 문제라고 하며 자세히 설명하겠습니다. 시작하자:

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

선형 계획법은 선형 함수를 사용하여 복잡한 관계를 나타내는 방법입니다. 선형 계획법의 목표는 이러한 기능에 가장 적합한 솔루션을 찾는 것입니다. 두 점 사이의 실제 관계는 매우 복잡할 수 있지만 선형 계획법을 사용하여 단순하게 나타낼 수 있습니다. 선형 계획법은 많은 산업 분야에서 응용 프로그램을 찾습니다.

선형 계획법의 기초

다음은 선형 계획법의 몇 가지 기본 용어입니다.

강제

의사결정 변수의 제한(또는 제한)을 제약이라고 합니다. 대부분의 시간 제약은 문제를 해결하기 위한 리소스에 대한 제한 사항입니다.

결정 변수

이러한 변수는 출력을 정의합니다. 결과는 이러한 변수에 따라 달라지므로 '결정 변수'라고 합니다.

비음성 제한

선형 계획법 문제의 결정 변수는 음수가 아닌 값만 가질 수 있습니다. 이는 결정 변수의 값이 0보다 크거나 같을 수 있음을 의미합니다.

목적 함수

목적 함수는 결정을 내리는 목적입니다. 간단히 말해서 선형 계획법 문제의 최종 결과입니다. 예를 들어, 주어진 자원 세트로 만들 수 있는 최대 이익을 찾을 때 최대 이익은 목적 함수입니다.

선형 계획법 문제 공식화

선형 계획법을 공식화하여 실생활에 적용하는 방법을 알아야 합니다. 당신이 장난감 제조업체이고 A와 B의 두 가지 장난감만 생산한다고 가정합니다. 대략적으로 말하면 장난감을 제조하는 데 두 개의 자원 X와 Y가 필요합니다. 다음은 장난감의 요구 사항입니다.

• 장난감 A 1단위는 X 자원 1단위와 Y 자원 3단위가 필요합니다.

• 장난감 B 1단위에는 X 자원 1단위와 Y 자원 2단위가 필요합니다.

X 자원 5단위와 Y 자원 12단위가 있습니다. 이 장난감 판매에 대한 이윤은 다음과 같습니다.

• 장난감 A의 판매 단위당 INR 6
• 장난감 B의 판매 단위당 INR 5

최대 이익을 얻으려면 각 장난감을 몇 개나 생산하시겠습니까?

해결책

선형 계획법 문제를 방정식으로 표현해 보겠습니다.

Z = 6a + 5b

여기서 z는 총 이익, 장난감 A 단위의 총 수, b는 B 단위까지의 총 수를 나타냅니다. 우리의 목표는 Z(이익)의 가치를 최대화하는 것입니다.

이제 회사에서 이러한 장난감을 가능한 한 많이 생산하기를 원하지만 리소스가 제한적입니다. 우리 자원의 한계는 이 문제의 제약입니다. 우리는 총

a + b 5

이제 장난감 A와 B의 모든 단위에는 각각 3단위와 2단위의 자원 Y가 필요합니다. 그리고 우리는 자원 Y의 총 12단위만 가지고 있으므로 수학적으로는 다음과 같습니다.

3a + 2b 12

장난감 A의 단위 값은 정수로만 가능하다는 것을 기억하십시오. 이것은 또한 ->0 및 b<-0의 제약 조건이 있음을 의미합니다.

이제 적절한 선형 계획법 문제가 있습니다. 이 예제를 따르면 다른 선형 계획법 문제를 공식화할 수 있습니다. 이 예제는 매우 간단했지만 LP 문제는 매우 복잡해질 수 있습니다.

읽기: 선형 계획법 프로젝트 아이디어 및 주제

선형 계획법 문제를 공식화하는 단계

선형 계획법 문제를 공식화하려면 다음 단계를 따르세요.

• 결정 변수 찾기
• 목적 함수 찾기
• 제약 조건 식별
• 비음성 제한을 기억하십시오

문제가 위의 기준을 충족하면 선형 계획법 문제입니다. 문제 유형을 식별할 때 이 기준을 염두에 두는 것이 가장 좋습니다.

R로 선형 계획법 문제 풀기

R을 사용하는 경우 선형 계획법 문제를 해결하는 것이 훨씬 간단해집니다. R에는 이러한 문제를 해결하기 위해 특별히 설계된 다양한 기능과 함께 제공되는 lpsolve 패키지가 있기 때문입니다. 데이터 과학자로서 LP 문제를 해결하기 위해 R을 매우 자주 사용할 가능성이 높습니다. 그렇기 때문에 구현을 더 잘 이해할 수 있도록 두 가지 고유한 예를 공유했습니다.

예시

기본적인 문제부터 시작하겠습니다. 조직에 판매 가격이 INR 25 및 INR 20인 두 개의 제품이 있으며 각각 제품 A와 B라고 합니다. 매일 그들은 이러한 제품을 생산하는 데 1800단위의 자원을 가지고 있습니다. 제품 A에는 20개의 자원 단위가 필요하고 B에는 12개의 자원 단위가 필요합니다. 이 두 제품의 생산 시간은 4분이며 조직은 매일 총 8시간의 근무 시간을 받습니다. 문제는 기업의 이윤을 극대화하기 위해 이들 제품 각각의 생산량은 얼마가 되어야 하는가이다.

해결책:

목적 함수를 정의하여 이 문제를 해결하기 시작합니다.

최대(판매) = 최대( 25 y 1 + 20 y 2 )

여기서 25와 20은 각각 제품 A와 B의 가격이고, y1은 제품 A의 총 생산 단위이고, y2는 생산된 제품 B의 총 단위입니다. 우리의 결정 변수는 y1과 y2입니다.

이제 문제에 대한 제약 조건을 설정합니다.

리소스 제약:

20 살 1 살 + 12 살 2 살 1800

시간 제한:

4 년 1 + 4 년 2 8*60

우리는 최대의 이익을 얻기 위해 제조해야 하는 정확한 제품 수를 찾는 것을 목표로 합니다.

R을 사용하여 문제 해결:

lpsolve를 사용하여 이 LP 문제를 해결하고 목적 함수를 설정하는 것으로 시작합니다.

> 요구(lpSolve)

필요한 패키지 로드: lpSolve

> 목표.in <- c(25, 20)

> 목적.in

[1] 25 20

그런 다음 제약 조건에 대한 행렬을 작성합니다.

> const <- 행렬(c(20, 12, 4, 4), nrow=2, byrow=TRUE)

> 상수

[,1] [,2]

[1,] 20 12

[2,] 4 4

> time_constraints <- (8*60)

> 리소스 제약 조건 <- 1800

> time_constraints

[1] 480

> 리소스 제약 조건

[1] 1800

이제 이미 정의된 방정식을 만들어 보겠습니다.

> rhs <- c(resource_constraints, time_constraints)

> RH

[1] 1800 480

> 방향 <- c(“<=”, “<=”)

> 방향

[1] “<=” “<=”

필요한 모든 정보가 추가되면 최적의 답을 찾기 시작할 수 있습니다. 패키지 구문은 다음과 같습니다.

lp(방향, 목표, const.mat, const.dir, const.rhs)

> 최적 <- lp(방향="최대", objective.in, const, 방향, rhs)

> 최적

성공: 목적 함수는 2625입니다.

> 요약(최적)

길이 클래스 모드

방향 1 -없음- 숫자

x.count 1 -없음- 숫자

목표 2 -없음- 숫자

const.count 1 -없음- 숫자

제약 조건 8 -없음- 숫자

int.count 1 -없음- 숫자

int.vec 1 -없음- 숫자

bin.count 1 -없음- 숫자

binary.vec 1 -없음- 숫자

num.bin.solns 1 -없음- 숫자

객체 1 -없음- 숫자

솔루션 2 -없음- 숫자

사전 해결 1 -없음- 숫자

compute.sens 1 -없음- 숫자

sens.coef.from 1 -없음- 숫자

sens.coef.to 1 -없음- 숫자

이중 1 -없음- 숫자

duals.from 1 -없음- 숫자

duals.to 1 -없음- 숫자

척도 1 -없음- 숫자

use.dense 1 -없음- 숫자

Dense.col 1 -없음- 숫자

Dense.val 1 -없음- 숫자

Dense.const.nrow 1 -없음- 숫자

Dense.ctr 1 -없음- 숫자

use.rw 1 -없음- 숫자

tmp 1 -없음- 문자

상태 1 -없음- 숫자

위의 코드를 실행한 후 문제에 대해 원하는 솔루션을 얻을 수 있습니다.

y1 및 y2에 대한 최적 값:

y1과 y2는 우리가 생산해야 하는 제품 A와 제품 B의 단위임을 기억하십시오.

> 최적의 솔루션

[1] 45 75

최적의 판매 수치:

얻은 y1 및 y2 값으로 생성할 수 있는 최대 이익은 다음과 같습니다.

> 최적 $ 개체

[1] 2625

더 읽어보기: 기계 학습을 위한 선형 대수학

선형 계획법의 사용

앞서 언급했듯이 선형 계획법은 많은 산업 분야에서 응용 프로그램을 찾습니다. 다음은 우리가 사용하는 몇 가지 영역입니다.

• 배달 서비스의 인기가 높아짐에 따라 선형 프로그래밍은 최적의 경로를 찾는 가장 선호되는 방법 중 하나가 되었습니다. Ola 또는 Uber를 이용할 때 소프트웨어는 선형 프로그래밍을 사용하여 최적의 경로를 찾습니다. Amazon 및 FedEx와 같은 배송 회사도 이를 사용하여 배달원을 위한 최적의 경로를 결정합니다. 그들은 배달 시간과 비용을 줄이는 데 중점을 둡니다.
• 기계 학습의 지도 학습은 선형 프로그래밍의 기본 개념에 대해 작동합니다. 지도 학습에서는 제공된 입력 데이터에 따라 출력을 예측하기 위한 최적의 수학적 모델을 찾아야 합니다.
• 소매 부문은 선반 공간을 최적화하기 위해 선형 계획법을 사용합니다. 사용할 수 있는 브랜드와 제품이 너무 많기 때문에 매장 내 어디에 둘지 결정하는 것은 매우 엄격한 작업입니다. 매장에 제품을 배치하면 매출에 큰 영향을 미칠 수 있습니다. Big Bazaar, Reliance, Walmart 등과 같은 주요 소매 체인은 제품 배치를 결정하기 위해 선형 프로그래밍을 사용합니다. 그들은 최대의 이익을 낼 수 있는 최상의 제품 배치를 보장하면서 소비자의 관심을 염두에 두어야 합니다.
• 기업은 공급망을 개선하기 위해 선형 계획법을 사용합니다. 공급망의 효율성은 선택한 경로, 타이밍 등과 같은 많은 요소에 따라 달라집니다. 선형 프로그래밍을 사용하여 효율성을 최적화하기 위해 최적의 경로, 타이밍 및 기타 리소스 할당을 찾을 수 있습니다.

선형 계획법 및 데이터 과학에 대해 자세히 알아보기

선형 프로그래밍은 데이터 과학의 가장 중요한 개념 중 하나입니다. 또한 능숙한 데이터 과학자가 되기 위해 알아야 할 기본 주제이기도 합니다. 우리가 논의한 바와 같이 이 개념에 대한 많은 응용 프로그램이 있으며 일상 생활에서 사용 사례를 찾을 수 있습니다.

블로그로 이동하여 데이터 과학 및 관련 개념에 대해 자세히 알아볼 수 있습니다. 더 많은 것을 배울 수 있는 귀중한 자료가 많이 있습니다. 다음은 추가 읽을 내용입니다.

• 데이터 과학자가 되어야 하는 가장 큰 이유
• 모든 데이터 과학자가 알아야 할 알고리즘
• 데이터 과학자가 되는 방법

반면에 데이터 과학 과정을 통해 업계 전문가에게 배울 수 있습니다. 비디오, 퀴즈 및 프로젝트를 통해 대화식으로 배우게 됩니다. 과정을 수강하면 전문 데이터 과학자가 되는 데 필요한 기술을 배우는 데 도움이 됩니다. 일하는 전문가를 위해 만들어졌으며 10개 이상의 사례 연구 및 프로젝트, 실용적인 실습 워크샵, 업계 전문가와의 멘토링, 업계 멘토와 1:1, 400시간 이상을 제공하는 IIIT-B & upGrad의 데이터 과학 PG 디플로마를 확인하십시오. 최고의 기업과의 학습 및 취업 지원.