資訊專欄INFORMATION COLUMN
摘要：列生成是用于求解大規(guī)模線性優(yōu)化問題的一種算法，其實就是單純形法的一種形式。如果需要求得整數(shù)最優(yōu)解需要結合分支定界算法。子問題用于生成新的切割方案列，子問題的約束對應切割約束。
列生成是用于求解大規(guī)模線性優(yōu)化問題的一種算法，其實就是單純形法的一種形式。單純性可以通過不斷迭代，通過換基變量的操作，最終找到問題的最優(yōu)解。但是當問題的規(guī)模很大之后，變量的個數(shù)就會增大到在有限時間內無法有效迭代求解。所以可以用列生成方法求解，列生成方法可以一開始不列舉所有的列，通過不斷給模型中加入列的方式，最終找到全部解，其關鍵點就是加新列的過程，可以只加入能讓目標值更優(yōu)的列，從而減少變量的使用個數(shù)。
列生成過程中，需要將問題建模為主問題+子問題的形式。
主問題：就是原問題，主要用于決策是否選用某些方案（列）
主問題松弛問題：將主問題變量范圍正整數(shù)松弛到正數(shù)
限制主問題：主問題去掉一部分列
限制主問題對偶問題：對限制主問題求對偶
價格子問題：原問題的局部問題，用于生成新的方案（列）
將一些鋼管切割成為需要的長度以滿足客戶需求，要求使用的鋼管最少。
每根鋼管長度L=16m
需求：3m鋼管25根；6m鋼管20根，7米鋼管18根
/(x_j/): 方案選用的個數(shù)
/(a_{ij}/): 方案/(j/)中鋼管/(i/)的個數(shù)
/(d_i/): 鋼管/(i/)的需求量
變量是整數(shù)的情況下無法用列生成法求得最優(yōu)解，需要將問題松弛。如果需要求得整數(shù)最優(yōu)解需要結合分支定界算法。
將主問題中的變量規(guī)模減小，一開始只加入一部分可行的切割方案（/(a_j/)，列），列生成就是不斷生成新的/(a_j/) 加入到問題中。判斷一個列是否可以加入到問題，需要判斷檢驗數(shù)/(/sigma_j = c_j - c_B B^{-1}a_j/),如果檢驗數(shù)為負，就可以將新的列加入。其中/(c_BB^{-1}/)有兩重含義：
對偶問題和原問題有同樣的最優(yōu)解，將原問題進行對偶，可以把原問題的變量轉化為約束、約束轉化為變量，因此，對于變量很多的問題將其轉化為對偶問題可以很容易得到其子問題。
對偶問題用于推導子問題?？梢赃M入主問題的列，就是檢驗數(shù)為負數(shù)的列，對于對偶問題，就是違反了約束的列。對偶問題中只有一個約束，/(/sum_{i in / I} a_{ij} /lambda_i /le 1/)可以寫成/(1-/sum_{i /in I} a_i /lambda_i /ge 0/)，求其最小值，如果最小值小于0，則說明其違反了約束。子問題用于生成新的切割方案(列)，子問題的約束對應切割約束。
以下所有的求解都可以用CPLEX進行求解，直接用CPLEX IDE實現(xiàn)
首先有可行的切割方案才能構造出主問題，因此可以用啟發(fā)式先計算出一些可行的切割方案，用于構造主問題。很簡單的，每根鋼管只生產(chǎn)一種產(chǎn)品，可以得到三種切割方案
| 切割方案 | 3m | 6m | 7m |
|---|---|---|---|
| 1 | 5 | 0 | 0 |
| 2 | 0 | 2 | 0 |
| 3 | 0 | 0 | 2 |
松弛限制主問題：
對偶問題：
求得對偶變量的值，將其帶入到子問題中
子問題：
目標函數(shù)值為-0.2<0，可以加入到主問題中繼續(xù)求解，新加入的一列是/(a_4=[1,2,0]^T/)，表示這個方案中一根鋼管切出一根3m和2根6米
松弛限制主問題：
對偶問題：
求得對偶變量的值，將其帶入到子問題中
子問題：
目標函數(shù)值為-0.1<0，可以加入到主問題中繼續(xù)求解，可以加入到主問題中繼續(xù)求解，新加入的一列是/(a_4=[1,1,1]^T/)，表示這個方案中一根鋼管切出1根3m，1根6米，1根7米
松弛限制主問題：
對偶問題：
求得對偶變量的值，將其帶入到子問題中
子問題:
根據(jù)求解可以得到
目標值：20.2
切割方案：方案1選擇1.2個；方案4選擇1個，方案5選擇18個
最后求得的結果包含了小數(shù)，如果想要取得整數(shù)解，需要結合分支定界算法
文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/125097.html
摘要：前言庫提供了專門從財經(jīng)網(wǎng)站獲取金融數(shù)據(jù)的接口，可作為量化交易股票數(shù)據(jù)獲取的另一種途徑，該接口在庫基礎上實現(xiàn)了以客戶端身份訪問網(wǎng)站的股票數(shù)據(jù)。第三四個參數(shù)為股票數(shù)據(jù)的起始時間斷。遍歷每個交易日后將符合跳空缺口條件的交易日增加缺口數(shù)值。 前言 Pandas庫提供了專門從財經(jīng)網(wǎng)站獲取金融數(shù)據(jù)的API接口，可作為量化交易股票數(shù)據(jù)獲取的另一種途徑，該接口在urllib3庫基礎上實現(xiàn)了以客戶端身份...
摘要：本人郵箱歡迎轉載轉載請注明網(wǎng)址代碼已經(jīng)全部托管有需要的同學自行下載引言迷宮對于大家都不會陌生那么迷宮是怎么生成已經(jīng)迷宮要如何找到正確的路徑呢用代碼又怎么實現(xiàn)帶著這些問題我們繼續(xù)往下看并查集朋友圈有一種算法就做并查集什么意思呢比如現(xiàn)在有零 本人郵箱: 歡迎轉載,轉載請注明網(wǎng)址 http://blog.csdn.net/tianshi_kcogithub: https://github.c...
閱讀 3748·2023-01-11 11:02
閱讀 4255·2023-01-11 11:02
閱讀 3072·2023-01-11 11:02
閱讀 5189·2023-01-11 11:02
閱讀 4750·2023-01-11 11:02
閱讀 5563·2023-01-11 11:02
閱讀 5327·2023-01-11 11:02
閱讀 4023·2023-01-11 11:02
