7장 노트정리, MS60 복습

안녕하세요 ^^ 2주차 수업을 듣고 복습해보았습니다 *Types of Integer Programming Models1) all-integer linear program (ILP)2)LP Relaxation -> 의사결정 변수에 정수라는 제한 없앤것3)mixed-integer linear program4)0-1 or binary integer linear program *프린트 예시 정리 <img src="https://t1.daumcdn.net/cfile/cafe/99C3444D5F5B018906" class="txc-image" width="1024" style="clear: none; float: none;" border="0" vspace="1" hspace="1" data-filename="예시1.jpg" exif="{}" actualwidth="1024" id="A_99C3444D5F5B018906F5C2"/> -의사결정변수 T , A  (2가지)-목적함수 10T+15A (이익최대화)-제약조건 (3가지)282T+400A<=2000   (예산)4T+40A<=140          (관리시간)T<=5                      (T의 최대 구매 개수) *LP Relaxation 방법으로 직접 구해보기 <img src="https://t1.daumcdn.net/cfile/cafe/99B4F0495F5B02A805" class="txc-image" width="1024" style="clear: none; float: none;" border="0" vspace="1" hspace="1" data-filename="예시2.jpg" exif="{}" actualwidth="1024" id="A_99B4F0495F5B02A805BC99"/> 제약조건의 식을 이용해  T 와 A를 구해보았습니다 40A=140-4T 식을 T=35-10A 로 간단하게 바꾼 다음,이 식을 200A=1000-141T 식의 T 자리에 대입한 결과 A는 3.252 , T는 2.479 라는 것을 알 수 있었습니다 따라서 10T+15A 식에 각각 T와 A 값을 대입하면 최대 73,574 달러의 이익을 얻을 수 있다는 것을 알 수 있습니다 *rounding 해보기 / Optimal Integer Solution 구하기 <img src="https://t1.daumcdn.net/cfile/cafe/999C2B4B5F5B04A807" class="txc-image" width="768" style="clear: none; float: none;" border="0" vspace="1" hspace="1" data-filename="예시3.jpg" exif="{}" actualwidth="768" id="A_999C2B4B5F5B04A8075D3C"/> 하지만 T와 A의 값이 소수 단위로 나온다고 해서 임의로 rounding 해서는 안됩니다실제로 정수값을 임의로 반올림했을 때의 결과는 제약조건에 맞지 않았습니다 ILP 방법으로 최적의 결과값을 구해보니 최대 70,000 달러의 이익을 얻을 수 있다는 것을 확인할 수 있었습니다 *MS60 프로그램 활용 1. LP Relaxation <img src="https://t1.daumcdn.net/cfile/cafe/99414E4E5F5B06860D" class="txc-image" width="703" style="clear: none; float: none;" border="0" vspace="1" hspace="1" data-filename="LP_1.png" exif="{}" actualwidth="703" id="A_99414E4E5F5B06860DF809"/> 의사결정변수 2개 , 제약조건개수 3개 , MAX 를 알맞게 입력합니다 <img src="https://t1.daumcdn.net/cfile/cafe/9985E6475F5B06D63B" class="txc-image" width="757" style="clear: none; float: none;" border="0" vspace="1" hspace="1" data-filename="LP_2.png" exif="{}" actualwidth="757" id="A_9985E6475F5B06D63B0BC9"/> 변수의 이름과 목적함수계수 , 제약조건을 알맞게 입력합니다 이 때 부등호는 '작거나 같다' 는 작다, '크거나 같다' 는 크다 라고 입력해도 무관하다고 합니다 <img src="https://t1.daumcdn.net/cfile/cafe/99B7B04D5F5B07510B" class="txc-image" width="940" style="clear: none; float: none;" border="0" vspace="1" hspace="1" data-filename="LP_3.png" exif="{}" actualwidth="940" id="A_99B7B04D5F5B07510B240C"/> 위에서 정리한 것과 같은 결과가 훨씬 간단하게 구해졌습니다 2. ILP <img src="https://t1.daumcdn.net/cfile/cafe/9995624F5F5B07953F" class="txc-image" width="858" style="clear: none; float: none;" border="0" vspace="1" hspace="1" data-filename="ILP_1.png" exif="{}" actualwidth="858" id="A_9995624F5F5B07953FEC26"/> 다음으로 ILP 방법을 적용해보았습니다 <img src="https://t1.daumcdn.net/cfile/cafe/9945D44E5F5B07CD06" class="txc-image" width="1024" style="clear: none; float: none;" border="0" vspace="1" hspace="1" data-filename="ILP_2.png" exif="{}" actualwidth="1024" id="A_9945D44E5F5B07CD06B6F4"/> 입력사항은 앞과 동일하고 T와 A가 정수여야 하므로 알맞게 선택해줍니다 <img src="https://t1.daumcdn.net/cfile/cafe/992E8C4C5F5B08370D" class="txc-image" width="634" style="clear: none; float: none;" border="0" vspace="1" hspace="1" data-filename="ILP_3.png" exif="{}" actualwidth="634" id="A_992E8C4C5F5B08370D884F"/> 앞에 구했던 최적의 결과값을 훨씬 간단하게 구할 수 있었습니다 -MS60 결과는 텍스트 문서로 첨부했습니다 *LP Relaxation 과 Integer Linear Program 비교 LP 는 정수라는 제약조건이 제거되었으므로 선택의 폭이 확장된 방법입니다 .따라서 목적달성에 유리할 가능성이 있습니다.ILP 는 정수라는 제약조건이 추가된 것이므로 선택의 폭이 줄어든 것입니다.따라서 목적달성에 불리할 가능성이 있습니다. 그리고 최적해를 구할 때 Max 값을 구할 경우 위의 예시를 보면 알 수 있듯 LP Relaxation 이 upper bound를 제공합니다. 반대로 Min 값을 구할 경우에는 LP Relaxation 이 lower bound를 제공합니다. 감사합니다 :) <a href="javascript:checkVirus('grpid%3DG7Le%26fldid%3DDVNf%26dataid%3D849%26fileid%3D10%26regdt%3D20200911142926&url=http%3A%2F%2Fcfile286.uf.daum.net%2Fattach%2F995C834C5F5B0AB40E52B6')"><img src="https://t1.daumcdn.net/daumtop_deco/icon/icon.hanmail.net/editor/p_etc_s.gif" border="0" alt="첨부파일" class="vam"/> LP.OUT</a> <a href="javascript:checkVirus('grpid%3DG7Le%26fldid%3DDVNf%26dataid%3D849%26fileid%3D11%26regdt%3D20200911142926&url=http%3A%2F%2Fcfile264.uf.daum.net%2Fattach%2F995AD94C5F5B0ABB0EFB51')"><img src="https://t1.daumcdn.net/daumtop_deco/icon/icon.hanmail.net/editor/p_etc_s.gif" border="0" alt="첨부파일" class="vam"/> ILP.OUT</a>