Решите недоопределенную систему уравнений в matlab

Question

У меня есть система неопределенных линейных уравнений Ax = b (т. Е. Более неизвестных, чем уравнения), которые я бы так хотел решить в Matlab.

Я знаю, что это обычно означает бесконечное количество решений, но я также знаю, что решения должны быть целыми положительными и меньше определенного числа. Могу ли я найти все решения, отвечающие этим дополнительным требованиям?

Эта проблема возникает из-за наличия неизвестной матрицы, где я знаю сумму каждой строки и столбца.

например. неизвестная матрица найти

0 3 2 0 
0 2 4 1 
2 1 0 0 

суммы Роу известные

5 
7 
3 

Колонка Суммы знаю

2 6 6 1 

Я попытался lsqnonneg (А, Ь) функция, которая дает только один верное решение

0 0 5 0 
0 6 0 1 
2 0 1 0 

Answer 1

То, что у вас есть, часто называется integer-linear programming, и он известен как NP-hard (что означает, что вы не задерживаете дыхание, пока не появится решение).

Если вы хотите решить эту проблему без целочисленности, у вас есть линейная программа и, следовательно, вы можете использовать linprog. Если вы думаете о неизвестных матрицах как вектор неизвестных элементов, то столбец сумма только

col_sum = kron(eye(4),[1,1,1]); 

col_sum = 

    1  1  1  0  0  0  0  0  0  0  0  0 
    0  0  0  1  1  1  0  0  0  0  0  0 
    0  0  0  0  0  0  1  1  1  0  0  0 
    0  0  0  0  0  0  0  0  0  1  1  1 

Аналогично, строка сумма

row_sum = repmat(eye(3),1,4); 

row_sum = 

    1  0  0  1  0  0  1  0  0  1  0  0 
    0  1  0  0  1  0  0  1  0  0  1  0 
    0  0  1  0  0  1  0  0  1  0  0  1 

Это ваши ограничения равенства и у вас есть ограничения неравенства, но только связанный с неизвестными значениями. linprog может связать их как дополнительные аргументы. Однако у вас нет объективной функции, которая может составлять что-то вроде суммы всех неизвестных, сведенных к минимуму, или одна из них или любая другая линейная задача, или вы можете оставить ее пустой, и вы получите какой-либо возможный результат.

Aeq = [col_sum;row_sum] 
beq = [2 6 6 1 5 7 3]'; 

X = linprog([],[],[],Aeq,beq,zeros(12,1),10*ones(12,1))% 0 <= vars <= 10 

X = reshape(X,3,4) 

X = 

    0.6550 2.0160 2.0160 0.3130 
    1.1192 2.5982 2.5982 0.6845 
    0.2258 1.3859 1.3859 0.0025 


>> sum(X,1) 

ans = 

    2.0000 6.0000 6.0000 1.0000 

>> sum(X,2) 

ans = 

    5.0000 
    7.0000 
    3.0000 

Если у вас есть некоторые записи, которые гарантированно быть равен нулю и т.д. Тогда это могло бы быть возможно, что все решения вынуждены быть целыми числами. В противном случае вам нужно иметь невыпуклые конкретные решатели целочисленного программирования, например given here

Answer 2

Оптимизация 'fmincon' подход мог бы быть в состоянии помочь вам - это позволяет нелинейных неравенств быть добавлены перед запуском: http://uk.mathworks.com/help/optim/ug/nonlinear-inequality-constraints.html

EDIT: Просто заметил использование строчных сумм, чтобы помочь определить оптимизированный ответ, так что ответ я дал бы ограниченного использования. Тем не менее, все равно стоит сделать снимок.