44. Является ли симплекс-таблица для злп на максимум окончательной? Ответ обоснуйте. Найдите решение злп или сделайте вывод о неразрешимости задачи.

Б.П	X1	X2	X3	X4	СЧ
X3	5	-2	1	0	3
X4	-1	3	0	1	4
f	0	3	0	0	10

Поскольку последняя - оценочная строка не имеет ни одной отрицательной оценки ,то симплекс- таблица решения ЗЛП на максимум окончательна и

45. Как найти допустимый базис в злп? Алгоритм метода искусственного базиса.

Базисом опорного решения называется базис системы векторов условий ЗЛП, в состав которого входят векторы, соответствующие отличным от нуля координатам опорного решения.

Для того чтобы найти допустимый базис необходимо:

1) привести систему ограничений к каноническому виду (ограничения в виде равенств)

2) выделить допустимый базис (переменные разделены на базисные и свободные, причем, если свободные переменные принимаем равными нулю – базисные положительны)

где - базисные переменные, - свободные переменные,

– свободные члены

В случае отсутствия нужного количества базисных переменных применяют различные методы выделения допустимого базиса, например М-метод, метод искусственного базиса.

Метод искусственного базиса:

Исходная задача:

• исходная система ограничений - уравнений переписывается в виде:

где все свободные переменные

• в системе вводятся дополнительные (искусственные) переменные , образующие базис:

• рассматривается вспомогательная целевая функция:

• симплексным методом решается ЗЛП:

• если эта задача имеет решение, то возможны два случая:

• допустимого базиса нет, т.е. исходная система не имеет неотрицательных решений

• допустимый базис существует; если в последней симплекс-таблице вспомогательной задачи все искусственные переменные - свободные, то из этой таблицы получим систему уравнений, эквивалентную исходной и преобразованную к виду, необходимому для решения исходной ЗЛП.

Пример:

Приводим к каноническому виду:

Вводим искусственные переменные ( – базисная переменная) :

Далее решаем симплекс-методом одновременно и задачи, в результате чего получаем, что и – свободные переменные.

А значит, мы нашли решение исходной задачи:

46. Всегда ли можно найти допустимый базис в задаче линейного программирования?

Ответ: НЕТ. Например, решая ЗЛП методом искусственного базиса, мы приходим к одной их двух альтернатив:

• допустимого базиса нет, т.е. исходная система не имеет неотрицательных решений.

• допустимый базис существует, т.е. исходная система имеет неотрицательное базисное решение.

Пример:

Решив эту задачу методом искусственного базиса, можно убедиться, что , а значит допустимый базис не существует, т.е. решений нет.