Question

要將甲、乙兩種長(zhǎng)短不同的鋼管截成A、B、C三種規(guī)格，每根鋼管可同時(shí)截得三種規(guī)格的短鋼管的根數(shù)如下表所示：

今需A、B、C三種規(guī)格的鋼管各13、16、18根，問(wèn)各截這兩種鋼管多少根可得所需三種規(guī)格鋼管，且使所用鋼管根數(shù)最少.

Answer 1

解:設(shè)需截甲種鋼管x根，乙種鋼管y根，則

作出可行域(如下圖)；

目標(biāo)函數(shù)為z=x＋y.

作出一組平行直線x＋y=t中(t為參數(shù))經(jīng)過(guò)可行域內(nèi)的點(diǎn)且和原點(diǎn)距離最近的直線，此直線經(jīng)過(guò)直線4x＋y=18和直線x＋3y=16的交點(diǎn)A(，)，直線方程為x＋y=.由于和都不是整數(shù)，所以可行域內(nèi)的點(diǎn)(，)不是最優(yōu)解.

經(jīng)過(guò)可行域內(nèi)的整點(diǎn)且與原點(diǎn)距離最近的直線是x＋y=8，經(jīng)過(guò)的整點(diǎn)是B(4，4)，它是最優(yōu)解.

答:要截得所需三種規(guī)格的鋼管，且使所截兩種鋼管的根數(shù)最少，方法是截甲種鋼管、乙種鋼管各4根.

點(diǎn)評(píng):此例的解法是，先依條件列出不等式組，作出可行域，不考慮x、y為非負(fù)整數(shù)的條件，求出符合題中其他條件的最優(yōu)解，然后看此最優(yōu)解是否為非負(fù)整數(shù)解，若是非負(fù)整數(shù)解，則即為所求.若不是非負(fù)整數(shù)解，則應(yīng)求出經(jīng)過(guò)可行域內(nèi)的非負(fù)整數(shù)解且與原點(diǎn)距離最遠(yuǎn)(或最近)的點(diǎn)的直線，點(diǎn)(4,4)也是可行域內(nèi)與過(guò)點(diǎn)(, )、斜率為－1的直線距離最近的點(diǎn)，這個(gè)非負(fù)整數(shù)解就是最優(yōu)解.