Задача на целочисленное программирование с решением

Решаем задачу целочисленного программирования. Еще эту задачу задачу называют — математическая 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.

This entry was posted in Программирование. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *