线性整数规划第二天

本文主要是介绍线性整数规划第二天，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一。问题

二。问题分析

线性规划问题（先不管整数条件）

可用matlab的linprog函数进行求解

三。代码及其实现

clc
clear all
c=[40 90];
a=[9,7;7,20];
b=[56,70];
aeq=[];
beq=[];
lb=[0;0];
ub=[inf;inf];
[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub);
x
best=c*x

 四。结果

Optimal solution found.


x =

    4.8092
    1.8168


best =

  355.8779

五。整数规划

利用分枝定界法

先给x1定界4<4.8092<5

x1小于4或x1大于5

x2保持约束不变

c=[40 90];
a=[9,7;7,20];
b=[56,70];
aeq=[];
beq=[];
lb=[0;0];
ub=[4;inf];
[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub);
x
best=c*x

c=[40 90];
a=[9,7;7,20];
b=[56,70];
aeq=[];
beq=[];
lb=[5;0];
ub=[inf;inf];
[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub);
x
best=c*x

输出结果：

Optimal solution found.


x =

    4.0000
    2.1000


best =

   349


Optimal solution found.


x =

    5.0000
    1.5714


best =

  341.4286

此时先把x1限定在4<x1再对x2定界x2=2.1，将x2限定在

x2小于2或大于3

c=[40 90];
a=[9,7;7,20];
b=[56,70];
aeq=[];
beq=[];
lb=[0;3];
ub=[4;inf];
[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub);
x
best=c*x

c=[40 90];
a=[9,7;7,20];
b=[56,70];
aeq=[];
beq=[];
lb=[0;0];
ub=[4;2];
[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub);
x
best=c*x

得到结果

Optimal solution found.


x =

    1.4286
    3.0000


best =

  327.1429


Optimal solution found.


x =

     4
     2


best =

   340

有一个整数解

再对x>5的情况进行x2的定界

x2的定界同上

c=[40 90];
a=[9,7;7,20];
b=[56,70];
aeq=[];
beq=[];
lb=[5;3];
ub=[inf;inf];
[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub);
x
best=c*x

c=[40 90];
a=[9,7;7,20];
b=[56,70];
aeq=[];
beq=[];
lb=[5;0];
ub=[inf;2];
[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub);
x
best=c*x

输出结果：

No feasible solution found.

Linprog stopped because no point satisfies the
constraints.


x =

     []

错误使用  * 
用于矩阵乘法的维度不正确。请检查并确保第一个矩阵中的列数与第二个矩阵中
的行数匹配。要执行按元素相乘，请使用 '.*'。

出错 homework2 (line 67)
best=c*x

出错 run (line 91)
evalin('caller', strcat(script, ';'));

均无可行解

综合上面情况：

最优解为

x =

     4
     2


best =

   340

这篇关于线性整数规划第二天的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！