8.9. Построение оптимальной последовательности операций в коммерческой деятельности

Пусть на оптовую базу прибыло N машин с товаром для разгрузки и M машин для загрузки товаров, направляемых в магазины. Материально ответственное лицо оптовой базы осуществляет оформление документов по операциям разгрузки или загрузки для одной машины, а затем переходит к обслуживанию другой машины. Издержки от операций обусловлены простоем транспорта, типом операции (прием или отправка товара) и не зависят от конкретной машины. Необходимо спланировать последовательность операций обоих видов таким образом, чтобы суммарные издержки по приему и отправке товаров для всех машин были минимальными.

Из условия следует, что состояние экономической системы характеризуется двумя параметрами: количеством принятых и оформленных машин по разгрузке товара и количеством машин, отправленных с товаром в магазины. Поэтому решение будем искать на плоскости XOY, на ограниченном прямыми прямоугольнике, который является областью допустимых состояний системы. Если по оси Х отложить число (N) разгруженных машин, а по оси Y – число (M) загруженных товаром машин, то можно построить на плоскости граф состояний процесса, в котором каждая вершина характеризует состояние операции приема и отгрузки товара на оптовой базе. Ребра этого графа означают выполнение работы по приему или отправке товара на очередной машине. Каждому ребру можно сопоставить издержки, связанные с выполнением операции по разгрузке или загрузке машины.

Пример 76. Пусть N = 6, m = 4. Известны затраты по выполнению каждой операции, которые показаны на ребрах графа (рис. 46).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Точка So определяет начало процесса, а S1 – конечное состояние, соответствующее приему и отправке всех машин. Оптимизацию процесса будем производить с конечного состояния – S1. Весь процесс разобьем на шаги, их количество K = N + M = 6 + 4 =10. Каждый шаг представляет собой сечение графа состояний, проходящее через вершины (на рис. 46 сечения показаны косыми линиями).

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

1-й шаг. K = 1. На первом шаге, с задаваемым сечением A1, B1,  из состояний A1 и В1 возможен только один вариант перехода в  конечное состояние S1. Поэтому в вершинах А1 и В1 записываем соответственно издержки 8 и 11. Ребра A1S1 и B1S1 обозначаем стрелкой, направленной в вершину S1,  как показано на рис. 47.

2-й шаг. K = 2. Второй шаг оптимизации задается сечением по вершинам A2, B2, C1. Из состояний A2 и С1 возможен единственный переход в вершины А1 и В1 соответственно, поэтому в вершинах А2 и С1 записываем суммарные издержки 17 и 22 на первых двух шагах перехода в конечное состояние S1.

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

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

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

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

Минимально возможные суммарные издержки по обслуживанию всех 10 машин на оптовой базе составляют 88 усл. ед.

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

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

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

Минимальные издержки Fmin соответствуют следующему оптимальному пути на графе:

И равны: Fmin = 12+9+9+7+7+10+9+8+9+8=88 усл. ед.

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

Вопросы к главе 8

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

2.  В чем заключаются особенности математической модели ДП?

3.  Что лежит в основе метода ДП?

4.  Сформулируйте задачу кратчайших расстояний по заданной сети. На сколько этапов разбивается задача? Сколько шагов содержится в каждом этапе и в чем суть этапа и шага?

5.  Что является переменной управления и переменной состояния в задаче выбора оптимальной стратегии обновления оборудования?

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

7.  Запишите математическую модель оптимального распределения инвестиций и рекуррентное соотношение Беллмана для ее реализации.

< Предыдущая		Следующая >