Das Finden der optimalen binären Matrix über Integer-Programmierung in MATLAB

Question

ich die Lösung in optimal binary matrix versuchte Umsetzung Matlab-Funktion intlinprog auf einen Testeingang, wie im folgenden Code

a=[450;400;250;200]; % test input 
b=[750;500]; % test input 
n = 4; % length of a 
m = 2; % length of b 
oness=ones(m,1); 
f = (kron(a,oness))'; % objective function 
cont1=kron(eye(n),oness'); 
cont2=-cont1; 
cont3=-kron(a',eye(m)); 
A=[cont1;cont2;cont3]; 
bb=[ones(n,1);-zeros(n,1);-b]; 
lb = zeros(m*n,1); 
ub = [ones(m*n,1)]; % enforces binary 
intcon= [1,2,3,4,5,6,7,8]; % all variable should be integers 
Aeq = []; 
beq = []; 
x = intlinprog(f,intcon,A,bb,Aeq,beq,lb,ub) 

Allerdings erhalte ich die Nachricht

Intlinprog gestoppt, weil keine ganzzahligen Punkte die Bedingungen erfüllen.

Eine naheliegende optimale Lösung für diesen Testeingang wäre x = [0;1;1;0;1;0;0;0].

Wenn ich jedoch die Integritätsbedingungen über intcon=[] entferne, bekomme ich eine optimale Lösung. Warum kann die Funktion nicht die Minimallösung mit Integralbedingungen finden?

Answer 1

Ich hatte einen Fehler in der Problemdefinition, die ich jetzt behoben habe. Der Code gibt nun korrekt aus. Im Folgenden finden Sie den richtigen Code:

a=[450;400;250;200]; % test input 
b=[750;500]; % test input 
n = 4; 
m = 2; 
oness=ones(m,1); 
f = -(kron(a,oness))'; 
cont1=kron(eye(n),oness'); 
cont2=-cont1; 
cont3=kron(a',eye(m)); 
A=[cont1;cont2;cont3]; 
bb=[ones(n,1);-zeros(n,1);b]; 
lb = zeros(m*n,1); 
ub = [ones(m*n,1)]; % enforces binary 
intcon= 1:8; 
Aeq = []; 
beq = []; 
x = intlinprog(f,intcon,A,bb,Aeq,beq,lb,ub) 

Antwort:

x = [1;0;0;1;1;0;0;0] die gleiche optimales Ergebnis geben als

x = [0;1;1;0;1;0;0;0]