Целочисленное программирование

Целочисленное программирование связано с оптимизацией задач, в которых некоторые из переменных принимают дискретные значения в определенном интервале, а не все вещественные значения в этом интервале. Обычно эти значения являются целыми числами, что и послужило основанием для названия этого класса моделей.

Требование целочисленности возникает во многих прикладных задачах. Например, перевозка комплектующих со складов на заводы, или поиск кратчайшего пути через сеть дорог, где от переменных логично требовать целых значений. В производстве продукты зачастую неделимы, следовательно и производственный план выражается целыми числами.

Многие ситуации требуют задания логических данных, принимающих вид «да/нет», «использовать/не использовать», «назначить/не назначить». Очевидно, что эти решения являются дискретными, имеющими только два количественных значения. Они могут быть смоделированы бинарными переменными, которые приобретают значение 0 или 1. Примеры дискретных решений возникают, когда разработчики сталкиваются с выбором из конечного множества альтернатив, плановики ищут оптимальную последовательность действий, при транспортном планировании отыскиваются маршрутизации транспортных средств, обеспечивающие минимальные затраты - все это Когда оптимизационные модели содержат как целые, так и непрерывные переменные их называют смешанными. Такие модели представляют реальные ситуации, но наряду с адекватностью моделирования приходится сталкиваться с большими вычислительными трудностями. Лишь сравнительно небольшие задачи с целочисленными переменными могут быть решены оптимально. На первый взгляд это может показаться непонятным, учитывая возможность решать задачи линейного программирования с большим количеством переменных. Однако дискретный характер переменных порождает комбинаторный рост альтернатив. В худшем случае, для подтверждения оптимальности должно быть перебрано большинство из этих решений. При возрастании количества целых переменных в задаче, найти оптимальное решение становится очень сложно, или даже невозможно. В таких случаях приходится использовать эвристические методы, которые не гарантируют оптимальности найденного решения, но обеспечивают некоторое приемлемое приближение к оптимуму.

Рассмотрим процесс моделирования задач оптимизации с целыми переменными. Введем некоторые новые термины.

Дата добавления: 2015-07-15