3.2.1. Нахождение опорного плана

Нахождение опорного плана покажем с помощью правила “северо-западного угла” и правила “минимального элемента”.

По правилу “северо-западного угла” заполнение таблицы начинается с левого верхнего элемента х₁₁ матрицы Х (что и обусловило название правила):

х₁₁ min(а₁,b₁),

при этом возможны три случая:

-если a₁<b₁, то х₁₁ а₁, а оставшаяся часть первой строки, начиная со второго элемента, заполняется нулями;

-если a₁>b₁, то х₁₁ b₁, а оставшиеся элементы первого столбца заполняются нулями;

-если a₁ b₁, то х₁₁ а₁ b₁, а оставшиеся элементы первых строки и столбца заполняются нулями.

Затем вычисляются х₁₂ min(а₁-х₁₁,b₂) при a₁>b₁ или х₂₁ min(а₂,b₁-х₁₁) при a₁<b₁.

Этот процесс повторяется до тех пор, пока матрица Х не будет полностью заполнена, т.е. ресурсы a_i будут исчерпаны, а b_j потребности удовлетворены.

Пример 3.5. Пусть дана Т-задача с четырьмя пунктами отправления a_i (i= ) и четырьмя пунктами потребления b_j (j= ) в виде исходной таблицы

Проверим условие баланса: , откуда 190=190.

Определим опорный план

,

где

Стоимость полученного плана составляет

F(Х)

П

21

ри построении опорного плана по правилу ”минимального элемента” вычисления проводятся следующим образом: находится элемент c_ij матрицы С с наименьшей стоимостью перевозки; начиная с этого элемента, последовательно нумеруются элементы матрицы С в порядке их возрастания; затем в том же порядке определяются элементы x_ij матрицы Х₀ с использованием процедуры правила “северо-западного угла”. Правило “минимального элемента” позволяет построить опорный план с учетом матрицы стоимости перевозок, сокращая общее количество итераций по его оптимизации. Например, стоимость одного из опорных планов, построенных по данному правилу, составляет F(Х)=295, что по сравнению со стоимостью плана, полученного по правилу “северо-западного угла”, меньше на 35 ед.

Клетки матрицы Х₀, в которых стоят ненулевые перевозки, являются базисными, их число удовлетворяет условию r m n-1 7, где r – ранг матрицы. Остальные клетки – свободные, в них стоят нулевые перевозки, число которых равно (m-1)(n-1) 9. Поэтому полученный план является не только допустимым, но и опорным.

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

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

3.2.2. Улучшение опорного плана

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

После получения начального опорного плана – Х₀ рассчитываются для каждой базисной клетки Т-таблицы потенциалы u_i и v_j по формуле

u_i v_j c_ij ( ). (3.25)

Для нахождения u_i и v_j одному из них придается произвольное значение (обычно u₁ полагают равным нулю).

Далее по вычисленным значениям потенциалов определяются оценки для небазисных клеток

. (3.26)

Затем анализируются значения оценок . При этом, если окажется, что для всех небазисных клеток , то план оптимален. Если имеется хотя бы в одной клетке оценка , то план следует улучшить перемещением перевозок по циклу. Цикл представляет собой последовательное соединение замкнутой ломаной линией некоторых клеток, расположенных в одном ряду (строке, столбце), причем число клеток в одном ряду должно быть равно двум. Цикл имеет четное число вершин, одна из которых размещается в небазисной клетке, в которой оценка имеет наибольшее значение. Другие вершины цикла размещаются в базисных клетках Т-таблицы. Цикл начинается и заканчивается выбранной небазисной переменной (клеткой). Вершина цикла с небазисной клеткой отмечается знаком “+”. Далее в направлении обхода цикла знаки вершин чередуются.

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

Процедура улучшения плана продолжается до получения оптимального решения.

Можно рекомендовать следующий порядок действий при решении Т-задачи:

1. Составляется начальный опорный план.

2. Для полученного плана по уравнениям (3.25) определяются потенциалы u_i и v_j, соответствующие базисным клеткам.

3. По вычисленным значениям потенциалов с помощью уравнений (3.26) находятся оценки для небазисных клеток.

4

23

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

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

5. Процедура улучшения плана в соответствии с пп. 2-4 продолжается до получения оптимального решения.

Рассмотрим применение описанного алгоритма на примере 3.5, опорный план которого получен по правилу “северо-западного угла” и имеет вид

 +

+ 









Определим значения потенциалов u_i и v_j по уравнениям (3.25), используя опорный план Х₀ и матрицу стоимостей перевозок С.

u₁ v₁ c₁₁; u₃ v₃ c₃₃;

u₂ v₁ c₂₁; u₃ v₄ c₃₄;

u₂ v₂ c₂₂; u₄ v₄ c₄₄.

u₂ v₃ c₂₃;

Из приведенных уравнений получаем

u₁ 0; u₂ 2; u₃ 9; u₄ 7; v₁ 1; v₂ 2; v₃ 1; v₄ 6.

По вычисленным значениям потенциалов находим оценки, используя уравнения (3.26)

Оценка имеет наибольшее положительное значение. Этой оценке соответствует переменная х₃₂, которая выбирается в качестве вводимой в новое базисное решение.

Улучшим опорный план, осуществляя перемещение перевозок по замкнутому циклу, начальная вершина которого располагается в клетке с оценкой .

Новое улучшенное решение имеет вид

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

Построенный план является вырожденным, так как количество базисных переменных равно 6, а r (m n-1) 7.

Введем в базисное решение переменную х₂₂ с нулевой перевозкой и проверим оптимальность нового плана вычислением новых потенциалов u_i и v_j и оценок .

Новые значения потенциалов: u₁ 0; u₂ 2; u₃ 2; u₄ 0; v₁ 1; v₂ 2; v₃ 1; v₄ 1.

Новые значения оценок: 0; 10; 6; 4; 2; 3; 7; 1; 1; 4.

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