Файл: пензенский государственный университет политехнический институт.docx

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Диссертация

Дисциплина: Не указана

Добавлен: 30.11.2023

Просмотров: 196

Скачиваний: 4

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

Содержание

Введение

Основные положения, выносимые на защиту:

Эквивалентные преобразования моделей задач линейного программирования

Анализ моделей и алгоритмов решения задач о назначениях

Анализ эквивалентных преобразований моделей задач о назначениях

Выводы

Модель и алгоритм решения задачи с приоритетными назначениями

Выводы

Алгоритм решения простейшей линейной многокритериальной задачи о назначениях Многообразие многокритериальных задач в сочетании с отсутствием единого принципа оптимальности порождает огромное число методов их решению. Использование того или иного подхода к решению конкретной задачи может оказать существенное влияние на трудоемкость вычислений. Это относится особенно к специальным классам задач, для которых при скалярном критерии качества разработаны эффективные алгоритмы, использующие специфику ограничений и критериальной функции. Одной из таких задач является задача о назначениях.В основе подавляющего большинства методов решения многокритериальных задач лежит понятие веса критерия, характеризующего его сравнительную важность. Наиболее распространенные методы решения многокритериальных задач основаны на свертке набора исходных целевых функций (с учетом их веса) в один обобщенный скалярный критерий [71]. Такой подход позволяет получить оптимальное по Парето решение и при этом характеризуется вычислительной эффективностью. Использование свертки обеспечивает возможность применения для решения многокритериальной задачи о назначениях специально разработанные для однокритериального случая методы – венгерский и метод Мака.Свертка частных критериев разного смыслового содержания не позволяет интерпретировать значение взвешенного обобщенного критерия, поэтому в общем случае использование операторов свертки требует предварительного нормирования матриц затратСl,l 1, k, т.е. приведения их к единой безразмерной шкале. Часто используемый способ нормирования – минимакс-нормализация.Предлагается следующий алгоритм решения простейшей многокритериальной линейной задачи о назначениях (70) – (75). Нормировать матрицы затрат Сl, l 1, k: cl clсl ijmin . c  cijl maxlmin Составить целевые функции безразмерными коэффициентами: f1(X), f2 (X),..., fk(X) с n nlfl(X)  сijxij, l 1, ki1 j1 Составить вектор   (1, 2,..., k)весовых коэффициентов относительной важности целевых функцийf1(X), f2 (X),..., fk(X) ,l 0 , l 1.k, l 1. В том случае, если все критерии имеют одинаковуюl1 важность,l 1, l 1.k. Составить скалярную целевую функция (обобщенный критерий) g(X)   ) ,( f1(X), f2 (X),..., fk(X),где  – оператор свертки. Перейти к однокритериальной задаче о назначениях вида g(X)  min, (76) n xij 1, j 1, n,i1 (77) n xij 1, i 1, n,j1 (78) xij{0,1}, i, j 1, n. (79) Решить задачу (76) – (79) венгерским методом или методом Мака. Результатом является получение решения, оптимального по Парето. Решая задачу многократно и с изменением весовых коэффициентов, можно получить множество Парето-оптимальных решений. Вид свертки в каждом конкретном случае отражает приемлемую для ЛПР форму компромисса между частными критериями. Наиболее часто используемыми свертками являются линейная свертка, мультипликативная свертка и свертка на основе отклонения от идеальной точки. 1   ...   8   9   10   11   12   13   14   15   ...   21

Решение простейшей линейной многокритериальной задачи о назначениях с использованием свертки на основе отклонения от идеальной точки Под идеальной точкой в многокритериальной задаче о назначениях вида (71) – (76) понимают такой векторF*(X)  Rk, компоненты которого являются минимумами целевых функцийf1(X), f2 (X),..., fk(X) по отдельности, т.е.fl*(X)  min fl(X),XDl 1, k. В практических задачах идеальная точка является недостижимой [73]. Свертка на основе идеальной точкиF*(X)имеет вид: g(X)  (F(X), F*(X)) , где  – некоторая метрика вRk. Наиболее часто используются взвешенная чебышевская метрика g(X)  maxlfl(X)  fl* l (80) и взвешенная евклидова метрика kg(X)  ( fl(X)  fl*)2.l1 (81) Предлагается следующий алгоритм составления обобщенного скалярного критерия на основе идеальной точки: составить kоднокритериальных задач о назначениях вида n nlfl(X)  cijxij min,i1 j1n (82)  xij 1, j 1, n,i1n (83)  xij 1, i  1, n,j1 (84) xij{0,1}, i, j 1, n, (85) гдеl 1,k; найти X * – оптимальное решение l-й задачи вида (82) – (84) и lfl*  fl(X*) , l 1, k; lсоставить вектор F*(X)  ( f*, f*,..., f*) , гдеfl*  fl(X*) , l 1, k;1 2 k lсоставить свертку на основе отклонения от идеальной точки по формуле (80) или (81). Разработана программа для нахождения решения многокритериальной линейной задачи о назначениях с использованием свертки на основе отклонения от идеальной точки средствами математического пакета Mathcad, полный текст которой представлен в приложении E. На рисунке 20 приведены результаты применения свертки на основе отклонения от идеальной точки к многокритериальной задаче о назначениях, исходные данные которой совпадают с исходными данными задачи, решенной с использованием линейной свертки: Рисунок 20 – Результаты решения многокритериальной линейной задачи о назначениях с использованием свертки на основе отклонения от идеальной точки На рисунке 20 представлены матрица X – оптимальное по Парето решение, полученное с использованием чебышевской метрики, и матрица Y – оптимальное по Парето решение, полученное с использованием евклидовой метрики. Также программа находит для каждого оптимального по Парето решения значения соответствующего ему критериального вектора. Применяя алгоритм многократно с изменением весовых коэффициентов, можно построить множество точек Парето. Выбор конкретного решения из множества Парето-оптимальных осуществляется ЛПР.Следует отметить, что в некоторых прикладных задачах ЛПР за идеальную точку может принять реальное решение, соответствующее некоторым принятым стандартам или планируемым значениям. 1   ...   10   11   12   13   14   15   16   17   ...   21

Модель и алгоритм решения многокритериальной задачи о назначениях с целевыми функциями противоположного направления

Модель и алгоритм решения многокритериальной открытой задачи о назначениях Обобщим открытую задачу о назначениях на случай многокритериальности. Математическая модель такой задачи в предположенииm nимеет вид:

Модель и алгоритм решения многокритериальной задачи с порядком назначений Обобщим задачу с порядком назначений на случай многокритериальности. Математическая модель такой задачи имеет вид:nn f1(X)  c1 x min,(121) ijiji1 j1… nn k(X)  ckx min,n (122)  xij 1,n j 1, n, (123)  xij 1, i  1, n, (124) {0,1}, i1, n, j 1, n, , i1, n, j h1, n, j*  1, h. (126) f xij гдеP {1,2,.., h}пр.(i, j)  (i, j*)– подмножество индексов работ, распределяемых в первую очередь.В главе 2 показано, что однокритериальная задача с порядком назначений эквивалента совокупности двух последовательно решаемых задач – открытой и с недопустимыми назначениями. Аналогично, многокритериальная задача с порядком назначений эквивалента совокупности двух последовательно решаемых задач – многокритериальной открытой задаче и многокритериальной задаче с недопустимыми назначениями. Следовательно, можно описать алгоритм решения многокритериальной задачи с порядком назначений. Нормировать матрицы затрат Сl, l 1, k: cl clсl ijmin . c  cijl maxlmin Найти размер штрафа Ml 2n. Построить математическую модель назначения на работы из множества P :

Выводы

Заключение

Список использованных источников

Эквивалентные преобразования моделей задач линейного программирования


Преобразования модели задачи линейного программирования называют эквивалентными, если они не влекут изменения оптимального решения задачи. Эквивалентные преобразования моделей задачи линейного программирования состоят в следующем [1]:

  • смена направления целевой функции при изменении ее знака:

fmax (x) fmin (x) ;

  • преобразование i-го ограничения-неравенства в ограничение- равенство путем введения дополнительных неотрицательных неизвестных:

ai1x1 ai2 x2 ... ainxn bi ai1x1 ai2 x2 ... ainxn si bi, si 0;

  • замена в целевой функции и во всех ограничениях неизвестной, не подчиненной условию неотрицательности, разностью двух новых неотрицательных неизвестных:

xj



xq xp,

xj 0 xq 0,


x
p
  0.
Вычислительный аппарат линейного программирования основан на эквивалентных преобразованиях моделей задач. Две модели полагают эквивалентными, если одна получена из другой с помощью эквивалентных преобразований. Задачи линейного программирования, модели которых получены с помощью эквивалентных преобразований, имеют одно и то же оптимальное решение либо обе не ограничены. Это означает, что если существует алгоритм нахождения оптимального решения одной из задач, то он может быть применен для решения эквивалентной ей.

    1. Простейшая линейная модель задачи о назначениях и ее особенности


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

исполнителей. Известны трудовые затраты

cij

на выполнение i-м


исполнителем j-й работы,

cij 0

( i1, n,

j 1, n), Каждому исполнителю


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

Математическая модель простейшей линейной задачи о назначениях имеет вид:

nn

f(X) cijxij min,

i1 j1
(1)

n

xij 1, j 1, n,

i1

(2)

n

xij 1, i 1, n,

j1

(3)

xij{0,1}, i, j 1, n,
(4)




где

X (xij)

– матрица бинарного отношения R, описывающего


назначение исполнителю работы:


xij

1, если (i, j) R,



0, если (i, j)  R.

Простейшей линейной модели задачи о назначениях присущи следующие особенности:

  • целевая функция стремится к минимуму;

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

  • матрица

X (xij)

бинарного отношения R, называемая матрицей


назначений, обладает тем свойством, что в каждой строке и в каждом столбце этой матрицы имеется ровно одна единица, остальные элементы матрицы являются нулями;

  • все элементы матрицы затрат С (сij)

неотрицательны;




  • ограничения задачи описываются только уравнениями;

  • свободные члены всех уравнений равны единице.



Анализ алгоритмов решения простейшей линейной задачи о назначениях


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

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

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

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

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

Теорема 1. Оптимальное решение задачи о назначениях не изменится, если к любой строке или столбцу матрицы затрат C прибавить (или вычесть) постоянную величину.

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

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

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

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

Разработана программа поиска решения простейшей линейной задачи о назначениях средствами математического пакета «Mathcad» (листинг 1).

Листинг 1 – Алгоритм поиска оптимального решения простейшей линейной задачи о назначениях

Смотрите также файлы