文章目錄
前兩次打卡，我們學會了線性規劃，這裡為什麼又引入一個整數規劃呢？其實兩個規劃很類似，唯一的差別就是整數規劃限制了我們的變量x必須為整數，而線性規劃沒有限制變量類型。
為什麼我們要引入整數規劃呢？在實際生活中，我們就算付錢，可能也很少遇到讓你付小數的錢，都是讓你給一個整數，是以這就是整數規劃的由來。
假設我們有如下的整數規劃：
假設我們先把最後一個條件限制為整數暫時忽略？你是不是能用前面的知識求解出max,x1,x2呢？請把你的matlab求解過程寫到部落格，送出到任務中。(晚上我送出答案）
我在這裡先直接給出答案：
x1 = 4.8092, x2 = 1.8168,z = 355.8779 根據我計算出的結果可以看到x1和x2都不滿足整數情況，是以這就不再是最優解了。
方法用處：分枝定界法可用于解純整數或混合的整數規劃問題
根據我們出的結果，我們可以暫定z的上限（最大值）可以是356；我們也可以一樣看出x1,x2分别為0時，z最小值為0；是以最大值z的範圍可以暫定為：0=<z=<356
因為 x1, x2 目前均為非整數，故不滿足整數要求，任選一個進行分枝。設選 x1進行分枝，把可行集分成 2 個子集：
x1 =<[4.8092] = 4 ， x1 >= [4.8092] +1 = 5 4與5之間沒有整數，是以這種方法就是叫做分枝。
這兩個子集的規劃及求解如下：
問題 B1 ：
目标函數：
Max z = 40x1 + 90x2 限制條件：
9*x1+7*x2<=56
7*x1+20*x2<=70
0<x1<4 x2>0 因為我們隻對x1做了分枝，是以x2的限制不變。
這裡計算方法跟線性規劃不一樣，但是有一點我沒有講到的是前面我們沒有遇到x在兩者之間的問題，是以我對此B1做matlab計算最優解如下：
clc
clear all
c=[40 90];%用目标函數系數來确定
a=[9 7 ;7 20];%限制條件左邊限制
b=[56 70];%限制條件右邊系數
aeq=[];%沒有等式限制，是以aeq,beq都為空
beq=[];
lb=[0;0];%下限依然都為0
ub=[4;inf];%x1上限為4，x2沒有上限
[x,y]=linprog(-c,a,b,aeq,beq,lb,ub); %這裡沒有等式限制，對應的矩陣為空矩陣
x %擷取對應x1,x2
best=c*x%計算最優值
運作結果：
是以我們得出：
x1 = 4.0, x2 = 2.1,z1 = 349
。
我們對下x1做了分支，是以我們還要計算x1的另一半（我們就是相當于把x1範圍劃分兩半，分别計算，後面我們再求其和）。是以對于x1有問題 B2 ：
Max z = 40x1 + 90x2 條件限制：
9*x1+7*x2<=56
7*x1+20*x2<=70
x1>=5 x2>0 上面我已經寫過解法了，請對照上面的解法寫出你的matlab求解，并寫在部落格裡（本篇文章所有留下的問題寫在一篇部落格送出任務）
我直接給出答案：
可以看到
x1=5 x2=1.5714 z=341.4286
現在我們把最優值再定界确定範圍為：
0 ≤ z ≤ 349
對第二步的問題B1繼續分支，我們可以看到問題B1隻有x2有小數，是以我們是對B1問題裡的x2進行分枝（按照第一步的方法）:
0=<x2<[2.1]=2,x2>[2.1]+1=3 進而得到問題如下：
B11問題目标函數：
Max z = 40x1 + 90x2 9*x1+7*x2<=56
7*x1+20*x2<=70
0<=x1<=4 2>x2>0 matlab計算代碼如下：
clc
clear all
c=[40 90];%用目标函數系數來确定
a=[9 7 ;7 20];%限制條件左邊限制
b=[56 70];%限制條件右邊系數
aeq=[];%沒有等式限制，是以aeq,beq都為空
beq=[];
lb=[0;0];%下限依然都為0
ub=[4;2];%x1上限為4，x2沒有上限
[x,y]=linprog(-c,a,b,aeq,beq,lb,ub); %這裡沒有等式限制，對應的矩陣為空矩陣
x %擷取對應x1,x2
best=c*x%計算最優值
運作：
然後我們再計算x2另一個分枝，唯一變化的還是x範圍.
問題B12:
Max z = 40x1 + 90x2 條件限制:
9*x1+7*x2<=56
7*x1+20*x2<=70
0<=x1<=4 x2>3 matlab計算結果為：（請你在部落格寫上此題的matlab計算過程）
是以我們可以再次确定z範圍為：
340 ≤ z ≤ 341
到這裡我們已經對問題B1做出完美分枝，是以我們再對問題B2進行分枝，請看第四步。
為了便于觀看，我把問題B2拖下來：
根據上面的結果，x2=1.5714為小數，是以我們對B2中的x2進行分枝。
0=<x2<[1.5714]=1,x2>[1.5714]+1=2 得到問題B21如下：
Max z = 40x1 + 90x2 9*x1+7*x2<=56
7*x1+20*x2<=70
x1>=5 1>x2>0 用matlab計算結果如下：（請你在部落格寫出你的matlab代碼）
B22問題如下：
Max z = 40x1 + 90x2 9*x1+7*x2<=56
7*x1+20*x2<=70
x1>=5 x2>2 matlab如下：
clc
clear all
c=[40 90];%用目标函數系數來确定
a=[9 7 ;7 20];%限制條件左邊限制
b=[56 70];%限制條件右邊系數
aeq=[];%沒有等式限制，是以aeq,beq都為空
beq=[];
lb=[5;2];%下限
ub=[inf;inf];%上限
[x,y]=linprog(-c,a,b,aeq,beq,lb,ub) %這裡沒有等式限制，對應的矩陣為空矩陣
運作如下：
根據結果我指出的地方可以看到，沒有解。
綜合B2的兩個分枝，B21分枝後依然有小數，不可取；B22不可行解，是以也不可取。這樣的操作呢，叫做剪枝。
由于B2的兩個分枝都不可取，B1隻有一個枝可取，即最優解為：
x1 = 4, x2 = 2,z = 340 開始，将要求解的整數規劃問題稱為問題 A ，将與它相應的線性規劃問題稱為問題 B。求解情況如下：
- B 沒有可行解，這時 A 也沒有可行解，則停止
- ） B 有最優解，并符合問題 A 的整數條件， B 的最優解即為 A 的最優解，則停止。
- B 有最優解，但不符合問題 A 的整數條件，記它的目标函數值為 z，通過我上述所說的四個步驟使用花枝定界法進行分枝，剪枝，最後得出結果。
再次提醒： 請務必完成我在本篇文章中留下的問題，寫一篇部落格送出任務，學習是靠你自己，你不努力，總有人比你更努力。