Методы оптимизации в технико-экономических задачах

Задача состоит в определении такого распределения грузов, при котором суммарная стоимость перевозок была бы минимальной, то есть

→ min

Ограничения:

1) наличие в каждом пункте отправления определённого количества товаров:

(i=1 m)

2) потребность у каждого пункта назначения в определённом количестве товаров:

(j=1 n)

3) xij≥0 (i=1 m, j=1 n)

Количество переменных хij в задаче с m пунктами отправления и n пунктами назначения равно (m * n), а число уравнений равно (m + n). Для того, чтобы соблюдалось равенство , число линейно независимых уравнений должно быть равно (m + n - 1). Таким образом, базис будет содержать (m + n - 1) неизвестных.

Базис является невырожденным, если в нём число отличных от нуля компонент точно совпадает с (m + n - 1). Если же это число меньше нуля, то базис - вырожденный.

Существует несколько методов определения начального базиса: метод северо-западного угла, метод двойного предпочтения, метод Фогеля и др.

Метод северо-западного угла является одним из наиболее простых и распространенных методов, но он дает самый далекий от оптимального план. В этом случае начинаем заполнять таблицу с крайней левой верхней клетки (C11) наибольшим возможным объемом груза. Затем вычеркиваем соответствующую строку или столбец и заполняем ставшую крайней левой верхней свободную клетку (т.е. C12 или C21). Продолжаем до тех пор, пока полностью не определим начальный базис.

В методе двойного предпочтения следует в каждой строке отметить галочкой клетку с наименьшим тарифом, затем то же сделать для каждого столбца. Далее выбираем клетку, в которой находятся две галочки, если таких клеток оказалось несколько, то выбираем ту, у которой наименьший тариф. В эту клетку записывается максимально возможное значение. Максимально возможное значение будет равно минимальному из чисел ai и bj. Далее процесс продолжается аналогично до полного определения начального базиса.

Метод, который дает наиболее близкий к оптимальному план - метод Фогеля. Согласно этому методу для каждой строки и столбца находим "штраф", равный модулю разности между двумя наименьшими стоимостями. Затем начинаем заполнять клетки с той строки или столбца, где имеется наибольший штраф. Заполняем клетку с наименьшей стоимостью перевозки наибольшим объемом груза. Затем столбец вычеркивается и "штрафы" пересчитываются. Процесс продолжается дальше до полного определения начального базиса.

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

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

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

+vj = cij

После того, как все потенциалы найдены, вычисляются косвенные стоимости (косвенные стоимости находятся для клеток, не вошедших в базис):

’= ui+vj

Затем, для каждой свободной клетки определяется разность:

’=ckl - ckl’ ,

где к и l - индексы свободных клеток.

Оптимальное решение найдено, если все разности fkl’=ckl - ckl’ для свободных клеток неотрицательные. Выражение для целевой функции через свободные неизвестные имеет все неотрицательные коэффициенты, значит уменьшить функцию дальше нельзя, найдено оптимальное решение.

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

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

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