Курсовая работа: Применение симплекс-метода
xb i Ü xb i — q * , i ¹ r,
xb r Ü q
и переходим к этапу 2.
Этот вариант называют также модифицированным симплекс-методом, поскольку он уменьшает объем вычислений на каждом шаге. Идея заключается в том, что на каждом шаге конаническую форму задачи для текущего базиса можно получить независимо от других таких форм непосредственно из исходной записи стандартной задачи ЛП. Для этого нужно: (1) сохранять исходную запись задачи на протяжении всей работы метода, это та цена, которую приходится платить за больше быстродействие;
(2) использовать так называемые симплекс – множители π – коэффициенты для непосредственного перехода от исходной записи задачи к ее текущей конанической форме базиса; и (3) использовать обращенный базис В־¹ - матрицу размера m x m, позволяющую вычислять на каждом шаге ведущий столбец a΄s и обновлять симплекс – множители π.
Преимущества метода
Улучшенный симплекс-метод, обладает значительными преимуществами по сравнению со стандартной формой. Это относится к точности, скорости и требованиям к памяти. Большая часть этих преимуществ определяется тем фактором, что, как правило, матрицы больших линейных задач (то есть с n>m>100) являются слабозаполненными, содержат малый процент ненулевых элементов.
Обычной является плотность 5% или менее. Улучшенная форма симплекс-метода в большей степени способна использовать преимущества, вытекающие из этого факта. В этой форме характеристические разности и ведущий вектор вычисляются непосредственно по исходным данным. Поскольку исходная матрица слабозаполнена, а перемножение следует производить только тогда, когда оба сомножителя отличны от нуля, то время вычислений значительно сокращается.
В дополнение к этому использование только исходных данных приводит к тому, что уменьшается возможность накопления ошибок округления. Наоборот, стандартные симплексные таблицы, даже если они первоначально являются слабозаполненными, в ходе итеративного процесса быстро заполняются ненулевыми элементами. Таким образом, время вычислений увеличивается, и, поскольку каждая таблица вычисляется из предшествующей, накопление ошибок может начать играть более серьезную роль.
Математическая постановка задачи
Задание: Найти такие неотрицательные x1, x2, что
2х1 – х2 ≤ 4,
x1 – 2x2 ≤ 2,
x1 + x2 ≤ 5,
и минимизировать функцию -3x1 + x2 = z.
Графическое решение (см. рисунок) показывает, что точка минимума – это точка (3,2), где z = -7. Вырожденность (при обращении нескольких переменных в 0, базис называют вырожденным) возникает, поскольку прямые, соответствующие ограничениям, пересекаются в одной точке (2,0). В нашей задаче в вершине пересекаются три прямые (обычно вершина является пересечением всего двух прямых).
Рисунок 1.
При использовании симплекс-метода первая таблица имеет следующий вид:
Таблица 1.
|
Итерация |
Базис |
Значение |
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
|
0 |
Х3 К-во Просмотров: 688
Бесплатно скачать Курсовая работа: Применение симплекс-метода
|