Стратегия социально-экономического развития Омской области

Для каждой конкретной задачи целочисленного программирования (другими  словами, дискретной оптимизации) метод  ветвей и границ реализуется по-своему. Есть много модификаций этого  метода. Однако менеджеру нет необходимости  вникать в подробности, относящиеся  к вычислительной математике. Вместе с тем он должен знать о возможностях, предоставляемых ему теорией  оптимизации.

Теория графов и оптимизация 

Один из разделов дискретной математики, часто используемый при  принятии решений - теория графов (см., например, учебные пособия [3,4]). Граф - это совокупность точек, называемых вершинами графа, некоторые из которых  соединены дугами (дуги называют также  ребрами). Примеры графов приведены на рис.5.

Рис.5. Примеры графов. 

На только что введенное  понятие графа "навешиваются" новые свойства. Исходному объекту  приписывают новые качества. Например, вводится и используется понятие  ориентированного графа. В таком  графе дуги имеют стрелки, направленные от одной вершины к другой. Примеры ориентированных графов даны на рис.6.

Рис.6. Примеры ориентированных  графов. 

Ориентированный граф был  бы полезен, например, для иллюстрации  организации перевозок в транспортной задаче. В экономике дугам ориентированного или обычного графа часто приписывают  числа, например, стоимость проезда  или перевозки груза из пункта А (начальная вершина дуги) в пункт  Б (конечная вершина дуги). 

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

Задача коммивояжера.

Требуется посетить все вершины  графа и вернуться в исходную вершину, минимизировав затраты  на проезд (или минимизировав время).  

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

Многие постановки экономического содержания сводятся к задаче коммивояжера. Например: 

- составить наиболее выгодный  маршрут обхода наладчика в  цехе (контролера, охранника, милиционера), отвечающего за должное функционирование  заданного множества объектов (каждый  из этих объектов моделируется  вершиной графа); 

- составить наиболее выгодный  маршрут доставки деталей рабочим  или хлеба с хлебозавода по  заданному числу булочных и  других торговых точек (парковка  у хлебозавода). 

Задача о  кратчайшем пути.

Как кратчайшим путем попасть  из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и  времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения  этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной  вершины до конечной. Рассмотрим пример (рис.7).

Рис.7. Исходные данные к задаче о кратчайшем пути. 

 

 

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

Таблица 4.

Исходные данные к задаче о кратчайшем пути.

 

Спрашивается в задаче: как кратчайшим путем попасть  из вершины 1 в вершину 4? 

Решение. Введем обозначение: С(Т) - длина кратчайшего пути из вершины 1 в вершину Т. (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С(4) и указании пути, на котором этот минимум достигается.  

Для исходных данных, представленных на рис.7 и в табл.4, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит  ее длина, равная 1, поэтому С(3) = 1. Кроме того, очевидно, что С(1) = 0. 

В вершину 4 можно попасть  либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение

С(4) = min {С(2) + 4; С(5) + 5}.

Таким образом, проведена  реструктуризация (упрощение) задачи - нахождение С(4) сведено к нахождению С(2) и С(5).  

В вершину 5 можно попасть  либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение

С(5) = min {С(3) + 2; С(6) + 3}.

Мы знаем, что С(3) = 1. Поэтому

С(5) = min {3; С(6) + 3}.

Поскольку очевидно, что С(6) - положительное число, то из последнего соотношения вытекает, что С(5) = 3. 

В вершину 2 можно попасть  либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение

С(2) = min {С(1) + 7; С(3) + 5; С(5) + 2}.

Нам известно, что С(1) = 0, С(3) = 1, С(5) = 3. Поэтому

С(2) = min {0 + 7; 1 + 5; 3 + 2} = 5.

Теперь мы можем найти С(4):

С(4) = min {С(2) + 4; С(5) + 5} = min {5 + 4; 3 + 5} = 8.

Таким образом, длина кратчайшего  пути равна 8. Из последнего соотношения  ясно, что в вершину 4 надо идти через  вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков:

1 → 3 → 5 → 4 .

Задача о кратчайшем пути для конкретных исходных данных (рис.7 и табл.4) полностью решена.  

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