Двухпараметрические задачи

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

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

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

Рассмотрим две двухпараметрические задачи и покажем как их можно решить с помощью этого метода.

Эти задачи рассматривались различными авторами [4,29], которые предлагали использовать для их решения классический алгоритм динамического программирования.

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

Сначала вернёмся к задаче о загрузке транспортных средств и рассмотрим её в следующей постановке. Пусть имеется N различных предметов. Каждый из них обладает весом, объемом и своей стоимостью. Требуется загрузить транспортное средство ограниченной грузоподъемности и вместительности таким образом, чтобы суммарная стоимость погруженных предметов была максимальной. Согласно такой постановке задачи ресурсы (вес и объем) зависимы. Задача сводится к следующему:

Найти

при ограничениях где

Cj - стоимость i-ro предмета,

V,- - объем i-ro предмета,

Wj- вес i-ro предмета,

kj - количество взятых предметов i-ro типа,

V,W - максимально возможная вместительность и грузоподъемность соответственно. Неизвестными являются k_t.

В рассматриваемой задаче очередной шаг - это определение количества предметов соответствующего типа в дополнение к уже погруженным в машину, а состояния системы - это соответствующие суммарный вес и объём.

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

Состояние i на шаге t можно представить как пару: (Vti. Wti), где Vti - накопленный объем за t шагов,

Wt i- накопленный вес за t шагов.

На первом шаге решается задача о том, какое количество экземпляров предмета П] возьмем. Можно не взять ничего. Можно взять один предмет П1, два и т.д., пока выполняется система ограничений. Каждое полученное состояние запоминаем. Дойдя до максимально возможного числа предметов первого типа, получим множество состояний первого шага. На первом шаге нельзя отбраковать ни пути, ведущие в одно и то же состояние, ни сами состояния. Переходим на второй шаг. Для каждого из состояний, сформированных на первом шаге, рассматривается вопрос: можно ли взять предмет Ш и в каком количестве. Необходимо выполнение системы неравенств. Если оказывается, что несколько состояний из первого шага приводят в одно и то же состояние на 2 шаге, то необходимо оставить тот путь, который приводит в данное состояние с максимальным значением целевой функции (задача на максимум), а все остальные исключить. Оставшееся состояние необходимо запомнить (алгоритм Веллмана).

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

В общем случае на шаге t имеем следующий алгоритм. Рассматриваем все состояния на шаге t-1 и решаем вопрос о взятии предмета n_t. Если оказывается, что несколько состояний на t-1-ом шаге приводят в одно и то же состояние на шаге t, то необходимо оставить тот путь, который приводит в данное состояние с максимальным значением целевой функции, а все остальные исключить. Перед тем как запомнить состояние его необходимо проверить. Пусть на t шаге имеется два состояния A(Vti, Wti) и B(Vt2,Wt2). «А» - рассматриваемое состояние, «В» - состояние из множества допустимых состояний на шаге t. Согласно новому принципу отбраковки состояний возможны следующие ситуации (значения целевой функции для текущего состояния обозначены Ft,):

Предполагается, что в каждом случае хотя бы одно из неравенств выполняется строго. Состояния A(Vti, Wti) и B(Vt2, Wt2) входят в множество Парето. Нельзя удалить ни одно состояние.

Состояние A(Vti, Wti) не эффективно по Парето и должно быть отбраковано.

Состояние B(Vt₂, Wt2) не эффективно по Парето и должно быть отбраковано.

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

Рассмотрев все N шагов, мы получим паретовское множество решений трёхкритериальной задачи, из которого можно выбрать решение с максимальным значением целевой функции. Обратным разворотом восстановим траекторию, что позволит найти неизвестные ki.

Таблица 4.3. Исходные данные для решения задачи

Эффективность нового алгоритма решения двухпараметрических задач распределения ресурса оценивалась в сравнении с классическим алгоритмом Веллмана. Последовательно увеличивалось число предметов, при фиксированной грузоподъемности и вместительности. Исходные данные представлены в таблице 4.3, а результаты в таблице 4.4.

Таблица 4.4. Результаты расчётов

Вычисления производились на персональном компьютере с процессором Intel Core 2 DUO 2400 МГц и оперативной памятью 2048 МБ.

По данным таблицы 4.4 видно, что новый алгоритм эффективнее классического алгоритма Веллмана. С ростом количества предметов растет и число состояний системы. Рост числа состояний присущ обоим алгоритмам, однако для алгоритма динамического программирования с использованием множеств Парето этот рост более медленный, и уже при числе предметов N= 30 количества состояний отличаются в 50 раз. Соответственно и время решения задачи различное, в зависимости от выбранного алгоритма решения. Так при использовании динамического программирования с использованием множеств Парето для числа предметов N=30 время решения составляет 25,3 секунды, что почти в 54 раза меньше, чем при решении той же задачи классическим алгоритмом.

Однако, при малом количестве состояний (3 или 4 шага) алгоритм Веллмана работает эффективнее. Для пользователя эта эффективность может быть не заметна, так как разница во времени счета составляет доли секунды. Это происходит потому, что при малом числе состояний число дополнительных операций, связанных с проверкой и отбраковкой неэффективных состояний, в общем объёме вычислений составляет значительную часть, т.к. количество отбракованных точек мало. Однако с увеличением количества состояний (числа шагов) количество отбракованных точек резко увеличивается, что делает влияние дополнительных операций по проверке и отбраковке неэффективных состояний на скорость решения несущественным.

При большем числе предметов были получены следующие результаты (таблица 4.5):

Таблица 4.5. Результаты расчётов. Продолжение