3주차 2차시 복습

[문건혜(경영)]

Linear Programming

: 목적의 달성도를 최대로 하는 가장 좋은 방법을 구하는 수학적 기법

 -> 경영자가 의사결정을 하는데 도움을 주기 위하여 개발된 문제해결 방법

▶ 수량의 최대화/최소화가 목적

▶추구하는 목적을 제한하는 제약조건(constraints) 포함

(순서)

① decision variables 결정

② 이를 토대로 objective function 구성

③ constraints 포함

④ mathematical statement 구성 - proportionality, additivity, divisibility을 필요조건으로 갖출 것 

A Simple Minimization Problem 

Ex) 생산 비용 최소화

	제품 양(갤런)
	A	B
A 수요	1	0
총생산량	1	1
가공시간	2	1

(mathematical statement)

  Min    2A + 3B

   subject to

         1A          ≥ 125

         1A + 1B ≥ 350 

         2A + 1B ≤ 600

               A, B ≥ 0    ->  non-negativity constraints 조건 필수

<feasible region>

constraints 토대로 feasible region을  구한다.

꼭짓점 ① (125, 350)

            ② (125, 225)

            ③ (250, 100)

feasible region 내의 optimal solution 찾아야 한다.

따라서, 

목적함수식을 2A + 3B = Z 로 두고 

B = -2/3S + Z/3 로 변환하여

기울기는 그대로 두고 절편을 최소화 하여 optimal solution을 구한다.

그림을 통해 ① 목적함수라인은 각자에 대해 서로 평행이다.

                    ② 생산비용의 최소를 가져오는 목적함수라인일수록 원점에서 가까워진다.

                        -> Z가 작아지면 B축 절편이 감소한다. 

                    ③ feasible region 내에서 가장 낮은 비용을 가져오는 목적함수라인 상의 점이 바로 

                         linear programming의 optimal solution이다. 

알 수 있다.

optimal solution은 

1A + 1B ≥ 350 

2A + 1B ≤ 600

이 만나는 곳에서 결정 된다.

A = 250

B = 100

2A + 3B = 800

최소비용은 800이다.

(정리)

1. 제약조건에 대한 실행가능 해 그래프를 그린다.

2. 모든 제약 조건을 동시에 만족시키는 해를 파악하여 실행가능 영역을 결정한다.

3. 특정 목적 함수 값을 가지는 의사결정 변수 값을 보여주는 목적함수 라인을 그린다.

4. 목적함수 라인이 더 적은 값을 가지도록 평행하게 움직인다.

5. 가장 적은 값을 가지는 목적함수 라인에서 최적해를 찾는다.

  (단, 최적해가 오직 하나만 존재하는 것은 아니다.)

6. 최적해는 실행가능 영역의 한 극점에서 발생한다. 

  (단, 꼭짓점에서만 발견되는 것은 아니며 꼭짓점이 아닌 곳에서 발견될 수도 있다.)

7. 가장 적은 값을 가지는 목적함수 라인 위의 어떠한 실행가능 해도 최적해가 된다.

<surplus bariable>

A 제품 생산량은 최소 125갤런만으로 가능하지만

optimal solution에 따르면 A 제품 생산량이 250갤런으로,

실제로는 A 제품의 생산량은 125갤런만큼 초과한다.

A 제품의 생산량 초과는 과잉생산을 야기한다. 

이러한 생산량의 초과를 surplus(잉여)라고 표현한다.

정확한 여유 변수를 확인하기 위해

부등식을 등식으로 변환하여 잉여변수 값을 구한다.

optimal solution(A=250/B=100) 대입하여 잉여변수를 구하면

값을 구할 수 있다.

MS60

MS60 사용시

cost을 minimum 시기키 위한 objective function을 입력하여 수기로 그래프를 그려 구하는 것 보다

훨씬 linear programming의 optimal solution을 빠르게 구할 수 있었습니다.

Special Cases

1) Alternative Optimal Solutions

   : optimal solution은 feasible solution 중에서 여러 꼭짓점에서 발생한다.

     최적 목적 함수 라인이 feasible region의 경계에 있는 constraints 라인과 일치하는 특별한 경우에는 복수의 최적해가 발생한다.

     이 경우 무수히 많은 해가 존재한다.

     max의 예를 응용해 봤을때

꼭짓점이 아닌 점에서도 Alternative Optimal Solutions가 존재함을 알 수 있다.

2) Infeasibility

    :  linear programming에서 모든 constraints(비음제약조건도 포함)을 만족하는 어떠한 해도 존재하지 않는 경우

      즉,  feasible region이 존재하지 않는다.

      Infeasibility는 objective function와는 관련이 없다. objective function의 계수를 바꾸더라도 실행불가능한 영역이 발생한다. 

     에러가 있는경우, 말도 안되는 의사결정인 경우, 복잡해서 답을 찾지 못하는 경우가 여기에 해당된다.

      max의 예를 응용해 봤을때

그래프 내에서 feasible region이 존재하지 않음을 알 수 있다.

3) Unbounded

    : max problem의 경우 제약 조건식에 위반됨 없이 해의 값이 무한히 증가하는 경우

    : min problem의 경우 모든 제약 조건식을 만족하면서 해의 값이 무한히 감소하는 경우

    => managerial utopia 

    unbounded는 objective function와 관련이 깊다. objective function를 수정한다면 optimal solution를 구할 수 있다. 

    unbounded는 대부분제약조건 생략하여 발생한다.

   실제 linear programming에서 unbounded가 발생한다는 것은 mathematical statement가 현실을 충분히 반영하지 못한 결과이다. 

※ garbage in garbage out

    : 쓰레기 넣으면 쓰레기 나온다.

   -> 의사결정 : 문제 정확히 define 해서 determine 해야한다.

데이터 분석의 가장 큰 효과는 "의사결정 프로세스의 최적화" 라고 생각합니다.  데이터 시대가 도래하면서 우리는 많은 정보속에서 살고 있습니다. 지니고 있는 데이터의 양과 질이 힘이고 무기인 시대이지만 데이터 자체는 무기화 되지 못하고, 뛰어난 알고리즘이 있다고 한들 잘못된 데이터를 입력한다면 잘못된 결정을 내립니다. 목표를 정하고 그에 맞게 분석할때 데이터의 가치가 생깁니다. 목적지향적인 통찰력과 상상력있는 온전한 인간만이 올바르게 데이터를 다룰 수 있습니다. 데이터의 목표를 정확히 define 할 때 인간의 능력은 빛을 바랄 것입니다. 

[문건혜(경영)]

중간시험 평가2