Симплекс - метод

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

 

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

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Теоретические аспекты

 

1.1 Общая постановка задачи

Двумерные задачи линейного программирования решаются графически. Для случая N=3 можно рассмотреть трехмерное пространство и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.

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

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

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

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

f(x₁,x₂,…,x_n)=c₁x₁+c₂x₂+…+c_nx_n →  max (min) при ограничениях:

 a₁₁x₁ + a₁₂x₂ + … + a_1jx_j + … + a_1nx_n = b₁

 a₂₁x₁ + a₂₂x₂ + … + a_2jx_j + … + a_2nx_n = b₂

 …...........................................................

 a_m1x₁ + a_m2x₂  + … + a_mjx_j + … + a_mnx_n = b_m

 x_j ≥0 (j = 1..n), (i = 1..m)

 

 

1.2 Алгоритм симплексного метода

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

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

                                                                                                                     Таблица 1.

ci	БП	c1	c2	...	cm	cm+1	...	cn	L(x)
		x1	x2	...	xm	xm+1	...	xn	bi
c1	x1	1	0	...	0	h1,m+1	...	h1n	f1
c2	x2	0	1	...	0	h2,m+1	...	h2n	f2
...	...	...	...	...	...	...	...	...	...
cm	xm	0	0	...	1	hm,m+1	...	hmn	fm
	Δj	0	0	...	0	Δm+1	...	Δn	L(x1)

 

Индексная строка для переменных находится по формуле:

     

и по формуле:

 

Возможны следующие случаи при решении задачи на максимум:

— если все оценки Δ_j ≥ 0, то найденное решение оптимальное;

— если хотя бы одна оценка Δ_j ≤ 0, но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращаем, так как L() → , т.е. целевая функция неограничена в области допустимых решений;

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

— если отрицательных оценок в индексной строке несколько, то в столбец базисной переменной (БП) вводят ту переменную, которой соответствует наибольшая по абсолютной величине отрицательная оценка.

Если хотя бы одна оценка Δ_k < 0, то k-й столбец принимаем за ключевой. За ключевую строку принимаем ту, которой соответствует минимальное отношение свободных членов (b_i) к положительным коэффициентам k-гo столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называется ключевым элементом.

3. Заполняем симплексную таблицу 2-го шага:

— переписываем ключевую строку, разделив ее на ключевой элемент;

— заполняем базисные столбцы;

• остальные коэффициенты таблицы находим по правилу "прямоугольника"*. Оценки можно считать по приведенным выше формулам или по правилу "прямоугольника" Получаем новое опорное решение, которое проверяем на оптимальность, и т.д.

* Правило "прямоугольника" заключается в следующем. Пусть ключевым элементом 1-го шага является элемент 1-й строки (m + 1)-го столбца h_1,m+1. Тогда элемент i-й строки (m + 2)-го столбца 2-го шага — обозначим его h’_i,m+2 — согласно правилу "прямоугольника" выражается формулой:

 

 

 

где h_i,m+2, h_i,m+1, h_1,m+1 — элементы 1-го шага.

Примечание. Если целевая функция L() требует нахождения минимального значения, то критерием оптимальности задачи является неположительность оценок Δj при всех j = 1..n

 

1.3. Анализ эффективности использования производственного потенциала предприятия

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

                                                                                                                    Таблица 2.

Производственные ресурсы	Расход ресурсов за месяц при  работе		Общий ресурс
	1-м способом	2-м способом
Сырье	1	2	4
Оборудование	1	1	3
Электроэнергия	2	1	8

 

При первом способе производства предприятие выпускает за один месяц 3 тыс. изделий, при втором — 4 тыс. изделий.

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

Решение. Составим математическую модель задачи. Обозначим: x₁ — время работы предприятия первым способом, x₂ — время работы предприятия вторым способом.

Математическая модель имеет вид:

 

 

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

 

 

                               

 

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

 

 

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

 

                               

Составляем симплексную таблицу 1-го шага (табл.3).

                                                                                                                Таблица 3.

ci	БП	3	4	0	0	0	L(x)
		x1	x2	x3	x4	x5	bi
0	x3	1	2	1	0	0	4
0	x4	1	1	0	1	0	3
0	x5	2	1	0	0	1	8
Δj		-3	-4	0	0	0	0

 

Получим решение:

 

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

В качестве ключевого столбца следует принять столбец базисной переменной х₂, а за ключевую строку взять строку переменной x₃, где min (4/2,3/l, 8/1) = min (2, 3, 8) = 2.

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