Исследование операций. Линейное, динамическое программирование



Исследование операций - часть 56


Пусть, наконец, несколько раз повторив такую процедуру, мы нашли опорное решение ОЗЛП. Браво! Но это еще не все. Тут надо поставить вопрос: а является ли это решение оптимальным? Выразим функцию L

через последние получившиеся свободные переменные и попробуем увеличивать их сверх нуля. Если от этого значение L

только уменьшается, значит, нам повезло, и мы нашли оптимальное решение, ОЗЛП решена. А если нет? Снова «пере разрешаем» систему уравнений относительно других базисных переменных, и снова не как попало, а так, чтобы, не выходя за пределы допустимых решений, приблизиться к оптимальному. И опять-таки для этого в линейном программировании существуют специальные приемы, гарантирующие, что при каждом новом «пере разрешении» мы будем приближаться к оптимальному решению, а не удаляться от него. На этих приемах мы тоже здесь не будем останавливаться. После конечного числа таких шагов цель будет достигнута — оптимальное решение найдено. А если его не существует? Алгоритм решения ОЗЛП сам покажет вам, что решения нет.

Читатель, может быть, спросит: только-то и всего? Зачем было придумывать хитрые методы решения ОЗЛП, может быть, надо просто перебрать, одну за другой, все возможные комбинации k свободных переменных, полагая их равными нулю, пока, наконец, не будет найдено оптимальное решение?

Действительно, для простых задач, где число переменных невелико, такой «слепой перебор» может привести к решению, и довольно быстро. Но на практике часто встречаются задачи, в которых число переменных (и наложенных условий) очень велико, порядка сотен и даже тысяч. Для таких задач простой перебор становится практически невозможным: слишком велико число комбинаций свободных и базисных переменных. Пример: только при п = 30 и m = 10 число возможных комбинаций свободных переменных с базисными равно

 = 30045015, т. е. свыше 30 миллионов! А эта задача — далеко не из сложных.

Разработанные в теории линейного программирования вычислительные методы («симплекс-метод», «двойственный симплекс-метод» и другие, см. [4,6,8]) позволяют находить оптимальное решение не «слепым» перебором, а «целенаправленным», с постоянным приближением к решению.


Содержание  Назад  Вперед