72. Симплексный метод. Признак оптимальности опорного плана. Симплексные таблицы.

Симплексный метод является аналитическим методом. Поиск решения сводится к последовательному перебору угловых точек области допустимых планов. Каждой угловой точке многогранника решений соотв. опорный план. Тогда для нахождения оптим. решения необх. исследовать только угловые точки многогранника решений. Симплексный метод представляет собой алгоритм, позволяющий осуществить упорядоченный переход от одного опорного плана к др., т.е. исходя из известного опорного плана задачи за конечное число шагов получить ее оптим. план. Каждый шаг (итерация) состоит в нахождении нового плана, которому соотв-ет лучшее значение целевой функции, чем на предыдущем шаге. Симпл.метод позволяет исходя из известного опорного плана задачи за конечное число шагов получить ее оптим.план. Каждый шаг состоит в нахождении нового плана, которому соотв-ет лучшее значение ЦФ, чем на предыдущем шаге.

Рассмотрим задачу линейного программирования:

Решим ограничения равенства:

Подставим их значения в целевую функцию.

Введем обозначения: ,

где С_Б – вектор коэффициентов целевой функции базисных переменных,

А_О – вектор свободных членов системы ограничений.

После подстановки в целевую функцию значений базисных переменных: ,

где ,

Признак оптимальности опорного плана:

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

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

Структура симплекс таблицы

73. Симплексный метод. Переход к нехудшему опорному плану. Симплексные преобразования.

Симплексный метод является аналитическим методом. Поиск решения сводится к последовательному перебору угловых точек области допустимых планов. Каждой угловой точке многогранника решений соотв. опорный план. Тогда для нахождения оптим. решения необх. исследовать только угловые точки многогранника решений. Симплексный метод представляет собой алгоритм, позволяющий осуществить упорядоченный переход от одного опорного плана к др., т.е. исходя из известного опорного плана задачи за конечное число шагов получить ее оптим. план. Каждый шаг (итерация) состоит в нахождении нового плана, которому соотв-ет лучшее значение целевой функции, чем на предыдущем шаге. Симпл.метод позволяет исходя из известного опорного плана задачи за конечное число шагов получить ее оптим.план. Каждый шаг состоит в нахождении нового плана, которому соотв-ет лучшее значение ЦФ, чем на предыдущем шаге.

1. В индексной строке симплекс-таблицы найти наибольший положительный элемент, если целевая минимизируется, (или отрицательный, в противном случае). Столбец соответствующий этому элементу – разрешающий.

2. Вычислить отношение свободных членов уравнения к положительным элементам разрешающего столбца. Данное отношение называется симплекс-отношением. Найти наименьшее из симплекс-отношений, оно соответствует разрешающей строке.

3. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент a_iojo. Если имеется несколько одинаковых по величине симплекс-отношений, то выбирают любое из них.

4. Неизвестные элементы, соответствующие разрешающим столбцу и строке, меняются местами.

5. Элементы разрешающей строки новой таблицы будут равны и .

6. Элементы разрешающего столбца равны нулю, за исключением a_i0j0 = 1, т.к. x_jo - базисная переменная.

7. Все остальные элементы находятся по формулам

и .

8. Вычисляем элементы индексной строки

и .

9. Алгоритм продолжается до тех пор, пока не будет достигнуто условие оптимальности:

а) Опорный план x₀ доставляет целевой функции минимальное значение , если для него все оценки свободных переменных неположительны.

б) Опорный план x₀ доставляет целевой функции максимальное значение , если все оценки свободных переменных неотрицательны.