할당 문제는 선형 프로그램의 고전적인 문제입니다. 예를 들어, 다가오는 교대 근무 (제조 공장에서) 동안 제조해야 할 작업이 n 개 있고 이러한 작업을 생산할 기계가 m 개있는 경우 최적의 방식으로 작업을 기계에 할당하려고합니다. 여기에서 발생하는 제조 비용을 줄이고 싶을 수 있으므로 비용 최적의 생산 계획을 찾고 싶습니다. 이 예에서 제약은 각 기계가 다가오는 근무 시간 동안 하나의 작업 만 수행 할 수 있다는 것입니다. 모든 작업을 예약해야합니다 (예 : 기계에 할당).

문제는 수학적 모델에서 설명 할 수 있습니다. 아래는 3 개의 작업과 3 개의 기계가있는 경우에 대해 설명합니다. 기계 1에서 작업 1을 생산하는 비용은 기계 2에서 생산할 때 USD 2이지만 기계 2에서 생산할 때 2 USD의 비용이 듭니다. 작업 2는 기계 1에서 2 USD, 기계 2에서 3 USD입니다. 작업 3은 기계 1에서 5 USD, 기계 2에서 1 USD입니다. 머신 3은 각각 USD 2에 대해 작업 1을 수행하고 USD 3에 대해 작업 2와 3을 수행 할 수 있습니다.

이에 대한 수학적 모델은 다음과 같습니다.

선형 프로그래밍 (연속 및 정수 문제 용)을위한 패키지 인 R의 lpSolve 패키지를 사용하여이 문제를 모델링하고 해결할 수 있습니다. lp.assign 함수는 다음 작업을 수행 할 수 있습니다.

library(lpSolve)

# prepare the cost matrix
cost.mat <- rbind(c(1,2,3),
                     c(2,3,3),
                     c(5,1,3))

# model and solve with lp.assign
solution <- lp.assign(cost.mat=cost.mat,
                      direction="min")

lp.assign은 특히 할당 문제를 해결하기위한 기능입니다. 정의에 의한 할당 문제는 모든 의사 결정 변수가 정수 변수 인 문제입니다. 그러므로 우리는 결정 변수가 정수 변수로 간주되어야한다고 lp.assign에 특별히 말할 필요가 없습니다.

다가오는 근무 기간 동안 직면해야하는 최소 비용을 살펴 보겠습니다.

solution

## Success: the objective function is 5

다가오는 교대를위한 최소 비용 생산 계획을 살펴 보겠습니다.

solution$solution

##      [,1] [,2] [,3]
## [1,]    1    0    0
## [2,]    0    0    1
## [3,]    0    1    0

운송 문제는 또 다른 고전적인 문제입니다. R에서 해결하는 것을 볼 수 있습니다. 여기 : lp.transport를 사용하여 lpSolve로 Bronson의 전송 문제 해결.

Linnart Felkl

최적화 및 시뮬레이션을 전문으로하는 산업 엔지니어 (R, Python, SQL, VBA)