[管理學(xué)]整數(shù)規(guī)劃(2)(已修改)
2024-10-31 01:40 本頁面
【正文】 整數(shù) (線性 )規(guī)劃 (Integer Programming,IP) 在線性規(guī)劃問題的討論中，有些最優(yōu)解是小數(shù)，但 某些常要求最優(yōu)解是整數(shù)（即整數(shù)解） 如決策變量是： 機(jī)器的臺數(shù)、人數(shù)、車輛數(shù)等等 如果在問題中所有變量有整數(shù)限制，稱： 純整數(shù)規(guī)劃 （或全整數(shù)規(guī)劃）； 如果問題中僅部分變量有整數(shù)限制，稱： 混合整數(shù)規(guī)劃 ； 如果在問題中決策變量僅取 0,1，稱： 01規(guī)劃 例 1（裝載問題）某 廠 擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤，及托運(yùn)限制如表，問兩種貨物各托運(yùn)多少箱，可獲利最大。 貨物 每箱體積 每箱重量（百斤） 每箱利潤 甲 5 2 20 乙 4 5 10 托運(yùn)限制 24 13 解： 設(shè) x1,x2分別為甲、乙兩種貨物托運(yùn)箱數(shù)，則： max Z = 20 x1 + 10 x2 . 5x1 + 4x2 ≤ 24 2 x1 + 5x2 ≤ 13 x1 ≥ 0， x2 ≥ 0 .x1,x2為整數(shù) 這是一個(gè)純整數(shù)規(guī)劃問題 例 2（背包問題，投資問題） 假設(shè)有人要出發(fā)旅行，他擬考慮帶七種。每種物品的重量與 價(jià)值，如表?，F(xiàn)在假設(shè)他最多能帶 35 kg物品，問該帶哪幾 件物品，總價(jià)值最大？ 物品 重量 aj 價(jià)值 Cj 1 3 12 2 4 12 3 3 9 4 3 15 5 15 90 6 13 26 7 16 112 解： ????否種物品如果帶第01 jx j）（或 7~110..m a x7171????????jxbxatsxCZjjjjjjj這是一個(gè) 01規(guī)劃問題 對 IP問題，可能會認(rèn)為，只要求出不受整數(shù)約 束的解，然后 “ 舍入化整 ” ，就可得到整數(shù)最優(yōu) 解，是這樣嗎？ 其實(shí)，這樣的方法常常是行不通的。 下面通過整數(shù)規(guī)劃的求解來說明。 圖解法 裝載問題為例： max Z = 20 x1 + 10 x2 . 5x1 + 4x2 ≤ 24 2 x1 + 5x2 ≤ 13 x1 ≥ 0， x2 ≥ 0 .x1,x2為整數(shù) 5 2 1 0 1 3 2 4 3 L1 L2 x1 x2 A B C 求解得： x1=,x2=0,Zmax=96 考慮化整 x1=5,x2=0,不可行 x1=4,x2=0,Zmax=80 最優(yōu)：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1