Текстовая формулировка. Математическая модель. Необходимые и достаточные условия разрешимости транспортной задачи. Свойство системы ограничений.
Методы построения начального опорного решения транспортной задачи: северо-западного угла и минимальной стоимости. Переход от одного опорного решения к другому – не худшему. Распределительный метод, признак оптимальности. Метод потенциалов, признак оптимальности опорного решения. Алгоритм решения транспортной задачи. Транспортная задача с нарушением баланса. Транспортная задача с ограничениями на пропускные возможности.
Формулы
Математическая модель транспортной задачи (тзлп). Необходимое и достаточное условие разрешимости транспортной задачи. Ранг системы векторов условий.
Признак оптимальности в методе потенциалов.
П.2.1. Замкнутая модель ТЗ
Задача 2.1.1. Автотранспортная фирма «Карланд» обеспечивает доставку одних и тех же строительных блоков с двух железобетонных заводов АО «Бетон» на три строительные площадки. На первую площадку требуется доставить b1, на вторую — b2 и на третью — b3 бетонных блоков. С первого завода должны быть отгружены a1, со второго — a2 бетонных блока. Тарифы на перевозку одного блока с каждого из заводов на соответствующую площадку приведены по вариантам:
Таблица 2.1.1.а
Площадка
№ 1
№ 2
№ 3
Отгрузка
Завод 1
a1 = 120
Завод 2
a2 = 100
Заказ
b1 = 70
b2 = 80
b3 = 70
Таблица 2.1.1.b
Площадка
№ 1
№ 2
№ 3
Отгрузка
Завод 1
a1 = 150
Завод 2
a2 = 100
Заказ
b1 =110
b2 = 80
b3 = 60
Таблица 2.1.1.c
Площадка
№ 1
№ 2
№ 3
Отгрузка
Завод 1
a1 = 120
Завод 2
a2 = 80
Заказ
b1 = 70
b2 = 80
b3 = 50
Таблица 2.1.1.d
Площадка
№ 1
№ 2
№ 3
Отгрузка
Завод 1
a1 = 150
Завод 2
a2 = 100
Заказ
b1 = 50
b2 = 80
b3 =120
Таблица 2.1.1.e
Площадка
№ 1
№ 2
№ 3
Отгрузка
Завод 1
a1 = 100
Завод 2
a2 = 140
Заказ
b1 = 80
b2 = 90
b3 =70
Выполните следующие задания:
1. Составьте математическую модель ТЗ.
2. Выпишите матрицу системы ограничений.
3. Определите ранг полученной матрицы.
4. Найдите первый опорный план
а) методом северо-западного угла;
б) методом минимальных тарифов.
5. Решите задачу методом потенциалов.
Задача 2.1.2. С трех складов, расположенных в Химках, на Сходне и в Ховрино, необходимо доставить в пять магазинов сахарный песок в соответствии с заявкой каждого магазина. Объёмы запасов песка, имеющегося на складах, объёмы заявок магазинов и тарифы на поставку одной тонны груза со складов в магазины даны в транспортных таблицах по вариантам: