Нахождение базисного решения методом наименьшей стоимости

1. Находится клетка с наименьшей стоимостью перевозки. Туда ставится максимально возможный груз ().

2. Затем находится следующая клетка с наименьшей стоимостью – заполняется аналогично.

Так же как и методе северо-западного угла, если на каком-то этапе одновременно вычеркивается и ПО, и ПН, то ставится 0 – вырожденное решение.

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

20. Определение потенциалов и оценок пустых (незанятых) клеток. Признак оптимальности базисного решения. Признак существования альтернативного решения; вырожденное решение.

Проверка решения на оптимальность может быть выполнена, например, методом потенциалов.

Метод потенциалов требует перехода к двойственной задаче. Потенциалы и являются переменными для двойственной задачи.

Прямая	Двойственная
Каждое - входит в ограничение дважды: для ПО и для ПН.	могут принимать любое значение.

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

Если неравенство для свободных переменных выполняется, то решение оптимальное. Если не выполняется – строить новое решение и проверять на оптимальность его.

Замечания:

1. Число уравнений в системе m+n-1, т.к. столько базисных переменных; Число потенциалов=m+n. Но это не затруднит проверку на оптимальность: один из потенциалов выбираем произвольно (обычно u₁=0), тогда остальные будут найдены однозначно.

2. Даже если какая-то базисная переменная равна 0 (т.е. вырожденное решение), то все равно соответствующее ограничение задается в виде равенства.

3. Произвольный выбор потенциала не влияет на оценки свободных переменных.

4. Если какая-то оценка свободной переменной равна 0, то это признак альтернативного решения.

5. Если среди оценок свободных клеток есть отрицательные, то решение не оптимальное

6. Оценки – полные аналоги оценок симплекс-таблицы, которые стоят в индексной строке.