линейная оптимизация с помощью scipy / simplex не обеспечивает оптимального - PullRequest
Новая
       96

линейная оптимизация с помощью scipy / simplex не обеспечивает оптимального

1 голос
/ 02 августа 2020

Я пытаюсь решить проблему, описанную Саулом Грассом в его книге «Иллюстрированное руководство по линейному программированию», стр. 12ff Проблема транспортировки.

Холодильники должны быть доставлены в 3 магазина (S1, S2, S3)
в следующих количествах (10,8,7)
Транспортные расходы от заводов F1, F2 до магазинов:
F1 (8,6,10) = 11 (общая отгрузка из F1)
F2 (9,5,7) = 14 (общая отгрузка из F2)

Саул Грасс дает целевую функцию для минимизации как:

8x_11 + 6x_12 + 10x_13 + 9x_21 + 5x_22 + 7x_23

и ограничения c как:
x_11 + x_12 + x_13 + 0x_21 + 0x_22 + 0x_23 = 11
0x_11 + 0x_12 + 0x_13 + x_21 + x_22 + x_23 = 14
x_11 + 0x_12 + 0x_13 + x_21 + 0x_22 + 0x_23 = 10
0x_11 + x_12 + 0x_13 + 0x_21 + x_22 + 0x_23 = 8
0x_11 + 0x_12 + x_13 + 0x_21 + 0x_22 + 1018 * 23 * = 7 1019 * Его лучшее решение - [10,1,0,0,7,7]:

10 x 8x_11 + 1 x 6x_12 + 0 x 10x_13 + 0 x 9x_21 + 7 x 5x_22 + 7 x 7x_23 = 170

Я попытался решить эту проблему с помощью scipy, но получил другой результат, который не так хорош, как решение Сола Грасса (204 против 170). Что не так в моем решении?

Мой код: 

import numpy as np
from scipy.optimize import linprog

c = [-8,-6,-10,-9,-5,-7] 
A = [[1,1,1,0,0,0],[0,0,0,1,1,1],[1,0,0,1,0,0],[0,1,0,0,1,0],[0,0,1,0,0,1]] 
b = [11,14,10,8,7]
x0_bounds = (0, None)
x1_bounds = (0, None)
x2_bounds = (0, None)
x3_bounds = (0, None)
x4_bounds = (0, None)
x5_bounds = (0, None)

res = linprog(c, A_ub=A, b_ub=b,  bounds=(x0_bounds, x1_bounds,x2_bounds,x3_bounds, x4_bounds,x5_bounds), method='simplex', options={"disp": True})
print(res)

Мой результат: 

Optimization terminated successfully.
         Current function value: -204.000000 
         Iterations: 4
     fun: -204.0
 message: 'Optimization terminated successfully.'
     nit: 4
   slack: array([0., 0., 0., 0., 0.])
  status: 0
 success: True
       x: array([ 0.,  4.,  7., 10.,  4.,  0.])

1 Ответ

2 голосов
/ 02 августа 2020

Видя , do c для параметров scipy.optimize.linprog, A_eq и b_eq следует использовать, когда заданы ограничения равенства . И c должно быть [8, 6, 10, 9, 5, 7], а не [-8, -6, -10, -9, -5, -7], поскольку scipy.optimize.linprog минимизировать целевую функцию.

Следовательно, вы можете сделать следующее: 

from scipy.optimize import linprog

c = [8, 6, 10, 9, 5, 7]
A = [[1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1], [1, 0, 0, 1, 0, 0], [0, 1, 0, 0, 1, 0], [0, 0, 1, 0, 0, 1]]
b = [11, 14, 10, 8, 7]
x0_bounds = (0, None)
x1_bounds = (0, None)
x2_bounds = (0, None)
x3_bounds = (0, None)
x4_bounds = (0, None)
x5_bounds = (0, None)

res = linprog(c, A_eq=A, b_eq=b, bounds=(x0_bounds, x1_bounds, x2_bounds, x3_bounds, x4_bounds, x5_bounds),
              method='simplex', options={"disp": True})
print(res)

который печатает 

Optimization terminated successfully.
         Current function value: 170.000000  
         Iterations: 6
     con: array([0., 0., 0., 0., 0.])
     fun: 170.0
 message: 'Optimization terminated successfully.'
     nit: 6
   slack: array([], dtype=float64)
  status: 0
 success: True
       x: array([10.,  1.,  0.,  0.,  7.,  7.])
...