Примечание. 1. Построим математическую модель транспортной задачи

Решение.

1. Построим математическую модель транспортной задачи.

Пусть x_ij – объем перевозок из пункта отправления А_i в пункт назначения В_j.

Тогда математическую модель сформулированной транспортной задачи можно записать в виде:

- суммарные затраты на перевозку груза должны быть минимальными

f = 4 x ₁₁ + 7 x ₁₂ + 2 x ₁₃ + 3 x ₁₄ + 3 x ₂₁ + 1 x ₂₂ + 0 x ₂₃ + 4 x ₂₄ + 5 x ₃₁ + 6 x ₃₂ + 3 x ₃₃ + 7 x ₃₄ ® min;

- объем поставок из пункта отправления А_i должен равняться запасу имеющегося груза

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

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

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

- объем поставок в пункт назначения В_j должен быть равен потребности

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

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

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

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

- объемы поставок должны выражаться неотрицательными числами

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

Следует также отметить, что данная задача является сбалансированной, поскольку объем спроса равен объему предложения:

70 + 120 + 150 + 130 = 470 = 30 + 190 + 250.

Примечание.

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

f = 4 x ₁₁ + 7 x ₁₂ + 2 x ₁₃ + 3 x ₁₄ + 0 x ₁₅ + 3 x ₂₁ + 1 x ₂₂ + 0 x ₂₃ + 4 x ₂₄ + 0 x ₂₅ + 5 x ₃₁ + 6 x ₃₂ + 3 x ₃₃ + 7 x ₃₄ + 0 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.

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

f = 4 x ₁₁ + 7 x ₁₂ + 2 x ₁₃ + 3 x ₁₄ + 3 x ₂₁ + 1 x ₂₂ + 0 x ₂₃ + 4 x ₂₄ + 5 x ₃₁ + 6 x ₃₂ + 3 x ₃₃ + 7 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.

2. Указанную в вариантах 1-20 себестоимость единицы продукции в i -м пункте c_i перед построением математической модели следует добавить к соответствующим строкам матрицы стоимости перевозок, чтобы получить совокупные затраты на производство и транспортировку продукции. Если, например, себестоимость продукции будет равна 2, 4, 3 ден. ед., то матрица затрат примет вид

.

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

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

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

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

3. Найдем начальный опорный план транспортной задачи.

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

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

Среди оставшихся незаполненных ячеек минимальная стоимость перевозок (1) записана в в ячейке A ₂ B ₂. Исходя из оставшихся объемов спроса и предложения, в данную ячейку можно записать значение объемов поставок 40 ед. Запасы пункта отправления A ₂ исчерпаны. Поэтому далее в строке A ₂ оставшиеся ячейки рассматриваться не будут. В пункте назначения B ₂ остался неудовлетворенным спрос в 80 ед.

Среди оставшихся незаполненных ячеек минимальная стоимость перевозок (3) записана в в ячейке A ₁ B ₄. Исходя из имеющихся объемов спроса и предложения, в данную ячейку можно записать значение объемов поставок 30 ед. Запасы пункта отправления A ₁ исчерпаны. Поэтому далее в строке A ₁ оставшиеся ячейки рассматриваться не будут. В пункте назначения B ₄ остался неудовлетворенным спрос в 100 ед.

Для рассмотрения осталась одна строка A ₃. Заполним оставшиеся ячейки, исходя из объемов неудовлетворенного спроса: в 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 ´ 3 + 40 ´ 1 + 150 ´ 0 + 70 ´ 5 + 80 ´ 6 + 100 ´ 7 = 90 + 40 + 350 + 480 + 700 = 1660.

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

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

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

u ₁ = 0;

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

A ₃ B ₄: u ₃ + v ₄ = 7; u ₃ + 3 = 7; u ₃ = 4;

A ₃ B ₁: u ₃ + v ₁ = 5; 4 + v ₁ = 5; v ₁ = 1;

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

A ₂ B ₂: u ₂ + v ₂ = 1; u ₂ + 2 = 1; u ₂ = –1;

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

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

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

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

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

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

A ₂ B ₄: D₂₄ = u ₂ + v ₄ – c ₂₄ = –1 + 3 – 4 = –2;

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

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

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

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

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

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

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

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

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

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

min {150; 80} = 80.

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

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

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

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

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

u ₁ = 0;

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

A ₃ B ₄: u ₃ + v ₄ = 7; u ₃ + 3 = 7; u ₃ = 4;

A ₃ B ₁: u ₃ + v ₁ = 5; 4 + v ₁ = 5; v ₁ = 1;

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

A ₂ B ₃: u ₂ + v ₃ = 0; u ₂ + –1 = 0; u ₂ = 1;

A ₂ B ₂: u ₂ + v ₂ = 1; 1 + v ₂ = 1; v ₂ = 0.

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

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

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

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

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

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

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

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

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

f = 30 ´ 3 + 120 ´ 1 + 70 ´ 0 + 70 ´ 5 + 80 ´ 3 + 100 ´ 7 = 90 + 120 + 350 + 240 + 700 = 1500.

Примечание. При решении задачи на максимум (варианты 21-30) можно поступать одним из двух способов.

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

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