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. 선형계획법
[극값]
  1.   기술공통
  2.   기초과학
        1. 과학
    1.   수학
          1. 수학
      1.   기초수학
      2.   집합,논리
      3.   해석학(미적분 등)
            1. 해석학
        1.   미분적분
              1. 미분적분학
          1.   함수
          2.   극한,연속,발산
          3.   미분
          4.   적분
          5.   직선,곡선,평면,곡면
          6.   최적화
                1. 최적 문제
                2. 최적화 문제 용어
                3. 최적화 문제 구분
                4. 변분법
                5. 라그랑주 승수법
                6. 비용 함수
                7. 선형계획법
            1.   극값
        2.   벡터해석학
        3.   미분방정식
      4.   대수학
      5.   확률/통계
      6.   수치해법
    2.   물리
    3.   화학
    4.   지구,천체 과학
    5.   생명과학
    6.   뇌과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
  8.   공학일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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