Полная версия

Главная arrow Математика, химия, физика arrow Дискретная оптимизация. Модели, методы, алгоритмы решения прикладных задач

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Двухкритериальные задачи специального вида.

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

Рассмотрим двухкритериальную задачу: Найти

x(xi, Х2,..., хп)- вектор неизвестных, координаты которого удовлетворяют условиям ai

Если одну из целевых функций, например, F(x) считать главной, а для другой вместо её минимизации ограничиться дополнительным условием G(x) 0 представляет собой «уступку» по главному критерию, при которой производится минимизация по второстепенному критерию F(x).

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

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

В качестве распределяемого ресурса примем Go. Если неизвестные Xi изменяются дискретно с постоянным шагом, то при нелинейных функциях gi(xi) использованный ресурс меняется дискретно, но регулярной сетки мы не получаем. В принципе она и не нужна, так как можно действовать также, как и при решении задачи о загрузке машины. Отличие состоит лишь в том, что вместо двух возможных переходов из каждого состояния (брать - не брать) имеется существенно больше переходов. Конкретно, число этих переходов из каждого состояния на i-ом шаге равно числу возможных значений х. Конечно, из некоторых состояний (при значительном исчерпании ресурса) это число переходов существенно меньше. Число состояний на каждом этапе зависит не только от

ДИСКреТНОСТИ ПО Xi, НО И ОТ СВОЙСТВ фуНКЦИЙ gj(Xi).

В качестве примера рассмотрим задачу оптимального выбора способа выполнения работ. Предположим что имеется определённый набор работ Ai, Аг,..., Ап, каждую из которых можно выполнить различными способами (механизмами, по различным технологиям и т.д.) Si, S2, Предположим, что

каждая работа выполняется только одним из способов, но один и тот же способ может использоваться на нескольких работах. Если каждый из способов может использоваться только один раз (для одной из работ) и каждая работа выполняется только одним из способов, то это известная задача выбора, которая решается как задача линейного программирования [20,21]. Неизвестными являются

Характерно, что в этом случае не учитывая требование целочисленности неизвестных, дробных значений не получаем. Целочисленность обеспечена автоматически [4].

Для рассматриваемой нами задачи введём обозначения: су и ty соответственно затраты и время выполнения i-ой работы j -ым способом.

Задача состоит в минимизации и затрат и времени выполнения всей совокупности работ за счёт оптимизации выбора способов их выполнения. Формально в каждой строке матриц су и ty надо выбрать только один элемент (можно в одном и том же столбце), так чтобы суммы выбранных элементов в каждой из матриц были минимальны. По смыслу задачи эти требования противоречивы, так как чем быстрее может быть выполнена работа, тем дороже это будет стоить. Поэтому данная задача или как -то должна быть сведена к однокритериальной или минимизация должна пониматься в смысле Парето.

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

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

Ценовой график для i-ой работы

Рис. 4.7. Ценовой график для i-ой работы.

Это монотонно убывающая функция. Если окажется, что требование монотонности убывания нарушается, (точка А на рис. 4.7, отмеченная знаком +), то это означает, что для данной работы один из способов (точка А) должен быть исключён из рассмотрения, так как имеется другой способ (точка В) который лучше и по затратам и по времени. Оставшиеся способы применительно к данной работе образуют множество Парето. Будем считать, что такая ранжировка способов и отбраковка заведомо неконкурентных из них выполнена для каждой работы (то есть множества Парето для каждой работы определены).

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

Построение множества Парето по шагам

Рис. 4.8. Построение множества Парето по шагам

Нижней точке соответствует наименьшее время, но наибольшая стоимость, а верхней наоборот.

Никакой отбраковки вариантов выбора на первом шаге естественно нет.

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

Новая точка может не совпадать ни с одной из имеющихся на вертикали 2. Предположим, что она попадает между двумя имеющимися (точка В на рис. 4.8). Тогда для суммарного времени имеем tc< t в а. Возникают следующие варианты.

  • 1. Суммарные затраты для точки В меньше, чем для С, т.е. z b
  • 2. z b>zc. В этом случае точка В должна быть отброшена, так как точка С имеет преимущества по двум критериям и на всех последующих шагах остаются те же возможности выбора (параллельные траектории из В и С).
  • 3. Суммарные затраты z b^za. Тогда нет никаких оснований оставлять точку А и все остальные точки вертикали 2, для которых и время и затраты больше, чем для точки В. (Эти точки на вертикали 2 могут быть только выше, чем точка В).
  • 4. z b>za. Точка В должна быть помещена на вертикаль 2, но другие точки она «не убивает».

Если новая точка окажется выше всех имеющихся на вертикали 2, (самое большое время), то она помещается на вертикаль (вариант 1) или не помещается (вариант 2) в зависимости от соотношения затрат в сравнении с верхней из имеющихся точек.

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

2, есть ничто иное как множество Парето для первых двух работ. Переходя к выбору способа выполнения третьей и всех последующих работ, мы поступаем аналогично: сначала берём минимальную по времени комбинацию способов выполнения уже рассмотренных работ (нижняя точка на уже «заселённой» вертикали) и к ней подключаем все оставленные для рассмотрения способы выполнения очередной работы (они упорядочены по возрастанию времени). Эти точки помещаются на очередную вертикаль. Затем последовательно по возрастанию времени рассматриваются все остальные комбинации способов выполнения уже рассмотренных работ (элементы множества Парето) и подключаются к ним поочерёдно способы выполнения очередной работы. Так последовательно по шагам мы формируем множество Парето для очередного набора работ. В итоге получается множество Парето для полного набора работ. Каждая его точка соответствует времени и затратам для соответствующей комбинации способов выполнения всего набора работ. Чтобы восстановить эти способы, нужно при помещении очередной точки на очередную вертикаль запоминать соответствующую ей связь с предыдущей вертикалью. Другими словами, для каждой точки на каждой вертикали надо хранить не только соответствующее суммарные время и затраты, но и номер точки на предыдущей вертикали, из которой мы пришли в данную точку, то есть связь. Тогда обратным разворотом получаем всю комбинацию номеров способов по каждой работе. Поскольку для каждой работы пришлось упорядочивать способы по- разному, эти номера не соответствуют исходным номерам столбцов в матрицах сц и tij. Однако нет необходимости хранить для каждой работы старую последовательность номеров. Лучше по полученным номерам определить время и затраты по выбранному способу выполнения каждой работы (последовательно, начиная с конца, по разностям соответствующих величин). Если требуется, по этим данным можно восстановить и исходные номера способов выполнения работ.

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

Если с помощью этого ограничения задача сведена к однокритериальной, то алгоритм полностью сохраняется, но на последней вертикали берётся верхняя точка при минимизации затрат при ограниченном времени (точка Е) или нижняя точка при минимизации времени при ограниченных затратах (точка F на рис. 4.8).

Если есть ограничения сразу по двум критериям, то число вариантов только сокращается.

В рассмотренной задаче выбора дискретность задана изначально (конечное число способов выполнения работ). Если исходные функции fi и gi непрерывны, то проблема замены их дискретным набором точек ничуть не сложнее, чем при статическом задании сетки состояний. Отличие в том, что кроме дискретности по исходным переменным и вычислении соответствующего дискретного набора по «ресурсу» (в задаче выбора - это время) имеет смысл задать и допустимую погрешность при сравнении по ресурсу, то есть считать неразличимыми достаточно близкие по ресурсу состояния. Это может потребоваться, так как приращение функции gi (xi) при изменении Xi на один дискрет может быть мало и число комбинаций (точек на вертикали) растёт очень быстро. Здесь могут иметь место обычные для динамического программирования расчёты сначала по крупной, а потом по мелкой сетке, то есть в нашем случае сначала при грубом дискрете по ресурсам, а потом с использованием полученного решения при малом дискрете.

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>