Автор работы: Пользователь скрыл имя, 05 Сентября 2014 в 14:42, реферат
Бурное развитие информационных технологий сместило многие акценты в развитии науки. В математике повысилась роль численных методов решения прикладных задач. Эти методы в сочетании с мощью современной вычислительной техники позволяют решать такие задачи, которые еще 50 лет назад не поддавались исследователям. Широкий класс задач, связанных с применением численных методов, - класс оптимизационных задач. Первое упоминание о математических методах в эффективном управлении производством принадлежит советскому математику Л. В. Канторовичу и датируется 1938 годом. За разработку теории линейного программирования академик Л. В. Канторович в 1975 г. получил Нобелевскую премию в области экономики (совместно с Т. Купмансом).
Федеральное государственное образовательное бюджетное учреждение
высшего профессионального образования
«ФинансовЫЙ УНИВЕРСИТЕТ при Правительстве
Российской Федерации»
(Финансовый университет)
Кафедра «Прикладная математика»
Курсовая работа
по дисциплине
«Исследование операций»
на тему:
«Задачи линейного программирования»
Выполнила:
студентка гр. ПМ 1-2
Рыбакова А.Р.
Научный руководитель:
к.ф.- м.н., доц. Гончаренко В.М.
Москва – 2013
Оглавление
Бурное развитие информационных технологий сместило многие акценты в развитии науки. В математике повысилась роль численных методов решения прикладных задач. Эти методы в сочетании с мощью современной вычислительной техники позволяют решать такие задачи, которые еще 50 лет назад не поддавались исследователям. Широкий класс задач, связанных с применением численных методов, - класс оптимизационных задач. Первое упоминание о математических методах в эффективном управлении производством принадлежит советскому математику Л. В. Канторовичу и датируется 1938 годом. За разработку теории линейного программирования академик Л. В. Канторович в 1975 г. получил Нобелевскую премию в области экономики (совместно с Т. Купмансом). Сам термин «линейное программирование» установили математики Джордж Данциг и Тьяллинг Купманс в конце 40-х годов двадцатого века.
Линейное программирование (ЛП) – это раздел математики, ориентированный на нахождение экстремума (максимума и минимума) в задачах, которые описываются линейными уравнениями. Причем линейными уравнениями описывается как сама целевая функция, так и входные параметры (переменные) условия ограничений на входные параметры. Необходимым условием задач линейного программирования (ЗЛП) является обязательное наличие ограничений на ресурсы. Другим важным условием решения задачи является выбор критерия останова алгоритма, то есть целевая функция должна быть оптимальна в некотором смысле. Оптимальность целевой функции должна быть выражена количественно. Если целевая функция представлена одним или двумя уравнениями, то на практике такие задачи решаются достаточно легко. Критерий оптимальности алгоритма должен удовлетворять следующим требованиям:
ЗЛП называют задачу оптимизации, в которой и целевая функция, и ограничения являются линейными.
В ЗЛП нельзя использовать классические методы поиска локального экстремума, поскольку линейная функция не имеет точек локального экстремума. Такие задачи можно решать методами нелинейного программирования, но оказывается, что для них есть специальные и гораздо более эффективные методы решения.
Хотя класс ЗЛП довольно узкий, такие задачи играют в прикладных областях важную роль. Дело в том, что линейные математические модели представляют собой модели первого приближения, в которых связь различных факторов выражена самой простой функциональной зависимостью – линейной. В ряде областей (в частности, в экономике) реальные процессы определяются большим количеством факторов. Тогда на первое место выходит не вид зависимости между какими-либо параметрами, а общая структура таких зависимостей. Для описания каждой конкретной зависимости достаточно линейной функции, а линейные модели становятся ключевыми.
В ЗЛП могут быть ограничения и типа равенств, и типа неравенств. Исходя из критериев оптимальности алгоритма, можно сформулировать задачу линейного программирования в общем виде.
Дана система ограничений, состоящая из m линейных уравнений и неравенств с n переменными
И линейная целевая функция
Необходимо найти такое решение системы , где
при котором целевая функция F принимает оптимальное (то есть максимальное или минимальное) значение.
Более кратко ЗЛП общего вида можно записать следующим образом:
Среди прикладных задач распространен частный случай ЗЛП, в котором все переменные удовлетворяют условию неотрицательности и нет ограничений типа равенства. Такую задачу можно записать в виде:
Эта задача называется ЗЛП в стандартной форме.
ЗЛП, в которой все переменные удовлетворяют условию неотрицательности, а других ограничений типа неравенств нет, то есть задачу вида
называют ЗЛП в канонической форме. Такая форма удобна для построения методов оптимизации.
В ЛП важную роль играют геометрические представления и интерпретации (точнее, представления, вытекающие из линейной алгебры). Так, вполне естественно набор переменных ЗЛП рассматривать как n-мерный арифметический вектор x, записываемый в виде матрицы-столбца: Введем отношение порядка в , полагая если (то есть каждая компонента вектора x не превышает соответствующей компоненты вектора y). Тогда ЗЛП в стандартной форме можно записать с помощью матричных соотношений:
Где – матрица коэффициентов левых частей ограничений, а – вектор-столбец правых частей ограничений. ЗЛП в канонической форме также можно записать с помощью матричных соотношений:
Формально задача в стандартной форме и задача в канонической форме являются частными случаями ЗЛП в общей форме. Однако любую ЗЛП можно привести к стандартной или канонической форме.
Пусть дана ЗЛП общего вида. Сначала преобразуем её так, чтобы все переменные удовлетворяли условию неотрицательности. Здесь можно использовать два приема. Первый прием состоит в использовании имеющихся в задаче ограничений типа неравенств. Например, пусть переменная x1 не связана условием неотрицательности, а в ограничении коэффициент при переменной x1 отличен от нуля. Тогда, введя взамен x1 новую переменную , вместо рассматриваемого ограничения получим условие неотрицательности .
Второй прием боле прост: любую переменную , не связанную условием неотрицательности можно заменить разностью двух новых переменных =, каждая из которых удовлетворяет условию неотрицательности.
Стоит отметить, что первый прием не повышает размерность задачи (иначе говоря, количество переменных) и с этой точки зрения более удобен на практике. Однако неочевидно, что использование этого приема позволяет получить условия неотрицательности для всех переменных.
Второй прием не только увеличивает размерность задачи, но и приводит к задаче, имеющей неединственное решение, так как определенное значение может быть реализовано парой значений и бесконечным числом способов. В то же время второй прием позволяет, хотя и формально, но легко показать, что условия неотрицательности переменных по существу не ограничивают общности ЗЛП.
Если в ЗЛП все переменные неотрицательные, то для её преобразования в стандартную форму нужно избавиться от ограничений типа равенства. Ограничения типа равенства в совокупности образуют систему линейных уравнений . Разделим по отношению к этой системе все переменные на базисные и свободные. Базисные переменные единственным образом выражаются через свободные. Это значит, что базисные переменные можно исключить из ЗЛП, выразив их через свободные переменные и выполнив в целевой функции и ограничениях соответствующие подстановки. В результате получим задачу, в которой оставшиеся переменные будут связаны условием неотрицательности и которая не имеет ограничений типа равенства, то есть задачу в стандартной форме.
Стоит отметить, что от ограничений типа равенства можно формально избавиться, заменив каждое двумя ограничениями типа неравенства. Например, ограничение
можно заменить двумя неравенствами
ЗЛП в общей форме можно преобразовать и в каноническую форму. Для этого, как уже было описано, необходимо обеспечить условие неотрицательности для каждой переменной, а затем избавиться от ограничений типа неравенства. Для ограничения вида
введем новую переменную . Тогда рассматриваемое ограничение естественным образом превращается в условие неотрицательности новой переменной. Повторив этот прием для каждого ограничения типа неравенства, придем к ЗЛП в канонической форме.
ЗЛП можно решить аналитически и графически.
Графические методы решения более наглядны, но имеют ограниченный круг использования – число неизвестных переменных должно быть не более трех. Только в таком случае решение задачи можно наглядно отобразить на бумаге или экране монитора.
Если в ЗЛП всего две переменных, то для решения задачи можно использовать геометрическую интерпретацию задачи.
В этом случае равенства типа на плоскости представляет собой прямую, а каждое ограничение типа неравенства – полуплоскость. Если задача записана в стандартной форме
то допустимое множество G будет пересечением некоторого множества полуплоскостей. Такое множество на плоскости представляет собой либо выпуклый многоугольник, либо отрезок (в вырожденном случае), расположенный в первом квадранте (Рис.1).
Рис.1
Линии уровня целевой функции составляют семейство параллельных прямых, общим вектором которых является вектор коэффициентов целевой функции. Перемещая прямую с таким нормальным вектором в направлении этого вектора, найдем ее крайнее положение, при котором она еще пересекает многоугольник. Каждая точка пересечения этой прямой с многоугольником изображает оптимальное решение задачи, а значение функции, соответсвующее этой линии уровня, есть максимальное (минимальное) значение целевой функции на допустимом множестве.
Таким образом, ЗЛП сводится к построению линий ограничений, опредлению точек пересечения линий ограничений, вычислению значений целевой функции в точках пересечений и выбора точки с максимальным(минимальным) значением целевой функции. Поэтому большинство методов ЛП сводится к определению точек пересечения, способу перехода от одной точки к другой, вычислению значения целевой функции в очередной точке пересечения и выбору оптимальной точки.
Графический метод полезен и в ЗЛП с большим числом переменных. Предположим, ЗЛП имеет n параметров оптимизации и n независимых ограничения типа равенства. Эти ограничения в совокупности составляют систему линейных уравнений . В силу предположения ранг матрицы системы равен количеству уравнений n. Следовательно, система имеет n базисных переменных и 2 свободных. Выразив с помощью системы базисные переменные через свободные, получим ЗЛП без ограничений типа равенства, имеющую всего два параметра оптимизации. Ее можно решить, применяя графический метод.
Рассмотренный выше графический метод решения систем линейных уравнений не всегда применим. Универсальным методом решения систем линейных уравнений является симплексный метод.
Симплекс-метод изобрел американский математик Дж. Данциг.
Идея симплексного метода состоит в том, что поставленная описательная задача переводится в математическую форму. Математическая формулировка задачи содержит уравнение целевой функции с указанием желаемого результата — определение минимума или максимума целевой функции; системы линейных ограничений, заданных равенствами или неравенствами. Полученное математическое описание приводят к матричному виду. Затем матричное описание задачи приводят к канонической форме. После того как система линейных уравнений приведена к канонической форме, приступают к решению задачи линейного программирования. Применение симплекс-метода предполагает, что изначально известно какое-либо допустимое базисное решение задачи, которое называют начальным допустимым базисным решением. Для этого решения выбирают начальный базис , преобразуют ограничения задачи в форму, разрешенную относительно базисных переменных, и исключают базисные переменные из целевой функции. Алгоритм решения задачи состоит из последовательности построения матриц. Каждый шаг решения приближает к получению желаемого результата.
Алгоритм решения следующий:
1) определить ведущий столбец;
2) определить ведущий элемент;
3) определить ведущую строку;
4) составить уравнения пересчета матрицы;
5) выполнить пересчет матрицы;
6) проверить результаты пересчета матрицы на оптимальность;
7) если найденное решение оптимально, то вычисления прекратить и сформулировать ответ. Если найденное решение не оптимально, то перейти к п. 1.
Признаком оптимальности решения является наличие в векторе решений только отрицательных или нулевых значений коэффициентов, как для фактических переменных, так и для фиктивных переменных (при решении задачи на поиск максимума). Столбец в канонической ЗЛП называется правильным, если все его элементы равны нулю, кроме единственного положительного и равного единице.
Вся матрица в канонической ЗЛП называется правильной, если она содержит минимум т правильных столбцов (где т равно числу строк в матрице).
Все правильные столбцы должны содержать единицы в разных строках матрицы.
Ответ записывается следующим образом: каждому отрицательному коэффициенту в векторе решений ставится в соответствие нулевой коэффициент для соответствующей переменной в ответе; для каждого нулевого коэффициента в векторе решений (то есть для правильного столбца) ставится в соответствие значение свободного члена (из вектора ) из строки, содержащей единицу в столбце данной переменной. Фиктивные переменные в ответе не учитываются.