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

Задача 6. На двух складах хранится однородный товар в объёмах ,. Его необходимо доставить в четыре магазина, потребности которыхb₁=30, b₂=30, b₃=20, b₄=20. Удельные транспортные затраты на перевозки: . Для данной задачи составить оптимальный план перевозок.

Определим тип задачи:

- суммарные запасы;

- суммарные потребности.

Т.к. , то задача закрытая.

Если выполняется неравенство - транспортная задача называется открытой транспортной задачей с избыточным спросом. Она может быть приведена к закрытой задаче, если ввести в рассмотрение условного поставщика, величина запасов у которого: , а удельные транспортные затраты по перевозке груза от условного поставщика ко всем потребителям принимаются равными 0: . Компоненты найденного плана поставок означают количество товара, которое недополучит потребитель .При этом матрица планирования транспортной задачи дополняется одной строкой.

Если выполняется неравенство - транспортная задача называется открытой транспортной задачей с избыточным предложением. Она может быть приведена к закрытой задаче, если ввести в рассмотрение условного потребителя, величина запасов у которого:, а удельные транспортные затраты по перевозке груза от условного поставщика ко всем потребителям принимаются равными 0: . Компоненты , найденного плана поставок означают количество товара, которое останется у поставщика после того как потребности всех потребителей будут удовлетворены. При этом матрица планирования транспортной задачи дополняется одним столбцом

Определим тип задачи:

- суммарные запасы;

- суммарные потребности.

Т.к. , то задача закрытая.

Не учитывая удельные транспортные затраты на перевозку груза, начинаем удовлетворять потребности 1-го потребителя B₁ за счёт 1-го поставщика A₁. Потребности потребителя B₁ удовлетворены, а у поставщика A₁ осталось 20 ед. товара, поэтому за счёт A₁ пытаемся удовлетворить потребности B₂ (переходим на клетку вправо). На складе A₁ товара не осталось, а потребности B₂ не удовлетворены, поэтому удовлетворяем его потребности за счёт склада А₂ (перемещаемся на клетку вниз). Потребности В₂ удовлетворены, а на складе А₂ осталось 40 ед. товара, поэтому удовлетворяем за счёт его потребности В₃ (переходим на клетку вправо). Потребности В₃ удовлетворены, а на складе А₂ осталось 20 ед. товара, поэтому удовлетворяем за счёт его потребности В₄ (переходим на клетку вправо). Всего базисных клеток.

Начальный план перевозок, полученный методом северо-западного угла, представлен в таблице 12:

Таблица 12

4 30	2 20	1	3	50
2	3 10	4 20	1 20	50
30	30	20	20	100

Клетка называется занятой, если в ней находится какой-либо объём перевозок. Базисом транспортной задачи называется набор занятых клеток, обладающих следующим свойством: в каждой строке и в каждом столбце должна быть хотя бы одна базисная клетка. Потенциалами строк и столбцов относительно базиса Б называется набор чисел,, удовлетворяющие уравнению:

, если (1)

где - потенциал-ой строки;- потенциал-ого столбца.

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

, если (2)

Если нет то текущий план оптимален.

Проверим на оптимальность начальный план перевозок, представленный в таблице 12.

По базисным клеткам по формуле (1) составим систему уравнений для определения потенциалов строк и столбцов:

Эта система содержит уравнений снеизвестными. Т.к. уравнений на 1 меньше чем неизвестных, система является неопределённой и одному неизвестному (которое чаще всего встречается) присваивают нулевое значение. После этого остальные потенциалы определяются однозначно.

Пусть , тогда

Вычисляем по формуле (2) относительные оценки небазисных клеток:

Т.к. есть , текущий план не оптимален.

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

Таблица 13

4 30	2 20	1 -2	3 1	50
2 -3	3 10	4 20	1 20	50
30	30	20	20	100

Примечание: в правом нижнем угле указаны относительные оценки небазисных клеток.

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

Чтобы найти клетку, исключаемую из базиса, строим цикл пересчёта, который начинается с клетки и в дальнейшем проходит по базисным клеткам. Циклом называется замкнутая ломаная линия, вершины которой расположены в базисных клетках, а звенья – вдоль строк и столбцов, причём в каждой строке и каждом столбце соединяются либо две клетки, либо не одной. Если ломаная цикла пересекается, то точки пересечения вершинами не являются.

В клетках, расположенных в вершинах цикла перераспределяем объёмы перевозок. К клетке вводимой в базис добавляем некоторую величину Θ (промежуточная рента), из следующей клетки Θ вычитаем, далее прибавляем и т.д. Промежуточная рента Θ равна минимальному объёму перевозок в тех клетках, где Θ вычитаем. Базисная клетка, в которой объём перевозок равен Θ выходит из базиса (если таких клеток несколько, то выходит одна, а в других объёмы перевозок равны 0). Следующий план будет дешевле предыдущего на величину

. (4)

Произведем перераспределение перевозок и доведем до оптимального план из таблицы 13.

Выбираем наименьшую отрицательную относительную оценку () и эту клетку включаем в базис ().

В таблице 14 построен цикл пересчёта и перераспределены перевозки:

Таблица 14

4 30 -Θ	2 20 +Θ	1	3	50
2 +Θ	3 10 -Θ	4 20	1 20	50
30	30	20	20	100

Определим промежуточную ренту Θ:

.

Уменьшение транспортных затрат:.

Новый план перевозок записан в таблице 15(изменяем объёмы перевозок только в клетках, находящихся в вершинах цикла):

Таблица 15

4 20	2 30	1	3	50
2 10	3	4 20	1 20	50
30	30	20	20	100

Проверим новый план на оптимальность.

Потенциалы строк и столбцов:

Пусть , тогда

Относительные оценки:

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

Таблица 16

4 20	2 30	1 -5	3 0	50
2 10	3 3	4 20	1 20	50
30	30	20	20	100

Т.к. есть , текущий план не оптимален. Вводим клеткув базис и строим цикл пересчёта.

Новый план перевозок представлен в таблице 17.

Таблица 17

4 20 -Θ	2 30	1 +Θ	3	50
2 10 +Θ	3	4 20 -Θ	1 20	50
30	30	20	20	100

Определим промежуточную ренту:

.

Уменьшение транспортных затрат:.

Новый план перевозок (смотри таблицу 18):

Таблица 18

4	2 30	1 20	3	50
2 30	3	4 0	1 20	50
30	30	20	20	100

Проверим новый план на оптимальность.

Потенциалы строк и столбцов:

Пусть , тогда

Относительные оценки:

План перевозок имеет вид (смотри таблицу 19):

Таблица 19

4 5	2 30	1 20	3 5	50
2 30	3 -2	4 0	1 20	50
30	30	20	20	100

Т.к. есть , текущий план не оптимален. Вводим клеткув базис и строим цикл пересчёта (смотри таблицу20).

Таблица 20

4	2 30 -Θ	1 20 +Θ	3	50
2 30	3 +Θ	4 0 -Θ	1 20	50
30	30	20	20	100

Определим промежуточную ренту:

.

Уменьшение транспортных затрат: .

Новый план перевозок (смотри таблицу 21):

Таблица 21

4	2 30	1 20	3	50
2 30	3 0	4	1 20	50
30	30	20	20	100

Проверим новый план на оптимальность.

Потенциалы строк и столбцов:

Пусть , тогда

Относительные оценки:

Т.к. нет , текущий план оптимален.

Стоимость перевозок по этому плану:

.

Минимальная стоимость перевозок в размере 160 руб. достигается, если перевезти с 1-го склада во 2-ой магазин 30 ед. товара и в 3-ий магазин 20 ед., а со 2-го склада – 30 ед. в 1-ый магазин и 20 ед. в 4-ый магазин.