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

Размещено на http://www.allbest.ru/

Введение

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

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

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

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

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

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

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

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

Целью данной работы является исследование методов решения ЗЛП и применение их на практике.

Объект исследования - методы решения задач линейного программирования.

Предмет исследования - практическое применение симплекс - метода в решении задачи линейного программирования, его особенности и программная реализация.

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

- рассмотреть общий вид задач линейного программирования;

- изучить методы решения ЗЛП;

- исследовать понятие «двойственных задач линейного программирования»;

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

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

1.1 Общий вид задач линейного программирования

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

(1)

и, кроме того, обращали бы в минимум линейную целевую функцию (ЦФ)

(2)

Очевидно, случай, когда ЦФ нужно обратить не в минимум, а в максимум, легко сводится к предыдущему, если изменить знак функции и рассмотреть вместо нее функцию

(3)

Допустимым решением ОЗЛП называют любую совокупность переменных , удовлетворяющую уравнениям (1).

Оптимальным решением называют то из допустимых решений, при котором ЦФ обращается в минимум.

На практике ограничения в задаче линейного программирования часто заданы не уравнениями, а неравенствами. В этом случае можно перейти к основной задаче линейного программирования.

Рассмотрим задачу линейного программирования с ограничениями-неравенствами, которые имеют вид

(4)

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

(5)

Введём уравнения:

(6)

,

где - добавочные переменные, которые также как и являются неотрицательными.

Таким образом, имеем общую задачу линейного программирования - найти неотрицательные , чтобы они удовлетворяли системе уравнений (6) и обращали в минимум (5).

Коэффициенты в формуле (6) перед равны нулю.

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор x=(x₁, x₂,...,x_n), удовлетворяющий системе ограничений и условиям неотрицательности.

Множество допустимых решений (планов) задачи образует область допустимых решений(ОДР).

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

1.2 Каноническая форма задачи линейного программирования

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

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

Она может быть представлена в координатной, векторной и матричной записи.

Каноническая задача линейного программирования в координатной записи имеет вид (формула 7):

Z(X)=c₁x₁+c₂x₂+…+c_nx_n> max

a₁₁x₁+a₁₂x₂+…+a_1nx_n?b₁

a₂₁x₁+a₂₂x₂+…+a_2nx_n?b₂ (7)

_{… … … … … … … …}

a_m1x₁+a_m2x₂+…+a_mnx_n?b_m

x_j?0, j=1,2,…,n.

Каноническая задача линейного программирования в матричной записи имеет вид (формулы 8, 9):

Z(X)=CX > max(min), (8)

AX=A₀, Y?и,

A=, X=, A₀= (9)

Здесь:

- А -- матрица коэффициентов системы уравнений;

- Х -- матрица-столбец переменных задачи;

- Ао -- матрица-столбец правых частей системы ограничений.

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

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

Возьмем линейное неравенство

a₁x₁+a₂x₂+...+a_nx_n?b (10)

и прибавим к его левой части некоторую величину x_n+1 , такую, что неравенство превратилось в равенство

a₁x₁+a₂x₂+...+a_nx_n+x_n+1=b (11)

При этом данная величина x_n+1 является неотрицательной.

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

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

Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

Каждое из неравенств задачи линейного программирования определяет на координатной плоскости некоторую полуплоскость, а система неравенств в целом - пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи (1) ОДР является пустым множеством.

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

(12)

можно представить в виде системы двух неравенств

(13)

ЦФ при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

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

Вектор с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня. Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора .

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

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

Рисунок 1 - Геометрическая интерпретация ограничений и ЦФ задачи

Рассмотрим методику решения задач ЛП графическим методом.

1) в ограничениях задачи (1) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые;

2) найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи (1). Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.

Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку; иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

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

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

3) определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений;

4) если ОДР - не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L - произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений;

5) построить вектор , который начинается в точке (0;0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны;

6) при поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ - против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум);

7) определить координаты точки max (min) ЦФ и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .

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

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

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

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

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

Алгоритм решения ЗЛП симплексным методом.

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

Рассмотрим шаги симлекс-метода.

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

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

Таблица 1 - Пример симплекс-таблицы

Базисные переменные	Свободные члены в ограничениях	Небазисные переменные
		x1	x2	…	xl	…	xn
xn+1	b1	a11	a12	…	a1l	…	a1n
xn+2	b2	a21	a22	…	a2l	…	a2n
…	…	...	...	…	...	…	...
…	…	…	…	…	…	…	…
…	...	...	...	…	...	…	...
xn+r	b2	ar1	ar2	…	arl	…	arn
…	…	…	…	…	…	…	…
…	...	...	...	…	...	…	...
…	…	…	…	…	…	…	…
xn+m	bm	am1	am2	…	aml	…	amn
F(x)max	F0	-c1	-c2	…	-c1	…	-cn

3) на третьем шаге пересчитываем всю симплекс-таблицу по специальным формулам;

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

5) если Вы дошли до пятого шага, значит нашли решение, которое допустимо. Однако, это не значит, что оно оптимально. Оптимальным оно будет только в том случае, если положительны все элементы в F-строке. Если же это не так, то необходимо улучшить решение, для чего находим для следующего перерасчета ведущие строку и столбец по следующему алгоритму. Первоначально, находим минимальное отрицательное число в строке F, исключая значение функции. Столбец с этим числом и будем ведущим. Для того, что бы найти ведущую строку, находим отношение соответствующего свободного члена и элемента из ведущего столбца, при условии, что они положительны. Минимальное отношение позволит определить ведущую строку. Вновь пересчитываем таблицу по формулам, т.е. переходим к шагу 3;

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

1.5 Двойственная задача линейного программирования

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

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

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

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

Различают симметричные, несимметричные и смешанные двойственные задачи.

1.6 Симметричные двойственные задачи

Дана исходная задача

L (x) = c1x1 + c2x2 +…+ cnxn > max (14)

при ограничениях:

a11x1 + a12x2 + … + a1nxn ? b1¦ y1

a21x1 + a22x2 + … + a2nxn ? b2¦ y2 (15)

am1x1 + am2x2 + … + amnxn ? bm¦ ym,

где xj ?0, j = 1, n, i = 1,m.

Задача дана в неканоническом виде. Составим математическую модель двойственной задачи, для этого:

- каждому неравенству системы ограничений исходной задачи приводим в соответствие переменную yi;

- составляем целевую функцию, коэффициентами которой являются свободные члены системы ограничений исходной задачи;

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

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

Математическая модель двойственной задачи имеет вид

S(y) = b1y1 + b2y2 +…+ bmym > min

при ограничениях:

a11y1 + a12y2 + … + am1ym ? c1

a12y1 + a21y2 + … + am2ym ? c2 (16)

a1ny1 + a2ny2 + … + amnym ? cn,

где yj ?0 , i = 1,m ,j = 1,n.

1.7 Несимметричные двойственные задачи

Дана исходная задача

L (x) = c1x1 + c2x2 +…+ cnxn > max

при ограничениях:



a11x1 + a12x2 + … + a1nxn = b1¦ y1

a21x1 + a22x2 + … + a2nxn = b2¦ y2 (17)

am1x1 + am2x2 + … + amnxn = bm ¦ ym,

где xj ?0 , j = 1,n.

Задача дана в каноническом виде. Составим математическую модель двойственной задачи.

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

- ограничениями двойственной задачи будут неравенства. Если в целевой функции двойственной задачи требуется найти минимум, то знак неравенства ?, если максимум, то ? ;

- переменные yi - произвольные по знаку.

Математическая модель двойственной задачи имеет вид

S(y) = b1y1 + b2y2 +…+ bmym > min

при ограничениях:

a11y1 + a21y2 + … + am1ym ? c1

a12y1 + a22y2 + … + am2ym ? c2 (18)

a1ny1 + a2ny2 + … + amnxn ? cn,

где yj ?0, i = 1, m, j = 1, n, yi - произвольные по знаку, i = 1, m.

1.8 Смешанные двойственные задачи

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

При составлении двойственной задачи необходимо выполнять правила симметричных и несимметричных задач.

Рассмотрим основные теоремы двойственности.

Теорема 1. Если одна из двойственных задач имеет оптимальное решение, то другая также имеет оптимальное решение, причем для любых оптимальных решений X и Y выполняется равенство

L(x)max = S(y)min.

Если одна из двойственных задач неразрешима ввиду того, что

L(x)max > ? (или S(y)min > - ?), то другая задача не имеет допустимых решений.

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

xопт j ( ?aijyопт i - cj ) = 0 (19)

yопт i ( ?aijxопт j - bi ) = 0

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

2. Постановка задачи

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

Таблица 2 - Условие задачи

Питательные вещества	Корм 1	Корм 2	Корм 3	Требуемое количество (ед.пит.вещества)
Белки (ед.\кг)	10	6	12	50
Жиры (ед.\кг)	7	10	11	45
Углеводы (ед.\кг)	15	22	9	68
Цена (руб./кг)	22	19,5	28,7

3. Решение задачи аналитическим методом

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

Определим минимальное значение целевой функции

F(X) = 22x₁+19.5x₂+28.7x₃ (20)

при следующих условиях-ограничений.

10x₁+6x₂+12x₃?50

7x₁+10x₂+11x₃?45 (21)

15x₁+22x₂+9x₃?68

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве вводим базисную переменную x₄ со знаком минус. В 2-м неравенстве вводим базисную переменную x₅ со знаком минус. В 3-м неравенстве вводим базисную переменную x₆ со знаком минус.

10x₁ + 6x₂ + 12x₃-1x₄ + 0x₅ + 0x₆ = 50

7x₁ + 10x₂ + 11x₃ + 0x₄-1x₅ + 0x₆ = 45 (22)

15x₁ + 22x₂ + 9x₃ + 0x₄ + 0x₅-1x₆ = 68

Умножим все строки на (-1) и будем искать первоначальный опорный план.

-10x₁-6x₂-12x₃ + 1x₄ + 0x₅ + 0x₆ = -50

-7x₁-10x₂-11x₃ + 0x₄ + 1x₅ + 0x₆ = -45 (23)

-15x₁-22x₂-9x₃ + 0x₄ + 0x₅ + 1x₆ = -68

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =	-10 -6 -12 1 0 0 -7 -10 -11 0 1 0 -15 -22 -9 0 0 1

Решим систему уравнений относительно базисных переменных:

x₄, x₅, x₆,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,-50,-45,-68)

Базисное решение называется допустимым, если оно неотрицательно.

Таблица 3 - Симплекс-таблица

Базис	В	x1	x2	x3	x4	x5	x6
x4	-50	-10	-6	-12	1	0	0
x5	-45	-7	-10	-11	0	1	0
x6	-68	-15	-22	-9	0	0	1
F(X0)	0	22	19.5	28.7	0	0	0

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

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

Определение новой свободной переменной.

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

Ведущей будет 3-ая строка, а переменную x₆ следует вывести из базиса.

Определение новой базисной переменной.

Минимальное значение и соответствует 3-му столбцу, т.е. переменную x₃ необходимо ввести в базис.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-9).

Таблица 4 - Нахождение решающего элемента

Базис	В	x1	x2	x3	x4	x5	x6
x4	-50	-10	-6	-12	1	0	0
x5	-45	-7	-10	-11	0	1	0
x6	-68	-15	-22	-9	0	0	1
F(X0)	0	22	19.5	28.7	0	0	0
и	0	22/-15=-1.47	19.5/-22=-0.89	28.7/-9=-3.19	-	-	-

Пересчет симплекс-таблицы.

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Таблица 5 - Преобразованная симплекс-таблица

Базис	В	x1	x2	x3	x4	x5	x6
x4	40.67	10	23.33	0	1	0	-1.33
x5	38.11	11.33	16.89	0	0	1	-1.22
x3	7.56	1.67	2.44	1	0	0	-0.11
F(X0)	-216.84	-25.83	-50.66	0	0	0	3.19

Представим расчет каждого элемента в виде таблицы:

Таблица 6 - Расчет элементов

B	x1	x2	x3	x4	x5	x6
-50-(-68* (-12)/ (-9))=40.67	-10-(-15*(-12)/ (-9))=10	-6-(-22*(-12)/ (-9))=23.33	-12-(-9* (-12)/ (-9))=0	1-(0* (-12)/ (-9))=1	0-(0* (-12)/ (-9))=0	0-(1*(-12)/ (-9))=-1.33
-45-(-68* (-11)/ (-9))=38.11	-7-(-15*(-11)/ (-9))=11.33	-10-(-22*(-11)/ (-9))=16.89	-11-(-9* (-11)/ (-9))=0	0-(0* (-11)/ (-9))=0	1-(0* (-11)/ (-9))=1	0-(1*(-11)/ (-9))=-1.22
-68/-9 = 7.56	-15/-9 = 1.67	-22/-9 = 2. 44	-9/-9 = 1	0/-9 = 0	0/-9 = 0	1/-9 =-0.11
0-(-68*28.7)/ (-9)=-216.84	22-(-15*28.7)/ (-9)=-25.83	19.5-(-22*28.7)/ (-9)=-50.66	28.7-(-9* 28.7)/(-9)=0	0-(0*28.7) /(-9)=0	0-(0*28.7) /(-9)=0	0-(1*28.7)/ (-9)=3.19

В базисном столбце все элементы положительные.

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

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

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.

Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i/a_i2

и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (23.33) и находится на пересечении ведущего столбца и ведущей строки.

Таблица 7 - Симплекс-таблица

Базис	В	x1	x2	x3	x4	x5	x6	min
x4	40.67	10	23.33	0	1	0	-1.33	1.74
x5	38.11	11.33	16.89	0	0	1	-1.22	2.26
x3	7.56	1.67	2.44	1	0	0	-0.11	3.09
F(X1)	-216.84	-25.83	-50.66	0	0	0	3.19	0

Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₄ в план 1 войдет переменная x₂

Строка, соответствующая переменной x₂ в плане 1, получена в результате деления всех элементов строки x₄ плана 0 на разрешающий элемент РЭ=23.33

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₂ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₂ и столбец x₂ .

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

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (23.33), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:

Таблица 8 - Расчет элементов

B	x1	x2	x3	x4	x5	x6
40.67/ 23.33 =1.74	10 / 23.33 = 0.43	23.33/23.33=1	0/23.33=0	1/23.33 =0.0429	0/23.33 =0	-1.33/23.33= -0.0571
38.11- (40.67 *16.89) /23.33 =8.68	11.33-(10*16.89) /23.33=4.1	16.89- (23.33*16.89) /23.33=0	0-(0*16.89) /23.33=0	0-(1*16.89) /23.33 =0.72	1-(0*16.89) /23.33=1	-1.22-(-1.33 *16.89)/ 23.33=-0.26
7.56-(40.67*2.44 /23.33)=3.3	1.67-(10*2.44 /23.33) =0.62	2.44-(23.33* 2.44 /23.33)=0	1-(0*2.44 /23.33)=1	0-(1*2.44 /23.33) =-0.1	0-(0*2.44 /23.33)=0	-0.11- (-1.33*2.44 /23.33) =0.0283
-216.84-(40.67* (-50.66)/23.33) =-128.56	-25.83-(10* (-50.66)/23.33) =-4.12	-50.66-(23.33* (-50.66)/23.33) =0	0-(0* (-50.66) /23.33)=0	0-(1* (-50.66) /23.33) =2.17	0-(0* (-50.66) /23.33)=0	3.19-(-1.33 *(-50.66) /23.33) =-0.29

После преобразований получаем новую таблицу:

Таблица 9 - Новая таблица

Базис	В	x1	x2	x3	x4	x5	x6
x2	1.74	0.43	1	0	0.0429	0	-0.0571
x5	8.68	4.1	0	0	-0.72	1	-0.26
x3	3.3	0.62	0	1	-0.1	0	0.0286
F(X1)	-128.56	-4.12	0	0	2.17	0	0.29

Итерация №1.

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

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.

Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (4.1) и находится на пересечении ведущего столбца и ведущей строки.

Таблица 10 - Симплекс-таблица

Базис	В	x1	x2	x3	x4	x5	x6	min
x2	1.74	0.43	1	0	0.0429	0	-0.0571	4.07
x5	8.68	4.1	0	0	-0.72	1	-0.26	2.12
x3	3.3	0.62	0	1	-0.1	0	0.0286	5.32
F(X2)	-128.56	-4.12	-0	0	2.17	0	0.29	0

Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₅ в план 2 войдет переменная x₁

Строка, соответствующая переменной x₁ в плане 2, получена в результате деления всех элементов строки x₅ плана 1 на разрешающий элемент РЭ=4.1

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₁ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₁ и столбец x₁ .

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

Представим расчет каждого элемента в виде таблицы:

Таблица 11 - Расчет элементов

B	x1	x2	x3	x4	x5	x6
1.74-(8.68* 0.43/4.1) =0.83	0.43-(4.1* 0.43/4.1) =0	1-(0*0.43/ 4.1)=1	0-(0*0.43/ 4.1)=0	0.0429-(-0.72* 0.43/4.1)=0.12	0-(1*0.43/ 4.1)=-0.1	-0.0571-(-0.26* 0.43/4.1)=-0.0301
8.68/4.1 =2.12	4.1/4.1=1	0/4.1=0	0/4.1=0	-0.72/4.1=-0.18	1/4.1=0.24	-0.26/4.1=-0.0628
3.3-(8.68* 0.62/4.1) =1.98	0.62-(4.1* 0.62/4.1) =0	0-(0*0.62/ 4.1)=0	1-(0*0.62/ 4.1)=1	-0.1-(-0.72* 0.62/4.1)=0.00482	0-(1*0.62/ 4.1)=-0.15	-0.0286-(-0.26* 0.62/4.1)=-0.0675
-128.56-(8.68* (-4.12)/ 4.1)= -119.82	-4.12-(4.1* (-4.12)/ 4.1)=0	0-(0*(-4.12)/4.1)=0	0-(0*(-4.12)/4.1)=0	2.17-(-0.72*(-4.12)/4.1)=1.44	0-(1* (-4.12)/4.1)=1.01	0.29-(-0.26* (-4.12)/4.1)=0.0356

После преобразований получаем новую таблицу:

Таблица 12 - Новая таблица

Базис	В	x1	x2	x3	x4	x5	x6
x2	0.83	0	1	0	0.12	-0.1	-0.0302
x1	2.12	1	0	0	-0.18	0.24	-0.0628
x3	1.98	0	0	1	0.00465	-0.15	0.0674
F(X2)	-119.82	0	0	0	1.44	1.01	0.0353

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

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Таблица 13 - Окончательный вариант симплекс-таблицы

Базис	В	x1	x2	x3	x4	x5	x6
x2	0.83	0	1	0	0.12	-0.1	-0.0302
x1	2.12	1	0	0	-0.18	0.24	-0.0628
x3	1.98	0	0	1	0.00465	-0.15	0.0674
F(X3)	-119.82	0	0	0	1.44	1.01	0.0353

Оптимальный план можно записать так:

x₂ = 0.83

x₁ = 2.12

x₃ = 1.98

F(X) = 22*2.12 + 19.5*0.83 + 28.7*1.98 = 119.82

4 Создание приложения для решения задачи

4.1 Описание алгоритма

Рисунок 3 - Алгоритм работы программы

4.2 Разработка программы

линейное программирование симплекс

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

- порождение начального базисного допустимого решения;

- поиск оптимального плана и экстремума нецелочисленной задачи линейного программирования;

- поиск оптимального плана и экстремума полностью целочисленной

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

- поиск оптимального плана и экстремума частично целочисленной задачи

линейного программирования.

Рассмотрим работу программы на примере задачи о рационе питания.

Необходимо минимизировать целевую функцию:

(28)

при ограничениях:

, где (29)

4.3 Тестирование программы

Общий вид программы с введенными имеет вид, представленный на рисунке 4.

Рисунок 4 - Общий вид программы с введенными данными

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

При нажатии на кнопку «Пуск» на главной панели программы, пользователь получает краткий ответ на решение поставленной задачи (рисунок 5).

Рисунок 5 - Программа в режиме после нажатия на кнопку «Пуск»

Также пользователь может просмотреть каждый этап решения задания при решении программы.

Для этого, в верхнем правом углу программы, ему необходимо выбрать нужный этап решения программы, который необходимо просмотреть (рисунок 6).

Рисунок 6 - Программа в режиме просмотра этапов решения задачи.

Заключение

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

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

Задачи линейного программирования решаются несколькими методами:

1) графический метод;

2) симплекс-метод;

3) двойственный симплекс-метод.

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

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

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

1. Акулич, И.Л. Математическое программирование в примерах и задачах:

учебное пособие для ВУЗов. И. Л. Акулич - Москва: Высшая школа, 2008.

2. Гончаров, Е. Н. Исследование операций. Примеры и задачи: учебное пособие. Е. Н. Гончаров, А. И. Ерзин, В. В. Залюбовский - Новосибирск: Государственный Новосибирский университет, 2005.

3. Павлова, Т. Н. Линейное программирование: учебное пособие. Т. Н. Павлова, О. А. Ракова, 2008.

4. Берюхова, Т.Н. Банк производственных задач в расчетах на ЭВМ: учебное пособие - Тюмень, 2006.

5. Карманов, В.Г. Математическое программирование: учебное пособие для студентов вузов - Москва, 2006.

6. Кузнецов, А.В. Математическое программирование: учебное пособие для вузов - Москва: Высшая школа, 2006.

7. Мочалов, И.А. Нечеткое линейное программирование. Промышленные АСУ и контроллеры, 2006.

8. Пашутин, С.А. Оптимизация издержек и технология формирования оптимального ассортимента, 2006.

9. Жиглявский, А.А., Жилинкас, А.Г. Методы поиска глобального экстремума - Москва. 2008.

10. Карманов, В.Г. Математическое программирование - Издательство физико-математической литературы, 2004.

11. Корн, Г., Корн, Т. Справочник по математике для научных работников и инженеров - Москва, 2010.

Размещено на Allbest.ru

...