- •Оглавление
- •Раздел 1. Линейная оптимизация 6
- •Раздел 2. Методы решения задачи многокритериальной оптимизации 19
- •Раздел 3. Применение matlab и excel для решения задач многокритериальной оптимизации 41
- •Перечень условных обозначений, символов, сокращений и терминов
- •Введение
- •Раздел 1. Линейная оптимизация
- •1.1. Линейное программирование
- •1.2. Многокритериальная оптимизация
- •Раздел 2. Методы решения задачи многокритериальной оптимизации
- •2.1. Метод последовательных уступок
- •2.2. Метод главного критерия
- •2.3. Метод свертывания критериев
- •Раздел 3. Применение matlab и excel для решения задач многокритериальной оптимизации
- •3.1. Пакет matlab
- •3.1.2. Toolboxes и его виды
- •3.1.3. Реализация генетического алгоритма в пакете matlab
- •3.2. Решения экономическую модель с помощью инструмента matlab
- •3.3. Решения экономическую задачу многокритериальной оптимизации с помощью ms Excel
- •3.3.1. Метод последовательных уступок
- •3.3.2. Метод главного критерия
- •3.3.3. Метод свертка критериев
- •3.4. Анализ полученных результатов
- •Заключение
- •Список использованной литературы
- •Приложения
Раздел 1. Линейная оптимизация
Многие проблемы, возникающие в экономических исследованиях, планировании и управлении, будучи сформулированными математически, представляют собой задачи, в которых необходимо решить систему линейных алгебраических уравнений или неравенств и среди всех неотрицательных решений найти то решение, при котором линейная функция принимает наибольшее или наименьшее значение. Изучение методов исследования и решения математических задач указанного типа составляет содержание раздела математики, который называется линейным программированием [12,17].
Традиционный подход исследования операций предполагается наличие единственного критерия оценки качества решения. Однако, расширение области применения методов исследования операций привело к тому, что аналитики стали сталкиваться с задачами, в которых существенным оказывается наличие нескольких критериев оценки качества решения. Такие задачи носят название многокритериальной задачей оптимизации [36,51].
1.1. Линейное программирование
В настоящее время оптимизация практически неотъемлемая часть в науке, технике, экономике и в любой другой области человеческой деятельности.
Оптимизация – целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях [44,46].
Поиски оптимальных решений привели к созданию специальных математических методов и уже в XVIIIвеке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др.) [45,48]. Однако до второй половиныXXвека методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев – невозможно [46].
В зависимости от своей постановки, любая из задач оптимизации может решаться различными методами, и наоборот – любой метод может применяться для решения многих задач.
Методы оптимизации могут быть:
1) скалярными (оптимизация проводится по одному критерию);
2) векторными (оптимизация проводится по многим критериям);
3) поисковыми (включают методы регулярного и методы случайного поиска), аналитическими (методы дифференциального исчисления, методы вариационного исчисления и др.);
4) вычислительными (основаны на математическом программировании, которое может быть линейным, нелинейным, дискретным, динамическим, стохастическим, эвристическим и т.д.);
5) теоретико-вероятностными, теоретико-игровыми и др. [45,46,48].
Наиболее часто используемым методом оптимизации является линейное программирование. Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования [4,29].
Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича «Математические методы организации и планирования производства». Поскольку методы, изложенные Л.В. Канторовичем, были мало пригодны для ручного подсчета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В. Канторовича осталась почти незамеченной [15,18].
В 50-е гг. ХХ века независимо от Канторовича метод решения задачи линейного программирования (так называемый симплекс-метод) был развит американским математиком Дж. Данцигом, который в 1951 г. и ввел термин «линейное программирование».
Можно сказать, свое второе рождение линейное программирование получило с появлением электронно-вычислительных машин (ЭВМ). В то время началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования [29,32].
Слово «программирование» объясняют тем, что неизвестные переменные, которые отыскиваются в процессе решения задачи, обычно определяют программу (план) действий некоторого объекта, например, промышленного предприятия. Слово «линейное» отражает линейную зависимость между переменными [12,18].
Линейное программирование находит широкое применение в различных областях практической деятельности: при организации работы транспортных систем, в управлении промышленными предприятиями, при составлении проектов сложных систем [4,17]. Многие распространённые классы задач системного анализа, в частности, задачи оптимального планирования, распределения различных ресурсов, управления запасами, календарного планирования, межотраслевого баланса укладываются в рамки моделей линейного программирования. Несмотря на различные области приложения, данные задачи имеют единую постановку [2,12,18].
Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:
1) рационального использования сырья и материалов, задачи оптимизации раскроя;
2) оптимизации производственной программы предприятий;
3) оптимального размещения и концентрации производства;
4) составления оптимального плана перевозок, работы транспорта;
5) управления производственными запасами и многие другие, принадлежащие сфере оптимального планирования [4,12,18,29].
Так, по оценкам американских экспертов, около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач линейного программирования и их многочисленных модификаций [4].
В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения [32].
Стандартная задача линейного программирования
Основная задача линейного программирования выглядит следующим образом [47].
Дана система m линейных уравнений с n неизвестными:
(1.1)
где все неизвестные могут принимать только неотрицательные значения:
(1.2)
и линейная функция от тех же переменных
(1.3)
называемая целевой функцией.
Требуется среди всех решений системы уравнений в(1.1) найти
такое неотрицательное решение, при котором целевая функция в формуле (1.3) принимает наибольшее возможное значение.
Любое неотрицательное решение системы уравнений в (1.1) называют допустимым решением, а то допустимое решение, при котором целевая функцияв (1.3) принимает наименьшее значение, называют оптимальным решением задачи линейного программирования в формулах (1.1)-(1.3). Кратко задачу формулируют так: найти вектор, минимизирующий целевую функцию в (1.3) при линейных ограничениях в (1.1) и (1.2).
Если в конкретной задаче будет необходимо найти наименьшее возможное значение некоторой линейной функции, как в формуле (1.3) при линейных ограничениях, то для приведения такой задачи к принятому нами виду основной задачи линейного программирования достаточно линейную функцию Z заменить противоположной ей функцией
(1.4)
так как если функция –Z принимает наибольшее значение при некоторых значениях переменных, то при тех же значениях переменных функция Zпримет наименьшее возможное значение [33,47,48].