Пример.

Имеется три карьера, производящие строительные материалы и четыре потребителя строительных материалов. Известны объемы производства на каждом карьере (запасы), потребности в их продукции каждого из потребителей (рис.3.3). Стоимость перевозки 1 т продукции с i –го  карьераj -му  потребителю задана той же таблицей. Определить, при каких объемах грузоперевозок суммарная стоимость перевозок будет минимальной.

Рис.3.3.Исходные данные транспортной задачи

Решение.

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

Вычислим суммарные запасы: и суммарные потребности:

.

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

Построим опорное решение методом «северо-западного» угла.

Для этого заполним ячейку (1,1). Занесем меньшее из чисел a₁иb₁, т.е.x₁₁ =min{a₁;b₁}=min{90;30} =30 и т.д. (рис.3.4).

В результате имеем таблицу с шестью заполненными клетками, что соответствует теории: m+n-1 =3+4-1=6.

Заметим, что суммарная стоимость перевозок равна

.

Рассчитаем систему потенциалов для этого решения.

Рис.3.4. Опорное решение, построенное методом «северо-западного» угла.

Для определения ;имеем следующую систему уравнений:

Имеем 6 уравнений и 7 неизвестных. Значение одной из неизвестных величин (любой !) можно задать произвольным образом (любое число). Положим U₃равным0. Тогда остальные величины будут равны:

U₁=1_, U₂= -1_, V₁= 8_, V₂= 7_, V₃= 4_, V₄= 6_.

Припишем значения потенциалов соответствующим строкам и столбцам. Введем дополнительный столбец U_i и дополнительную строкуV_j (рис.3.5) и занесем вычисленные значения потенциалов в полученные клетки.

Рис. 3.5. Транспортная таблица с вычисленными значениями потенциалов

Вычислим значения невязок для всех клеток без перевозок по формуле (3.7). Запишем их в правый верхний угол каждой клетки (жирный курсив). В ряде клеток (2,1), (2,3), (2,4) и (3,1) наблюдаются нарушения (невязки больше нуля). Выберем клетку (2,4), в которой наблюдается наибольшее превышение, равное 4. Построим замкнутый цикл с началом в этой клетке. В качестве остальных вершин выберем клетки (3,4), (3,2) и (2,2). Пронумеруем клетки (рис.3.4).

Нечетные вершины (2,4) и (3,2) образуют положительную полуцепь. Четные вершины (3,4) и (2,2) образуют отрицательную полуцепь. Величина q =min{90;130}=90.

Вычислим новые значения для узлов контура. В четных вершинах значения уменьшаются на q=90, в клетке (2,2) значение перевозки станет равным90-q = 0; в клетке (3,4) - равным130 -q = 130-90 = 40.В нечетных вершинах значения увеличатся наq=90, так в клетке (3,4) значение равно0+q=0+90=90,а в клетке (3,2) значение равно50+q=50+90=140.

Получим новое опорное решение (рис.3.6).

Рис. 3.6

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

.

Уменьшение стоимости перевозок по сравнению с начальным планом составило F₀ - F₁=2700 - 2340= 360.

Теоретически это уменьшение равно (q умножить на соответствующее превышение), т.е. те же 360 (произведение 90 на 4).

Рассчитаем новую систему потенциалов.

Для определения ;имеем следующую систему уравнений:

Имеем 6 уравнений и 7 неизвестных. Значение одной из неизвестных величин (любой !) можно задать произвольным образом (любое число). Положим U₃равным0. Тогда остальные величины будут равны

U₁=1_, U₂=3_, V₁=8_, V₂=7_, V₃=4_, V₄=6_.

Припишем значения потенциалов соответствующим строкам и столбцам в столбец U_i и строкуV_j(рис.3.6).

Вычислим значения невязок для всех клеток без перевозок по формуле (3.7). Запишем их в правый верхний угол каждой клетки (жирный курсив). В одной клетке (3,1) наблюдается нарушение (невязка равна 3, т.е. больше нуля). Построим замкнутый цикл с началом в этой клетке. В качестве остальных вершин выберем клетки (1,1),(1,2) и (3,2). Пронумеруем клетки (рис. 3.6).

Нечетные вершины (3,1) и (1,2) образуют положительную полуцепь. Четные вершины (1,1) и (3,2) образуют отрицательную полуцепь. Величина q =min{30;140}=30.

Вычислим новые значения для узлов контура.

В четных вершинах значения уменьшается на q=30: в клетке (1,1) значение перевозки станет равным30-q=0; в клетке (3,2) - равным140 - q=140-30=110.

В нечетных вершинах значения увеличатся на q: в клетке (3,1) значение станет равным0+q=0+30=30, а в клетке (1,2)60+q=60+30=90.

Получим новое опорное решение (рис.3.7).

Рис.3.7

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

.

Уменьшение стоимости перевозок по сравнению с предыдущим планом составило F₁ -F₂ = 2340 – 2250 = 90.

Теоретически это уменьшение равно (qумножить на соответствующее превышение), т.е. те же 90 (произведение 30 на 3).

Рассчитаем очередную систему потенциалов для полученного опорного решения.Для определения ;имеем следующую систему уравнений:

Имеем 6 уравнений и 7 неизвестных. Положим U₃= 0 , тогда остальные величины будут равны

U₁=1_, U₂=3_, V₁=5_, V₂=7_, V₃=4_, V₄=6_.

Запишем значения потенциалов соответствующим строкам и столбцам в столбец U_i и строкуV_j(рис. 3.6).

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