Материал: 5021

Кроме того, задана матрица тарифов:

Поэтому вводим фиктивного потребителя с потребностью в 20 единиц груза и нулевыми тарифами.

Составляем таблицу и первоначальное распределение поставок производим по методу «северо-западного» угла:

Число занятых клеток должно быть равно 3+5–1=7, у нас получилось 6. Это получилось потому, что при заполнении клетки (1,2) мы одновременно вычеркнули первую строку и второй столбец. Надо занести нулевую поставку в одну из клеток, расположенных рядом по строке или столбцу то клетки (1,2), т.е. или в (1,3), или в (2,2). Займем клетку (1,3). При таком расположении поставок затраты на перевозку груза составят:

Вычислим потенциалы Ui , i 1,...,3 , Vj , j 1,...,5исходя из того, что для занятых клеток должно выполняться равенство Ui Vj cij . Полагаем, что один из потенциалов равен нулю, например U1 0 .

Далее вычислим характеристики для свободных клеток: Eij cij Ui Vj . Отрицательные характеристики заносятся в левый нижний угол клетки.

Выбираем клетку с наименьшей отрицательной характеристикой, т.е. (2,2). Строим контур с вершиной в этой клетке. Свободную клетку помечаем знаком «+», следующую по контуру – знаком «–» и т.д., меняя знаки. В свободную клетку заносится минимальная поставка из клеток, помеченных знаком «–». В нашем случае обе поставки равны 20 единицам. Поэтому мы вычитаем 20 единиц груза из поставок, стоящих в «отрицательных клетках» и прибавляем 20 единиц груза к поставкам, стоящим в « положительных клетках». Так как в «отрицательных клетках» было по 20 единиц груза, то после перераспределения поставок, в одну из них запишем нулевую поставку, а другую оставим пустой. Получим следующее (лучшее) распределение:

При таком распределении поставка в 20 ед. попала в клетку с характеристикой равной –4, следовательно функция затрат улучшилась на

Продолжая вышеописанный процесс нахождения потенциалов, характеристик для пустых клеток и построение контура, приходим к следующему распределению:

Найдя для этого распределения характеристики незанятых клеток, видим, что среди них нет отрицательных характеристик, и, следовательно, мы нашли оптимальное решение, при котором функция затрат на перевозку груза достигла своего минимального значения:

120 2 10 120 150 110 .

Чтобы оптимальный план получить за меньшее число итераций, надо первоначальное распределение поставок проводить по методу «наименьшего тарифа», т.е. сначала заполнить клетки соответствующие минимальным тарифам.

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