 |
Главная |
Симплексные преобразования
 2020-02-04 |
 229 |
 Обсуждений (0) |
из
5.00
|
Правила симплексного преобразования:
1) В индексной строке симплекс-таблицы найти наибольший положительный элемент, если целевая максимизируется, (или отрицательный, в противном случае). Столбец соответствующий этому элементу – разрешающий.
2) Вычислить отношение свободных членов уравнения к положительным элементам разрешающего столбца. Данное отношение называется симплекс-отношением. Найти наименьшее из симплекс-отношений, оно соответствует разрешающей строке.
3) На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент 
. Если имеется несколько одинаковых по величине симплекс-отношений, то выбирают любое из них.
4) Неизвестные элементы, соответствующие разрешающим столбцу и строке, меняются местами.
5) Переход к следующей таблице. Элементы разрешающей строки новой таблицы будут равны 
и 
.
6) Элементы разрешающего столбца равны нулю, за исключением 
.
7) Все остальные элементы находятся по формулам
и 
.
8) Алгоритм продолжается до тех пор, пока не будет достигнуто условие оптимальности:
а) Опорный план 
доставляет целевой функции минимальное значение 
, если для него все оценки свободных переменных неотрицательны.
б) Опорный план доставляет целевой функции максимальное значение 
, если все оценки свободных переменных внеположительны.
4.4 Симплекс-таблица
Решим разобранную выше задачу с помощью симплекс-таблицы.
|
| х1 | х2 | х3 | х4 | х5 | х6 | в | оо |
| х3 | 1 | 3 | 1 | 0 | 0 | 0 | 18 | 6 |
| х4 | 2 | 1 | 0 | 1 | 0 | 0 | 16 | 16 |
| х5 | 0 | 1 | 0 | 0 | 1 | 0 | 5 | 5 |
| х6 | 3 | 0 | 0 | 0 | 0 | 1 | 21 | - |
| Z | 2 | 3 | 0 | 0 | 0 | 0 |
|
|
Получим вторую симплексную таблицу (табл. 5.2)
|
| х1 | х2 | х3 | х4 | х5 | х6 | в | оо |
| х3 | 1 | 0 | 1 | 0 | -3 | 0 | 3 | 3 |
| х4 | 2 | 0 | 0 | 1 | -1 | 0 | 11 | 5,5 |
| x2 | 0 | 1 | 0 | 0 | 1 | 0 | 5 | - |
| х6 | 3 | 0 | 0 | 0 | 0 | 1 | 21 | 7 |
| Z | 2 | 0 | 0 | 0 | -3 | 0 |
|
|
| x1=0;x2=5;x3=3;x4=11;x5=0;x6=21 |
| Z=2*0+3*5=15 |
Критерий оптимальности вновь не выполнен.
Новая симплексная таблица примет вид табл. 5.3.
| Базис | х1 | х2 | х3 | х4 | х5 | х6 | bi | Оценочное отношение | |
| х1 | 1 | 0 | 1 | 0 | -3 | 0 | 3 | - | |
| х4 | 0 | 0 | -2 | 1 | 5 | 0 | 5 | 1 | |
| х2 | 0 | 1 | 0 | 0 | 1 | 0 | 5 | 5 | |
| х6 | 0 | 0 | -3 | 0 | 9 | 1 | 12 | 1,33333333 | |
| Z | 0 | 0 | -2 | 0 | 3 | 0 |
|
| |
| x1=3;x2=5;x3=0;x4=5;x5=0;x6=12 | |||||||||
| Z=2*3+3*5=21 | |||||||||
И на этот раз критерий оптимальности не выполнен; пятый столбец и вторая строка разрешающие, а25 = 5 — разрешающий элемент.
Переходим к табл. 5.4
| Базис | х1 | х2 | х3 | х4 | х5 | х6 | bi | Оценочное отношение |
| х1 | 1 | 0 | -0,2 | 0,6 | 0 | 0 | 6 |
|
| х5 | 0 | 0 | -0,4 | 0,2 | 1 | 0 | 1 |
|
| х2 | 0 | 1 | 0,4 | -0,2 | 0 | 0 | 4 |
|
| х6 | 0 | 0 | 0,6 | -1,8 | 0 | 1 | 3 |
|
| Z | 0 | 0 | -0,8 | -0,6 | 0 | 0 |
|
|
| x1=6;x2=4;x3=0;x4=0;x5=1;x6=3 |
| Z=2*6+3*4=24 |
Критерий оптимальности выполнен, значит Fmax = 24, оптимальное базисное решение (6; 4; 0; 0; 1; 3)
| 2020-02-04 |
229 |
Обсуждений (0) |
из
5.00
|
Обсуждение в статье: Симплексные преобразования |
|
Обсуждений еще не было, будьте первым... ↓↓↓ |
Почему 1285321 студент выбрали МегаОбучалку...
Система поиска информации
Мобильная версия сайта
Удобная навигация
Нет шокирующей рекламы