Решение оптимизационных задач дискретного программирования

     Пусть — конечное множество точек, — «расстояние» от точки i до точки j, — матрица «расстояний». Маршрут z  коммивояжера — это любая перестановка точек из P, . Длина l(z) маршрута z  есть сумма соответствующих элементов матрицы :

     

  

     Пусть Z — множество всех маршрутов. Необходимо найти маршрут такой, что

     

  .

     В этой задаче G = Z, . Оценим величину , пользуясь первым членом асимптотического представления Стирлинга для факториала

     

.

     Пусть  Тогда

     

отсюда  видно, что трудоемкость вычислений резко растет с ростом размерности  задачи. 
 
 

1.2. Особенности задач

     Невозможность выполнения большого перебора на ЭВМ.

     Многие  из методов решения задач дискретной оптимизации основаны на идее перебора вариантов, качество алгоритма оценивается числом точек x для которых вычислялись значения f(x) или значения некоторых других функций. Выше было отмечено, что объем вычислительной работы резко возрастает с ростом числа переменных. Поэтому перебор большого числа вариантов принципиально невозможен ни при каком быстродействии ЭВМ, хотя рост быстродействия ЭВМ позволяет решать задачи, решение которых на ЭВМ с более низким быстродействием не представлялось возможным. 

     Нерегулярность.

     Дискретные  задачи математического программирования входят в класс нерегулярных задач.

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

     Трудности при определении окрестности.

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

2. Основные сведения о методах решения задач 

     Выделим следующие (основные) методы решения  задач:

     — метод отсечения для задач (частично) целочисленного линейного программирования;

     — комбинаторные методы;

     — приближенные методы. 

     Методы  отсечения.

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

  целые.

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

     Основная  идея методов отсечения, элементы алгоритма.

       Описанный подход основан на идее сведения решения нерегулярной задачи к решению конечной последовательности регулярных задач, неудача связана с «прямолинейным» применением идеи сведения. Применительно к задаче целочисленного линейного программирования идея регуляризации позволяет свести решение этой задачи к решению последовательности специальным образом построенных линейных задач. Впервые эта идея для задач указанного типа была высказана Данцигом. Она состоит в следующем. Если полученное решение удовлетворяет условию целочисленности, то процесс окончен. В противном случае к ограничениям исходной задачи добавляется новое линейное ограничение, обладающее двумя свойствами:

     — полученный нецелочисленный план ему не удовлетворяет;

     — любой целочисленный план ему удовлетворяет.

     Решается  задача с дополнительно введенным  ограничением, процесс повторяется  до получения целочисленного решения. Идея отсечения приводит к трем проблемам:

     — нахождение универсального правила формирования отсечений;

     — доказательство конечности процесса отсечения;

     — борьба с чрезмерным «разрастанием» размерности задач при добавлении ограничений.

     Только  решение этих проблем может привести к универсальному и реализуемому в вычислительном отношении алгоритму. Р. Гомори удалось решить эти проблемы.

      

     Трудности вычислительной реализации. В дальнейшем выявилась большая непредсказуемость в поведении различных алгоритмов отсечения. Вычислительный эксперимент показал, что существуют задачи сравнительно небольшой размерности, решение которых не удается получить при больших затратах машинного времени. Далее было найдено теоретическое объяснение этого явления. Было показано, что для некоторых вариантов алгоритма Гомори существуют задачи, в которых число отсечений быстро растет с ростом размерности задачи и ростом коэффициентов, а в текущих симплекс-таблицах появляются весьма большие числа.

     Методы  отсечения не нашли все же широкого применения при решении прикладных задач по следующим причинам:

     — определение того, какое отсечение (из большого их числа) есть сильнейшее, есть сложная в вычислительном отношении задача;

     — методы отсечения приспособлены в основном для решения чисто целочисленных задач;

     — методы отсечения не приспособлены для решения задач со слабо заполненными матрицами. 

     Комбинаторные методы.

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

     Таким образом, комбинаторные методы основаны на двух элементах:

     — последовательное разбиение на подмножества;

     — оценивание получаемых подмножеств. 

     Приближенные  методы.

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

      2.1 Графический метод решения задач дискретного программирования 

      Изначально  предположим существование множество  точек, которые в декартовой плоскости можно представить узлами.

         j(Аi ; Сj )

        
 
 
 
 
 

      Для решения подобного типа задач  необходимо визуально вращать луч  по часовой стрелки начальное  значение  Сj

      По  мере вращения находим сумму  i при этом заполнение заданного множества соответствует 

       i i; xi

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

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

      Пример 1

      Z=8x1+7x2+6x3+4x4+2x5 max

      5x1+6x2+7x3+6x4+5x5 23

        

      Решение 
 

      

       . 

      5+6+7+6=24

      Х=(1,1,1,0,0)

        Z 1 =21 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

3. Модели дискретного  программирования

3.1. Задача о назначении

      Имеет некоторое количество n исполнителей, которые могут выполнять n различных  работ. Известна полезность , связанная  с выполнением i-м исполнителем j-й работы          .  Необходимо назначить исполнителей на работы так, чтобы добиться максимальной полезности, при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должен быть закреплен только один исполнитель.

      Математическая  модель задачи примет вид:

                                                                                                  

     Каждый  исполнитель назначается только на одну работу:

     

, 

     На  каждую работу назначается только один исполнитель:

     

, 

     

 

     В задаче на узкое место вместо целевой  функции получаем

     

     Получим оптимальную задачу, у которой , . Эта задача имеет оптимальное целочисленное решение, так как все и целочисленны.  
 
 

3.2. Задачи транспортного типа

     1. Транспортная задача в матричной  постановке.

     Постановка  задачи. Пусть имеется m пунктов производства и n пунктов потребления однородного продукта. Объем производства в пункте производства с номером i  равен ; объем потребления в пункте потребления с номером j равен . Предполагается, что производство и потребление сбалансированы, т.е.:

     

     Задана  матрица  транспортных расходов: затраты на перевозку единицы продукции из пункта производства i в пункт потребления j.

     Требуется составить план перевозок, который  не выводит за пределы мощностей  производителей, удовлетворяет полностью  всех потребителей и минимизирует суммарные  затраты на перевозки. Через  обозначим объем перевозки из пункта производства i в пункт потребления j, . Тогда