Метаматические модели, приводящие к задачам целочисленного программирования

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

Определить максимальное (минимальное) значение функции:

при ограничениях

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

При наличии в задаче линейного программирования двух переменных, а в системе ограничений – неравенств она может быть решена графическим методом.

Целочисленное программирование – общая характеристика задач и методов их решения

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

Задача целочисленного программирования формулируется следующим образом:

Найти такое решение план Х=(х₁, х₂,…, х_n), при котором линейная функция принимает максимальное или минимальное значение при ограничениях

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

Понятия о методе ветвей и границ.

Метод ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор. Пока не получено оптимальное целочисленное решение исходной задачи.

Графический метод

При наличии в задаче линейного программирования двух переменных, а в системе ограничения – неравенств, она может быть решена графическим методом без требований целочисленных переменных.

Если оптимальное решение этой задачи является целочисленным, то оно и является оптимальным для исходной задачи.

⇐ Предыдущая12345Следующая ⇒

Поделиться: