Раздел 2. Транспортная задача
П.2.1. Замкнутая и открытая модели ТЗ
Пример 1. Решить транспортную задачу методом потенциалов.
bj ai | ||||
1. Проверим, является ли данная задача замкнутой.
Подсчитаем суммарные запасы груза и суммарные потребности заказчиков ,
.
Поскольку , модель транспортной задачи замкнутая, и задача имеет оптимальный план.
2. Построим первый опорный план транспортной задачи методом северо-западного угла.
Начинаем заполнение распределительной таблицы с верхней левой клетки, то есть построение исходного опорного плана начинаем с удовлетворения потребностей первого потребителя b1 за счет запасов первого поставщика a1. Для этого сравниваем запас a1 = 200 с потребностями b1 = 150. Так как a1 > b1, то потребности b1 полностью удовлетворяем за счет a1, и в первую клетку помещаем min (200, 150)=150. У первого поставщика осталось 50 единиц груза. Так как потребности первого получателя груза полностью удовлетворены, исключим из рассмотрения первый столбец, заполнив в нем оставшиеся клетки точками. Далее заполняем таблицу по строкам слева направо и сверху вниз. Следующая самая верхняя левая незаполненная клетка – (1,2). Потребителю b2 поставляем 50 единиц груза, оставшихся у первого поставщика. Поскольку от первого поставщика весь груз вывезен, заполняем оставшиеся клетки первой строки точками. Второму получателю, пока что, недопоставлено 80 единиц груза. Следующая незаполненная клетка – (2,2). Потребителю b2 отправляем недостающие 80 единиц груза, при этом его потребности полностью удовлетворены, поэтому оставшиеся клетки во втором столбце заполняем точками. У второго поставщика a2 осталось еще 100 единиц груза. Аналогичным образом заполняем оставшиеся клетки, пока не удовлетворим всех потребителей и не вывезем все запасы груза у поставщиков.
bj ai | ||||
* | * | |||
* | * | |||
* | * |
В результате распределения груза получим первый опорный план, в котором x11 = 150, x12 = 50, x22 = 80, x23 = 100, x33 = 50, x34 = 140. Эти переменные соответствуют заполненным клеткам и являются базисными, остальные переменные, соответствующие клеткам с точками, являются свободными (значения свободных переменных равны нулю). Первый опорный план можно представить в матричном виде
Число заполненных клеток k = 6. Это число должно равняться рангу системы ограничений r = m + n – 1 = 3 + 4 – 1 = 6. Так как k = r = 6, то построенный план является невырожденным. Подсчитаем затраты на перевозку по этому плану
.
3. Построим первое опорное решение транспортной задачи методом минимальной стоимости (минимального тарифа).
bj ai | ||||
* | * | |||
* | * | |||
* | * |
Найдем клетку с минимальным тарифом. Это клетка (1,3) с тарифом
c13 =1. Построение исходного опорного плана начинаем с занесения поставки груза в клетку с наименьшей стоимостью c13. Заполняем клетку x13 = 150. Оставшиеся клетки третьего столбца заполняем точками, так как потребности третьего получателя полностью удовлетворены. У первого поставщика осталось 50 единиц груза. Ищем следующую клетку с минимальным тарифом. Таких клеток две: c14 =2, c32 =2. Заполним сначала клетку (3,2). Поставим в нее x32=min (190, 130)=130. Второй столбец заполняем точками. У третьего поставщика осталось 60 единиц груза. Ищем следующую клетку с наименьшим тарифом – это клетка (1,4). В нее помещаем 50 единиц груза, min(50,140)=50. Первую строку заполняем точками, так как от первого поставщика вывезен весь груз. Четвертому получателю недопоставлено 90 единиц. Аналогичным образом распределяем весь имеющийся груз и получаем первый опорный план перевозок.
Подсчитаем затраты на перевозку по этому плану.
.
Итак, в каждой строке и в каждом столбце таблицы заполнена хотя бы одна клетка, циклов по заполненным клеткам нет, число заполненных клеток m+n-1=6, следовательно, план опорный и невырожденный.
4. Проверка первого опорного плана (решения) на оптимальность. Метод потенциалов
После построения исходного опорного плана приступаем к проверке его на оптимальность методом потенциалов, который заключается в последовательном улучшении опорных планов транспортной задачи на основе информации, полученной с помощью чисел, называемых потенциалы поставщиков и потребителей (, - двойственные переменные, то есть переменные задачи, двойственной к транспортной). Потенциалы находим из условия , где cij - тарифы заполненных клеток. Будем проверять на оптимальность первый опорный план, построенный методом минимального тарифа. В двойственной задаче одна свободная переменная, поэтому возьмем одну любую из двойственных переменных и приравняем ее к нулю. Возьмем, например, (выгоднее брать в качестве нулевой переменной ту, которая соответствует строке или столбцу с наибольшим количеством заполненных клеток).
В таблице в дополнительном столбце справа помещаем потенциалы отправителей , а в строке снизу – потенциалы получателей. Составим систему уравнений для определения потенциалов:
Из этой системы находим
bj ai | |||||
* | * | =2 | |||
* | * | =8 | |||
* | * | =6 | |||
Считаем оценки для свободных клеток:
Запишем получившиеся оценки в левом верхнем углу свободных клеток.
bj ai | |||||
9>0 7 * | 10>0 8 * | =2 | |||
1>0 5 * | 2>0 9 * | =8 | |||
7>0 9 * | -2<0 3 * | =6 | |||
Так как среди оценок имеются отрицательные , то данный план не является оптимальным. Его можно улучшить перераспределением поставок. Для этого выбираем свободную клетку с наименьшим отрицательным значением (наибольшим по абсолютной величине). В данном случае это клетка (3,3).
bj ai | |||||
* | * | 1 150-- | 2 50+ | =2 | |
* | * | =8 | |||
* | *+ | 60-- | =6 | ||
Сроим цикл пересчета, начиная с клетки (3,3), в которую нужно поместить поставку груза (её отмечают знаком «+»), и двигаясь по занятым клеткам (в данном случае это клетки (3,4), (1,4), (1,3)), поочередно отмечая их знаками «-», «+». Если в клетку (3,3) добавили + , то в смежных по циклу клетках необходимо вычесть для сохранения баланса перевозок по третьей строке и третьему столбцу. Звенья цикла должны быть параллельны строкам или столбцам таблицы, причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, а другое – в столбце. Количество вершин в цикле должно быть четно. В результате построения цикла в соответствующих строках и столбцах должно быть парное количество знаков «-», «+».
Определяем величину поставки в клетку (3,3), как минимальную величину из поставок, стоящих в отрицательных клетках, то есть . Перераспределяем по циклу поставки на величину . Значение записываем в незанятую клетку (3,3), отмеченную знаком «+», двигаясь по циклу, прибавляем эту величину к поставкам в клетках со знаком «+», вычитаем в клетках со знаком «-».
В результате получаем новое опорное решение или новый опорный план, в котором клетки с грузом, равным величине , становятся свободными.
bj ai | ||||
* | * | |||
* | * | |||
* | * |
Если освобождается больше одной клетки, то есть число заполненных клеток меньше числа m + n - 1, то такой план называется вырожденными, и для определения потенциалов необходимо ввести недостающее количество нулевых элементов в число основных базисных переменных. Свободные клетки заполняют нулевыми поставками так, чтобы они не образовывали цикл по заполненным клеткам, и чтобы в каждой строке и в каждом столбце находилась хотя бы одна заполненная клетка. Проверим новый опорный план на оптимальность. Пусть =0. Тогда найдем все остальные потенциалы, рассматривая только заполненные клетки и помня, что для них , то есть что сумма потенциалов должна быть равна тарифу, стоящему на пересечении соответствующих потенциалам строки и столбца.
bj ai | |||||
* | * | =0 | |||
* | * | =6 | |||
* | * | =2 | |||
Число заполненных клеток k=m+n-1, следовательно, план невырожденный. Найдем оценки для всех клеток с точками, где стоят свободные переменные. Данный опорный план не является оптимальным, так как не все оценки для свободных клеток , а именно, .
bj ai | |||||
9>0 7 * | 8>0 8 * | =0 | |||
-1<0 5 * | 2>0 9 * | =6 | |||
9>0 9 * | 2>0 6 * | =2 | |||
Возьмем клетку (2,2) за начало цикла пересчета. Цикл будет проходить по клеткам (2,2), (3,2), (3,3), (1,3), (1,4), (2,4) и опять вернется в (2,2).
bj ai | |||||
9>0 7 * | 8>0 8 * | 1 90- | 2 110++ | =0 | |
-1<0 5 *+ | 2>0 9 * | 30- | =6 | ||
9>0 9 * | 130- | 60+ | 2>0 6 * | =2 | |
Ищем количество единиц груза , перераспределяемых по циклу пересчета, как минимум по клеткам, помеченных знаком минус. Получаем новый опорный план
bj ai | ||||
* | * | |||
* | * | |||
* | * |
Проверяем данный опорный план на оптимальность
bj ai | |||||
8>0 7 * | 8>0 8 * | =0 | |||
3>0 9 * | 1>0 8 * | =5 | |||
8>0 9 * | 2>0 6 * | =2 | |||
Полученный опорный план является оптимальным, так как все оценки для свободных клеток . Выписываем оптимальный план: x11 = 0; x12 = 0; x13 = 60; x14 =140; x21 = 150; x22 = 30; x23 = 0; x24 = 0; x31 = 0; x32 = 100; x33 = 90; x34 = 0. Или в матричной форме
Высчитываем минимальные затраты на транспортировку продукции:
Пример 2.
bj ai | ||||
1. Проверим, является ли данная задача замкнутой.
Подсчитаем суммарные запасы груза и суммарные потребности заказчиков ,
.
Поскольку , модель транспортной задачи открытая, и для дальнейшего решения необходимо ввести фиктивного поставщика , так как . Тарифы перевозок для фиктивного поставщика равны нулю.
bj ai | ||||
Далее решаем ТЗ как в Примере 1.
Пример 3.
bj ai | ||||
1. Проверим, является ли данная задача замкнутой.
Подсчитаем суммарные запасы груза и суммарные потребности заказчиков ,
.
Поскольку , модель транспортной задачи открытая, и для дальнейшего решения необходимо ввести фиктивного получателя , так как . Тарифы перевозок для фиктивного получателя равны нулю.
bj ai | |||||
Далее решаем ТЗ как в Примере 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. С трех складов, расположенных в Химках, на Сходне и в Ховрино, необходимо доставить в пять магазинов сахарный песок в соответствии с заявкой каждого магазина. Объёмы запасов песка, имеющегося на складах, объёмы заявок магазинов и тарифы на поставку одной тонны груза со складов в магазины даны в транспортных таблицах по вариантам:
Таблица 2.1.2.а
Магазины Склады | №1 | №2 | №3 | №4 | №5 | Объём запаса |
Химки | ||||||
Сходня | ||||||
Ховри-но | ||||||
Заявки |
Таблица 2.1.2.б
Магазины Склады | №1 | №2 | №3 | №4 | №5 | Объём запаса |
Химки | ||||||
Сходня | ||||||
Ховри-но | ||||||
Заявки |
Таблица 2.1.2.в
Магазины Склады | №1 | №2 | №3 | №4 | №5 | Объём запаса |
Химки | ||||||
Сходня | ||||||
Ховри-но | ||||||
Заявки |
Таблица 2.1.2.г
Магазины Склады | №1 | №2 | №3 | №4 | №5 | Объём запаса |
Химки | ||||||
Сходня | ||||||
Ховри-но | ||||||
Заявки |
Таблица 2.1.2.д
Магазины Склады | №1 | №2 | №3 | №4 | №5 | Объём запаса |
Химки | ||||||
Сходня | ||||||
Ховри-но | ||||||
Заявки |
Таблица 2.1.2.е
Магазины Склады | №1 | №2 | №3 | №4 | №5 | Объём запаса |
Химки | ||||||
Сходня | ||||||
Ховри-но | ||||||
Заявки |
Таблица 2.1.2.ж
Магазины Склады | №1 | №2 | №3 | №4 | №5 | Объём запаса |
Химки | ||||||
Сходня | ||||||
Ховри-но | ||||||
Заявки |
Таблица 2.1.2.з.
Магазины Склады | №1 | №2 | №3 | №4 | №5 | Объём запаса |
Химки | ||||||
Сходня | ||||||
Ховри-но | ||||||
Заявки |
Таблица 2.1.2.и
Магазины Склады | №1 | №2 | №3 | №4 | №5 | Объём запаса |
Химки | ||||||
Сходня | ||||||
Ховри-но | ||||||
Заявки |
Таблица 2.1.2.к
Магазины Склады | №1 | №2 | №3 | №4 | №5 | Объём запаса |
Химки | ||||||
Сходня | ||||||
Ховри-но | ||||||
Заявки |
Выполните задания 1 — 5 задачи 2.1.1.
Задача 2.1.3. Решить транспортную задачу методом потенциалов:
(а)
bj ai | ||||
(б)
bj ai | ||||||
(в)
bj ai | ||||
(г)
bj ai | ||||
(д)
bj ai | ||||
(e)
bj ai | ||||
Задача 2.1.4. Решить открытую транспортную задачу:
(а)
bj ai | ||||
(б)
bj ai | |||||
(в)
bj ai | ||||
(г)
bj ai | |||||
(д)
bj ai | |||