EMMUP(var7)
.pdf
Таблица 6.1.
Исходные данные левой части
ВС |
ВЛ1 ВЛ2 ВЛ3 ВЛ4 m=5 |
||||
1 |
18 |
21 |
23 |
1 |
3 |
2 |
17 |
20 |
22 |
24 |
2 |
3 |
16 |
19 |
21 |
23 |
1 |
4 |
15 |
18 |
20 |
22 |
24 |
n=5 |
14 |
17 |
19 |
21 |
23 |
Алгоритм решения задачи о назначениях для левой части табл. 6.0.
Шаг 3. Находим в каждой строке min cij и вычитаем его из cij i-й строки
18 |
21 |
23 |
1 |
3 |
1 |
17 |
20 |
22 |
24 |
2 |
2 |
16 |
19 |
21 |
23 |
1 |
1 |
15 |
18 |
20 |
22 |
24 |
15 |
14 |
17 |
19 |
21 |
23 |
14 |
Шаг 4. Находим в каждом столбце получившейся матрицы min cij и вычитаем его из cij. Получаем матрицу С1.
17 |
20 |
22 |
0 |
2 |
15 |
18 |
20 |
22 |
0 |
15 |
18 |
20 |
22 |
0 |
0 |
3 |
5 |
7 |
9 |
0 |
3 |
5 |
7 |
9 |
0 |
3 |
5 |
0 |
0 |
17 |
17 |
17 |
0 |
2 |
15 |
15 |
15 |
22 |
0 |
15 |
15 |
15 |
22 |
0 |
0 |
0 |
0 |
7 |
9 |
0 |
0 |
0 |
7 |
9 |
Итерация I
Шаг 5. Идем сверху вниз по строкам матрицы С1. Встретив в строке ноль
без пометок, помечаем его знаком *, а остальные 0 вправо до конца
строки и вниз до конца солбца помечаем ^. 0* называется помечен-
ным, а 0^ - непомеченным:
|
17 |
|
17 |
|
17 |
|
0 |
* |
2 |
# |
15 |
|
15 |
|
15 |
|
22 |
|
0 * |
15 |
|
15 |
|
15 |
|
22 |
|
0 ^ |
|
|
0 |
* |
0 |
^ |
0 |
^ |
7 |
|
9 |
|
0 |
^ |
0 |
* |
0 |
^ |
7 |
|
9 |
Шаг 6. Помечаем знаком # строки с 0^ (без 0*).
Шаг 7. В строках со знаком # помечаем знаком # столбцы, в которых стоит
0^.
Шаг 8. В столбце, помеченном знаком #, находим 0* и помечаем знаком #
строку, в которой он стоит:
& |
17 |
|
17 |
|
17 |
|
0 |
* |
2 |
& |
15 |
|
15 |
|
15 |
|
22 |
|
0 * |
# |
15 |
|
15 |
|
15 |
|
22 |
|
0 ^ |
& |
0 |
* |
0 |
^ |
0 |
^ |
7 |
|
9 |
& |
0 |
^ |
0 |
* |
0 |
^ |
7 |
|
9 |
Шаг 9. Помечаем знаком & столбцы со знаком # и строки без знака #. Зачеркиваем все нули min числом прямых линий.
Шаг 10.Ищем Δ=min не зачеркнутое cij. Вычитаем |
из незачеркнутых cij. |
|
|||||||||||
|
Прибавляем |
к зачеркнутым 2 раза cij. Не меняем cij зачеркнутые |
|
||||||||||
|
1 раз (Δ выделено цветом). |
|
|
|
|
|
|
|
|||||
& |
|
|
|
|
|
|
|
Матрица С2 |
|
|
|||
17 |
|
17 |
17 |
0 |
2 |
|
2 |
2 |
2 |
0 |
2 |
||
# |
15 |
|
15 |
15 |
22 |
0 |
|
0 |
0 |
0 |
22 |
0 |
|
& |
15 |
|
15 |
15 |
22 |
0 |
|
0 |
0 |
0 |
22 |
0 |
|
|
& |
0 |
|
0 |
0 |
7 |
9 |
|
0 |
0 |
0 |
22 |
24 |
|
# |
0 |
|
0 |
0 |
7 |
9 |
|
0 |
0 |
0 |
22 |
24 |
|
|
|
Зачеркиваем 0 |
|
|
Вычитаем ( |
прибавляем) |
|
|||||
Полученный план не оптимален. Возвращаемся на шаг 5 и повторяем шаги 5-10, выполняя итерацию 2.
Итерация II
Шаг 11.Идем сверху вниз по строкам матрицы С2. Встретив в строке ноль
без пометок, помечаем его знаком *, а остальные 0 вправо до конца
строки и вниз до конца солбца помечаем ^. 0* называется помечен-
ным, а 0^ - непомеченным:
2 |
2 |
2 |
0 |
* |
2 |
|
0 * |
0 ^ |
0 ^ |
22 |
|
0 |
^ |
0 ^ |
0 * |
0 ^ |
22 |
|
0 |
^ |
0 ^ |
0 ^ |
0 * |
22 |
|
24 |
|
0 ^ |
0 ^ |
0 ^ |
22 |
|
24 |
|
Шаг 12.Помечаем знаком # строки с 0^ (без 0*).
Шаг 13.В строках со знаком # помечаем знаком # столбцы, в которых стоит
0^.
Шаг 14.В столбце, помеченном знаком #, находим 0* и помечаем знаком #
строку, в которой он стоит:
|
# |
# |
# |
|
|
|
|
|
2 |
2 |
2 |
0 |
* |
2 |
|
|
0 * |
0 ^ |
0 ^ |
22 |
|
0 |
^ |
# |
0 ^ |
0 * |
0 ^ |
22 |
|
0 |
^ |
# |
0 ^ |
0 ^ |
0 * |
22 |
|
24 |
|
# |
0 ^ |
0 ^ |
0 ^ |
22 |
|
24 |
|
Полученный план оптимален, так как во всех строках и столбцах
имеется 0*
Шаг 15.Формируем матрицу назначений, меняя 0* на 1 и 0^ на 0. Суммируем cij стоящие в клетках с 1 в X и находим оптимальный план на Z.
|
Матрица Х |
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
0 |
18 |
21 |
23 |
1 |
3 |
1 |
0 |
0 |
0 |
0 |
17 |
20 |
22 |
24 |
2 |
0 |
1 |
0 |
0 |
0 |
16 |
19 |
21 |
23 |
1 |
0 |
0 |
1 |
0 |
0 |
15 |
18 |
20 |
22 |
24 |
0 |
0 |
0 |
0 |
1 |
14 |
17 |
19 |
21 |
23 |
Критерий оптимального плана Z= |
80 |
|
|
|
|
||||
Таблица 6.2.
Исходные данные правой части
ВС |
ВЛ1 ВЛ2 ВЛ3 ВЛ4 m=5 |
||||
1 |
20 |
21 |
22 |
23 |
24 |
2 |
17 |
18 |
19 |
20 |
21 |
3 |
15 |
16 |
17 |
18 |
19 |
4 |
13 |
14 |
15 |
16 |
17 |
n=5 |
11 |
12 |
13 |
14 |
15 |
Алгоритм решения задачи о назначениях для правой части табл. 6.0.
Итерация I
Шаг 16.Находим в каждой строке min cij и вычитаем его из cij i-й строки
20 |
21 |
22 |
23 |
24 |
20 |
17 |
18 |
19 |
20 |
21 |
17 |
15 |
16 |
17 |
18 |
19 |
15 |
13 |
14 |
15 |
16 |
17 |
13 |
11 |
12 |
13 |
14 |
15 |
11 |
Шаг 17.Находим в каждом столбце получившейся матрицы min cij и вычитаем его из cij. Получаем матрицу С1.
0 |
1 |
2 |
3 |
4 |
0 |
1 |
2 |
3 |
4 |
0 |
1 |
2 |
3 |
4 |
0 |
1 |
2 |
3 |
4 |
0 |
1 |
2 |
3 |
4 |
0 |
1 |
2 |
3 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Шаг 14.Идем сверху вниз по строкам матрицы С1. Встретив в строке ноль
без пометок, помечаем его знаком *, а остальные 0 вправо до конца
строки и вниз до конца солбца помечаем ^. 0* называется помечен-
ным, а 0^ - непомеченным:
0 * |
0 ^ |
0 ^ |
0 ^ |
0 ^ |
0 ^ |
0 * |
0 ^ |
0 ^ |
0 ^ |
0 ^ |
0 ^ |
0 * |
0 ^ |
0 ^ |
0 ^ |
0 ^ |
0 ^ |
0 * |
0 ^ |
0 ^ |
0 ^ |
0 ^ |
0 ^ |
0 * |
Полученный план оптимален, так как во всех строках и столбцах
присутствует 0*. Матрица Х
1 |
0 |
0 |
0 |
0 |
20 |
21 |
22 |
23 |
24 |
0 |
1 |
0 |
0 |
0 |
17 |
18 |
19 |
20 |
21 |
0 |
0 |
1 |
0 |
0 |
15 |
16 |
17 |
18 |
19 |
0 |
0 |
0 |
1 |
0 |
13 |
14 |
15 |
16 |
17 |
0 |
0 |
0 |
0 |
0 |
11 |
12 |
13 |
14 |
15 |
Критерий оптимального плана Z= |
86 |
|
|
|
|
||||
Шаг 26.По матрицам назначений находим пары оптимально спариваемых
|
рейсов: |
|
|
|
|
|
|
|
|
|
|
|
|
а) |
1-14 |
2-11 3-12 4-13 |
5-15 |
|
Z= 80 |
|
|
||||
|
б) |
11-1 |
12-2 |
13-3 |
14-4 |
15-5 |
|
Z= 86 |
Таблица 6.0. |
|||
|
|
|
|
|
|
|
|
|
|
|
||
|
Время нахождения ВС на земле для любой пары рейсов |
|
||||||||||
B |
11 |
12 |
13 |
14 |
15 |
A |
1 |
2 |
3 |
4 |
5 |
|
1 |
18 |
21 |
|
23 |
1 |
3 |
11 |
20 |
21 |
22 |
23 |
24 |
2 |
17 |
20 |
|
22 |
24 |
2 |
12 |
17 |
18 |
19 |
20 |
21 |
3 |
16 |
19 |
|
21 |
23 |
1 |
13 |
15 |
16 |
17 |
18 |
19 |
4 |
15 |
18 |
|
20 |
22 |
24 |
14 |
13 |
14 |
15 |
16 |
17 |
5 |
14 |
17 |
|
19 |
21 |
23 |
15 |
11 |
12 |
13 |
14 |
15 |
|
|
|
Результаты решения задачи о назначениях |
Таблица 6.4. |
||||||||
|
|
|
|
|
||||||||
B |
11 |
12 |
13 |
14 |
15 |
A |
1 |
2 |
3 |
4 |
5 |
|
1 |
0 |
0 |
|
0 |
1 |
0 |
11 |
1 |
0 |
0 |
0 |
0 |
2 |
1 |
0 |
|
0 |
0 |
0 |
12 |
0 |
1 |
0 |
0 |
0 |
3 |
0 |
1 |
|
0 |
0 |
0 |
13 |
0 |
0 |
1 |
0 |
0 |
4 |
0 |
0 |
|
1 |
0 |
0 |
14 |
0 |
0 |
0 |
1 |
0 |
5 |
0 |
0 |
|
0 |
0 |
1 |
15 |
0 |
0 |
0 |
0 |
0 |
Шаг 27. |
Используя результаты шага 26, находим цепочку (a) рейсов, дающую |
||
|
минимальную сумму времени нахождения каждого ВС на земле |
||
|
1-14 2-11 3-12 4-13 5-15 -1 |
|
|
Шаг 28. |
ВС, вылетающее из A в понедельник в 8.00, выполнит все рейсы |
||
|
цепочки во вторник следующей недели в 20.10 и в среду следующей |
||
|
недели может начать новую цепочку. |
|
9 |
|
Количество дней на цепочку - |
9 |
|
Шаг 29. |
Определяем число ВС: Nвс = Nrsu ntc |
nrsu =10 9 10 = 9 |
|
Литература
1.Пособие к выполнению контрольных работ по дисциплине "Экономико-математические методы управления производством" для студентов 3-го курса специальности 19.07.00 заочного обучения М.: МГТУ ГА, 2015. - 28 с.
2.Андрианов В.В. Алгоритмы методов разработки управленческих решений: Учебное издание. - М.: МГТУ ГА, 2001. - 124 с.