Динамическое программирование 2 (стр. 2 из 5)

Построение оптимальной последовательности операций в коммерческой деятельностиПримерПусть на оптовую базу «Ларес» прибыло 10 машин с товаром для разгрузки и 8 машин для загрузки товаров, направляемых в магазины. Материально-ответственное лицо оптовой базы осуществляет оформление документов по операциям разгрузки или загрузки для одной машины, а затем переходит к обслуживанию другой машины. Известны затраты по выполнению каждой операции, которые показаны на ребрах графа (рис. 2).Издержки от операций обусловлены простоем транспорта, типом операции (прием или отправка товара) и не зависят от конкретной машины. Необходимо спланировать последовательность операций обоих видов таким образом, чтобы суммарные издержки по приему и отправке товаров для всех машин были минимальными.Решение:Из условия следует, что состояние экономической системы характеризуется двумя параметрами: количеством принятых и оформленных машин по разгрузке товара и количеством машин, отправленных с товаром в магазины. Поэтому решение будем искать на плоскости X0Y, на ограниченном прямыми прямоугольнике, который является областью допустимых состояний системы. Если по оси X отложить число (10) разгруженных машин, а по оси Y – число (8) загруженных товаром машин, то можно построить на плоскости граф состояний процесса, в котором каждая вершина характеризует состояние операции приема и отгрузки товара на оптовой базе. Ребра этого графа означают выполнение работы по приему или отправке товара на очередной машине. Каждому ребру можно сопоставить издержки, связанные с выполнением операции по разгрузке или загрузке машины.Точка S₀ определяет начало процесса, a S₁ – конечное состояние, соответствующее приему и отправке всех машин. Оптимизацию процесса будем производить с конечного состояния S₁. Весь процесс разобьем на шаги, их количество k = n + m = 10 + 8 = 18. Каждый шаг представляет собой сечение графа состояний, проходящее через вершины (на рис. 2 сечения показаны косыми линиями).

К=18 К=17 К=16 К=15 К=14 К=13 К=12 К=11 К=10 К=9Рисунок 2 – Графическая схема связи операцийI этап. Условная оптимизация.1-й шаг. k = 1. На первом шаге, с задаваемым сечением А₁В₁, из состояний А₁ и B₁ возможен только один вариант перехода в конечное состояние S₁. Поэтому в вершинах А₁ и B₁ записываем соответственно издержки 13 и 10. Ребра A₁S₁ и B₁S_l обозначаем стрелкой, направленной в вершину S₁, как показано на рис. 3. Рисунок 3 – Сетевая модель операции, шаг 1 2-й шаг. k = 2. Второй шаг оптимизации задается сечением по вершинам А₂, В₂, C₁. Из состояний А₂ и C₁ возможен единственный переход в вершины А₁ и B₁ соответственно, поэтому в вершинах А₂ и C₁ записываем суммарные издержки 29 и 28 на первых двух шагах перехода в конечное состояние S₁. Из вершины В₂ возможны два варианта перехода: в вершину А₁ или вершину B₁. При переходе В₂ → А₁ сумма издержек составляет 11 + 13 = 24, на переходе В₂ → В₁ сумма составляет 15 + 10 = 25. Из двух вариантов суммарных издержек выбираем наименьшую (24) и обозначаем стрелкой условно оптимальный переход В₂ → А₁, как показано на рис. 4.

Рисунок 4 – Сетевая модель операции, шаг 2 3-й шаг. k = 3. На третьем шаге сечение проходит через вершины А₃, В₃, С₂, D₁. Из вершин А₃ и D₁ возможен единственный переход в вершины А₂ и С₁ соответственно. Суммарные издержки для состояния D₁ равны 28 + 19 = 47; для состояния А₃: 29 + 20 = 49. Из вершины В₃ возможны два варианта перехода: в вершину А₂ издержки равны 29 + 9 = 38; в вершину В₂ – 13 + 24 = 37. Для вершины С₂ возможен переход в вершину В₂ (21 + 24 = 45) и в вершину С₁ (18 + 28 = 46). Выбираем для вершин В₃ и С₂ наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход, как показано на рис. 5.

Рисунок 5 – Сетевая модель операции, шаг 3 4-й шаг. k = 4. Четвертый шаг оптимизации задается сечением по вершинам А₄, В₄, C₃, D₂, Е₁. Из состояний А₄ и Е₁ возможен единственный переход в вершины А₃ и D₁ соответственно, поэтому в вершинах А₄ и Е₁ записываем суммарные издержки:А₄А₃: 18 + 49 = 67Е₁D₁: 18 + 47 = 65.Вершина В₄: В₄А₃: 10 + 49 =59 В₄В₃: 13 + 37 = 50.Вершина С₃: С₃В₃: 20 + 37 =57С₃С₂: 21 + 45 = 66.Вершина D₂: D₂С₂: 19 + 45 =64 D₂D₁: 11 + 47 = 58.

Рисунок 6 – Сетевая модель операции, шаг 4 5-й шаг. k = 5. На пятом шаге сечение проходит через вершины А₅, В₅, С₄, D₃, Е₂, F₁. Из вершин А₅ и F₁ возможен единственный переход в вершины А₄ и Е₁ соответственно:А₅А₄: 15 + 67 = 82F₁Е₁: 16 + 65 = 81.Вершина В₅: В₅А₄: 13 + 67 =80 В₅В₄: 12 + 50 = 62.Вершина С₄: С₄В₄: 18 + 50 = 68С₄С₃: 12 + 57 = 69.Вершина D₃: D₃С₃: 18 + 57 = 75 D₃D₂: 11 + 58 = 69.Вершина Е₂: Е₂D₂: 16 + 58 = 74Е₂Е₁: 15 + 65 = 80.

Рисунок 7 – Сетевая модель операции, шаг 5 6-й шаг. k = 6. Шестой шаг оптимизации задается сечением по вершинам А₆, В₆, C₅, D₄, Е₃, F₂, G₁. Из состояний А₆ и G₁ возможен единственный переход в вершины А₅ и F₁ соответственно, поэтому в вершинах А₆ и G₁ записываем суммарные издержки:А₆А₅: 13 + 82 = 95G₁F₁: 10 + 81 = 91.Вершина В₆: В₆А₅: 14 + 82 =96 В₆В₅: 15 + 62 = 77.Вершина С₅: С₅В₅: 10 + 62 = 72С₅С₄: 12 + 68 = 80.Вершина D₄: D₄С₄: 16 + 68 = 84 D₄D₃: 12 + 69 = 81.Вершина Е₃: Е₃D₃: 15 + 69 = 84Е₃Е₂: 14 + 74 = 88.Вершина F₂: F₂Е₂: 15 + 74 = 89F₂F₁: 12 + 81 = 93.

Рисунок 8 – Сетевая модель операции, шаг 6 7-й шаг. k = 7. Сечение А₇, В₇, C₆, D₅, Е₄, F₃, G₂, Н₁. Вершина А₇: А₇А₆: 18 + 95 = 113Вершина Н₁: Н₁G₁: 11 + 91 = 102Вершина В₇: В₇А₆: 15 + 95 = 110 В₇В₆: 18 + 77 = 95.Вершина С₆: С₆В₆: 9 + 77 = 86 С₆С₅: 13 + 72 = 85.Вершина D₅: D₅С₅: 15 + 72 = 87D₅D₄: 10 + 81 = 91.Вершина Е₄: Е₄D₄: 15 + 81 = 96Е₄Е₃: 14 + 84 = 98.Вершина F₃: F₃Е₃: 16 + 84 = 100F₃F₂: 10 + 89 = 99.Вершина G₂: G₂F₂: 14 + 89 = 103G₂G₁: 11 + 91 = 102.8-й шаг. k = 8. Сечение А₈, В₈, C₇, D₆, Е₅, F₄, G₃, Н₂, I₁. Вершина А₈: А₈А₇: 16 + 113 = 129Вершина I₁: I₁Н₁: 12 + 102 = 114Вершина В₈: В₈А₇: 14 + 113 = 127 В₈В₇: 20 + 95 = 115.Вершина С₇: С₇В₇: 15 + 95 = 110 С₇С₆: 11 + 85 = 96.Вершина D₆: D₆С₆: 13 + 85 = 98D₆D₅: 13 + 87 = 100.Вершина Е₅: Е₅D₅: 13 + 87 = 100Е₅Е₄: 10 + 96 = 106.Вершина F₄: F₄Е₄: 14 + 96 = 110F₄F₃: 18 + 99 = 117.Вершина G₃: G₃F₃: 12 + 99 = 111G₃G₂: 18 + 102 = 120.Вершина Н₂: Н₂G₂: 17 + 102 = 119Н₂Н₁: 12 + 102 = 114. 9-й шаг. k = 9. Сечение А₉, В₉, C₈, D₇, Е₆, F₅, G₄, Н₃, I₂. Вершина А₉: А₉А₈: 10 + 129 = 139Вершина В₉: В₉А₈: 13 + 129 = 142 В₉В₈: 10 + 115 = 125.Вершина С₈: С₈В₈: 16 + 115 = 131 С₈С₇: 9 + 96 = 105.Вершина D₇: D₇С₇: 14 + 96 = 110D₇D₆: 14 + 98 = 112.Вершина Е₆: Е₆D₆: 15 + 98 = 113Е₆Е₅: 15 + 100 = 115.Вершина F₅: F₅Е₅: 12 + 100 = 112F₅F₄: 16 + 110 = 126.Вершина G₄: G₄F₄: 19 + 110 = 129G₄G₃: 9 + 111 = 120.Вершина Н₃: Н₃G₃: 16 + 111 = 127Н₃Н₂: 10 + 114 = 124.Вершина I₂: I₂Н₂: 11 + 114 = 125I₂I₁: 8 + 114 = 122.10-й шаг. k = 10. Сечение А₁₀, В₁₀, C₉, D₈, Е₇, F₆, G₅, Н₄, I₃. Вершина А₁₀: А₁₀А₉: 14 + 139 = 153Вершина В₁₀: В₁₀А₉: 12 + 139 = 151 В₁₀В₉: 10 + 125 = 135.Вершина С₉: С₉В₉: 15 + 125 = 140 С₉С₈: 18 + 105 = 123.Вершина D₈: D₈С₈: 13 + 105 = 118D₈D₇: 15 + 110 = 125.Вершина Е₇: Е₇D₇: 14 + 110 = 124Е₇Е₆: 13 + 113 = 126.Вершина F₆: F₆Е₆: 12 + 113 = 125F₆F₅: 19 + 112 = 131.Вершина G₅: G₅F₅: 13 + 112 = 125G₅G₄: 11 + 120 = 131.Вершина Н₄: Н₄G₄: 16 + 120 = 136 Н₄Н₃: 15 + 124 = 139.Вершина I₃: I₃Н₃: 11 + 124 = 135 I₃I₂: 15 + 122 = 137. 11-й шаг. k = 11. Сечение В₁₁, C₁₀, D₉, Е₈, F₇, G₆, Н₅, I₄. Вершина В₁₁: В₁₁А₁₀: 10 + 153 = 163 В₁₁В₁₀: 9 + 135 = 144.Вершина С₁₀: С₁₀В₁₀: 10 + 135 = 145 С₁₀С₉: 10 + 123 = 133.Вершина D₉: D₉С₉: 13 + 123 = 136 D₉D₈: 14 + 118 = 132.Вершина Е₈: Е₈D₈: 11 + 118 = 129Е₈Е₇: 14 + 124 = 138.Вершина F₇: F₇Е₇: 10 + 124 = 134F₇F₆: 18 + 125 = 143.Вершина G₆: G₆F₆: 11 + 125 = 136G₆G₅: 18 + 125 = 143.Вершина Н₅: Н₅G₅: 15 + 125 = 140 Н₅Н₄: 19 + 136 = 155.Вершина I₄: I₄Н₄: 16 + 136 = 152I₄I₃: 14 + 135 = 149.12-й шаг. k = 12. Сечение C₁₁, D₁₀, Е₉, F₈, G₇, Н₆, I₅. Вершина С₁₁: С₁₁В₁₁: 11 + 144 = 155 С₁₁С₁₀: 8 + 133 = 141.Вершина D₁₀: D₁₀С₁₀: 15 + 133 = 148 D₁₀D₉: 13 + 132 = 145.Вершина Е₉: Е₉D₉: 15 + 132 = 147 Е₉Е₈: 14 + 124 = 138.Вершина F₈: F₈Е₈: 9 + 129 = 141F₈F₇: 21 + 134 = 155.Вершина G₇: G₇F₇: 12 + 134 = 146G₇G₆: 13 + 136 = 149.Вершина Н₆: Н₆G₆: 15 + 136 = 151 Н₆Н₅: 16 + 140 = 156.Вершина I₅: I₅Н₅: 11 + 140 = 151 I₅I₄: 9 + 149 = 158. 13-й шаг. k = 13. Сечение D₁₁, Е₁₀, F₉, G₈, Н₇, I₆. Вершина D₁₁: D₁₁С₁₁: 11 + 141 = 152D₁₁D₁₀: 12 + 145 = 157.Вершина Е₁₀: Е₁₀D₁₀: 16 + 145 = 161 Е₁₀Е₉: 13 + 141 = 154.Вершина F₉: F₉Е₉: 11 + 141 = 152F₉F₈: 20 + 138 = 158.Вершина G₈: G₈F₈: 14 + 138 = 152G₈G₇: 12 + 146 = 158.Вершина Н₇: Н₇G₇: 14 + 146 = 160 Н₇Н₆: 13 + 151 = 164.Вершина I₆: I₆Н₆: 10 + 151 = 161 I₆I₅: 17 + 151 = 168. 14-й шаг. k = 14. Сечение Е₁₁, F₁₀, G₉, Н₈, I₇. Вершина Е₁₁: Е₁₁D₁₁: 9 + 152 = 161Е₁₁Е₁₀: 11 + 154 = 165.Вершина F₁₀: F₁₀Е₁₀: 15 + 154 = 169F₁₀F₉: 19 + 152 = 171.Вершина G₉: G₉F₉: 13 + 152 = 165G₉G₈: 12 + 152 = 164.Вершина Н₈: Н₈G₈: 13 + 152 = 165 Н₈Н₇: 15 + 160 = 175.Вершина I₇: I₇Н₇: 9 + 160 = 169 I₇I₆: 16 + 161 = 177. 15-й шаг. k = 15. Сечение F₁₁, G₁₀, Н₉, I₈. Вершина F₁₁: F₁₁Е₁₁: 16 + 161 = 177F₁₁F₁₀: 18 + 169 = 187.Вершина G₁₀: G₁₀F₁₀: 10 + 169 = 179G₁₀G₉: 10 + 164 = 174.Вершина Н₉: Н₉G₉: 9 + 164 = 173 Н₉Н₈: 12 + 165 = 177.Вершина I₈: I₈Н₈: 13 + 165 = 178 I₈I₇: 14 + 169 = 183. 16-й шаг. k = 16. Сечение G₁₁, Н₁₀, I₉. Вершина G₁₁: G₁₁F₁₁: 9 + 177 = 186G₁₁G₁₀: 10 + 174 = 184.Вершина Н₁₀: Н₁₀G₁₀: 10 + 174 = 184Н₁₀Н₉: 10 + 173 = 183.Вершина I₉: I₉Н₉: 11 + 173 = 184 I₉I₈: 10 + 178 = 188. 17-й шаг. k = 17. Сечение Н₁₁, I₁₀. Вершина Н₁₁: Н₁₁G₁₁: 10 + 184 = 194Н₁₁Н₁₀: 9 + 183 = 192.Вершина I₁₀: I₁₀Н₁₀: 9 + 183 = 192 I₁₀I₉: 15 + 184 = 199. 18-й шаг. k = 18. Вершина S₀: S₀Н₁₁: 10 + 192 = 202 S₀I₁₀: 13 + 192 = 205. Минимально возможные суммарные издержки по обслуживанию всех 18 машин на оптовой базе «Ларес» составляют 202 усл. ед.II этап. Безусловная оптимизация.Определяем оптимальную траекторию на исходном сетевом графе, просматривая результаты всех шагов в обратном порядке, учитывая, что выбор некоторого управления на k-м шаге приводит к тому, что состояние на (k-1)-м шаге становится определенным. В результате строим ориентированный граф от состояния S₀ к состоянию S₁, представленный на рис. 9, на каждом шаге безусловной оптимизации переход почти всегда единствен и совпадает с построенными условно оптимальными переходами.

Рисунок 9 – Оптимальная последовательность операцийМинимальные издержки F_min соответствуют следующему оптимальному пути на графе:(S₀→ H₁₁ → H₁₀ → H₉ → G₉ → G₈ → F₈ → E₈ → D₈ → C₈ → C₇→ C₆ → → C₅ → B₅ → B₄ → B₃ → B₂ → A₁ → S₁) иравны: F_min = 10 + 9 + 10 + 9 + 12 + 14 + 9 + 11 + 13 + 9 + 11 + 13 + 10 + 12 + 13 + + 13 + 11 + 13 = 202 усл. ед. Таким образом, в соответствии с решением оптимальное управление процессом разгрузки и загрузки машин товаром состоит в следующем: на первом шаге следует оформить документы по загрузке одной машины, на втором – по разгрузке двух машин, затем по загрузке одной машины; далее обслуживать одну машину по разгрузке товара, четыре машины по загрузке, три машины по разгрузке, одну машину по загрузке; в последнюю очередь оформить документы по разгрузке трех машин, по загрузке одной машины и разгрузить последнюю машину.

ЗАКЛЮЧЕНИЕ