Презентация на тему МОДИФИЦИРОВАННЫЙ СИМПЛЕКС МЕТОД

данный момент, а важные данные передает в более компактной

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

and x ≥ 0,
где c вектор-строка
x, b, и 0

векторы-столбцы

:

I = (m × m единичная матрица)
0 = (n + m элементы нулевого вектора)

последовательности улучшающихся ОД решений до тех пор, пока не

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

В котором n небазисных переменных из n + m элементов

устанавливаются равными нулю.

систему уравнений m с m переменными (основными (базисными) переменными):

где вектор базисных переменных:

получен исключением небазисных (неосновных) переменных:

переменных из [A, I].
(В дополнение, элементы xB, и

столбцы B в разном порядке). Симплекс метод вводит только базисные переменные, такие что B - невырожденная, так что обратная матрица B-1 всегда будет существовать.
Чтобы решить B x B = b, обе стороны умножаются на B-1 :
B-1 B x B = B-1 b.

функций (включая нули для фиктивных переменных) для соответствующих элементов

xB. Целевая функция для этого базисного решения:

множества уравнений, появляющаяся в симплекс-таблице для любой итерации исходного

симплекс-метода. Для исходной системы уравнений, матричная форма такая:




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

и единичная матрица, за исключением того, что каждое произведение

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

серии алгебраических операций с обеими сторонами исходного множества, для

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

Желаемая матричная форма системы уравнений после любой итерации:

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

= cB B-1 b:

чисел симплекс-таблицы из исходных параметров задачи (A, b, cB).

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