Question

某汽車公司有兩家裝配廠，生產甲、乙兩種不同型號的汽車，若A廠每小時可完成1輛甲型車和2輛乙型車；B廠每小時可完成3輛甲型車和1輛乙型車．今欲制造40輛甲型車和20輛乙型車，問這兩家工廠各工作幾小時，才能使所費的總工作時數最少？

Answer 1

設A廠工作xh，B廠工作yh，總工作時數為th，則t=x+y，
且x+3y≥40，2x+y≥20，x≥0，y≥0，
可行解區域如圖．
而符合問題的解為此區域內的格子點（縱、橫坐標都是整數的點稱為格子點），
于是問題變為要在此可行解區域內，
找出格子點（x，y），使t=x+y的值為最�。�
由圖知當直線l：y=-x+t過Q點時，
縱、橫截距t最小，但由于符合題意的解必須是格子點，
我們還必須看Q點是否是格子點．
解方程組

x+3y=40 2x+y=20

得Q（4，12）為格子點．
故A廠工作4h，B廠工作12h，可使所費的總工作時數最少．