Решаем задачу целочисленного программирования. Еще эту задачу задачу называют — математическая NP-оптимизация, где все числа могут принимать только целые значения (например, 0 и 1).
Условие задачи:
z =15x — y -> max
10x – y <= 50
x + y <= 32,5
x >= 0, y >= 0,
Следует ограничиваться только целочисленными значениями переменных x и y.
Проведем сначала графическое решение задачи:
График будет выглядеть примерно так, кроме того, мы можем проверить решение этой задачи арифметическим способом.
Итак, мы имеем решение x = 7,5 и y = 25. Однако, не следует даже считать дальше и находить z, так как это решение недопустимо, поскольку 7,5 – не целое число, а нам по условию нужно решить задачу ограничиваясь целочисленными значениями переменных.
Тогда, чтобы решить эту задачу, нужно найти возможные целые значения переменных x и y. Чем мы сейчас и займемся; для этого делим исходную задачу на две подзадачи (a и b) и выбираем переменную с не целочисленными значениями (вводим новые ограничения x <= 7 и y >= 8):
Подзадача a:
z = 15x — y -> max
10x – y <= 50
x + y <= 32,5
x <= 7
x >= 0
y >= 0
Графическое решение:
Подзадача b:
z = 15x — y -> max
10x – y <= 50
x + y <= 32,5
x >= 8
x >= 0
y >= 0
Графическое решение:
Выводы и окончательное решение общей задачи:
В подзадаче «а» мы получаем: x = 7, y = 20, значит zmax = 85; а задача «b» не имеет решения (как вы можете убедиться на рисунке). А значит целочисленное решение подзадачи «а» и будет ответом всей задачи.
Ответ: x = 7, y = 20, zmax = 85.
