Менеджмент: конспект лекций

Шевчук Денис Александрович

В отличие от предыдущих задач, управляющие параметры Х k , k = 1,2,…, n , принимают значения из множества, содержащего два элемента – 0 и 1.

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

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

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

а затем в окрестности оптимального решения ищутся целочисленные точки.

Методы направленного перебора . Из них наиболее известен метод ветвей и границ. Суть метода такова. Каждому подмножеству Х множества возможных решений Х 0 ставится в соответствие число – «граница» А (Х ). При решении задачи минимизации необходимо, чтобы А (Х 1) ≥ А (Х 2 ), если Х 1 входит в Х 2 или совпадает с Х 2 .

Каждый шаг метода ветвей и границ состоит в делении выбранного на предыдущем шаге множества Х С на два – Х 1С и Х 2С . При этом пересечение Х 1С и Х 2С пусто, а их объединение совпадает с Х С . Затем вычисляют границы А (Х 1С ) и А ( Х 2С ) и выделяют «ветвь» Х С +1 – то из множеств Х 1С и Х 2С, для которого граница меньше. Алгоритм прекращает работу, когда диаметр вновь выделенной ветви оказывается меньше заранее заданного малого числа

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

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

Один из разделов дискретной математики, часто используемый при принятии решений – теория графов. Граф – совокупность точек, называемых вершинами графа, некоторые из которых соединены дугами (дуги называют также ребрами). На только что введенное понятие графа «навешиваются» новые свойства. Исходному объекту приписывают новые качества. Например, вводится и используется понятие ориентированного графа. В таком графе дуги имеют стрелки, направленные от одной вершины к другой.

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

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

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

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

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

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

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

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

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

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

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

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

Для исходных данных, представленных в табл.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.