Математическое программирование — страница 5

расходы не увеличились. Определение: циклом пересчета таблицы называется последовательность клеток, удовлетворяющая условиям: 1) одна клетка пустая, все остальные занятые; 2) любые две соседние клетки находятся в одной строке или в одном столбце; 3) никакие 3 соседние клетки не могут быть в одной строке или в одном столбце . Пустой клетке присваивают знак « + », остальным - поочередно знаки « - » и « + ». Для перераспределения плана

перевозок с помощью цикла перерасчета сначала находят незаполненную клетку (r, s), в которой ar+bs>Crs, и строят соответствующий цикл; затем в минусовых клетках находят число X=min{Xij}. Далее составляют новую таблицу по следующему правилу: 1) в плюсовые клетки добавляем X; 2) из минусовых клеток отнимаем Х; 3) все остальные клетки вне цикла остаются без изменения. Получим новую таблицу, дающее новое решение X, такое, что f(X1) £ f(X0); оно снова

проверяется на оптимальность через конечное число шагов обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует. 11. Алгоритм метода потенциалов. 1) проверяем тип модели транспортной задачи и в случае открытой модели сводим ее к закрытой; 2) находим опорный план перевозок путем составления 1-й таблицы одним из способов - северо-западного угла или наименьшего тарифа; 3) проверяем план (таблицу) на

удовлетворение системе уравнений и на невыражденность; в случае вырождения плана добавляем условно заполненные клетки с помощью « 0 »; 4) проверяем опорный план на оптимальность, для чего: а) составляем систему уравнений потенциалов по заполненным клеткам; б) находим одно из ее решений при a1=0; в) находим суммы ai+bj=C¢ij («косвенные тарифы») для всех пустых клеток; г) сравниваем косвенные тарифы с истинными: если косвенные тарифы не

превосходят соответствующих истинных(C¢ij £ Cij) во всех пустых клетках, то план оптимален (критерий оптимальности). Решение закончено: ответ дается в виде плана перевозок последней таблицы и значения min f. Если критерий оптимальности не выполняется, то переходим к следующему шагу. 5) Для перехода к следующей таблице (плану): а) выбираем одну из пустых клеток, где косвенный тариф больше истинного (C¢ij= ai+bj > Cij ); б) составляем

цикл пересчета для этой клетки и расставляем знаки « + », « - » в вершинах цикла путем их чередования, приписывая пустой клетке « + »; в) находим число перерасчета по циклу: число X=min{Xij}, где Xij - числа в заполненных клетках со знаком « - »; г) составляем новую таблицу, добавляя X в плюсовые клетки и отнимая X из минусовых клеток цикла 6) См. п. 3 и т.д. Через конечное число шагов (циклов) обязательно приходим к ответу, ибо транспортная задача