Задача о назначениях

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

Задача о назначениях

Вступление

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

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

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

Имеется m групп людей (станков) численностью a₁, a₂, …, a_m, которые должны выполнять n видов работ (операций) объёмом b₁, b₂, …, b_n.

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

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

(2.1.)

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

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

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

где:

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

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

(2.5.)

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

1. Во всех возможных элементарных матрицах, из которых состоит исходная матрица, расставляем приоритетные связи (Матрица 1);

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

3. В матрице связей выбираем элемент с максимальным значением количества приоритетных связей. Если таких элементов несколько, выбираем первый попавшийся на пути их анализа слева направо сверху вниз;

4. По координатам выбранного в матрице связей элемента находим элемент исходной матрицы и включаем его в целевую функцию;

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

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

Решим два примера, один - на максимум (Матрица 1), другой - на минимум (Матрица 9). В них обозначены

Матрица А - исходная матрица;

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

Матрица V - матрица связей после вычеркивания;

Матрица P - матрица, показывающая оптимальный план решения задачи;

Звездочкой обозначены выбранные для оптимального плана элементы A.

Матрица 1

S V P

V P

V P

f(x) = 7 + 9 + 1 + 9 = 26

Матрица 9

S V P

V P

V P

V P

f(x) = 11 + 0 + 4 + 7 = 22

Разработана программа:

sliding_nazn.exe - программа решения задачи, в Интернете искать по адресу smetod1.narod.ru/ sliding_nazn.zip;

sliding_nazn_instruk.doc - инструкция по применению программы решения задачи, в Интернете искать по адресу smetod1.narod.ru/ sliding_nazn_instruk.doc;

Преимущества:

Минимальные затраты машинного времени.

Возможность решения задач, исходные матрицы которых большеразмерны, т.е. от 10х10 до 120х120.

Примечание.

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

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

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

И все-таки автор данную программу подверг определенному тестированию, т.е. проверке на ее способность давать оптимальный результат. Тестирование было своеобразным и простым.

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

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

Не прибегая к особому решению, можно констатировать, что в первом случае целевая функция f(x) д.б. равной нулю, во втором - числу 300, умноженному на одностороннюю размерность исходной матрицы, для матрицы 120х120 это число 120. То есть, оптимальный результат решения задачи заранее известен: в задаче на минимум f(x) = 0 для матрицы любой (в пределах объявленного диапазона) размерности, в задаче на максимум f(x) = 300*120 = 36000 для матрицы, к примеру, 120х120.

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

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

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

Обобщая сказанное, следует вывод, что малоемкие задачи о назначениях - от 3х3 до 10х10 - лучше всего методом приоритетных связей: быстро и с получением 100%-го оптимума.

Слайдовый же метод целесообразно применять в задачах больших по емкости - от 11х11 до 120х120: не менее быстро, но с некоторой долей недобора оптимальности результата.

Размышления:

Если бы существовала некая другая (назовем ее обобщенной) оптимальность, то ее формула выглядела бы следующим образом:

О =

где:

О - обобщенная оптимальность, измеряется в единицах опт,

1 опт = 1 ;

матрица большеразмерный оптимальность программа

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

время получения результата - время, потраченное на реализацию программы для получения целевой функции, т.е. результата решения (внедряется временной фактор, которого нет, например, в оптимальном раскрое картона для упаковочной тары: один раз этот оптимальный раскрой определили и используют его вне зависимости от времени).

Для показа сравнимости и значения формулы возьмем два факта.

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

О₁ = 100/129600 = 0.0008 опт

Для получения результата решения задачи о назначениях с ожидаемым процентом оптимальности (пусть это будет 80%) при исходной матрице 120х120 слайдовым методом требуется не более 6 минут. Вычислим обобщенную оптимальность для этого случая.

О₂ = 80/6 = ок. 14 опт

Обобщенная оптимальность во втором случае больше, чем в первом, в 17500 раз. Так что, в обобщенном смысле второй случай в 17500 раз «оптимальнее» первого, хотя в этом случае абсолютная оптимальность и ниже, т.е. 80%. Время представляется более предпочтительной величиной, к которой надо стремиться, чем сама оптимальность. И под завершение статьи хочется озадачить читателя еще одним вопросом, над которым, кажется, еще никто не задумывался. Исходная матрица для задачи о назначениях заполняется экспертными оценками полностью.

А что, если в силу каких-либо причин таких оценок не достает до полного заполнения матрицы? Т.е. исходная матрица имеет «дыры»? А задачу решить нужно, нужно хоть как-то, хоть с какой-то оптимальностью, хочется, чтобы задача рассчитала пусть наполовину эффективный ответ. Особенно в большеразмерных матрицах.

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

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