Читать реферат по математике: "Математическое программирование" Страница 4

(Назад) (Cкачать работу)

Критерий оптимальности. Если известны потенциалы решения X0 транспортной задачи и для всех незаполненных клеток выполняются условия ai+bj £ Ci j, то X0 является оптимальным планом транспортной задачи.

Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличились.

Определение: циклом пересчета таблицы называется последовательность клеток, удовлетворяющая условиям:

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

Пустой клетке присваивают знак “ + ”, остальным - поочередно знаки “ - ” и “ + ”.

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

в плюсовые клетки добавляем X;из минусовых клеток отнимаем Х;все остальные клетки вне цикла остаются без изменения.

Получим новую таблицу, дающее новое решение X, такое, что f(X1) £ f(X0); оно снова проверяется на оптимальность через конечное число шагов обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.

Алгоритм метода потенциалов.

проверяем тип модели транспортной задачи и в случае открытой модели сводим ее к закрытой;

находим опорный план перевозок путем составления 1-й таблицы одним из способов - северо-западного угла или наименьшего тарифа;

проверяем план (таблицу) на удовлетворение системе уравнений и на невыражденность; в случае вырождения плана добавляем условно заполненные клетки с помощью “ 0 ”;проверяем опорный план на оптимальность, для чего:

а) составляем систему уравнений потенциалов по заполненным клеткам;

б) находим одно из ее решений при a1=0;

в) находим суммы ai+bj=C¢ij (“косвенные тарифы”) для всех пустых клеток;

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

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

Для перехода к следующей таблице (плану):

а) выбираем одну из пустых клеток, где косвенный тариф больше истинного (C¢ij= ai+bj > Cij );

б) составляем цикл пересчета для этой клетки и расставляем знаки “ + ”, “ - ” в вершинах цикла путем их чередования, приписывая пустой клетке “ + ”;

в) находим число перерасчета по циклу: число X=min{Xij}, где Xij - числа в заполненных клетках со знаком “ - ”;

г) составляем новую таблицу, добавляя X в плюсовые клетки и отнимая X из минусовых клеток цикла

См. п. 3 и т.д.

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

Похожие работы