Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
4.Симплекс-метод численного решения задачи ЛП.
Существует несколько форм симплекс-метода: с короткой матрицей, с расширенной матрицей, двойственный алгоритм, модифицированный. При рассмотрении алгоритма с короткой матрицей будем считать, что задача дана на максимум целевой функции. Если задача дана на минимум, то ее можно привести к задаче на максимум, изменив знак целевой функции. Для применения симплекс-метода ЗЛП должна быть представлена в канонической форме (4.5). Если в системе ограничений (4.5) m < n и все уравнения линейно независимы, то эту систему можно разрешить относительно тех m переменных, которым в матрице ограничений соответствуют линейно независимые столбцы. Пусть независимыми будут первые m столбцов, тогда ограничения задачи (4.5) можно разрешить относительно Х1, Х2, …, Хm(4.8) :
Переменные Х1, Х2, …, Хm будут базисными, а переменные Хm + 1,
Хm + 2, …, Хn – свободными.
Целевую функцию надо выразить через свободные переменные (4.9):
Симплекс-алгоритм носит итеративный характер и состоит в построении и последовательном преобразовании симплексной таблицы, в результате которого от начального плана можно за конечное число шагов получить оптимальный план, либо установить, что ЗЛП не имеет решения. Задачу (4.8), (4.9), разрешенную относительно базисных переменных, удобно представить в виде симплексной таблицы.
В F-строке записаны коэффициенты модифицированной целевой функции с обратными знаками, b0 – это значение функции при нулевых значениях свободных переменных. Если в столбце свободных членов все коэффициенты bio ≥ 0, то вектор Х = (Х1 = b10, Х2 = b20, …, Хm = bm0, Хm + 1 = 0, ..., Хn = 0) называется начальным опорным планом. Значение целевой функции равно элементу В-столбца в F-строке.
Решение задачи линейного программирования u1089 симплексным методом проводится в два этапа. Сначала находится начальное базисное решение, а затем проводится направленный перебор базисных решений для получения оптимального плана.
Алгоритм построения начального опорного плана:
1. Отыскание разрешающего столбца(r) (минимальный отрицательный элемент).
2. Выбор разрешающей строки(s) (по наименьшему полож. симплексному отношению элементов столбца свободных членов к элементам разрешающего столбца (кроме F-строки).
3. Выбор разрешающего элемента (Аsr).
4. Симплексные преобразования таблицы:
- х-переменные разрешающих столбца и строки меняются местами;
- разрешающий элемент заменяется обратной величиной;
- остальные элементы разрешающего столбца делятся на разрешающий элемент и меняют знак на противоположный;
- остальные элементы разрешающей строки делятся на разрешающий элемент;
- все прочие элементы таблицы вычисляются по методу прямоугольника по формуле (4.10):
В результате выполнения этого шага переменная xr становится базисной, а переменная xs выводится из базиса и становится свободной. После чего переходят к шагу 1.
5.Признак оптимальности опорного плана задачи ЛП.
Алгоритм нахождения оптимального плана:
1. Проверка базисного решения на оптимальность.
Если все элементы F-строки неотрицательны, то базисное решение оптимально. В противном случае оно может быть улучшено. Если все элементы F-строки положительны, то полученный оптимальный план будет единственным, если в F-строке есть нулевые элементы, то существует бесконечно много оптимальных планов.
2. Выбор разрешающего столбца.
Разрешающий столбец выбирают по минимальному отрицательному элементу F-строки. Пусть r – номер разрешающего столбца. Если в F-строке есть отрицательный элемент, в столбце которого нет положительных элементов, то целевая функция неограниченна и решения ЗЛП не существует.
3. Вычисление симплексного отношения и выбор разрешающей строки.
Разрешающая строка определяется по минимальному положительному симплексному отношению. Симплексное отношение – это отношение элементов столбца свободных членов к положительным элементам разрешающего столбца. Пусть s – номер разрешающей строки.
4. Выбор разрешающего элемента.
На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент. Обозначим его через bsr.
5. Симплексное преобразование таблицы.
Выполняется точно так же, как и в предыдущем алгоритме. После чего осуществляется переход к шагу 1.