DataBaser.Net: 선형계획법

1 응용분야
2 예제1
3 예제2
4 참고자료

EXCEL 경영과학 (개정판)/강금식, 정우석/박영사 문제를 R로 풀어봤다.

1 응용분야 #

자원분배
- 제조: 제품생산 조합결정, 생산일정계획, 원료배합, 재고관리
- 마케팅: 판매조직관리(판매원 할당, 판매지역 선정 등), 광고 예산 할당 및 일정계획
- 재무: 자본예산계획수립, 운전자금관리, 투자의 포트폴리오 결정, 자금회전 분석
- 인사: 인력할당 및 배치, 임금 및 급여관리
- 대항행정: 교직원 할당, 연구실 및 강의실 공간분배, 운영자금의 분배 및 재분배
사업 및 일정계획: 재무관리계획, 인력계획, 공사진행계획, 배달 및 판매일정계획, 농작물재배계획
영양관리문제: 환자영양관리, 단체급식관리
수송문제: 상품수송 일정계획, 원유수송 일정계획, 군수물자 수송계획
할당문제: 경찰수사력할당, 인력할당, 컴퓨터터미널 할당

2 예제1 #

평화가구는 테이블과 의자를 생산하여 시중에 모두 판매하는 회사이다. 두 제품이 거치는 생산공정은 같다. 즉, 두 제품은 목수일을 통해 목재를 자리고, 못질을 한 후, 페인팅과 광택 공정을 거치고 마지막으로 검사 공정을 거친다. 각 테이블은 2시간의 목수일, 2시간의 페인팅 및 광택일, 0.1시간의 검사일을 필요로 하며, 각 의자는 5시간의 목수일, 1시간의 페인팅 및 광택일, 0.1시간의 검사일을 필요로한다. 현재 생산기간(예컨데, 일) 동안 목수 일을 하는데 50시간, 페인팅/광택 일을 하는데 22시간, 검사 일을 하는데는 1.3시간이 사용가능하다고한다. 테이블 하나를 팔면 6만원의 이익이 남고, 의자 하나를 팔면 5만원의 이릭이 남는다고 한다. 이익을 최대화하기 위해서는 테이블, 의자를 각각 얼마만큼 생산해야 하는가?

> library("lpSolve")
> # Set up problem: maximize
> # x1: 테이블, x2: 의자
> # 최대화: 6x1 + 5x2 
> # 제약조건: 2x1 + 5x2 <= 50
> # 제약조건: 2x1 + 1x2 <= 22
> # 제약조건: 0.1x1 + 0.1x2 <= 1.3
> f.obj <- c(6, 5)
> f.con <- matrix (c(2, 5, 2, 1, 0.1, 0.1), nrow=3, byrow=TRUE)
> f.dir <- c("<=", "<=", "<=")
> f.rhs <- c(50, 22, 1.3)
> #총이익
> lp ("max", f.obj, f.con, f.dir, f.rhs)
Success: the objective function is 74 
> #생산량
> lp ("max", f.obj, f.con, f.dir, f.rhs)$solution
[1] 9 4
> #쌍대이론
> lp ("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals
[1]  0  1 40  0  0

테이블 9개, 의자 3개를 생산했을 경우 최대이익은 74만원이다.

참고

lp ("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.from
lp ("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.to
lp ("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals
lp ("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.from
lp ("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.to
lp ("max", f.obj, f.con, f.dir, f.rhs, int.vec=1:3)
lp ("max", f.obj, f.con, f.dir, f.rhs, int.vec=1:3)$solution
lp ("max", f.obj, f.con, f.dir, f.rhs, int.vec=1:3, compute.sens=TRUE)$duals

* sens: 민감도, dual: 쌍대, solution: 해

[edit]

3 예제2 #

사료 A, B가 있다. 각각의 영양분은 1,2,3이 들어있다. A사료에는 1영양분이 0.2, 2영양분이 0.3이 들어있고, B사료에는 1영양분이 0.4, 2영양분이 0.1, 3영양분이 0.3만큼 들어있다. 각각의 영양분은 하루에 1은 30, 2는 50, 3은 20만큼 필요하다. A사료의 가격은 5,000원이고, B사료의 가격은 7천원이다. 사료 A, B의 최소 구입량과 구매가격을 구하라.

목적함수 Min Z = 5000x1 + 7000x2
제약조건
- 0.2x1 + 0.4x2 ≥ 30
- 0.3x1 + 0.1x2 ≥ 50
- 0.0x1 + 0.3x2 ≥ 20
비음조건 x1 ≥ 0 , x2 ≥ 0

> library("lpSolve")
> f.obj <- c(5000, 7000)
> f.con <- matrix(c(0.2, 0.4, 0.3, 0.1, 0, 0.3), nrow=3, byrow=TRUE)
> f.dir <- c(">=",">=",">=")
> f.rhs <- c(30, 50, 20)
> lp ("min", f.obj, f.con, f.dir, f.rhs)
Success: the objective function is 1188889 
> lp ("min", f.obj, f.con, f.dir, f.rhs)$solution
[1] 144.44444  66.66667
> lp ("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals
[1]     0.00 16666.67 17777.78     0.00     0.00
>

사료를 구입하는데 필요한 최적의 금액은 1188889원이고, A사료는 144.44444개, 66.66667개를 구입하면 된다.

[edit]