Транспортная задача: Построение исходного допустимого плана в транспортной задаче
Построение исходного допустимого плана в транспортной задаче.
Процесс решения транспортной задачи удобно оформлять в виде последовательности таблиц.
Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта aj), а столбцы — пунктам потребления (послед няя клетка каждого столбца содержит значение потребности bj).
Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для данных пунктов.
Клетки, которые содержат нулевые перевозки (xi,j = 0), называют свободными, а ненулевые — занятыми (xi,j > 0).
Метод северо-западного угла.
По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла.
Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления.
Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы. Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами:
![\[{x_{i,j}} = \min \left\{ {a_i^{\left( q \right)},b_j^{\left( q \right)}} \right\}\]](https://spisok-literaturi.ru/cache/aa6ef9a73599f3f2cb28fc73587fbfda.png)
После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину:
![\[b_j^{\left( {q + 1} \right)} = b_j^{\left( q \right)} - {x_{i,j}}\]](https://spisok-literaturi.ru/cache/bed16cb0d1baba6a2201b4c0ae339084.png)
Очевидно, что на каждом шаге выполняется хотя бы одно из равенств:
![\[a_i^{\left( {q + 1} \right)} = 0\]](https://spisok-literaturi.ru/cache/7f2b75b35ddae280bf66be32d6fa9c04.png)
или
![\[b_j^{\left( {q + 1} \right)} = 0\]](https://spisok-literaturi.ru/cache/bb9fb6b6f260c038b2a31d99fb71333a.png)
Если справедливо первое, то это означает, что весь запас i-ro пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i + 1, т. е. переместиться к следующей клетке вниз по столбцу.
Если же
то значит, полностью удовлетворена потребность для j-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции.
Основываясь на условии баланса запасов и потребностей, нетрудно доказать, что за конечное число шагов мы получим допустимый план.
Не исключено, что на некотором промежуточном шаге текущий не распределенный запас оказывается равным текущей неудовлетворенной потребности
![\[\left( {a_i^{\left( q \right)} = b_j^{\left( q \right)}} \right)\]](https://spisok-literaturi.ru/cache/ca02a86d0644c0882284ea0f23c067f1.png)
В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает «потерю» одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана.
