º»¹®/³»¿ë
2021Çг⵵ 2Çб⠱⸻½ÃÇè(°úÁ¦¹°)
±³°ú¸ñ¸í
:
°æ¿µÀÇ»ç°áÁ¤·Ð
Çйø
:
¼º¸í
:
¿¬¶ôó
:
¡Ø A4¿ëÁö ÆíÁý »ç¿ë
- ÀÌÇÏ ÀÛ¼º
¼±Çü°èȹ¹ý(LP; Linear Programming)ÀÇ Æ¯º°ÇÑ °æ¿ì·Î Á¤¼ö°èȹ¹ý(IP; Integer Programming)À» µé ¼ö ÀÖ´Ù. È¥ÇÕ Á¤¼ö°èȹ¹ý(Mixed Integer Programming)ÀÇ ÇØ¹ý Áß¿¡ ºÐ´ÜŽ»ö¹ý(Branch and Bound) ¾Ë°í¸®Áò¿¡ ´ëÇØ ¼³¸íÇϽÿÀ. ¾Ë°í¸®Áò¿¡ ´ëÇÑ ¼³¸í ÀÌÈÄ¿¡ ÀÌ ¾Ë°í¸®ÁòÀÇ Å¸´ç¼º¿¡ ´ëÇØ º»ÀÎÀÇ »ý°¢À» ±â¼úÇϽÿÀ.
1.¼·Ð
1)1) ±è¼¼Çå(2000)
¿ì¸®´Â °æ¿µÀÇ»ç°áÁ¤·Ð¿¡¼ ¿©·¯ °èȹ¹ý°ú ÇØ¹ý µîÀ» ¹è¿ü´Ù. ´ëÇ¥ÀûÀÎ °ÍÀÌ ¹Ù·Î Á¤¼ö°èȹ¹ýÀ̾ú´Ù. ÀÌ´Â integer programmingÀ̶ó°í ÇÏ´Â ¾àÀÚ¸¦ °¡Áö°í ÀÖ¾î IP¶ó°í ¸»Çϴµ¥ ÁÖ¿äÇÑ Æ¯Â¡ÀÌ ¹Ù·Î ÀÇ»ç°áÁ¤À» ³»¸± ¶§ ¹ß»ýÇÏ´Â º¯¼ö°¡ ¸ðµÎ Á¤¼öÀÇ ¸ð½ÀÀ» Çϰí ÀÖ´Ù´Â °ÍÀÌ´Ù. ±×·¸´Ù¸é ºñ½ÁÇÑ ¾àÀÚ¸¦ »ç¿ëÇϰí ÀÖ´Â Á¤¼ö¼±Çü°èȹ¹ýÀ̶ó°í ÇÏ´Â °ÍÀº IPÀÇ À¯Çü¿¡ ¼ÓÇϱâ´Â ÇÏÁö¸¸ ¸ñÀûÇÔ¼ö³ª Á¦¾àÁ¶°Ç±îÁö ¸ðµÎ 1Â÷½Ä¡¦(»ý·«)
2.º»·Ð
(1)ºÐ´ÜŽ»ö¹ýÀÇ ¾Ë°í¸®Áò
(2)Ÿ´ç¼º