Линейное программирование, неожиданное решение с ограничением равенства

Question

Я пытаюсь выяснить, что не так с моей реализацией, я ожидаю, что результат будет [5, 10], я не понимаю, как он получает [7.5, 7.5], x1 должен быть половиной x2.

from scipy.optimize import linprog 
import numpy as np 

c = [-1, -1] 

A_eq = np.array([ 
    [1, 0.5], 
    [1, -0.5], 
]) 

b_eq = [15, 0] 

x0_bounds = (0, None) 
x1_bounds = (0, None) 

res = linprog(
    c, 
    A_eq=A_eq.transpose(), 
    b_eq=b_eq, 
    bounds=(x0_bounds, x1_bounds), 
    options={"disp": True}) 

print res.x 
# =>                                             
# Optimization terminated successfully.                                    
#   Current function value: -15.000000                                   
#   Iterations: 2                                        
# [ 7.5 7.5]                                     

Обновление от автора:

Как было сказано матрица транспонирования не требуется. Проблема была в самой матрице, для того, чтобы получить желаемый результат, который [5, 10], он должен быть:

A_eq = np.array([ 
    [1, 1], 
    [1, -0.5], 
]) 

Answer 1

согласно scipy linprog docs:

Минимизация: с^Т * х

условии:

A_ub * х = < b_ub

A_eq * х == b_eq

Итак, вы теперь решить следующие уравнения:

Minimize -x1 -x2 

ПОДЧИНЯЮЩИХСЯ *

x1 + x2 = 15 (i) 
0.5 * x1 - 0.5 * x2 = 0 (ii) 

Теперь, (б) влечет x1 = x2 (так что ваше желаемое решение необоснованно), а затем (i) фиксирует x1 = x2 = 7.5. Таким образом, решение, возвращенное linprog(), действительно верно. Поскольку вы ожидаете другого результата, возможно, вам стоит взглянуть на то, как вы перевели свою проблему в код, так как я думаю, что там вы найдете как проблему, так и решение.

*) Поскольку вы берете транспонирование.

Answer 2

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

x1 + x2 == 15 
0.5 * x1 - 0.5 * x2 == 0 

minimize -x1 -x2 

Так, очевидно, у вас есть x1 == x2 (второе ограничение), и, таким образом x1 = x2 = 7.5 (первое ограничение).

Глядя на ваш вопрос, вы, вероятно, не хотите транспонировать A:

res = linprog(
    c, 
    A_eq=A_eq, 
    b_eq=b_eq, 
    bounds=(x0_bounds, x1_bounds), 
    options={"disp": True} 
) 

Почему дает вам проблему:

x1 + 0.5 * x2 == 15 
x1 - 0.5 * x2 == 0 

minimize -x1 -x2 

И вы получите x1 = 7.5 и x2 = 15 (единственные возможные значения).