I этап. Условная оптимизация

1-й шаг: k = 1. На первом шаге с задаваемым сечением ,  из состояний и  возможен только один вариант перехода вконечное состояние . Поэтому в вершинах и  записываемсоответственно издержки 8 и 11. Ребра  и  обозначаемстрелкой, направленной в вершину - , как показано на рис. 1.2.2.

Рис 1.2.2 Фрагмент связи операции (шаг 1)

2-й шаг: k = 2. Второй шаг оптимизации задается сечением по вершинам . Из состояний  и , возможен единственный переход в вершины , и  соответственно, поэтому в вершинах  и  записываем суммарные издержки 17 и 22 на первых двух шагах перехода в конечное состояние .

Из вершины  возможны два варианта перехода: в вершинy  или вершину . При переходе сумма издержек составляет 10 + 8 = 18, на переходе  сумма составляет 13 + 11 = 24. Из двух вариантов суммарных издержек выбираем наименьшую (18) и обозначаем стрелкой условно оптимальный переход , как показано на рис. 1.2.3.

Рис 1.2.3 Сетевая модель операции (шаг 2)

3-й шаг: k = 3. На третьем шаге сечение проходит через вершины , , , . Из вершин  и  возможен единственный переход в вершины    соответственно. Суммарные издержки для состояния равны 22 + 12 = 34. Из вершины  возможны два варианта перехода: в вершину издержки равны 17 + 8 = 25; в вершину  18 + 9 = 27.

Для вершины  возможен переход в вершину  (18 + 10 = 28) и в вершину  (22 + 12 = 34). Выбираем для вершин  и  наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход, как показано на рис. 1.2.4.

Рис 1.2.4 Сетевая модель операции (шаг 3)

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

Рис 1.2.5 Сетевая модель связи расходов операций

II этап. Безусловная оптимизация.

Определяем оптимальную траекторию на исходном сетевом графе, просматривая результаты всех шагов в обратном порядке, учитывая, что выбор некоторого управления на k-м шаге приводит к тому, что состояние на (к — 1)-м шаге становится определенным.

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

Рис 1.2.6 Оптимальная последовательность операций

Практическая часть

Условие задачи:

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

Рис 2.1 Графическая схема связи операций

Решение задачи с помощью математического аппарата