Решение задач линейной оптимизации симплекс – методом
Реферат - Математика и статистика
Другие рефераты по предмету Математика и статистика
?лана смешения компонентов полностью повторяет решение, рассмотренное в завершающей части п.4 (см. стр.11-12).
7.Формирование двойственной задачи
Произвольной задаче линейного программирования определенным образом соответствует некоторая другая задача линейного программирования. Будем называть ее двойственной, а первоначальную задачу исходной.
Обозначим
; ; ; ; (7.1)
Теперь исходная задача (2.1)-(2.3) в канонической форме может быть записана в матричном виде следующим образом.
Требуется определить вектор , обращающий в максимум
.(7.2)
при условиях
AX=B;(7.3)
.(7.4)
Тогда двойственная задача определить вектор , обращающий в минимум
f(Y)=YB(7.5)
при условиях
.(7.6)
Транспонируя обе части неравенства (7.6), записанного в виде строки, и учитывая , получим
.(7.7)
Отметим, что в двойственной задаче переменные yi могут быть и отрицательными.
Рассмотрим в качестве исходной задачу (2.12),(2.13). С учетом (7.1) и (7.7) запишем
С=(120,100,150,0,0,0,0,0), B=(,,,, ),
.
Двойственная задача имеет вид
;(7.8)
(7.9)
8.Формирование оптимального решения двойственной задачи на основе теоремы о двойственности
Оказывается, что для задач (7.2)-(7.4) и (7.5),(7.6), называемых двойственной парой, справедлива следующая теорема.
Теорема (первая теорема о двойственности).Если одна из задач двойственной пары (7.2)-(7.4) и (7.5),(7.6) имеет решение, то другая задача также разрешима. При этом для любых оптимальных планов и (здесь Мх,Му множества планов соответственно прямой и двойственной задач) задач (7.2)-(7.4) и (7.5),(7.6) имеет место равенство
.
Если линейная форма одной из задач не ограничена (для F(X) сверху, для f(Y) - снизу), то другая задача не имеет ни одного плана.
Оптимальное решение двойственной задачи может быть найдено на основе следующего следствия из этой теоремы.
Следствие.Если вектор является оптимальным опорным планом задачи (7.2)-(7.4), то вектор (8.1), является оптимальным опорным планом задачи (7.5),(7.6).
Стоит отметить, что в ходе решения исходной задачи вторым алгоритмом, при каждом шаге вычисляется вектор . И если Х оптимальный опорный план задачи (7.2)-(7.4), то в (m+1)-й строке, соответствующей основной таблице, находится решение задачи (7.5),(7.6).
Пусть двойственная задача имеет вид (7.8),(7.9).
Так как исходная задача (2.12),(2.13) имеет решение, то на основании рассмотренной теоремы о двойственности двойственная задача также разрешима.
Оптимальным опорным планом исходной является (см.п.4, п.6). При этом
;
; .
Вычислим
.
На основании следствия из теоремы о двойственности можно заключить, что является оптимальным планом двойственной задачи, при котором . Анализируя (m+1)-ю строку основной таблицы (см.табл.6.3, шаг5), можно убедиться в том, что оптимальный план двойственной задачи, сформированный на основе теоремы о двойственности, совпадает с оптимальным планом, найденном при решении исходной задачи вторым алгоритмом симплекс-метода. Это говорит о том, что оптимальный план задачи (7.8)-(7.9) найден верно.
9.Анализ результатов и выводы
В данной работе рассматриваются два способа решения исходной задачи линейного программирования.
Первый заключается в том, что сначала решается вспомогательная задача (L-задача), позволяющая построить начальный опорный план, затем на основе этого найденного плана решается исходная задача (определяется ее оптимальный план). Второй способ является объединением двух этапов и состоит в решении расширенной задачи (M-задачи), также приводящей к нахождению оптимального плана исходной задачи.
Вычислительную основу этих двух способов решения составляют соответственно первый и второй алгоритмы симплекс-метода. Один из параметров, по которому может быть оценен любой итерационный алгоритм количество шагов, приводящих к решению задачи или установлению ее неразрешимости. Для данной задачи наиболее эффективным методом оказался первый метод(L-задача + исходная задача), т.к. он привел к решению за 4 шага, а второй метод (M-задача) за 5 шагов. Разница в числе шагов, вероятно, обусловлена неоднозначность выбора разрешающего элемента в исходной таблице L-задачи (3.2.1).
Сравнение количества вычислений на каждой итерации приводит к следующим оценочным результатам рассматриваемых алгоритмов. Преимущественная часть вычислений на каждом шаге алгоритмов определяется размерностью главной части таблицы (в первом алгоритме) или основной таблицы (во втором алгоритме). В первом случае она имеет размерность (m+1)x(n+1), во втором - (m+1)x(m+1). Даже учитывая, что второй алгоритм требует построения вспомогательной таблицы, он оказывается более компактным.
Еще одно несомненное достоинство второго алгоритма заключается в возможности определения оптимального плана двойственной задачи из (m+1)-й строки основной таблицы, соответствующей последней итерации, без всяких дополнительных вычислений.