1

Задачка решается с помощью системы неравенств. Есть несколько неравенств, и ответом будет наибольшее значение X и Y, при которых R = X+Y максимально Ексель например легко даёт ответ с помощью поиска решений. Но в питоне такой опции, как я понимаю, нет. Можете Подсказать, как возможно реализовать алгоритм решения такой задачи? Вот неравенства для примера:

2X+3Y <= 9;  
3X+2Y <= 13;  
x-y <= 1;  
y <= 2;
KAS
  • 33

1 Answers1

3

Вопрос можно свести к задаче линейного программирования: найти наибольшую сумму x+y (наименьшее -x-y) при заданных ограничениях на x,y:

>>> import scipy.optimize
>>> scipy.optimize.linprog([-1,-1], A_ub=[[2,3],[3,2],[1,-1],[0,1]], b_ub=[9,13,1,2])
     fun: -3.8
 message: 'Optimization terminated successfully.'
     nit: 2
   slack: array([0. , 3. , 0. , 0.6])
  status: 0
 success: True
       x: array([2.4, 1.4])

То же самое, используя PuLP пакет:

import pulp  # $ pip install pulp

problem = pulp.LpProblem("test1", pulp.LpMaximize)
x = pulp.LpVariable('x')
y = pulp.LpVariable('y')
problem += x + y  # maximize sum
problem += 2*x + 3*y <= 9
problem += 3*x + 2*y <= 13
problem += x - y <= 1
problem += y <= 2
problem.solve()
for v in problem.variables():
    print(v.name, "=", v.varValue)

Оба решения находят: X=2.4, Y=1.4.

jfs
  • 52,361
  • А без доп.модулей возможно это решить? В версии, в которой мы работаем, пишет, что такие модули не найдены( – KAS May 10 '18 at 09:10
  • @KAS: если нет модулей, значит поставить следует. – jfs May 10 '18 at 12:22
  • Я понимаю, но мы показываем задачи преподавателю на вузовских компьютерах, и на них я ничего поставить не могу к сожалению – KAS May 10 '18 at 12:29
  • @KAS если вы можете свой код копировать, значит можете поставить. Если не ясно как можно to vendor зависимости, задайте отдельный вопрос. – jfs May 10 '18 at 12:40
  • ладно, снова большое спасибо) Не подскажите еще по Вашему коду, что делает строка for v in problem.variables(): и зачем нужны + перед равно в "проблемах"? – KAS May 10 '18 at 13:01
  • @KAS: если не ясно чем = от += в Питоне отличаются, то задайте отдельный вопрос. Если не знаете, что for-цикл делает в Питоне, то [для экономии времени] лучше начать с любого учебника по Питону (это самые, самые, самые основы). Дополнительно: Различия между циклами for и while, Как реализован цикл for? Почему for x in a: x=1 не меняет a список – jfs May 10 '18 at 13:14
  • Нет, я знаю это конечно, что += добавляет правую часть к текущему значению функции, просто мне не ясно, зачем это нужно в данном случае. Или неравенства можно суммировать? Тогда понятно. А в цикле я не понял, что значит problem.variables() и что вообще этот цикл делает, если внутри него только строка print? Ну ладно в общем, извините что ерундой отвлекаю – KAS May 10 '18 at 13:27
  • @KAS: problem.variables() это коллекция переменных задачи (x, y в этом случае) -- на английском это очевидно. print() здесь печатает решение: x = 2.4, y = 1.4¶ Каждая problem += конструкция используется, чтобы задачу по кускам собрать (более наглядный метод постановки задачи вместо использования матрицы A_ub и вектора b_ub как в первом примере -- они равнозначны)¶ Если написать problem = вместо problem +=, то problem будет указывать не на pulp.LpProblem() объект, а на объект создаваемый самым последним неравенством (с типом, выражающим ограничение в pulp) – jfs May 10 '18 at 13:41
  • Я знаю, что делает принт) Меня просто удивило, зачем вообще вводить этот цикл, когда вроде как проще написать print x.varValue print y.varValue. Ну видимо это слишком по-любительски, но смотрится все-таки попроще – KAS May 10 '18 at 19:02