Задача 1 Задача о назначениях
Распределить пятерых работников между пятью работами, если затраты, обусловленные выполнением работ, приведены в таблице 1.
Таблица 1 – Затраты обусловленные выполнением работ
| В1 | В2 | В3 | В4 | В5 | |
| A1 | |||||
| A2 | |||||
| A3 | |||||
| A4 | |||||
| A5 |
Составить экономико-математическую модель и решить задачу с помощью надстройки «Поиск решения».
Решение:
Экономико-математическая модель:
Целевая функция:
целевая функция будет стремиться к минимуму так как мы стремимся минимизировать наши затраты по выполнению работ.
Ограничения:
xij – равное 1 показывает, что i-го работника необходимо назначить на выполнение j-ой работы.
Экономико-математическая модель задачи составлена. Решим эту задачу с использованием надстройки Excel «Поиск решения».
На рисунке 1 представлен ход работы утилиты «Поиск решения».
Рисунок 1 – Ход работы утилиты Поиск решения
На рисунке 2 представлен результат решения задачи.
Рисунок 2 – Результат решения задачи
Вывод: из рисунка 2 следует, что для того, чтобы общая величина затрат была минимальной необходимо для выполнения работы А1 назначить работника В4, А2 – В3, А3 – В5, А4 – В1, А5 – В2, при этом суммарные затраты будут минимальны и составят 25 ед.
Задача 2 Транспортная задача
Исходная информация транспортной задачи представлена в таблице 2.
Таблица 2 – Исходные данные
| В1 | В2 | В3 | В4 | Запасы | |
| А1 | |||||
| А2 | |||||
| А3 | |||||
| Потребности |
Определить:
1. приближенный план, схему перевозок, а также его стоимость методом северо-западного угла;
2. приближенный план, схему перевозок, а также его стоимость методом минимального элемента;
3. оптимальный план, схему перевозок, а также его стоимость с помощью надстройки «Поиск решения».
Решение:
Метод северо-западного угла
Проверим необходимое и достаточное условие разрешимости задачи.
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 3 (120—117). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.
Занесем исходные данные в распределительную таблицу 3.
Таблица 3 – Распределительная таблица
| В1 | В2 | В3 | В4 | В5 | Запасы | |
| А1 | ||||||
| А2 | ||||||
| А3 | ||||||
| Потребности |
Первый опорный план начинается заполняться с верхнего левого угла (таблица 4).
Таблица 4 – Опорный план 1
| В1 | В2 | В3 | В4 | В5 | Запасы | ||||
| А1 | u1=0 | ||||||||
| А2 | u2=-2 | ||||||||
| А3 | u3=-4 | ||||||||
| v1=3 | v2=6 | v3=10 | v4=5 | v5=4 | |||||
| Потребности |
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 3*30 + 6*10 + 4*17 + 8*23 + 6*7 + 1*30 + 0*3 = 474
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1+ v1= 3; 0 + v1 = 3; v1 = 3
u1 + v2 = 6; 0 + v2 = 6; v2 = 6
u2 + v2 = 4; 6 + u2 = 4; u2 = -2
u2 + v3 = 8; -2 + v3 = 8; v3 = 10
u3 + v3 = 6; 10 + u3 = 6; u3 = -4
u3 + v4 = 1; -4 + v4 = 1; v4 = 5
u3 + v5 = 0; -4 + v5 = 0; v5 = 4
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;3): 0 + 10 > 5; ∆13 = 0 + 10 - 5 = 5
(1;4): 0 + 5 > 2; ∆14 = 0 + 5 - 2 = 3
(1;5): 0 + 4 > 0; ∆15 = 0 + 4 - 0 = 4
(2;5): -2 + 4 > 0; ∆25 = -2 + 4 - 0 = 2
max(5,3,4,2) = 5
Выбираем максимальную оценку свободной клетки (1;3): 5
Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» (таблица 5).
Таблица 5 – Цикл 1
| В1 | В2 | В3 | В4 | В5 | |||||
| А1 | u1=0 | ||||||||
| - | + | ||||||||
| А2 | u2=-2 | ||||||||
| + | - | ||||||||
| А3 | u3=-4 | ||||||||
| v1=3 | v2=6 | v3=10 | v4=5 | v5=4 |
Цикл приведен в таблице (1,3 → 1,2 → 2,2 → 2,3).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план (таблица 6).
Таблица 6 – Опорный план 2
| В1 | В2 | В3 | В4 | В5 | |||||
| А1 | u1=0 | ||||||||
| А2 | u2=3 | ||||||||
| А3 | u3=1 | ||||||||
| v1=3 | v2=1 | v3=5 | v4=0 | v5=-1 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 3; 0 + v1 = 3; v1 = 3
u1 + v3 = 5; 0 + v3 = 5; v3 = 5
u2 + v3 = 8; 5 + u2 = 8; u2 = 3
u2 + v2 = 4; 3 + v2 = 4; v2 = 1
u3 + v3 = 6; 5 + u3 = 6; u3 = 1
u3 + v4 = 1; 1 + v4 = 1; v4 = 0
u3 + v5 = 0; 1 + v5 = 0; v5 = -1
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;1): 3 + 3 > 3; ∆21 = 3 + 3 - 3 = 3
(2;5): 3 -1 > 0; ∆25 = 3 -1 - 0 = 2
max(3,2) = 3
Выбираем максимальную оценку свободной клетки (2;1): 3
Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» (таблица 7).
Таблица 7 – Цикл 2
| В1 | В2 | В3 | В4 | В5 | |||||
| А1 | u1=0 | ||||||||
| - | + | ||||||||
| А2 | u2=3 | ||||||||
| + | - | ||||||||
| А3 | u3=1 | ||||||||
| v1=3 | v2=1 | v3=5 | v4=0 | v5=-1 |
Цикл приведен в таблице (2,1 → 2,3 → 1,3 → 1,1).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 13. Прибавляем 13 к объемам грузов, стоящих в плюсовых клетках и вычитаем 13 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план 3 (таблица 8).
Таблица 8 – Опорный план 3
| В1 | В2 | В3 | В4 | В5 | |||||
| А1 | u1=0 | ||||||||
| А2 | u2=0 | ||||||||
| А3 | u3=1 | ||||||||
| v1=3 | v2=4 | v3=5 | v4=0 | v5=-1 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1= 0.
u1 + v1 = 3; 0 + v1 = 3; v1 = 3
u2 + v1 = 3; 3 + u2 = 3; u2 = 0
u2 + v2 = 4; 0 + v2 = 4; v2 = 4
u1 + v3 = 5; 0 + v3 = 5; v3 = 5
u3 + v3 = 6; 5 + u3 = 6; u3 = 1
u3 + v4 = 1; 1 + v4 = 1; v4 = 0
u3 + v5 = 0; 1 + v5 = 0; v5 = -1
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(3;2): 1 + 4 > 3; ∆32 = 1 + 4 - 3 = 2
Выбираем максимальную оценку свободной клетки (3;2): 3
Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» (таблица 9).
Таблица 9 – Цикл 3
| В1 | В2 | В3 | В4 | В5 | |||||
| А1 | u1=0 | ||||||||
| - | + | ||||||||
| А2 | u2=0 | ||||||||
| + | - | ||||||||
| А3 | u3=1 | ||||||||
| + | - | ||||||||
| v1=3 | v2=4 | v3=5 | v4=0 | v5=-1 |
Цикл 3 приведен в таблице (3,2 → 3,3 → 1,3 → 1,1 → 2,1 → 2,2).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 7. Прибавляем 7 к объемам грузов, стоящих в плюсовых клетках и вычитаем 7 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план 4.
Таблица 10 – Опорный план 4
| В1 | В2 | В3 | В4 | В5 | |||||
| А1 | u1=0 | ||||||||
| А2 | u2=0 | ||||||||
| А3 | u3=-1 | ||||||||
| v1=3 | v2=4 | v3=5 | v4=2 | v5=1 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1= 0.
u1 + v1 = 3; 0 + v1 = 3; v1 = 3
u2 + v1 = 3; 3 + u2 = 3; u2 = 0
u2 + v2 = 4; 0 + v2 = 4; v2 = 4
u3 + v2 = 3; 4 + u3 = 3; u3 = -1
u3 + v4 = 1; -1 + v4 = 1; v4 = 2
u3 + v5 = 0; -1 + v5 = 0; v5 = 1
u1 + v3 = 5; 0 + v3 = 5; v3 = 5
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;5): 0 + 1 > 0; ∆15 = 0 + 1 - 0 = 1
(2;5): 0 + 1 > 0; ∆25 = 0 + 1 - 0 = 1
max(1,1) = 1
Выбираем максимальную оценку свободной клетки (1;5): 0
Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» (таблица 11).
Таблица 11 – Цикл 4
| В1 | В2 | В3 | В4 | В5 | |||||
| А1 | u1=0 | ||||||||
| - | + | ||||||||
| А2 | u2=0 | ||||||||
| + | - | ||||||||
| А3 | u3=-1 | ||||||||
| + | - | ||||||||
| v1=3 | v2=4 | v3=5 | v4=2 | v5=1 |
Цикл 4 приведен в таблице (1,5 → 1,1 → 2,1 → 2,2 → 3,2 → 3,5).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 5) = 3. Прибавляем 3 к объемам грузов, стоящих в плюсовых клетках и вычитаем 3 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план 5 (таблица 12).
Таблица 12 – Опорный план 5
| В1 | В2 | В3 | В4 | В5 | |||||
| А1 | u1=0 | ||||||||
| А2 | u2=0 | ||||||||
| - | |||||||||
| А3 | u3=-1 | ||||||||
| v1=3 | v2=4 | v3=5 | v4=2 | v5=0 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1= 0.
u1 + v1 = 3; 0 + v1 = 3; v1 = 3
u2 + v1 = 3; 3 + u2 = 3; u2 = 0
u2 + v2 = 4; 0 + v2 = 4; v2 = 4
u3 + v2 = 3; 4 + u3 = 3; u3 = -1
u3 + v4 = 1; -1 + v4 = 1; v4 = 2
u1 + v3 = 5; 0 + v3 = 5; v3 = 5
u1 + v5 = 0; 0 + v5 = 0; v5 = 0
Опорный план 5 является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Минимальные затраты составят:
F(x) = 3*7 + 5*30 + 0*3 + 3*23 + 4*17 + 3*10 + 1*30 = 368
Схема перевозок:
из 1-го склада необходимо груз направить 1-му потребителю в количестве 7 ед., 3-му потребителю в количестве 30 ед.;
из 2-го склада необходимо груз направить 1-му потребителю – 23 ед., 2-му потребителю – 17ед.;
из 3-го склада необходимо груз направить второму потребителю – 10 ед., 4-му – 30 ед.
На 1-ом складе остался невостребованным груз в количестве 3 ед.
Оптимальный план является вырожденным, так как базисная переменная x15=0.