Алгоритм симплексного метода решения задач при принятии управленческих решений

Запись исходного опорного решения- проверка исходного опорного решения по критерию оптимальности- запись оптимального решения, либо переход к лучшему опорному решению и проверка его на оптимальность.

Решение – совокупность значений переменных величин. Виды решений: базисные (возможные), опорные (допустимые), оптимальные.

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

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

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

Базис системы-линейно-независимые векторы между собой.

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

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

С разрешающим элементом производятся симплексные преобразования однократного замещения. Из базиса выводится базисная переменная величина, соответствующая разрешающей строке, а вводится свободная переменная величина, соответствующая разрешающему столбцу. На месте разрешающего элемента ставится 1, все остальные элементы разрешающего столбца, включая оценку равны 0. Элементы разрешающей строки делятся на разрешающий элемент. Остальные элементы симплексной таблицы находятся по правилу прямоугольника: из произведения элементов, стоящих на главной диагонали вычитается произведение элементов, стоящих на побочной диагонали и делится на разрешающий элемент.

Алгоритм симплексного метода решения задач при принятии управленческих решений.

1.С-ма ограничений приводится к каноническому виду. Составляется первая симплексная таблица.

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

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

4. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

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

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

7. Элемент табл. 2, соответствующий разрешающему элементу табл. 1, равен обратной величине разрешающего элемента.

8. Элементы строки табл. 2, соответствующие элементам разрешающей строки табл. 1, получаются путем деления соответствующих элементов табл. 1 на разрешающий элемент,

9. Элементы столбца табл. 2, соответствующие элементам разрешающего столбца таблицы 1, получаются путем деления соответствеующ элементов таб1 на разрешающий элемент и берутся с противоположным знаком.

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

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

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