Шпаргалка по Математическому программированию (стр. 4 из 8)

…………………………………………………..

X_m + а_mn₊₁X_m₊₁ + а_mn₊₂X_m₊₂ + … + а_mnX_n = a_m

Выполняется соотношение Z_j – c_j > 0, то план Х_Б0 не является оптимальным и можно перейти к плану Х_Б1 такому, что Z (Х_Б1) ≤ Z (Х_Б0).

Здесь Z_j = (С, Ā_j) – скалярное произведение векторов.

С – вектор, состоящий из коэффициентов при базисных переменных целевой функции Z

Ā_j – вектор, состоящий из коэффициентов разложения соответствующего вектора по векторам базиса.

c_j – коэффициент целевой функции Z при переменной Х_j

Следствие из теоремы: Если для всех векторов Ā₁, Ā₂, …, Ā_n некоторого опорного плана Х выполняется соотношение Z_j – c_j < 0, то опорный план Х является оптимальным. Величины (Z_j – c_j) – называются оценками оптимальности соответствующих векторов.

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

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

31. Выбор вектора, вводящегося в базис и выводящегося из базиса. Симплексное отношение.

Для перехода к новому опорному плану необходимо один из свободных векторов

ввести в базис, а какой-то из базисных векторов вывести. Для введения в базис выберем вектор, имеющий хотя бы одну положительную координату. Пусть таким вектором будет вектор А m+1 .

Разложению –

соотв. вектор, кот. будет являться опорным планом, если его координаты будут неотрицательными, а кол-во положительных координат будет равняться m.

Координаты вектора Х1 должны быть неотрицательными, т.е.

Если

, то эта координата будет неотрицательной.

Пусть минимум в соотношении (5) был получен при i =1, тогда если взять

то первая координата вектора 1 х станет равной нулю.

Соотношение (6) называется симплексным отношением. Таким образом, мы перешли от исходного опорного плана 0 х (базисные векторы А1,А2,…Аm) к опорному плану 1 х (базисные векторы А2,А3,…,Аm,Am+1).

32. разрешающий элемент таблицы, его выбор. Правило полных жордановых исключений для перерасчета симплекс таблицы.

33. Правило «четырехугольника» для перерасчета симплекс-таблицы

34. Признак единственности оптимального плана, множества оптимальных планов и отсутствия оптимального плана при решении задача ЛП симплекс-методом.

При решении задач симплекс-методом возможны следующие виды оптимальных решений:

1. Единственность. Если оценки всех свободных векторов строго отрицательные, то полученный опорный план является оптимальным и единственным. (см. пример в предыдущем параграфе).

2. Альтернативный оптимум (множество оптимальных решений).

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

3. ЗЛП не имеет оптимального решения, так как целевая функция не ограничена снизу. Если в симплекс таблице имеется положительная оценка, а все элементы данного столбца отрицательны и нулевые, то данный вектор можно ввести в базис. Однако никакой из базисных векторов нельзя вывести из базиса. Из этого следует, что дальнейшее уменьшение целевой функции возможно при переходе к неопорному плану.

4. ЗЛП не имеет оптимального решения, так как система ограничений противоречива. Поскольку при решении ЗЛП обычным симплекс-методом должен быть исходный опорный план, то система линейных уравнений заведомо не противоречива. Следовательно, такой случай не может встретиться при решении обычным симплекс методом.

5. Если ОДЗ состоит из одной точки, то решение такой задачи является тривиальным, и может быть получено без использования симплекс-метода.

35. В каких случая применяется метод искусственного базиса

Если задача линейного программирования находится в канонической форме, однако, не во всех уравнениях присутствуют базисные переменные, т. е. исходный опорный план отсутствует. В этом случае в те уравнения, в которых нет базисных переменных, необходимо добавить с коэффициентом +1 некоторую неотрицательную переменную. Такая переменная называется искусственной.

36. Построение М-задачи в методе искусственного базиса

Искусственную переменную необходимо добавить в целевую функцию с очень большим положительным числом (так как целевая функция на нахождения минимума). Это число обозначается латинской буквой M. Его можно считать равным +∞. В связи с этим иногда метод искусственного базиса называют М- методом. Такое преобразование исходной задачи называется построением расширенной задачи. Если решается задача с целевой функцией на нахождение искусственную переменную необходимо добавить в целевую функцию с очень большим положительным числом (так как целевая функция на нахождения минимума). Это число обозначается латинской буквой M. Его можно считать равным +∞. В связи с этим иногда метод искусственного базиса называют М- методом. Такое преобразование исходной задачи называется построением расширенной задачи. Если решается задача с целевой функцией на нахождение максимума, то искусственные переменные входят в целевую функцию с коэффициентом –М.

Таким образом, в расширенной задаче мы имеем опорный план (хотя некоторые из базисных переменных и являются искусственными).

Строится исходная симплекс таблица.

37. построение индексной строки в методе искусственного базиса

Строится исходная симплекс таблица, в которой индексная строка разбивается на две строки, поскольку оценки состоят из двух слагаемых. В верхней строке записывается слагаемое оценки без M, в нижней строке – коэффициенты при М. Знак оценки определяется знаком коэффициента при M, независимо от величины и знака слагаемого без M, так как M очень большое положительное число.

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

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

38. Критерий оптимальности в методе искусственного базиса. Признак построение начального опорного плана исходной задачи.

39. Алгоритм двойственного симплекс-метода

Алгоритм двойственного симплекс-метода:

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

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

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

4. Пересчитывают симплексную таблицу по правилу полных жордановых исключений

5. проверяют полученный план на допустимость. Признаком получения допустимого опорного плана является отсутствие в столбце А0 отрицательных элементов. Если в столбце А0 имеются отрицательные элементы то переходят ко второму пункту. Если же их нет, то переходят к решению полученной задачи обычным способом.