- •Симплекс–метод
- •Оптимальное решение ЗЛП графическим методом всегда ассоциируется с угловой точкой пространства решений. Это
- •Переход от геометрического способа решения ЗЛП к симплекс-методу лежит через алгебраическое описание крайних
- •Основное свойство симплекс-метода заключается в том, что решение задачи ЛП осуществляется итерационно. На
- •Процесс реализации симплекс-метода включает большое количество однотипных громоздких и утомительных вычислений. Это делает
- •Стандартная форма записи ЗЛП предполагает выполнение следующих требований:
- •Неравенства любого типа (со знаками неравенств или ) можно преобразовать в равенства путем
- •Для неравенств типа «» в левую часть неравенства вводится неотрицательная остаточная переменная.
- •Идеи, лежащие в основе графического метода решения ЗЛП, также являются основой и алгебраического
- •Мы можем увидеть пространство решений графического метода, имеющее бесконечное число точек решений, но
- •После преобразования к стандартной форме имеем следующую ЗЛП.
- •В нашем примере имеем угловых точек. Но, глядя на рисунок
- •В действительности точки Е и F также являются угловыми точками, но это недопустимые
- •Для полного перехода к алгебраическому методу решения задач ЛП необходимо как-то назвать угловые
- •В таблице перечислены все базисные и небазисные решения текущего примера.
- •Как видно из примера, при возрастании размерности задачи процесс перечисления всех угловых точек
Симплекс–метод
1
Оптимальное решение ЗЛП графическим методом всегда ассоциируется с угловой точкой пространства решений. Это является ключевой идеей алгебраического
симплекс-метода для решения любой задачи линейного программирования.
2
Переход от геометрического способа решения ЗЛП к симплекс-методу лежит через алгебраическое описание крайних точек пространства решений.
Для реализации этого перехода сначала надо привести задачу ЛП к
стандартной форме, преобразовав неравенства ограничений в равенства путем введения дополнительных переменных.
3
Основное свойство симплекс-метода заключается в том, что решение задачи ЛП осуществляется итерационно. На каждой итерации алгоритм переходит к новой угловой точке, которая потенциально может улучшить значение целевой функции. Этот процесс перехода от одной угловой точки к следующей заканчивается, когда дальнейшее улучшение значений целевой функции
невозможно.
4
Процесс реализации симплекс-метода включает большое количество однотипных громоздких и утомительных вычислений. Это делает компьютер незаменимым инструментом для решения ЗЛП, поскольку вычислительный алгоритм симплекс-метода позволяет сравнительно легко автоматизировать вычисления.
5
Стандартная форма записи ЗЛП предполагает выполнение следующих требований:
1.Все ограничения (включая ограничения неотрицательности переменных) преобразуются в равенства с неотрицательной правой частью.
2.Все переменные неотрицательные.
6
Неравенства любого типа (со знаками неравенств или ) можно преобразовать в равенства путем добавления в левую часть неравенств дополнительных переменных — остаточных или избыточных, которые связаны с неравенствами типа «» и «» соответственно.
7
Для неравенств типа «» в левую часть неравенства вводится неотрицательная остаточная переменная.
Неравенства типа «» в ЗЛП обычно устанавливают нижнюю границу. Избыточная переменная определяет превышение значения левой части неравенства над этой границей.
Часто условие неотрицательности переменных является естественным. Но, конечно, возможны ситуации, когда переменные могут принимать любые действительные значения.
8
Идеи, лежащие в основе графического метода решения ЗЛП, также являются основой и алгебраического симплекс-метода. Ниже показаны параллели между этими двумя методами.
Вграфическом методе пространство решений определяется как пересечение полупространств, порождаемых ограничениями.
Всимплекс-методе пространство решений
задают система из m линейных уравнений и n неотрицательных переменных.
9