29 Сформулируйте критерий отсутствия решений в алгоритме симплекс-метода.

Если ограничения задачи линейного программирования несовместны (т.е. они не могут выполняться одновременно), то задача не имеет допустимых решений. Такая ситуация не может возникнуть, если все неравенства, составляющие систему ограничений, имеют тип " ≤ " с неотрицательными правыми частями, т.к. в этом случае дополнительные переменные могут составить допустимое решение. Для других типов ограничений использются искусственные переменные. Если задача имеет решение, то в оптимальной таблице в базисе нет искусственных переменных (Ri). Если они там есть, то задача не имеет решений.

31 Где в алгоритме симплекс-метода используется метод Гаусса?

Метод Жордана–Гаусса применяется для решения системы m линейных уравнений

с n неизвестными вида: Σa x = b (33 стр)

Данный метод заключается в том, что с помощью элементарных преобразований

система уравнений приводится к равносильной системе уравнений с матрицей опреде-

ленного вида.

Над строками расширенной матрицы ~A осуществляем следующие элементарные

преобразования:

1. перестановка двух строк;

2. умножение строки на любое число, отличное от нуля;

3. прибавление к одной строке другой строки, умноженной на некоторое число;

4. отбрасывание нулевой строки (столбца).

32 Дайте определение р-матрицы кзлп.

Р-матрицей КЗЛП (3.18) будем называть расширенную матрицу системы линейных уравнений , равносильной системе (3.36), содержащую единичную подматрицу порядка m на месте n первых столбцов, все симплекс разности которой неотрицательны.

33 Дайте определение псевдоплана кзлп.

Псевдоплан КЗЛП – это базисное решение системы линейных уравнений данной КЗЛП, определяемое P-матрицей

34 Сформулируйте критерий отсутствия решения в алгоритме р-метода.

Составление псевдоплана. Систему ограничений исходной задачи приводят к системе неравенств смысла «≤».

Проверка плана на оптимальность. Если в полученном опорном плане не выполняется условие оптимальности, то задача решается симплексным методом.

Выбор ведущих строки и столбца. Среди отрицательных значений базисных переменных выбираются наибольшие по абсолютной величине. Строка, соответствующая этому значению, является ведущей.

Расчет нового опорного плана. Новый план получается в результате пересчета симплексной таблицы методом Жордана-Гаусса. Далее переход к этапу 2.

35 В каком случае к решению злп необходимо применять двухэтапный симплекс-метод?

Симплекс-метод, называемый также методом последовательного улучшения плана, реализует перебор угловых точек области допустимых решений в направлении улучшения значения целевой функции. Основная идея этого метода следующая. Прежде всего, находится какое-либо допустимое начальное (опорное) решение, т.е. какая-либо угловая точка области допустимых решений. Процедура метода позволяет ответить на вопрос, является ли это решение оптимальным. Если "да", то задача решена. Если "нет", то выполняется переход к смежной угловой точке области допустимых решений, где значение целевой функции улучшается, т.е. к нехудшему допустимому решению. Если некоторая угловая точка имеет несколько смежных, то вычислительная процедура метода обеспечивает переход к той из них, для которой улучшение целевой функции будет наибольшим. Процесс перебора угловых точек области допустимых решений повторяется, пока не будет найдена точка, которой соответствует экстремум целевой функции Е. При построении начального базиса в заданной задаче использовался метод искусственного базиса, поэтому найденное решение не является допустимым. В этом случае для решения задачи необходимо использовать двухэтапный симплекс- метод.