Полная версия

Главная arrow Туризм arrow Основы функционирования систем сервиса

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

СИМПЛЕКС-МЕТОД

Алгоритм симплекс-метода

Симплекс-метод заключается в нахождении и тестировании вершины (угла), являющейся решением задачи ЛП [44]. На каждом этапе метод выделяет вершину и соответствующие ей переменные, которые обеспечивают движение к минимуму (максимуму) с наибольшей скоростью. Выбранная переменная заменяет другую, наиболее ограничивающую. Симплекс-метод позволяет также определить, существует ли решение. Реализующий симплекс-метод алгоритм можно записать в виде:

Шаг 1. Определяется некоторая вершина в ОДР, соответствующая базисным допустимым решениям (переменным), найденным путем выделения из матрицы т — линейно независимых столбцов и приравнивания нулю всех других переменных , соответствующих другим столбцам матрицы.

Шаг 2. Выбирается из всех возможных оставшихся п — т ребер, соответствующих небазисным переменным, ребро (переменная), которое приводит при движении по нему к наискорейшему уменьшению целевой функции.

Шаг 3. Осуществляется как бы движение от начальной вершины вдоль выбранного ребра к другой вершине, которая дает новое решение, имеющее меньшее значение ЦФ. Новая вершина образуется путем замены базисной переменной (ребра) на новую базисную переменную (ребро).

Далее алгоритм возвращается к шагу 2 и завершается, когда будет достигнута вершина, из которой уже нельзя двигаться по ребрам без уменьшения целевой функции при поиске максимума.

Столбцы и элементы векторов обычно упорядочиваются и записываются в виде симплекс-таблицы, образование которой будет показано ниже.

Симплекс-метод решает задачу Л П в стандартной форме.

Минимизировать (максимизировать) функцию при условиях х > 0; Ах = Ь.

Матрица А действительная, имеет размерность т х «и ранг т.

Сформулированную задачу ЛП можно также записать в виде

Исходя из записи задачи ЛП в виде (8Л) можно сказать, что расширенная матрица

размерности (т + 1) (п + 2) соответствует решениям[х/]т.

Представим матрицу А в виде совокупности столбцов [44]

Так как матрица А имеет ранг т, то найдутся т линейно независимых столбцов матрицы А, например {аУ1 ,...,аУ/и Рассмотрим вектор х° > 0, такой, что все его п — т элементов равны 0 и Ах° = Ь. Пусть это будут элементы с номерами ... , in_m. Предположим также, что место расположения aw линейно независимых столбцов матрицы А соответствует месту расположения ненулевых элементов векторах0. Геометрически, согласно утверждению 3 § 7.6, это означает, что х° является вершиной (углом) ОДР и, кроме того, удовлетворяет заданным условиям. Такое решение называется допустимым базисным решением. Углы допустимого множества являются допустимыми базисными решениями.

Напомним, что множество базисных решений содержит всю информацию, необходимую для оптимального решения задачи ЛП. Для рассмотренного в § 7.6 двумерного случая базисными решениями являются все 6 точек, а допустимыми базисными решениями являются точки Л, В, Си 0.

Таким образом, любой аналогичный х° вектор х можно записать как

где хв — вектор, элементы которого сответствуют линейно независимым столбцам матрицы A; xF вектор с нулевыми элементами.

Аналогично определим векторы

Переменные, являющиеся элементами вектора хв, называются базисными переменными, а переменные, являющиеся элементами вектора xF, называются свободными (небазисными) переменными.

Так как F =0, то значение целевой функции для начального вектора х° будет равно

где/° — значение /в точке х°.

Решение (8.1) вида [х°/°]т при х > 0 называется очевидным {явным) решением. Таким образом, если приравнять нулю небазисные переменные, получается очевидное решение.

Для удобства переставим т линейно независимых столбцов матрицы А в левую часть и запишем матрицу в виде

Здесь матрица В соответствует т линейно независимым столбцам имеет размерность тх т и ранг т, а матрица F

является тх (п — т) матрицей. Так как матрица В состоит из линейно независимых столбцов, то она имеет обратную В-1 и detB ф 0. Отметим, что для образования матрицы В можно выбрать любые т линейно независимых столбцов матрицы А.

Представим задачу (8.1) с учетом введенных обозначений

Данному представлению соответствует расширенная матрица Предположим, что

откуда следует

Если вектор хв будет решением системы Вхй=Ь, то он будет базисным решением. Если выполняется неравенство в = В-1Ь > О, тогда хв будет допустимым решением.

Таким образом, текущее решение удовлетворяет следующему уравнению:

Рассмотрим матрицу (8.4). Базисные переменные будут представлены в явном виде, если заменить матрицу В единичной матрицей I. Умножив первую строку матрицы (8.4) слева на В~1, получим

где В_1Ь > О, т.е. т верхних элементов в правом столбце неотрицательны и представляют собой текущее значение переменных.

В левой стороне верхней строки получилась единичная матрица: В-1 В = I. Данное представление очень удобно, так как при умножении на вектор хв каждая переменная будет находиться в отдельной строке.

Таким образом, базисное решение, которое будем считать допустимым и соответствующим базису В, есть хт = [хв 0], где хв = = В_1Ь. Базисное решение является результатом предположения, что xF= 0. Однако, если xF* 0, то х^может быть вычислено какх5= = B~'b — B^'Fx/r. Подставив это выражение в целевую функцию (функцию стоимости), получим

Так как необходимо определить зависимость стоимости от небазисных переменных, одну из которых затем включить в базисные, то нижняя строка под матрицей I должна быть нулевой. Для этого в (8.7) умножим первую строку (матрицы) на св и сложим со второй

где — значение целевой функции для начального век

тора х0 из (8.3).

Матрица (8.8) называется симплекс-таблицей. Приведение ее к данному виду является начальным этапом симплекс-алгоритма. В процессе выполнения алгоритма осуществляется переход от одной таблицы к другой, пока нижний правый элемент таблицы не станет максимальным или минимальным.

С использованием симплекс-таблицы легко увидеть допустимое решение. Переменные xFсоответствуют нулевой подматрице, переменные хв — единичной матрице:

Предположим, что задача Л П приведена к стандартной форме, вычислена симплекс-таблица и выбрано начальное базисное решение, соответствующее вершине многогранника решений.

Тогда — решение задачи (8.1). Так

как b > О, это решение базисное допустимое.

Представим матрицу (8.9) в более удобном виде, сохранив основные обозначения:

Рассмотрим отдельно задачи максимизации и минимизации.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>