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

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

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

• 1. Добавляем к левой части неравенств некоторую неотрицательную величину Ui>=0.
• 2X1+3X2+U1=60
• 6X1+X2+U2=60 (1.1)
• 2X1+X2+U3=24

X1>=0, X2>=0, Ui>=0 (i=1,2,3)

Целевая функция: 4X1+3X2+0U1+0U2+0U3max

Причем каждому решению системы неравенств (1.0) соответствует единственное решение системы уравнений и неравенств (1.1).

2. Записываем Гауссову таблицу.

3. Записываем симплекс-таблицу.

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

В втором столбце записываются переменные, находящиеся в базисе.

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

Последняя строка - индексная. Ее элементы вычисляются по формуле

Б_s= s-й столбец*1 столбец - число, стоящее в 1 строке и s-м столбце.

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

У нас в базисе U1, U2, U3.

Опорное решение: (0;0;60;60;24). Fmax=0

Симплексное преобразование выполняется по следующему правилу:

• 1) Выбираем разрешающий столбец, соответствующий наибольшему по модулю отрицательному элементу в индексной строке.
• 2) Выбирается разрешающая строка, которая соответствует наименьшему положительному из отношений элементов правой части уравнений на соответствующие элементы разрешающего столбца. На пересечении разрешающей строки и разрешающего столбца стоит разрешающее число.
• 3) Элементы разрешающей строки делятся на разрешающее число.
• 4) Вычисляются элементы всех остальных строк по формуле:

Новые эл-ты = старые эл-ты -

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

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

Это и есть достаточные условия существования оптимального плана решения.

4. В нашем случае: наибольшее по модулю отрицательное число в индексной строке стоит в 1 столбце, следовательно разрешающий столбец 1. Разрешающая строка 2.

Вводим в базис X1 вместо U2.

В базисе U1, X1, U3.

Новое опорное решение: (10; 0; 40; 0; 4) Fmax=40

Решение не является оптимальным, т. к. в индексной строке есть отрицательные элементы.

5. Наибольшее по модулю отрицательное число в индексной строке стоит во 2 столбце, следовательно разрешающий столбец 2. Разрешающая строка 3.

Вводим в базис X2 вместо U3.

В базисе X1, X2, U1.

Опорное решение: (9; 6; 24; 0; 0), Fmax=54.

Решение не является оптимальным, т. к. в индексной строке есть отрицательные элементы.

6. Наибольшее по модулю отрицательное число в индексной строке стоит в 4 столбце, следовательно разрешающий столбец 4. Разрешающая строка 1.

Вводим в базис U2 вместо U1.

В базисе U1, X1, X2.

Опорное решение: (3; 18; 0; 24; 0), Fmax=66.

Данное решение является оптимальным, т. к. в индексной строке отсутствуют отрицательные элементы.

Ответ: оптимальный план 3 свадебных торта и 18 праздничных тортов. Fmax=66.

Задание №3

Разложить в ряд Фурье по синусам функцию

Теоретическое введение:

Определение. Функциональный ряд вида

называется тригонометрическим рядом или рядом Фурье. Постоянные числа a0, an, и bn (n=1,2,…) называются коэффициентами тригонометрического ряда или коэффициентами Фурье.

Если дана периодическая функция f(x) с периодом 2р, то целью применения ряда Фурье является отыскание тригонометрического ряда, сходящегося к данной функции. Таким образом, мы отыскиваем функцию, являющуюся суммой ряда в интервале (-р, р):

.

При этом коэффициенты Фурье находят по формулам:

, ,

О разложении в ряд Фурье непериодической функции. Пусть на некотором отрезке [a, b] задана кусочно-монотонная функция f (x). Покажем, что данную функцию в точках ее непрерывности можно представить в виде суммы ряда Фурье. Для этого рассмотрим произвольную периодическую кусочно-монотонную функцию f1 (x) с периодом 2м ? b - a, совпадающую с функцией f (x) на отрезке [a, b].

Разложим функцию f1 (x) в ряд Фурье. Сумма этого ряда во всех точках отрезка [a, b] (кроме точек разрыва) совпадает с заданной функцией f (x), т. е. мы разложили функцию

f (x) в ряд Фурье на отрезке [a, b].

Решение:

Разложим исходную функцию f (x) в ряд Фурье по синусам на отрезке [0, 3].

;

Ответ:

а) Нарисовать график функции ѓ(x) на отрезке [0;3]

Теоретическое введение :

Определение. Функция f(x) называется кусочно-монотонной на отрезке , если этот отрезок можно разбить конечным числом точек на интервалы так, что на каждом из интервалов функция монотонна, т.е. либо невозрастающая, либо неубывающая.

Решение:

Из этого определения следует, что данная функция является кусочно монотонной, т.к. на интервалах (0;1,5) и (1,5;3) она монотонна.

б) Написать, к чему сходится этот ряд в точках отрезка [0,3].

Теоретическое введение:

Определение. Функция f (x) называется удовлетворяющей условиям Дирихле на сегменте [a, b], если: функция непрерывна на сегменте [a, b] или же имеет на нем конечное число точек разрыва 1 рода; функция кусочно-монотонна на сегменте [a, b].

Теорема Дирихле: Пусть периодическая функция f (x) с периодом 2р удовлетворяет на любом сегменте условиям Дирихле. В таком случае ряд Фурье, соответствующий этой функции, сходится во всех точках числовой оси. При этом в каждой точке непрерывности функции f (x) сумма ряда S (x) равна значению функции в этой точке. В каждой точке x₀ разрыва функции сумма ряда равна среднему арифметическому предельных значений функции при x>x₀ слева и справа, т.е.:

S(x) = 0,5[f(x0 + 0)+f(x0 - 0)]

Решение:

Внутри интервала (0;3) ряд сходится к значениям самой функции f(x).

S(0)=

S(3)=

в) Нарисовать график суммы ряда на отрезке [-3,9].

Практическая часть:

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

г) Пользуясь равенством Парсеваля найти сумму: .

Теоретическое введение:

Для функции f(x), такой, что f²(x)L(-;), справедливо равенство Парсеваля:

Решение:

Ответ : 0,75.

Задание №4

Найти линейную комбинацию функций 1, x, x²+3x+3 дающую наилучшее приближение по норме функции f(x) = x³+3x²+2x+3 на отрезке [-1,1].

Указание: ортогонализировать данную систему функций и воспользоваться экстремальным свойством коэффициентов Фурье.

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

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

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

Определение. Система кусочно-непрерывных на отрезке [a, b] функций (конечная или бесконечная) называется ортогональной, если при любых n ? k выполняется равенство(т.е. функции попарно ортогональны) и функции имеют положительную норму.

Пусть функция f(x), определенная на отрезке [a, b], такова, что: .При этом:

Коэффициенты , вычисленные по данной формуле называют коэффициентами Фурье функция f(x) по системе ортогональных функций. А ряд называют рядом Фурье функция f(x) по ортогональной системе функций.

Теорема. Если система функций ц₁(x), ц₂(x), …, ц_n(x) ортонормирована(), то для любой функции f норма среди всевозможных систем чисел достигает своего минимума для единственной системы чисел, определяемых равенствами т.е. для коэффициентов Фурье функции f.

Решение:

L₁(x)=1

L₂(x)=x

L₃(x)= x²+3x+3

Ортогонализируем данную систему фукций:

• 1. f1(x)=L1=1
• 2. f2(x)=бf1+L2, причем б подбираем таким образом, чтобы (f1;f2)=0

б =

f₂(x)=x

3. f3(x)=вf2 + гf1 + L3, причем в и г подбираем так, чтобы (f3;f1)=0 и (f3;f2)=0

г =

в =

f₃ = -3x - + x² + 3x + 3 = x² - 1/3

4. f1(x)= 1

f₂(x)= x

f₃(x)= x² - 1/3

5. Воспользуемся экстремальным свойством коэффициентов Фурье:

Отсюда,

F(x) = c₁f₁ + c₂f₂ + c₃f₃ = 4 + 2,6x + 3(x² - 1/3) = 3x² + 2,6x +3.

Ответ: F(x)= 3x2 + 2,6x +3

Задание №5

Найти объем тела, ограниченного поверхностями:

9(x² + y²) >= 16z²

x² + y² + z² <= 25

z<=0

Теоретическое введение:

Пусть в пространстве задана некоторая область V, ограниченная замкнутой поверхностью S. Пусть в области V и на ее границе определена некоторая непрерывная функция f(x, y ,z), где x, y ,z - прямоугольные координаты точки области. Для ясности в случае, если f(x, y ,z)0, мы можем считать эту функцию плотностью распределения некоторого вещества в области V.

Разобьем область V произвольным образом на области , обозначая символом не только самую область, но и её объём. В пределах каждой частичной области выберем произвольную точку и обозначим через значение функции f в этой точке. Составим интегральную сумму вида (1) и будем неограниченно увеличивать число малых областей так, чтобы наибольший диаметр стремился к нулю. Если функция f(x, y ,z) непрерывна, то при этом будет существовать предел интегральных сумм вида (1). Этот предел, не зависящий ни от способа разбиения области V, ни от выбора точек , обозначается символом (2) и называется тройным интегралом.

Если подынтегральная функция f(x, y ,z)=1, то тройной интеграл по области V выражает объем области V:

Декартовы прямоугольные координаты:

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

координатах сводится к последовательному вычислению одного однократного и одного

двойного интегралов. Если область интегрирования ограничена снизу и сверху соответственно поверхностями:

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

Вычисление начинаем с внутреннего интеграла

по переменной z, считая переменные x и y константами, а затем вычисляем двойной интеграл по проекции области V на плоскость X0Y.