Расстановка потенциалов и перераспределение поставок
Операция 2.2. Проверка небазисных клеток на соответствие их условию оптимальности. Оптимальный план транспортной задачи должен отвечать критерию оптимальности, который выражается в том, соответствуют ли небазисные клетки матрицы условию, формулируемому следующим выражением:
Если это условие для всех небазисных клеток выполняется, то план является оптимальным, а если нет, хотя бы для одной клетки, то план не оптимален. Иначе говоря, существует некоторый план с меньшим функционалом. Разность потенциалов может интерпретироваться как некоторая условная цена перевозки единицы продукции по маршруту, связывающему соответствующие станции «i» и «j». Если она ниже cij, значит, использование данного маршрута не улучшит план, а если cij ниже разности потенциалов, т. е. условие (2.8) не выполняется, следовательно, существует план лучше рассчитанного, который необходимо отыскать. Проверим условие (2.8) для табл. 2.6. Клетка А1В1: 4 – 5 < 10, условие выполняется. Клетка А1В2: 7 – 5 < 9, условие выполняется и т. д. Если для всех небазисных клеток условие 3 выполняется, то рассматриваемый план будет оптимален. Дальнейшие действия переходят по алгоритму к операции 4. Однако для нашего примера это не так. Не выполняется условие для клетки А2В4 (10 – 0> 6), клетки А3В3 (13 – 1 > 9), а также для клеток А3В4, А4В3, из чего следует, что разработанный опорный план не оптимален. Отметим эти клетки. Операция 3. Улучшение плана. Поскольку полученный план не оптимален, дальнейшие действия алгоритма состоят в его преобразовании в лучшую сторону или просто улучшения.
|
. (2.8)
