(Microsoft PowerPoint - chapter_9sub.ppt [\310\243\310\257 \270\360\265\345])

Similar documents
최소비용흐름문제의선형계획모형 최소비용흐름문제는선형계획문제로표현할수있다. 예 4.1 의최소비용흐름문제는다음과같은선형계획문제가된다. min z = 5x 12 +4x 13 +7x 14 +2x x 34 +8x 35 +5x 45 sub.to x 12 +x 13 +x

FGB-P 학번수학과권혁준 2008 년 5 월 19 일 Lemma 1 p 를 C([0, 1]) 에속하는음수가되지않는함수라하자. 이때 y C 2 (0, 1) C([0, 1]) 가미분방정식 y (t) + p(t)y(t) = 0, t (0, 1), y(0)

완벽한개념정립 _ 행렬의참, 거짓 수학전문가 NAMU 선생 1. 행렬의참, 거짓개념정리 1. 교환법칙과관련한내용, 는항상성립하지만 는항상성립하지는않는다. < 참인명제 > (1),, (2) ( ) 인경우에는 가성립한다.,,, (3) 다음과같은관계식을만족하는두행렬 A,B에

비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2

1 경영학을 위한 수학 Final Exam 2015/12/12(토) 13:00-15:00 풀이과정을 모두 명시하시오. 정리를 사용할 경우 명시하시오. 1. (각 6점) 다음 적분을 구하시오 Z 1 4 Z 1 (x + 1) dx (a) 1 (x 1)4 dx 1 Solut

04 Çмú_±â¼ú±â»ç

제 9 장 일정계획 ( Scheduling ) 1

<B4EBC7D0BCF6C7D02DBBEFB0A2C7D4BCF62E687770>

Microsoft PowerPoint - LA_ch6_1 [호환 모드]

Vector Differential: 벡터 미분 Yonghee Lee October 17, 벡터미분의 표기 스칼라미분 벡터미분(Vector diffrential) 또는 행렬미분(Matrix differential)은 벡터와 행렬의 미분식에 대 한 표

PowerPoint Presentation

학습목차 2.1 다차원배열이란 차원배열의주소와값의참조

슬라이드 1

제 8 장 생산계획 (Production Planning) 1

OR MS와 응용-03장

제 3강 역함수의 미분과 로피탈의 정리

장연립방정식을풀기위한반복법 12.1 선형시스템 : Gauss-Seidel 12.2 비선형시스템 12.1 선형시스템 : Gauss-Seidel (1/10) 반복법은초기근을가정한후에더좋은근의값을추정하는체계적인절차를이용한다. G-S 방법은선형대수방정

Microsoft Word - SPSS_MDA_Ch6.doc

슬라이드 1

JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 ( ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각

프로그래밍개론및실습 2015 년 2 학기프로그래밍개론및실습과목으로본내용은강의교재인생능출판사, 두근두근 C 언어수업, 천인국지음을발췌수정하였음

Microsoft PowerPoint - ch07 - 포인터 pm0415


설계란 무엇인가?

½Ç°ú¸Ó¸®¸»¸ñÂ÷ÆDZÇ(1-5)¿Ï

제 2 교시 2019 학년도 3 월고 1 전국연합학력평가문제지수학영역 1 5 지선다형 1. 의값은? [2점] 일차방정식 의해는? [2 점 ] 두수, 의최대공약수는? [2 점 ] 일차함수 의그래프에서

목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2

<B1B9BEEE412E687770>


23

PowerPoint Presentation

소성해석

<30342DBCF6C3B3B8AEBDC3BCB33228C3D6C1BE292E687770>

Microsoft PowerPoint - chap06-1Array.ppt

PowerPoint 프레젠테이션

Microsoft PowerPoint - chap06-2pointer.ppt

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770>

(001~006)개념RPM3-2(부속)

Microsoft PowerPoint - MDA 2008Fall Ch2 Matrix.pptx

5장. 최적화

금오공대 컴퓨터공학전공 강의자료

<30325FBCF6C7D05FB9AEC7D7C1F62E687770>

Microsoft PowerPoint - chap04-연산자.pptx

(Microsoft PowerPoint - Ch19_NumAnalysis.ppt [\310\243\310\257 \270\360\265\345])

3. 다음은카르노맵의표이다. 논리식을간략화한것은? < 나 > 4. 다음카르노맵을간략화시킨결과는? < >

OCW_C언어 기초

7. 인실수 에대하여 log 의지표를 이라할때, 옳 은것을보기에서모두고르면? ( 단, 는 를넘지않는최대의정수이다.) 7 ) ㄱ. log ㄴ. log 의지표는 이다. ㄷ. log log 이면 은 자리의정수 이다. 10. 다음은어느인터넷사이트의지도상단에있는버튼의기능을설명한

¼Òâ¹Ý¹®Áý¿ø°í.hwp

텀블러514

Microsoft PowerPoint - e pptx

(Microsoft PowerPoint - Chapter_8.ppt [\310\243\310\257 \270\360\265\345])


<31302DB1E8BDC2B1C72E687770>

5장. JSP와 Servlet 프로그래밍을 위한 기본 문법(완성-0421).hwp

제 5강 리만적분

이 장에서 사용되는 MATLAB 명령어들은 비교적 복잡하므로 MATLAB 창에서 명령어를 직접 입력하지 않고 확장자가 m 인 text 파일을 작성하여 실행을 한다

설계란 무엇인가?

<4D F736F F F696E74202D2035BBF3C6F2C7FC5FBCF8BCF6B9B0C1FA2E BC8A3C8AF20B8F0B5E55D>

5Àå-1.hwp

고 학년도 9월고수학 1 전국연합학력평가영역문제지 1 1 제 2 교시 수학영역 5 지선다형 3. 두다항식, 에대하여 는? [ 점 ] 1. 의값은? ( 단, ) [ 점 ] 다항식 이 로인수분해될때, 의값은? ( 단,,

슬라이드 1

제 12강 함수수열의 평등수렴

02-급식 매뉴얼

윈도우즈프로그래밍(1)

작용소의 행렬표현과 그 응용

예제 1.1 ( 관계연산자 ) >> A=1:9, B=9-A A = B = >> tf = A>4 % 4 보다큰 A 의원소들을찾을경우 tf = >> tf = (A==B) % A

A Dynamic Grid Services Deployment Mechanism for On-Demand Resource Provisioning

R

행삭제 열삭제

Chap 6: Graphs

= ``...(2011), , (.)''

, ( ) 1) *.. I. (batch). (production planning). (downstream stage) (stockout).... (endangered). (utilization). *

금오공대 컴퓨터공학전공 강의자료

<4D F736F F D20B1B8C1B6BFAAC7D0325FB0ADC0C7C0DAB7E15F34C1D6C2F75F76332E646F63>

2013unihangulchar {45380} 2unihangulchar {54617}unihangulchar {44592} unihangulchar {49328}unihangulchar {50629}unihangulchar {51312}unihangulchar {51

PowerPoint Presentation

도형의닮음 1 강 - 닮은도형과닮음중심 사이버스쿨우프선생 닮음도형 : 일정한비율로확대또는축소하였을때닮음모양의도형 기호 : ABCD A'B'C'D' [ 예제 1 ] 그림에서와같이두닮은도형 ABCD 와 A'B'C'D' 에서대응점, 대

PowerPoint Template

수리영역 5. 서로다른두개의주사위를동시에던져서나온두눈의수의곱 이짝수일때, 나온두눈의수의합이 또는 일확률은? 5) 의전개식에서상수항이존재하도록하는모든자 연수 의값의합은? 7) 다음순서도에서인쇄되는 의값은? 6) 8. 어떤특산

Microsoft PowerPoint - C++ 5 .pptx

제 4 장수요와공급의탄력성

<342EBAAFBCF620B9D720B9D9C0CEB5F92E687770>

PowerPoint Presentation

Microsoft PowerPoint - chap03-변수와데이터형.pptx

Microsoft PowerPoint - C프로그래밍-chap03.ppt [호환 모드]

<INPUT DATA & RESULT / 전단벽 > NUM NAME tw Lw Hw 철근 위치 Pu Mu Vu RESULT (mm) (mm) (mm) 방향 개수 직경 간격 (kn) (kn-m)

PowerPoint 프레젠테이션

Microsoft PowerPoint - E제14장연습및예상문제_2012.pptx

Poison null byte Excuse the ads! We need some help to keep our site up. List 1 Conditions 2 Exploit plan 2.1 chunksize(p)!= prev_size (next_chunk(p) 3

HW5 Exercise 1 (60pts) M interpreter with a simple type system M. M. M.., M (simple type system). M, M. M., M.

chap x: G입력

Microsoft PowerPoint - 강의자료8_Chap9 [호환 모드]

PowerPoint Presentation

학습목표 함수프로시저, 서브프로시저의의미를안다. 매개변수전달방식을학습한다. 함수를이용한프로그래밍한다. 2

슬라이드 0

PowerPoint 프레젠테이션

Microsoft Word - LectureNote.doc

= Fisher, I. (1930), ``The Theory of Interest,'' Macmillan ,

PowerPoint 프레젠테이션

차례 어린이를 위한 영양 식생활 실천 가이드 1. 골고루 먹기 4 2. 똑똑하게 먹기 요리사 되어보기 건강한 몸 만들기 복습하기 32

Transcription:

산업공학개론 제 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