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


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


Запись опубликована в рубрике Программирование. Добавьте в закладки постоянную ссылку.

Добавить комментарий

🇬🇧 Attention! Comments with URLs/email are not allowed.
🇷🇺 Комментарии со ссылками/email удаляются автоматически.