Математическое обоснование структурной модели транспортной системы

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

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

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

Но принцип динамического программирования отнюдь не предполагает, что, выбирая управление на одном отдельном шаге, можно забыть обо всех остальных. Напротив, управление на каждом шаге должно выбираться с учетом всех его последствий в будущем. Динамическое программирование — это планирование дальновидное, с учетом перспективы. Это не близорукое планирование «вслепую» на один шаг. Напротив, управление на каждом шаге выбирается исходя из интересов операции в целом.

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

Как же строить такое управление? Уже было сформулировано общее правило: в процессе поэтапного планирования управление на каждом шаге должно приниматься с учетом будущего. Однако из этого правила есть исключение. Среди всех шагов существует один, который может планироваться попросту, без «оглядки на будущее». Какой это шаг? Очевидно, последний. Этот последний шаг, единственный из всех, можно планировать так, чтобы он как таковой приносил наибольшую выгоду.

Спланировав оптимальным образом этот последний шаг, можно к нему «пристраивать» предпоследний, к этому в свою очередь предпредпоследний и т. д.

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

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

Самая общая задача динамического программирования ставится следующим образом:

Пусть предполагается к осуществлению некоторое мероприятие или серия мероприятий (короче, «операция»), преследующая определенную цель. Спрашивается: как нужно организовать (спланировать) операцию для того, чтобы она была наиболее эффективной, т. е. наилучшим образом удовлетворяла поставленным перед ней требованиям? Чтобы поставленная задача оптимального планирования приобрела количественный, математический характер, необходимо ввести в рассмотрение некоторый численный критерий W, которым мы будем характеризовать качество, успешность, эффективность операции. Величина W, в зависимости от характера решаемой задачи, может выбираться различными способами. Например, при планировании деятельности системы промышленных предприятий в качестве критерия W может быть (смотря по обстоятельствам) выбран общий годовой объем продукции или же чистый годовой доход; критерием эффективности работы транспортной системы может быть, например, общий грузооборот или же средняя стоимость перевозки тонны груза. Вообще критерий эффективности в каждом конкретном случае выбирается исходя из целевой направленности операции и задачи исследования (какой элемент управления оптимизируется и для чего). Задача рационального планирования — выбрать такой способ организации данной системы действий, чтобы обратить в максимум, (или минимум) какой-то критерий W. Если в качестве критерия взята такая величина, увеличение которой нам выгодно (например, доход от группы предприятий), то ее стремятся обратить в максимум. Если, наоборот, величину W выгодно уменьшать, то ее стремятся обратить в минимум.

Продемонстрируем схему такой процедуры. Пусть планируется m-шаговая операция, и неизвестно, чем кончился (m-1)-й шаг. Сделаем об этом ряд «гипотез» или «предположений». Эти гипотезы мы обозначим:

S⁽¹⁾_m-1, S⁽²⁾_m-1, …, S^(f)_m-1, … (1).

Оговоримся, что буквой S^(f)_m-1 не обязательно обозначается одно число: это может быть и группа чисел, характеризующих исход (m-1)-го шага, а может быть и просто качественное состояние той физической системы, в которой протекает управляемый процесс.

Найдем для каждого из предположений (1) условное оптимальное управление на последнем (m-м) шаге. Это будет то из всех возможных управлений U_m, при котором достигается максимально возможное значение выигрыша на последнем шаге.

Предположим, что для каждого из предположений (1) условное оптимальное управление U*_m на последнем шаге найдено:

U*_m(S⁽¹⁾_m-1); U*_m(S⁽²⁾_m-1); …; U*_m(S^(f)_m-1); … (2).

Это означает, что последний шаг спланирован для любого исхода предпоследнего.

Перейдем к планированию следующего от конца, предпоследнего шага. Снова сделаем ряд гипотез о том, чем кончился предпредпоследний ((m- 2)-й) шаг:

S⁽¹⁾_m-2, S⁽²⁾_m-2, …, S^(k)_m-2, … (3).

Поставим вопрос: как нужно выбирать для каждой из этих гипотез условное оптимальное управление на (m-1)-м шаге?

Очевидно, его нужно выбирать так, чтобы оно, совместно с уже выбранным управлением на последнем шаге, обеспечивало максимальное значение критерия W на двух последних шагах.

Другими словами, для каждой из гипотез (3) нужно найти такое условное оптимальное управление на (m-1)-м шаге U*_m-1(S_m-2), чтобы оно, в совокупности с уже найденным условным оптимальным управлением U*_m(S_m-1), давало максимально возможный выигрыш на двух последних шагах.

Очевидно, к (m-1)-му шагу таким же точно способом может быть присоединен (m-2)-й и т. д. вплоть до самого последнего (от конца) 1-го шага, с которого процесс начинается.

Первый шаг, в отличие от всех других, планируется несколько иначе. Так как мы обычно знаем, с чего начинается процесс, то нам уже не требуется делать гипотезы о том, в каком состоянии мы приступаем к первому шагу. Это состояние нам известно. Поэтому, учитывая, что все последующие шаги (2-й, 3-й и т. д.) уже спланированы (условно), нам остается просто спланировать первый шаг так, чтобы он был оптимальным с учетом всех управлений, уже принятых наилучшим образом на всех последующих шагах.

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

Принято считать, что принцип оптимальности впервые был сформулирован Ричардом Эрнестом Беллманом в 1953 г. (в трактовке Е.С. Вентцель):

Каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление таким образом, чтобы оно в совокупности с оптимальным управлением на всехпоследующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный. Р. Э. Беллманом были сформулированы и условия, при которых принцип верен. Основное требование — процесс управления должен быть без обратной связи, т. е. управление на данном шаге не должно оказывать влияния на предшествующие шаги.

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