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

Сентябрь 7, 2022

Главная
Алгебра
Модифицированный симплекс метод

Содержание

2. Он вычисляет и хранит только информацию, необходимую на данный момент, а важные данные передает в более
3. Максимизировать Z = c x, согласно A x ≤ b and x ≥ 0, где c
4. A - матрица Для дополненной формы, вектор-столбец фиктивных переменных: Ограничения : I = (m × m
5. Нахождение базового допустимого решения Общий подход симплекс-метода – получение последовательности улучшающихся ОД решений до тех пор,
6. Исключая эти n переменных приравниванием к нулю, получаем систему уравнений m с m переменными (основными (базисными)
7. И базисная матрица Полученная исключением столбцов, соответствующих коэффициентам небазисных переменных из [A, I]. (В дополнение, элементы
8. cB – вектор, чьи элементы - коэффициенты целевых функций (включая нули для фиктивных переменных) для соответствующих
9. Пример: - Итерация 0 so so
10. - Итерация 1 so so
11. - Итерация 2 so so
12. Матричная форма для текущего множества уравнений Матричная форма для множества уравнений, появляющаяся в симплекс-таблице для любой
14. Эта матрица будет иметь те же элементы, что и единичная матрица, за исключением того, что каждое
15. Так как мы выполняем одни и те же серии алгебраических операций с обеими сторонами исходного множества,
16. Example: матричная форма, полученная после итерации 2 для задачи о стекольном заводе, используя B-1 и cB:
17. Используя величины xB = B-1 b и Z = cB B-1 b:
18. Только B-1 должна быть получена для вычисления всех чисел симплекс-таблицы из исходных параметров задачи (A, b,
20. Скачать презентацию

Слайд 2

Он вычисляет и хранит только информацию, необходимую на данный момент, а

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

Слайд 3

Максимизировать Z = c x,
согласно
A x ≤ b and x ≥

где c вектор-строка

x, b, и 0 векторы-столбцы

Слайд 4

A - матрица
Для дополненной формы, вектор-столбец фиктивных переменных:
Ограничения :
I =

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

Слайд 5

Нахождение базового допустимого решения
Общий подход симплекс-метода – получение последовательности улучшающихся ОД

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

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

Слайд 6

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

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

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

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

Слайд 7

И базисная матрица
Полученная исключением столбцов, соответствующих коэффициентам небазисных переменных из [A,

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

Слайд 8

cB – вектор, чьи элементы - коэффициенты целевых функций (включая нули

для фиктивных переменных) для соответствующих элементов xB. Целевая функция для этого базисного решения:

Слайд 9

Пример:
- Итерация 0
so
so

Слайд 10

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

Слайд 11

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

Слайд 12

Матричная форма для текущего множества уравнений
Матричная форма для множества уравнений, появляющаяся

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

Слайд 13

Слайд 14

Эта матрица будет иметь те же элементы, что и единичная матрица,

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

Слайд 15

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

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

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

Слайд 16

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

заводе, используя B-1 и cB:

Слайд 17

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

Слайд 18

Только B-1 должна быть получена для вычисления всех чисел симплекс-таблицы из

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