一、普通優(yōu)化問題分枝定界求解

題目的原問題為

? 在計算過程中，利用MATLAB中的linprog（）函數(shù)進行求解最優(yōu)解，具體的計算步驟如下：

A為約束系數(shù)矩陣，B為等式右邊向量，C為目標函數(shù)的系數(shù)向量。

? 進行第一次最優(yōu)求解以A=[2 9;11 -8],B=[40;82],C=[-3,-13]利用linprog函數(shù)求解。解得x1=9.2，x2=2.4，都不是整數(shù)，選定x1進行分枝操作。以x1<=9，x1>=10為約束條件進行下一次的分枝，此時求得的最大值為-58.8。

? 對于x1<=9 以A=[2 9;11 -8;1 0],B=[40;82;9],C=[-3,-13]進行求解，求得的解x1=9，x2=2.444，最大值為-58.7778。x110以A=[2 9;11 -8;-1 0],B=[40;82;-10],C=[-3,-13]求解，發(fā)現(xiàn)無界。接下來對x2進行分枝，以x2<=2，x2>=3進行分枝操作。

? 對于x2<=2以A=[2 9;11 -8;1 0；0?1],B=[40;82;9;2],C=[-3,-13]進行求解，求得的解x1=8.9，x2=2.0，最大值為-52.7273。由于是在x1<=9的條件下進行分枝的，此次迭代中不能再對x1進行分枝，轉(zhuǎn)而x2>=3以A=[2 9;11 -8;1 0；0?-1],B=[40;82;9;-3],C=[-3,-13]進行求解，求得的x1=6.5，x2=3，最大值為-58.5，x2為整數(shù)，所以接下來對x1繼續(xù)進行分枝，以x1<=6，x1>=7進行分枝操作。

? 對于x1<=6以A=[2 9;11 -8;1 0；0?-1;1?0],B=[40;82;9;-3;6],C=[-3,-13]進行求解，解得x1=6，x2=3.111，求得的最大值為-58.444，因為x1為常數(shù)，則接下來對x2進行分枝操作。對于x1>=7以A=[2 9;11 -8;1 0；0?-1;-1?0],B=[40;82;9;-3;-7],C=[-3,-13]進行求解，發(fā)現(xiàn)無解。接下來以x2<=3，x2>=4進行分枝操作。

? 對于x2<=3以A=[2 9;11 -8;1 0;0?-1;1?0;0 1],B=[40;82;9;-3;6;3],C=[-3,-13]進行求解，解得x1=6，x2=3，求得的最大值為-57，求得的解和最大值都為整數(shù)。對于x2>=4，以A=[2 9;11 -8;1 0;0?-1;1?0;0 -1],B=[40;82;9;-3;6;-4],C=[-3,-13]進行求解，解得x1=2，x2=4，求得的最大解為-58，求得的解和最大值也都為整數(shù)。相較于x2<=3和x2>=4的情況x2>=4的情況時求得的最大值更大，此時解和最大值都為整數(shù)，所以不再進行分枝。最后，得到最優(yōu)解為（2 ;4），最大值為58，分枝定界完畢。為了接下來更清楚的觀察整個過程，將展示樹圖的分枝定界。

?二、旅行商問題（規(guī)約矩陣）

? 旅行商問題是一個商品推銷員要去若干個城市推銷商品，該推銷員從一個城市出發(fā)，需要經(jīng)過所有城市后，回到出發(fā)地。應如何選擇行進路線，以使總的行程最短。旅行商問題可以通過好多方法來求解，這里主要應用分支界定法來進行求解。原問題如下所示，求解五個城市之間的TSP問題。

? ?此5×5矩陣表示五個城市之間的代價，第一行第三列的1表示從第一個城市到第三個城市的代價為1，第三行第一列的5表示從第三個城市到第一個城市的代價為5，所以兩個城市之間的來返代價并不一樣。為了方便后續(xù)表述，將五個城市分別記為城市a,b,c,d,e。且將城市自身的代價記為∞，則重新將TSP問題進行表述為

? 上述矩陣為重新表述的TSP問題。利用規(guī)約矩陣對TSP問題的代價進行計算，具體的代價計算公式為

? ?其中Cc為總的代價，為CA約束下的代價，w(A,C)為具體城市到城市之間的代價，C1’為當前代價。利用規(guī)約矩陣，以a城市為出發(fā)點的代價下限計算如下：

? ?其中，C列的絕對值之和為當前代價C1’，在對矩陣進行操作時，看每行每列是否有零，若沒有則減去最小的數(shù)值，若有零則不減。則從城市a出發(fā)，可以到達其他的四個城市，分枝定界圖和規(guī)約矩陣如下：

?

? a的代價為對B矩陣的C列絕對值進行求和得C1’=8。接下來對a到b，a到c，a到d和a到e之間的代價進行計算，具體的規(guī)約矩陣如下：

在矩陣B的基礎(chǔ)上，進行計算，將涉及到的城市的代價寫為無窮：

?利用計算代價公式得

? ?由上式計算結(jié)果可見，從a城市到c城市的代價最小，再從c城市出發(fā)，可以到達的城市有城市b，d，e，分枝定界圖和規(guī)約矩陣如下：

? ?由上式結(jié)果可見從a到c到b的代價最大，從a到c到d和從a到c到e的代價一樣 ，接下來繼續(xù)計算這兩條路徑的代價，從a到c到d還可以走b和e，從a到c到e還可以走b和d。分枝定界圖和規(guī)約矩陣如下：

?

?利用公式計算代價得

? ?由以上結(jié)果可見從a到c到d到b的代價于a到c到d到e的代價和a到c到e到b的代價都是一樣為11，從a到c到e到d的代價最小為8，再接下來就只考慮從d出發(fā)到城市b的代價和從b城市重新回到城市a的代價分枝定界圖和規(guī)約矩陣如下：

? ?至此，求出了旅行商問題的最優(yōu)解，最優(yōu)路徑為a→c→e→d→b→a，對應于數(shù)字為1→3→5→4→2→1代價為8。

注：旅行商問題中涉及到規(guī)約矩陣，不懂的讀者可以先行了解規(guī)約矩陣文章來源地址http://www.zghlxwxcb.cn/news/detail-598268.html

到了這里，關(guān)于整數(shù)規(guī)劃——分支界定算法（旅行商問題，規(guī)約矩陣求解）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！