Фирма «Три Толстяка» занимается доставкой мясных консервов с трёх складов
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
Фирма «Три Толстяка» занимается доставкой мясных консервов с трёх складов, расположенных в разных точках города в три магазина. Запасы консервов, имеющиеся на складах, а также объёмы заказов магазинов и тарифы на доставку (в условных денежных единицах) представлены в транспортной таблице 2.1.
Таблица 2.1 – Транспортная таблица
Склады Магазины Запасы, тыс. шт.
№1 №2 №3
Склад № 1 3 5 1 700
Склад № 2 7 2 3 200
Склад № 3 4 3 1 100
Заказы, тыс. шт. 300 500 200
Найти план перевозок, обеспечивающий наименьшие денежные затраты.
Нужно полное решение этой работы?
Ответ
Наименьшие затраты на перевозку составят min условных денежных единиц при оптимальном плане перевозок:
.
Решение
Записываем исходные данные задачи (табл. 2.2):
Таблица 2.3 – Исходные данные
A\B 300 500 200
700 3 5 1
200 7 2 3
100 4 3 1
Целевая функция:
.
– вектор запасов поставщиков (склады №1, №2, №3),
– вектор запросов потребителей (магазины №1, №2, №3).
Проверяем выполнение необходимого и достаточного условия разрешимости задачи. Находим суммарные запасы поставщиков и суммарные запросы потребителей:
;
.
Так как имеем задачу с правильным балансом.
Находим начальное опорное решение методом северо-западного угла (табл. 2.3).
Таблица 2 3 – Опорное решение. 1-й шаг метода потенциалов
A\B 300 500 200
700 3
300 5
400 [-] 1
[+]
200 7
2
100 [+] 3
100 [-]
100 4
3
1
100
Значение целевой функции на данном опорном решении:
.
Решаем задачу методом потенциалов.
Для проверки оптимальности опорного решения находим потенциалы
. Записываем систему уравнений для нахождения потенциалов. Система состоит из 5 уравнений и имеет 6 неизвестных. Система неопределённая. Одному из потенциалов задаём значение произвольно: пусть u1 = 0. Получаем:
Проверяем опорное решение на оптимальность. Для этого вычисляем оценки для всех незаполненных клеток таблицы:
;
;
;
.
Полученное опорное решение не является оптимальным, т.к. имеются положительные оценки.
Шаг 1.
Переходим к новому опорному решению. Для клетки (1, 3) строим цикл (табл. 2.3). Осуществляем сдвиг по циклу на величину