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

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

Постановка задачи:

Однородный груз сосредоточен у m поставщиков А1, А2…..Am в объемах а1, а2…аm.

Данный груз необходимо доставлять n потребителям В1, В2…Вn, которые формируют заявки на груз в объемах в1, в2…вn.

Известны затраты (тарифы) на перевозку единицы груза от i-го поставщика J-му потребителю.

Сij( i=1,m , j=1,n)- затраты на перевозку.

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

Занесем все условия задачи в специальную транспортную таблицу

Математическая модель транспортной задачи:

Пусть Х= х11 х12… х1n

х21 х22… х2n

………………………

xm1 xm2…xmn

- это план перевозки грузов

от каждого поставщика к каждому потребителю хij≥0 (i=1,m; j=1,n)

Суммарные затраты на перевозку грузов будут составлять ∑∑сij xij.

Поскольку эти затраты нужно минимизировать, то имеем целевую функцию

F(X)= ∑∑cij xij->min

Груз, выводимый от одного поставщика, определяется суммой всех переменных по строке

∑ xij( j=1,n).

И так как весь груз должен быть выведен, то эта сумма должна равняться запасам поставщика

∑xij=ai( j=1,n) i=1,m.

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

∑xij= bj (i=1,n)

J=1,n

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

F(x)= ∑∑cij xij->min при ограничениях:

∑хij=ai(j=1,n)

∑xij=bj(i=1,m)

xij≥0

32)Открытая и закрытая модели транспортной задачи. Приведение открытой модели к закрытой.

Модель ТЗ называется закрытой(задача с правильным балансом), если суммарные запасы поставщиков совпадают с суммарным спросом потребителей.

Если данное условие не выполняется, т.е. ∑ai≠∑bj (i=1,m, j=1,n) , то модель открытая, а задача с неправильным балансом.

Открытую модель необходимо привести к закрытому виду, при этом возможно 2 случая:

1) ∑ai>∑bj (i=1,m. j=1,n) запасов больше, чем заявок. В этом случае вводят фиктивного потребителя Вn+1, который формирует спрос на груз в объеме bn+1=∑ai-∑bj( i=1,m j=1,n).

Тарифы данного потребителя считаем равными нулю.

2) ∑ai< ∑ bj( i=1, m j=1,n) спрос превышает имеющиеся запасы, в этом случае вводят фиктивного поставщика Am+1,запасы которого составляют am+1= ∑bj- ∑bi( j=1,n i=1,m).

Тарифы для данного поставщика равны нулю.

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

Построение начального опорного решения ТЗ методом наименьших тарифов.

1. Приведём задачу к закрытому виду. Заполнение начинаем с клетки с наименьшим тарифом.

2. Занесём в эту клетку максимально возможный груз, который можно направить от 1-го поставщика 1-му потребителю. X=min{a1, b1}

3. Определяем остатки запасов и заявок. Вычёркиваем из рассмотрения поставщика или потребителя с нулевыми остатками.

ЗАМЕЧАНИЕ. На каждом шаге алгоритма вычёркивать можно только одного участника. Одновременно строку и столбец вычёркивать нельзя. На свой выбор вычёркиваем. Если вычеркнут поставщик, то у потребителя ставиться ставим базисный ноль. Он участвует в дальнейшем рассмотрении груза.

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

ЗАМЕЧАНИЕ. Фиктивные поставщики и потребители с тарифами=0 рассматриваются в последнюю очередь.

5. Выписываем матрицу начального решения Х1 и находим значение целевой функции.

Построение начального опорного решения ТЗ методом северо-западного угла.

1. Приведём задачу к закрытому виду. Заполнение начинаем с левого верхнего угла Трансп. Табл.

2. Занесём в эту клетку максимально возможный груз, который можно направить от 1-го поставщика 1-му потребителю. X=min{a1, b1}

3. Определяем остатки запасов и заявок. Вычёркиваем из рассмотрения поставщика или потребителя с нулевыми остатками.

ЗАМЕЧАНИЕ. На каждом шаге алгоритма вычёркивать можно только одного участника. Одновременно строку и столбец вычёркивать нельзя. На свой выбор вычёркиваем. Если вычеркнут поставщик, то у потребителя ставиться ставим базисный ноль. Он участвует в дальнейшем рассмотрении груза.

4. Среди оставшихся не вычеркнутых клеток вновь находим левую верхнюю. И снова распределяем груз, но уже туда. Алгоритм повторяем до тех пор пока весь груз не распределим и свободных клеток не останется.

5. Выписываем матрицу начального решения Х1 и находим значение целевой функции.