Симплексный метод с использованием М- базиса

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

ПЕРМСКАЯ  ГОСУДАРСТВЕННАЯ СЕЛЬСКОХОЗЯЙСТВЕННАЯ АКАДЕМИЯ          Д.Н. ПРЯНИШНИКОВА

         (ПГСХА)

 

 

 

                                          Кафедра ИТАП

 

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

по дисциплине «Методы оптимизации»

На тему: «Симплексный метод с использованием М- базиса»

 

       Выполнил: студент группы Пи-31а

         Мережников К.Н.

 

          Проверил: 

          А.М. Гревцев  

 

 

 

 

Пермь  2012

Оглавление

Введение

1 Теоретическая часть 4

1.1  Описание симплексного метода. 4

1.2  Табличный симплексный метод. 7

1.3 Метод искусственного базиса (М-Метод) 11

2 Решение задач 17

2. 1 Табличный симплекс-метод 17

2. 2 Метод искусственного базиса 25

Заключение

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

 

 

 

Введение

 

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

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

 

1 Теоретическая часть

1.1 Описание симплексного метода.

Симплекс-метод - алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Данный метод, имеющий несколько различных форм (модификаций), метод был разработан советским математиком Канторовичем Л. В. в 1937 году. Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях. Многогранник ограничивающих условий для 3-мерного пространства (рисунок 1)

Рисунок 1

 

Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства  ограничивают некоторый многогранник (возможно, бесконечный). Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника.

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

Рассмотрим  теперь более подробно основы симплекс-метода и сформулируем алгоритм. Для решения  системы все неизвестные произвольно  подразделяют на базисные и свободные. Число базисных переменных определяется числом линейно-независимых уравнений. Остальные неизвестные свободные. Им придают произвольные значения и подставляют в систему. Любому набору свободных неизвестных можно придать бесчисленное множество произвольных значений, которые дадут бесчисленное множество решений. Если все свободные неизвестные приравнять к нулю, то решение будет состоять из значений базисных неизвестных. Такое решение называется базисным.

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

Последовательность  вычислений симплекс-методом можно  разделить на две основные фазы:

1.нахождение исходной  вершины множества допустимых  решений (нахождение базисного решения),

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

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

 

 

Тонкости симплекс метода:

1) Когда прямая (если рассматривается  двухмерная задача линейного  программирования, а в общем случае  гиперплоскость), представляющая целевую  функцию параллельна прямой (гиперплоскости), соответствующей одному из неравенств-ограничений  (которое в точке оптимума выполняется,  как точное равенство) целевая  функция принимает одно и тоже  оптимальное значение на некотором  множестве точек границы области  допустимых решений. Эти решения  называются альтернативными оптимальными решениями. Наличие альтернативных решений можно определить по оптимальной симплекс-таблице. Если в z-строке оптимальной таблицы есть нулевые коэффициенты небазисных переменных, то есть альтернативные решения.

2) Если в разрешающем столбце  симплекс-таблицы все коэффициенты  меньше или равны нуль, то нельзя  выбрать разрешающую строку, в  этом случае решение неограничено.

3) Если ограничения задачи линейного  программирования несовместны (т.е.  они не могут выполняться одновременно), то задача не имеет допустимых  решений. Такая ситуация не  может возникнуть, если все неравенства,  составляющие систему ограничений,  имеют тип " ≤ " с неотрицательными  правыми частями, т.к. в этом  случае дополнительные переменные  могут составить допустимое решение.  Для других типов ограничений  использются искусственные переменные. Если задача имеет решение,  то в оптимальной таблице в  базисе нет искусственных переменных (Ri). Если они там есть, то задача  не имеет решений.

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

Процесс нахождения исходной вершины не сильно отличается от однофазного  симплекс-метода, однако может в  итоге оказаться сложнее, чем  дальнейшая оптимизация

 

1.2 Табличный симплексный метод.

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

F=a_0,1x₁+a_0,2x₂+...a_0,nx_n +b₀ → max

a_1,1x₁+a_1,2x₂+...a_1,nx_n + x_n+1=b₁

a_2,1x₁+a_2,2x₂+...a_2,nx_n +x_n+2 =b₂

.......................................

a_m,1x₁+a_m,2x₂+...a_m,nx_n+x_n+m=b_m

Исходная таблица (таблица 1) для задачи имеет следующий вид:

	x1	x2	...	xn-1	xn	b
F	-a0,1	-a0,2	...	-a0,n-1	-a0,n	-b0
xn+1	a1,1	a1,2	...	a1,n-1	a1,n	b1
xn+2	a2,1	a2,2	...	a2,n-1	a2,n	b2
...	...	...	...	...	...	...
xn+m	am,1	am,2	...	am,n-1	am,n	bm

Таблица 1.

x₁, x₂, x_n - исходные переменные, x_n+1, x_n+2, x_n+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку).

 

 

 

  Алгоритм табличного симплекс-метода.  

Приводим задачу ЛП  к каноническому виду

F=a_0,1x₁+a_0,2x₂+...a_0,nx_n +b₀ → max

a_1,1x₁+a_1,2x₂+...a_1,nx_n+x_n+1=b₁

a_2,1x₁+a_2,2x₂+...a_2,nx_n+x_n+2=b₂

.......................................

a_m,1x₁+a_m,2x₂+...a_m,nx_n+x_n+m=b_m

В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов  целевой функции F меняются на противоположные a_0,n=-a_0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" - коэффициенты запишутся без изменений.    

Шаг 0. Составляем симплексную таблицу (таблица 2), соответствующую исходной задаче

	x1	x2	...	xn-1	xn	b
F	-a0,1	-a0,2	...	-a0,n-1	-a0,n	-b0
xn+1	a1,1	a1,2	...	a1,n-1	a1,n	b1
xn+2	a2,1	a2,2	...	a2,n-1	a2,n	b2
...	...	...	...	...	...	...
xn+m	am,1	am,2	...	am,n-1	am,n	bm

Таблица 2.

 

 

 

 Шаг 1. Проверка на допустимость.   

Проверяем на положительность элементы столбца b (свободные члены), если среди  них нет отрицательных то найдено  допустимое решение (решение соответствующее  одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент a_k,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис.

Если же среди свободных членов есть отрицательные элементы - а  в соответствующей строке - нет  то условия задачи несовместны и  решений у нее нет.

Если после перерасчета в  столбце свободных членов остались отрицаетельные элементы, то переходим  к первому шагу, если таких нет, то ко второму.  

Шаг 2. Проверка на оптимальность. 

На предыдущем этапе найдено  допустимое решение. Проверим его на оптимальность Если среди элементов  симплексной таблицы, находщихся в  строке F (не беря в расчет элемент b₀ - текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.

Если в строке F есть отрицательные  элементы то решение требует улучшения. Выбираем среди отрицательных элементов  строки F максимальный по модулю (исключая значение функции b₀)

a_0,l=min{a_0,i }

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

b_k/a_k,l =min {b_i/a_i,l } при a_i,l>0, b_i>0

k - cтрока, для которой это  отношение минимально - ведущая.  Элемент a_k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x_k) исключается из базиса, переменная соответствующая ведущему столбцу (x_l) включается в базис.

Если в новой таблице после  перерасчета в строке F остались отрицательные элементы переходим  к шагу 2

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

Если в строке F и в столбце  свободных членов все элементы положительные, то найдено оптимальное решение.  

Правила преобразований симплексной таблицы. 

При составлении новой симплекс-таблицы  в ней происходят следующие изменения: 

• Вместо базисной переменной x_k записываем x_l; вместо небазисной переменной x_l записываем x_k.  
• ведущий элемент заменяется на обратную величину a_k,l'= 1/a_k,l
• все элементы ведущего столбца (кроме a_k,l) умножаются на -1/a_k,l
• все элементы ведущей строки (кроме a_k,l) умножаются на 1/a_k,l
• оставшиеся элементы симплекс-таблицы преобразуются по формуле a_i,j'= a_i,j- a_i,lx a_k,j/ a_k,l