Специальные задачи линейного программирования

1. Заполнить все возможные сочетания допустимых значений ₁, ₂, ₃.
2. Определить и записать значения левых частей ограничений (1)-(4) и целевой функции.
3. Вычеркнуть те варианты, в которых не удовлетворяется хотя бы одно ограничение, как приводящие к недопустимым решениям.
4. Из оставшихся вариантов принимается тот, в котором целевая функция максимальна. В примере max L = 8 — в шестом варианте (оптимальном), в котором = = 1; .

    Из  этого примера видно, что в данном случае всего вариантов будет 2³ = 8 и для каждого варианта надо вычислить четыре ограничения и целевую функцию, т. е. выполнить N = 8(4 + 1) = 40 вычислительных операции. Значит, в общем случае N = 2ⁿ(m + 1), где n — число переменных, m – число ограничений. Следовательно, при увеличении размерности задачи число вычислений резко возрастает (табл. 6).

Таблица 6.

    Для сокращения трудоемкости полного перебора применяют различные методы.

    Метод фильтрующего ограничения предполагает следующую последовательность действий.

1. Принимают некоторые значения ₁, ₂, ₃, например: 1, 0, 0.
2. Определяют значение целевой функции при таком на боре переменных L = 3₁ - 2₂ + 5₃ = 3*1 – 2*0 + 5*0 = 3.
3. Далее устанавливают новые значения переменных и целевой функции; причем если полученная целевая функция меньше 3, то этот вариант не рассматривают. Дли исключения возможного рассмотрения такого варианта, вводят дополнительное ограничение 3₁ - 2₂ + 5₃ ≥ 3, которое называют фильтром (Ф).
4. Составляют таблицу (табл. 7), в которой для каждого варианта проверяют выполнение всех ограничений, включая Ф.

    Если  вычисление прекращается и величины не определены, то в клетках таблицы ставится прочерк.

    Введение  фильтрующего ограничения Ф привело  к сокращению числа вычисляемых величин (24 вместо 40, т. е. 60%).

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

    Например, из таблицы видно, что в пятом  варианте Ф = 5. Поэтому для дальнейших вычислений в качестве фильтрующего ограничения принимаем 3₁ - 2₂ + 5₃ ≥ 5 (Ф₁). Однако для следующего варианта значение целевой функции будет еще больше (Ф = 8) и в качестве фильтрующего ограничения принимается 3₁ - 2₂ + 5₃ ≥ 8 (Ф₂). Для седьмого и восьмого вариантов значение целевой функции не удовлетворяет требованиям фильтра Ф₂ и значения ограничений не вычисляем. Значит, трехкратный фильтр (Ф, Ф₁, Ф₂) позволил сократить вычисления еще на 4, т. е. надо выполнить 20 вычислений вместо 40 (50%). Более значительное сокращение трудоемкости достигается методом Беллмана с фильтром, где наибольший Ф получают сразу. 
 
 
 
 
 
 
 

    Заключение

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

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

Список  используемой литературы

1. Глухов В. В., Медников М. Д., Коробко С. Б. Математические методы и модели для менеджмента.2-е изд., испр. и доп. – СПб.: Издательство «Лань», 2005. – 5 с. – (Учебники для вузов. Специальная литература).

2. «Исследование операций в экономике»: Учебное пособие для вузов / Кремер Н. Ш., Путко Б. А., Тришин И. М., Фридман М. Н.: под ред. проф. Кремера Н. Ш. – М.: ЮНИТИ, 2004

3. Харчистов  Б.Ф. Методы оптимизации: Учебное  пособие. - Таганрог: Изд-вo ТРТУ, 2004. - 140с.

4. «Линейное и нелинейное программирование» под общей редакцией профессора Ляшенко И. Н., Киев – 1975

5. «Математические методы и модели в коммерческой деятельности»: Учебник, 2-е изд., перераб. и дополн. / Фомин Г. П. – М: Финансы и статистика, 2005

6. «Математические методы и модели исследования операций»: Учебное пособие / Кутузов А. Л. – издательство СПб ГПУ, 2005

7. «Математические методы: Учебник» / Партика Т. Л., Попов И. И. – М: ФОРУМ: ИНФРА, 2005