《現(xiàn)代物流運(yùn)籌學(xué)（第二版）》 課件 6.整數(shù)規(guī)劃及其解法

整數(shù)規(guī)劃《現(xiàn)代物流運(yùn)籌學(xué)》主講教師：王東輝整數(shù)規(guī)劃的性質(zhì)整數(shù)規(guī)劃的解法0102目錄CONTENT案例某公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨物每件的體積、重量，可獲利潤(rùn)以及托運(yùn)所受限制如表所示。問(wèn)兩種貨物各裝運(yùn)多少箱，可使獲得利潤(rùn)最大？

表1-1

貨物每件體積(立方米)每件重量(百斤)

每件利潤(rùn)(百元)甲乙54252010托運(yùn)限制2414數(shù)學(xué)模型特點(diǎn)

設(shè)甲、乙兩種貨物裝運(yùn)箱數(shù)分別為x1和x2。顯然，x1、x2都要求為整數(shù),于是可建立整數(shù)規(guī)劃模型如下：maxz＝20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x1,x2為整數(shù)(1)(2)(3)(4)(5)

貨物每件體積(立方米)每件重量(百斤)

每件利潤(rùn)(百元)

甲乙54252010托運(yùn)限制24(立方米)14(百斤)它和線性規(guī)劃問(wèn)題的區(qū)別在于條件(5)整數(shù)規(guī)劃的特點(diǎn)與分類

整數(shù)規(guī)劃（IP）：要求一部分或全部決策變量取整數(shù)值的規(guī)劃問(wèn)題稱為整數(shù)規(guī)劃。不考慮整數(shù)條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問(wèn)題稱為該整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題。若該松弛問(wèn)題是一個(gè)線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。數(shù)學(xué)模型整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式：

整數(shù)規(guī)劃的分類純整數(shù)線性規(guī)劃：指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃?；旌险麛?shù)線性規(guī)劃：決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃。0-1型整數(shù)線性規(guī)劃：決策變量只能取值0或1的整數(shù)線性規(guī)劃。010-1型整數(shù)線性規(guī)劃ONE案例現(xiàn)有資金總額為B，可供選擇的投資項(xiàng)目有n個(gè)，項(xiàng)目j所需投資額和預(yù)期收益分別為aj和cj（j＝1,2,..,n），此外由于種種原因，有三個(gè)附加條件：若選擇項(xiàng)目1，就必須同時(shí)選擇項(xiàng)目2，反之不一定項(xiàng)目3和4中至少選擇一個(gè)項(xiàng)目5,6,7中恰好選擇2個(gè)應(yīng)該怎樣選擇投資項(xiàng)目，才能使總預(yù)期收益最大。數(shù)學(xué)模型解：對(duì)每個(gè)投資項(xiàng)目都有被選擇和不被選擇兩種可能，因此分別

用0和1表示，令xj表示第j個(gè)項(xiàng)目的決策選擇，記為：

投資問(wèn)題可以表示為：02整數(shù)規(guī)劃的解法“湊整法”TWO整數(shù)規(guī)劃的解法“湊整法”直覺(jué)認(rèn)為，對(duì)整數(shù)規(guī)劃問(wèn)題的求解可以先不考慮對(duì)變量的整數(shù)約束，作為一般線性規(guī)劃問(wèn)題來(lái)求解，當(dāng)解為非整數(shù)時(shí)可用四舍五入或湊整方法尋找最優(yōu)解。是否合適？是否可行？案例求下述整數(shù)規(guī)劃問(wèn)題的最優(yōu)解:

案例(3,3)(3,2)(4,3)(4,2)(4,1)，Z=14(3.25，2.5)2x1+3x2=14x1+0.5x2=4.53x1+2x2=0注意：(4，1)不是可行域的頂點(diǎn)，因此直接用圖解法或單純形法都無(wú)法找出整數(shù)規(guī)劃問(wèn)題的最優(yōu)解來(lái)。這就要求研究解整數(shù)規(guī)劃問(wèn)題的特殊方法。010203整數(shù)規(guī)劃的可行域包含在其對(duì)應(yīng)的一般線性規(guī)劃可行域之內(nèi)整數(shù)規(guī)劃的最優(yōu)解可能不是其對(duì)應(yīng)的一般線性規(guī)劃的頂點(diǎn)整數(shù)規(guī)劃需要專門的求解方法研究解整數(shù)規(guī)劃問(wèn)題的特殊方法收獲整數(shù)規(guī)劃與對(duì)應(yīng)的線性規(guī)劃解的關(guān)系任何求max的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標(biāo)函數(shù)值小于或等于相應(yīng)的線性規(guī)劃的最大目標(biāo)函數(shù)值；（對(duì)應(yīng)線性規(guī)劃最優(yōu)解為其上界）任何求min的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標(biāo)函數(shù)值大于或等于相應(yīng)的線性規(guī)劃的最小目標(biāo)函數(shù)。（對(duì)應(yīng)線性規(guī)劃最優(yōu)解為其下界）整數(shù)規(guī)劃之相應(yīng)線性規(guī)劃的最優(yōu)解經(jīng)四舍五入不能得到其最優(yōu)解整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其對(duì)應(yīng)的線性規(guī)劃的最優(yōu)解。