Некоторые теоретические сведения
ЛАБОРАТОРНАЯ РАБОТА
Тема: Задача о назначениях.
1. Учебные цели занятия:
· изучение моделей и методов решения задач по распределению производственных ресурсов;
· изучение и практическое освоение основных понятий теории транспортных задач и задач назначения на примере задачи о распределении работников по производственным объектам;
· экспериментальная (на компьютере) проверка теоретических положений.
Некоторые теоретические сведения.
Задача о назначениях имеет следующую формулировку:
Для выполнения работ B1, B2, …, Bn требуется соответственно b1, b2, …, bn работников. Имеющиеся работники по своей квалификации могут быть разбиты на группы А1, А2, …, Аm, причем количество работников каждой из квалификаций составляет соответственно а1, а2,…, аm чел. Необходимо составить распределение работников по работам с учетом возможных дополнительных условий:
· Несовпадение количества имеющихся и количества требуемых работников и при этом требование непременного выполнения определенных работ (приоритетные работы) или полной загрузки работников некоторой квалификации (приоритетные работники);
· Запрет на выполнение некоторых работ работниками определенных квалификаций;
· Ограничения по количеству (не больше или не меньше) на число работников с данной квалификацией, привлекаемых для выполнения некоторых работ.
Эффективность выполнения работником каждой из работ зависит от уровня его квалификации. Экспертами составлена таблица, в которой величина сij (i=1,…,m; j=1,…,n) представляет собой выраженная в баллах эффективность выполнения работником, имеющим квалификацию Аi, работы типа Bj. Критерием качества распределения работ является выраженная в баллах суммарная эффективность выполнения работ всеми работниками в соответствии с данным распределением.
Определение опорных планов транспортной задачи.
Задача о назначениях является дискретным аналогом транспортной задач линейного программирования. Транспортная задача является частным случаем основной задачи линейного программирования, следовательно, минимальное значение целевой функции достигается в вершине многогранника решений (опорном плане).
Число компонент хij в плане транспортной задачи с m пунктами отправления и n пунктами назначения равно mn, а число уравнений в системе ограничений равно m+n. Ограничившись рассмотрением только закрытых моделей, мы предполагаем выполнение дополнительного условия, что уменьшает ранг системы ограничений транспортной задачи на единицу. Таким образом, опорный план транспортной задачи может иметь не более n+m-1 отличных от нуля переменных.
Если опорный план имеет n+m-1 отличных от нуля переменных, то он называется невырожденным, а если меньше – то вырожденным.
Построение опорных планов транспортной задачи, как и в более общем случае основной задачи линейного программирования, является проблемой, заслуживающей большого внимания. Учет структуры ограничений транспортной задачи позволил разработать специальные методы построения опорных планов более эффективные, чем универсальные методы, используемые в общей теории линейного программирования. Рассмотрим четыре наиболее часто применяемых на практике метода: метод северо-западного угла, метод минимального элемента, метод двойного предпочтения и метод Фогеля.
Сущность этих методов состоит в том, что опорный план находят последовательно за m+n-1 шагов, на каждом из которых в таблице планирования заполняют одну клетку, которую называют занятой. Заполнение одной из клеток обеспечивает полностью либо удовлетворение потребности в грузе пункта назначения (того, в столбце которого находится заполняемая клетка), либо полный вывоз груза из пункта отправления (того, в столбце которого находится заполняемая клетка), либо то и другое вместе.
В первом случае временно исключают из рассмотрения столбец, содержащий заполненную на данном этапе клетку, и рассматривают задачу, таблица планирования которой содержит на один столбец меньше, чем перед этим шагом, но то же количество строк и соответственно измененные запасы груза в одном из пунктов отправления (в том, за счет запаса которого была удовлетворена потребность в грузе пункта назначения на данном шаге).
Во втором случае временно исключают из рассмотрения строку, содержащую заполненную на данном этапе клетку, и рассматривают задачу, таблица планирования которой содержит на один строку меньше, чем перед этим шагом, при неизменном количестве столбцов и при соответствующем изменении потребности в грузе в пункте назначения, в столбце которого находится заполняемая клетка.
Третий случай соответствует построению вырожденного опорного плана. При этом, вообще говоря, следовало бы исключить из матрицы планирования и строку, и столбец, соответствующие этой клетке. Однако поскольку на практике важным является получение m+n-1 (пусть даже часть из них будут нулевыми) базисных компонент опорного плана, обычно поступают следующим образом: из матрицы планирования исключается только соответствующая строка; хотя оставшийся запас пункта отправления, соответствующего рассматриваемому столбцу, равен нулю, далее проводится формальная процедура построения базисных компонент опорного плана транспортной задачи.
После того как проделаны m+n-2 описанных выше шагов, получают задачу с одним пунктом отправления и одним пунктом назначения. При этом останется свободной только одна клетка, а запасы оставшегося пункта отправления будут равны потребностям оставшегося пункта назначения. Заполнив эту клетку, тем самым делают (m+n-1)-й шаг и получают искомый опорный план.
1. Метод северо-западного угла. При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из пунктов назначения. Заполнение клеток таблицы планирования начинается с левой верхней клетки для переменной хij ("северо-западный угол") и заканчивается клеткой для переменной хij.
2. Метод минимального элемента. Сущность метода минимального элемента состоит в последовательном заполнении клеток с минимальными в рассматриваемой части таблицы планирования тарифами. Этот метод, как правило, позволяет найти опорный план транспортной задачи, при котором общая стоимость перевозок груза меньше, чем общая стоимость перевозок при опорном плане, найденном для данной задачи с помощью метода северо-западного угла.
3. Метод двойного предпочтения.В рамках этого метода сначала находится множество клеток с тарифами, минимальными в своих строках, а затем множество клеток с тарифами, минимальными в своих столбцах. Затем производится последовательное в порядке возрастания тарифов заполнение клеток из пересечения этих множеств. Если при этом не удается построить все m+n-1 компонент опорного плана, то производится последовательное в порядке возрастания тарифов заполнение клеток из первого, а затем второго множества вплоть до нахождения опорного плана. Метод двойного предпочтения использует больше информации об исходных данных рассматриваемой транспортной задачи и, как правило, более эффективен с точки зрения величины значения целевой функции на построенном опорном плане, чем метод минимального элемента.
4. Метод аппроксимации Фогеля. При определении опорного плана транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем столбцам и всем строкам находят разность между двумя наименьшими тарифами клеток из этих строк и столбцов. Эти разности записывают в специально отведенных для этого строке и столбце таблицы планирования. Среди указанных разностей выбирают максимальную и в этой строке (столбце) заполняют клетку с минимальным в строке (столбце) тарифом. Метод аппроксимации Фогеля, хотя и сравнительно сложен, является наиболее эффективным из рассмотренных методов построения опорных планов транспортной задачи. Как правило, его применение позволяет получить либо опорный план, близкий к оптимальному, либо сам оптимальный план.
3. Порядок выполнения работы
1. Построить закрытую математическую модель распределения работников по работам в виде задачи назначения в соответствии с вариантом.
2. Построить опорный план полученной задачи о назначениях одним из методов, приведенных в п.2 в соответствии с вариантом.
Вариант 1.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 2 | 2,5 | 3 | 5 | 5 |
| А2 | 1 | 2 | 1 | 1 | 5 |
| А3 | 1,5 | 1 | 3 | 2 | 5 |
| bj | 3 | 5 | 5 | 2 | |
| Дополнительные условия: | а) для выполнения работы B3 должно быть направлено не более 3 работников квалификацииА1 б) для выполнения работы B1 не могут быть привлечены работники квалификацииА3 | ||||
| № метода нахождения опорного плана |
Вариант 2.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 3 | 1,5 | 3 | 4 | 5 |
| А2 | 1 | 1,5 | 3 | 1 | 4 |
| А3 | 1 | 1 | 3 | 2 | 3 |
| bj | 2 | 7 | 2 | 2 | |
| Дополнительные условия: | а) для выполнения работы B2 должно быть направлено не менее 4 работников квалификацииА1; б) работа B1 должна быть полностью обеспечена работниками | ||||
| № метода нахождения опорного плана |
Вариант 3.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 2 | 2,5 | 3 | 5 | 4 |
| А2 | 1 | 2 | 1 | 1 | 4 |
| А3 | 1,5 | 1 | 3 | 2 | 6 |
| bj | 3 | 5 | 5 | 2 | |
| Дополнительные условия: | а) для выполнения работы B3 не могут быть привлечены работники квалификации А3; б) работа B1 должна быть полностью обеспечена | ||||
| № метода нахождения опорного плана |
Вариант 4.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 2 | 3 | 5 | 1 | 5 |
| А2 | 4 | 2 | 2 | 1 | 4 |
| А3 | 1,5 | 1,5 | 3 | 2 | 10 |
| bj | 2 | 8 | 3 | 1 | |
| Дополнительные условия: | а) все работники квалификации А3 должны быть привлечены к работе; б) для выполнения работы B2 должно быть направлено не менее 3 работников квалификацииА3 | ||||
| № метода нахождения опорного плана |
Вариант 5.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 2 | 3 | 5 | 1 | 5 |
| А2 | 4 | 2 | 2 | 1 | 4 |
| А3 | 1,5 | 1,5 | 3 | 2 | 10 |
| bj | 2 | 8 | 3 | 1 | |
| Дополнительные условия: | а) работы B1 и B4 должны быть полностью обеспечены работниками; б) для выполнения работы B2 должно быть направлено не более 1 работника квалификации А1 | ||||
| № метода нахождения опорного плана |
Вариант 6.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 4 | 5 | 1 | 2 | 7 |
| А2 | 2,5 | 1 | 2 | 2 | 5 |
| А3 | 3,5 | 3 | 2 | 4 | 14 |
| bj | 8 | 6 | 3 | 4 | |
| Дополнительные условия: | а) все работники квалификации А2 и А3 должны быть привлечены к работе; б) для выполнения работы B2 должно быть направлено не менее 3 работников квалификацииА2 | ||||
| № метода нахождения опорного плана |
Вариант 7.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 1 | 1,5 | 3,5 | 2 | 10 |
| А2 | 2 | 2 | 4 | 4 | 12 |
| А3 | 3 | 4 | 5 | 2 | 3 |
| bj | 6 | 9 | 6 | 5 | |
| Дополнительные условия: | а) для выполнения работы B4 не могут быть привлечены работники квалификации А3; б) для выполнения работы B2 должно быть направлено не менее 8 работников квалификацииА1 | ||||
| № метода нахождения опорного плана |
Вариант 8.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 2 | 2 | 5 | 3 | 13 |
| А2 | 1 | 2,5 | 1,5 | 4,5 | 11 |
| А3 | 2,5 | 1,5 | 5 | 4 | 14 |
| bj | 10 | 8 | 11 | 12 | |
| Дополнительные условия: | а) работы B1 и B4 должны быть полностью обеспечены работниками; б) для выполнения работы B1 и B3 не могут быть привлечены работники квалификации А3. | ||||
| № метода нахождения опорного плана |
Вариант 9.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 4 | 5 | 3,5 | 2,5 | 30 |
| А2 | 1,5 | 2 | 1 | 5 | 15 |
| А3 | 5 | 1,5 | 3,5 | 5 | 40 |
| bj | 13 | 22 | 14 | 12 | |
| Дополнительные условия: | а) все работники квалификации А1 и А2 должны быть привлечены к работе; б) для выполнения работы B1 не могут быть привлечены работники квалификации А2 | ||||
| № метода нахождения опорного плана |
Вариант 10.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 2 | 5 | 3 | 3 | 12 |
| А2 | 1,5 | 2 | 5 | 5 | 10 |
| А3 | 2 | 4 | 3,5 | 2,5 | 14 |
| bj | 10 | 8 | 14 | 8 | |
| Дополнительные условия: | а) работа B1 должна быть полностью обеспечена работниками; б) для выполнения работы B3 должно быть направлено не более 10 работников квалификацииА1 | ||||
| № метода нахождения опорного плана |
Вариант 11.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 4 | 5 | 1 | 1 | 6 |
| А2 | 1 | 2 | 1 | 1 | 4 |
| А3 | 2,5 | 1 | 3 | 3 | 5 |
| bj | 4 | 5 | 5 | 2 | |
| Дополнительные условия: | а) для выполнения работы B1 должно быть направлено не более 3 работников квалификации А3; б) для выполнения работы B2 не могут быть привлечены работники квалификации А2 | ||||
| № метода нахождения опорного плана |
Вариант 12.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 7 | 2,5 | 3 | 4 | 3 |
| А2 | 1 | 5 | 3 | 1,5 | 4 |
| А3 | 1 | 1 | 3 | 1 | 5 |
| bj | 3 | 6 | 3 | 2 | |
| Дополнительные условия: | а) для выполнения работы B2 должно быть направлено не менее 3 работников квалификацииА3; б) работа B4 должна быть полностью обеспечена работниками | ||||
| № метода нахождения опорного плана |
Вариант 13.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 5 | 2,5 | 8 | 5 | 3 |
| А2 | 1 | 2 | 1 | 1 | 4 |
| А3 | 7,5 | 1 | 3 | 9 | 7 |
| bj | 3 | 5 | 5 | 2 | |
| Дополнительные условия: | а) для выполнения работы B1 не могут быть привлечены работники квалификации А1; б) работа B1 должна быть полностью обеспечена работниками. | ||||
| № метода нахождения опорного плана |
Вариант 14.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 2 | 3 | 5 | 1 | 15 |
| А2 | 4 | 2 | 2 | 1 | 4 |
| А3 | 1,5 | 1,5 | 3 | 2 | 2 |
| bj | 2 | 8 | 3 | 1 | |
| Дополнительные условия: | а) все работники квалификации А3 должны быть привлечены к работе; б) для выполнения работы B2 должно быть направлено не менее 3 работников квалификацииА1. | ||||
| № метода нахождения опорного плана |
Вариант 15.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 1,5 | 2,5 | 3 | 5 | 3 |
| А2 | 1 | 2 | 9 | 1 | 1 |
| А3 | 5 | 7 | 3 | 2 | 4 |
| bj | 3 | 2 | 4 | 2 | |
| Дополнительные условия: | Дополнительные условия: а) работы B1 и B2 должны быть полностью обеспечены работниками; б) для выполнения работы B2 должно быть направлено не более 1 работника квалификации А1 | ||||
| № метода нахождения опорного плана |
Вариант 16.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 5 | 3 | 2,5 | 3 | 13 |
| А2 | 1,5 | 2,5 | 3,5 | 4,5 | 11 |
| А3 | 2,5 | 1,5 | 5 | 4 | 14 |
| bj | 10 | 8 | 11 | 12 | |
| Дополнительные условия: | а) все работники квалификации А2 и А3 должны быть привлечены к работе; б) для выполнения работы B2 должно быть направлено не менее 3 работников квалификацииА2 | ||||
| № метода нахождения опорного плана |
Вариант 16.
| B1 | B2 | B3 | B4 | ai | |
| А1 | 5 | 3 | 2,5 | 3 | 13 |
| А2 | 1,5 | 2,5 | 3,5 | 4,5 | 11 |
| А3 | 2,5 | 1,5 | 5 | 4 | 14 |
| bj | 10 | 8 | 11 | 12 | |
| Дополнительные условия: | а) все работники квалификации А2 и А3 должны быть привлечены к работе; б) для выполнения работы B2 должно быть направлено не менее 3 работников квалификацииА2 | ||||
| № метода нахождения опорного плана |