2 Математическая модель

Математическая модель в общем виде:

Вводятся обозначения:

m - количество видов заводов

n - количество видов складов

а - мощность i-ro завода

bj - потребность j-го склада

Cij - стоимость перевозки единицы продукции от i-ro завода к j-тому складу

Хij - количество единиц продукции, запланированных к перевозке от i-ro завода к j-тому складу

Zmin - минимальная стоимость перевозок (min транспортные издержки) Математическая модель данной задачи имеет вид:

Z =30X11+32X12+25X13+50X14+23X15+40X21+10X22+12X33+21X24+25X25+21X31+20X31+50X33+18X34+14X35 min

3 Метод реализации модели

Данная ТЗ решается методом потенциалов.

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

Для этого используется табл. 2.

Таблица 2

Суть метода минимальной стоимости заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел а; или bj. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

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

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

После получения опорного плана для дальнейших вычислений необходимо воспользоваться методом потенциалов. Для проверки найденного плана ТЗ, необходимо предварительно вычислить числа Ui и Vj , называемые потенциалами и отвечающие исходному плану. Для начала итерационного процесса нужно составить систему потенциалов для Хij > 0 в полученном опорном плане. Для Uj и Vj справедливо равенство Ui + Vj = Сij.

Получается m + n-1 уравнений с m + n неизвестными. Принимая U1 = О,

найдем значения остальных неизвестных Uj и Vj.

Затем находится значение Uj + Vj - Сij для всех Хij = 0. Если при решении получается, что для всех Хij = 0 значение Ui + Vj-Cij > 0, то найденный план является оптимальным.

Если для некоторых Хij = 0 значения Ui + Vj-Cij > 0, то найденный опорный план не является оптимальным, то есть не выполняется условие оптимальности

С ij — С ij < 0. Следовательно, нужно переходить к новому опорному плану и снова проверить его на оптимальность.

Для перехода к новому опорному плану выбирается наибольшее положительное число из всех С ij — С ij < 0

Чтобы найти вектор, исключаемый из первоначального базиса, можно воспользоваться таким приемом: из клетки, имеющей максимум С ij — С ij >0,

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

Из клеток со значением (+) выбирается наименьшее значение. Это значение необходимо вычесть из всех клеток со знаком (+) и прибавить к тем клеткам, у которых знак (-). При помощи этого способа получается новый опорный план. Далее снова находятся потенциалы Хij > 0. Этот процесс повторяется до тех пор, пока не получится оптимальный план, то есть пока не

будет выполняться критерий оптимальности С ij — С ij < 0 Вычисления сводятся в таблицу 2.

4 АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ