Решение системы линейных неравенств в Matlab и получение всего набора решений

Question

Я хочу решить систему линейных неравенств в Matlab, где неизвестные x(1), x(2), x(3), x(4), Я хочу весь набор решений x(1), x(2), x(3), x(4), Следовательно, я не могу использовать linprog потому что это дает мне только одну возможную точку.

Пояснение: этот вопрос https://stackru.com/questions/37258835/how-to-set-the-objective-function-when-using-linprog-in-matlab-to-solve-a-system был о linprogr что, однако, дает только одно возможное решение. Здесь я спрашиваю, как найти весь набор решений.

Это множество неравенств. Любое предложение?

5x(1)+3x(2)+3x(3)+5x(4)<5
-5x(1)-3x(2)-3x(3)-5x(4)<-3
-x(2)-x(3)<0
x(2)+x(3)<1
-x(1)-x(4)<0
x(1)+x(4)<1
-3x(3)-5x(4)<-1
3x(3)+5x(4)>3
x(3)<1
-x(3)<0
x(4)<1
-x(4)<0
-5x(1)-3x(2)<0
5x(1)+3x(2)<2
x(2)<1
-x(2)<0
x(1)<1
-x(1)<0

Answer 1

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

Вот несколько ссылок на инструменты, которые могут сделать это:

• CDD
• госзакупках

Другой подход заключается в перечислении оптимальных базисов с использованием дополнительных двоичных переменных. (У вас нулевая цель, так что это становится эффективным: перечисление всех возможных баз LP). Такой подход делает проблему MIP. Мы можем перечислить это с помощью алгоритма:

1. решить мип
2. если это невозможно: остановите
3. добавить ограничение, чтобы запретить текущую точку
4. перейти к шагу 1

Вот ссылка, иллюстрирующая этот подход для перечисления всех оптимальных базисов (непрерывной) задачи ЛП.

Отметим, что перечислить все целочисленные решения системы неравенств проще. Многие инструменты программирования с ограничениями сделают это автоматически. Кроме того, мы можем использовать технику "плоскости резания", описанную выше.