Алгоритм и пример симплекс-метода (ммэ) Рубрика: Прочее

Пример 5.3. Решить следующую задачу линейного программирования симплекс-методом:


Решение:
I итерация
1 этап: составление исходной симплекс-таблицы.
Задача линейного программирования задана в каноническом виде. Составим расширенную матрицу и выделим с помощью метода Жордана-Гаусса базисные переменные. Примем в качестве базисных – переменные х1 и х2.

Умножим (поэлементно) первую строку на –3 и сложим со второй:
.
Умножим вторую строку на  :
.
Сложим вторую с первой строкой:
.
В результате система ограничений примет следующий вид:

Выразим базисные переменные через свободные:

Выразим целевую функцию также через свободные переменные, для этого подставим полученные значения базисных переменных в целевую функцию:
.
Запишем целевую функцию в следующем виде:
.
Составим исходную симплекс-таблицу:
Таблица 5.11
Исходная симплекс-таблица

СП БП				Оценочные отношения
	–1		0
	0		2
	4	–	–3

2 этап: определение базисного решения.
Согласно определению базисного решения свободные переменные равны нулю, а значения базисных переменных – соответствующим значениям свободных чисел, т.е.:
.
Найденное базисное решение является вырожденным, т.к. имеется базисная переменная х2, равная нулю.
3 этап: проверка совместности системы ограничений ЗЛП.
Так как в таблице 5.11 имеется строка с отрицательным свободным числом (–1), в которой нет ни одного отрицательного элемента (т.е. отрицательного коэффициента при свободной переменной), то согласно признаку несовместности (признак 1) система ограничений данной задачи не совместна (строка целевой функции при рассмотрении данного признака не учитывается). Следовательно, рассматриваемая задача линейного программирования не имеет решения.
Ответ: рассматриваемая задача линейного программирования не имеет решения в силу несовместности ее системы ограничений.