НОВОСТИ ТРАНСПОРТНОЙ ОТРАСЛИ

Характеристика динамического программирования. Оптималь­ное планирование грузопотоков, рассмотренное в предыдущем раз­деле, может также решаться методами линейного программиро­вания.

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

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

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

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

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

Предметом задач динамического программирования является выбор такой последовательности этапов и такой их длительности, чтобы «функция пользы» или иначе «целевая функция», определен­ным образом зависящая от последовательности и длительности эта­пов, достигла максимума. Обычно «целевая функция» определяет доход от исследуемой операции (процесса).

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

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

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

В принципе, задачи указанного типа можно решать перебором всех возможных вариантов с целью выбора лучшего варианта. Но при решении практически важных задач число возможных ва­риантов решения оказывается таким большим, что даже для совре­менных быстродействующих электронных вычислительных машин, делающих 10000—20000 операций (типа сложения) в секунду время перебора всех вариантов исчисляется годами. Увеличение быстродействия цифровых ЭВМ до 10⁶ операций в секунду не решает проблемы.

Метод динамического программирования дает возможность за­менить перебор всех вариантов решения задачи определенной системой операций — программой ее решения. При этом объем вычислений резко уменьшается, но все же остается столь боль­шим, что обычно не может быть выполнен ручным счетом. На ЭВМ решение задач управления и планирования методом дина­мического программирования оказывается вполне возможным.

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

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

Выбор оптимального маршрута в реальных условиях.

Выбор оптимального маршрута в реальных условиях ослож­няется различными привходящими обстоятельствами. Реальная транспортная сеть не будет упорядоченной.

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

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

ПРИ ПОДДЕРЖКЕ: