Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики.
В последние годы в прикладной математике большое внимание уделяется новому классу задач оптимизации, заключающихся в нахождении в заданной области точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных. Изучение этого круга задач и методов их решения привело к созданию новой научной дисциплины, получившей позднее название линейного программирования. Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. К задачам, решаемых этим методом в рамках математического программирования относятся такие типичные экономические задачи как «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», «Задача о выборе производственной программы», «Транспортная задача», «Задача размещения», «Модель Неймана расширяющейся экономики» и другие.Моделируемая ЭИС характеризуется наличием нескольких видов деятельности j (j = 1, …, n), для осуществления которых требуются имеющиеся в ограниченном количестве различные ресурсы bi, (i = 1, …, m). Результативность или ценность каждого j-го вида деятельности ЭИС характеризуется величиной cj. Цель построения модели заключается в определении уровней каждого вида деятельности ЭИС xj, при которых оптимизируется общий результат деятельности ЭИС в целом при выполнении ограничений, накладываемых на использование ресурсов, т. е. cj xj ? bi, i = 1, …, m. При максимизации cj представляет собой “полезность” j-го вида деятельности (ущерб, наносимый конкуренту по бизнесу, предотвращенный ущерб), а в случае минимизации характеризует затраты (потери собственные, расход материальных средств). Линейность предполагает наличие двух свойств - пропорциональности и аддитивности, присущих как целевой функции, так и ограничениям.Графический метод, несмотря на свою очевидность и применимость лишь в случае малой размерности задачи, позволяет понять качественные особенности задачи линейного программирования, характерные для любой размерности пространства переменных и лежащие в основе численных методов ее решения. Поясним графический метод на примере задачи ЛП в основной форме для n = 2 Линии уровня функции f(x) = (c, x) (линией уровня называется множество {x R: f(x)= ?, ? R}) образуют семейство параллельных прямых Hc?. В соответствии с предыдущим, поиск решения задачи сводится к нахождению максимального числа ?* среди всех таких ?, что полуплоскость Hc? имеет непустое пересечение с X. Если же решается задача ЛП на минимум, и, следовательно, ищется минимальное ?*, удовлетворяющее указанным требованиям, то Hc? перемещается в направлении, противоположном вектору c.Данная формальная модель задачи линейного программирования обычно задается в форме, так называемой симплекс-таблицы, удобной для выполнения операций симплекс-метода: Симплекс-таблица Столбец p симплекс-таблицы , соответствующий выбранному коэффициенту A0,p разрешающего столбца должна быть введена в базис вместо одной из текущих базисных переменных . Элемент Aq,p называется разрешающим элементом, строка q симплекс-таблицы , содержащая ведущий элемент, называется, соответственно, разрешающей строкой. Практика применения симплекс метода показала, что число итераций, требуемых для решения задачи линейного программирования обычно колеблется от 2m до 3m, хотя для некоторых специально построенных задач вычисления по правилам симплекс метода превращаются в прямой перебор базисных допустимых решений . Элемент, соответствующий разрешающей строке, удаляется из базиса, а на его место ставят элемент, соответствующий разрешающему столбцу.В курсовой работе было рассмотрено два метода решения задач линейного программирования: графический и симплекс-метод.
План
СОДЕРЖАНИЕ
Введение
1.Общая задача линейного программирования (ЛП)
1.1 Постановка задачи
1.2 Графический метод решения задач ЛП
1.3 Симплекс-метод решения задач ЛП
2. Примеры решения задач ЛП
Заключение
Список использованных источников
Введение
В последние годы в прикладной математике большое внимание уделяется новому классу задач оптимизации, заключающихся в нахождении в заданной области точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных. Это так называемые задачи математического программирования, возникающие в самых разнообразных областях человеческой деятельности и прежде всего в экономических исследованиях, в практике планирования и организации производства. Изучение этого круга задач и методов их решения привело к созданию новой научной дисциплины, получившей позднее название линейного программирования.
В данном курсовом проекте будет рассмотрено два метода решения задач линейного программирования: графический и симплекс-метод.
Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трех изобразить графически вообще невозможно. Поэтому для решения, в том числе этой проблемы, в конце 40-х годов американским математиком Дж. Данцигом был разработан эффективный метод решения данного класса задач - симплекс-метод. К задачам, решаемых этим методом в рамках математического программирования относятся такие типичные экономические задачи как «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», « Задача о выборе производственной программы», «Транспортная задача», «Задача размещения», «Модель Неймана расширяющейся экономики» и другие. Решение таких задач дает большие выгоды как народному хозяйству в целом, так и отдельным его отраслям.
Таким образом, цель курсовой работы: применение методов линейного программирования к экстремальным задачам экономики.
Для достижения поставленной цели решаются задачи: постановки задачи линейного программирования, графического метода решения задач ЛП, симплекс-метода решения задач ЛП.
1. Общая задача линейного программирования
Вывод
В курсовой работе было рассмотрено два метода решения задач линейного программирования: графический и симплекс-метод. Они являются наиболее популярными из всех методов линейного программирования и позволяют получить гораздо большее количество информации, нежели просто найденное оптимальное решение.
Однако, симплекс-метод в отличие от графического можно использовать в задаче пространства с размерностью больше трех и это его значительное преимущество. Тогда как графический метод можно применять только в задачах двумерного пространства.
Таким образом, использование симплекс-метода в задачах линейного программирования является наиболее оптимальным.
Список литературы
1) Солодовников, А.С. Математика в экономике. Часть 1. Линейная алгебра, аналитическая геометрия и линейное программирование / А.С. Солодовников, В.А. Бабайцев, А.В. Браилов, И.Г. Шандра.-М.: Издательство «Финансы и статистика»,2011.
2) Струченков В.И. Методы оптимизации в прикладных задачах / В.И.Струченков.-М.: Издательство «Солон-Пресс»,2009.
3) Юденков, А.В. математическое программирование в экономике : Учебное пособие / А.В.Юденков, М.И.Дли, В.В. Круглов.- М.: издательство «Финансы и статистика»,2010.
