Первоначальное распределение поставок

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

Прежде чем начать заполнение клеток таблицы поставками, нужно установить число таких клеток. Это число определяется числом линейно независимых уравнений системы ограничений. Рассмотрим закрытую модель. Система ограничений содержит m+n уравнений, однако из-за условия закрытости число линейно независимых уравнений, а следовательно, и число заполняемых клеток равно m+n-1.

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

2.1.9. Правило "Северо-западного угла"

Не обращая внимания на показатели затрат, начинаем заполнение клеток поставками с клетки (1,1). Спрос первого потребителя составляет величину a1. Если a1 меньше или равна B1 (величины запаса первого поставщика),.то в клетку (1,1) заносим эту величину ai и вычитаем из B1 a1. В противном случае, если a1 больше B1, то в клетку (1,1) пишем поставку равную b1, а остатки A1-B1 пишем в клетку (2,1).т.е. сравнивая этот остаток с запасом В2 и так далее. Таким образом, спускаясь ступенями, заполняем поставками таблицу.

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

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

2.1.10. Циклы перераспределения поставок

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

Определение. Циклом называется замкнутый многоугольник (вообще может быть невыпуклый). Сторонами многоугольника являются горизонтальные и вертикальные отрезки. Одна вершина совпадает со свободной клеткой, для которой образуется цикл, а все остальные - с заполненными клетками.