Учебная работа № /8221. «Контрольная Изучение свойств области допустимых решений задачи линейного программирования. Решение задачи линейного программирования симплекс-методом
Учебная работа № /8221. «Контрольная Изучение свойств области допустимых решений задачи линейного программирования. Решение задачи линейного программирования симплекс-методом
Содержание:
Лабораторная работа 1. Изучение свойств области допустимых решений задачи линейного программирования.
1.1. По содержательному описанию экономической задачи построить математическую модель задачи линейного программирования. Привести задачу к каноническому виду. В канонической форме модель должна содержать 3-4 ограничения и 5-6 переменных.
1.2. Решить задачу графически в пространстве двух произвольно выбранных свободных переменных. Привести вручную необходимые для этого преобразования задачи к симметричной форме. Отобразить на графике все базисные решения, выделить среди них опорные.
1.3. Повторить все геометрические построения в пространстве двух других свободных переменных.
1.4. Пользуясь полученными графиками, сформулировать свойства области допустимых решений задачи линейного программирования. Объяснить в каких случаях число базисных решений будет меньше теоретически возможного.
Лабораторная работа 2. Решение задачи линейного программирования симплекс-методом. Варианты разрешимости задачи.
2.1. По содержательному описанию экономической задачи построить математическую модель задачи линейного программирования.
2.2. Решить задачу симплекс-методом. Объяснить правила перехода из одной симплекс-таблицы к другой (признак оптимальности, возможность улучшения плана, выбор переменных вводимых и выводимых из базиса).
2.3. Изменить условия задачи так, чтобы ее решение требовало применения метода искусственного базиса. Найти оптимальное решение.
2.4. Сформулировать аналитические признаки следующих вариантов разрешимости задачи:
— задача имеет единственное оптимальное решение;
— задача имеет множество оптимальных решений;
— задача неразрешима из-за неограниченности целевой функции;
— задача разрешима при неограниченной области допустимых решений;
— задача имеет вырожденное оптимальное решение;
— задача неразрешима из-за несовместимости системы ограничений.
Дать геометрическую интерпретацию каждого варианта.
Выдержка из похожей работы
1,2 Графический метод решения задач ЛП
1,3 Симплекс-метод решения задач ЛП
2, Примеры решения задач ЛП
Заключение
Список использованных источников
Введение
В последние годы в прикладной математике большое внимание уделяется новому классу задач оптимизации, заключающихся в нахождении в заданной области точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных, Это так называемые задачи математического программирования, возникающие в самых разнообразных областях человеческой деятельности и прежде всего в экономических исследованиях, в практике планирования и организации производства, Изучение этого круга задач и методов их решения привело к созданию новой научной дисциплины, получившей позднее название линейного программирования,
В данном курсовом проекте будет рассмотрено два метода решения задач линейного программирования: графический и симплекс-метод,
Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств, Задачу пространства размерности больше трех изобразить графически вообще невозможно, Поэтому для решения, в том числе этой проблемы, в конце 40-х годов американским математиком Дж, Данцигом был разработан эффективный метод решения данного класса задач — симплекс-метод, К задачам, решаемых этим методом в рамках математического программирования относятся такие типичные экономические задачи как «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», « Задача о выборе производственной программы», «Транспортная задача», «Задача размещения», «Модель Неймана расширяющейся экономики» и другие, Решение таких задач дает большие выгоды как народному хозяйству в целом, так и отдельным его отраслям,
Таким образом, цель курсо��ой работы: применение методов линейного программирования к экстремальным задачам экономики,
Для достижения поставленной цели решаются задачи: постановки задачи линейного программирования, графического метода решения задач ЛП, симплекс-метода решения задач ЛП,
1, Общая задача линейного программирования
1,1 Постановка задачи
Задача линейного программирования (ЛП) ассоциируется с задачей распределительного типа, в которой требуется распределить ограниченные ресурсы по нескольким видам деятельности, Интерпретация задачи ЛП в этом случае состоит в следующем, Моделируемая ЭИС характеризуется наличием нескольких видов деятельности j (j = 1, …, n), для осуществления которых требуются имеющиеся в ограниченном количестве различные ресурсы bi, (i = 1, …, m), Интенсивность расходования каждого из ресурсов на каждый из видов деятельности ЭИС известна и равна aij, Результативность или ценность каждого j-го вида деятельности ЭИС характеризуется величиной cj, Цель построения модели заключается в определении уровней каждого вида деятельности ЭИС xj, при которых оптимизируется общий результат деятельности ЭИС в целом при выполнении ограничений, накладываемых на использование ресурсов, т, е, cj xj ? bi, i = 1, …, m, Структура целевой функции y(u) отражает вклад каждого вида деятельности ЭИС в общий результат, При максимизации сj представляет собой “полезность” j-го вида деятельности (ущерб, наносимый конкуренту по бизнесу, предотвращенный ущерб), а в случае минимизации характеризует затраты (потери собственные, расход материальных средств), Линейность модели выявляется или принимается в качестве допущения на этапе формализации задачи, Линейность предполагает наличие двух свойств — пропорциональности и аддитивности, присущих как целевой функции, так и ограничениям, Пропорциональность целевой функции означает, что вклад каждой управляемой переменной в целевую функцию пропорционален величине этой переменной, Аддитивность же целевой функции заключается в том, что целевая функция представляет собой сумму вкладов от различных управляемых переменных»
