Question

兩種大小不同的鋼板可按下表截成A,B,C三種規(guī)格成品:

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

某建筑工地需A，B，C三種規(guī)格的成品分別為15，18，27塊，問怎樣截這兩種鋼板，可得所需三種規(guī)格成品，且所用鋼板張數(shù)最小.

Answer 1

要截得所需三種規(guī)格的鋼板，且使所截兩種鋼板的張數(shù)最少的方法有兩種：
第一種截法是截第一種鋼板3張，第二種鋼板9張；
第二種截法是截第一種鋼板4張，第二種鋼板8張；
兩種方法都最少要截兩種鋼板共12張.

設需要第一種鋼板x張，第二種鋼板y張，鋼板總數(shù)為z張，z=x+y,
約束條件為：
作出可行域如圖所示：
令z=0，作出基準直線l:y=-x,平行移動直線l發(fā)現(xiàn)在可行域內(nèi)，經(jīng)過直線x+3y=27和直線2x+y=15的交點A可使z取最小，由于都不是整數(shù)，而最優(yōu)解（x,y）中，x,y必須都是整數(shù)，可行域內(nèi)點A不是最優(yōu)解；
通過在可行域內(nèi)畫網(wǎng)格發(fā)現(xiàn)，經(jīng)過可行域內(nèi)的整點且與A點距離最近的直線是x+y=12,經(jīng)過的整點是B(3,9)和C（4，8），它們都是最優(yōu)解.
答 要截得所需三種規(guī)格的鋼板，且使所截兩種鋼板的張數(shù)最少的方法有兩種：
第一種截法是截第一種鋼板3張，第二種鋼板9張；
第二種截法是截第一種鋼板4張，第二種鋼板8張；
兩種方法都最少要截兩種鋼板共12張.