Question

要將兩種大小不同的鋼板截成A、B、C三種規(guī)格，每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表所示：

規(guī)格類型	A規(guī)格	B規(guī)格	C規(guī)格
鋼板類型
第一種鋼板	2	1	1
第二種鋼板	1	2	3

今需A、B、C三種規(guī)格的成品分別為15、18、27塊，問各截這兩種鋼板多少張可得所需三種規(guī)格成品，且使所用鋼板張數(shù)最少？

Answer 1

設(shè)需要第一種鋼板x張，第二種鋼板y張，鋼板總數(shù)z張，則

2x+y≥15 x+2y≥18 x+3y≥27 x∈N，y∈N

目標(biāo)函數(shù)z=x+y
作出可行域如圖所示，作出直線x+y=0．作出一組平行直線x+y=t（其中t為參數(shù)）．
其中經(jīng)過可行域內(nèi)的點且和原點距離最近的直線，
經(jīng)過直線x+3y=27和直線2x+y=15的交點A(

18

5

，

39

5

)，直線方程為x+y=

57

5

．
由于

18

5

和

39

5

都不是整數(shù)，而最優(yōu)解（x，y）中，x，y必須都是整數(shù)，
所以，可行域內(nèi)點A(

18

5

，

39

5

)不是最優(yōu)解．
經(jīng)過可行域內(nèi)的整點（橫坐標(biāo)和縱坐標(biāo)都是整數(shù)的點），且與原點距離最近的直線是x+y=12．
經(jīng)過的整點是B（3，9）和C（4，8），它們是最優(yōu)解．
故要截得所需三種規(guī)格的鋼板，且使所截兩種鋼板的張數(shù)最少的方法有兩種，第一種截法是截第一種鋼板3張、第二種鋼板9張；第二種截法是截第一種鋼板4張、第二種鋼板8張．兩種方法都最少要截兩種鋼板共12張．