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

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

Например, пусть имеет место опорный план следующего вида.

Пункт назна­чения Пункт отправления	B 1	B 2	B 3	B 4	Запас
A 1
A 2
A 3
Потребность

Сумма числа строк и столбцов транспортной таблицы без единицы равна по-прежнему 6. В то время как загружено только 4 ячейки. Таким образом, опорный план является вырожденным. Вычислить потенциалы строк и столбцов транспортной таблицы не представляется возможным. Поэтому в две произвольные незагруженные ячейки (например, A ₁ B ₃ и A ₃ B ₃) следует записать нулевые поставки. В результате получится невырожденный опорный план следующего вида.

Пункт назна­чения Пункт отправления	B 1	B 2	B 3	B 4	Запас
A 1
A 2
A 3
Потребность

Далее задачу следует решать обычным способом.

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

1) Изменить знак в матрице затрат c_ij на противоположный и решать задачу аналогично описанному выше. Отрицательное итоговое значение затрат (максимальные затраты) считать положительным.

2) Выбирать в качестве вершины максимальной неоптимальности вершину, для которой D _ij принимает наименьшее отрицательное значение. План будет оптимальным, если все D _ij ³ 0.

Рассмотрим подробнее второй способ решения.

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

Опорный план нашей транспортной задачи будет иметь вид.

Пункт назна­чения Пункт отправления	B 1	B 2	B 3	B 4	Запас
A 1
A 2
A 3
Потребность

Данный опорный план является вырожденным, поскольку содержит 5 загруженных ячеек вместо необходимых 6. Поэтому в произвольную незагруженную ячейку (например, A ₁ B ₂) запишем нулевую поставку.

Пункт назна­чения Пункт отправления	B 1	B 2	B 3	B 4	Запас	ui
A 1		9 0 +	30 –
A 2
A 3		120 –	+
Потребность
vj

Вычислим потенциалы по загруженным ячейкам транспортной таблицы.

u ₁ = 0;

A ₁ B ₃: u ₁ + v ₃ = 4; 0 + v ₃ = 4; v ₃ = 4;

A ₂ B ₃: u ₂ + v ₃ = 4; u ₂ + 4 = 4; u ₂ = 0;

A ₁ B ₂: u ₁ + v ₂ = 9; 0 + v ₂ = 9; v ₂ = 9;

A ₂ B ₁: u ₂ + v ₁ = 7; 0 + v ₁ = 7; v ₁ = 7;

A ₃ B ₂: u ₃ + v ₂ = 9; u ₃ + 9 = 9; u ₃ = 0;

A ₃ B ₄: u ₃ + v ₄ = 10; 0 + v ₄ = 10; v ₄ = 10.

Проверим опорный план на оптимальность. Для этого по незагруженным ячейкам вычислим D _ij = u_i + v_j – c_ij.

A ₁ B ₁: D₁₁ = u ₁ + v ₁ – c ₁₁ = 0 + 7 – 6 = 1;

A ₁ B ₄: D₁₄ = u ₁ + v ₄ – c ₁₄ = 0 + 10 – 5 = 5;

A ₂ B ₂: D₂₂ = u ₂ + v ₂ – c ₂₂ = 0 + 9 – 5 = 4;

A ₂ B ₄: D₂₄ = u ₂ + v ₄ – c ₂₄ = 0 + 10 – 8 = 2;

A ₃ B ₁: D₃₁ = u ₃ + v ₁ – c ₃₁ = 0 + 7 – 8 = –1 < 0;

A ₃ B ₃: D₃₃ = u ₃ + v ₃ – c ₃₃ = 0 + 4 – 6 = –2 < 0.

Опорный план не является оптимальным, поскольку среди незагруженных ячеек имеются такие, для которых D _ij < 0 (D₃₁ = –1 < 0, D₃₃ = –2 < 0). Ячейка A ₃ B ₃ будет вершиной максимальной неоптимальности (в качестве вершины максимальной неоптимальности выбирают ячейку с наименьшим отрицательным значением D _ij).

Строим контур перераспределения поставок.

Среди разгружаемых ячеек находим минимальную величину поставок:

min {30; 120} = 30.

Для всех разгружаемых ячеек уменьшаем объем перевозок на эту величину, а для загружаемых – увеличиваем.

Получаем транспортную таблицу вида:

Пункт назна­чения Пункт отправления	B 1	B 2	B 3	B 4	Запас	ui
A 1
A 2						–2
A 3
Потребность
vj

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

Вычислим потенциалы по загруженным ячейкам транспортной таблицы.

u ₁ = 0;

A ₁ B ₂: u ₁ + v ₂ = 9; 0 + v ₂ = 9; v ₂ = 9;

A ₃ B ₂: u ₃ + v ₂ = 9; u ₃ + 9 = 9; u ₃ = 0;

A ₃ B ₃: u ₃ + v ₃ = 6; 0 + v ₃ = 6; v ₃ = 6;

A ₃ B ₄: u ₃ + v ₄ = 10; 0 + v ₄ = 10; v ₄ = 10;

A ₂ B ₃: u ₂ + v ₃ = 4; u ₂ + 6 = 4; u ₂ = –2;

A ₂ B ₁: u ₂ + v ₁ = 7; –2 + v ₁ = 7; v ₁ = 9.

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

A ₁ B ₁: D₁₁ = u ₁ + v ₁ – c ₁₁ = 0 + 9 – 6 = 3;

A ₁ B ₃: D₁₃ = u ₁ + v ₃ – c ₁₃ = 0 + 6 – 4 = 2;

A ₁ B ₄: D₁₄ = u ₁ + v ₄ – c ₁₄ = 0 + 10 – 5 = 5;

A ₂ B ₂: D₂₂ = u ₂ + v ₂ – c ₂₂ = –2 + 9 – 5 = 2;

A ₂ B ₄: D₂₄ = u ₂ + v ₄ – c ₂₄ = –2 + 10 – 8 = 0;

A ₃ B ₁: D₃₁ = u ₃ + v ₁ – c ₃₁ = 0 + 9 – 8 = 1.

Опорный план является оптимальным, поскольку среди незагруженных ячеек нет таких, для которых D _ij < 0.

Определим величину максимальных затрат при оптимальном плане перевозок:

f = 30 ´ 9 + 70 ´ 7 + 120 ´ 4 + 90 ´ 9 + 30 ´ 6 + 130 ´ 10 =

= 270 + 490 + 480 + 810 + 180 + 1300 = 3530 ден. ед.

6. Найти решение исходной транспортной задачи с учетом дополнительных условий.

Запрет перевозок по маршруту А ₁ В ₄ достигается путем искусственного завышения стоимости перевозок в указанной ячейке (например, заданием величины 50 ден. ед.).

Для выполнения условий типа «не менее» (т.е. учета обязательных поставок по заданным маршрутам) следует уменьшить объемы спроса и предложения в заданных пунктах отправления и назначения на указанную величину (т.е. избавиться от обязательных поставок). После нахождения оптимального решения ответ корректируется с учетом обязательных поставок.

Ограничение типа «не более» реализуется путем разбиения столбца транспортной таблицы на два столбца. Спрос одного из них полагают равным максимально возможному объему поставок, а другого – оставшемуся спросу. Тарифы в обоих столбцах одинаковы и равны исходным. Исключение составляет лишь одна ячейка из второго столбца (по заданному маршруту), которая должна быть блокирована.

С учетом дополнительных условий табличная модель нашей транспортной задачи примет вид:

Пункт назна­чения Пункт отправления	B 1(1)	B 1(2)	B 2	B 3	B 4	Запас
A 1
A 2
A 3
Потребность

Построим начальный опорный план методом минимального элемента.

Пункт назна­чения Пункт отправления	B 1(1)	B 1(2)	B 2	B 3	B 4	Запас	ui
A 1	30 –	0 +
A 2		20 –			+
A 3	20 +				130 –
Потребность
vj

Количество загруженных ячеек равно 6, что на две единицы меньше суммы количества строк и столбцов транспортной таблицы. Следовательно, опорный план является вырожденным. Запишем нулевое значение в ячейку A ₁ B ₁⁽²⁾ и будем считать ее загруженной.

Вычислим потенциалы по загруженным ячейкам транспортной таблицы.

u ₁ = 0;

A ₁ B ₁⁽¹⁾: u ₁ + v ₁⁽¹⁾ = 6; 0 + v ₁⁽¹⁾ = 6; v ₁⁽¹⁾ = 6;

A ₁ B ₁⁽²⁾: u ₁ + v ₁⁽²⁾ = 6; 0 + v ₁⁽²⁾ = 6; v ₁⁽²⁾ = 6;

A ₂ B ₁⁽²⁾: u ₂ + v ₁⁽²⁾ = 7; u ₂ + 6 = 7; v ₁⁽²⁾ = 1;

A ₂ B ₂: u ₂ + v ₂ = 5; 1 + v ₂ = 5; v ₂ = 4;

A ₂ B ₃: u ₂ + v ₃ = 4; 1 + v ₃ = 4; v ₃ = 3;

A ₃ B ₁⁽¹⁾: u ₃ + v ₁⁽¹⁾ = 8; u ₃ + 6 = 8; u ₃ = 2;

A ₃ B ₄: u ₃ + v ₄ = 10; 2 + v ₄ = 10; v ₄ = 8.

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

A ₁ B ₂: D₁₂ = u ₁ + v ₂ – c ₁₂ = 0 + 4 – 9 = –5;

A ₁ B ₃: D₁₃ = u ₁ + v ₃ – c ₁₃ = 0 + 3 – 4 = –1;

A ₁ B ₄: D₁₄ = u ₁ + v ₄ – c ₁₄ = 0 + 8 – 50 = –42;

A ₂ B ₁⁽¹⁾: D₂₁⁽¹⁾ = u ₂ + v ₁⁽¹⁾ – c ₂₁⁽¹⁾ = 1 + 6 – 7 = 0;

A ₂ B ₄: D₂₄ = u ₂ + v ₄ – c ₂₄ = 1 + 8 – 8 = 1 > 0;

A ₃ B ₁⁽²⁾: D₃₁⁽²⁾ = u ₃ + v ₁⁽²⁾ – c ₃₁⁽²⁾ = 2 + 6 – 50 = –42;

A ₃ B ₂: D₃₂ = u ₃ + v ₂ – c ₃₂ = 2 + 4 – 9 = –3;

A ₃ B ₃: D₃₃ = u ₃ + v ₃ – c ₃₃ = 2 + 3 – 6 = –1.

Опорный план не является оптимальным, поскольку среди незагруженных ячеек имеются такие, для которых D _ij > 0 (D₂₄ = 1 > 0). Ячейка A ₂ B ₄ будет вершиной максимальной неоптимальности (в качестве вершины максимальной неоптимальности выбирают ячейку с набольшим положительным значением D _ij).

Строим контур перераспределения поставок.

Среди разгружаемых ячеек находим минимальную величину поставок:

min {30; 20; 130} = 20.

Для всех разгружаемых ячеек уменьшаем объем перевозок на эту величину, а для загружаемых – увеличиваем.

Получаем транспортную таблицу вида:

Пункт назна­чения Пункт отправления	B 1(1)	B 1(2)	B 2	B 3	B 4	Запас	ui
A 1
A 2
A 3
Потребность
vj

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

Вычислим потенциалы по загруженным ячейкам транспортной таблицы.

u ₁ = 0;

A ₁ B ₁⁽¹⁾: u ₁ + v ₁⁽¹⁾ = 6; 0 + v ₁⁽¹⁾ = 6; v ₁⁽¹⁾ = 6;

A ₁ B ₁⁽²⁾: u ₁ + v ₁⁽²⁾ = 6; 0 + v ₁⁽²⁾ = 6; v ₁⁽²⁾ = 6;

A ₃ B ₁⁽¹⁾: u ₃ + v ₁⁽¹⁾ = 8; u ₃ + 6 = 8; u ₃ = 2;

A ₃ B ₄: u ₃ + v ₄ = 10; 2 + v ₄ = 10; v ₄ = 8;

A ₂ B ₄: u ₂ + v ₄ = 8; u ₂ + 8 = 8; v ₄ = 0;

A ₂ B ₂: u ₂ + v ₂ = 5; 0 + v ₂ = 5; v ₂ = 5;

A ₂ B ₃: u ₂ + v ₃ = 4; 0 + v ₃ = 4; v ₃ = 4.

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

A ₁ B ₂: D₁₂ = u ₁ + v ₂ – c ₁₂ = 0 + 5 – 9 = –4;

A ₁ B ₃: D₁₃ = u ₁ + v ₃ – c ₁₃ = 0 + 4 – 4 = 0;

A ₁ B ₄: D₁₄ = u ₁ + v ₄ – c ₁₄ = 0 + 8 – 50 = –42;

A ₂ B ₁⁽¹⁾: D₂₁⁽¹⁾ = u ₂ + v ₁⁽¹⁾ – c ₂₁⁽¹⁾ = 0 + 6 – 7 = –1;

A ₂ B ₁⁽²⁾: D₂₁⁽²⁾ = u ₂ + v ₁⁽²⁾ – c ₂₁⁽²⁾ = 0 + 6 – 7 = –1;

A ₃ B ₁⁽²⁾: D₃₁⁽²⁾ = u ₃ + v ₁⁽²⁾ – c ₃₁⁽²⁾ = 2 + 6 – 50 = –42;

A ₃ B ₂: D₃₂ = u ₃ + v ₂ – c ₃₂ = 2 + 5 – 9 = –2;

A ₃ B ₃: D₃₃ = u ₃ + v ₃ – c ₃₃ = 2 + 4 – 6 = 0.

Опорный план является оптимальным, поскольку среди незагруженных ячеек нет таких, для которых D _ij > 0.

Учтем обязательные поставки, которые были исключены ранее, вернем прежние значения тарифов и объединим столбцы B ₁⁽¹⁾ и B ₁⁽²⁾. В результате получим таблицу следующего вида.

Пункт назна­чения Пункт отправления	B 1	B 2	B 3	B 4	Запас
A 1
A 2
A 3
Потребность

Минимальные суммарные затраты на перевозку с учетом дополнительных условий равны

f = 30 ´ 6 + 20 ´ 5 + 150 ´ 4 + 20 ´ 8 + 40 ´ 8 + 100 ´ 9 + 110 ´ 10 =

= 180 + 100 + 600 + 160 + 320 + 900 + 1100 = 3360 ден. ед.

Таким образом, в силу учета дополнительных условий суммарные затраты по изготовлению и доставке продукции потребителям увеличились на 3360 – 3070 = 290 ден. ед.

7. Построим табличную модель транспортной задачи без учета затрат на производство продукции. В качестве тарифов используем матрицу c_ij – затраты времени на доставку груза из пункта отправления А_i в пункт назначения В_j.

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

Пункт назна­чения Пункт отправления	B 1	B 2	B 3	B 4	Запас
A 1
A 2
A 3
Потребность

Среди загруженных ячеек выбираем ячейку с наибольшим значением времени c_ij. Это ячейка A ₃ B ₄, для которой c ₃₄ = 7. Эта величина определяет время, в течение которого осуществляется план перевозок. Далее следует исключить из рассмотрения все свободные ячейки, для которых c_ij > c ₃₄. Таких ячеек в данном плане нет.

Строим цикл (контур) разгрузки, основными требованиями для которого являются: 1) наличие груза в разгружаемых ячейках; 2) ячейка A ₃ B ₄ является разгружаемой.

Пункт назна­чения Пункт отправления	B 1	B 2	B 3	B 4	Запас
A 1
A 2			30 –	+
A 3			120 +	130 –
Потребность

Определяем величину груза, перемещаемого по циклу (минимальное значение объема перевозок среди всех разгружаемых ячеек):

min {30; 130} = 30.

Перемещая груз, получаем новый опорный план:

Пункт назна­чения Пункт отправления	B 1	B 2	B 3	B 4	Запас
A 1
A 2		120 –		30 +
A 3		+		100 –
Потребность

Ячейка A ₃ B ₄ осталась еще загруженной. Поэтому для нее строим еще контур.

Определяем величину груза, перемещаемого по циклу:

min {120; 100} = 100.

Перемещая груз, получаем новый опорный план:

Пункт назна­чения Пункт отправления	B 1	B 2	B 3	B 4	Запас
A 1
A 2	40 –	20+
A 3	+	100 –
Потребность

Ячейка A ₃ B ₄ оказалась разгруженной. Мы ее перечеркиваем и в дальнейших расчетах не рассматриваем.

Среди загруженных ячеек выбираем ячейку с наибольшим значением времени c_ij. Это ячейка A ₃ B ₂, для которой c ₃₂ = 6. Исключаем из рассмотрения все свободные ячейки, для которых c_ij > c ₃₂. Такая ячейка одна – A ₁ B ₂.

Для ячейки A ₃ B ₂ строим контур. Определяем величину груза, перемещаемого по циклу:

min {40; 100} = 40.

Перемещая груз, получаем новый опорный план:

Пункт назна­чения Пункт отправления	B 1	B 2	B 3	B 4	Запас
A 1	30 –			+
A 2		60+		130 –
A 3	40+	60 –
Потребность

Ячейка A ₃ B ₂ осталась еще загруженной. Поэтому для нее строим еще контур.

Определяем величину груза, перемещаемого по циклу:

min {30; 130; 60} = 30.

Перемещая груз, получаем новый опорный план:

Пункт назна­чения Пункт отправления	B 1	B 2	B 3	B 4	Запас
A 1
A 2
A 3
Потребность

Данное решение является оптимальным, так как нельзя построить разгрузочный цикл для ячейки A ₃ B ₂. Следовательно, оптимальный план перевозок осуществляется за время T = c ₃₂ = 6.