Табличный метод решения транспортной задачи

Для решения транспортной задачи чаще всего используется табличный метод

В левом нижнем (или верхнем) углу каждой клетки записывается значение С_ij.- цена клетки. В правом углу клеток записываются текущие значения . Для того чтобы вносить меньше цифр, принять нулевые значения их не пишут, оставляют пустыми. Заполненная таблица называется планом перевозок.

Допустимый план - в котором по каждой строке и столбцу выполняется баланс. В этом случае удовлетворяются все ограничения.

Опорный план - в котором 0 только m+n-1 клетки, т.е. базисные клетки, все остальные должны быть пустыми.

Особенности заполнения таблицы транспортной задачи:

сначала заполняется левый столбец и верхняя строчка;

затем вносятся балансовые столбец и строчка и считается сумма;

в верхнем правом углу каждой клетки записывается соответствующая стоимость ;

для матрицы х нулевые значения не пишутся;

последними записываются стоимости (записывается общая стоимость всего плана).

Если в этой таблице поставить вместо , так что по строке и по столбцу суммы были равны балансовым, то говорят, что построен «план перевозок» (те цифры, которые сходятся по балансу). Иногда этот план наз. допустимым планом.

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

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

Для получения начального опорного плана есть 2 метода:

1) метод северо-западного угла;

2) метод наименьших затрат.

Для получения нового опорного плана:

метод циклических перестановок;

метод потенциалов Контаровича.

Дата добавления: 2015-07-11