Транспортная задача линейного программирования

Транспортная задача заключается в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А₁, _А2,..., А_m в n пунктов потребления В₁,В₂,..., В_n.

Рассмотрим транспортную задачу, где в качестве критерия оптимальности является стоимость перевозок всего груза, которая должна быть минимальной.

Введем обозначения:

а_i - запасы груза в i-ом пункте отправления

b_j - величина заказа на этот груз в j-ом пункте назначения

с_ij - стоимость перевозки единицы груза из A i-ro пункта отправления и Bj-ый пункт потребления (тариф перевозок);

x_ij - количество груза, доставленного из i пункта в j пункт,

Определить план перевозок груза из пунктов отправления в пункты назначения так, чтобы: вывести все грузы от поставщиков; удовлетворить заявки каждого потребителя; обеспечить минимальные транспортные расходы на перевозку груза.

Все исходные данные транспортной задачи можно написать в виде транспортной таблицы 4.

Таблица 4.

пункты отправления	пункты назначения	запасы аi
B1	B2	…	Bj	…	Bn
A1	С11 X11	С12 X12	…	C1j X1j	…	C1n X1n	A1
A2	C21 X21	C22 X22	…	C1j X1j	…	C1n X1n	A2
…	…	…	…	…	…	…	…
Aj	Ci1 Xi1	Ci2 Xi2	…	Cij Xij	…	Cin Xin	Ai
…	…	…	…	…	…	…	…
Am	Cm1 Xm1	Cm2 Xm2	…	Cmj xmj	…	Cmn xmn	Am
заявки bj	B1	B2	…	bj	…	bn

где - суммарный запас груза у поставщиков;

- суммарная величина заявок потребителей.

Математическая постановка транспортной задачи заключается в определении матрицы

, которая удовлетворяет следующим условиям:

и обеспечивает минимальное значение целевой функции

.

а) Всякое неотрицательное решение системы линейных уравнений, определяемое матрицей , называется допустимым планом транспортной задачи.

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

в) Допустимый план транспортной задачи, имеющий не более отличных от нуля величин , называется опорным.

г) Если в опорном плане число отличных от нуля компонент равно в точности , то план является невырожденным, если меньше, то план называется вырожденным.

д) План , при котором функция 4 принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

е) Для решения транспортной задачи необходимо и достаточно, чтобы суммарные запасы груза в пунктах отправления были равны сумме заявок пунктов назначения:

.

ж) Модель транспортной задачи, удовлетворяющая этому условию, называется закрытой. Если же указанное условие не выполняется, то модель называется открытой.

В случае превышения запаса над заявками: вводится фиктивный пункт назначения с потребностью и соответствующие тарифы считаются равными нулю: .

При вводится фиктивный пункт отправления груза с запасом груза и тарифы принимаются равными нулю: .

Рассмотрим один из методов построения первого опорного плана – метод наименьших тарифов.

з) Наилучшим элементом матрицы тарифов называется наименьший тариф, если задача поставлена на минимум, наибольший тариф – если задача поставлена на максимум целевой функции.

Алгоритм построения первого опорного плана методом наименьшей стоимости включает следующие этапы:

1. Среди тарифов находится наименьший.

2. Клетку с выбранным тарифом заполняем максимально возможным объемом груза с учетом ограничений по строке и столбцу, при этом либо весь груз вывозится от соответствующего поставщика, либо полностью удовлетворяется заявка потребителя. Строка или столбец таблицы вычеркивается и в дальнейшем распределении не участвует.

3. Из оставшихся тарифов вновь находим наилучший, и процесс продолжается до тех пор, пока не будет распределен весь груз.

Если модель транспортной задачи открытая и введены фиктивный поставщик или потребитель, то распределение осуществляется сначала для действительных поставщиков и потребителей, и в последнюю очередь нераспределенный груз направляется от фиктивного поставщика или к фиктивному потребителю.

Дальнейшее улучшения первого опорного плана и получение оптимального алана производим методом потенциалов.

и) План транспортной задачи будет являться оптимальным, если существует система чисел , называемых потенциалами, удовлетворяющая условиям:

для занятых клеток, где

для свободных клеток, где

при решении задачи на минимум, а при решении задачи на максимум:

для занятых клеток, где

для свободных клеток, где

Потенциалы и являются переменными двойственной транспортной задачи и обозначают оценку единицы груза в пунктах отправления и назначения соответственно.

Введем обозначение оценки свободной клетки таблицы:

Если среди оценок нет отрицательной (задача поставлена на минимум), то опорный план является оптимальным и все свободные клетки потенциальны.

Алгоритм метода потенциалов включает следующие этапы:

1. Построение первого опорного плана.

2. Проверка вырожденности плана.

Потенциалы и могут быть рассчитаны только для невырожденного плана. Если число занятых клеток в опорном плане меньше, чем , то вносим нуль в одну из свободных клеток таблицы так, чтобы общее число занятых клеток стало равным . Нуль вводят в клетку с наилучшим тарифом одного из одновременно вычеркиваемых рядов таблицы. При этом фиктивно занятая нулем клетка не должна образовывать замкнутого контура с другими клетками таблицы.

3. Определение значения функции цели путем суммирования произведений тарифов (удельных затрат) на объем перевозимого груза по всем занятым клеткам таблицы.