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

ФЕДЕРАЛЬНОЕ  АГЕНСТВО  ПО  ОБРАЗОВАНИЮ  РФ

ГОСУДАРСТВЕННОЕ  ОБРАЗОВАТЕЛЬНОЕ  УЧЕРЕЖДЕНИЕ  ВЫСШЕГО  ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ  «МОСКОВСКИЙ  ГОСУДАРСТВЕННЫЙ  ИНСТИТУТ  РАДИОТЕХНИКИ,  ЭЛЕКТРОНИКИ  И  АВТОМАТИКИ  (ТЕХНИЧЕСКИЙ  УНИВЕРСИТЕТ)»

 

 

 

Факультет  ИТ

 

 

 

 

 

 

 

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

Дисциплина:  Теория  принятия  решений

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

 

 

 

 

 

 

 

 

 

 

Студент:   Шаповал  П.Н.

Учебная  группа:  ИТА-2-09

Работу  проверил  проф.  Куренков  Н.И.

  _______________

 

 

 

 

 

 

 

 

 

 

 

Москва  2011 

Содержание:

 

Введение…………………………………………………………………………...3

1.Обзор научно технической литературы……………………………………….4

1.1 История  развития экономико-математического  планирования……..4

1.2 Линейное  программирование………………………………………….5

1.3 Постановка  задачи линейного программирования....……………......5

2.Обзор основных методов решения  задач ЛП………………………………....8

2.1 Графический  метод..…………………………………………………...8

2.2 Симплекс  метод…………………………………………………….....10

3. Решение задачи линейного программирования симплексным методом….13

Заключение……………………………………………………………………….16

Список литературы………………………………………………………………17

 

Введение.

 

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

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

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

Таким  образом  целью  данной  курсовой  работы  является:  освоить  навыки  использования  линейного  программирования  для  решения  задач  оптимизации.  Для  этого  были  поставлены  следующие  задачи:

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

2)Изучить  методы  решения  задач  линейного  программирования. 

3)Дать  критический  анализ  излагаемых  методов.

4)Выделить  метод  и  с  помощью  него  решить  задачу.

 

1.  Обзор  научно-технической  литературы.

 

1.1  История  развития  экономико-математического  планирования.

 

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

В  том  же  1939  г.  ленинградский  экономист  В.  В.  Новожилов,  рассматривая  эффективность  плановых  и  проектных  решений,  сформулировал  важные  теоретические  положения,  ставшие  потом  органической  частью  теории  оптимального  планирования  социалистической  экономики.

Далее  методы  планирования  продолжали  совершенствоваться,  но  только  развитие  вычислительной  техники  в  конце  50-х  гг.  позволило  сделать  плановые  многовариантные  расчеты  достаточно  распространенными.  Важную  роль  в  организации  и  пропаганде  экономико-математических  исследований  в  этот  период  сыграл  академик  В.  С.  Немчинов.  Именно  в  эти  годы  получают  развитие  некоторые  разделы  прикладной  математики,  связанные  с  решением  оптимизационных  задач:  линейное  и  нелинейное  программирование,  теория  оптимального  управления  и  др.  В  60-е  гг.  основное  внимание  исследователей  сосредоточивается  на  разработке  оптимизационных  моделей  различных  типов  и  их  практическом  применении  к  решению  задач  планирования.

 

1.2  Линейное  программирование.

Линейное  программирование  —  математическая  дисциплина,  посвященная  теории  и  методам  решения  задач  об  экстремумах  линейных  функций  на  множествах  n-мерного  векторного  пространства,  задаваемых  системами  линейных  уравнений  и  неравенств.

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

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

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

 

1.3  Постановка  задачи  линейного  программирования.

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

  (1.1)

на  некотором  множестве  D  Ì  Rⁿ  ,где  x  Π D  удовлетворяют  системе  ограничений

  (1.2)

и,  возможно,  ограничениям

  (1.3)

He  умаляя  общности,  можно  считать,  что  в  системе  (1.2)  первые  т  ограничений  являются  неравенствами,  а  последующие  —  l-уравнениями.  Очевидно,  этого  всегда  можно  добиться  за  счет  простого  переупорядочения  ограничений.  Относительно  направления  знака  неравенства  будем  предполагать,  что  левая  часть  меньше  или  равна  правой.  Добиться  этого  можно,  умножив  на  (-1)  обе  части  тех  неравенств,  которые  имеют  противоположный  знак.  Ограничения  (1.3),  вообще  говоря,  могут  быть  рассмотрены  как  частный  случай  ограничений  в  форме  неравенств,  но  в  силу  особой  структуры  их  обычно  выделяют  отдельно  и  называют  условиями  не  отрицательности  (или  тривиальными  ограничениями).

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

  (1.4)

эквивалентна  задаче  поиска  минимума  функции

  (1.5)

Часто  условия  задачи  (1.1)  -  (1.3),  содержащей  ограничения  только  типа  неравенств,  бывает  удобно  записывать  в  сокращенной  матричной  форме

  (1.6)

где  с  и  x  —  векторы  из  пространства  Rⁿ,  b  —  вектор  из  пространства  R^m,  a  А  —  матрица  размерности  m  ´  п.

Задачу  линейного  программирования,  записанную  в  форме  (1.1)  -  (1.3),  называют  общей  задачей  линейного  программирования  (ОЗЛП).

Если  все  ограничения  в  задаче  линейного  программирования  являются  уравнениями  и  на  все  переменные  x_j  наложены  условия  неотрицательности,  то  она  называется  задачей  линейного  программирования  в  канонической  форме,  или  канонической  задачей  линейного  программирования  (КЗЛП).  В  матричной  форме  КЗЛП  можно  записать  в  следующем  виде:

  (1.7)

Поскольку  любая  оптимизационная  задача  однозначно  определяется  целевой  функцией  f  и  областью  D,  на  которой  отыскивается  оптимум  (максимум),  будем  обозначать  эту  задачу  парой  (D,  f).

Условимся  относительно  терминологии,  которая  используется  в  дальнейшем  и  является  общепринятой  в  теории  линейного  программирования.

Планом  ЗЛП  называется  всякий  вектор    из  пространства  Rⁿ.

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

max  f(x)  =  f(x^*).

Величина  f^*  =  f(x^*)  называется  оптимальным  значением  целевой  функции.

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

 

 

2. Обзор основных алгоритмов решения задач ЛП.

2.1  Графический метод.

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

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

Геометрическая интерпретация  целевой функции:

1. Уравнение при фиксированном значении z = z₀ определяет на плоскости X₁ o X₂ прямую . При изменении z получают семейство параллельных прямых, называемых линиями уровня.

2. Вектор коэффициентов целевой  функции  называется градиентом функции. Он перпендикулярен линиям уровня.

3. Градиент функции  показывает направление наибольшего возрастания целевой функции.

4. Антиградиент  показывает направление наибольшего убывания целевой функции.

Графическое решение задач линейного  программирования:

Суть графического метода решения  задач ЛП основывается на следующих  утверждениях:

1) совокупность опорных планов  задачи ЛП совпадает с системой  вершин многогранника решений; 

2) целевая функция достигает  оптимального значения в вершине  многогранника решений. 

Для практического решения задачи

 

 

   x_j   j=1,2

Необходимо:

1) построить с учетом системы  ограничений область допустимых  решений D (многогранник планов);

2) построить вектор градиента;

3) построить перпендикулярно к  нему в области допустимых  решений одну из прямых семейства z = const;

4) искомая точка экстремума X _опт найдется параллельным перемещением вспомогательной прямой z = const в направлении вектора (если ищется z_max) и в направлении вектора (если ищется z_min);

5) координаты точки X _опт можно определить, решив совместно уравнения прямых, пересекающихся в этой точке, или по чертежу

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

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

 

2.2 Симплекс – метод.

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