Алгоритм отыскания опорного решения задачи ЛП
Этот алгоритм выполняется сразу после записи симплекс-таблицы.
Алгоритм 2:
1. Просматриваем столбец свободных членов (не смотря на свободный член строки ). Если все свободные члены , то данная таблица уже соответствует опорному решению, иначе переходим к п. 2.
2. В столбце свободных членов выбираем первый по порядку отрицательный элемент и в этой строке находим еще один отрицательный элемент. Если такого элемента нет, то задача ЛП не имеет решения, если есть, то переходим к п. 3.
3. Столбец с найденным отрицательным элементом объявляем генеральным.
4. В генеральном столбце фиксируем элементы, имеющие такой же знак, что и знак соответствующих свободных членов, и среди них в качестве генерального элемента выбираем тот, отношение к которому соответствующего свободного члена минимально:
, знак = знак .
5. По выбранному генеральному элементу выполняем стандартное симплекс- преобразование (алгоритм 1) и переходим к п. 1.
Если при вычислениях нет ошибок, то количество отрицательных свободных членов должно уменьшаться или должна уменьшаться их абсолютная величина.
Примечание к пункту 2:
Задача ЛП не имеет решения, когда соответствующая строка СТ имеет, например, вид: , которая не удовлетворяется ни при
каких неотрицательных переменных.
Дата добавления: 2022-05-27; просмотров: 99;