Главная Войти О сайте












Как решать симплексным методом

Если в задаче имеется N неизвестных, то область допустимых решений в системе ограничивающих условий будет являться выпуклым многогранником в N-мерном пространстве.Графическое решение такой задачи невозможно, и в этом случае применяется симплексный метод линейного программирования.Как решать симплексным методом

Запишите систему ограничений как систему линейных уравнений, число неизвестных в которой будет больше количества уравнений. Выберите R неизвестных при ранге системы R. Используя метод Гаусса, приведите систему к такому виду:

x1= b1+a1r+1x r+1+…+ a1nx n;
x2= b2+a2r+1x r+1+…+ a2nx n;

xr= br+ar,r+1x r+1+…+ amx n.

Придайте свободным переменным конкретные значения и после этого рассчитайте базисные величины. Их значения должны быть неотрицательными. Так, если за базисные величины приняты значения от X1 до Xr, то решение данной системы от b1 до 0 будет являться опорным, при условии, что значения от b1 до br ≥ 0.

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

Сформируйте симплекс-таблицу. Перенесите в ее левую часть члены с переменными во всех равенствах, а свободные от переменных – в правую. Таким образом, в столбцах будут указаны базовые переменные, свободные члены, Х1…Xr, Xr+1…Xn, в строках отобразятся Х1…Xr, Z.

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

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

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


CompleteRepair.Ru