Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
03 Матпрограммирование - презентации / МП Лекция 3-Симплекс-метод.pptx
Скачиваний:
55
Добавлен:
15.03.2016
Размер:
903.83 Кб
Скачать

Симплекс–метод

1

Оптимальное решение ЗЛП графическим методом всегда ассоциируется с угловой точкой пространства решений. Это является ключевой идеей алгебраического

симплекс-метода для решения любой задачи линейного программирования.

2

Переход от геометрического способа решения ЗЛП к симплекс-методу лежит через алгебраическое описание крайних точек пространства решений.

Для реализации этого перехода сначала надо привести задачу ЛП к

стандартной форме, преобразовав неравенства ограничений в равенства путем введения дополнительных переменных.

3

Основное свойство симплекс-метода заключается в том, что решение задачи ЛП осуществляется итерационно. На каждой итерации алгоритм переходит к новой угловой точке, которая потенциально может улучшить значение целевой функции. Этот процесс перехода от одной угловой точки к следующей заканчивается, когда дальнейшее улучшение значений целевой функции

невозможно.

4

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

5

Стандартная форма записи ЗЛП предполагает выполнение следующих требований:

1.Все ограничения (включая ограничения неотрицательности переменных) преобразуются в равенства с неотрицательной правой частью.

2.Все переменные неотрицательные.

6

Неравенства любого типа (со знаками неравенств или ) можно преобразовать в равенства путем добавления в левую часть неравенств дополнительных переменных — остаточных или избыточных, которые связаны с неравенствами типа «» и «» соответственно.

7

Для неравенств типа «» в левую часть неравенства вводится неотрицательная остаточная переменная.

Неравенства типа «» в ЗЛП обычно устанавливают нижнюю границу. Избыточная переменная определяет превышение значения левой части неравенства над этой границей.

Часто условие неотрицательности переменных является естественным. Но, конечно, возможны ситуации, когда переменные могут принимать любые действительные значения.

8

Идеи, лежащие в основе графического метода решения ЗЛП, также являются основой и алгебраического симплекс-метода. Ниже показаны параллели между этими двумя методами.

Вграфическом методе пространство решений определяется как пересечение полупространств, порождаемых ограничениями.

Всимплекс-методе пространство решений

задают система из m линейных уравнений и n неотрицательных переменных.

9