Нахождение рациональных затрат при строительстве трубопроводов и транспортных артерий

ТЕМА 6. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ.

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

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

Динамическое программирование позволяет свести одну сложную задачу со многими неизвестными ко многим задачам с малым числом переменных. Это сокращает процесс вычислений и ускоряет процесс принятия управленческого решения.

В отличие от линейного программирования, в котором симплекс-метод является универсальным методом решения, в динамическом программировании такого универсального метода не существует.

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

Требуется проложить путь (трубопровод, шоссе) между двумя пунктами А и В таким образом, чтобы суммарные затраты на его содержание были минимальные.

Y	(север)				В
А				Х (восток)

Решение. Разделим расстояние между пунктами А и В на шаги (отрезки). На каждом шаге можем двигаться либо строго на восток (по оси Х), либо строго на север (по оси У). Тогда путь от А до В представляет ступенчатую ломаную линию, отрезки которой параллельны одной из координатных осей. Затраты на содержание каждого из отрезков даны в таблице.

Путь можно рассматривать как управляемую систему, перемещающуюся под влиянием управления из начального состояния А в конечное В.

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

Процедуру условной оптимизации проводим в обратном направлении, т.е. от В к А.

Найдем условную оптимизацию последнего шага. В точку В можно попасть из или . В узлах запишем стоимость пути. Стрелкой покажем минимальный путь.

Рассмотрим предпоследний шаг.

Для точки условное управление – по оси Х, а для точки - по оси У. Управление для выбираем как min(13+10,14+14)= =min(23,28)=23, т.е. по оси У.

Условную оптимизацию проводим для всех остальных узловых точек.

Получим , где - север, - восток. Минимальные затраты составляют 10+13+8+12+9+9+10=71 млн. руб.

Ответ: Прокладывать путь целесообразно по схеме: с, с, в, с, в, в, в; при этом затраты будут минимальные – 71 млн. руб.

Дата добавления: 2014-12-27