Постановка задачи линейного программирования. Построение модели и решение задачи определения оптимального плана производства в ООО "Мельник". Определение оптимального плана производства симплексным методом. Решение задачи оптимизации с помощью MS Excel.
Аннотация к работе
У фабрики по изготовлению мучной продукции стоит конкретная задача: при ограниченном количестве двух типов сырья, трудовых ресурсах и возможности изготавливать два различных вида продукции максимизировать прибыль от ее реализации. Оценки, приписываемые каждому из видов сырья, должны быть такими, чтобы оценка всего используемого сырья была минимальной, а суммарная оценка сырья, используемого на производство единицы продукции каждого вида,-не меньше цены единицы продукции данного вида. Область математики, разрабатывающая теорию и численные методы решения задач по нахождению максимального значения линейной функции (в нашем случае определение максимальной прибыли) многих переменных (два различных вида продукции) при наличии линейных ограничений (запасы сырья и трудовые ресурсы ограничены) называется линейным программированием.Линейное программирование - это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием. Такие задачи находят обширные приложения в различных сферах человеческой деятельности. К математическим задачам линейного программирования относят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов. Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Для него разработаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ;Для случая N=3 можно рассмотреть трехмерное пространство и целевая функция будет достигать свое оптимальное значение в одной из вершин многогранника. Допустимым решением (допустимым планом) задачи ЛП, данной в стандартной форме, называется упорядоченное множество чисел (х1, х2, …, xn), удовлетворяющих ограничениям; это точка в n-мерном пространстве. В общем виде, когда в задаче участвуют N-неизвестных, можно сказать, что область допустимых решений, задаваемая системой ограничивающих условий, представляется выпуклым многогранником в n-мерном пространстве и оптимальное значение целевой функции достигается в одной или нескольких вершинах. Симплекс-метод - это универсальный метод решения задач ЛП, представляющий собой итерационный процесс, который начинается с одного решения и в поисках лучшего варианта движется по угловым точкам области допустимых решений до тех пор, пока не достигнет оптимального значения. Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений к соседней, в которой целевая функция принимает лучшее (или, по крайней мере, не худшее) значение до тех пор, пока не будет найдено оптимальное решение - вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).С каждой задачей линейного программирования можно некоторым образом сопоставить другую задачу ЛП, называемую двойственной по отношению к исходной (прямой). Заинтересованность в определении оптимального решения прямой задачи путем решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными. Задача, состоящая в нахождении минимального значения функции f*=b1y1 b2y2 … bmym>min (1.6) при условиях: a11y1 a12y2 … am1ym ? c1 a12y1 a22y2 … am2ym ? c2 Задачи (1.4) - (1.5) и (1.6) - (1.7) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам: Целевая функция исходной задачи задается на максимум, а целевая функция двойственной-на минимум.Для изготовления теста используются такие ингредиенты как яйца и сахар, так же затрачивается и ресурсы труда. Для изготовления бисквитного теста требуется 5 штук яиц и 0,3 килограмма сахара, для изготовления затрачивается 15 минут.В задаче требуется установить, сколько продукции каждого вида надо производить, поэтому искомыми величинами, а значит, и переменными задачи являются суточные объемы производства каждого вида продукции: х1 - суточный объем производства бисквитного теста, (кг); В условии задачи сформулирована цель - добиться максимального дохода от реализации продукции, т.е. критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму. Чтобы рассчитать величину суточного дохода от продажи продукции обоих видов, необходимо знать объемы производства, т.е. x1 и х2 кг продукции в сутки, а также цены на продукцию бисквитного и песочного теста - согласно условию 30 и 20 руб. за 1 кг продукции соответственно. Поэтому запишем целевую функцию в виде суммы дохода от продажи продукции бисквитного и песочного теста.
План
Оглавление
Введение
Глава 1. Постановка основной задачи линейного программирования
1.1 Линейное программирование
1.2 Симплекс метод решения задач линейного программирования
1.3 Двойственная задача линейного программирования
Глава 2. Построение модели и решение задачи определения оптимального плана производства в ООО «Мельник»
2.1 Построение экономико-математической модели
2.2 Определение оптимального плана производства симплексным методом
2.3 Решение задачи оптимизации в табличном процессоре MS Excel