План чтения лекции по учебной дисциплине «Математические методы» (стр. 2 из 2)
где ¡1, ¡2 – какие-то коэффициенты, ¡0 – свободный член, которого в первоначальном виде у функции L не было; теперь, при переходе к переменным x1, x2, он мог и появится. Однако мы его тут же и отбросим: ведь максимум линейной функции L достигается при тех же значениях x1, x2, что и максимум однородной линейной функции (без свободного члена):
(7.5.)Посмотрим, как изобразить геометрически условие L’Þmax. Положим сначала L’=0, т.е.
и построим на плоскости x1Ox2 прямую с таким уравнением; очевидно, она проходит через начало координат (рис. 7.5.) 
Назовём её «опорной прямой». Если мы будем придавать L’ какие-то значения C1, C2, C3, …, прямая будет перемещаться параллельно самой себе; при перемещении в одну сторону L’ будет возрастать, в другую – убывать. Отметим на рис. 7.5. стрелками, поставленными у опорной рамой, то направление, в котором L’ возрастает. На рис. 7.5. это оказалось направление «направо - вверх», но могло быть и наоборот: всё зависит от коэффициентов g1, g2. теперь изобразим опорную прямую и ОДР на одном чертеже (7.6.). Давайте будем мысленно двигать опорную прямую параллельно самой себе в направлении стрелок (возрастания L’). Когда L’ достигнет максимума? Очевидно, в точке A (крайней точке ОДР в направлении стрелок). В этой точке свободные переменные принимают оптимальные значения x1*,x2*, а из них можно по формулам (7.3.) найти и оптимальные значения всех остальных (базисных) переменных x3*, x4*, …, xn*. Заметим, что максимум L’ достигается в одной из вершин ОДР, где, по крайней мере, две из базисных переменных (в нашем случае это x3 и x5) обращаются в нуль. Могло бы обращаться в нуль и больше базисных переменных, если бы через точку А проходило более двух прямых xi=0.
А может ли оказаться, что оптимального решения не существует? Да, может, если в ОДР функция L’ (а значит и L) не ограничена сверху. Пример такого ненормального случая показан на рис. 7.7. (в разумно поставленных задачах обычно такого недоразумения не возникает).
На рис. 7.6. оптимальное решение существовало и было единственным. А сейчас рассмотрим случай, когда оптимальное решение существует, но не единственно (их бесконечное множество). Это случай, когда максимум L’ достигается не в одной точке А, а на целом отрезке АВ, параллельном опорной прямой (рис. 7.8.).
Итак, мы рассмотрели в геометрической интерпретации случай n-m=k=2 и убедились в следующем: оптимальное решение (если оно существует) всегда достигается в одной из переменныхx1, x2, …, xnравны нулю.
Оказывается, аналогичное правило справедливо и в случае n-m=k>2 (только геометрическая интерпретация теряет в этом случае свою наглядность). Обойдёмся без доказательства, просто сформулируем это правило.
Оптимальное решение ОЗЛП (если оно существует) достигается притакой совокупности значений переменныхx1, x2, …, xn, где, по крайней мере, k из них обращаются в нуль, а остальные неотрицательны.
При k=2 такая совокупность значений изображается точкой на плоскости, лежащей в одной из вершин многоугольника допустимых решений (ОДР). При k=3 ОДР представляет собой уже не многоугольник, а многогранник, и оптимальное решение достигается в одной из его вершин. При k>3 геометрическая интерпретация теряет наглядность, но всё же геометрическая терминология остаётся удобной. Мы будем продолжать говорить о «многограннике допустимых решений» в k-мерном пространстве, а оптимальное решение (если оно существует) будет достигаться водной из вершин этого многогранника, где, по крайней мере, k переменных равны нулю, а остальные – неотрицательны. Будем для краткости называть такую вершину «опорной точкой», а вытекающее из неё решение «опорным решением».
Отсюда вытекает идея, лежащая в основе большинства рабочих методов решения ОЗЛП, - идея «последовательных проб». Действительно, попробуем разрешить уравнения (7.1.) относительно каких–нибудь m базисных переменных и выразим их через остальные kсвободных. Попробуем положить эти свободные переменные равными нулю – авось повезёт, наткнёмся на опорную точку. Вычислим базисные переменные при нулевых значениях свободных. Если все они оказались неотрицательными, значит, нам повезло, мы сразу же получим допустимое (опорное) решение, и его остаётся только оптимизировать. А если нет? Значит, данный выбор свободных и базисных переменных допустимого решения не даёт; точка лежит не на границе, а вне ОДР. Что делать? Надо «пере разрешить» уравнения относительно каких-то других базисных переменных, но не как попало, а так, чтобы это приближало нас к области допустимых решений (для этого в линейном программировании существуют специальные приёмы, на которых мы останавливаться не будем). Пусть, наконец, несколько раз повторив такую процедуру, мы нашли опорное решение ОЗЛП. Но это ещё не всё. Тут надо поставить вопрос: а является ли это решение оптимальным? Выразим функцию L через последние получившиеся свободные переменные и попробуем увеличить их сверх нуля. Если от этого значения L только уменьшается, значит, нам повезло, и мы нашли оптимальное решение, ОЗЛП решена. А если нет? Снова «пере разрешаем» систему уравнений относительно других базисных переменных, и снова не как попало, а так чтобы, не выходя за пределы допустимых решений, приблизиться к оптимальному. И опять- таки для этого в линейном программировании существуют специальные приёмы, гарантирующие, что при каждом новом «пере разрешении» мы будем приближаться к оптимальному решению, а не удаляться от него. На этих приёмах мы тоже здесь не будем останавливаться. После конечного числа таких шагов цель будет достигнута – оптимальное решение найдено. А если его не существует? Алгоритм решения ОЗЛП сам покажет вам, что решения нет.
Для простых задач, где число переменных невелико, такой «слепой перебор» может привести к решению, и довольно быстро. Но на практике часто встречаются задачи, в которых число переменных (и наложенных условий) очень велико, порядка сотен и даже тысяч. Для таких задач простой перебор становится практически невозможным: слишком велико число комбинаций свободных и базисных переменных. Пример: только при n=30 и m=10 число возможных комбинаций свободных переменных с базисными равно,
т.е. свыше 30 миллионов! А эта задача – далеко не из сложных.Разработанные в теории линейного программирования вычислительные методы («симплекс-метод», «двойственный симплекс-метод» и другие) позволяют находить оптимальное решение не «слепым» перебором, а «целенаправленным», с постоянным приближением к решению. Добавим, что совместимые ЭВМ, как правило, снабжены подпрограммами для решения задач линейного программирования, так что лицу, желающему их решить, нет даже особой надобности обучаться решению таких задач «вручную» - труд крайне неприятный и изнурительный.