整数线性规划实现（matlab分枝界定法）
文章目錄
一、本次問題
1.利用第一天所學(xué)知識(shí)求解：
2.本題理解：
（1）分支界定法
背景：
基本理論（解題步驟）：
求解實(shí)現(xiàn)1：
1.第一步
2.第二步
3.第三步
4.第四步
結(jié)論：綜上，最優(yōu)解：x1 = 4 ，x2 = 2 ；最優(yōu)值：340?
求解實(shí)現(xiàn)2：
結(jié)果2：最優(yōu)解：x1 = 4 ，x2 = 2 ；最優(yōu)值：340?
?求解實(shí)現(xiàn)3：
結(jié)果3：最優(yōu)解：x1 = 4 ，x2 = 2 ；最優(yōu)值：340?
總結(jié)：
一、本次問題
1.利用第一天所學(xué)知識(shí)求解：
建模學(xué)習(xí)打卡第一天_菜菜笨小孩的博客-CSDN博客
代碼如下：
%打卡第一天 clear all clc c=[40 90];%用目標(biāo)函數(shù)系數(shù)來確定 a=[9 7 ;7 20];%不等式約束條件左邊約束 b=[56 70];%不等式約束條件右邊系數(shù) aeq=[];%沒有等式約束，因此aeq,beq都為空 beq=[]; lb=[0;0];%沒有下限 ub=[inf;inf];%沒有上限 [x,fval]=linprog(-c,a,b,aeq,beq,lb,ub); x %獲取對(duì)應(yīng)x1,x2 best=c*x%計(jì)算最優(yōu)值2.本題理解：
由于問題要求求解結(jié)果都為整數(shù)，所以第一問結(jié)果錯(cuò)誤，那么我們?cè)撊绾吻蟮孟胍谜麛?shù)解呢？
（1）分支界定法
背景：
今天利用matlab來實(shí)現(xiàn)求解完全整數(shù)規(guī)劃問題的分支定界法。這里求解的模型為目標(biāo)函數(shù)最小化模型:
基本理論（解題步驟）：
- 分支定界法：用以求解整數(shù)規(guī)劃問題的一種方法。
- 求解步驟：
首先我們規(guī)定求解的整數(shù)規(guī)劃問題為A，相應(yīng)的線性規(guī)劃問題為B
1. 若B無可行解，則A也無可行解，停止計(jì)算
2. 若B有最優(yōu)解，且符合整數(shù)條件，該最優(yōu)解為A的最優(yōu)解，停止計(jì)算
3. 若B有最優(yōu)解，但不符合整數(shù)條件，記它的目標(biāo)函數(shù)值為z*，作為最優(yōu)值的下界
注意事項(xiàng)：在對(duì)兩分支進(jìn)行分解時(shí)，優(yōu)先選擇目標(biāo)函數(shù)值最小的分支進(jìn)行分解。
分支定界法中，通過定界進(jìn)而進(jìn)行剪枝，對(duì)分支進(jìn)行了篩選，使我們僅在一部分可行解中尋求最優(yōu)解，而不是全部窮舉出來再尋找，其求解效率更高。
求解實(shí)現(xiàn)1：
linprog函數(shù)及其參數(shù)的意義請(qǐng)看建模學(xué)習(xí)打卡第一天_菜菜笨小孩的博客-CSDN博客
簡(jiǎn)單介紹下，首先MATLAB中求解的是目標(biāo)函數(shù)是最小值的問題，但如果我們的目標(biāo)函數(shù)是求最大值，可以通過對(duì)目標(biāo)函數(shù)中每一項(xiàng)中乘以-1，將求最大值問題轉(zhuǎn)化為求最小值問題；A，b分別為不等式約束中的系數(shù)矩陣。Aeq和beq分別為等式約束中的系數(shù)矩陣，lb，和ub分別為每個(gè)變量的上下區(qū)間；最后c為目標(biāo)函數(shù)中各變量的系數(shù)矩陣。
1.第一步
根據(jù)上面給出的結(jié)果，知道結(jié)果不符合題意。
于是我們可以暫定z的上限（最大值）為356，又因?yàn)楫?dāng)x1，x2全為0時(shí)，z也為0，所以可以暫定z的范圍為 0<= z <= 356；并且將對(duì)x1值的范圍兩種情況定為問題A和問題B，并分別為枝干求解
2.第二步
首先，我們對(duì)A問題進(jìn)行分支，改變x1的約束條件，不改變x2的約束條件，即對(duì)x1分支得兩個(gè)子集
x1 =<[4.8092] = 4 ， x1 >= [4.8092] +1 = 5約束條件變?yōu)?#xff1a;
9*x1+7*x2<=56 7*x1+20*x2<=70 0<x1<4或x1>5 x2>0先對(duì)0<x1<4求解??代碼如下：
clc clear allc=[40 90];%用目標(biāo)函數(shù)系數(shù)來確定 a=[9 7 ;7 20];%約束條件左邊約束 b=[56 70];%約束條件右邊系數(shù)aeq=[];%沒有等式約束，因此aeq,beq都為空 beq=[];lb=[0;0];%下限依然都為0 ub=[4;inf];%x1上限為4，x2沒有上限[x,y]=linprog(-c,a,b,aeq,beq,lb,ub); %這里沒有等式約束，對(duì)應(yīng)的矩陣為空矩陣 x %獲取對(duì)應(yīng)x1,x2 best=c*x%計(jì)算最優(yōu)值結(jié)果為：此時(shí)的最優(yōu)解 x1=4 , x2=2.1 ; 最優(yōu)值為 349。也不符合題意，所以舍
再對(duì) x1 > 5求解 代碼如下：
clc clear allc=[40 90];%用目標(biāo)函數(shù)系數(shù)來確定 a=[9 7 ;7 20];%約束條件左邊約束 b=[56 70];%約束條件右邊系數(shù)aeq=[];%沒有等式約束，因此aeq,beq都為空 beq=[];lb=[5;0];% x1的下限變成5，x2下限依然都為0 ub=[inf;inf];%x1，x2沒有上限 1 [x,y]=linprog(-c,a,b,aeq,beq,lb,ub); %這里沒有等式約束，對(duì)應(yīng)的矩陣為空矩陣 x %獲取對(duì)應(yīng)x1,x2 best=c*x%計(jì)算最優(yōu)值結(jié)果為：此時(shí)的最優(yōu)解 x1=5?, x2=1.5714?; 最優(yōu)值為 341.4286。也不符合題意，所以舍
3.第三步
通過第二部對(duì)問題A的分支，我們可以進(jìn)一步暫定 z 的范圍為 0<= z <= 249，又因?yàn)榈诙街兄挥衳2的為小數(shù)，因此我們也就對(duì)問題B x2的范圍進(jìn)行限定為 (同上) ：
0=<x2<[2.1]=2,x2>[2.1]+1=3此時(shí)約束條件：
9*x1+7*x2<=56 7*x1+20*x2<=70 0<=x1<=4 2>x2>0 或 x2>3先對(duì)約束條件 0<=x1<=4,0<=x2<=2求解? 代碼如下：
clc clear allc=[40 90];%用目標(biāo)函數(shù)系數(shù)來確定 a=[9 7 ;7 20];%約束條件左邊約束 b=[56 70];%約束條件右邊系數(shù)aeq=[];%沒有等式約束，因此aeq,beq都為空 beq=[];lb=[0;0];%下限依然都為0 ub=[4;2];%x1上限為4，x2上限為2[x,y]=linprog(-c,a,b,aeq,beq,lb,ub); %這里沒有等式約束，對(duì)應(yīng)的矩陣為空矩陣 x %獲取對(duì)應(yīng)x1,x2 best=c*x%計(jì)算最優(yōu)值結(jié)果：此時(shí)的最優(yōu)解 x1=4?, x2=2?; 最優(yōu)值為 340。符合題意，所以暫時(shí)留著
?再對(duì)約束條件 0<=x1<=4,x2>=3求解? 代碼如下：
clc clear allc=[40 90];%用目標(biāo)函數(shù)系數(shù)來確定 a=[9 7 ;7 20];%約束條件左邊約束 b=[56 70];%約束條件右邊系數(shù)aeq=[];%沒有等式約束，因此aeq,beq都為空 beq=[];lb=[0;3];% x1下限依然都為0，x2下限為3 ub=[4;inf];%x1上限為4，x2無上限[x,y]=linprog(-c,a,b,aeq,beq,lb,ub); %這里沒有等式約束，對(duì)應(yīng)的矩陣為空矩陣 x %獲取對(duì)應(yīng)x1,x2 best=c*x%計(jì)算最優(yōu)值結(jié)果:此時(shí)的最優(yōu)解 x1=1.4286?, x2=3?; 最優(yōu)值為 327.1429。不符合題意，所以舍
4.第四步
通過上前的，我們可以進(jìn)一步確定z的范圍：0<= z <=241,此時(shí)我們已對(duì)問題A完成了完美分支，接下來我需對(duì)問題B再進(jìn)行分支
根據(jù)上面的結(jié)果，x2=1.5714為小數(shù)，因此我們對(duì)B中的x2進(jìn)行分支。
0=<x2<[1.5714]=1,x2>[1.5714]+1=2?此時(shí)條件約束：
9*x1+7*x2<=56 7*x1+20*x2<=70 x1>=5 1>x2>0 或 x2>2?先對(duì)x1>=5，1>x2>0求解，代碼如下：
clc clear allc=[40 90];%用目標(biāo)函數(shù)系數(shù)來確定 a=[9 7 ;7 20];%約束條件左邊約束 b=[56 70];%約束條件右邊系數(shù)aeq=[];%沒有等式約束，因此aeq,beq都為空 beq=[];lb=[5;0];% x1下限為5，x2下限為0 ub=[inf;1];%x1無上限，x2上限為1[x,y]=linprog(-c,a,b,aeq,beq,lb,ub); %這里沒有等式約束，對(duì)應(yīng)的矩陣為空矩陣 x %獲取對(duì)應(yīng)x1,x2 best=c*x%計(jì)算最優(yōu)值結(jié)果為：此時(shí)的最優(yōu)解 x1=5.4444?, x2=1?; 最優(yōu)值為 307.7778。不符合題意，所以舍
?再對(duì)x1>=5，x2>2求解，代碼如下：
clc clear allc=[40 90];%用目標(biāo)函數(shù)系數(shù)來確定 a=[9 7 ;7 20];%約束條件左邊約束 b=[56 70];%約束條件右邊系數(shù)aeq=[];%沒有等式約束，因此aeq,beq都為空 beq=[];lb=[5;2];% x1下限為5，x2下限為2 ub=[inf;inf];%x1無上限，x2無上限[x,y]=linprog(-c,a,b,aeq,beq,lb,ub); %這里沒有等式約束，對(duì)應(yīng)的矩陣為空矩陣 x %獲取對(duì)應(yīng)x1,x2 best=c*x%計(jì)算最優(yōu)值結(jié)果：此時(shí)無解
?
結(jié)論：綜上，最優(yōu)解：x1 = 4 ，x2 = 2 ；最優(yōu)值：340?
至于結(jié)果為負(fù)是因?yàn)閙atlab求解線性規(guī)劃轉(zhuǎn)化為求最小值
求解實(shí)現(xiàn)2：
?linprog函數(shù)及其參數(shù)的意義請(qǐng)看建模學(xué)習(xí)打卡第一天_菜菜笨小孩的博客-CSDN博客
簡(jiǎn)單介紹下，首先MATLAB中求解的是目標(biāo)函數(shù)是最小值的問題，但如果我們的目標(biāo)函數(shù)是求最大值，可以通過對(duì)目標(biāo)函數(shù)中每一項(xiàng)中乘以-1，將求最大值問題轉(zhuǎn)化為求最小值問題；A，b分別為不等式約束中的系數(shù)矩陣。Aeq和beq分別為等式約束中的系數(shù)矩陣，lb，和ub分別為每個(gè)變量的上下區(qū)間；最后c為目標(biāo)函數(shù)中各變量的系數(shù)矩陣。
但線性規(guī)范有兩種比較特殊的情況，即整數(shù)規(guī)劃和0-1整數(shù)規(guī)劃。在之前（不知MATLAB幾之前……），MATLAB是不能直接求解這兩種規(guī)劃的，bintprog函數(shù)可以用來求0-1整數(shù)規(guī)劃，但求解過程比較麻煩，而且最新版的MATLAB已經(jīng)遺棄了這個(gè)函數(shù)，同時(shí)提供了一個(gè)比較新的、專用于求解整數(shù)規(guī)劃和0-1整數(shù)規(guī)劃的函數(shù)——intlinprog。intlinprog的一個(gè)原型為：
[x,fval,exitflag]= intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
該函數(shù)的使用和linprog函數(shù)的使用十分相似，其僅僅在linprog函數(shù)的基礎(chǔ)上多了一個(gè)參數(shù)——intcon。在函數(shù)intlinprog中，intcon的意義為整數(shù)約束變量的位置。在本題中整數(shù)變量為x1，x2，所以intcon=[1,2]；fval為最優(yōu)化的值，一般是一個(gè)標(biāo)量，exitflag意為函數(shù)的退出標(biāo)志。
本題代碼如下：
clear all clcc=[-40 -90];%用目標(biāo)函數(shù)系數(shù)來確定 A=[9 7;7 20];%約束條件左邊約束 b=[56 70];%約束條件右邊系數(shù) %lb=zeros(2,1);% 生成一個(gè)2行1列的全0矩陣,很顯示，上面例子中的x,y的最小值為0 %intcon=[1,2];%整數(shù)約束變量的位置 %[x,fval,exitflag]=intlinprog(c,intcon,A,b,[],[],lb,[]) %用矩陣lb求不用設(shè)置上限lb=[0;0];%下限依然都為0 ub=[inf;inf];%x1沒有上限，x2沒有上限 intcon=[1,2];%整數(shù)約束變量的位置 [x,fval,exitflag]=intlinprog(c,intcon,A,b,[],[],lb,ub) %此時(shí)需要設(shè)置上下限結(jié)果2：最優(yōu)解：x1 = 4 ，x2 = 2 ；最優(yōu)值：340?
至于結(jié)果為負(fù)是因?yàn)閙atlab求解線性規(guī)劃轉(zhuǎn)化為求最小值
?求解實(shí)現(xiàn)3：
linprog函數(shù)及其參數(shù)的意義請(qǐng)看建模學(xué)習(xí)打卡第一天_菜菜笨小孩的博客-CSDN博客
簡(jiǎn)單介紹下，首先MATLAB中求解的是目標(biāo)函數(shù)是最小值的問題，但如果我們的目標(biāo)函數(shù)是求最大值，可以通過對(duì)目標(biāo)函數(shù)中每一項(xiàng)中乘以-1，將求最大值問題轉(zhuǎn)化為求最小值問題；A，b分別為不等式約束中的系數(shù)矩陣。Aeq和beq分別為等式約束中的系數(shù)矩陣，lb，和ub分別為每個(gè)變量的上下區(qū)間；最后c為目標(biāo)函數(shù)中各變量的系數(shù)矩陣。
1.首先我們需要定義一個(gè)滿足分支定理?xiàng)l件的函數(shù)：
%A,b,c分別對(duì)應(yīng)此題的不等式約束系數(shù)矩陣，不等式約束常數(shù)向量，目標(biāo)函數(shù)系數(shù)向量 %Aeq 等式約束系數(shù)矩陣, Beq 等式約束常數(shù)向量 %vlb 定義域的下界 vub 定義域的上界 %optXin 每次迭代的最優(yōu)x optF 每次迭代最優(yōu)的f值 iter迭代次數(shù)function [xstar, fxstar, flagOut, iter] = BranchBound1(c,A, b, Aeq, Beq, vlb, vub, optXin, optF, iter)global optX optVal optFlag;%將最優(yōu)解定義為全局變量iter = iter + 1;optX = optXin; optVal = optF;%更新迭代得到的值% options = optimoptions("linprog", 'Algorithm', 'interior-point-legacy', 'display', 'none');[x, fit, status] = linprog(c,A, b, Aeq, Beq, vlb, vub, []);%status返回算法迭代停止原因%status = 1 算法收斂于解x，即x是線性規(guī)劃的最優(yōu)解if status ~= 1%沒有找到最優(yōu)解，此分支不用繼續(xù)迭代下去，返回xstar = x;fxstar = fit;flagOut = status;return;endif max(abs(round(x) - x)) > 1e-3%找到的函數(shù)最優(yōu)解仍不是整數(shù)解if fit > optVal %此題求解的是max,此時(shí)的函數(shù)值大于之前解得的值xstar = x;fxstar = fit;flagOut = -100;return;endelse%此時(shí)解得的函數(shù)解為整數(shù)解，此分支求解結(jié)束，不再繼續(xù)向下求解，返回if fit > optVal %此題求解的是max,此時(shí)的函數(shù)值大于之前解得的值xstar = x;fxstar = fit;flagOut = -101;return;else %解出的值<之前解得的值，先放入全局變量中暫時(shí)存放optVal = fit;optX = x;optFlag = status;xstar = x;fxstar = fit;flagOut = status;return;endendmidX = abs(round(x) - x);%得到x對(duì)應(yīng)的小數(shù)部分notIntV = find(midX > 1e-3);%得到非整數(shù)的x的索引值，find()函數(shù)返回非0的索引值pXidx = notIntV(1);%得到第一個(gè)非整數(shù)x的下標(biāo)索引tempVlb = vlb;%臨時(shí)拷貝一份tempVub = vub;%fix(x) 函數(shù)將x中元素零方向取整if vub(pXidx) >= fix(x(pXidx)) + 1%原上界大于此時(shí)找到的分界的位置值tempVlb(pXidx) = fix(x(pXidx)) + 1;%將這個(gè)分界位置值作為新的下界參數(shù)傳入，進(jìn)一步遞歸[~, ~, ~] = BranchBound1(c,A, b, Aeq, Beq, tempVlb, vub, optX, optVal, iter + 1);endif vlb(pXidx) <= fix(x(pXidx))%原下界小于此時(shí)找到的分界的位置值tempVub(pXidx) = fix(x(pXidx));%將這個(gè)分界位置值作為新的上界參數(shù)傳入，進(jìn)一步遞歸[~, ~, ~] = BranchBound1(c,A, b, Aeq, Beq, vlb, tempVub, optX, optVal, iter + 1);endxstar = optX;fxstar = optVal;flagOut = optFlag; end2.調(diào)用上面函數(shù)對(duì)問題進(jìn)行求解：
%A,b,c分別對(duì)應(yīng)此題的不等式約束系數(shù)矩陣，不等式約束常數(shù)向量，目標(biāo)函數(shù)系數(shù)向量 %Aeq 等式約束系數(shù)矩陣, Beq 等式約束常數(shù)向量 %lb 定義域的下界 ub 定義域的上界clear all clcA = [9 7;7 20]; b = [56 70]; c = [-40,-90];%標(biāo)準(zhǔn)格式是求min，此題為max，需要轉(zhuǎn)換一下lb = [0; 0];%x值的初始范圍下界 ub=[inf;inf];%x值的初始范圍上界optX = [0; 0];%存放最優(yōu)解的x，初始迭代點(diǎn)(0,0) optVal = 0;%最優(yōu)解 [x, fit, exitF, iter] = BranchBound1(c,A, b,[], [], lb, ub, optX, optVal, 0)結(jié)果3：最優(yōu)解：x1 = 4 ，x2 = 2 ；最優(yōu)值：340?
至于結(jié)果為負(fù)是因?yàn)閙atlab求解線性規(guī)劃轉(zhuǎn)化為求最小值
總結(jié)：
綜上所述：最優(yōu)解：x1 = 4 ，x2 = 2 ；最優(yōu)值：340? 為正解；本次通過學(xué)習(xí)分支界定法求整數(shù)線性規(guī)劃，學(xué)了很長(zhǎng)時(shí)間，最終功夫不負(fù)有心人啊！！如果本文章有錯(cuò)誤問題，請(qǐng)大家指出！！感謝！
總結(jié)
以上是生活随笔為你收集整理的整数线性规划实现（matlab分枝界定法）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： etcd 启动分析_Etcd 架构与实现
- 下一篇： 【蓝桥杯每日一练】 巴斯卡三角形（杨辉三