Решение прямой и двойственной задачи линейного программирования и симплекс-методом

Оглавление

Введение

§1. Основные определения и теоремы линейного программирования

§2. Графический метод решения задач линейного программирования на примерах

§3. Примеры решения задач линейного программирования

§4. Задача нахождения на графе кратчайшего пути между каждой парой вершин (алгоритм Флойда)

Заключение

Использованная литература.

Введение

Задачи на наибольшие и наименьшие значения привлекали к себе внимание на протяжении всей истории математики. Античные геометры поставили и решили несколько задач на экстремумы, которые теперь называются изопериметрическими: среди плоских замкнутых кривых заданной длины найти кривую, охватывающую набольшую площадь (ответ - окружность). До второй половины XVII столетия не существовало общих приемов решения задач на экстремум. Первый общий рецепт, с помощью которого предлагалось исследовать задачи на максимум и минимум, был описан П. Ферма (около 1630 г.). На современном языке он звучит так: в точке экстремума (некоторой функции одного переменного) производная равна нулю, и потому экстремумы следует искать среди корней производных. Этот результат входит сейчас в школьный курс математики под названием теоремы Ферма. На самом же деле Ферма описал этот прием фактически лишь для многочленов. В общем виде он был впервые получен Ньютоном (в шестидесятые годы XVII столетия), а затем переоткрыт Лейбницем и впервые опубликован им в знаменитой статье, с которой начинается история математического анализа: «Новый метод нахождения наибольших и наименьших величин...». В XVIII в. усилиями Эйлера и Лагранжа были созданы приемы решения экстремальных задач с функциями от нескольких переменных без ограничений и с ограничениями типа равенств. Основной прием - метод множителей Лагранжа - сейчас входит в программу любого математического и технического вуза. Уже в наши дни эти исследования были дополнены исследованием задач, где ограничения задаются равенствами и неравенствами. Весь этот цикл вопросов получил название математического программирования.К началу XX в. многие считали, что проблематика теории задач на экстремум практически исчерпана. Но оказалось, что это не так. В 1939 г. к заведующему отделом Института математики и механики при Ленинградском университете профессору Л. В. Канторовичу пришли на консультацию представители фанерного треста и предложили его вниманию несколько задач, возникших у них на производстве. При математической формализации выяснилось, что они сводятся к нахождению экстремума линейных функций на многогранниках. Перебрать все вершины многогранников не представлялось возможным из-за огромного их числа Л. В. Канторович нашел иные пути решения и исследования таких задач. Этим он заложил основы нового направления в теории экстремальных задач. Оно получило название линейного программирования. Методы линейного программирования нашли широчайшее применение на практике, в основном в экономике. За разработку математических методов и их внедрение в экономику Л. В. Канторовичу в 1965 г. была присуждена Ленинская, а в 1975 (совместно с американским экономистом Т. Ч. Купмансом) — Нобелевская премия.Усложнение современной экономической практики привело к необходимости широчайшего внедрения методов нахождения оптимальных решений, а, следовательно, и вычислительной техники в повседневную работу инженеров и экономистов. Одним из главных направлений развития общества в наше время становится совершенствование различных видов целенаправленной деятельности человека. Обычно та или иная цель деятельности может быть достигнута разными путями, но всегда полезно знать лучший из них, так как в реальных условиях приходится считаться с ограниченностью материальных ресурсов и времени, расходуемых на достижение цели. Понятие «лучший» относительно: оно начинает что-либо означать тогда, когда назван показатель (критерий) качества принимаемых решений.Роль критерия качества этим не исчерпывается. Как правило, представляет интерес его количественная оценка. Если она существует, появляется возможность построить математическую модель изучаемой системы и определить тем самым характер связи принятого критерия с параметрами исследуемых объектов. Несмотря на разнообразие подобных экстремальных задач, все они с формальной точки зрения сводятся к одной общей постановке: у объекта выделяются переменные величины x=(x1, x2, ..., xn),, влияющие на его поведение (развитие), вводится функционал от этих переменныхF(x1, x2, ..., xn),значение которого характеризует качество поведения объекта. Возможно, переменные являются свободными, то есть на них не накладывается никаких ограничений, но чаще объект действует в ограниченных условиях, и это находит отражение в условиях на переменные в виде уравнений или неравенств:g(x1, x2, ..., xn)=0 или g(x1, x2, ..., xn)≤0.Многие задачи прикладной математики, да и классической математики, являются задачами поиска экстремума. В математике накоплен огромный арсенал методов их решения, в котором различаются аналитические и численные методы. Аналитическое методы основаны на классических результатах математического анализа, численные чаще всего требуют использования вычислительной техники, всегда наиболее мощной, самой современной, с изощренными методами программирования.В теории линейного программирования (ЛП) все функции-ограничения, а также сам функционал – целевая функция являются линейными по всем переменным. Теория графов представляет собой раздел математики, имеющий широкие практические применения. Многие проблемы, возникающие в различных областях знаний, включая электротехнику, управление, планирование перевозок, торговлю и т. д., могут быть сформулированы как задачи теории графов.К 50-м годам прошлого века в теории графов сложилось два различных направления: алгебраическое и оптимизационное. Последнее получило широкое развитие благодаря появлению ЭВМ и в связи с разработкой методов линейного программирования, которые можно сформулировать на языке теории графов. Нас будет интересовать оптимизационное направление.Рассмотрим задачу нахождения на графе кратчайшего пути между каждой парой вершин. Ее можно решить многократным повторением алгоритма Дейкстры, но это требует больших вычислительных затрат. Однако существуют эффективные алгоритмы решения упомянутой задачи. Один из таких алгоритмов разработан Флойдом, и он допускает наличие отрицательных длин дуг в графах. Вместе с тем он не гарантирует правильного решения задачи при наличии контуров отрицательной длины.В информатике алгоритм Флойда - это алгоритм поиска кратчайших путей во взвешенном графе с положительным или отрицательным весом ребер (но без отрицательных циклов). За одно выполнение алгоритма будут найдены длины (суммарные веса) кратчайших путей между всеми парами вершин.Объект нашего исследования: графический метод решения задач линейного программирования. Предмет исследования: методы и приемы решения задач линейного программирования, в том числе задач на графах. Цель исследования: систематизация методов и приемов решения задач линейного программирования.Структура и объем исследования. Курсовая работа состоит из введения, теоретической части (4-х параграфов), практической части (системы решенных задач), заключения и списка использованной литературы.

Использованная литература

Акулич И.Л. Математическое программирование в примерах и задачах. - М.; Высшая школа. 1993. - 335 с.

Аттетков А.В., Гаткин С.В.. Зарубин B.C. Методы оптимизации - М.;Издательство МГТУ им. Н.Э. Баумана, 2004. - 432 с

Габбасов Р., Кириллова Ф.М. Методы оптимизации. - Минск: Изд-во БГУ, 1981.

Галеев Э.М., Тихомиров В.М. Краткий курс теории экстремальных задач. – М.: Изд-во Моск. ун-та, 1989. – 204 с.

Пантелеев А.В.. Летова Т.А. Методы оптимизации в примерах н задачах. - М.; Высшая школа. 2005. - 544 с.