列生成算法的應(yīng)用-ppt課件

1、列生成算法最早被用來(lái)求解大規(guī)模線性規(guī)劃問(wèn)題 塊角構(gòu)造的線性規(guī)劃用D-W分解算法求解相當(dāng)有效，其主要思想是首先將問(wèn)題轉(zhuǎn)化為一個(gè)可以處置的等價(jià)問(wèn)題，轉(zhuǎn)化的目的在于：將問(wèn)題轉(zhuǎn)化為具有某種特殊構(gòu)造的又有現(xiàn)成方法求解的問(wèn)題將問(wèn)題化為規(guī)模較小的子問(wèn)題由D-W分解原理，上述LP問(wèn)題對(duì)應(yīng)的主問(wèn)題MP是列生成算法步驟如下：列生成算法解線性規(guī)劃問(wèn)題234B =100132 1B =1 112 3B =5 1 分配n項(xiàng)義務(wù)給m臺(tái)機(jī)器完成，分配不同義務(wù)到不同機(jī)器所獲得的效益是不同的，每項(xiàng)義務(wù)必需而且僅能由一臺(tái)機(jī)器完成，每臺(tái)機(jī)器都有才干限制ci;，問(wèn)題是要得到最大經(jīng)濟(jì)效益的分配但不能超出每臺(tái)機(jī)器的負(fù)荷才干，類(lèi)似的問(wèn)題稱(chēng)

2、為廣義分配問(wèn)題數(shù)學(xué)上，GAP問(wèn)題能被表示成如下: (2) (1) (3) (4)注：2表示一個(gè)義務(wù)被分配而且僅被分配到一個(gè)機(jī)器 3代表至多一個(gè)可行分配被選擇到每個(gè)機(jī)器結(jié)合列生成技術(shù)運(yùn)用分支定價(jià)算法解這個(gè)多列GAP問(wèn)題LP松弛的解松弛的解列生成的主要思想就是：對(duì)大規(guī)模LP問(wèn)題，不用列出一切的列，只經(jīng)過(guò)解由這個(gè)約束矩陣列的一個(gè)子集構(gòu)成的問(wèn)題，稱(chēng)為限制的主問(wèn)題，而獲得原問(wèn)題的解。在每一步解限制的主問(wèn)題的迭代里，經(jīng)過(guò)主問(wèn)題的最優(yōu)性檢驗(yàn)獲得原問(wèn)題的最優(yōu)解或者產(chǎn)生進(jìn)基列重新進(jìn)展迭代。567867那么主問(wèn)題的最優(yōu)性判別由下式獲得PP的最優(yōu)的最優(yōu)值值價(jià)錢(qián)問(wèn)題價(jià)錢(qián)問(wèn)題分支定界過(guò)程實(shí)現(xiàn)分支定界過(guò)程實(shí)現(xiàn)實(shí)現(xiàn)分支定價(jià)

3、算法的挑戰(zhàn)之一是確定分支戰(zhàn)略。分支的機(jī)理是劃分解空間以刪除分?jǐn)?shù)解。然而解空間的直接劃分經(jīng)過(guò)固定一個(gè)單個(gè) 是不適宜的，由于這將導(dǎo)致列生成算法難于實(shí)現(xiàn)，而且產(chǎn)生不平衡的分支定界樹(shù)，使分支定界算法變壞。定理： 假設(shè)列生成問(wèn)題的最優(yōu)解 是不可行的，即是 分?jǐn)?shù)，那么必至少存在一個(gè)j,使因此得以下分支戰(zhàn)略在一個(gè)分支：令在另外一個(gè)分支：令這個(gè)分支規(guī)那么經(jīng)過(guò)以下兩個(gè)步驟實(shí)現(xiàn)：1、在每個(gè)分支節(jié)點(diǎn)求解限制的主問(wèn)題時(shí)，在左分支對(duì)由第i個(gè)價(jià)錢(qián)問(wèn)題所產(chǎn)生的列做如下處置：刪除第j個(gè)分量不為0的列；在右支刪除第j個(gè)分量為0的列。2、為堅(jiān)持價(jià)錢(qián)問(wèn)題的相容性，當(dāng)求解第i個(gè)價(jià)錢(qián)問(wèn)題的子問(wèn)題產(chǎn)生新的添加列時(shí)，在左分支固定第j個(gè)分量為0，即不允許分配第j個(gè)義務(wù)給第i個(gè)機(jī)器