Инструменты пользователя

Инструменты сайта


examination:mo:question11

Вопрос 11. Задачи целочисленного программирования. Различные подходы к решению.

Целочисленное программирование - раздел математического программирования, в котором на все или некоторые переменные дополнительно накладывается ограничение целочисленности.

Простейший метод решения задач целочисленного программирования - сведение ее к задаче линейного программирования с добавлением проверки на целочисленность.

Условно методы решения задач целочисленного программирования можно разделить на 3 основных группы:

  1. Методы отсечения
  2. Комбинаторные методы
  3. Приближенные методы

Процедура решения задач методами отсечения осуществляется следующим образом:

  1. Решается задача линейного программирования без каких-либо ограничений целочисленности, если в решении хотя бы одна переменнная или функция цели является дробной, то →
  2. Добавляется новое ограничение, отсекающее область допустимых значений, которая не содержит ни одного целочисленного решения (то есть отбрасываем дробную часть одной или нескольких переменных, которые являются дробными)
  3. Заново вычисляем и проверяем полученные значения на оптимальность

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

В системе координат находят область допустимых решений, строят вектор С и линию уровня. перемещая линию уровня по направлению С для задач на максимум, определяют наиболее удаленную от начала координат точку и ее координаты. В случае, когда координаты этой точки нецелочисленные, в области допустимых решений строят целочисленную решетку и находят на ней такие целые числа x1 и x2, которые удовлетворяют системе ограничений и при которых значение целевой функции наиболее близко к экстремальному нецелочисленному решению. Координаты такой вершины являются целочисленным решением. Аналогично решается задача на минимум.

Метод ветвей и границ

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

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

examination/mo/question11.txt · Последние изменения: 2014/01/15 12:19 (внешнее изменение)