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

Реклама. Продолжение ниже
Симплексная таблица и ее преобразование (алгоритм симплекс-метода) ( 1 ) Пусть
Симплексная таблица и ее преобразование (алгоритм симплекс-метода) ( 1 ) Пусть
Симплексная таблица и ее преобразование (алгоритм симплекс-метода) ( 1 ) Пусть
Симплексная таблица и ее преобразование (алгоритм симплекс-метода) ( 1 ) Пусть
Симплексная таблица и ее преобразование (алгоритм симплекс-метода) ( 1 ) Пусть
Симплексная таблица и ее преобразование (алгоритм симплекс-метода) ( 1 ) Пусть
Симплексная таблица и ее преобразование (алгоритм симплекс-метода) ( 1 ) Пусть
Симплексная таблица и ее преобразование (алгоритм симплекс-метода) ( 1 ) Пусть
Симплексная таблица и ее преобразование (алгоритм симплекс-метода) ( 1 ) Пусть
Симплексная таблица и ее преобразование (алгоритм симплекс-метода) ( 1 ) Пусть
Симплексная таблица и ее преобразование (алгоритм симплекс-метода) ( 1 ) Пусть
Симплексная таблица и ее преобразование (алгоритм симплекс-метода) ( 1 ) Пусть
Симплексная таблица и ее преобразование (алгоритм симплекс-метода) ( 1 ) Пусть
Симплексная таблица и ее преобразование (алгоритм симплекс-метода) ( 1 ) Пусть
1/14
Средняя оценка: 4.8/5 (всего оценок: 25)
Код скопирован в буфер обмена
Скачать (136 Кб)
Реклама. Продолжение ниже
1

Первый слайд презентации

Симплексная таблица и ее преобразование (алгоритм симплекс-метода) ( 1 ) Пусть система ограничений Ax = b преобразована в приведенную форму: ( 2 ) x i 0  0, i 

Изображение слайда
1/1
2

Слайд 2

Будем считать, что в приведенной форме ( 2 ) базисные вектора расположены первыми по порядку, т.е. В качестве исходного базиса необходимо выбирать единичный базис, так как в этом случае все вектора . Координаты вектора А j совпадают с координатами его разложения по базису:

Изображение слайда
1/1
3

Слайд 3

БДП известен изначально. Его координаты: Форма симплексной таблицы c  Базис A 0 = b c 1 … c m … c k … c n A 1 … A m … A k … A n c 1 A 1 x 10 1 … 0 … … c 2 A 2 x 20 0 … 0 … … … … … … … … … … … … c m A m x m 0 0 … 1 … … C(x)/  j C( x 0 ) 0 … 0 …  k …  n

Изображение слайда
1/1
4

Слайд 4

c σ – коэффициенты целевой функции при базисных переменных; А 1, А 2, …, А n – векторы-столбцы решаемой задачи; c 1, с 2, …, c n – коэффициенты целевой функции; C ( x ) – значение целевой функции на плане x ;  j – двойственные оценки. Из симплексной таблицы легко выписывается БДП: = ( x 10, x 20,…, x m0, 0, 0,…,0 )

Изображение слайда
1/1
5

Слайд 5

Значение целевой функции на этом плане вычисляется по формуле: Двойственные оценки  j вычисляются по формуле: Переход к новому БДП осуществляется при помощи двух правил. Правило 1. Определение номера вектора, вводимого в базис. ( 3 )

Изображение слайда
1/1
6

Слайд 6

Правило 2. Определение номера вектора, выводимого из базиса. Необходимо определить номер r выводимого из базиса вектора A r, r . Новый носитель плана будет выглядеть так:  нов =    k  \  r . ( 4 ) ( предполагаем, что минимум достигается при i = r ). Номер выводимого вектора определяется с помощью симплекс-таблицы: (5)

Изображение слайда
1/1
7

Слайд 7

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

Изображение слайда
1/1
Реклама. Продолжение ниже
8

Слайд 8

Фрагмент симплексной таблицы c  базис A 0 = b … с j … с k … A j … A k … … … … … … … с i A i x i 0 … … … … … … … … … с r A r x r 0 … … … … … … … … … C(х)/  j C ( х )  j  k

Изображение слайда
1/1
9

Слайд 9

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

Изображение слайда
1/1
10

Слайд 10

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

Изображение слайда
1/1
11

Слайд 11

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

Изображение слайда
1/1
12

Слайд 12

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

Изображение слайда
1/1
13

Слайд 13

Начальный БДП х 0 = (0; 0; 3; 5) Решение ЗЛП с  базис A 0 =b 1 2 0 0 A 1 A 2 A 3 A 4 0 A 3 3 1 1  1 0 0  A 4 5 1 3 0 1 C(х)/  j 0 -1 -2 * 0 0 0  A 3 4/3 2/3  0 1 -1/3 2 A 2 5/3 1/3 1 0 1/3 C(х)/  j 10/3 -1/3 * 0 0 2/3 1 A 1 2 1 0 3/2 -1/2 2 A 2 1 0 1 -1/2 1/2 C(х)/  j 4 0 0 1/2 1/2

Изображение слайда
1/1
14

Последний слайд презентации: Симплексная таблица и ее преобразование (алгоритм симплекс-метода) ( 1 ) Пусть

Выполнив преобразования симплекс-таблицы, получаем оптимальный план х опт = (2; 1; 0; 0) и значение целевой функции на этом плане С ( х опт ) = 4.

Изображение слайда
1/1
Реклама. Продолжение ниже
Реклама. Продолжение ниже