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

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

Так, если бы объемы производства продукции составляли бы 30, 190, 270 единиц при прежних объемах спроса, то математическая модель задачи приняла бы вид (добавлен фиктивный потребитель):

f = 6 x ₁₁ + 9 x ₁₂ + 4 x ₁₃ + 5 x ₁₄ + 2 x ₁₅ +

+ 7 x ₂₁ + 5 x ₂₂ + 4 x ₂₃ + 8 x ₂₄ + 4 x ₂₅ +

+ 8 x ₃₁ + 9 x ₃₂ + 6 x ₃₃ + 10 x ₃₄ + 3 x ₃₅ ® min;

x ₁₁ + x ₁₂ + x ₁₃ + x ₁₄ + x ₁₅ = 30;

x ₂₁ + x ₂₂ + x ₂₃ + x ₂₄ + x ₂₅ = 190;

x ₃₁ + x ₃₂ + x ₃₃ + x ₃₄ + x ₃₅ = 270;

x ₁₁ + x ₂₁ + x ₃₁ = 70;

x ₁₂ + x ₂₂ + x ₃₂ = 120;

x ₁₃ + x ₂₃ + x ₃₃ = 150;

x ₁₄ + x ₂₄ + x ₃₄ = 130;

x ₁₅ + x ₂₅ + x ₃₅ = 20;

x_ij ³ 0, i = 1,..., 3, j = 1,..., 5.

Отметим, что поскольку в математическую модель добавлен фиктивный потребитель, то для него в целевой функции также следует учитывать себестоимость производства продукции (коэффициенты при переменных x ₁₅, x ₂₅, x ₃₅).

Если бы спрос на продукцию составил бы величину 70, 120, 150, 160 единиц при прежних объемах производства, то математическая модель задачи приняла бы вид (добавлен фиктивный поставщик):

f = 6 x ₁₁ + 9 x ₁₂ + 4 x ₁₃ + 5 x ₁₄ +

+ 7 x ₂₁ + 5 x ₂₂ + 4 x ₂₃ + 8 x ₂₄ +

+ 8 x ₃₁ + 9 x ₃₂ + 6 x ₃₃ + 10 x ₃₄ +

+ 0 x ₄₁ + 0 x ₄₂ + 0 x ₄₃ + 0 x ₄₄ ® min;

x ₁₁ + x ₁₂ + x ₁₃ + x ₁₄ = 30;

x ₂₁ + x ₂₂ + x ₂₃ + x ₂₄ = 190;

x ₃₁ + x ₃₂ + x ₃₃ + x ₃₄ = 250;

x ₄₁ + x ₄₂ + x ₄₃ + x ₄₄ = 30;

x ₁₁ + x ₂₁ + x ₃₁ + x ₄₁ = 70;

x ₁₂ + x ₂₂ + x ₃₂ + x ₄₂ = 120;

x ₁₃ + x ₂₃ + x ₃₃ + x ₄₃ = 150;

x ₁₄ + x ₂₄ + x ₃₄ + x ₄₄ = 160;

x_ij ³ 0, i = 1,..., 4, j = 1,..., 4.

Поскольку в математическую модель добавлен фиктивный поставщик, а для него не определена величина себестоимости производства единицы продукции, то в целевой функции при переменных x ₄₁, x ₄₂, x ₄₃, x ₄₄ используются нулевые коэффициенты.

2. Табличная модель исходной транспортной задачи будет иметь вид.

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

Для случая ввода фиктивного потребителя табличная модель транспортной задачи примет вид.

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

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

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

3. Для построения начального опорного плана транспортной задачи могут применяться следующие методы:

- северо-западного угла (диагональный);

- минимального элемента (минимальной стоимости) и др.

Воспользуемся методом северо-западного угла.

Загрузим левую верхнюю ячейку транспортной таблицы (A ₁ B ₁). Исходя из объемов спроса (70 ед.) и предложения (30 ед.), в данную ячейку можно записать значение объемов поставок 30 ед. Для пункта потребления B ₁ остался неудовлетворенным спрос в 40 ед. продукции. Поскольку запас первого поставщика (пункта производства А ₁) исчерпан, то мы не будем больше рассматривать оставшиеся ячейки из первой строки транспортной таблицы.

Переходим к лежащей ниже ячейке – ячейке A ₂ B ₁. Исходя из оставшихся объемов спроса (40 ед.) и предложения (190 ед.), в данную ячейку можно записать значение объемов поставок 40 ед. Потребность пункта назначения B ₁ теперь удовлетворена полностью. Поэтому далее в столбце B ₁ оставшиеся ячейки рассматриваться не будут. В пункте отправления A ₂ остался запас в 150 ед. продукции.

Переходим к ячейке справа – ячейке A ₂ B ₂. Исходя из имеющихся на данный момент объемов спроса (120 ед.) и предложения (150 ед.), в данную ячейку можно записать значение объемов поставок 120 ед. Потребность пункта назначения B ₂ удовлетворена полностью. Поэтому также как и ранее в столбце B ₂ оставшиеся ячейки рассматриваться не будут. В пункте отправления A ₂ остался запас в 30 ед. продукции.

Переходим к ячейке справа – ячейке A ₂ B ₃. Исходя из текущих объемов спроса (150 ед.) и предложения (30 ед.), в данную ячейку можно записать значение объемов поставок 30 ед. Запас второго поставщика (пункта производства А ₂) исчерпан полностью. Поэтому мы не будем больше рассматривать оставшиеся ячейки из второй строки транспортной таблицы. Для пункта потребления B ₃ остался неудовлетворенным спрос в 120 ед. продукции.

Переходим к лежащей ниже ячейке – ячейке A ₃ B ₃. Исходя из оставшихся объемов спроса (120 ед.) и предложения (250 ед.), в данную ячейку можно записать значение объемов поставок 120 ед. Потребность пункта назначения B ₃ теперь удовлетворена полностью. В пункте отправления A ₃ остался запас в 130 ед. продукции.

Переходим к ячейке справа – ячейке A ₃ B ₄. Это нижняя левая ячейка транспортной таблицы. В силу сбалансированности исходной транспортной задачи оставшиеся объемы спроса и предложения для данного маршрута совпадают и равны 130 ед. продукции. Поэтому в ячейку A ₃ B ₄ записываем поставку в 130 ед. Условие сбалансированности транспортной задачи является обязательным условием для построения ее табличной модели.

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

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

Значение целевой функции на данном опорном плане равно

f = 30 ´ 6 + 40 ´ 7 + 120 ´ 5 + 30 ´ 4 + 120 ´ 6 + 130 ´ 10 =

= 180 + 280 + 600 + 120 + 720 + 1300 = 3200.

Воспользуемся методом минимального элемента.

Минимальная стоимость перевозок (4 ден. ед.) записана в двух ячейках A ₁ B ₃ и A ₂ B ₃. Исходя из объемов спроса и предложения, в ячейку A ₁ B ₃ можно записать значение объемов поставок 30 ед. (запас – 30 ед., спрос – 150 ед.), а в ячейку A ₂ B ₃ – 150 ед. (запас – 190 ед., спрос – 150 ед.). Поэтому загрузке подлежит ячейка A ₂ B ₃, как имеющая больший возможный объем поставок. Потребность пункта назначения B ₃ удовлетворена полностью. Поэтому далее в столбце B ₃ оставшиеся ячейки рассматриваться не будут. В пункте отправления A ₂ остался запас в 40 ед.

Среди оставшихся незаполненных ячеек минимальная стоимость перевозок (5 ден. ед.) также записана в двух ячейках A ₂ B ₂ и A ₁ B ₄. Исходя из текущих объемов спроса и предложения, в ячейку A ₂ B ₂ можно записать значение объемов поставок 40 ед. (запас – 40 ед., спрос – 120 ед.), а в ячейку A ₁ B ₄ – 30 ед. (запас – 30 ед., спрос – 130 ед.). Поэтому загрузке подлежит ячейка A ₂ B ₂, как имеющая больший возможный объем поставок. Запасы пункта отправления A ₂ исчерпаны. Поэтому далее в строке A ₂ оставшиеся ячейки рассматриваться не будут. В пункте назначения B ₂ остался неудовлетворенным спрос в 80 ед. продукции.

Поскольку загрузка ячейки A ₂ B ₂ не повлияла на текущее состояние спроса и предложения в первой строке и четвертном столбце транспортной таблицы, то далее загрузке подлежит ячейка A ₁ B ₄, куда следует записать значение объемов поставок 30 ед. Запасы пункта отправления A ₁ исчерпаны. Поэтому далее в строке A ₁ оставшиеся ячейки рассматриваться также не будут. В пункте назначения B ₄ остался неудовлетворенным спрос в 100 ед. продукции.

Для рассмотрения осталась только одна третья строка транспортной таблицы. Заполним оставшиеся ячейки, исходя из объемов неудовлетворенного спроса: в A ₃ B ₁ – 70 ед. груза, в A ₃ B ₂ – 80 ед. груза, в A ₃ B ₄ – 100 ед. груза.

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

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

Значение целевой функции на данном опорном плане равно

f = 30 ´ 5 + 40 ´ 5 + 150 ´ 4 + 70 ´ 8 + 80 ´ 9 + 100 ´ 10 =

= 150 + 200 + 600 + 560 + 720 + 1000 = 3230.

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

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

В качестве исходного опорного плана выберем план, полученный методом минимального элемента.

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

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

u ₁ = 0;

A ₁ B ₄: u ₁ + v ₄ = 5; 0 + v ₄ = 5; v ₄ = 5;

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

A ₃ B ₁: u ₃ + v ₁ = 8; 5 + v ₁ = 8; v ₁ = 3;

A ₃ B ₂: u ₃ + v ₂ = 9; 5 + v ₂ = 9; v ₂ = 4;

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

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

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

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

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 ₂₁ = 1 + 3 – 7 = –3;

A ₂ B ₄: D₂₄ = u ₂ + v ₄ – c ₂₄ = 1 + 5 – 8 = –2;

A ₃ B ₃: D₃₃ = u ₃ + v ₃ – c ₃₃ = 5 + 3 – 6 = 2 > 0.

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

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

1) контур представляет собой замкнутый многоугольник произвольной формы, начинающийся и заканчивающийся в вершине максимальной неоптимальности;

2) остальные вершины контура находятся в загруженных ячейках (могут быть задействованы не все загруженные ячейки);

3) контур состоит из последовательности чередующихся горизонтальных и вертикальных (но не диагональных) отрезков;

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

Разгружаемые ячейки помечаем знаком «–», загружаемые – знаком «+».

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

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

min {150; 80} = 80.

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

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

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

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

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

u ₁ = 0;

A ₁ B ₄: u ₁ + v ₄ = 5; 0 + v ₄ = 5; v ₄ = 5;

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

A ₃ B ₁: u ₃ + v ₁ = 8; 5 + v ₁ = 8; v ₁ = 3;

A ₃ B ₃: u ₃ + v ₃ = 6; 5 + v ₃ = 6; v ₃ = 1;

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

A ₂ B ₂: u ₂ + v ₂ = 5; 3 + v ₂ = 5; v ₂ = 2.

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

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

A ₁ B ₂: D₁₂ = u ₁ + v ₂ – c ₁₂ = 0 + 2 – 9 = –7;

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

A ₂ B ₁: D₂₁ = u ₂ + v ₁ – c ₂₁ = 3 + 3 – 7 = –1;

A ₂ B ₄: D₂₄ = u ₂ + v ₄ – c ₂₄ = 3 + 5 – 8 = 0;

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

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

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

f = 30 ´ 5 + 120 ´ 5 + 70 ´ 4 + 70 ´ 8 + 80 ´ 6 + 100 ´ 10 =

= 150 + 600 + 280 + 560 + 480 + 1000 = 3070 ден. ед.

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

Так, например, рассмотрим опорный план следующего вида (может быть получен путем перераспределения поставок по контуру с вершиной максимальной неоптимальности в ячейке A ₂ B ₄).

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

Отметим, что план является невырожденным.

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

u ₁ = 0;

A ₁ B ₄: u ₁ + v ₄ = 5; 0 + v ₄ = 5; v ₄ = 5;

A ₂ B ₄: u ₂ + v ₄ = 8; u ₂ + 5 = 8; u ₂ = 3;

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

A ₃ B ₁: u ₃ + v ₁ = 8; 5 + v ₁ = 8; v ₁ = 3;

A ₃ B ₃: u ₃ + v ₃ = 6; 5 + v ₃ = 6; v ₃ = 1;

A ₂ B ₂: u ₂ + v ₂ = 5; 3 + v ₂ = 5; v ₂ = 2.

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

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

A ₁ B ₂: D₁₂ = u ₁ + v ₂ – c ₁₂ = 0 + 2 – 9 = –7;

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

A ₂ B ₁: D₂₁ = u ₂ + v ₁ – c ₂₁ = 3 + 3 – 7 = –1;

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

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

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

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

f = 30 ´ 5 + 120 ´ 5 + 70 ´ 8 + 70 ´ 8 + 150 ´ 6 + 30 ´ 10 =

= 150 + 600 + 560 + 560 + 900 + 300 = 3070 ден. ед.

Отметим, что хотя оба оптимальных плана различны, значение целевой функции для обоих планов одинаково.