線性規(guī)劃問題就是求出一組變量，在一組線性約束條件下，使某個(gè)線性目標(biāo)函數(shù)達(dá)到極大（小）值。滿足線性約束條件的變量區(qū)域稱為可行解區(qū)。由于可行解區(qū)的邊界均是線性的（平直的），屬于單純形，所以線性目標(biāo)函數(shù)的極值只要存在，就一定會(huì)在可行解區(qū)邊界的某個(gè)頂點(diǎn)達(dá)到。因此，在求解線性規(guī)劃問題時(shí)，如果容易求出可行解區(qū)的所有頂點(diǎn)，那么只要在這些頂點(diǎn)處比較目標(biāo)函數(shù)的值就可以了。
例如，線性規(guī)劃問題：max S=x+y（求S=x+y的最大值）；2x+y<=7, x+2y<=8, x>=0, y>=0的可行解區(qū)是由四條直線2x+y=7, x+2y=8, x=0, y=0圍成的，共有四個(gè)頂點(diǎn)。除了原點(diǎn)外，其他三個(gè)頂點(diǎn)是（1）。因此，該線性規(guī)劃問題的解為（2）
（1）A. （2,3），（0,7），（3.5,0）
B. （2,3），（0,4），（8,0）
C. （2,3），（0,7），（8,0）
D. （2,3），（0,4），（3.5,0）
（2）A. x=2，y=3
B. x=0，y=7
C. x=0，y=4
D. x=8，y=0