Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
Дисциплины, в которых изучаются модели и методы оптимизации («Методы оптимизации и теория принятия решений», «Исследование операций», Математические модели исследования экономики и математическое программирование») присутствуют во многих образовательных программах профессионального образования. Это очевидно объясняется тем, что современное управление, требующее принятия решений, имеющих не только большое стоимостное выражение, но и различные социальные последствия, должно быть обеспечено разнообразным инструментарием, позволяющим осуществлять выбор из имеющихся вариантов, если не наилучшего (оптимального) решения, то, во всяком случае, предпочтительного с точки зрения лица принимающего решение. Необходимость изучения методов оптимизации и теории принятия решений в инженерных направлениях и специальностях обусловлена, как минимум, двумя факторами. Во-первых, большинство инженеров рано или поздно становятся руководителями (линейными, среднего или высшего звена) и, следовательно, вынуждены принимать управленческие решения, во-вторых, сама инженерная деятельность предполагает принятие многочисленных технических и технологических решений (при проектировании наилучшей конструкции двигателя, в случае выбора оптимальной последовательности обработки потоков задач и оптимального режима функционирования энергостанций и во многих других ситуациях). Это, так называемые задачи математического программирования, возникающие в самых разнообразных областях человеческой деятельности и прежде всего в экономических исследованиях, в практике планирования и организации производства («Определение наилучшего состава смеси», «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», «Задача о диете», «Транспортная задача» и т.д.).Симплекс метод - метод линейного программирования , который реализует рациональный перебор базисных допустимых решений, в виде конечного итеративного процесса, необходимо улучшающего значение целевой функции на каждом шаге. Для решения задачи линейного программирования симплекс-методом необходимо привести задачу к канонической форме, для этого все ограничения должны иметь вид строгого равенства: - ограничения вида «меньше или равно» приводятся к строгому равенству путем добавления к левой части каждого ограничения неотрицательной целой переменной, которая записывается в целевую функцию с коэффициентом равным нулю; чтобы привести ограничения вида «больше или равно» к строгому равенству надо из левой части каждого ограничения вычесть неотрицательную целую переменную и добавить искусственную неотрицательную переменную (y1,y2…yn), которая войдет в целевую функцию с коэффициентом (-M). Алгоритм: 1) Привести математическую модель к канонической форме, заполнить симплекс таблицу и вычислить значение целевой функции и относительных оценок ?i. Если все относительные оценки не отрицательны и среди них есть хотя бы одна равная нулю, а в базисе нет искусственных переменных, то задача решена и имеет бесконечное множество решений, одно из которых вышло в базис и находится в столбце B;Для решения задачи составим ее математическую модель. Для этого введем обозначения: Х1 - прибыль от реализации 1 т молока;Из отрицательных относительных оценок нужно выбрать наибольшую по модулю, (-M-150), соответствующий ей столбец называется главным. В таблицу 2 переменные главного столбца вместе со своими коэффициентами записываются на место переменных главной строки, при этом главный столбец уходит, а все остальные переменные и их коэффициенты переписываются без изменений. В главной строке есть нули, поэтому элементы соответствующие этим нулям, переписываются без изменений. В таблицу 3 переменные главного столбца вместе со своими коэффициентами записываются на место переменных главной строки, при этом главный столбец уходит, а все остальные переменные и их коэффициенты переписываются без изменений. В таблице 4 переменные главного столбца и главной строки вместе со своими коэффициентами меняются местами, а все остальные переменные и их коэффициенты переписываются без изменений.В данной курсовой работе было рассмотрено решение задачи линейного программирования симплекс методом.
План
Содержание
Введение
1 Теоретическая часть
1.1 Алгоритм решения задач линейного программирования симплекс-методом
1.2 Алгоритм решения задач линейного программирования в Microsoft Excel
2 Практическая часть
2.1 Построение математической модели задачи линейного программирования
2.2 Нахождение максимальной прибыли
2.3 Решение задачи линейного программирования в Microsoft Excel
Заключение
Список используемых источников
Введение
Дисциплины, в которых изучаются модели и методы оптимизации («Методы оптимизации и теория принятия решений», «Исследование операций», Математические модели исследования экономики и математическое программирование») присутствуют во многих образовательных программах профессионального образования. Как правило, это программы по направлениям инженерного образования, и по направлениям, связанным с управлением (менеджментом) и экономикой.
Это очевидно объясняется тем, что современное управление, требующее принятия решений, имеющих не только большое стоимостное выражение, но и различные социальные последствия, должно быть обеспечено разнообразным инструментарием, позволяющим осуществлять выбор из имеющихся вариантов, если не наилучшего (оптимального) решения, то, во всяком случае, предпочтительного с точки зрения лица принимающего решение. Необходимость изучения методов оптимизации и теории принятия решений в инженерных направлениях и специальностях обусловлена, как минимум, двумя факторами. Во-первых, большинство инженеров рано или поздно становятся руководителями (линейными, среднего или высшего звена) и, следовательно, вынуждены принимать управленческие решения, во-вторых, сама инженерная деятельность предполагает принятие многочисленных технических и технологических решений (при проектировании наилучшей конструкции двигателя, в случае выбора оптимальной последовательности обработки потоков задач и оптимального режима функционирования энергостанций и во многих других ситуациях). Сегодня оптимизационные задачи и задачи принятия решений моделируются и решаются в самых различных областях техники.
Очевидно, что логика современных инновационных программ инженерного образования, включающих в себя блок курсов, связанных с эффективным управлением (стратегический и операционный производственный менеджмент, управление проектами, инновационный менеджмент и др.), и сопровождаемых технологиями проблемного и проектного обучения, предполагает, что обучающиеся должны владеть навыками математического обоснования принятия решений. К ним относятся и навыки математического моделирования оптимизационных задач, выбора адекватного математического обеспечения (метода, алгоритма, программной системы) с необходимым обоснованием, анализа полученных результатов и их интерпретации в терминах предметной области.
Современная теория математического обоснования принятия решений во многом строится на теории оптимизации, и не может быть изложена достаточно стройно без знания основ математического программирования и исследования операций.
В последние годы в прикладной математике большое внимание уделяется новому классу задач оптимизации, заключающихся в нахождении в заданной области точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных. Это, так называемые задачи математического программирования, возникающие в самых разнообразных областях человеческой деятельности и прежде всего в экономических исследованиях, в практике планирования и организации производства («Определение наилучшего состава смеси», «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», « Задача о диете», «Транспортная задача» и т.д.).
В 1939 году Леонид Витальевич Канторович опубликовал работу «Математические методы организации и планирования производства», в которой сформулировал новый класс экстремальных задач с ограничениями и разработал эффективный метод их решения, таким образом были заложены основы линейного программирования. Линейное программирование является частным случаем математического программирования . Одновременно оно - основа нескольких методов решения задач целочисленного и нелинейного программирования . Одним из обобщений линейного программирования является дробно-линейное программирование .
Термин «программирование» нужно понимать в смысле «планирования» Он был предложен в середине 1940-х годов Джорджем Данцигом , одним из основателей линейного программирования, еще до того, как компьютеры были использованы для решения линейных задач оптимизации .
Оптимизационные модели - это формализованные с помощью математического аппарата экономические задачи, в которых присутствуют условия для нахождения оптимального решения.
Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.
Симплексный метод в отличие от геометрического универсален. С его помощью можно решить любую задачу линейного программирования.
В основу симплексного метода положена идея последовательного улучшения получаемого решения.
Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений к соседней, в которой целевая функция принимает лучшее (или, по крайней мере, не худшее) значение до тех пор, пока не будет найдено оптимальное решение - вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).
Таким образом, имея систему ограничений, приведенную к канонической форме (все функциональные ограничения имеют вид равенств), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще. Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то осуществляется переход к другому, обязательно допустимому базисному решению. Симплексный метод гарантирует, что при этом новом решении целевая функция, если и не достигнет оптимума, то приблизится к нему (или, по крайней мере, не удалится от него). С новым допустимым базисным решением поступают так же, пока не отыщется решение, которое является оптимальным.
Процесс применения симплексного метода предполагает реализацию трех его основных элементов: 1) способ определения какого-либо первоначального допустимого базисного решения задачи;
2) правило перехода к лучшему (точнее, не худшему) решению;
Симплексный метод включает в себя ряд этапов и может быть сформулирован в виде четкого алгоритма (четкого предписания о выполнении последовательных операций). Это позволяет успешно программировать и реализовывать его на ЭВМ. Задачи с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную.
Вывод
В данной курсовой работе было рассмотрено решение задачи линейного программирования симплекс методом. Задача была решена симплекс методом, также решение задачи линейного программирования представлено в Microsoft Excel.
Таким образом, вычислительная техника в настоящее время находит широкое применение, как в общей математике, так и в одном из ее разделов - математических методах.
В данной работе был составлен оптимальный план выпуска продукции каждого вида, обеспечивающий максимальную прибыль.(заключение маловато) линейное программирование симплекс метод
Список литературы
1 Зайченко Ю.П. Исследование операций. Киев: Высшая школа, 1997. - 152 с.
2 Шумилова Л. Исследование операций. Киев: Высшая школа, 2004. - 137 с.
3 Реклейтис Г. Оптимизация в технике. М.:Мир,1982г. (В 2-х томах).
4 Вентцель Е.С. Исследование операций. М.: Высшая школа, 2002. - 255 с.
5 Кузнецов Ю.Н. Математическое программирование. М.: ЮНИТИ, 1999. - 311 с.
6 Химмельблау Д. Прикладное программирование. М.: Мир, 1999. - 391 с.
7 Коршунов Ю.М. Математические основы кибернетики. М.: Энергия, 2001. - 214 с.
8 Сакович В.А. Исследование операций. Минск: Высшая школа, 1998. - 162 с.
Размещено на .ru
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
