Вам понадобитсяОтобразите систему ограничений системой линейных уравнений, которая отличается тем, что число неизвестных в ней больше количества уравнений. При ранге системы 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.
Просматривайте последнюю строку таблицы и выбирайте среди коэффициентов либо минимальное отрицательное число при поиске max, либо максимальное положительное при поиске на min. Если подобных значений нет, значит, найденное базисное решение можно считать оптимальным.
Просматривайте тот столбец таблицы, который тождественен выбранному положительному или отрицательному значению в последней строке. Выберите в нем положительные величины. Если таковых не обнаруживается, то задача решений не имеет.
Среди оставшихся коэффициентов столбца выберите тот, для которого соотношение свободного члена к этому элементу минимально. Вы получите разрешающий коэффициент, а строка, в которой он присутствует, станет ключевой.
Переведите базисную переменную, соответствующую строке разрешающего элемента, в разряд свободных, а свободную переменную, соответствующую столбцу разрешающего элемента – в категорию базисных. Постройте новую таблицу с другими названиями базисных переменных.
Разделите все элементы ключевой строки, кроме столбца свободных членов, на разрешающие элементы и вновь полученные значения. Внесите их в строку с откорректированной базисной переменной в новой таблице. Элементы ключевого столбца, равные нулю, тождественны всегда единице. Столбец, где в ключевой строке обнаруживается нуль, и строка, где в ключевом столбце находится нуль, в новой таблице сохранятся. В другие графы новой таблицы запишите результаты преобразования элементов из старой таблицы.
Исследуйте варианты до тех пор, пока не найдете оптимального решения.
