Переход к следующей симплекс-таблице осуществляют по правилам:
-
все элементы разрешающей строки делят на генеральный элемент;
-
разрешающий столбец дополняют нулями;
-
если в разрешающей строке есть нули, то соответствующие столбцы переписывают без изменений;
-
все другие элементы рассчитывают с помощью метода прямоугольников: если г – генеральный элемент, с – старый элемент, то п – новый элемент находят по формуле:
-
а
с
г
b
Таким образом, вторая симплекс-таблица имеет вид:
Таблица 2.3.2
Вторая симплексная таблица
Базис | С | р0 | – 1 | – 4 | 0 | 0 | 0 | М | С.О. |
р1 | р2 | р3 | р4 | р5 | р6 | ||||
р6 | М | 4 | 0 | 34/7 | –1 | 0 | 1/7 | 1 | 4/(34/7)=14/17 |
р4 | 0 | 5 | 0 | 6/7 | 0 | 1 | 1/7 | 0 | 5/(6/7)=30/7 |
р1 | – 1 | 1 | 1 | 1/7 | 0 | 0 | –1/7 | 0 | 1/(1/7)=7 |
z-строка | – 1 | 0 | 27/7 | 0 | 0 | 1/7 | 0 |
| |
М-строка | 4 | 0 | 34/7 | –1 | 0 | 1/7 | 0 |
|
Этой симплексной таблице соответствует опорный план:
x1 = 1, x2 = 0, x3 = 0, х4 = 5, x5 = 0, x6 = 4.
Он не является оптимальным, так как в М-строке есть положительные оценки.
По правилам, описанным выше, перейдем к третьей симплексной таблице:
Таблица 2.3.3
Третья симплексная таблица
Базис | С | р0 | – 1 | – 4 | 0 | 0 | 0 |
|
р1 | р2 | р3 | р4 | р5 | ||||
р2 | – 4 | 14/17 | 0 | 1 | –7/34 | 0 | 1/34 |
|
р4 | 0 | 73/17 | 0 | 0 | 3/17 | 1 | 2/17 | (73/17)/(3/17)=73/3 |
р1 | – 1 | 15/17 | 1 | 0 | 1/34 | 0 | –5/34 | (15/17)/(1/34)=30 |
z-строка | –71/17 | 0 | 0 | 27/34 | 0 | 1/34 |
|
В этой таблице отсутствует М-строка, поскольку искусственные векторы выведены из базиса, и в дальнейшем не рассматриваются.
Третьей симплексной таблице соответствует опорный план:
x1 = 15/17, x2 = 14/17, x3 = 0, х4 = 73/17, x5 = 0.
Он не является оптимальным, так как в z-строке есть положительные оценки.
Перейдем к четвертой симплексной таблице:
Таблица 2.3.4
Четвертая симплексная таблица
Базис | С | р0 | – 1 | – 4 | 0 | 0 | 0 |
|
р1 | р2 | р3 | р4 | р5 | ||||
р2 | – 4 | 35/6 | 0 | 1 | 0 | 7/6 | 1/6 |
|
р3 | 0 | 73/3 | 0 | 0 | 1 | 17/3 | 2/3 |
|
р1 | – 1 | 1/6 | 1 | 0 | 0 | –1/6 | –1/6 |
|
z-строка | –47/2 | 0 | 0 | 0 | –9/2 | –1/2 |
|
Этой симплекс-таблице соответствует опорный план:
x1 = 1/6, x2 = 35/6, x3 = 73/3, х4 = 0, x5 = 0.
Он является оптимальным и единственным, так как в z-строке нет положительных оценок. Значение целевой функции min (– z) = – 47/2, значит,
max z = – min (– z) = 47/2.
Замечание.
-
Если в симплексной таблице есть две одинаковые положительные наибольшие оценки оптимальности, то выбирают любую.
-
Если в разрешающем столбце симплексной таблицы нет положительных чисел, то целевая функция является неограниченной на области допустимых решений ЗЛП, т.е. ЗЛП не имеет решений.
-
В последней симплексной таблице нет необходимости заполнять все клетки, а можно только заполнить z-строку и столбец р0.
- Рецензенты:
- Содержание
- 1. Программа курса Введение
- Математические основы программирования
- Общий вид задачи линейного программирования
- Методы решения общей задачи линейного программирования
- Двойственные задачи линейного программирования
- Распределительные методы
- Элементы нелинейного программирования
- Элементы теории игр
- Введение
- Классификация задач математического программирования
- 2. Математическое программирование
- 2.1. Постановка задач линейного программирования
- Алгоритм графического метода решения злп
- 2.3. Симплекс-метод решения задачи линейного программирования
- Алгоритм симплекс-метода решения злп
- Пример 2.3.1. Решить злп (2.2.1), (2.2.5) симплекс-методом.
- Критерий оптимальности опорного плана:
- Переход к следующей симплекс-таблице осуществляют по правилам:
- 2.4. Двойственная задача линейного программирования
- 2.5. Элементы теории матричных игр
- Алгоритм принципа максимина (минимакса)
- Решение. Эта матричная игра имеет размерность (3х4), т.Е. Игрок а имеет три стратегии, а игрок в – четыре. Запишем ее в нормальной форме.
- Последовательность действий при решении игры
- 2.6. Транспортная задача. Метод потенциалов
- Алгоритм метода потенциалов состоит из следующих этапов:
- Критерий оптимальности плана перевозок
- 2.7. Задача о назначениях
- Алгоритм метода Фогеля
- Алгоритм венгерского метода решения задачи о назначениях
- 2.8. Дробно-линейное программирование
- Правила решения задачи дробно-линейного программирования графическим методом
- 2.9. Целочисленное программирование
- 2.10. Параметрическое программирование
- Алгоритм решения задачи параметрического программирования
- 3. Задания для самостоятельной работы