Ошибка минимизации Python Linprog - симплекс метод

Question

Я использую библиотеку scipy.optimize.linprog для вычисления минимизации с помощью симплекс-метода. У меня есть два случая, когда я получаю ошибку:

"ValueError: Фаза 1 симплекс-метода не смогла найти выполнимое решение. Псевдообъективная функция оценивается как 3.1e-12, что превышает требуемый допуск 1e-12 для решения, которое считается" близким " достаточно "до нуля, чтобы быть основным решением. Рассмотрите возможность увеличения допуска более 3,1e-12. Если этот допуск неприемлемо велик, проблема может быть неосуществимой. ».

Может быть, кто-то найдет, где проблема.

Minimaze:     45x1 + 54x2 + 42x3 + 36x4

Subject to:   x1 + x2 + x3 + x4 = 1600
              30x1 + 60x2 + 70x3 + 80x4 = 100000
              30x1 + 40x2 + 0x3 + 20x4 = 30000

Код, который я написал:

A = np.array([[-30, -60, -70, -80], [-30, -40, 0, -20], [-1, -1, -1, -1]])
b = np.array([-100000, -30000, -1600])
c = np.array([45, 54, 42, 36])

res = linprog(c, A_eq=A, b_eq=b, bounds=(0, None))

Вот вторые примеры:

Minimize:     100x1 + 50x2 + 100x3

Subject to:   x1 + x2 + x3 = 3000
              28x1 + 14x2 + 10x3 <= 42000
              10x1 + 12x2 + 6x3 <= 24000
              30x1 + 20x2 + 30x3 >= 75000
              10x1 + 10x2 + 15x3 >= 36000

Вот код:

A_ub = np.array([[28, 14, 10], [10, 12, 6], [-30, -20, -30], [-10, -10, -15]])
b_ub = np.array([42000, 24000, -75000, -36000])
A_eq = np.array([[1, 1, 1]])
b_eq = np.array([3000])
c = np.array([100, 50, 200])

res = linprog(c, A_ub, b_ub, A_eq, b_eq, bounds=(0, None))

print('Optimal value:', res.fun, '\nX:', res.x)

Answer 1

Я проверил систему и решения действительно возможны. После прочтения этого поста кажется, что в linprog есть проблемы с плавающей запятой, явно проблема метода. Кажется, что передача method='interior-point' улучшает алгоритм.

У меня сработало в обоих случаях

Дело 1:

res = linprog(c, A_eq=A, b_eq=b, method='interior-point')
print('Optimal value:', res.fun, '\nX:', res.x)
>> Optimal value: 64090.8624935836 
X: [4.90908724e+02 1.50821194e-05 3.45454303e+02 7.63635788e+02]

Случай 2:

res = linprog(c, A_ub, b_ub, A_eq, b_eq, bounds=(0, None), method='interior-point')
print('Optimal value:', res.fun, '\nX:', res.x)
#output:
>> Optimal value: 449999.99988966336 
X: [ 377.22836393  748.5144238  1874.25721154]