Skip to content

ๆ•ฐๅญฆ่ง„ๅˆ’

  • ่‹ฅๅนฒๅ˜้‡ๅœจๆปก่ถณไธ€ไบ›็ญ‰ๅผๆˆ–่€…ไธ็ญ‰ๅผ็š„้™ๅˆถๆกไปถไธ‹, ไฝฟๅพ—็›ฎๆ ‡ๅ‡ฝๆ•ฐๅ–ๅพ—ๆœ€ๅคงๆœ€ๅฐๅ€ผ

    • image_2024-06-23-09-50-27

ๆ•ดๆ•ฐ่ง„ๅˆ’็š„ๆพๅผ›

\[\begin{aligned}&\bullet\text{ ๆ•ดๆ•ฐ็บฟๆ€ง่ง„ๅˆ’ }(\mathrm{IP})\text{ ๅŽป้™คๅ†ณ็ญ–ๅ˜้‡ๅ–ๆ•ดๆ•ฐ็บฆๆŸๅŽๆ‰€ๅพ—็บฟๆ€ง}\\&\text{่ง„ๅˆ’ (LP) ็งฐไธบ (IP) ็š„ๆพๅผ›(relaxation)}\\&\bullet\quad(\mathrm{IP})\text{ ็š„ๅฏ่กŒๅŸŸๅŒ…ๅซไบŽ }(\mathrm{LP})\text{ ็š„ๅฏ่กŒๅŸŸไธญ}\\&\bullet\quad(\mathrm{IP})\text{ ็š„ๅฏ่กŒ่งฃไนŸๆ˜ฏ }(\mathrm{LP})\text{ ็š„ๅฏ่กŒ่งฃ,ไฝ†ๅไน‹ไธ็„ถ}\\&\bullet\quad(\mathrm{IP})\text{ ็š„ๆœ€ไผ˜ๅ€ผไธไผ˜ไบŽ }(\mathrm{IP})\text{ ็š„ๆœ€ไผ˜ๅ€ผ}\\&\bullet\quad(\mathrm{IP})\text{ ็š„ๆœ€ไผ˜่งฃไธŽ }(\mathrm{IP})\text{ ็š„ๆœ€ไผ˜่งฃ}\\&\bullet\text{ ่‹ฅ }(\mathrm{IP})\text{ ็š„ๆœ€ไผ˜่งฃไธบๆ•ดๆ•ฐ่งฃ,ๅˆ™ๅฎƒไนŸๆ˜ฏ }(\mathrm{IP})\text{ ็š„ๆœ€ไผ˜่งฃ}\\&\bullet\quad\text{่‹ฅ }(\mathrm{IP})\text{ ็š„ๆœ€ไผ˜่งฃไธไธบๆ•ดๆ•ฐ่งฃ,ไธๅญ˜ๅœจ้ซ˜ๆ•ˆ็š„ๅ–ๆ•ด็ญ–็•ฅๅฐ†}\quad(\mathrm{LP})\text{ ็š„}\\&\text{ๆœ€ไผ˜่งฃๅ˜ไธบ }(\mathrm{IP})\text{ ็š„ๆœ€ไผ˜่งฃ}\end{aligned}\]
\[\begin{aligned}\text{min cx}\\\text{(IP) s.t. Ax}&=\mathbf{b}\\\mathbf{x}\in\mathbb{Z}_+^n\\\text{min cx}\\\text{(LP) s.t. Ax}&=\mathbf{b}\\\mathbf{x}\in\mathbb{R}_+^n\end{aligned}\]