Задачи линейного программирования. 2

Федеральное государственное образовательное бюджетное учреждение

высшего профессионального образования

«ФинансовЫЙ УНИВЕРСИТЕТ при Правительстве

Российской Федерации»

(Финансовый  университет)

 

Кафедра «Прикладная математика»

 

 

Курсовая работа

по дисциплине

«Исследование операций»

на тему:

«Задачи линейного программирования»

Выполнила:

студентка гр. ПМ 1-2

Рыбакова А.Р.

Научный руководитель:

к.ф.- м.н., доц. Гончаренко В.М.

 

 

 

Москва – 2013

Оглавление

 

 

 

Введение

Бурное развитие информационных технологий сместило многие акценты в развитии науки. В математике повысилась роль численных методов решения прикладных задач. Эти методы в сочетании с мощью современной вычислительной техники позволяют решать такие задачи, которые еще 50 лет назад не поддавались исследователям. Широкий класс задач, связанных с применением численных методов, - класс оптимизационных задач. Первое упоминание о математических методах в эффективном управлении производством принадлежит советскому математику Л. В. Канторовичу и датируется 1938 годом. За разработку теории линейного программирования академик Л. В. Канторович в 1975 г. получил Нобелевскую премию в области экономики (совместно с Т. Купмансом). Сам термин «линейное программирование» установили  математики Джордж Данциг и Тьяллинг Купманс в конце 40-х годов двадцатого века.

Задачи линейного программирования

Формулировка ЗЛП

Линейное программирование (ЛП) – это раздел математики, ориентированный на нахождение экстремума (максимума и минимума) в задачах, которые описываются линейными уравнениями. Причем линейными уравнениями описывается как сама целевая функция, так и входные параметры (переменные) условия ограничений на входные параметры. Необходимым условием задач линейного программирования (ЗЛП) является обязательное наличие ограничений на ресурсы. Другим важным условием решения задачи является выбор критерия останова алгоритма, то есть целевая функция должна быть оптимальна в некотором смысле. Оптимальность целевой функции должна быть выражена количественно. Если целевая функция представлена одним или двумя уравнениями, то на практике такие задачи решаются достаточно легко. Критерий оптимальности алгоритма должен удовлетворять следующим требованиям:

1. Быть единственным для данной задачи;
2. Измеряться в единицах количества;
3. Линейно зависеть от входных параметров.

 

Стандартная (нормальная) и каноническая формы представления ЗЛП и сведение к ним

ЗЛП называют задачу оптимизации, в которой и целевая функция, и ограничения являются линейными.

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

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

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

Дана система ограничений, состоящая из 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.

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

Вся матрица в канонической ЗЛП называется правильной, если она содержит минимум т правильных столбцов (где т равно числу строк в матрице).

Все правильные столбцы должны содержать единицы в разных строках матрицы.

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

Ведущим столбцом может быть назначен любой столбец матрицы, удовлетворяющий одному из условий:

• первый столбец, содержащий положительный элемент (кроме нуля) в строке (векторе) решений;
• столбец, содержащий наибольший положительный элемент в строке (векторе) решений;
• если столбец t удовлетворяет условию:

 при решении задач на максимум;

 при решении  задач на минимум,

причем – коэффициент целевой функции в столбце j и – коэффициент в столбце j выбранной строки i матрицы A.

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

Критерием останова алгоритма поиска решения будет:

• для поиска максимума целевой функции – все коэффициенты вектора решений или равны нулю или отрицательны.
• для поиска минимума целевой функции – все коэффициенты вектора решений или равны нулю, или положительны.

Двойственные ЗЛП

Определение двойственной ЗЛП

Рассмотрим ЗЛП в стандартной форме

(1)

 

ЗЛП

(2)

называется двойственной задачей по отношению к ЗЛП (1), рассмотренной выше.

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

Если в прямой ЗЛП задано нахождение максимального значения целевой функции, то в двойственной (или обратной) ЗЛП — нахождение минимума целевой функции. Правило составления обратной ЗЛП таково.

Вместо неизвестных величин x в прямой ЗЛП вводятся новые неизвестные переменные y, количество которых равно количеству выражений ограничений в прямой ЗЛП.

Количество выражений ограничений в обратной ЗЛП будет равно количеству неизвестных в целевой функции прямой ЗЛП.

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

Коэффициентами целевой функции обратной ЗЛП будут свободные члены выражений ограничений прямой ЗЛП.

Существует три разновидности двойственной задачи.

1. Симметричная  двойственная задача.

Симметричной двойственной задачей называется такая задача, в которой целевая функция содержит все переменные с коэффициентами, отличными от нуля; все уравнения и неравенства условий ограничений также содержат все переменные с коэффициентами, отличными от нуля; количество ограничении равно количеству переменных.

2. Несимметричная  двойственная задача.

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

3. Смешанная  двойственная задача.

Смешанная двойственная задача может иметь произвольную структуру математической модели (по отношению к симметричной и несимметричной задачам).

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

Основные теоремы двойственности

1. Основное неравенство двойственных задач. Если прямая (1) и двойственная (2) задачи линейного программирования имеют непустые допустимые множества, то для любых их допустимых решений x и y выполняется неравенство , то есть значение целевой функции прямой задачи не превышает значения целевой функции двойственной задачи.
2. Первая теорема двойственности. Если допустимые множества прямой (1) и двойственной (2) задач непусты, то они имеют оптимальные решения x* и y*, причем оптимальные значения целевых функций двух задач совпадают: . Аналогично, если для прямой ЗЛП отсутствует область допустимых решений, то двойственная ЗЛП не имеет решения.
3. Вторая теорема двойственности. Оптимальные решения x* и y* пары двойственных задач связаны между собой следующими равенствами:

 

4. Если одна из пары двойственных задач решена симплексным методом, то в исходной прямоугольной матрице A решенной задачи можно выделить квадратную подматрицу B, столбцы которой соответствуют базисным переменным оптимального решения. Тогда оптимальное решение двойственной задачи вычисляется по формуле где – вектор строка оптимального решения; – вектор-строка, координаты которой равны коэффициентам целевой функции исходной задачи при базисных переменных последней симплексной таблицы.

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

Некоторая компания выпускает краску для внутренних и наружных работ из сырья двух типов: A1, A2. В таблице ниже представлены основные данные задачи.

	Расход сырья (в тоннах) на тонну краски		Максимально возможный ежедневный расход сырья
	для внутренних работ	для наружных работ
Сырье А1	4	6	24
Сырье А2	2	1	6
Доход (в $1000) на тонну краски	4	5

 

Директор, в связи с финансовыми проблемами, поставил два условия:

1. ограничить ежедневный выпуск краски для внутренних работ до 2 т;
2. ежедневное производство краски для внутренних работ не должно превышать более чем нa тонну аналогичный показатель производства краски для внешних работ.

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

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

Обозначим

за – ежедневный объем производства краски для наружных работ;

за – ежедневный объем производства краски для внутренних работ.

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

.

Из таблицы и условий директора находим ограничения:

 

Условия неотрицательности появились потому, что количество краски не может быть отрицательным значением.

Задача содержит всего две переменные, поэтому проще всего решить её графическим методом.

Рис. 2

С геометрической точки зрения, наша исходная функция F изображается как множество прямых перпендикулярных вектору . На рисунке вектор изображен красным цветом.

Причем очевидно, что значение функции будет возрастать при перемещении прямой в направлении вектора .

Перемещаясь вдоль вектора обнаружим, что касание прямой, перед выходом из области допустимых решений, произойдет в точке D, которая лежит на пересечении прямых 1 и 2. В данной точке значение функции будет наибольшим. Решая систему

 

находим, что наибольшее значение функция достигает при

 

Заключение

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

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

Список используемой литературы

1. Аттетков А.В. Введение в методы оптимизации: учеб. Пособие / А.В. Аттетков, В.С. Зарубин, А.Н. Канатников. – М.: Финансы и статистика; ИНФРА-М, 2008. – 272 с.: ил.
2. Агальцов В.П., Волдайская И.В. Математические методы в программировании: Учебник. – М.: ИД «ФОРУМ»: ИНФРА-М, 2006 – 224 с.: ил.
3. Палий И.А. Линейное программирование. Учебное пособие / И.А. Палий – М.: Эксмо, 2008. – 256 с.
4. Исследование операций в экономике: Учебное пособие для вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; под ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2004. Гл. 1-6.
5. Партыка Т.Л., Попов И.И. Математические методы: Учебник – М.: ФОРУМ: ИНФРА-М, 2005. – 464 с.: ил.