В задаче об оптимальном планировании перевозок:
Ai – пункты отправления;
ai – запасы в пунктах отправления;
Bj – пункты назначения;
bj – заявки пунктов назначения.
Таблица 9 – Транспортная таблица
B1 B2 B3 B4 B5 ai
A1 6 6 8 9 8 50
A2 3 6 8 8 5 100
A3 4 6 7 8 7 150
A4 5 5 5 7 8 150
A5 5 7 7 8 6 200
bj 80 100 140 160 170
Определить начальный план транспортной задачи методом северо-западного угла;
Определить начальный план транспортной задачи методом минимального элемента;
Найти оптимальный план транспортной задачи методом потенциалов и стоимость перевозки по этому плану.
Решение
Построим математическую модель задачи.
Пусть , , - количество единиц груза, перевозимого от i-го отправления j-му пункту назанчения. Тогда общие затраты, связанные с реализацией перевозок, представятся целевой функцией:
или
Требуется спланировать перевозки так, чтобы весь товар из пунктов отправления был вывезен. Но поскольку суммарный груз, вывезенный, не может превышать запасы в пунктах отправления, то переменные должны удовлетворять следующим ограничениям по предложениям:
Аналогично потребности каждого пункта назначения должны быть полностью удовлетворены, поэтому должны выполняться ограничения-неравенства по потребностям:
Объем перевозок товара не может быть отрицательным, поэтому справедливы условия неотрицательности на переменные , ,
Занесём исходные данные задачи в таблицу 10:
в столбец - предложение груза от i-го склада, ;
в строку - потребности в грузе j-го магазина, ;
в нижний правый угол каждой клетки, расположенной в i-строке и jм столбце, стоимости перевозок;
Таблица 10 – Транспортная таблица
ai \ bj 80 100 140 160 170
50 6 6 8 9 8
100 3 6 8 8 5
150 4 6 7 8 7
150 5 5 5 7 8
200 5 7 7 8 6
Опорный план, полученный методом северо-западного угла (табл. 11).
По центру каждой клетки проставляем объёмы перевозок , ,
. По указанному правилу загружаем первую клетку из условия:
.
Таблица 11 – Опорный план, найденный методом северо-западного угла
ai \ bj 0 30 80 0 30 100 0 20 140 0 30 160 0 170
0 50 50
6
6
8
9
8
0 70 100 30
3 70
6
8
8
5
0 120 150
4 30
6 120
7
8
7
0 130 150
5
5 20
5 130
7
8
0 170 200
5
7
7 30
8 170
6
Так как , то из рассмотрения исключим строку с номером 1 и .
Из оставшихся клеток находим самую верхнюю и самую левую, . Так как , то из рассмотрения исключим столбец с номером 1 и и т.д.
Проверяем условие для базисных клеток , что соответствует числу занятых клеток и, следовательно, базисный план построен верно.
Опорный план, полученный методом северо-западного угла (табл. 12).
По центру каждой клетки проставляем объёмы перевозок , , . Находим ,
По этому правилу загружаем первую клетку из условия:
.
Таблица 11 – Опорный план, найденный методом минимального элемента
ai \ bj 0 80 0 100 0 90 140 0 50 100 160 0 150 170
0 50
6
6
8 50
9
8
0 20 100 80
3
6
8
8 20
5
0 60 150 4
6 90
7 60
8
7
0 50 150 5 100
5 50
5
7
8
0 50 200 5
7
7 50
8 150
6
Так как , то из рассмотрения исключим столбец с номером 1 и .
Из оставшихся клеток находим ,. Так как , то из рассмотрения исключим строку с номером 2 и и т.д.
Проверяем условие для базисных клеток , что соответствует числу занятых клеток и, следовательно, базисный план построен верно.
Оптимальный план транспортной задачи, найденный методом потенциалов.
Шаг 1
Задать вопрос
на новый заказ в Автор24.
