Динамическое програмирование

1 шаг 2 шаг 3 шаг 4 шаг

рис.2

Переходим к оптимизации предпоследнего, третьего, шага. Для этого рассмотрим все возможные исходы предшествующего, второго, шага. После этого шага груз может оказаться только в одном из пунктов - 5,6,7. Для каждого пункта выбираем условное оптимальное решение - оптимальный маршрут в пункт 10 и соответствующие минимальные затраты. Так, если груз оказался в пункте, 5, то далее можно следовать либо через пункт 8, либо через пункт 9. В первом случаи затраты равны 7+1=8 единицам, во втором - 5+4=9 единицам. Значит, условный оптимальный маршрут из пункта 5 в пункт 10 проходит через пункт 8, а условные минимальные затраты составляют 8 единиц. На ребре 5 - 8 сети ставим стрелку, а в кружке 5 записываем минимальные затраты: 8=7+1. ребро 5 - 9 остается без стрелки. Аналогично для пункта 6 находим условно-оптимальный маршрут 6 - 8 - 10 с затратами в 4 единицы; для пункта 7 - условно-оптимальный маршрут 7 - 9 - 10 с затратами в 5 единиц.

Далее оптимизируем путь доставки груза на втором шаге процесса. Для этого рассматриваем все возможные исходы первого шага. После первого шага груз мог оказаться только в одном из пунктов: 2, 3 или 4. При нахождении условного оптимального решения в каждом из этих пунктов надо просмотреть все возможные маршруту их этого пункта и для каждого из них найти сумму затрат на этом шаге и условных минимальных затрат на оптимальном продолжении маршрута, уже построенном для следующего пункта. Этого требует принцип оптимальности. Из всех возможных маршрутов выбирается тот, для которого эта сумма меньше (если суммы равны, выбирается любой маршрут). Для пункта 2 оптимальным будет маршрут 2 - 6 - 8 - 10 с затратами 12+4=16 единиц; для пункта 3 - маршрут 3 - 7 - 9 - 10 с затратами 7+5=12 единиц; для пункта 4 - маршрут 4 - 7 - 9 - 10 с затратами 13+5=18 единиц.

Оптимизируем, наконец, первый шаг. Для выбора условного оптимального решения рассматриваем три возможных маршрута: через пункты 2, 3 или 4. Устанавливаем, что наивыгоднейшим будет маршрут 1 - 3 с затратами в 17 единиц. Итак, этап условной оптимизации закончен, и остается пройти процесс в направлении от пункта 1 к пункту 10 и прочитать оптимальный маршрут: 1 - 3 - 7 - 9 - 10.

Заметим, что на первом этапе нами выбран маршрут 1- 3 доставки груза, по которому затраты в 2,5 раза превышают затраты на маршруте 1 - 2 и в 5 раз на маршруте 1 - 4. Оказалось, что с точки зрения всего четырехэтапного маршрута, а не одного первого этапа, следует пойти на «жертву» на первом этапе с тем, чтобы минимизировать общие затраты на всем четырехэтапном маршруте. Это иллюстрирует одну из главных особенностей метода: выбирать решение на каждом шаге, руководствуясь не выгодой, получаемой на данном шаге, а общей выгодой, получаемой по окончании всего процесса.

Примененный метод рассуждения не только позволил найти оптимальный маршрут доставки груза из пункта 1 в пункт 10, но и всю структуру оптимальных маршрутов относительно пункта 10 для данной сети дорог. Например, наиболее экономный маршрут доставки груза из пункта 4 в пункт 10 пройдет через пункты 7 и 9. Этот факт для практических нужд часто более ценен, чем нахождение только одного оптимального маршрута (рис. 3). (4)

рис. 3

IV Выводы по результатам работы

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

Рассмотренный метод динамического программирования в практическом применении имеет как недостатки, так и преимущества. Отметим, что методом динамического программирования можно решать даже те задачи, которые не могут быть решены методами математического анализа. Однако он связан с большой вычислительной работой, в связи с этим метод непосредственно может быть применен к экономическим задачам, включающим не более 3 - 4 видов ресурсов.

Список литературы:

1. Баканов М.И., Шеремет А.Д. Теория экономического анализа: Учебник. - 4-е изд., доп. и перераб. - М.: Финансы и статистика, 1999

2. Браславец М.Е. Экономико-математические методы в организации и планировании сельскохозяйственного производства, 1974

3. Кравченко Р.Г., Попов И.Г., Толпекин С.З. Экономико-математические методы в организации и планировании сельскохозяйственного производства, 1974

4. Кузнецов А.В., Холод Н.И. Математическое программирование: [ Учеб. Пособие для эконом. спец. вузов]. - Мн.: Выш. шк., 1984. - 221 с., ил.

5. Кузнецов Ю. Н. и др. Математическое программирование. Учеб. пособие для вузов. М., «Высш. школа», 1976. - 352с. с ил.