Исследование операций, методы оптимизации

;

Следовательно, задача закрытого типа.

Количество занятых клеток 6, т.е. 4+3-1=6. Начальный опорный план невырожденный.

Суммарные расходы на перевозку равны 12 100 руб.

2) Способ минимального элемента. В данном методе рассматриваются тарифы и в первую очередь заполняется клетка с минимальным значением тарифа. При этом в клетку записывается максимально возможное значение поставки. Затем из рассмотрения исключают строку, соответствующую поставщику, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос которого полностью удовлетворен. После этого из оставшихся клеток таблицы снова выбирают клетку с наименьшим тарифом. Процесс распределения заканчивается, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен. В результате получаем опорный план, который должен содержать n+m-1 заполненных клеток.

В процессе заполнения таблицы могут быть одновременно исключены и столбец и строка. Такое возможно в случае, когда исчерпан запас поставщика и полностью удовлетворен спрос потребителя. Полученный план будет вырожденным, т.к. не выполняется условие равенства количества занятых клеток величине n+m-1. В этом случае в свободную клетку необходимо записать число «0» - «ноль-загрузка», условно считая эту клетку занятой. Однако число «0» записывается в те свободные клетки, которые не образуют циклов с ранее занятыми клетками.

Циклом в матрице называется непрерывная замкнутая ломанная линия, вершины которой находятся в клетках матрицы, а звенья расположены вдоль строк и столбцов. При чем в каждой вершине цикла встречается ровно два звена, одно из них расположено по строке, второе - по столбцу. Если цикл образует самопересекающаяся ломанная линия, то точки ее самопересечения вершин не образуются. Примеры циклов:

Циклы в матрице тарифов удовлетворяю следующим свойствам:

1) число вершин в каждом цикле четно;

2) одна вершин цикла должна быть свободной клеткой, все остальные - занятыми.

Рассмотрим предыдущий пример.

Суммарные расходы на перевозку равны 11300 руб.

2) Метод Фогеля. В распределительной таблице по строкам и столбцам определяют разность между двумя наименьшими тарифами. Максимальную разность отмечают знаком « ». Далее в строке (или в столбце) с наибольшей разностью заполняется клетка с наименьшим тарифом. Строки (или столбцы) с нулевыми остатками груза в дальнейшем в расчет не принимаются. На каждом этапе загружается только одна клетка. Распределение груза производится по рассмотренным ранее правилам.

Суммарные расходы на перевозку равны 10 900 руб.

3. Метод потенциалов

Потенциалы и_i и v_j приписываются каждому поставщику и потребителю. Всего потенциалов п+m. Для заполненных клеток, которых т+п-- 1, выполняются условие (8)

.

Они служат теми уравнениями, из которых находят значения потенциалов. Эта система уравнений имеет бесчисленное множество решений, любое из которых составит искомую систему потенциалов. Чтобы найти какое-либо одно решение, значение одного из потенциалов нужно выбрать произвольно. Остальные устанавливаются из системы уравнений для заполненных клеток. Обычно считают, что u₁ = 0, и вычисляют остальные потенциалы.

Пример.

Для каждой клетки вычисляют оценки:

.

Если опорный допустимый план оптимален, то ? 0. Если же есть хоть одна отрицательная оценка, то план не оптимален. Тогда в базис вводят клетку с минимальной оценкой. Эту клетку называют перспективной.

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

Для улучшения опорного плана для перспективной свободной клетки строится замкнутый цикл. Вершинам этого цикла присваиваются знаки: свободной клетке - «плюс», следующей по часовой или против часовой стрелки клетке - знак «минус», следующей клетки - «плюс» и т.д.

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

-+ +-

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

1) построить опорный план по одному из правил;

2) вычислить потенциалы поставщиков и потребителей и , решив систему уравнений

;

3) вычислить оценки для всех свободных клеток. Если все ? 0, то опорный план оптимален. Если же для всех свободных клеток > 0, то оптимальный план единственный. Если же хоть для одной свободной оценки =0, то имеется бесчисленное множество оптимальных планов с одним и тем же значением целевой функции;

4) в случае если есть < 0, то строиться цикл, расчетная таблица заполняется заново и алгоритм начинается с пункта 2.

Размещено на Allbest.ru