Файл: Казаков А.П. Технология и организация перегрузочных работ учебник.pdf

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

Решим предыдущую задачу методом эквивалентов, который также

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

Коэффициент эквивалентности затрат времени на обработку на 1-м причале /-го типа судна с г-м грузом по отношению к затратам вре­ мени на базисном причале

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

310

По наименьшим коэффициентам эквивалентности распределяем ресурсы, записывая их в левой стороне каждой клетки. Внизу в скобках проставляем ко­ личество обрабатываемых этим ресурсом судов. Заполняем вначале клетку 3—4, где /С3 4 = 60 имеет наименьшее значение. Затем в порядке постепенного уве­ личения Kij заполняем другие клетки.

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

Оптимальная загрузка судна. В § 7 рассматривалась задача об оптимальной загрузке судна при наличии на причале двух видов гру­ за с различными погрузочными объемами. При наличии большего чис­ ла грузов с различными погрузочными объемами задача оптимальной загрузки судна решается методом линейного программирования.

Gt — количество грузов i-го признака, т;

— удельный погрузочный объем i-ro груза, м3/т; Qj — грузоподъемность /-го трюма, т;

Vj — вместимость /-го трюма, м3;

х1} — количество' груза i-ro вида, которое необходимо погрузить в /-й трюм.

Количественный набор грузов xtj, при котором обеспечивается мак­ симальная загрузка всех трюмов судна;

Для численного решения задачи можно воспользоваться симплек­ сным методом.

311

§58. Выбор оптимального сочетания транспортных

иперегрузочных средств методом динамического

программирования

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

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

Для иллюстрации метода динамического программирования рас­ смотрим задачу обоснования оптимального сочетания технических средств для перегрузки и транспортировки груза из пункта А в пункт Д. Ради краткости всю совокупность работ, обеспечивающих доставку груза из пункта А в пункт В, будем называть ЛД-работой.

Пусть в результате предварительного анализа ЛД-работа расчле­ нена на N этапов, каждому из которых в порядке очередности выпол­ нения присвоен номер i = 1, 2, 3, ..., N. В общем случае работа на t'-м этапе (t-я работа) может быть выполнена несколькими способами, количество которых определяется номенклатурой технологии и техни­ ческих средств, предназначенных для выполнения работ такого типа.

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

словами, выбрать различные способы осуществления работы. Если сформулировать количественный критерий оценки эффективности транспортного процесса, то этот критерий, как правило, выразит един­ ственный наиболее эффективный вариант выполнения всей работы по доставке груза из пункта Л в пункт Д. Задача сводится к тому, чтобы отыскать этот вариант.

Наиболее часто при выборе оптимального варианта в качестве кри­ терия принимается показатель минимальных удельных приведенных затрат. Обычно приведенные затраты сг при выполнении t-й работы не зависят от работы на i— 1 этапе, а зависят от способа выполнения (управления) цг и от начальных условий yt—1, отражающих состояние транспортного процесса к моменту начала t-ro этапа, или, что то же самое, к моменту окончания предыдущего этапа. Формально эта зави­ симость имеет вид ct — с; (t/,_ь щ). Тогда величина приведенных

312

Требуется выбрать начальное состояние г/0 и способы выполнения работ (управления) ии м2, .... uNтаким образом, чтобы целевая функция

Чтобы решить задачу динамического программирования, сформу­ лируем принцип оптимальности [19, 38]: оптимальное управление обла­ дает тем свойством, что, каково бы ни было начальное состояние и на­ чальное управление, последующее управление должно быть оптималь­ ным по отношению к состоянию, получающемуся в результате дей­ ствия начального управления.

Придадим этому принципу математическую форму применительно к нашей задаче.

Если обозначить величину минимально необходимых приведен­ ных затрат на выполнение первых i— 1 этапов Л5-работы через Сг= 1( то минимальные приведенные затраты на выполнение первых этапов

Задача динамического программирования сводится к решению этой рекуррентной системы уравнений. Рассмотрим сначала последова­ тельность этапов от начала к концу. При i = 1 естественно считать, что С(_ 1 = С = 0, поскольку при отсутствии способов выполнения работы затрат нет. Одновременно с этим у0 отражает возможность ис­ пользования имеющихся технических средств погрузки в пункте А.

Таким образом, Сг = min сх (у0, их) и зависит от начального состоя­ ния уо,

при i = 2 имеем

С2 = min lct {у0, %) + с2 (у1 иг)];

«I, М2

Величина Ct определяет условно-минимальные затраты и условно­ оптимальное решение у0 и иъ «2, ...,цг для каждого фиксированного у0 на i-этапном процессе.

Следовательно, рекуррентное соотношение (209) дает практический способ определения оптимального решения. Подставляя в это уравне­ ние для каждого этапа значения ct (г/,-ь ut) и складывая с величиной Ct_ 1, вычисленной на предыдущем этапе, получим совокупность условно-оптимальных решений для данного этапа. Таким образом, для каждого фиксированного начального состояния по формуле (209) получаем последовательно (для г = 1, 2, ..., N) значения Сь С2, ..., С аг. Величина CN определяет условно-оптимальные затраты для АВ-ра-

313