Решение и постоптимальный анализ задачи линейного программирования

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

БЕРДЯНСКИЙ УНИВЕРСИТЕТ МЕНЕДЖМЕНТА И БИЗНЕСА

КАФЕДРА МАТЕМАТИКИ ТА МАТЕМАТИЧНИХ МЕТ0ДИВ

КУРСОВАЯ РАБОТА

по дисциплине

«Математические методы исследования операций»

на тему

 

Решение и постоптимальный анализ задачи линейного программирования

Вариант № 3 / 4

1 .Теоретические сведения

 

1.1 Симплекс-метод

 

Теорема (фундаментальная). Если ЗЛП имеет оптимальное решение (в ограниченной области всегда, а в неограниченной - в зависимости от ограниченности целевой функции Z), то оно совпадает, по крайней мере, с одним из допустимых базисных решений (ДБР) системы ограничений.

Согласно фундаментальной теореме вместо исследования бесконечного множества допустимых решений, необходимо исследовать лишь конечное число ДБР. Таким образом, принципиальная схема решения ЗЛП такова:

найти все ДБР;

вычислить для каждого из них соответствующее значение ЦФ z;

сравнить и определить наилучшее.

Но, в общем случае при больших значениях п и т количество ДБР может быть огромным (порядка С _п^т) и практическое осуществление перебора всех ДБР станет невозможным. Эти трудности обусловлены тем, что указанная принципиальная схема связана с беспорядочным перебором ДБР, без учета, насколько новое проверяемое ДБР изменяет ЦФ z и приближает ли оно нас к искомому оптимуму. Если же указанный перебор ДБР производить целеустремленно, добиваясь на каждом шаге монотонного изменения ЦФ z, т.е. чтобы каждое следующее ДБР было лучше предыдущего (или по крайней мере не хуже), то число анализируемых ДБР можно резко сократить.

Основной метод решения ЗЛП - симплекс-метод - базируется на идее последовательного улучшения решения. Очевидно, что для реализации этой идеи метод должен включать три основных элемента:

> способ определения исходного ДБР;

> правило перехода к следующему "лучшему" ДБР;

> критерий, по которому можно определить оптимальность найденного решения или необходимость его дальнейшего улучшения.

Табличный симплекс-метод

Пусть для исходной ЗЛП задано начальное ДБР, базис которого образуют первые т столбцов матрицы А. Введем новую переменную z и с помощью элементарных преобразований Жордана-Гаусса преобразуем расширенную систему к диагональной форме относительно переменных z,x₁,x₂,...,x_m :

Данной диагональной форме в дальнейшем будем ставить в соответствие следующую таблицу:

В дальнейшем второй столбец будем опускать!

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

Схема табличного симплекс-метода.

Шаг 0. Начальный шаг.

Пусть задано ДБР х° исходной задачи. Построим соответствующую этому ДБР х° симплекс-таблицу.

Шаг 1. Проверка условия оптимальности.

Если коэффициенты z-строки d_0J, j = 1,m неотрицательные, то прекратить вычисления: текущей симплекс-таблице соответствует оптимальное ДБР.

Шаг 2. Выбор ведущего столбца.

Среди коэффициентов d₀j,j = 1,n выбрать отрицательный. Пусть мы выбрали d_0p. Тогда р-й столбец будет ведущим. Переменная х_р будет вводиться во множество базисных переменных.

Шаг 3. Выбор ведущей строки.

Если коэффициенты a_ip,i = 1,m неположительные, то прекратить вычисления:

целевая функция не ограничена сверху, иначе выбрать q-ую строку, для которой q-ая строка называется ведущей.

Элемент таблицы a_qp на пересечении ведущих строки и столбца называется ведущим элементом.

Шаг 4. Переход к новой симплекс-таблице.

Используя преобразования Жордана-Гаусса над СЛАУ, в симплекс-таблице сделать ведущий элемент равным единице, а все остальные коэффициенты ведущего столбца равными нулю. Слева от таблицы в q-ой строке запишем переменную х_р.

Перейти на шаг 1.

 

1.2 Постоптимальный анализ

 

Постоптимальный анализ (анализ моделей на чувствительность) – это процесс, реализуемый после того, как оптимальное решение задачи получено. В рамках такого анализа выявляется чувствительность оптимального решения к определенным изменениям исходной модели. Иными словами, анализируется влияние возможных изменений исходных условий на полученное ранее оптимальное решение. Важность этого анализа ЗЛП объясняется также ещё и тем, что большая часть параметров ЗЛП точно не известна, и на практике обычно берутся приближенные значения параметров.

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

В постоптимальном анализе исследуются три класса параметров:

1. Компоненты вектора ограничений b_t

После нахождения оптимального решения .представляется вполне логичным выяснить, как отразится на оптимальном решении изменение запасов ресурсов. Отметим, что неравенства модели типа "<" обычно могут быть интерпретированы, как ограничения на использование лимитированного ресурса. А ограничения типа ">" могут быть интерпретированы, как некоторые требования к моделируемому процессу.

При анализе изменений запасов ресурсов особенно важны два следующих аспекта:

> На сколько можно увеличить (уменьшить) запас некоторого ресурса для улучшения полученного оптимального значения целевой функции z?

> На сколько можно снизить (увеличить) запас некоторого ресурса при сохранении полученного оптимального значения целевой функции z?

2. Коэффициенты ЦФ Cj

Определяется пределы допустимых изменений коэффициентов целевой функции.

> Каков диапазон изменения (увеличения или уменьшения) того или иного коэффициента целевой функции, при котором не происходит изменение оптимального решения?

> Насколько следует изменить тот или иной коэффициент целевой функции, чтобы сделать некоторый недефицитный ресурс дефицитным и, наоборот, дефицитный ресурс сделать недефицитным?

1. Существует диапазон изменения А коэффициентов ЦФ как базисных, так и небазисных переменных, в которых текущее оптимальное решение остается оптимальным.

- для небазисных переменных существует только нижняя или верхняя граница;

- для базисных - обычно существуют и нижняя и верхняя границы.