Двойственный симплекс-метод

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

Поэтому цикл начинается с анализа базисных переменных. Если все переменные неотрицательны, вычисления завершаются. Иначе выбирается направляющая строка k по минимальной базисной переменной. Затем вычисляются значения q: для < 0.(40)

Если в прямом методе формула следует из требования получения нового неотрицательного решения, то здесь – из необходимости соблюсти в новом решении условия оптимальности. При отсутствии в направляющей строке отрицательных akj констатируется неразрешимость задачи из-за противоречивости условий. Действительно, равенство с отрицательной правой частью и всеми неотрицательными коэффициентами при переменных в левой части не может быть удовлетворено неотрицателными переменными. Направляющий столбец r определяется по минимальному q. Далее текущая симплекс-таблица пересчитывается так же, как в прямом методе. В результате получается новое базисное решение, в котором, по крайней мере, xk станет неотрицательной.

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

9. Декомпозиция задач планирования большой размерности.

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