Определение опорного плана транспортной задачи

Математическая дисциплина, занимающаяся изучением экстремальных (максимальных или минимальных) задач управления, планирования и разработкой методов их решения, получила название математического программирования.
Задачи управления и планирования возможно представить как выбор параметров и системы функций, например:
Требуется найти максимум функции f(xi,x2,...,xn)
при условиях

Требуется найти максимум функции f(xi,x2,...,xn)
при условиях
Здесь f, gi — функции,
x1, x2, · · · , xn — параметры управления.
Выражение f(xi,x2,...,xn) называется функцией цели.
Условия представляют собой ограничения поставленной задачи.

транспортная задача
Цель - в минимизации полной стоимости перевозок известного количества товаров со складов к потребителю.
постановка транспортной задачи :
определение оптимального плана перевозок однородного груза
из m пунктов отправления A1, A2, . . . , Am
в n пунктов назначения B1, B2, . . . , Bn.
в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки.

транспортная задача
определение оптимального плана перевозок груза
из m пунктов отправления A1, A2, . . . , Am
в n пунктов назначения B1, B2, . . . , Bn.
определение минимального значения целевой функции стоимости перевозок
Всякое неотрицательное решение систем линейных уравнений,
называется планом транспортной задачи.
План, при котором целевая функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

транспортная задача
определение оптимального плана перевозок груза
из m пунктов отправления A1, A2, . . . , Am
в n пунктов назначения B1, B2, . . . , Bn.

транспортная задача
Сij тарифы перевозок
Xij количество груза

Определение оптимального плана транспортной задачи начинают с нахождения какого-нибудь ее опорного плана.
опорный план находят последовательно за n+m-1 шагов, на каждом из которых в таблице условий задачи заполняют одну клетку, которую называют занятой.
заполнение одной из клеток обеспечивает полностью либо удовлетворение потребности в грузе одного из пунктов назначения, либо вывоз груза из одного из пунктов отправления.
Опорный план является исходным условием для проверки последнего на оптимальность и нахождения оптимального плана.

Метод северо-западного угла
на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения.
Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного X11 (“северо-западный угол”)
заканчивается для неизвестного Xmn, т. е. идет как бы по диагонали таблицы с севера на запад.

Метод северо-западного угла
Задача 1. На три базы A1, A2, A3 поступил однородный груз в количествах, соответственно равных 140, 180 и 160 ед. Это груз требуется перевезти в пять пунктов назначения B1, B2, B3, B4, B5 соответственно в количествах 60, 70, 120, 130 и 100 ед. Тарифы перевозок единицы груза с каждого из пунктов отправления в соответствующие пункты назначения указаны в таблице:

Метод северо-западного угла
Решение.
пунктов отправления m=3, а число пунктов назначения n=5 5+3-1=7
Заполнение таблицы начнем с неизвестного x11, т. е. попытаемся удовлетворить потребности первого пункта назначения за счет запасов первого пункта отправления. Так как запасы пункта A1 больше, чем потребности пункта B1, то полагаем x11=60, записываем это значение в соответствующей клетке табл и временно исключаем из рассмотрения столбец B1, считая при этом запасы пункта A1 равными 80.

Метод северо-западного угла
Решение. первые из оставшихся пунктов отправления A1 и назначения B2. Запасы пункта A1 больше потребностей пункта B2. Положим X12=70, запишем это значение в соответствующей клетке табл и временно исключим из рассмотрения столбец B2. В пункте A1 запасы считаем равными 10 ед.

Метод северо-западного угла
Решение. Снова рассмотрим первые из оставшихся пунктов отправления A1 и назначения B3. Потребности пункта B3 больше оставшихся запасов пункта A1. Положим X13=10 и исключим из рассмотрения строку A1. Значение X13=10 запишем в соответствующую клетку табл и считаем потребности пункта B3 равными 110 ед.

Метод северо-западного угла
Решение. Теперь перейдем к заполнению клетки для неизвестного x23 и т. д.
Через шесть шагов остается один пункт отправления A3 с запасом груза 100 ед. и один пункт назначения B5 с потребностью 100 ед. Соответственно имеется одна свободная клетка, которую и заполняем, полагая x35=100. В результате получаем опорный план

Метод северо-западного угла
Решение. В результате получаем опорный план

Метод северо-западного угла
общая стоимость перевозок всего груза
S=2*60+3*70+4*10+1*110+4*70+7*60+2*100=1380

Метод минимального элемента
Очевидно, выбор пунктов назначения и отправления целесообразно производить, ориентируясь на тарифы перевозок, а именно:
на каждом шаге следует выбирать какую-нибудь клетку, отвечающую минимальному тарифу (если таких клеток несколько, то следует выбирать любую из них), и рассмотреть пункты назначения и отправления, соответствующие выбранной клетке.
Сущность метода минимального элемента и состоит в выборе клетки с минимальным тарифом.
Этот метод, как правило, позволяет найти опорный план транспортной задачи, при котором общая стоимость перевозок груза меньше, чем общая стоимость перевозок при плане, найденном для данной задачи с помощью метода северо-западного угла.
Поэтому наиболее целесообразно опорный план транспортной задачи находить методом минимального элемента.

Метод минимального элемента
Задача 2

Метод минимального элемента
Решение. Минимальный тариф равный 1, находится в клетке для переменной x13. Положим x13=160, запишем это значение в соответствующую клетку таблицы и временно исключим из рассмотрения строку A1. Потребности пункта назначения B3 читаем равными 30.

Метод минимального элемента
Решение. В оставшейся части таблицы с двумя строками A2 и A3 и четырьмя столбцами B1, B2, B3 и B4 клетка с наименьшим тарифом находится на пересечении строки A3 и столбца B2, где С32=2. Положим X32=50 и внесем это значение в соответствующую клетку.

Метод минимального элемента
Решение. Временно исключим из рассмотрения столбец B2 и будем считать запасы пункта A3 равными 120.
После этого рассмотрим оставшуюся часть таблицы с двумя строками A2 и A3 и тремя столбцами B1, B3 и B4. В ней минимальный тариф находится в клетке на пересечении строки A3 и столбца B3 и равен 3. Заполним описанным выше способом эту клетку
и аналогично заполним клетки, находящиеся на пересечении строки A2 и столбца B1, строки A3 и столбца B4, строки A2 и столбца B4. В результате получим опорный план.
При данном плане перевозок общая стоимость перевозок составляет.
S=1*160+4*120+8*20+2*50+3*30+6*90=1530

Метод аппроксимации Фогеля
на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами.
разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи.
Среди разностей выбирают максимальную.
В строке (или столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.
Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными тарифами, находящимися в данном столбце (строке).

Метод аппроксимации Фогеля
Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке. Так в строке A2 минимальный тариф равен 4, а следующий за ним равен 5, разность между ними 5-4=1. Точно так же разность между минимальными элементами в столбце B4 равна 6-2=4.

Метод аппроксимации Фогеля

Метод аппроксимации Фогеля

Метод аппроксимации Фогеля
Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу B4. В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки A1 и столбца B4. Таким образом эту клетку следует заполнить.. Заполнив ее, тем самым мы удовлетворим потребности пункта B4. Поэтому исключим из рассмотрения столбец B4 и будем считать запасы пункта A1 равными 160-110=50

Метод аппроксимации Фогеля