🗊Презентация Модифицированный симплекс метод

МОДИФИЦИРОВАННЫЙ СИМПЛЕКС МЕТОД Симплекс-метод – не самая эффективная компьютерная процедура, так как она вычисляет и хранит информацию, которая не нужна для текущей итерации и может вообще не использоваться для принятия решений при последующих итерациях. Для коэффициентов неосновных переменных в уравнении (0), коэффициентов введенных основных переменных в других уравнениях и правых частях уравнений при каждой итерации используется только релевантная информация. Поэтому нужна процедура, которая может получать эту информацию эффективно, без вычислений и хранения всех других коэффициентов (это и есть модифицированный симплекс-метод).

Он вычисляет и хранит только информацию, необходимую на данный момент, а важные данные передает в более компактной форме. Он вычисляет и хранит только информацию, необходимую на данный момент, а важные данные передает в более компактной форме. Он использует операции с матрицами, поэтому необходимо описывать задачу используя матрицы. ЗАГЛАВНЫЕ буквы, выделенные жирным шрифтом представляют матрицы, прописные буквы, выделенные жирным шрифтом представляют векторы. Курсив – это скалярные величины, выделенный ноль (0) обозначает нулевой вектор (его элементы равны нулю, как строки, так и столбцы), ноль (0) представляет обычное число 0. С использованием матриц стандартная форма модели линейного программирования принимает форму:

Нахождение базового допустимого решения Нахождение базового допустимого решения Общий подход симплекс-метода – получение последовательности улучшающихся ОД решений до тех пор, пока не будет найдено оптимальное решение. Одна из ключевых особенностей модифицированного симплекс-метода – то, как он находит новое ОД решение после определения его основных (базисных) и неосновных (небазисных) переменных. Имея эти переменные, получающееся основное решение – решение m уравнений В котором n небазисных переменных из n + m элементов

Исключая эти n переменных приравниванием к нулю, получаем систему уравнений m с m переменными (основными (базисными) переменными): Исключая эти n переменных приравниванием к нулю, получаем систему уравнений m с m переменными (основными (базисными) переменными):

И базисная матрица И базисная матрица

Пример: Пример:

- Итерация 1 - Итерация 1

- Итерация 2 - Итерация 2

Матричная форма для текущего множества уравнений Матричная форма для множества уравнений, появляющаяся в симплекс-таблице для любой итерации исходного симплекс-метода. Для исходной системы уравнений, матричная форма такая: Алгебраические операции, выполняемые симплекс-методом (умножить уравнение на константу и прибавить произведение одного уравнения на другое) выражаются в виде матрицы, предварительно умножив обе части исходной системы уравнений на соответствующие матрицы

Эта матрица будет иметь те же элементы, что и единичная матрица, за исключением того, что каждое произведение для определенной алгебраической операции займет место, необходимое для выполнения этой операции, используя перемножение матриц. Даже после серии алгебраических операций в течение нескольких итераций, мы все еще можем сделать вывод, что эта матрица должна быть для всей серии, используя то, что мы знаем о правой стороны новой системы уравнений. После любой итерации, xB = B-1b и Z = cB B-1b, поэтому правые стороны новой системы уравнений приняли вид Эта матрица будет иметь те же элементы, что и единичная матрица, за исключением того, что каждое произведение для определенной алгебраической операции займет место, необходимое для выполнения этой операции, используя перемножение матриц. Даже после серии алгебраических операций в течение нескольких итераций, мы все еще можем сделать вывод, что эта матрица должна быть для всей серии, используя то, что мы знаем о правой стороны новой системы уравнений. После любой итерации, xB = B-1b и Z = cB B-1b, поэтому правые стороны новой системы уравнений приняли вид

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

Example: матричная форма, полученная после итерации 2 для задачи о стекольном заводе, используя B-1 и cB: Example: матричная форма, полученная после итерации 2 для задачи о стекольном заводе, используя B-1 и cB:

Используя величины xB = B-1 b и Z = cB B-1 b: Используя величины xB = B-1 b и Z = cB B-1 b:

Только B-1 должна быть получена для вычисления всех чисел симплекс-таблицы из исходных параметров задачи (A, b, cB). Любое из этих чисел может быть получено индивидуально, как правило, выполняют только векторное умножение (одна строка на один столбец) вместо полного матричного умножения. Необходимые числа для выполнения итераций симплекс-метода можно получить по мере необходимости, не проводя ненужные вычисления, чтобы получить все числа. Только B-1 должна быть получена для вычисления всех чисел симплекс-таблицы из исходных параметров задачи (A, b, cB). Любое из этих чисел может быть получено индивидуально, как правило, выполняют только векторное умножение (одна строка на один столбец) вместо полного матричного умножения. Необходимые числа для выполнения итераций симплекс-метода можно получить по мере необходимости, не проводя ненужные вычисления, чтобы получить все числа.

Краткий обзор модифицированного симплекс метода 1. Инициализация: Как в исходном симплекс методе. 2. Итерация: Шаг 1 Определить введенные базисные (основные) переменные: Как в исходном симплекс методе. Шаг 2 Определить уходящие базисные переменные: Как в исходном симплекс методе, за исключением подсчета только необходимых для этого чисел [коэффициенты введенных базисных переменных в каждом уравнении за исключением Ур. (0), а затем, для каждого строго положительного коэффициента, правая часть этого уравнения]. Шаг 3 Определить новое ОД решение: Получить B-1 и задать xB=B-1b. 3. Анализ на оптимальность: Как в исходном симплекс методе, за исключением подсчета только необходимых для этого анализа чисел, т.е., коэффициентов небазисных (неосновных) переменных в Уравнении (0). На шаге 3 итерации, B-1 можно получить каждый раз используя стандартную компьютерную программу для обращения (инверсии) матрицы. Так как B (затем B-1) мало изменяется от одной итерации к другой, более эффективно получать новое B-1 (обозначаем B-1 new) из B-1 на предыдущей итерации (B-1 old). (Для исходного ОД решения).