Решение задач симплекс - методом (подробный разбор)

Условие задачи

F_min=x1-2x2+x3+2x4 – целевая функция, м.б либо макс либо мин

Это общий вид ЗЛП, нужно найти либо мин, либо макс

Мин – затраты, макс – прибыль

Для решения мы должны найти неизвестные х1,х2,х3,х4

Эти значения подставить в целевую функцию и находим либо мин, либо макс

Решение задачи на поиск мин и макс решается практически одинаково. Единственное различие в нахождении главного столбца.

Еще м.быть условия, что наши искомые переменные не м.быть отрицательными, т.е либо положительными, либо = нулю.

Для решения задачи строим таблицу

Кол-во строк и столбцов зависит от кол-ва переменных.

Первый солбец – это неизвестные

Второй – свободные члены

Дальше идут неизвестные х1 х2 и т.д(зависит от условий. В нашем примере их 4)

Кол-во строк – это кол-во уравнений

Своб. Члены – это те цифры, которые стоят за знаком неравенства.

У уравнения F_min свободного члена нет, по этому ставим ноль (не зависимо мин или макс)

Заполняем коэффициенты (это те цифры, которые стоят перед х1, х2…). Обращаем внимание на знаки в уравнении.

Если внимательно посмотреть на все уравнения, в каждом из них нахватаете какого – либо неизвестного. В случае, когда коэффициент отсутствует, проставляется ноль

Строка F_min заполняется с противоположными знаками не зависимо макс или мин.

Ищем главный столбец, затем главная срока, затем главный элемент

Гл. столбец находится со строки F_min, есали у нас мин, мы выбираем из положительных чисел самое макс. В нашем случае положительное одно – 2, этот столбец главный

Если макс – выбирается из отрицательных по модулю самое наибольшее

Главный столбец –выделить цветом.

Чтобы найти главную строку – столбец свободных членов делим на главный столбец. Из полученных результатов выбирается самое наименьшее из положительных и при мин и при макс.

При делении там где ноль – эту сроку вообще не рассматривают.

Самый наименьший результат – в строке У2

Главный элемент – это пересечение гл. сроки и гл. столбца. В нашем случае это 1

Чертим такую же таблицу, будем вносить данные

В новой таблице главный столбец и главная срока будут меняться местами х2 меняем с у2

Заполняем главный столбец. Каждый элемент главного столбца делим на главный элемент (на 1 ) и пишем в новую табл с противоположным знаком.

Главный элемент переносим, т.к это 1 и знак его никогда не меняется он всегда положительный.

В главной строке так же каждое значение делим на главный элемент, но знаки меняться не будут.

Не всегда гл. эл. 1 . не ед, то значение гл. эл. поменяется на обратную. Величину, если 2 то, запишется ½, если 3 – 1/3

Значение остальных ячеек ищем по формуле Жордана – Гауса

Где i- номер сроки,

j – номер столбца,

r – главная строка

s – главный столбец

Чтобы понять как применять формулу каждую ячейку 1 таблицы пронумеруем

Для каждой ячейки нужно подставить значение и получить результат

– a 23 r =2 s=3

Значения берем из 1 таблицы, подставляем в формулу и получаем результаты

После заполнения таблицы берем только строку F_min Задачу нужно решать до тех пор, пока все элементы в строке F_min положительные. Ноль не считается.

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

Т.к. в строке F нет положительных элементов, найдено оптимальное решение. =-14 (всегда берем значение из столбца свободных членов)

Проверка

Подставляем в целевую функцию значения из столбца свободн членов.

Х1 =0, т.к. нет этой переменной, есть только х2 =7, остальные = нулю

X1-2x2+x3+2x4=0-2*7+0+0 = -14