Транспортная задача: Построение исходного допустимого плана в транспортной задаче

Построение исходного допустимого плана в транспортной задаче.

Процесс решения транспортной задачи удобно оформлять в виде последовательности таблиц.

Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта aj), а столбцы — пунктам потребления (послед няя клетка каждого столбца содержит значение потребности bj).

Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для данных пунктов.

Клетки, которые содержат нулевые перевозки (xi,j = 0), называют свободными, а ненулевые — занятыми (xi,j > 0).

Метод северо-западного угла.

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

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

Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы. Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами:

ОППА ошибка в формуле!

После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину:

ОППА ошибка в формуле!

Очевидно, что на каждом шаге выполняется хотя бы одно из равенств:

ОППА ошибка в формуле!

или

ОППА ошибка в формуле!

Если справедливо первое, то это означает, что весь запас i-ro пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i + 1, т. е. переместиться к следующей клетке вниз по столбцу.

Если же

ОППА ошибка в формуле!

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

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

Не исключено, что на некотором промежуточном шаге текущий не распределенный запас оказывается равным текущей неудовлетворенной потребности

ОППА ошибка в формуле!

В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает «потерю» одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана.



Наши друзья

Качественное решение задач курсовых работ, РГЗ по техническим предметам.
botaniks.ru

Это интересно...

Наши контакты

Рейтинг@Mail.ru

© 2009-2016, Список Литературы