- •Глава 4. Линейное программирование
- •4.1. Постановка задачи
- •В общем случае модель задачи лп имеет вид
- •4.2. Примеры задач линейного программирования
- •Задача составления рациона или как экономно питаться
- •4.2.2. Задача оптимального планирования
- •4.2.3. Сбалансированная транспортная задача
- •4.2.4. Общая распределительная задача
- •4.2.5. Задача планирования работы оборудования
- •4.2.6. Игра двух лиц с нулевой суммой как задача линейного программирования
- •4.2.7. Резюме
- •4.3. Формы записи задач линейного программирования и способы приведения к ним
- •4.3.1. Каноническая форма задач лп
- •4.3.2. Стандартная форма задачи лп
- •4.4. Упрощение модели
- •4.5. Основные понятия лп. Свойства задач лп
- •4.6. Геометрия задач лп
- •4.7. Выделение вершин допустимого множества
- •4.8. Методы решения задач лп
- •4.9. Симплекс-метод
- •4.9.1. Харатеристика метода
- •4.9.2. Переход от одного базисного решения к другому
- •4.9.3. Признак оптимальности. Основные этапы симплекс-метода
- •4.9.4. Построение начального базисного решения
- •4.9.5. Связь между параметрами последовательных итераций
- •4.9.6. Алгоритм симплекс-метода
- •4.9.7. Примеры
- •4.9.8. Учет двусторонних ограничений
- •4.10. Модифицированный алгоритм
- •4.11. Двойственность задач лп
- •4.11.1. Запись двойственной задачи в симметричном случае
- •4.11.2. Интерпретация двойственной задачи
- •4.11.3. Запись двойственной задачи в общем случае
- •4.11.4. Теоремы двойственности
- •4.11.5. Двойственный симплекс-метод
- •4.12. Параметрический анализ
- •4.12.1. Параметрирование вектора ограничениий
- •4.12.2. Параметрирование коэффициентов линейной формы
- •4.13. Задания для самостоятельной работы
4.8. Методы решения задач лп
Методы линейного программирования - численные методы решения оптимизационных задач, cводящихся к формальным моделям линейного программирования.
Существуют конечные и итеративные методы решения задач ЛП.
Итеративный методсходится к точному решению асимптотически на бесконечном числе итераций, а при конечном дает приближенное решение.
Конечные методыпозволяют получить точное решение за конечное число шагов. Они делятся на
универсальные, применимые для любых задач ЛП;
специальные, предназначенные для решения определенных классов задач ЛП.
Последние учитывают специфику класса и поэтому более эффективны, чем универсальные.
Итеративные методы интересны теоретически, а на практике находят применение конечные методы. Начало развитию методов линейного программирования было положено в работах Канторовича Л.В. в конце тридцатых годов 20 века. Позднее был разработан целый ряд эффективных методов, первым из которых стал симплекс-метод.
4.9. Симплекс-метод
4.9.1. Харатеристика метода
Данный метод является основополагающим среди универсальных методов. Он разработан Данцигом в 1947 году. В одной из первых задач, решенных этим методом, допустимое множество представляло собой симплекс – выпуклый многогранник, у которого число вершин на единицу больше размерности пространства. Отсюда и произошло название метода. В некоторых отечественных монографиях (авторы Гольштейн Е.Г., Юдин Д.Б. и др.) его называют методом последовательного улучшения плана.
Симплекс-метод реализует направленный перебор допустимых базисных решений в виде итеративного процесса. На каждой итерации осуществляется переход по ребру допустимого множества от одной вершины (крайней точки) к другой, смежной исходной, в которой значение критерия лучше или, в редких случаях, не хуже, чем в исходной. Поскольку число крайних точек конечно, а целевая функция линейна, то такой процесс сходится за конечное число шагов к глобальному оптимуму (для разрешимой задачи).
В результате симплекс метод позволяет отыскать оптимальное решение, просматривая значительно меньше вершин по сравнению с их общим числом. Строгих оценок достаточного числа итераций для достижения оптимального решения нет. Однако экспериментально установлено, что реальное число итераций находится в пределах m 3 m, а наиболее вероятно (1,52) m. Так, для вышерассмотренного примера вместо десятков тысяч вершин метод “пройдет” не более 30.
В симплекс-методе можно выделить три основные компоненты:
Способ построения начального базисного решения.
Процедуру перехода от одного базисного решения к другому.
Признак оптимальности.
Неразрешимость задачи определяется по ходу работы алгоритма.
4.9.2. Переход от одного базисного решения к другому
Здесь нам понадобятся некоторые понятия линейной алгебры..
Векторы А1, А2, …, АS являются линейно-независимыми, если равенство k1A1+k2A2+…+kSAS=0 выполняется только приk1=k2=…=kS=0. Признаком линейной независимости векторов является ненулевое значение определителя, составленного из этих векторов, так как однородная система имеет единственное (нулевое) решение только при таком определителе.
Если есть система линейно-независимых векторов, то любой другой вектор может быть выражен в виде их линейной комбинации и притом единственным образом:
Ap=1A1+2A2+…+SAS, p[1, S].
В канонической форме условия записываются в виде
(4.4)
Пусть система (4.4) имеет базисное решение:
(4.5)
Тогда из (4.4) следует
(4.6)
Так как система (4.6) совместна, то ее определитель не равен нулю и, значит, векторы, входящие в (4.6), являются линейно-независимыми. Для их обозначения введем следующее понятие: система m линейно-независимых векторов, соответствующих базисным переменным, называетсябазисом. Таким образом, каждой экстремальной точке соответствует своё базисное решение и свой базис.
Теперь, имея исходные базисное решение (4.5) и базис , построим новое базисное решение. Как следует из геометрических представлений, смежные вершины отличаются по составу базисных переменных только одной. Поэтому новое решение можно получить вводом в исходное небазисной переменной с одновременным переводом одной базисной переменной в небазисные.
Пусть вводимой будет переменная с индексом r[1,m], принимающая в новом решении некоторое положительное значение
В новом решении, как в любом допустимом, условия (4.4) также должны выполняться, поэтому имеем:
(4.7)
Задача состоит в том, чтобы определить X(1) по X(0). С этой целью сделаем несложные преобразования. Выразим вектор Ar через исходный базис:
Ar=A11r+A22r+…+Ammr. (4.8)
Так как известен базис, то известны (или находятся решением этой ситстемы) коэффициенты разложения ir. Умножим левую и правую части равенства (4.8) на :
Ar=A11r+A22r+…+Ammr . (4.9)
Вычитая (4.9) из (4.6), получим:
или окончательно:
(4.10)
Сравнивая равенства (4.7) и (4.10), видим, что правые части равны, а левые содержат одну и ту же ситстему векторов. Поэтому коэффициенты при одноименных векторах должны совпадать. Приравнивая их, получаем искомые соотношения:
(4.11)
Однако решение (4.11) может быть недопустимым, если не оговорить возможные значения . Предположим, что среди коэффициентовirесть положительные. Тогда с увеличением значения соответствующие переменные могут стать отрицательными. Поэтому для допустимости решенияX(1) необходимо, чтобы было ограничено сверху:
(4.12)
С учетом (4.12) решение (4.11) всегда будет допустимым, но число ненулевых переменных в нем может превышатьm, так как добавлена xr, а значит, оно может быть небазисным. Если же в качестве значения выбрать0, то одна из переменных станет равной нулю, а решение (4.11) базисным.
Пусть минимум в (4.12) достигается на переменной xk. Тогда базисные переменные в новом опорном решении будут вычисляться по формулам:
(4.13)
Этому решению соответствует новый базис {Ai}(1)={A1,…,Ak-1,Ar, Ak+1,…,Am}. Таким образом, переход к новому базисному решению произошел путем замены переменнойXk на Xr, соответсвенно в базисе Ak на Ar.
Рассмотрим возможные ситуации при переходе от одного решения к другому. Как было показано выше, при существовании положительных коэффициентов ir достигается новое базисное решение (смежная вершина), что иллюстрируется рис. 4.6-а. Если же все ir неположительны, величина , а это значение вводимой переменной, не ограничена сверху. Следовательно, введение такой переменной не приведет к получению базисного решения (достижению новой вершины). Это признак того, что соответствующее ребро допустимого множества, а значит, и само множество оказываются неогранниченными (рис. 4.6-б).
При вычислении 0минимум может достигаться более чем на одном индексе. При этом обнуляется более одной переменной из входящих в исходное решение. Следовательно, в новом решении будут базисные переменные с нулевым значением, что означает попадание ввырожденное базисноерешение.
Если исходное решение вырожденное и нулевой переменной соответствует коэффициет kr>0, то согласно (4.12) 0=0 и значения переменных не изменяются. Однако состав базиса и базисных переменных изменится произойдет замена наПри высокой степени вырожденности теоретически возможно зацикливание, то есть возврат к старому базису, но на практике такие случаи не встречались.