산업공학개론 제 9 장선형계획법
선형계획모형 () 선형계획모형 목적함수와제약식이모두선형으로수식화될수있는경우 일정한제약조건하에서목적하고자하는값을최대화 ( 최소화 ) 하고자하는수리적방법 선형계획모형의예제 제품배합문제 한정된자원을이용하여최대이익을내는제품배합을결정 수송문제 여러공급원에서여러목적지로최소비용으로제품수송방법결정 배정문제 여러작업을여러기계에게최소작업비용으로작업할당
선형계획모형 () 선형계획문제의특징 [] 목적함수와제약조건들이변수의선형관계로표현된다. 개의목적함수와다수의제약식으로구성 목적함수는최대화혹은최소화가목표 cf) 차계획법, 비선형계획법, 동적계획법... [] 각제약조건들은등식 () 혹은부등식 (, ) 으로표현된다. [] 모든선형계획문제의변수들은음수가될수없다. 음수인경우는적절한변형을통해양수화시킴 제약공간상의모든실수값을가질수있다. cf) 정수계획법
Ref) 기타모형 차계획법 : 목적함수가 차식, 제약식은 차식인문제 비선형계획법 [] 목적함수나제약식이 차식이아닌함수 ( 비선형함수 ) 로표시되는수리계획법 [] 현실의비선형성 선형계획법 ( 민감도분석이용하여보완 ) [] 선형계획의 Simple method( 단체법 ) 과같은효율적인해가존재하지않는다. [] Solution : 편미분, 라그랑지승수법, 쿤 - 터커정리 정수계획법 [] (IP ; Integer Programming) : 의사결정변수가정수의값만을갖는수리계획법 [] 정수계획법의모형화는변수가정수이어야한다는조건만추가하면선 형계획법과같다.
[ 예 ] 제품배합문제의기하학적접근 A,B 두상품을생산하는데상품 A 는개당 원의이익이나고, B 는개당 원의이익이발생한다. 상품 A 를생산하는데 9 개의재료와 시간동안기계를사용해야하며, B 는 개의재료와 시간의기계를사용해야한다. 이때재료는총 00 개를사용할수있으며, 기계가동시간은최대 00 시간이라고한다. 또상품 A 는최소 개이상을생산해야만한다고한다. 이때최대의이익을산출해내는상품 A 와 B 의생산량을결정하라. 결정변수 : 제품 A 의생산량 > 제품 B 의생산량 > 목적함수 제약식 Ma s. t. 9 00 00 0 이익의최대화기계가동시간제약재료사용량제약 A의최소생산량제약비음인해만을구함
[ 예 ] 제품배합문제의기하학적접근 - ( 계속 ) Ma s. t. 9 00 00 0 0 0 9 00 가능해공간 00 최대화 0 00/ 00/ Maimize
[ 예 ] 제품배합문제의기하학적접근 - ( 계속 ) Ma s. t. 9 00 00 0 0 0 가능해 : 제약식을모두만족하는해 비가능해 : 제약식을만족하지못하는해 최적해 : 목적함수를최적으로하는해 기저해 : 기하학적의미는꼭지점 (Verte) 최적해, 9 00 가능해공간 00 최대화 0 00/ 00/ Maimize
제품배합문제의기하학적고찰 최적해는제약공간의 Verte 중에서얻을수있다!! 최대화 최적해 제약식 0 제약식 목적함수식 8
[ 예 ] 개제품의배합문제 A,B,C 세상품을생산하는데상품 A 의 단위는압연시간이. 분, 조립공정에.0 분이필요하다. 이익은 00 원이발생한다. 상품 B 의 단위는압연시간이.0 분, 용접공정에. 분이필요하고, 이익은 00 원이발생한다. 상품 C 의 단위는.0 분의압연시간과. 분의용접시간,. 분의조립시간이필요하고, 00 원의이익이발생한다. 압연공정의생산시간은일주일에,00 분이고, 용접공정은일주일에 00 분, 조립공정은일주일에,00 분이가동될수있다. 최대의이익을발생시킬수있는제품 A, B, C 의생산량은? Maimize s. t.. 0.0.0,.0. 0.0, 00 0 00.0.. 00 00 00 00 이익의최대화압연시간제약용접시간제약조립시간제약비음인해만을구함 9
선형계획모형 기하학적접근? 해가제약공간상의기저해 (Verte) 중에서얻어진다.,개이내의문제에서만가시적인풀이가능 차원이상의문제에적용이어렵다. 제약식의수가많아도해결이어렵다. 알고리즘적인해법이요구 > 단체법 (Simple Method) Dantzig 제약식의교점중에서최적해를탐색 0
[ 예 ] 기저해의탐색 Ma, 0 0 : 목적함수 제약식을등식화 제약식만을이용한연립방정식 Ma,,, 0 Slack var. 0 0 무수히많은해가존재 두개의변수값만으로연립방정식의해를찾는다면, 개의해가얻어짐 기저변수기저해 (,,, ) (, ) (, ) (, ) (, ) (, ) (, ) (/, 8/, 0, 0) (, 0, -8, 0) (, 0, 0, ) (0,,, 0) (0,, 0, -0) (0, 0,, 0) BFS non-bfs BFS BFS non-bfs BFS 기저비가능해 (non-bfs) 기저가능해 (BFS) 0
기저해 (basic solution) : 제약식의개수 ( 차수 ) 만큼의기저변수로표현되는해 기저가능해 (BFS: Basic Feasible Solution) : 양수로만이루어진기저해 기저비가능해 (non-bfs) : 음수가포함된기저해 최적해 : 목적함수를최대화하는가능해 목적식반영 Ma 기저변수 기저해 (,,, ) 목적식의값 (, ) (/,8/,0,0) 00/ (, ) (, 0, -8, 0) 0 (, ) (, 0, 0, ) (, ) (0,,, 0) 0 (, ) (0,, 0, -0) 0 (, ) (0, 0,, 0) 0 기저가능해 기저비가능해 최적해 > 비가능해는탐색하지않고, 가능해내에서만탐색을하되, 목적함수값을꾸준히증가시킬수있도록하는방법이필요.
단체법 (Simple Method) 단체법 ( 單體法 ) 차연립방정식이론을바탕으로함 행렬연산 : 가우스 - 조단소거법 이해가쉽고실용성도높다. 가능해집합의 Verte 중하나를최적해로찾는다. 초기기저가능해 > 해의개선 > 최적해 단체법풀이과정 () 문제를계산형으로변환 () 최적여부확인 목적식의계수가모두음이면최적상태 () 기준열과기준행을중심으로 Pivoting 목적식의계수중절대값이제일큰열을기준열 ( 제약식의상수값 )/( 제약식의기준열계수 ) 가양수이면서최소인제약식을기준행 () 개선된해와목적값도출 제약식의상수값으로표현되는기저해 개선된해 목적식의상수값 개선된목적값 Yes No 기저해 최적해, 목적값 최적값
단체법풀이과정 선형계획모형 Ma s. t. 9 0, 00 00 0 최적해도출 Yes Pivoting 계산형으로변환최적여부확인 No 진입변수선택탈락변수선택기저변경 (pivoting) 개선된해 / 목적값도출 z 9,,, 0 9 0 00 00 - 목적식의계수가모두음이면최적해 eg),이므로비최적임. 기저해 (0,0,00,00), 목적값 0, 기저변수, - 진입변수 : 추가될기저변수 - 목적식의계수중에서절대값이제일큰계수의변수를선택 eg), 중에서 의변수인 를진입변수로선택 - 탈락변수 : 삭제될기저변수 - 각제약식에서 ( 상수항 )/( 진입변수의계수 ) 가최소인행의기저변수를탈락변수로선택 eg)00/, 00/ 중더작은첫번째제약식의기저변수인 를탈락변수로선택 - 기저변경 : 탈락되는행의진입변수를중심으로 pivoting 을함. - 기저변수중에서탈락변수는빠지고, 진입변수가새롭게추가. eg) 탈락되는첫번째제약식의진입변수 를중심으로 pivoting 기저변수가,, 로변경 - 개선된해 / 목적값구한후에, 다시최적해확인!!!
가우스 - 조단소거법 예제 연립방정식을행렬 (A b) 로표현하여, 선형결합을통하여 (I b ) 로변형한다. 해 b 0 - - - - ()() () ()-() () - - 0 - - ()-() () - - 0 - - - 0 0 0 0 ()/ () - - 0 - - ()*() () ()*() () 0 0 0 0 ()-*() () 0 0-0 0 0 0 0 0 0 0
*** [ 예 ] 단체법풀이 Maimize 0, 0 8 () 계산형으로변형 정규형 0 0 () 최적해여부확인 : 목적식계수가음을포함하므로아님. 초기해 (0, 0, 0, 0,, 0, 0) 목적함수값 z0 표준형 최대의목적함수계수 () 를갖는 열선택. 초기기저해 z 8 0 0, 최소의비율을갖는 행선택. 행 열을기준으로 pivot을실시 0 0 0 / 0/ 0/ 0 9 0, z 8 0 () 를기준으로 Pivoting ()-()*/ () ()-()/ () ()/ () ()-()*/ () () 개선된해도출개선된해 (0, 0, 0,, 8, 0, 0) 목적함수값 z goto () 최적해여부확인 : 목적식계수가양이남아있으므로최적해아님.
z 0 8 9 z 0 0 9 9 행 열기준으로목적함수의모든계수값이 ( 음 ) 이므로현재의해가최적해가된다. 최대의목적함수계수 (9/) 를갖는 열선택. 최소의비율을갖는 행선택. 행 열을기준으로 pivot 을실시 0, 0 0, 0 기준으로 Pivoting 최적해 *(0, 0, 0,, 0, 0, 0) 목적함수값 z*9 개선된해 (0, 0, 0,, 8, 0, 0) 목적함수값 z 탐구 ) 탈락변수선택시, 최소의비율선택이유? 가능해유지 ( 우변상수가음이되면비가능해가됨 ) 탐구 ) Pivoting 의의미? 또다른 Verte( 기저해 ) 를탐색탐구 ) 진입변수선택시, 최대의목적함수계수이유? 빠르게해를개선하기위하여 ()-()*9/ () ()// () ()-()/ () ()-()*/ ()
[ 예 ] 단체법풀이 - 단체표사용 - 단체법을표로압축 - 계산형문제의계수만추출 - 프로그램화하기용이 Maimize 0, 8 0 0 0 z 0, 8 0 0 0 0 단체표 z - 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0-9/ / / 0 0 -/ 0-0 / / / 0 -/ 0 8 0 / / / 0 / 0 0 / / / 0 0 -/ 0-0 -/ -/ 0-9/ -/ 0-9 0 / / 0 / -/ 0 0 0 0 / / -/ / 0 0 0 -/ -/ 0 -/ / 0 제 열의목적함수계수가 로최대. 진입변수 가된다. min{ /, 0/, 0/ } 0/. 최소의비율을갖는 행을기준열로 Pivoting 최대의목적함수계수는 9/. 따라서진입변수 이된다. min{ 8/(/), /(/), 0/(/) } 8/(/) 0. 최소의비율을갖는 행을기준열로 Pivoting 목적함수의모든계수값이 ( 음 ) 이므로현재의해가최적해가된다. 8
0, 0 0 0 8 Minimize [ 예 ] 단체법풀이 ( 최소화문제 ) 8 Maimize z 0 8 9 0, 0 0 0 0, 0 0 0 () 계산형으로변형 () 최적해여부확인 : 목적식계수가양을포함하지않음. 이미최적!!! 최적해 (0,0,0,0,,0,0) 목적함수값 z0
0, 0 0 0 8 Minimize 8 Maimize z 0 8 () 계산형으로변형 () 최적해여부확인 : 목적식계수가양을포함하므로최적해가아님. 0 0, 0 0 0 0, 0 0 0 z - - - -8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - -/ -/ -/ 0 0 -/ 0-0 / / / 0 -/ 0 8 0 / / / 0 / 0 0 / / / 0 0 -/ 0 목적함수의모든계수값이 ( 음 ) 이므로최적!!! 단체표
[ 예 ] 단체법연습 () () Ma Min, 0 0 Ma - -, 0 0 (p.0 의예제 ) 기저비가능해기저가능해 0 () Ma, 0 0 () Min Ma -, 0 0
() Ma, 0 0,,, 0 0 기저가능해 () Ma -, 0 0 0 () Ma, 0 0
대표적선형계획법문제들 수송문제 (Transportation Problem) 생산량 m개의생산지로부터 n개의수요지로수요량을만족시키면서, 최소의비용으로전달하는문제 m n Minimize c i i 생산지 s s s m.... m 단위당수송비용 : c c mn 수요지.... n d d d n 수요량 Minimize c i m n i... m... n i i i i c 0, n 0, m s d i, i,......, i, i......... c n mn m mn mn d,,..., s s d,,..., mn m n n m
[ 예 ] 수송문제 A 건설회사에서 곳의야산으로부터모래를운반하여 곳의아파트부지에공급한다. 모래의운반과관련한비용및생산량과수요량이다음의행렬에정리되어있다. 최소의운반비용을얻을수있는수송경로를구하여라. 야산 아파트부지 d d d d 공급량 s s 0 s 8 9 0 수요량 합 : 단위: 00 만원/ 톤 Minimize m m n i i n i i i c i s s 0, i, i i,, i,,...,,,..., n m Minimize 8 i 0, i, 9 0
[ 예 ] 수송문제 환에의한해법 Step ) 초기해를하나찾는다.( 최소가법이용 ) Step ) 초기해를개선시킬수있는수송비용의음환 (negative cycle) 을찾는다. Step ) 음환을찾을수없으면최적이다. ) 최소가법을이용하여찾은초기해 수요지공급지 s s s 수요량 d 0 d d d 공급량 8 9 0 총합 : cell c i i 단위당수송비용 결정변수값 ( 수송량 ) 총비용 0 8 9 기저변수 :,,,,, ( 양수 ) 비기저변수 :,,,,,, (zero) 기저해 : (,0,0,0, 0,,0,0,,,,) cf. 기저변수의개수 mn- - 다른기저해 (Verte) 를찾는방법? zero 인비기저변수중하나를양수로증가시키고 ( 진입변수 ), 기저해중하나를 zero 으로감소시킨다 ( 탈락변수 ). - 개선될지예상하는방법? 단위당증가비용과단위당감소비용을비교하여, 총비용이감소하도록기저해를변경시킨다. 음환 (negative cycle) 을찾아서기저를변경한다.
[ 예 ] 수송문제 환에의한해법 ( 계속 ) ) 음환 (negative cycle) 을찾는다. 수요지공급지 s s s 수요량 - 환 (cycle) : 비기저셀 (cell) 에서출발하여기저셀들을연결하는최소고리. - 모든비기저셀 (cell) 에대하여각음환의비용변화량을구한다. d - 0 d d d 공급량 8 9-0 총합 : 환 (cycle) ( ) ( ) ( ) ( ) ( ) ( ) 환의비용변화량 (cost) c 8< 0 c i ( 부호) ( 셀의수송비) c c c c c < 0 9 > 0 8 0 > 0 0 8< 0 0 8 9 0 최소 - 음환 : 비용변화량이음 (negative) 인환. 해의개선가능성이존재한다는의미. 음환이존재하지않으면최적해!!! ) 해의개선 음환 - 환의비용변화량이최소인환을개선. - 환에서음수가되지않는범위내에서그비기저셀 ( 진입변수 ) 의값을최대한증가시킨다. e.g. 최소비용음환인 값을 만큼증가 (,,, ) (0,,,) (,,,0) 진입기저해 : (,,0,0, 0,,0,0,,0,,) 탈락 수요지공급지 s s s 수요량 d 8 d 0 총비용 0 9 0 d 9 d 공급량 0 총합 :
수요지공급지 s s s 수요량 d d d d * 0 8 9 공급량 0 총합 : 기저해 : (,0,0,0, 0,,0,0,,,,) 목적값 : *0**8**9* c, c, c, c, c, c 0 수요지공급지 s s s d 8 d 0 수요량 총합 : d * 9 d 공급량 0 기저해 : (,,0,0, 0,,0,0,,0,,) 목적값 : **0***9*0 c, c, c, c, c, c 수요지공급지 s s s 수요량 d d d d * 0 8 9 공급량 0 총합 : 기저해 : (,,0,0, 0,0,,0,,0,,) 목적값 : *****9*0 c, c, c, c, c, c 수요지공급지 s s s 수요량 d d d d 0 8 9 공급량 0 총합 : 기저해 : (,,0,0, 0,0,,0,,0,,) 목적값 : *****9*00 최적해 c, c, c, c, c, c 모두양이므로최적!!
식단문제 여러가지영양분을지닌음식들로부터필수영양분을최소의음식값으로섭취하는문제 [ 예 ] 주위에서흔히볼수있는음식재료에포함된영양분이다음표에정리되어있다. 최소의비용으로식단을마련해보고자한다. 단하루의식단에서쌀은 0 포, 쇠고기는 근, 우유는 통, 계란은 개, 배추는 단을넘지않기로한다. 재료영양 쌀 ( 포 ) 쇠고기 ( 근 ) 우유 ( 통 ) 계란 ( 개 ) 배추 ( 단 ) 일필요량 열량 (Kcal) 0 080 00 00 단백질 (g). 9 8. 0 비타민 (I.U) 0 9 8 080 000 철분 (mg) 0. 0. 0.. 탄수화물 (g) 0 0 콜레스테롤 (u) 0 0 0 값 ( 원 ) 0 0 0 0 Minimize 0 0 080. 0. 0, 9 i 0, i,, 0 9 8 0., 0 00 8 080 0 0.,. 0. 00 0 000. 8
배정문제 (Assignment Problem) m 개의작업을 n 개의기계에각기하나씩최소의비용이되도록할당하는문제 공급량과수요량이각기 씩발생하는특별한경우의수송문제 기계.... m 작업 아니면 i 0 처리비용 : c m c mm.... m 만약기계i가작업 에할당되면 Minimize m m i i n i i i 0 c i,, or i, i, i i,,..., m,,..., m 9
배낭문제 (Knapsack Problem) 한정된배낭의용량에맞게각각의용량을가지는물건을최대의효용을얻도록채우는문제 대표적인정수계획법문제중의하나 [ 예 ] 갑돌이는등산을계획하고있는데, 가면서먹을음식을결정해야만한다. 배당에는총. kg까지만음식을담기로결정했다고한다. 각각의음식의무게와그음식을가져감으로써얻을수있는만족도가다음과같을때, 가장큰만족도를얻을수있는음식의조합을결정하시오. 물건 고기 쌀 라면 과일 빵 만족도 0 8 8 0 배낭의무게 무게 ( 0 0 g ) 8 Maimize 0 8 i 8 or 0, i 8 0 0
배정문제 :Machineco 대의기계를이용하여 개의작업을수행해야한다. 각기계는각각하나의작업에만할당될수있다. 각작업을마치는데기계마다 setup time 이필요하다. Machineco 사는 작업을완료하는데필요한총 setup time 을최소화하는배정을찾아야한다. Job Job Job Job Machine 8 Machine Machine 8 9 Machine 0
배정문제 :Machineco
배정문제 :Machineco Hungarian Method 단계 : 각행에서의최소값을각행요소에서빼서새비용행렬을만든다. 각열에서의최소값을각열요소에서빼서새비용행렬을만든다. 단계 : Optimality Test 비용행렬에서 0 을 cover 할수있는최소의수직 / 수평선을그린다. 기계 ( 작업 ) 의수와동일한수직 / 수평선이그려지면최적. 최적해는비용행렬의 0 요소중에존재한다. 그렇지않으면, 단계 으로 단계 : 단계 에서만들어진비용행렬중에서수직 / 수평선아래에있지않은 0 이아닌최소의요소를찾는다.(k 로둠 ) 수직 / 수평선아래에있지않은요소들에서 k 만큼뺀다. 수직 / 수평선과교차하는지점의요소에 k 만큼을더한다. 단계 로
배정문제 :Machineco
웹에서 LP 풀어볼수있는주소 http://people.hofstra.edu/stefan_waner/realworld/si mple.html