Задача о назначениях: метод приоритетных связей

Размещено на http://www.allbest.ru/

Задача о назначениях: метод приоритетных связей

Вступление

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

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

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

В данной статье представлен новый метод решения задачи о назначениях - метод приоритетных связей.

1. Постановка задачи

Имеется m групп людей (станков) численностью a1, a2, …, am, которые должны выполнять n видов работ (операций) объёмом b1, b2, …, bn.

Известна производительность каждой i - ой группы людей (станков) при выполнении каждого j - го вида работ (операций) cij, i = 1, 2, …, m, j = 1, 2, …, n. Требуется так распределить людей (станки) для выполнения работ (операций), чтобы суммарный объём производства работ (операций) был максимальным.

Математическая модель данной задачи выглядит следующим образом:

(2.1.)

i = 1, 2, …, m, (2.2.)

j = 1, 2, …, n, (2.3.)

xij 0, i = 1, 2, …, m, j = 1, 2, …, n, (2.4.)

где:

xij - число людей (станков) i - ой группы, занятых j - м видом работ (операций).

Для перехода от нахождения максимума к нахождению минимума нужно умножить коэффициенты целевой функции на (-1). Тогда целевая функция будет иметь вид

(2.5.)

Алгоритм решения:

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

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

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

Решим пример задачи о назначениях (на минимум):

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

При этом приоритетные схемы должны быть полными, т.е. количество связей в схеме должно быть равно строго n - 1, где n - количество строк исходной квадратичной матрицы.

Ниже показаны приоритетные схемы, соответствующие им планы и величины целевых функций f(x), полученные при решении:

Получены два оптимальных решения, где целевая функция f(x) = 6.

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

Получено одно оптимальное решение (Матрица 21), где целевая функция f(x) = 26. Разработана программа и примеры с ответами: mps_nazn.exe - программа решения задачи; mps_nazn_instruk.doc - инструкция по применению программы решения задачи; primery_nazn_mps.zip - примеры решения задач о назначениях на максимум и на минимум с ответами.

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

Но практическое предпочтение остается за размерностями лишь от 3х3 до 12х12, т.к. при размерности 11х11 время решения задачи составляет 30 сек., но уже при матрице 12х12 - 4 мин. 30 сек.

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

задача назначение метод приоритетная связь

2. Глоссарий

Элементарная матрица - матрица размерностью 2х2 (матрица 22);

Элементарная связь - воображаемая линия между диагонально расположенными элементами элементарной матрицы (матрицы 23 и 24);

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

Схема решения - совокупность соединенных между собой элементарных связей, отражающая одно из решений;

Приоритетная схема решения - совокупность соединенных между собой приоритетных связей;

Оптимальная схема - одна (или несколько) из приоритетных схем, отражающих оптимальное решение;

План - одно из допустимых решений, удовлетворяющее системе ограничений и условиям неотрицательности;

Целевая функция - функция переменных задачи, которая характеризует качество выполнения задачи и экстремум которой требуется найти;

Вычеркивание - исключение из исходной матрицы строки и столбца, на пересечении которых находится выбранный элемент;

Размещено на Allbest.ru