Симплексная таблица и ее преобразование (алгоритм симплекс-метода)

Сентябрь 13, 2022

Главная
Математика
Симплексная таблица и ее преобразование (алгоритм симплекс-метода)

Содержание

2. Будем считать, что в приведенной форме (2) базисные вектора расположены первыми по порядку, т.е. В качестве
3. БДП известен изначально. Его координаты: Форма симплексной таблицы
4. cσ – коэффициенты целевой функции при базисных переменных; А1, А2, …, Аn – векторы-столбцы решаемой задачи;
5. Значение целевой функции на этом плане вычисляется по формуле: Двойственные оценки Δj вычисляются по формуле: Переход
6. Правило 2. Определение номера вектора, выводимого из базиса. Необходимо определить номер r выводимого из базиса вектора
7. Опр. Элемент вводимого в базис, и вектора, выводимого из базиса, называется ведущим (или разрешающим) элементом симплексной
8. Фрагмент симплексной таблицы
9. δik - символ Кронекера (6) Формулы пересчета элементов симплекс-таблицы при переходе к новому базису:
10. Координаты нового плана вычисляются по формулам: (7) Новые двойственные оценки: (8)
11. Значение целевой функции на новом плане равно (9) Теорема. Для нового базисного допустимого плана имеет место
12. П р и м е р . Приведем ЗЛП к каноническому виду путем введения дополнительных переменных:
13. Начальный БДП х0 = (0; 0; 3; 5) Решение ЗЛП
15. Скачать презентацию

Слайд 2

Будем считать, что в приведенной форме (2) базисные вектора расположены первыми

по порядку, т.е.

В качестве исходного базиса необходимо выбирать единичный базис, так как в этом случае все вектора

.

Координаты вектора Аj совпадают с координатами его разложения по базису:

Слайд 3

БДП
известен изначально.
Его координаты:
Форма симплексной таблицы

Слайд 4

cσ – коэффициенты целевой функции при базисных переменных;
А1,

А2, …, Аn – векторы-столбцы решаемой задачи;
c1, с2, …, cn – коэффициенты целевой функции;
C(x) – значение целевой функции на плане x;
Δj – двойственные оценки.

Из симплексной таблицы легко выписывается БДП:

=

(x10, x20,…, xm0, 0, 0,…,0)

Слайд 5

Значение целевой функции на этом плане вычисляется по формуле:
Двойственные оценки

Δj вычисляются по формуле:

Переход к новому БДП осуществляется при помощи двух правил.
Правило 1. Определение номера вектора, вводимого в базис.

(3)

Слайд 6

Правило 2. Определение номера вектора, выводимого из базиса.
Необходимо определить номер

r выводимого из базиса вектора Ar , r∈σ. Новый носитель плана будет выглядеть так: σнов = σ ∪ {k} \ {r}.

(4)

(предполагаем, что минимум достигается при i=r) .

Номер выводимого вектора определяется с помощью симплекс-таблицы:

(5)

Слайд 7

Опр. Элемент
вводимого в базис, и вектора, выводимого из базиса, называется

ведущим (или разрешающим) элементом симплексной таблицы.

, стоящий на пересечении вектора,

Слайд 8

Фрагмент симплексной таблицы

Слайд 9

δik - символ Кронекера
(6)
Формулы пересчета элементов симплекс-таблицы при переходе к

новому базису:

Слайд 10

Координаты нового плана вычисляются по формулам:
(7)
Новые двойственные оценки:
(8)

Слайд 11

Значение целевой функции на новом плане равно
(9)
Теорема.
Для нового

базисного допустимого плана имеет место неравенство С(хнов) ≥ С(х0), т.е. полученный путем преобразований план не хуже, чем план, имеющийся на предыдущей итерации.

Слайд 12

П р и м е р .
Приведем ЗЛП к

каноническому виду путем введения дополнительных переменных:

Слайд 13

Начальный БДП х0 = (0; 0; 3; 5)
Решение ЗЛП