Эффективно получить теневые цены в scipy linprog - PullRequest
Новая
       10

Эффективно получить теневые цены в scipy linprog

0 голосов
/ 16 мая 2018

У меня огромная проблема с linprog: почти 1 тыс. Переменных и ограничений. Я могу рассчитать решение с scipy.optimize.linprog(method='simplex'), но мне нужны теневые цены (или альтернативные издержки) ~ 100 неравенств.

Я могу рассчитать их, добавив 1 к правой части неравенства и затем решив эту проблему. Затем я получаю теневую цену, вычтя значения целевых функций для обоих решений: shadow_price_i = f_max_original - f_max_i. Затем повторите 100 раз. Этот метод работает, но он мучительно медленный (1 час).

Могу ли я что-нибудь сделать, чтобы получить теневые цены быстрее? Может быть, какой-то трюк или функциональность мне не хватает ...

1 Ответ

0 голосов
/ 09 января 2019

Решите двойную проблему, и это даст вам все теневые цены с помощью еще одного звонка в linprog. Вот пример для стандартной проблемы LP: 

     c = np.array([400,200,250])  # negative of objective function
     b = [1000,300,625] # constraint bounds
     A = [[3, 1, 1.5], [0.8, 0.2, 0.3], [1, 1,1]]  # constraints
     x1_bnds =(0, None) # bounds on x1
     x2_bnds = (0,None) # bounds on x2
     x3_bnds = (0,None) # bounds on x
     result = opt.linprog(-c,A_ub=A, b_ub=b, bounds=(x1_bnds,x2_bnds, x3_bnds))

     dual_c = b
     dual_b = -1.0 * c
     dual_A = -1.0 * np.transpose(A)
     result = opt.linprog(dual_c,A_ub=dual_A, b_ub=dual_b, bounds=(x1_bnds,x2_bnds, 
           x3_bnds))
...