Системный анализ структуры и функционирования гостиницы "Русский дворик"

Задача о назначениях имеет следующую формулировку:

Для выполнения работ B1,B2,…Вn требуется соответственно b1,b2,…,bn работников. Имеющиеся работники по своей квалификации могут быть разбиты на группы А1,А2,…Аm, причем количество работников каждой из квалификаций составляет соответственно а1,а2,…аm чел. Необходимо составить распределение работников по работам с учетом возможных дополнительных условий:

• Несовпадение количества имеющихся и количества требуемых работников и при этом требование непременного выполнения определенных работ (приоритетные работы) или полной загрузки работников некоторой квалификации (приоритетные работники);
• Запрет на выполнении некоторых работ работниками определенных квалификаций;
• Ограничения по количеству (не больше или не меньше) на число работников с данной квалификацией, привлекаемых для выполнения некоторых работ.
• Эффективность выполнения работником каждой из работ зависит от уровня его квалификации. Экспертами составлена таблица, в которой величина cij (i=1,…m;j=1,…n) представляет собой выраженная в баллах эффективность выполнения работником, имеющим квалификацию Ai, работы типа Bj. Критерием качества распределения работ является выраженная в баллах суммарная эффективность выполнения работ всеми работниками в соответствии с данным распределением.

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

Если опорный план имеет n+m-1 отличных от нуля переменных, то он называется невырожденным, а если меньше - то вырожденным. Учет структуры ограничений транспортной задачи позволил разработать специальные методы построения опорных планов более эффективные, чем универсальные методы, используемые в общей теории линейного программирования. Рассмотрим четыре наиболее часто применяемых на практике метода: метод северо-западного угла, метод минимального элемента, метод двойного предпочтения, метод Фогеля.

Таблица 6

Условие задачи

	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	16            15
Дополнительные условия:		а)для выполнения работы В1 должно быть направлено не более 3 работников квалификации А3 б) для выполнения работы В2 не могут быть привлечены работники квалификации А2

 

Данная модель является открытой (т.к bjai), следовательно нам нужно преобразовать эту модель в закрытую. Т.к в нашей модели недостаток груза, нам нужно добавить фиктивного поставщика с нулевыми тарифами. Дополнительное условие, что для выполнения работы В2 не могут быть привлечены работники квалификации А2 не выполняется, поэтому в клетке (А2;В2) ставится штраф -1000.

                                                                                                                    Таблица 7

Условие задачи после проведенных изменений (описанных выше)

	B1	B2	B3	B4	ai
А1	-4	-5	-1	-1	6
А2	-1	-2           1000	-1	-1	4
А3	-2,5	-1	-3	-3	5
А4	0	0	0	0	1
bj	4	5	5	2	16            16

 

 

Метод северо-западного угла

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

 
                                                                                                                    Таблица8

Решение задачи методом северо-западного угла

	B1	B2	B3	B4	ai
А1	-4               4	-5               2			6(2,-)
А2		-2   1000  3	-1               1		4(1,-)
А3			-3               4	-3                 1	5 (1,-)
А4				0              1	1 (-)
bj	4(-)	5(3,-)	5(4,-)	2(1,-)

 

 

Значение целевой функции для этого опорного плана:

F(x) = 4*(-4)+ 2*(-5) + 3*(1000) + 4*(-3)+ 1*(-1) + 1*(-3)+1*0 = 2958

 

 

 

Метод минимального элемента

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

                                                                                                            Таблица 9

Решение задачи методом минимального элемента

	B1	B2	B3	B4	ai
А1	-4                 1	-5              5	-1	-1	6 (1,-)
А2	-1                3	-2    1000	-1               1	-1	4 (1,-)
А3	-2,5	-1	-3               3	-3               2	5 (3,-)
А4	0	0	0                1	0	1   (-)
bj	4 (3,-)	5(-)	5(2,1,-)	2(-)

 

                                                                                                       

Значение целевой функции для этого опорного плана:

F(x) = 1*(-4)+3*(-1)+5*(-5)+1*(-1)+3*(-3)+1*0+2*(-3)=-48

Метод двойного предпочтения

В рамках этого метода сначала находится множество клеток с тарифами, минимальными в своих строках, а затем множество клеток с тарифами, минимальными в своих столбцах. Затем производится последовательное в порядке возрастания тарифов заполнение клеток из пересечения этих множеств. Если при этом не удается построить все m+n-1 компонент опорного плана, то производится последовательное в порядке возрастания тарифов заполнение клеток из первого, а затем второго множества вплоть до нахождения опорного плана. Метод двойного предпочтения использует больше информации об исходных данных рассматриваемой транспортной задачи и, как правило, более эффективен с точки зрения величины значения целевой функции на построенном опорном плане, чем метод минимального элемента.

 

                                                                                                                 Таблица 10

Нахождение минимальных тарифов в строках и столбцах

 

	B1	B2	B3	B4	ai
А1	-4               ^	-5             ^<	-1	-1	6
А2	-1	-2    1000   <	-1	-1	4
А3	-2,5	-1	-3             ^<	-3             ^<	5
А4	0                <	0                <	0                <	0                <	1
bj	4	5	5	2

 

 

                                                                                                                  Таблица 11

Решение задачи методом двойного предпочтения

 

	B1	B2	B3	B4	ai
А1	-4           ^  1	-5         ^<  5	-1	-1	6 (1,-)
А2	-1               2	-2     1000 <	-1               2	-1	4 (2,-)
А3	-2,5	-1	-3         ^< 3	-3         ^<  2	5 (3,-)
А4	0             < 1	0                <	0                <	0                <	1 (-)
bj	4(3,2,-)	5(-)	5(2,-)	2(-)

 

 

Значение целевой функции для этого опорного плана равно: 
F(x) = 1*(-4)+2*(-1)+1*(0)+5*(-5)+2*(-1)+3*(-3)+2*(-3)=-48

Метод аппроксимации Фогеля

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

                                                                                                               

 

 Таблица 12

Решение задачи о назначениях методом аппроксимации Фогеля

 

	B1	B2	B3	B4	ai
А1	-4               1	-5               5	-1	-1	6 (1,-)
А2	-1               3	-2  1000	-1              1	-1	4 (1,-)
А3	-2,5	-1	-3               3	-3               2	5 (3,-)
А4	0	0	0                1	0	1 (-)
bj	4(3,-)	5(-)	5(2,1,-)	2(-)
	1,5(3,1,-)	3(-)	2(-)	2(1,-)

 

                                                                                                                           
         Значение целевой функции для этого опорного плана равно: 
F(x) =1*(-4)+3*(-1)+5*(-5)+1*(-1)+3*(-3)+1*(0)+2*(-3)=-48

Таким образом, минимальное значение целевой функции F(x)=-48 было получено в ходе решения с помощью метода минимального элемента, двойного предпочтения и метода аппроксимации Фогеля. Максимальное значение целевой функции было получено с помощью метода северо-западного угла F(x)=2958.