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

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

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

 

 

 

Факультет  ИТ

 

 

 

 

 

 

 

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

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

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

 

 

 

 

 

 

 

 

 

 

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

Учебная  группа:  ИТА-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).

 

Рисунок 1.1 – Переход от одной вершины к другой

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

Симплекс метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала.

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

 

x₁ + a_1,m+1x_m+1 + ... + a_1sx_s+...+ a_1nx_n = b₁;

x₂ + a_2,m+1x_m+1 + ... + a_2sx_s+...+ a_2nx_n = b₂;

...

x_m + a_m,m+1x_m+1 + ... + a_msx_s+...+ a_mnx_n = b_m

Общая  идея  перехода  от  ОЗЛП  к  КЗЛП  достаточно  проста:

• ограничения  в  виде  неравенств  преобразуются  в  уравнения  за  счет  добавления  фиктивных  неотрицательных  переменных  ,  которые одновременно  входят  в целевую функцию с коэффициентом 0,  т.  е.  не  оказывают  влияния  на  ее  значение;
• переменные,  на  которые  не  наложено  условие  не  отрицательности,  представляются  в  виде  разности  двух  новых  неотрицательных  переменных:

• переменные,  на  которые  наложено  условие  неположительности,  представляются  в виде  новой неотрицательной переменной  помноженной на   ( -1) :

Следует  отметить,  что  переход  от  ОЗЛП  к  КЗЛП  приводит  к  увеличению  её  размерности,  что  усложняет  процесс  решения.

 

Алгоритм решения:

1. Выбираем начальное допустимое базисное решение. Базисным решением называется решение, полученное при нулевых значениях небазисных переменных, т.е. x_i=0, i=m+1,...,n. Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных неотрицательны, т.е. x_j = b_j ³ 0, j=1,2,...,m. В этом случае целевая функция примет следующий вид: W=c_bx_b=c₁b₁+c₂b₂+...+c_mb_m.

  Заполняем первоначальную таблицу  симплекс - метода:

2. Вычисляем вектор относительных оценок c при помощи правила скалярного произведения с_j = с_j - c_bS_j,

где

с_b - вектор оценок базисных переменных;

Sj - j-тый столбец из коэффициентов a_ij в канонической системе, соответствующей рассматриваемому базису.

Дополняем первоначальную таблицу c - строкой.

 

3. Если все оценки c_j £ 0 (c_j ³ 0), i=1,...,n, то текущее допускаемое решение - максимальное (минимальное). Решение найдено.

4. В противном случае в базис необходимо ввести небазисную переменную x_r с наибольшим значением c_j вместо одной из базисных переменных (см. таблицу).

5. При помощи правила минимального отношения min(b_i/a_ir) определяем переменную x_p, выводимую из базиса. Если коэффициент a_ir отрицателен, то b_i/a_ir=¥. В результате пересечение столбца, где находится вводимая небазисная переменная x_r, и строки, где находится выводимая базисная переменная x_p, определит положение ведущего элемента таблицы

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

7. Вычисляем новые относительные оценки с использованием правила скалярного преобразования и переходим к шагу 4. 

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

 

Оптимизация размещения побочного производства лесничества.

Лесничество имеет 24 га свободной земли под  паром и заинтересовано извлечь  из нее доход. Оно может выращивать саженцы быстрорастущего гибрида  новогодней ели, которые достигают  спелости за один год, или бычков, отведя часть земли под пастбище. Деревья выращиваются и продаются в партиях по 1000 штук. Требуется 1.5 га для выращивания одной партии деревьев и 4 га для вскармливания одного бычка. Лесничество может потратить только 200 ч. в год на свое побочное производство. Практика показывает, что требуется 20 ч. для культивации, подрезания, вырубки и пакетирования одной партии деревьев. Для ухода за одним бычком также требуется 20 ч. Лесничество имеет возможность израсходовать на эти цели 6 тыс. руб. Годовые издержки на одну партию деревьев выливаются в 150 руб. и 1,2 тыс. руб. на одного бычка. Уже заключен контракт на поставку 2 бычков. По сложившимся ценам, одна новогодняя ель принесет прибыль в 2,5 руб., один бычок - 5 тыс. руб.

Целевая функция:      5000 x1 + 2500 x2 à max,                             

 Ограничения:

• По использованию земли, га:  4 x₁ + 1,5 x₂ £ 24
• По бюджету, руб.:    1200 x₁ + 150 x₂ £ 6000
• По трудовым ресурсам, ч:   20 x₁ + 20 x₂ £ 200
• Обязательства по контракту, шт.:  x₁ ³ 2
• Областные ограничения:   x₁ ³ 0, x₂ ³ 0

Приведем  задачу к стандартной форме:

4 x₁ + 1,5 x₂ +x₃= 24

1200 x₁ + 150 x₂ +x₄= 6000

20 x₁ + 20 x₂ +x₅= 200

x₁ – x₆= 2

x₁ ... x₆ ³ 0

Первые три  уравнения имеют соответственно по базисной переменной x₃, x₄, x₅, однако в четвертом она отсутствует ввиду того, что при переменной x₆ стоит отрицательный единичный коэффициент. Для приведения системы к каноническому виду используем метод искусственных переменных.

x₁ – x₆+x₇= 2, ввели искусственную переменную x₇

 

 

2 этап симплекс-метода: W=5000 x₁ + 2500 x₂ à max

Изменяем  базисные переменные в предыдущей таблице  и коэффициенты с_i целевой функции.

Вариант с  заменой х₅ на х₂ (вводом х₂ в базисные переменные) приводит к более быстрому окончанию итераций).

Все значения С строки неположительные, сл. найдено оптимальное решение.

Таким образом, корнями задачи ЛП про размещение побочного производства лесничества  будут x₁=3.6 бычка и х₂=6.4 партий ели, а прибыль – 34000 рублей (без учета целочисленности задачи).

 

Заключение

 

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

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

 

 

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

 

1. Ашманов С.А. Линейное программирование. М.: Наука, 2001.
2. Калихман И.Л. Линейная алгебра и программирование. - М.: Высшая школа, 1987
3. Лунгу К.К. Линейное программирование. Руководство к решению задач. – М.: ФИЗМАТЛИТ, 2005.
4. Лищенко «Линейное и нелинейное программирование», М. 2003
5. Орлов А.И. Теория принятия решений. Учебное пособие. - М.: Издательство "Март", 2004