Вам понадобится
  • - математический справочник
Инструкция
1
Отобразите систему ограничений системой линейных уравнений, которая отличается тем, что число неизвестных в ней больше количества уравнений. При ранге системы 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
2
Придавайте конкретные значения свободным переменным, после чего рассчитывайте базисные величины, значения которых неотрицательны. Если базисными величинами являются значения от X1 до Xr, то решение указанной системы от b1 до 0 будет опорным при условии, что значения от b1 до br ≥ 0.
3
При допустимости базисного решения проверьте его на оптимальность. Если решение не окажется таковым, перейдите к следующему опорному решению. При каждом новом решении линейная форма будет приближаться к оптимуму.
4
Составьте симплекс таблицу. Для этого члены с переменными во всех равенствах переносятся в левую часть, а свободные от переменных члены оставляются в правой части. Все это отображается в табличной форме, где в столбцах указываются базовые переменные, свободные члены, Х1….Xr, Xr+1…Xn, а в строках отображаются Х1….Xr, Z.
5
Просматривайте последнюю строку таблицы и выбирайте среди коэффициентов либо минимальное отрицательное число при поиске max, либо максимальное положительное при поиске на min. Если подобных значений нет, значит, найденное базисное решение можно считать оптимальным.
6
Просматривайте тот столбец таблицы, который тождественен выбранному положительному или отрицательному значению в последней строке. Выберите в нем положительные величины. Если таковых не обнаруживается, то задача решений не имеет.
7
Среди оставшихся коэффициентов столбца выберите тот, для которого соотношение свободного члена к этому элементу минимально. Вы получите разрешающий коэффициент, а строка, в которой он присутствует, станет ключевой.
8
Переведите базисную переменную, соответствующую строке разрешающего элемента, в разряд свободных, а свободную переменную, соответствующую столбцу разрешающего элемента – в категорию базисных. Постройте новую таблицу с другими названиями базисных переменных.
9
Разделите все элементы ключевой строки, кроме столбца свободных членов, на разрешающие элементы и вновь полученные значения. Внесите их в строку с откорректированной базисной переменной в новой таблице. Элементы ключевого столбца, равные нулю, тождественны всегда единице. Столбец, где в ключевой строке обнаруживается нуль, и строка, где в ключевом столбце находится нуль, в новой таблице сохранятся. В другие графы новой таблицы запишите результаты преобразования элементов из старой таблицы.
10
Исследуйте варианты до тех пор, пока не найдете оптимального решения.