Linear Programming   선형계획법

(2022-08-16)

선형 계획


1. 선형 계획법 (Linear Programming, LP)경영과학의 가장 기본적인 모형
     - 단순하면서도 응용 분야가 넓은 이상적인 모형

  ㅇ 1949년경, 미 해군 소속인 George B. Dantzig이, 
     - 군사 자원의 최적 할당 문제를 다루면서,
     - 선형 계획법 문제를 정형화시키고,
     - 이의 해를 구하는 심플렉스 방법을 개발

  ㅇ 목적함수, 제약조건(등식 또는 부등식)이 결정 변수선형 함수로 표현되는 최적화 문제
     - 제약 조건 : 연립 일차 부등식 또는 연립 일차 방정식 (선형 제약 형태)
     - 목적함수  : 일차식 (선형 함수 형태)


2. 선형 계획 문제의 일반 형태

  ※ (구성  :  1개의 선형 목적 함수와 다수의 선형 제약 조건들로써 구성됨)

  ㅇ 목적 함수  :  
[# \text{min or max} \;\; z = c_1x+c_2x_2+\cdots+c_nx_n #]
ㅇ 제약 조건 :
[# \begin{array}{Llll} \mbox{subject to} & a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n & \lesseqqgtr & b_1 \\ & a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n & \lesseqqgtr & b_2 \\ & \qquad \vdots & & \vdots \\ & a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n & \lesseqqgtr & b_m \end{array} #]
ㅇ 양수 조건 :
[# x_1\geq0,\; x_2\geq0,\; \cdots\; ,\; x_n\geq0 #]
ㅇ (항목별 설명) - 목적 함수 : 최소화(min)/최대화(max)시키려는, 결정변수 벡터 {#\mathbf{x}#}의 선형 함수 - 제약 조건(식) : 결정변수 x가 만족해야 하는 연립 선형 방정식 (등식 또는 부등식 형태) - 양수 조건 : 결정변수 벡터 {#\mathbf{x}#}의 각 원소 xi는 음수가 될 수 없음 3. 선형 계획 문제의 해법심플렉스 해법, 내부점 해법 등 4. 선형 계획 문제의 적용 분야 및 例) ㅇ 적용 분야 : 교통망, 통신망, 제조업, 경제학, 경영학 등 ㅇ 적용 문제 : 운송 계획 문제, 생산 계획 문제, 일정 계획 문제, 영양 문제 등

최적화
   1. 최적 문제   2. 최적화 문제 구분   3. 최적화 문제 용어   4. 최적화 문제 표현   5. 변분법   6. 라그랑주 승수법   7. 비용 함수   8. 선형계획법   9. 최적화 알고리즘   10. 손실 함수  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"