- 1
- 2
- 3
- . . .
- последняя »
Задача 1.
Решить задачу линейного программирования симплексным методом.
Вариант 2.
Найти наибольшее значение функции f(X) = x1 – 4x4 при ограничениях x1 – x2 + x3 + x4 = 3
x1 + x2 + 2x3 = 5,
xj 0, j = 1, 2, 3, 4. Решение.
Задача записана в каноническом виде, но не имеет необходимого числа единичных столбцов, т. е. не обладает очевидным начальным опорным решением.
Для нахождения опорного плана переходим к М-задаче: f(X) = x1 – 4x4 – Мy1 max
x1 – x2 + x3 + x4 = 3
x1 + x2 + 2x3 + y1 = 5,
xj 0, j = 1, 2, 3, 4; y1 0. Очевидное начальное опорное решение (0; 0; 0; 3; 5).
Решение осуществляется симплекс-методом с искусственным базисом.
Расчеты оформим в симплекс-таблицах
Номерсимплекс-таблицы | Базис | CjCi | B | 1 | 0 | 0 | -4 | -M | Q |
A1 | A2 | A3 | A4 | P1 | |||||
0 | A4 | -4 | 3 | 1 | -1 | 1 | 1 | 0 | 3:1= 3 |
P1 | -M | 5 | 1 | 1 | 2 | 0 | 1 | 5:2= 2,5 | |
j | - | -5M-12 | -M-5 | -M+4 | -2M-4 | 0 | 0 |
| |
1 | A4 | -4 | 1/2 | 1/2 | -3/2 | 0 | 1 | 1/2:1/2=1 | |
A3 | 0 | 5/2 | 1/2 | 1/2 | 1 | 0 | 5/2:1/2=1 | ||
j | - | -2 | -3 | 6 | 0 | 0 |
| ||
2 | A1 | 1 | 1 | 1 | -3 | 0 | 2 |
| |
A3 | 0 | 2 | 0 | 2 | 1 | -1 | 2:2=1 | ||
j | - | 1 | 0 | -3 | 0 | 6 |
| ||
3 | A1 | 1 | 4 | 1 | 0 | 3/2 | 1/2 | ||
A2 | 0 | 1 | 0 | 1 | 1/2 | -1/2 | |||
j | - | 4 | 0 | 0 | 3/2 | 9/2 |
Начальное опорное решение (0; 0; 0; 3; 5), соответствующее симплекс-таблице 0, неоптимальное, так как в - строке есть отрицательные значения, наименьшее в столбце А3. Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке P1, эта строка направляющая. Направляющий элемент на пересечении направляющих строки и столбца. Столбец P1 выводим из базиса, а А3 - вводим в базис.
При пересчете таблицы столбец Р1 далее можно не рассчитывать.
После пересчета получаем симплекс-таблицу 1. Соответствующее опорное решение (0; 0; 5/2; 1/2; 0) не оптимально, так как в - строке есть отрицательные значения, в столбце А1.Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А4. В качестве направляющей строки возьмем А4. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А4 выводим из базиса, а А1 - вводим в базис.
После пересчета получаем симплекс-таблицу 2. Опорное решение, соответствующее симплекс-таблице 2 (1; 0; 2; 0; 0) – не оптимально, так как в - строке есть отрицательные значения, в столбце А2. Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А3. В качестве направляющей строки возьмем А3. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А3 выводим из базиса, а
- 1
- 2
- 3
- . . .
- последняя »
Похожие работы
Тема: Линейное программирование |
Предмет/Тип: Другое (Контрольная работа) |
Тема: Линейное программирование |
Предмет/Тип: Информатика, ВТ, телекоммуникации (Реферат) |
Тема: Линейное программирование 2 3 |
Предмет/Тип: Информатика, ВТ, телекоммуникации (Контрольная работа) |
Тема: Линейное программирование 3 |
Предмет/Тип: Математика (Реферат) |
Тема: Линейное программирование 4 |
Предмет/Тип: Математика (Реферат) |
Интересная статья: Основы написания курсовой работы