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

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

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

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