Материал: Применение линейного программирования для решения оптимизационных задач

Применение линейного программирования для решения оптимизационных задач

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Российской Федерации

Московский государственный институт путей сообщения

Юридический институт

Кафедра «Информационно-математические технологии и информационное право»

КУРСОВАЯ РАБОТА

по дисциплине «Методы оптимальных решений»

на тему: «Применение линейного программирования для решения оптимизационных задач»

Выполнила: студентка Минаева Екатерина

Руководитель: Моргунов Роман Борисович

Москва 2015

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ТЕОРЕТИКО-МЕТОДОЛОГИЧЕСКОЕ ОПИСАНИЕ МЕТОДА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ

.1      Общая характеристика линейного программирования

.2      Методы решения ЗЛП

.3      Транспортная задача в Excel

ГЛАВА 2. ПРИМЕНЕНИЕ И ИСПОЛЬЗОВАНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

.1 Решение ЗЛП графическим методом

.2 Проверка оптимального решения в среде MS Excel с использованием программной надстройки «Поиск решения»

.3 Решение ТЗЛП в среде MS Excel с использованием программной надстройки «Поиск решения»

ЗАКЛЮЧЕНИЕ

СПИСОК ИСТОЧНИКОВ И ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ

ВВЕДЕНИЕ

Актуальность темы данной курсовой работы заключается в следующем: развитие современного общества характеризуется повышением технического уровня, усложнением организационной структуры производства, углублением общественного разделения труда, предъявлением высоких требований к методам планирования и хозяйственного руководства. В этих условиях только научный подход к руководству экономической жизнью общества позволит обеспечить высокие темпы развития народного хозяйства. Одним из необходимых условий дальнейшего развития экономической науки является применение точных методов количественного анализа, широкое использование математики. В настоящее время новейшие достижения математики и современной вычислительной техники находят все более широкое применение в экономических исследованиях и планировании. Этому способствует развитие таких разделов математики, как математическое программирование, теория игр, теория массового обслуживания, а также бурное развитие быстродействующей электронно-вычислительной техники. Уже накоплен достаточный опыт постановки и решения экономических задач с помощью математических методов. Особенно успешно развиваются методы оптимального планирования, которые и составляют сущность математического программирования.

Целью настоящей работы является всесторонний анализ применения линейного программирования для решения задач оптимизации.

Реализация поставленной цели определила необходимость решения следующих взаимосвязанных задач:

·        Рассмотреть теоретико-методологическое описание метода ЛП для решения задач оптимизации

·        Решить задачи оптимизации графическим методом

·        Проверить оптимальное решение в среде MS Excel с использованием программной надстройки «Поиск решения»

·        Решить ТЗЛП в среде MS Excel с использованием программной надстройки «Поиск решения»

Объектом исследования выступает математическое программирование, а предметом - метод линейного программирования для решения оптимизационных управленческих задач.

Настоящая работа состоит из введения, двух глав, заключения, списка источников и литературы.

ГЛАВА 1. ТЕОРЕТИКО-МЕТОДОЛОГИЧЕСКОЕ ОПИСАНИЕ МЕТОДА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ

.1 Общая характеристика линейного программирования

Линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения. Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции. По типу решаемых задач методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.

Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений. Отсюда - необходимость разработки новых методов.

Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование». Итак, линейное программирование возникло после Второй Мировой Войны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а так же математической «стройности».

Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр. Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств.

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

·        рационального использования сырья и материалов;

·        задачи оптимального раскроя;

·        оптимизации производственной программы предприятий;

·        оптимального размещения и концентрации производства;

·        составления оптимального плана перевозок, работы транспорта (транспортные задачи);

·        управления производственными запасами;

·        и многие другие, принадлежащие сфере оптимального планирования. Линейное программирование является одной из основных частей того раздела современной математики, который получил название математического программирования. Совокупность соотношений, содержащих целевую функцию и ограничения на ее аргументы, называется математической моделью задачи оптимизации.

ЗЛП записывается в общем виде так:

При ограничениях:

Здесь x_j -неизвестные, a_ij -заданные постоянные величины. Ограничения могут быть заданы уравнениями.

Наиболее часто встречаются задачи в виде: имеется n ресурсов при m ограничениях. Нужно определить объемы этих ресурсов, при которых целевая функция будет достигать максимума (минимума), т. е. найти оптимальное распределение ограниченных ресурсов. При этом имеются естественные ограничения x_j > 0.

При этом экстремум целевой функции ищется на допустимом множестве решений, определяемом системой ограничений, причем все или некоторые неравенства в системе ограничений могут быть записаны в виде уравнений. В краткой записи ЗЛП имеет вид:

При ограничениях:

Для составления математической модели ЗЛП необходимо:

1)обозначить переменные;

2)составить целевую функцию;

3)записать систему ограничений в соответствии с целью задачи;

4)записать систему ограничений с учетом имеющихся в условии задачи показателей.

Если все ограничения задачи заданы уравнениями, то модель такого вида называется канонической. Если хоть одно из ограничений дано неравенством, то модель неканоническая.

.2 Методы решения ЗЛП

линейный программирование оптимизационный задача

Задачи линейного программирования решаются несколькими методами. В настоящей курсовой работе мы подробно рассмотрим графический метод решения метод решения в среде Exsel.

Графический метод решения задачи линейного программирования основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно.

Графический метод довольно прост и нагляден. Он основан на геометрическом представлении допустимых решений задачи. Каждое из неравенств задачи ЛП определяет на координатной плоскости (х₁, х₂) некоторую полуплоскость, а система неравенств в целом - пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлен выпуклым многоугольником, неограниченным выпуклой многоугольной областью, отрезком, лучом и т.д. В случае несовместности системы ограничений задачи ОДР является пустым множеством.

При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи, существует бесконечное множество решений (альтернативный оптимум); область допустимых решений - единственная точка; задача не имеет решений.

Алгоритм решения ЗЛП графическим методом:

.        Построение ОДР

.        Выбор оптимальной точки на границе

.        Определение координаты этой точки

.        Нахождение значения оптимальной функции

Рассмотрим задачу линейного программирования в стандартной форме с двумя переменными (n = 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т. е. n - m = 2.

Найти минимальное значение функции:

При ограничениях вида:

Допустим, что система (2) при условии (3) совместна. Каждое из неравенств из систем (2) и (3) определяет полуплоскость с граничными прямыми:

Линейная функция (1) при фиксированных значениях Z является уравнением прямой линии:

Построим многоугольник решений системы ограничений (2) и график линейной функции (1) при Z=0. Тогда, поставленной задаче линейного программирования можно дать следующую интерпретацию:

Найти точку многоугольника решений, в которой прямая с₁х₁+с₂х₂=const опорная и функция Z при этом достигает минимума. Значения Z=c₁x₁+c₂x₂ уменьшаются в направлении вектора N=(-c₁,-c₂), поэтому прямую Z=0 передвигаем параллельно самой себе в направлении вектора N.

Если многоугольник решений ограничен (см. риc.1), то прямая дважды становится опорной по отношению к многоугольнику решений (в точках B и E), причём минимальное значение принимает в точке E. Координаты точки E(x₁,x₂) находим, решая систему уравнений прямых DE и EF.

Рис.1. Пример графического решения ЗЛП с 6 условиями

Если же многоугольник решений представляет собой неограниченную многоугольную область, то возможны два случая.

Случай 1. Прямая с₁x₁+c₂x₂=const, передвигаясь в направлении вектора N или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу.

Случай 2. Прямая, передвигаясь, всё же становится опорной относительно многоугольника решений. Тогда в зависимости от вида области линейная функция может быть ограниченной сверху и неограниченной снизу, ограниченной снизу и неограниченной сверху, либо ограниченной как снизу, так и сверху. Для решения оптимизационных задач в среде MS Excel используется инструмент «Поиск решения» (пункт меню «Данные Поиск решения»). Для решения задачи необходимо выполнить следующие этапы:

ü  Внести исходные данные;

ü  Определить ячейки, в которые будет помещен конечный результат (изменяемые ячейки);

ü  Внести в определенную ячейку формулу для расчета целевой функции;

ü  Внести в ячейки формулы для расчета ограничений.

В результате получается следующее:

ü  Вызвать надстройку «Поиск решения» и, определив для нее основные параметры, определить решение:

После того, как будут заполнены все основные формы, нажимаем кнопку «Выполнить», после чего появится диалоговое окно «Результаты поиска решений». Решение задачи выглядит следующим образом:

.Для повторного решения задачи оптимизации следует удалить содержимое ячеек с элементами решения и сбросить полученные результаты (клавиша «Delete»).

.Фрагмент рабочего листа MS Excel с результатами решения задачи оптимизации сохраняется и переносится в документ MS Word (например, с помощью команд «Ctrl&PrintScreen» в среде MS Excel и «Вставить» в документе MS Word или с помощью команд «Копировать» и «Вставить», расположенных на панели инструментов во всех приложениях пакета MS Office)

.3 Транспортная задача в среде Excel

Транспортная задача - математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки.

Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

Когда суммарный объем предложения равен объему спроса, транспортная задача закрытого типа или называется закрытой.

Транспортная задача (классическая) - задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).