12.3. Обобщённая схема алгоритма Гомори

Структурно алгоритм Гомори делится на так называемые большие итерации. Каждая большая итерация содержит следующие этапы.

Решение текущей задачи методами линейного программирования (малые итерации). На первой итерации в качестве текущей задачи выступает нецелочисленный аналог исходной целочисленной задачи ЛП.
Поиск первой нецелочисленной компоненты в оптимальном плане, полученном на первом этапе.

Если все компоненты являются целочисленными, то алгоритм завершается.
Если существуют нецелочисленные компоненты, то переходим к пункту 3 алгоритма.

Построение для найденной компоненты условия отсечения согласно правилу (3). Вновь сформированное ограничение добавляется к системе ограничений текущей задачи и таким образом получается новая текущая задача. Переходим на начало следующей большой итерации (пункт 1).

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

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

Контрольные вопросы:

Какие экономические задачи относятся к целочисленному программированию?
Алгоритм Гомори.
С помощью алгоритма Гомори решить задачу:

Лекция № 13 Сетевое планирование

Изучаемые вопросы:

Основные понятия теории сетевых моделей
Алгоритм Форда

12.1. Основные понятия теории сетевых моделей

Методы сетевого планирования разработаны в 60-е гг. двадцатого столетия. Методы сетевого планирования относятся к одному из разделов современной теории управления большими системами и предназначены для составления и наблюдения за исполнением проектов производства или исследований. Впервые сетевые методы планирования были оформлены в США в виде системы ПЕРТ или метода критического пути («Critical Path Scheduling»). Математической основой этих методов служит теория графов, которая является, в свою очередь, частью теории множеств.

Рассмотрим множество, состоящее из конечного числа элементов, которые мы будем обозначать буквами x₁, x₂ ,..., х_n, а само множество буквой X. Запишем это символически: X = { x₁, x₂ ,..., х_n}.

Каждому элементу х_i, принадлежащему X, поставим в соответствие нуль, один или несколько элементов из X. Тогда мы построим, пользуясь терминологией теории множеств, некоторый «граф». Обозначим через Г закон, предоставляющий данное соответствие, и запишем граф символически G = (X, Г).

Граф может быть представлен с помощью чертежа, это называется представление графа с помощью направленных дуг, или с помощью таблицы с двумя входами (матрица).

Для примера рассмотрим множество из 5 элементов: Х= {А, В, С, D, Е). Пусть закон Г, определяющий соответствие между элементами этого множества, определен следующим образом: ГА = {В, С, D}, ГВ = {В}, ГС = {D, E}, ГD = {А, С}, ГЕ = О, где символ О означает пустое множество. На рис. 7 представлено графическое изображение этого графа, а в таблице рис. 8 — его табличное задание.

	A	B	C	D	E
A	0	1	1	1	0
B	0	1	0	0	0
C	0	1	0	1	1
D	1	0	1	0	0
E	0	0	0	0	0

На данном примере удобно проиллюстрировать все основные понятия, которые используются в теории графов.

Вершиной графа называется элемент множества, образующего граф. На рис. 7 вершины графа, которые часто также называют точками, это элементы множества А, В, С, D, Е. Дугой графа называется ориентированная пара вершин графа. На рис 7. дугами являются пары: (А, В), (А, С), (С, D) и т. д.

Путем называется последовательность сцепленных дуг, позволяющих пройти из одной вершины в другую. На рис. 7 пути: (А, С, Е), (А, С, D),(D, С, В) и т. п.

Контуром называется путь, начальная вершина которого совпадает с конечной. На рис. 1 контуром является путь (А, С, D, А).

Петлей называется дуга, начало и конец которой совпадают (В, В).

Ребром называется неориентированная дуга, т. е. дуга, у которой не указано направление движения.

Цепью называется сцепленная последовательность ребер.

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

Предком некоторой вершины называется вершина, из которой исходит дуга, входящая в данную вершину.

Потомком некоторой вершины называется вершина, в которую входит дуга, исходящая из данной вершины.

В дальнейшем будем рассматривать связные графы без контуров.

Для связного графа без контуров возникает и решается задача разбиения его вершин на слои так, чтобы:

а) все элементы данного слоя не имели предков в следующем слое, а элементы последнего – потомков;

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

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

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

Критическим путем сетевого графика называется самый длинный путь.

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

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

Ранний срок наступления события определяется по формулам:

t₁ = 0,