Как решить недоопределенную систему неравенств с кратными переменными

Question

Я пытаюсь найти способ решить систему линейных неравенств, таких как:

c>0
y+c<0
x+c>0
x+y+c<0
w+c>0
w+y+c>0
w+x+c>0
w+x+y+c<0

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

Answer 1

В общем, существуют бесконечные решения недостаточно определенной системы. Однако вы можете найти наименьшее решение адаптированной проблемы. В этом случае вы можете сделать следующее:

Вы сначала векторизуете свою проблему

x = [c y x w].';
M = [1 0 0 0
     1 1 0 0
     1 1 1 0
     1 0 0 1
     1 1 0 1
     1 0 1 1
     1 1 1 1];
y = [ 1 -1 1 -1 1 1 1 -1].';

Вы можете установить значения y Как ты хочешь. Их нужно только удовлетворять условиям вашего неравенства (т.е. y(1)>0, y(2)<0,...). Теперь вы решаете недоопределенную систему Mx = y.

Наименьшее решение этой системы можно найти с помощью псевдообратного M.

x = M.'(M*M.')^(-1)*y;

Если вы выбрали y В соответствии с вашими ограничениями решение этой проблемы также является решением вашей проблемы.

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