Переход от одного опорного решения к другому в транспортной задаче 245.
Наличие положительной оценки свободной клетки (Δij > 0) при проверке опорного решения на оптимальность свидетельствует о том, что полученное решение не оптимально и для уменьшения значения целевой функции надо перейти к другому опорному решению. При этом надо перераспределить грузы, перемещая их из занятых клеток в свободные. Свободная клетка становится занятой, а одна из ранее занятых клеток — свободной. Для свободной клетки с Δij > 0 строится цикл (цепь, многоугольник), все вершины которого кроме одной находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (—) и (+). У вершин со знаком (—) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (—). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность, и т.д. до тех пор, пока не получим оптимальное решение. Рассмотрим переход от одного опорного решения к другому на заданном примере. ... Смотреть решение »

Найденное исходное опорное решение проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему соответствует система m+ п действительных чисел ui и vj, удовлетворяющих условиям ui + vj = cij для занятых клеток и ui + vj - сij ≤ 0 для свободных клеток.
Числа ui и vj называют потенциалами.
В распределительную таблицу добавляют строку vj и столбец ui.
 Потенциалы ui и vj находят из равенства ui + vj = cij, справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, например u1 = 0, тогда остальные потенциалы определяются однозначно.
Так, если известен потенциал ui, то vj = сij — ui; если известен потенциал vj, то ui = cij – vj. Обозначим Δij = ui + vj - cij.
Эту оценку называют оценкой свободных клеток.
Если Δij ≤ 0, то опорное решение является оптимальным. Если хотя бы одна из оценок Δij > 0, то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому.
Проверим найденное опорное решение на оптимальность, добавив в распределительную табл. 23.3 столбец ui и ... Смотреть решение »

Задача 245. На складах A1, А2, А3 имеются запасы продукции в количествах 90, 400, 110 т соответственно. Потребители В1, В2, B3 должны получить эту продукцию в количествах 140, 300, 160 т соответственно. Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей (усл. ед.)
Решение. ... Смотреть решение »