Метод искусственного базиса на примере системы ограничений, содержащей уравнения
Алгебраический симплексный метод. Основные положения данного метода.
Симплексный метод- это метод целенаправленного перебора опорных решений задачи, который позволяет ха конечное число шагов, либо найти оптимальное решение, либо установить, что оптимальное решение не существует.
Основное содержание симплексного метода состоит в следующем:
1. Необходимо указать способ нахождения начального опорного решения.
2. Следует указать способ перехода от одного опорного решения к другому, причем переход должен осуществляется к более оптимального или по по крайней мере не существующему решению.
3. Требуется задать критерий, который позволяет своевременно прекратить перебор решений, остановивших на оптимальном или сделать заключение , что оптимального решения нет.
Свое название симплексный метод получил от простых областей допустимых решений, которые рассматривались на ранних этапах разработки метода.
10. Алгоритм решение задачи симплексным методом(первый опорный план)
Рассмотрим алгоритм симплексного метода на примере задачи линейного программирования. Система ограничений, которой содержит неравенство вида <=
Приведем задачу к канонической форме. Введем m дополнительных неотрицательных переменных
х n+1; x n+2 ….. x n+m
в результате получим:
F( X)= c1 x1+ c2x2+….a1nxn +cnxn +0*xn+1 +0*xn+2 + ……+0*xm+n
Система
2.найдем начальное опорное решение. Выпишем матрицу из коэффициентов полученной системы ограничений
Матрица
Коэффициенты при дополнительных переменных образуют единичную диагональную матрицу- базис, поэтому x n+1, x n+2…..x n+m называют базисными переменными.
Выразим базисные переменные через основные:
X n+1=b1-a11x1-a12x2-……-a m x n
X n+2=b2-a1x1-a22x2-……-a2m x n
…………………………………..
X m+ n=bm-am1x1-am2x2-…..-a m n x n
Прировняем к 0 основные переменные: x1=x2=….=x n=0
Тогда: xn+1=b1
Xn+2=b2
…………
X m +n=b m
В результате получаем начальное опорное решение
X1= (0; 0;….;0; b1; b2…..b m)
Занесем начальное опорное решение, базисные переменные, коэффициенты системы ограничений в специальную симплексную таблицу.
3.Проверка плана на оптимальность. При решении задачи на max опорный план считается оптимальным; если все коэффициенты индексной строки неотрицательны.
Если хотя бы один элемент отрицателен, то план считается неоптимальным ( т.е. – оптимальный; + неоптимальный)
При решении задачи на min, план считается оптимальным если все коэффициенты индексной строки не положительны.
Если план оказался оптимальным, то задача решена, необходимо выписать ответ, проанализировать его и сделать вывод о количестве оптимальных решений.
Если же план не оптимальный, то решение задачи продолжается т.е. переходим к др. пункту.
11. Алгоритм решения задачи симплексным методом ( проверка на оптимальность, определения ведущего столбца и строки, построение нового опорного плана).
Проверка плана на оптимальность. При решении задачи на max опорный план считается оптимальным; если все коэффициенты индексной строки неотрицательны.
Если хотя бы один элемент отрицателен, то план считается неоптимальным ( т.е. – оптимальный; + неоптимальный)
При решении задачи на min, план считается оптимальным если все коэффициенты индексной строки не положительны.
Если план оказался оптимальным, то задача решена, необходимо выписать ответ, проанализировать его и сделать вывод о количестве оптимальных решений.
Если же план не оптимальный, то решение задачи продолжается т.е. переходим к др. пункту.
Определение ведущего столбца. При решении задачи на max из всех отрицательных элементов индексной строки выбираем наибольший по модулю, этот элемент и определяет ведущий столбец.
Определение ведущей строки. Элементы столбца ЗБП делим на соответствующие элементы ведущего столбца, а результаты заносим в последний столбец таблицы.
Замечание. Делить можно числа только одного знака (+/+;-/-) т.е. в последнем столбце таблицы должны получаться только положительные значения. Если встретились числа разных знаков или деление на 0, то в столбце на соответствующем месте ставится прочерк.
Из всех элементов последнего столбца выбираем наименьший, он и определяет ведущую строку.
Определение разрешающего элемента. Разрешающий элемент находится на пересечении ведущей строки и ведущего столбца.
Заполнение нового опорного плана. В первую очередь заполняется столбец БП (базисные переменные). Базисная переменная, которая в старом плане
Оказалась на ведущей строке, покидает базис, ее место занимает переменная из ведущего столбца, а остальные переменные свое место в базисе сохраняют.
Далее заполняем строку, которая в старом плане была ведущей, для этого элементы старой ведущей строки делим на разрешающий элемент, а результаты заносим в новый план на соответствующее место.
В результате деления на месте старого разрешающего элемента окажется единица. Остальные элементы старого ведущего столбца в новом плане обнуляем. Все остальные элементы нового плана рассчитываются по формуле:
Элемент нового плана = элемент старого плана-(произведение дополняющих элементов до прямоугольника)/разрешающий элемент
Получив новый план проверяем его на оптимальность. Алгоритм повторяется до тех пор пока не получим оптимальное решение.
13. Анализ оптимального плана симплексного метода на примере задачи планирования товарооборота.
Оптимальное решение выписывают из столбца ЗБП последнего оптимального плана симплексной таблицы. Если какая либо переменная в этом столбце отсутствует, то в оптимальном плане она равна 0.
Значение целевой функции также берется из столбца ЗБП последнего оптимального плана. Оптимальный вектор переменных обозначаем X*, а оптимальное значение целевой функции F max(X*)
При решении задачи планирования товарооборота( задача о распределе6нии ресурсов), основные переменные указывают на количество реализуемой продукции каждого вида, для получения max дохода. А дополнительные переменные указывают на количество недоиспользованных ресурсов каждого вида. Если какая нибудь дополнительная переменная равна 0, то соответствующий ей ресурс использован полностью и является дефицитным. Положительное значение дополнительной переменной говорит о имеющихся излишках ресурсов.
Нулевое значение какой-либо основной переменной говорит о том, что соответствующий товар невыгоден, его реализация нерентабельна.
Вывод о количестве оптимальных решений можно сделать по индексной строке оптимального плана. Если в индексной строке 0 соответствуют только столбцам базисных переменных, то полученное оптимальное решение единственно. Если 0 соответствует небазисной переменной, то задача будет иметь альтернативный оптимум.
Альтернативный оптимум можно найти, если принять за ведущий столбец, столбец с небазисным 0. При этом среди элементов данного столбца должен быть один положительный.
Если известны два оптимальных решения, то в задачи с альтернативным оптимумом можно записать бесконечное множество оптимальных решений, но все они будут линейными комбинациями найденных оптимальных решений.
Xопт =t *X*+ (1-t)X**
X*- первое оптимальное решение
X**- второе оптимальное решение
0<=t<=1
Если в ходе решения в ведущем столбце все коэффициенты aij оказались <=0, то целевая функция F(X)- неограниченна на множестве допустимых решений. А значит, оптимального решения задача не имеет.
Если в ходе последнем столбце симплексной таблицы оказалось сразу несколько одинаковых наименьших элементов, то опорный план считается вырожденным, а дальнейшие решения может привести к зацикливанию. Для определения ведущей строки в данном случае применяется метод Креко: рассматривают все строки претендующие на ведущую, в каждой из них находят предполагаемый разрешающий элемент. Элементы каждой строки делят на свой разрешающий элемент, а результаты записывают в дополнительные строки симплексной таблицы.
Дополнительные строки сравнивают между собой двигаясь слева на право по столбцам, сравнение проводят до тех пор пока не встретится наименьший элемент. Он и определит ведущую строку в рассматриваемом плане.
Метод искусственного базиса на примере системы ограничений, содержащей уравнения.
Заметим что классический симплексный метод основывается на задаче с системой ограничений вида <=, на первом шаге такой задачи ее условий приводятся к канонической форме. Тем самым образуется базис для построения начального решения.
Если задача сразу представлена в канонической форме, то в ней как правило отсутствуют переменные выполняющие роль базисных. Введение же дополнительных переменных нарушит каноническую форму и не позволит реализовать алгоритм симплексного метода. В этом случае прибегают к методу искусственного базиса.
F(X)=c1x1+c2x2+…..+cnxn àextr
A11x1+a12x2+….+a1nxn=b1
A21x1+a22x2+….+a2nxn=b2
…………………………
Am1x1+am2x2+….+amnxn=bm
xj =>0; j=1,n
введем m- искусственных переменных yi=0;i=1,m. каждая искусственная переменная вводится только в одно уравнение системы, и так как они заведомо равны 0, то знак равенства не изменяется
A11x1+a12x2+….+a1nxn+y1=b1
A21x1+a22x2+….+a2nxn+y2=b2
…………………………
Am1x1+am2x2+….+amnxn+ym=bm
xj >=0; j=1,n
y>=i0; i=1,m
Использование искусственных переменных в системе ограничений приводит к тому, что на целевую функцию накладывается так называемый штраф в виде бесконечно большой положительной величины, точное значение которой не задается, а используется обозначение М. При решении задачи на min целевая функция примет вид:
F(X)=c1x1+c2x2+…..+cnxn+My1+My2+….+Mym min
При решении задачи на max целевая функция примет вид:
F(X)=c1x1+c2x2+…..+cnxn+My1+My2+….+Mym max
Дальнейшее решение будет протекать по следующим этапам:
1. Необходимо выразить искусственные переменные через основные
2. Полученные выражения подставить в целевую функцию
3. Выполнить тождественное преобразование целевой функции ( раскрыт скобки, привести подобные)
4. В результате целевая функция будет содержать только основные переменные, но коэффициенты при них будут содержать штрафы М
5. Для преобразования целевой функции и преобразованной системы ограничений находим начальное опорное решение, обычным симплексным методом
Заметим, что в результате преобразования целевой функции появляется свободный член, а значит, первоначальное значение целевой функции будет отлично от 0.
6. Дальнейшее решение продолжаем по алгоритму классического симплексного метода. На каждом шаге нужно стараться исключить искусственные переменные из базисных. В отличном от решении должны статься только основные переменные.
Причем их значение должны освободиться от штрафа М. Штрафы останутся только в индексной строке искусственных переменных.