기말고사를 위하여 - 정수계획법

선형계획법 기억나지?

 

선형이 뭐야. 일차함수잖아. 

 

제약식도 일차함수고, 목적함수도 일자함수여서 계산하기가 쉽다고 했잖아.

 

우리 수능 수학 공부 좀 했으면 "특수한 케이스가 답이다" 라는 건 익숙할거고

 

그래서 제약식의 교점에서 답이 나올거라곤 알고 있고 . 

 

근데 이제 모든 교점에서 최적해라면 그건 말이 안 되잖아 값이 다 다를텐데

 

사실 그건 로컬최적해였던거지. 국지최적해라고 하는게 낫겠다 여튼 

 

그것들이 사실 전역최적해의 후보들이란거지 이러한 개념을 가지고 한번 들어가보자 

 

 

  정수계획법이 뭐야? 제약식에 "정수조건" 이 들어간 거 뿐이지

 

이거 제약식은 함수인데 그럼 연속적이란 소리고. 

 

정수조건이 포함되어 버리면 결국 제약식을 만족하는 범위 안에 존재하는 정수들을 전부 조사해보는 수 밖엔 답이 없다.

 

 

이걸 푸는 건 개쌩노가다 밖에 없어서 NP-Hard 문제인 것들이 많이 있다고 했어. (배낭 문제는 단순하지만 NP -Hard 문제로 밝혀짐 - > 다항시간에 푸는 알고리즘이 존재하지 않는다 -> 개씹노가다 밖에 답이 없다)

 

근데 언제까지고 개씹노가다만 할 순 없으니까 만들어낸게 절단평면법, 분지한계법 등이란거야 

 

그 중에서 분지한계법을 수업시간에 했고 (절단평면법은 분지한계법을 좀 더 일반화한 거라고 생각하면 됨)

 

분지한계법에 대해서 생각해보자 

 

분지한계법은 정수 하나를 0 혹은 1로 나눠서 케이스 분류하는거지

 

이때 변수들 목적함수 계수 / 제약식 계수 가 가장 큰 것 기준으로 내림차순으로 정렬해야하고 시작해야함 

 

max :  5x + 20y 

sub. to : 15x+ 10y < 10

 

이러면 시작을 20y + 5x 이렇게 놓고 시작해야한단 소리임 그냥 이게 편해 (책에 나옴)

 

그럼 5x+ 2y 를 max 하는게 목표니까 왼쪽 문자부터 1을 넣다가 제약식에 분수로 걸치는 변수가 나타날거임 

 

그걸 이제 1이랑 0 으로 나눠주면 됨 

 

이건 그냥 책이랑 ppt 열심히 읽읍시다. 이해했잖아 다들