文章目錄

一、本次問(wèn)題

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é)：

一、本次問(wèn)題

1.利用第一天所學(xué)知識(shí)求解：

建模學(xué)習(xí)打卡第一天_菜菜笨小孩的博客-CSDN博客

代碼如下：

%打卡第一天
clear all
clc
c=[40 90];%用目標(biāo)函數(shù)系數(shù)來(lái)確定
a=[9 7 ;7 20];%不等式約束條件左邊約束
b=[56 70];%不等式約束條件右邊系數(shù)
aeq=[];%沒(méi)有等式約束，因此aeq,beq都為空
beq=[];
lb=[0;0];%沒(méi)有下限
ub=[inf;inf];%沒(méi)有上限
[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub);
x  %獲取對(duì)應(yīng)x1,x2
best=c*x%計(jì)算最優(yōu)值

2.本題理解：

由于問(wèn)題要求求解結(jié)果都為整數(shù)，所以第一問(wèn)結(jié)果錯(cuò)誤，那么我們?cè)撊绾吻蟮孟胍谜麛?shù)解呢？

（1）分支界定法

背景：

今天利用matlab來(lái)實(shí)現(xiàn)求解完全整數(shù)規(guī)劃問(wèn)題的分支定界法。這里求解的模型為目標(biāo)函數(shù)最小化模型:

基本理論（解題步驟）：

• 分支定界法：用以求解整數(shù)規(guī)劃問(wèn)題的一種方法。
• 求解步驟：
  首先我們規(guī)定求解的整數(shù)規(guī)劃問(wèn)題為A，相應(yīng)的線性規(guī)劃問(wèn)題為B

1. 對(duì)問(wèn)題B進(jìn)行求解
   1. 若B無(wú)可行解，則A也無(wú)可行解，停止計(jì)算
   2. 若B有最優(yōu)解，且符合整數(shù)條件，該最優(yōu)解為A的最優(yōu)解，停止計(jì)算
   3. 若B有最優(yōu)解，但不符合整數(shù)條件，記它的目標(biāo)函數(shù)值為z*，作為最優(yōu)值的下界
2. 找出問(wèn)題A的一個(gè)整數(shù)可行解，其目標(biāo)函數(shù)值作為最優(yōu)解的上界
3. 進(jìn)行迭代
   1. 分支，在B的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量x j x_jxj?，其值為b j b_jbj?，構(gòu)造兩個(gè)約束條件，，分別加入到問(wèn)題B中，形成兩個(gè)子問(wèn)題B1?、B2?。不考慮整數(shù)條件求解這兩個(gè)子問(wèn)題。即分支
   2. 定界。對(duì)每個(gè)后繼問(wèn)題表明其求解的結(jié)果，與其他問(wèn)題進(jìn)行比較，將最優(yōu)目標(biāo)函數(shù)值最小者（不包括問(wèn)題B）作為新的下界，在已符合整數(shù)條件的各分支中，找出目標(biāo)函數(shù)值最小者作為新的上界。
   3. 剪枝，將目標(biāo)函數(shù)值不在上界、下界中的分支剪去
   4. 重復(fù)1 2 3，直到得到最優(yōu)解
      注意事項(xiàng)：在對(duì)兩分支進(jìn)行分解時(shí)，優(yōu)先選擇目標(biāo)函數(shù)值最小的分支進(jìn)行分解。

分支定界法中，通過(guò)定界進(jìn)而進(jìn)行剪枝，對(duì)分支進(jìn)行了篩選，使我們僅在一部分可行解中尋求最優(yōu)解，而不是全部窮舉出來(lái)再尋找，其求解效率更高。

求解實(shí)現(xiàn)1：

linprog函數(shù)及其參數(shù)的意義請(qǐng)看建模學(xué)習(xí)打卡第一天_菜菜笨小孩的博客-CSDN博客

簡(jiǎn)單介紹下，首先MATLAB中求解的是目標(biāo)函數(shù)是最小值的問(wèn)題，但如果我們的目標(biāo)函數(shù)是求最大值，可以通過(guò)對(duì)目標(biāo)函數(shù)中每一項(xiàng)中乘以-1，將求最大值問(wèn)題轉(zhuǎn)化為求最小值問(wè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值的范圍兩種情況定為問(wèn)題A和問(wèn)題B，并分別為枝干求解

2.第二步

首先，我們對(duì)A問(wèn)題進(jìn)行分支，改變x1的約束條件，不改變x2的約束條件，即對(duì)x1分支得兩個(gè)子集

x1 =<[4.8092] = 4 ， x1 >= [4.8092] +1 = 5

約束條件變?yōu)椋?/p>

9*x1+7*x2<=56
7*x1+20*x2<=70
0<x1<4或x1>5  x2>0

先對(duì)0<x1<4求解??代碼如下：

clc
clear all

c=[40 90];%用目標(biāo)函數(shù)系數(shù)來(lái)確定
a=[9 7 ;7 20];%約束條件左邊約束
b=[56 70];%約束條件右邊系數(shù)

aeq=[];%沒(méi)有等式約束，因此aeq,beq都為空
beq=[];

lb=[0;0];%下限依然都為0
ub=[4;inf];%x1上限為4，x2沒(méi)有上限

[x,y]=linprog(-c,a,b,aeq,beq,lb,ub);  %這里沒(méi)有等式約束，對(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 all

c=[40 90];%用目標(biāo)函數(shù)系數(shù)來(lái)確定
a=[9 7 ;7 20];%約束條件左邊約束
b=[56 70];%約束條件右邊系數(shù)

aeq=[];%沒(méi)有等式約束，因此aeq,beq都為空
beq=[];

lb=[5;0];% x1的下限變成5，x2下限依然都為0
ub=[inf;inf];%x1，x2沒(méi)有上限
1
[x,y]=linprog(-c,a,b,aeq,beq,lb,ub);  %這里沒(méi)有等式約束，對(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.第三步

通過(guò)第二部對(duì)問(wèn)題A的分支，我們可以進(jìn)一步暫定 z 的范圍為 0<= z <= 249，又因?yàn)榈诙街兄挥衳2的為小數(shù)，因此我們也就對(duì)問(wèn)題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 all

c=[40 90];%用目標(biāo)函數(shù)系數(shù)來(lái)確定
a=[9 7 ;7 20];%約束條件左邊約束
b=[56 70];%約束條件右邊系數(shù)

aeq=[];%沒(méi)有等式約束，因此aeq,beq都為空
beq=[];

lb=[0;0];%下限依然都為0
ub=[4;2];%x1上限為4，x2上限為2

[x,y]=linprog(-c,a,b,aeq,beq,lb,ub);  %這里沒(méi)有等式約束，對(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 all

c=[40 90];%用目標(biāo)函數(shù)系數(shù)來(lái)確定
a=[9 7 ;7 20];%約束條件左邊約束
b=[56 70];%約束條件右邊系數(shù)

aeq=[];%沒(méi)有等式約束，因此aeq,beq都為空
beq=[];

lb=[0;3];% x1下限依然都為0，x2下限為3
ub=[4;inf];%x1上限為4，x2無(wú)上限

[x,y]=linprog(-c,a,b,aeq,beq,lb,ub);  %這里沒(méi)有等式約束，對(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.第四步

通過(guò)上前的，我們可以進(jìn)一步確定z的范圍：0<= z <=241,此時(shí)我們已對(duì)問(wèn)題A完成了完美分支，接下來(lái)我需對(duì)問(wèn)題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 all

c=[40 90];%用目標(biāo)函數(shù)系數(shù)來(lái)確定
a=[9 7 ;7 20];%約束條件左邊約束
b=[56 70];%約束條件右邊系數(shù)

aeq=[];%沒(méi)有等式約束，因此aeq,beq都為空
beq=[];

lb=[5;0];% x1下限為5，x2下限為0
ub=[inf;1];%x1無(wú)上限，x2上限為1

[x,y]=linprog(-c,a,b,aeq,beq,lb,ub);  %這里沒(méi)有等式約束，對(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 all

c=[40 90];%用目標(biāo)函數(shù)系數(shù)來(lái)確定
a=[9 7 ;7 20];%約束條件左邊約束
b=[56 70];%約束條件右邊系數(shù)

aeq=[];%沒(méi)有等式約束，因此aeq,beq都為空
beq=[];

lb=[5;2];% x1下限為5，x2下限為2
ub=[inf;inf];%x1無(wú)上限，x2無(wú)上限

[x,y]=linprog(-c,a,b,aeq,beq,lb,ub);  %這里沒(méi)有等式約束，對(duì)應(yīng)的矩陣為空矩陣
x    %獲取對(duì)應(yīng)x1,x2
best=c*x%計(jì)算最優(yōu)值

結(jié)果：此時(shí)無(wú)解

?

結(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ù)是最小值的問(wèn)題，但如果我們的目標(biāo)函數(shù)是求最大值，可以通過(guò)對(duì)目標(biāo)函數(shù)中每一項(xiàng)中乘以-1，將求最大值問(wèn)題轉(zhuǎn)化為求最小值問(wè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ù)可以用來(lái)求0-1整數(shù)規(guī)劃，但求解過(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
clc

c=[-40 -90];%用目標(biāo)函數(shù)系數(shù)來(lái)確定
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沒(méi)有上限，x2沒(méi)有上限
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ù)是最小值的問(wèn)題，但如果我們的目標(biāo)函數(shù)是求最大值，可以通過(guò)對(duì)目標(biāo)函數(shù)中每一項(xiàng)中乘以-1，將求最大值問(wèn)題轉(zhuǎn)化為求最小值問(wè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%沒(méi)有找到最優(yōu)解，此分支不用繼續(xù)迭代下去，返回
        xstar = x;
        fxstar = fit;
        flagOut = status;
        return;
    end
    
    if max(abs(round(x) - x)) > 1e-3%找到的函數(shù)最優(yōu)解仍不是整數(shù)解
        if fit > optVal   %此題求解的是max,此時(shí)的函數(shù)值大于之前解得的值
            xstar = x;
            fxstar = fit;
            flagOut = -100;
            return;
        end
        
    else%此時(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;
        end
    end
    midX = 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);
    end
    
    if 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);
    end
    xstar = optX;
    fxstar = optVal;
    flagOut = optFlag;
end

2.調(diào)用上面函數(shù)對(duì)問(wèn)題進(jìn)行求解：

%A,b,c分別對(duì)應(yīng)此題的不等式約束系數(shù)矩陣，不等式約束常數(shù)向量，目標(biāo)函數(shù)系數(shù)向量
%Aeq   等式約束系數(shù)矩陣,   Beq    等式約束常數(shù)向量
%lb   定義域的下界        ub    定義域的上界

clear all
clc

A = [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? 為正解；本次通過(guò)學(xué)習(xí)分支界定法求整數(shù)線性規(guī)劃，學(xué)了很長(zhǎng)時(shí)間，最終功夫不負(fù)有心人?。?！如果本文章有錯(cuò)誤問(wèn)題，請(qǐng)大家指出！！感謝！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-451095.html

到了這里，關(guān)于整數(shù)線性規(guī)劃實(shí)現(xiàn)（matlab分枝界定法）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！