Задача о назначениях (Метод экспертных оценок)

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

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

Задача о назначениях (Метод экспертных оценок)

1. 

1. Вступление

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

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

Имеется 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.)

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

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

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

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

4. Для начала формирования плана решения задачи, в соответствии с которым и будет вычислено в итоге значение целевой функции f(x), всегда выбираем два элемента исходной матрицы - два любые максимума или любой максимум с любым подмаксимумом.

5. Проводим соответствующие назначения и вычеркивания.

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

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

Пример 1. Решить задачу о назначениях на максимум методом экспертных оценок.

Матрица 1

Отметим максимумы (Матрица 2)

Матрица 2 Матрица 3

Вычеркнем строки и столбцы, исходящие из перекрестков, на которых находятся отмеченные максимумы (Матрица 3).

Матрица решения сформирована (Матрица 4).

Матрица 4

Подсчитаем целевую функцию

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

Пример 2. Решить задачу о назначениях на минимум методом экспертных оценок (Матрица 5).

Матрица 5

Отметим максимумы и подмаксимумы (Матрица 6)

Матрица 6 Матрица 7

Вычеркнем строки и столбцы, исходящие из перекрестков, на которых находятся отмеченные максимумы (Матрица 7).

Матрица решения сформирована (Матрица 8).

Матрица 8

задача метод экспертный оценка

Подсчитаем целевую функцию

F(x) = 1+4+8+10=23

Примечания.

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

2. Очень малое время для расчета задачи.

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

3. Глоссарий

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

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

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

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

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

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

Матрица 22 Матрица 23 Матрица 24 Матрица 25 Матрица 26

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

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

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

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