lpsolve - невыполнимое решение, но у меня есть пример 1

Как найти решение

Давай займемся математикой.

Ваша проблема:

min x+y
s.t. 2x = 2y
     x + y = 1.11 x y
     x >= 1
     y >= 1

Первое ограничение 2x = 2y можно упростить до x=y. Теперь заменим всю задачу:

min 2*x
s.t. 2*x = 1.11 x^2
     x >= 1

И переставляем:

min 2*x
s.t. 1.11 x^2-2*x=0
     x >= 1

Из геометрии мы знаем, что 1.11 x^2-2*x образует открывающуюся вверх параболу с минимумом меньше нуля. Следовательно, точек ровно два. Они задаются квадратным уравнением: 200/111 и 0.

Только один из них удовлетворяет второму ограничению: 200/111.

Почему я не могу найти это ограничение с помощью решателя

Самый простой выход - сказать, что это потому, что член x^2 (x*y перед заменой является нелинейным). Но дело обстоит немного глубже. Нелинейные задачи можно легко решить, если они выпуклые. выпуклая задача - это задача, ограничения которой образуют единое непрерывное пространство, так что любая линия, проведенная между двумя точки в пространстве остаются в границах пространства.

Ваша проблема не выпуклая. Ограничение 1.11 x^2-2*x=0 определяет бесконечное количество точек. Никакие две из этих точек не могут быть соединены прямой линией, которая остается в пространстве, заданном ограничением, потому что это пространство искривлено. Если бы ограничение было вместо 1.11 x^2-2*x<=0, тогда пространство было бы выпуклым, потому что все точки можно было бы соединить прямыми линиями, которые остаются внутри него.

Невыпуклые задачи являются частью более широкого класса задач, называемых NP-Hard. Это означает, что нет (и, возможно, не может быть) простого способа решения проблемы. Мы должны быть умными.

Решатели, которые могут обрабатывать смешанное целочисленное программирование (MIP / MILP), могут решать многие невыпуклые задачи. эффективно, как и другие методы, такие как генетические алгоритмы. Но под капотом все эти техники полагаются на прославленные догадки и проверки.

Итак, ваш решатель терпит неудачу, потому что проблема невыпуклая, а ваш решатель недостаточно умен, чтобы использовать MIP, чтобы угадать и проверить свой путь к решению, ни достаточно умен, чтобы использовать квадратное уравнение.

Как тогда я могу решить проблему?

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

Но рассмотрим несколько обобщений проблемы:

(a) a x^3+b x^2+c x+d=0
(b) a x^4+b x^3+c x^2+d x+e =0
(c) a x^5+b x^4+c x^3+d x^2+e x+f=0

(а) имеет три потенциальных решения, которые необходимо проверить (точные решения сложны), (b) их четыре (хитрее), а (c) пять. Формулы для (a) и (b) намного сложнее, чем квадратная формула, и математики показали, что существует нет формулы для (c), которая может быть выражена с помощью" элементарных операций ". Вместо этого мы должны прибегать к прославленным догадкам и проверкам.

Таким образом, методы, которые мы использовали для решения вашей проблемы, не очень хорошо подходят для обобщения. Вот что значит жить в царстве невыпуклых и NP-сложных, и это хороший повод для финансирования исследований в математике, информатике и смежных областях.