Решение задачи линейного программирования симплекс методом.

Недавно столкнулся с проблемой решения задачи симплекс методом. После долгих поисков толкового алгоритма решения данным методом – конкретных результатов получено не было. В ходе самостоятельных рассуждений симплекс метод был побеждён.

В данном посте я постараюсь без воды, научить вас решать задачи такого вот плана:

На каждом шаге решения нам необходимо будет заполнять таблицу следующего вида:

Ну, что же, начнём заполнение таблицы решения. В первую строку нашей таблицы запишем индексы целевой функции, а в столбцы x1, x2, x3, x4, x5, x6 индексы функций объединённых в систему. В столбце RHS разместим результаты функций.

Теперь самое интересное в решении симплекс-методом, среди столбцов данной таблицы есть единичная матрица. Кто из математики забыл, напомню, единичной матрицей называют такую матрицу, у которой диагональ состоит из единиц, а все остальные элементы равны нулю. На фото снизу я выделил столбцы, которые образуют единичную матрицу:

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

Шаг 2. Далее нам необходимо заполнить строку Zj, делается это следующим образом: элементы, находящиеся в столбце CB, умножаются на элементы столбцов x1, x2, x3, x4, x5, x6 и слаживаются между собой. Сказанное выше можно увидеть на фото ниже:

Шаг 3. В конце каждой итерации необходимо высчитать Cj-Zj, в этом нет ничего сложного, здесь простое вычитание из первой строки последней строки. В конечном итоге таблица выглядит следующим образом:

Шаг 4. Если мы видим в строке Cj-Zj есть положительные элементы, то нам необходимо продолжать решение симплекс методом.

В строке Cj-Zj находим наибольшее число, как мы видим - это восемь, следовательно, столбец номер два с восьмёркой становится ведущим столбцом, выделим его жёлтым цветом:

Шаг 5. Теперь необходимо найти ведущую строку, делается это следующим образом: элементы столбца RHS делятся на элементы ведущего столбца. После деления из -6 (12/-2), 3 (12/4) и 5 (25/5) выбирается минимально положительный элемент, в данном случае 3, и таким образом, строка, в которой он получился -  становится ведущей строкой. Выделим её жёлтым цветом:

Шаг 6. Возвращаемся в самое начало, к практически пустой таблице (за исключением строки один, Cj – она во всех таблицах не подлежит изменениям):

Как вы понимаете новую таблицу, мы должны  заполнить, исходя из предыдущих расчётов. Ну, что же начнём с первой строки. Делим ведущую строку на элемент, получившийся на пересечении ведущей строки и ведущего столбца, в нашем случае на 4:

Далее самое сложное, на месте других элементов, находящихся в ведущем столбце, мы должны получить нули в новой, строящейся таблице. Это можно представить в виде следующей формулы: (элемент в ведущем столбце)-(x*элемент в первой строке, новой таблицы)=0.

В нашем случае, X для первой строки (старой таблицы)  равен: -2-(x*1)=0, т.е. x=-2. Умножаем первую строку в новой таблице на -2 и отнимаем от первой строки (старой таблицы).

В нашем случае, X для третей строки (старой таблицы) равен: 5-(x*1)=0, т.е. x=5. Умножаем первую строку в новой таблице на 5 и отнимаем от третей строки (старой таблицы).

Ну, вот собственно, алгоритм я вам рассказал, теперь идёт повторение Шагов, описанных выше, начиная с первого. 

Мною же далее была получена следующая таблица:

В строке Cj-Zj есть положительные элементы, следовательно, я строю следующую таблицу:

Ну, собственно конец наших расчётов и мучений, в последней строке нет положительных элементов, следовательно функция находится в максимуме равном 39, при X4=1, X2=4, X1=23.

Понравилось? Опубликуй у себя: