第二天打卡-整數規劃（1）

一、談談我的理解

前兩次打卡，我們學會了線性規劃，這里為什么又引入一個整數規劃呢？其實兩個規劃很類似，唯一的區別就是整數規劃限制了我們的變數x必須為整數，而線性規劃沒有限制變數型別，
為什么我們要引入整數規劃呢？在實際生活中，我們就算付錢，可能也很少遇到讓你付小數的錢，都是讓你給一個整數，因此這就是整數規劃的由來，

二、題目

1）題目與簡析

假設我們有如下的整數規劃：

假設我們先把最后一個條件限制為整數暫時忽略？你是不是能用前面的知識求解出max,x1,x2呢？請把你的matlab求解程序寫到博客，提交到任務中，(晚上我提交答案）
我在這里先直接給出答案：

x1 = 4.8092, x2 = 1.8168,z = 355.8779

根據我計算出的結果可以看到x1和x2都不滿足整數情況，因此這就不再是最優解了，

2）分枝定界法步驟

方法用處：分枝定界法可用于解純整數或混合的整數規劃問題

2.1）第一步

根據我們出的結果，我們可以暫定z的上限（最大值）可以是356；我們也可以一樣看出x1,x2分別為0時，z最小值為0；因此最大值z的范圍可以暫定為：0=<z=<356

2.2）第二步

因為 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，

2.3）第三步

對第二步的問題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進行分枝，請看第四步，

2.4）第四步

為了便于觀看，我把問題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不可行解，因此也不可取，這樣的操作呢，叫做剪枝，

2.5）結論

由于B2的兩個分枝都不可取，B1只有一個枝可取，即最優解為：

x1 = 4, x2 = 2,z = 340

三、總結

開始，將要求解的整數規劃問題稱為問題 A ，將與它相應的線性規劃問題稱為問題 B，求解情況如下：

1. B 沒有可行解，這時 A 也沒有可行解，則停止
2. ） B 有最優解，并符合問題 A 的整數條件， B 的最優解即為 A 的最優解，則停止，
3. B 有最優解，但不符合問題 A 的整數條件，記它的目標函式值為 z，通過我上述所說的四個步驟使用花枝定界法進行分枝，剪枝，最后得出結果，

再次提醒： 請務必完成我在本篇文章中留下的問題，寫一篇博客提交任務，學習是靠你自己，你不努力，總有人比你更努力，