Симплекс метод - это метод последовательного перехода от одного базисного решения (вершины многогранника решений) системы ограничений задачи линейного программирования к другому базисному решению до тех пор, пока функция цели не примет оптимального значения (максимума или минимума).
Симплекс-метод является универсальным методом, которым можно решить любую задачу линейного программирования, в то время, как графический метод пригоден лишь для системы ограничений с двумя переменными.
Перед тем, как перейти к алгоритму симплекс метода, несколько определений.
Всякое неотрицательное решение системы ограничений называется допустимым решением.
Пусть имеется система m ограничений с n переменными (m < n).
Допустимым базисным решением является решение, содержащее m неотрицательных основных (базисных) переменных и n - m неосновных. (небазисных, или свободных) переменных. Неосновные переменные в базисном решении равны нулю, основные же переменные, как правило, отличны от нуля, то есть являются положительными числами.
Любые m переменных системы m линейных уравнений с n переменными называются основными, если определитель из коэффициентов при них отличен от нуля. Тогда остальные n - m переменных называются неосновными (или свободными).
Алгоритм симплекс метода
Шаг 1. Привести задачу линейного программирования к канонической форме. Для этого перенести свободные члены в правые части (если среди этих свободных членов окажутся отрицательные, то соответствующее уравнение или неравенство умножить на - 1) и в каждое ограничение ввести дополнительные переменные (со знаком "плюс", если в исходном неравенстве знак "меньше или равно", и со знаком "минус", если "больше или равно").
Шаг 2. Если в полученной системе m уравнений, то m переменных принять за основные, выразить основные переменные через неосновные и найти соответствующее базисное решение. Если найденное базисное решение окажется допустимым, перейти к допустимому базисному решению.
Шаг 3. Выразить функцию цели через неосновные переменные допустимого базисного решения. Если отыскивается максимум (минимум) линейной формы и в её выражении нет неосновных переменных с отрицательными (положительными) коэффициентами, то критерий оптимальности выполнен и полученное базисное решение является оптимальным - решение окончено. Если при нахождении максимума (минимума) линейной формы в её выражении имеется одна или несколько неосновных переменных с отрицательными (положительными) коэффициентами, перейти к новому базисному решению.
Шаг 4. Из неосновных переменных, входящих в линейную форму с отрицательными (положительными) коэффициентами, выбирают ту, которой соответствует наибольший (по модулю) коэффициент, и переводят её в основные. Переход к шагу 2.
Важные условия
Если допустимое базисное решение даёт оптимум линейной формы (критерий оптимальности выполнен), а в выражении линейной формы через неосновные переменные отсутствует хотя бы одна из них, то полученное оптимальное решение - не единственное.
Если в выражении линейной формы имеется неосновная переменная с отрицательным коэффициентом в случае её максимизации (с положительным - в случае минимизации), а во все уравнения системы ограничений этого шага указанная переменная входит также с отрицательными коэффициентами или отсутствует, то линейная форма не ограничена при данной системе ограничений. В этом случае её максимальное (минимальное) значение записывают в виде .
На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.
(2x - 15)/10 = 0
2x - 15 = 0
2x = 15
x = 15/2 = 7,5
2) Задумал х, прибавил 7, получил x + 7, умножил это на 3, получил 3(x + 7),
Вычел 15 и получил 30.
3(x + 7) - 15 = 30
3(x + 7) = 30 + 15 = 45
x = 45/3 - 7 = 15 - 7 = 8
3) В 1 день км, во 2 день x + 10 км, а всего 48 км.
x + x + 10 = 48
2x = 48 - 10 = 38
x = 38/2 = 19; x + 10 = 29
4) Положили x яблок и 5x слив, а всего 18 фруктов.
x + 5x = 18
6x = 18
x = 3 - яблок; 5x = 15 - слив
5) В банке x л воды, в ведре 3x л.
x + 3x = 24
4x = 24
x = 6 л - в банке; 3x = 18 л - в ведре.
6) Андрею x лет, а Олегу в 3 раза больше или на 8 лет больше
3x = x + 8
2x = 8
x = 4 - Андрею, 3x = 12 - Олегу.
7) Из банки отлили 1/2 молока, потом половину остатка, то есть 1/4.
А потом еще половину остатка, то есть 1/8. Всего отлили
1/2 + 1/4 + 1/8 = 4/8 + 2/8 + 1/8 = 7/8 банки.
Осталось 1/8 банки и это 100 г. Значит, в банке было 100*8 = 800 г.
8) Скорость автобуса х км/ч, а автомобиля х+12 км/ч.
Некое расстояние автобус проехал за 4 часа, а машина за 3 часа.
4x = 3(x + 12)
4x = 3x + 36
x = 36 км/ч - скорость автобуса.
x + 12 = 36 + 12 = 48 км/ч - скорость автомобиля.
За 4 часа он проехал 36*4 = 144 км.
9) За 1 час ученик отошел от школы на 3 км, и в это время выехал вел.
За время t ученик успеет пройти 3t км, а вел проедет 16t км.
И это на 3 км больше, чем пройдет ученик.
S = 3t + 3 = 16t
13t = 3
t = 3/13 часа = 180/13 мин ~ 13,85 мин.
Расстояние от школы, которое успеет проехать велосипедист
S = 16t = 16*3/13 = 48/13 км ~ 3,7 км.