Linear Programming   선형계획법

(2020-04-02)

선형 계획

1. 선형계획법 (Linear Programming, LP)목적함수,제약조건(등식 또는 부등식)이 결정 변수선형 함수로 표현되는 최적화 문제
     - 제약 조건 : 연립 일차 방정식 또는 연립 일차 부등식
     - 목적함수  : 일차식

  ㅇ 경영과학의 가장 기본적인 모형
     - 단순하면서도 응용 분야가 넓은 이상적인 모형

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


2. 선형계획 문제의 일반 형태목적 함수 : 
[# \text{min or max} \; z = c_1x+c2x_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. 선형 계획 문제의 해법심플렉스 해법, 내부점 해법 등


[최적화] 1. 최적 문제 2. 최적화 문제 용어 3. 최적화 문제 구분 4. 변분법 5. 라그랑주 승수법 6. 비용 함수 7. 선형계획법
[극값]

 
        최근수정     요약목록     참고문헌