Рассмотрим матрицу [4x8] «A» и матрицу [1x8] «B».Мне нужно проверить, существует ли значение «X», такое, что
[A]^T * [X] = [B]^T exists for any x >= 0 { X is a [4X1] matrix, T = transpose }
Теперь вот уловка / утомительная часть.Матрица A всегда имеет 1 в качестве диагонали.A11,A22,A33,A44 = 1 Эту матрицу можно рассматривать как две половины, причем первая половина - это первые 4 столбца, а вторая половина - вторые 4 столбца, как показано ниже:
1 -1 -1 -1 1 0 0 1
A = -1 1 -1 0 0 1 0 0
-1 -1 1 0 1 0 0 0
-1 -1 -1 1 1 1 0 0
Каждая строка в первой половине может иметьдва или три -1, и если у него есть два -1, то соответствующая строка во второй половине должна иметь одну «1», или, если в какой-либо строке есть три -1, во второй половине матрицы должно быть два «1».Общая цель состоит в том, чтобы сумма каждой строки была равна 0.
Теперь B - это матрица [1x8], которую также можно рассматривать как две половины следующим образом:
B = -1 -1 0 0 0 0 1 1
Здесьв первой половине может быть один, два, три или четыре -1, а во второй половине должно быть одинаковое количество единиц.Это должно быть сделано в комбинациях. Например, если в первой половине есть два -1, они могут быть размещены в 4, выберите 2 = 6 способов, и для каждого из них будет 6 способов разместить 1 во второй половине, которыев общей сложности 6 * 6 = 36 способов.то есть 36 различных значений для B, если в первой половине есть два -1.Размещение 1 в матрице А также должно быть таким же.Я мог бы подумать о том, чтобы сделать это, рассмотрев valarray или что-то в этом роде и составить матрицы A и B, но я не знаю, что делать.
Теперь для каждого A я должен проверить его с каждой комбинацией B, чтобы увидеть, существует ли
[A]^T * [X] = [B]^T
Я пытаюсь доказать, что результат, который мне нужен, мне нужензнать, существует ли такой X или нет.Я очень запутался в реализации этого.Любые предложения приветствуются.Это подпадает под понятие линейного программирования в математике.Я хочу это либо в C ++, либо в Matlab.Любые другие языки также приемлемы, но я знаком только с этими двумя.Заранее спасибо.
Обновление:
Вот мой ответ на эту проблему:
clear;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%# Generating all possible values of vector B
%# permutations using dec2bin (start from 17 since it's the first solution)
vectorB = str2double(num2cell(dec2bin(17:255)));
%# changing the sign in the first half, then check that the total is zero
vectorB(:,1:4) = - vectorB(:,1:4);
vectorB = vectorB(sum(vectorB,2)==0,:);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%# generate all possible variation of first/second halves
z = -[0 1 1; 1 0 1; 1 1 0; 1 1 1]; n = -sum(z,2);
h1 = {
[ ones(4,1) z(:,1:3)] ;
[z(:,1:1) ones(4,1) z(:,2:3)] ;
[z(:,1:2) ones(4,1) z(:,3:3)] ;
[z(:,1:3) ones(4,1) ] ;
};
h2 = arrayfun(@(i) unique(perms([zeros(1,4-i) ones(1,i)]),'rows'), (1:2)', ...
'UniformOutput',false);
%'# generate all possible variations of complete rows
rows = cell(4,1);
for r=1:4
rows{r} = cell2mat( arrayfun( ...
@(i) [ repmat(h1{r}(i,:),size(h2{n(i)-1},1),1) h2{n(i)-1} ], ...
(1:size(h1{r},1))', 'UniformOutput',false) );
end
%'# generate all possible matrices (pick one row from each to form the matrix)
sz = cellfun(@(M)1:size(M,1), rows, 'UniformOutput',false);
[X1 X2 X3 X4] = ndgrid(sz{:});
matrices = cat(3, ...
rows{1}(X1(:),:), ...
rows{2}(X2(:),:), ...
rows{3}(X3(:),:), ...
rows{4}(X4(:),:) );
matrices = permute(matrices, [3 2 1]); %# 4-by-8-by-104976
A = matrices;
clear matrices X1 X2 X3 X4 rows h1 h2 sz z n r
options = optimset('LargeScale','off','Display','off');
for i = 1:size(A,3),
for j = 1:size(vectorB,1),
X = linprog([],[],[],A(:,:,i)',vectorB(j,:)');
if(size(X,1)>0) %# To check that it's not an empty matrix
if((size(find(X < 0),1)== 0)) %# to check the condition X>=0
if (A(:,:,i)'* X == (vectorB(j,:)'))
X
end
end
end
end
end
Я получил его с помощью пользователей stackoverflow,Единственная проблема заключается в том, что функция linprog генерирует множество исключений в каждой итерации вместе с полученными ответами.Исключение составляет:
(1)Exiting due to infeasibility: an all-zero row in the constraint matrix does not have a zero in corresponding right-hand-side entry.
(2) Exiting: One or more of the residuals, duality gap, or total relative error has stalled: the primal appears to be infeasible (and the dual unbounded).(The dual residual < TolFun=1.00e-008.
Что это значит.Как я могу преодолеть это?