Суть симплекс-метода

реферат
на тему:
Суть симплекс-метода
ПЛАН
1. Понятие симлекс-метода, его в решении задач
линейного программирования
2. Понятие двойственного симплекс-метода, его особенности
Список использованной литературы
1. Понятие симлекс-метода, его в решении задач
линейного программирования
Пусть требуется найти максимум функции
Z (x1, x2) = 3×1 + 2,5×2
на множестве, описываемый системой неравенств. Значение функции Z (x1, x2) = 3×1 + 2,5×2 в некоторой точке с координатами х1, х2 можно воспринимать как отклонение этой точки от прямой Z (x1, x2) = 3×1 + 2,5×2 = 0. Поэтому чем больше точка отклоняется от прямой Z (x1, x2) = О, тем большее значение имеет в этой точке функция Z (x1, x2). Кроме того, точки любой прямой, параллельной прямой Z (x1, x2) = 0, равно отклонены от прямой Z (x1, x2) = 0. Итак, точка, в которой функция Z (x1, x2) достигает наибольшего значения, должна быть точкой области, которая будет лежать на прямой, имеет с общие точки и отклонена от прямой Z (x1, x2) = О всего.
Нержавейка в Сочи
Таким образом, искомая точка может лежать только на границе области, то есть принадлежать некоторым прямым, ограничивающие область (рис. 1, 2). Отклонение такой точки от каждой из пограничных прямых, которым она принадлежит, очевидно, равна нулю.
Рис. 1 Рис. 2
Допустимый решение, в котором функция Z достигает наибольшего значения, называть оптимальным решением. Точку, соответствующую оптимальному решению, называть оптимальной точкой. Если оптимальная точка существует и единственная (на рис. 1 — точка M2), то это — некоторая вершина многоугольника. А если оптимальных точек множество (рис. 2), то к их множества относятся и некоторые вершины многоугольника (на рис. 2 — точки M1 * i М2 *). Поэтому для нахождения оптимальной точки достаточно рассматривать лишь вершины многоугольника.
Итак, из геометрического взгляда нашу задачу можно сформулировать так: среди вершин многоугольника найти такую, в которой бы функция Z (x1, x2) достигла наибольшего значения.
Симплекс-метод как раз и дает возможность найти сначала какую-то вершину многоугольника, а затем от нее перейти к той, в которой значение функции Z не меньше, чем в предыдущий.
Перейдем теперь к общему случаю. Пусть требуется найти максимум функции
Z (x) = (p, x) = p1x1 + p2x2 +. + Рnхn (1)
(или, что то же, минимум функции Z1 (x) = -Z (x)) на множестве, определяемом системой линейных неравенств
i (x) = (ai, x ) + bi = аi1x1 + ai2x2 +. + Аinхn + bi О (i = 1, 2,., M). (2)
Запишем данные нашей задачи в виде таблицы.
Таблица 1
x1 x2. xn +1
1 a11 a12. a1n b1
2 a21 a22. a2n b2
. . . . . .
m am1 am2. amn bm
Z p1 p2. pm 0
Не нарушая общности рассуждений, предположим, что ранг матрицы (aij) (i = 1, m; j = 1, n) равно n. Найдем сначала какую допустимую вершину множества решений. Пусть через n шагов Жордановых исключений иметь таблицу:
Таблица 2
2 января. n 1
x1
.
. . . . . .
xn
n + 1
.
. . . . . .
m
.
Z
.
Z (n)
Пусть вершина 1 = 0, 2 = 0,., n = 0 допустима, то есть b (n) n + 1 0,., b (n) m 0. Если при этом все коэффициенты в Z-строке неположительные, то есть р (n) 1 0, р (n) 2 0,., Р (n) n 0, то в вершине 1 = 0, 2 = 0,., N = 0 максимум функции Z (x).
Действительно, в таком случае Z (x) = р (n) 1 января (x) + р (n) 2 февраля (x) +. + Р (n) nn (x) + Z (n) Z (n) любого x, для которого 1 (x) 0, 2 (x) 0,., N (x) 0
Пусть теперь среди чисел р1 (n), р2 (n),., Рn (n) является положительные, например p1 (n)> 0. Тогда, увеличивая отклонения 1 (х) и оставляя 2 (x),., N (х) равными нулю, то есть двигаясь по «ребру» 2 (x) = 0,., N (х) = 0 в направлении увеличения 1 ( х), увеличивать и функцию Z (x). При этом, выйдя из вершины 1 = 0, 2 = 0,., N = 0, будем двигаться по упомянутому ребру до тех пор, пока впервые столкнемся с какой-то из «плоскостей», ограничивающие множество. В результате этого попадем в новую вершину множество. Рассуждая так же, как при нахождении допустимой вершины, мы приходим к следующим правилам:
1. За основной выбираем какой-либо из колонок, содержащих положительные элементы Z-строки. (Если таких элементов в Z-строки нет, точка, принадлежащая базовым плоскостям, является оптимальной).
2. В -рядках находим отрицательные элементы в основном столбце. (Если таких элементов нет, то множество ограничено, функция Z (x) на этом множестве ограничено и оптимальной точки не существует).
3. Находим меньше по абсолютной величине отрицательное отношение свободных членов -рядкив в соответствующие элементы основного столба. Строка, соответствует такому отношению, берем за основной.
4. С выбранным таким образом основным элементом выполняем шаг Жорданова исключения. Получив новую таблицу (новую допустимую вершину), снова возвращаемся к правилу 1.
за конечное число шагов найдем оптимальную точку или установим, что таковой не существует. Возможно зацикливания при этом преодолеваем так же, как и при решении системы неравенств.
только описанный метод решения задачи линейного программирования (и системы линейных неравенств) называется симплекс-методом.
2. Понятие двойственного симплекс-метода, его особенности
В оптимальной точке вектор р — градиент целевой функции Z (x) = (p, x) выражается через градиенты (нормальные векторы) ai базовых плоскостей i (x) = 0 с неположительные коэффициентами . Если, например, в таблице 10 точка х *, принадлежащий плоскостям 1 (x) = 0, 2 (x) = 0,., N (x) = 0, оптимальная, то есть числа р1 (n), р2 (n) ,., Рn (n) неположительные, то
p = p1 (n) a1 + p2 (n) a2 +. + Pn (n) an. (3)
Такое равенство является достаточным условием того, что точка х *, которая принадлежит плоскостям 1 (x) = 0, 2 (x) = 0,., N (x) = 0, оптимальная на множестве точек, которые удовлетворяют неравенству 1 (x) 0, 2 (x) 0,., n (x) 0
Действительно, для любого х, удовлетворяющее неравенству 1 (x) 0, 2 (x) 0, ., n (x) 0, если р i (n) 0. Тогда в -рядках в колонке, содержащей р1 (n)> 0, найдем отрицательный элемент. Если такого нет, то родами допустимой точки не существует. При этом отклонение 1 можно сделать сколь угодно большим, и при достаточно большом 1 все отклонения n + 1,., M станут неотъемлемыми (если все an + 11 (n)> 0, an + 21 (n)> 0,. , am1 (n)> 0). Это означает, что область не ограничено и функция Z (x) в этой области не достигает наибольшего значения (оно бесконечно большое). Оптимальной точки в таком случае иcнуе (рис. 2).
Пусть в колонке, содержащий р1 (n)> 0, является отрицательный элемент, например an + 11 (n) <0. Тогда строка, содержащая этот отрицательный элемент, возьмем основным и найдем все отрицательные отношение элементов Z-строки к соответствующим элементам основной строки (свободные члены не в счет). Меньше по модулю отрицательное отношение определяет основной столбик. С найденным таким образом основным элементом, принадлежит основном строке и основном столбце, выполняем один крокжорданового исключения. Если все указанные маленькие отрицательные отношение отличаются от нуля, то через конечное число шагов или будет найдено родами-допустимую точку, или выяснится, что ее не существует.
Пусть теперь в таблице 10 все элементы Z-строки неположительные, то есть мы имеем родами-допустимую точку. Если при этом все свободные члены в -рядках неотъемлемые, то есть bn + 1 (n) 0, bn + 2 (n) 0,., Bm (n) 0, то точка также допустима, то есть оптимальна.
Предположим, что среди свободных членов bn + 1 (n), bn + 2 (n),., bm (n) является отрицательные. Тогда мы должны с данной родами допустимой точки перейти к другой родами допустимой так, чтобы, по возможности, избавиться отрицательных свободных членов в -рядках. Итак, если в прямом симплекс-методе переходят от одной допустимой вершины к другой так, что функция Z (x) при этом увеличивалась, и двигаются по допустимым вершинах до тех пор, пока достигнут допустимой вершины, которая одновременно будет и родами-допустимой, то в двойственном симплекс-методе движутся по родами допустимых вершинах, приближаясь к области, пока не получат родами допустимой вершины, которая будет одновременно и допустимой. При переходе от одной родами допустимой вершины к другой значение функции Z (x) уменьшается (во всяком совете не увеличивается). Итак, если множество не пустая, то max Z (x) = min Z (x), где * (не пустая) множество всех родами допустимых точек. Это является так называемый принцип двойственности. Чтобы перейти от одной родами допустимой вершины к другой, в -рядку с отрицательным свободным членом отыскиваем положительные элементы. Если таковых нет, то система неравенств несовместима, множество пустая и оптимальной точки не существует (потому что не существует допустимых точек). Пусть такие элементы есть. Тогда этот -строчка берем основным и снова находим меньше по модулю отрицательное отношение элементов Z-строки к соответствующим элементам основной строки. Такое отношение определяет основной элемент. С определенным таким образом основным элементом выполняем шаг Жорданова исключения. Если все указанные малейшие отношения не равны нулю, то через конечное число шагов или получим допустимую, а следовательно, и оптимальную, вершину или выясним, что система несовместима.
Список использованной литературы
1. Вентцель Е.С. Исследование операций. — М .: Знание, 1978.
2. Зайченко Ю.П. Исследование операций. — М .: Высшая школа, 1999.
3. Катренко А.В. Исследование операций. Учебник. — Львов, 2004.
4. Ржевский С.В. Элементы исследования операций. — М., 1999.
5. Справочник по математике для экономистов / Под ред. Ермолаева В.И. — М .: Высшая школа, 1997.

Комментирование и размещение ссылок запрещено.

Комментарии закрыты.