ПРИНЯТИЕ РЕШЕНИЙ НА ОСНОВЕ МЕТОДОВ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

Классификация методов целочисленного программирования

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

Основные трудности решения задач целочисленного программирования связаны с эффектом округления чисел, возникающим при расчете на ЭВМ. Округление чисел неприемлемо для получения решения задачи целочисленного программирования по следующим причинам:

  • 1) решение в результате округления может быть получено в точке, не являющейся на самом деле оптимальной. Округление может привести к недопустимости решения, т. е. к выходу из области допустимых решений;
  • 2) округление не имеет смысла в том случае, если переменные в задаче целочисленного программирования — булевы, т. е. могут принимать только два значения: 0 или 1.

Существуют следующие методы решения задач целочисленного программирования:

  • 1) методы отсечений. К этой группе методов относится метод отсекающих плоскостей Гомори. Алгоритм метода состоит в следующем: сначала решается задача целочисленного программирования как задача линейного программирования без учета требования целочисленно- сти, а затем вводятся дополнительные ограничения, которые отсекают от области допустимых решений части плоскости, не содержащие целочисленных значений переменных;
  • 2) комбинаторные методы. К этой группе методов относится метод ветвей и границ. Существо метода заключается в переборе всех допустимых целочисленных решений. Основная трудность реализации метода состоит в формировании множества приемлемой мощности допустимых целочисленных решений;

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >