Решение алгебраических и трансцендентных уравнений

Скачать 2.1 Mb.

Название	Решение алгебраических и трансцендентных уравнений
страница	24/27
Дата публикации	26.05.2015
Размер	2.1 Mb.
Тип	Решение

100-bal.ru > Математика > Решение

1 ... 19 20 21 22 23 24 25 26 27

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

Выразим целевую функцию через свободные переменные и допишем к задаче:

f = ₀ -_r+1х_r+1 - ... -_nх_n.

Для базисного решения получим f =₀.

Перед нами стоит цель: уменьшить значение функции f за счет изменения свободных переменных. Свободные переменные для базисного решения равны 0, следовательно, мы можем их только увеличивать. Попробуем увеличивать х_j, где r+1 j  n. Можем ли мы за счет увеличения этой свободной переменной уменьшить значение целевой функции? Если _j, положительное, то f уменьшается, а если _j отрицательное или 0, то нет. Т.е. если _j отрицательное, то нет смысла увеличивать х_j, и наоборот.

Итак, если все _j отрицательны, то данное базисное решение является оптимальным, а минимум целевой функции f равен ₀.

Как перейти от одного базисного решения к другому, более хорошему? Пусть есть такое j, что _j >0. При этом можно улучшить целевую функцию за счет увеличения х_j. Все остальные свободные переменные оставляем равными 0. Тогда имеем:

Посмотрим, до какой степени можно увеличивать х_j. Для этого надо определить, что происходит при этом с базисными переменными. Если коэффициент а_ij не положителен, то значение x_i при увеличении x_j тоже растет и это не препятствует неограниченному росту x_j.

Если получилось, что в выбранном столбце все a_ij<=0, то задача поставлена некорректно, а оптимального решения не существует, поскольку можно бесконечно увеличивать х(_j) и вместе с ним бесконечно уменьшать значение целевой функции, а решение все время будет оставаться допустимым.

Пусть среди а_ij есть положительные числа. Тогда при возрастании х_j будут уменьшаться соответствующие базисные переменные x_i. При этом увеличивать х_j можно до тех пор, пока первая из переменных х₁, х₂...,х_r обратится в 0. Это произойдет, когда х_j примет значение минимальной из величин b_i/а_i,_j, у которых a_ij>0. После этого значение переменной х_j станет отлично от 0,а какая-то из переменных х_i обратится в 0. Это означает, что на очередном шаге мы переменную х_j переводим в базисные, а х_i - в свободные.

Алгоритм симплекс-метода:

1. Заполняем исходную таблицу (считается, что исходный базис найден).

2. Ищем в нижней строке максимальный положительный элемент (кроме 0). Если таких нет, то задача решена. Пусть _j - максимальное положительное число в нижней строчке.

3. В j-том столбце ищем положительные коэффициенты а_kj (если таких нет, то задача не имеет решения). Во вспомогательный столбец заносим b_k/а_kj. Пусть минимальный элемент во вспомогательном столбце находится в i-й строке. На пересечении разрешающего столбца (j) и разрешающей строки (i) находится разрешающий элемент a_ij.

4. Заполняем новую таблицу в следующем порядке:

заголовок;
первый столбец (вместо х_i пишем х_j);
единичные столбцы;
разрешающую строку (делим на а_ij);
остальные строчки по порядку.

5. Возвращаемся к пункту 2.

ОСНОВНАЯ ФОРМУЛА симплекс-преобразования: (пункт 4e) имеет вид:

Пример.

Решим с помощью симплекс-метода задачу:

Видно, что данная система решена относительно свободных переменных х4 и х5 и свободных при базисных переменных х1, х2 и х3. Заполняем исходную симплекс-таблицу и действуем далее по алгоритму.
БазисСвободные членых1х2х3х4х5Вспомогательный столбецх12100-112 <- минимумх27010237/3х310011-2f3000-12Базисное решение (2,7,1,0,0) f=3
БазисСвободные членых1х2х3х4х5Вспомогательный столбецх52100-11х21-310500.2 <- минимумх35201-10f-1-20010Базисное решение (0,1,5,0,2) f= -1
БазисСвободные членых1х2х3х4х5Вспомогательный столбецх52.20.40.2001х40.2-0.60.2010х35.21.40.2100f-1.2-1.4-0.2000Базисное решение (0,0,5.2,0.2,2.2) f= -1.2

Видим, что данная таблица является последней и соответствующее ей базисное решение является оптимальным. Ответ получаем такой: fmin =-1.2, вектор X=(0;0;5.2;0.2;2.2).

1 ... 19 20 21 22 23 24 25 26 27

Похожие:

	Урока по теме: «уравнения. Решение задач с помощью уравнений» Зун учащихся по теме «Уравнения. Решение задач с помощью уравнений», навыков устных и письменных вычислений, упрощения алгебраических...		Урок математики в 6 ом классе по теме : «решение уравнений» Обучающие цели: повторение, обобщение и систематизация знаний учащихся по теме «Решение уравнений» и их применение отработка практических...
	Тематический план модуля «Решение некоторых трансцендентных уравнений и неравенств» Методические указания по выполнению выпускной квалификационной работы для специальности среднего профессионального образования 030912...		Тематический план курса I. Целые рациональные уравнения. 21 Лекция... Сведение уравнения к квадратному с помощью удачной подстановки. 13 Решение возвратных и обобщенных возвратных уравнений. 23 Решение...
	Урок конференция по теме "Решение задач с помощью квадратных уравнений" 8-й класс Решение задач с помощью квадратных уравнений”. Продолжить закрепление решение квадратных уравнений по формуле		Решение иррациональных уравнений и систем (10 класс) Цель: Закрепить решение иррациональных уравнений; развивать логическое мышление; расширять кругозор учащихся
	Дипломная работа «О некоторых применениях алгебры матриц» В данной дипломной работе рассматривается новые применения матриц в теории систем линейных уравнений, теории чисел и теории алгебраических...		Радиофизический факультет Ип в различных системах. Также содержание дисциплины направлено на обучение студентов основам решения задач линейной алгебры, решения...
	Оригинальность идеи и подхода, использование разнообразных приемов Определители. И их применение к решению систем линейных алгебраических уравнений		Тема: Решение задач с помощью системы уравнений первой и второй степени. Здравствуйте, ребята. Ещё начиная с начальной школы вы учились решать задачи. Для этого с каждым годом вы обучались всё новым и новым...
	Тема : Решение показательные уравнений Сегодня я дам вам действовать,чтобы вы поняли и запомнили способы и методы решения показательных уравнений		Урок математики в 4 классе по теме «Решение уравнений вида х×8 = 26 + 70» Познакомить с приемом решения уравнений на основе знаний связи между множителями и произведением
	Конспект урока на обобщающее повторение алгебры в 11 классе по теме... Повторение и обобщение знаний учащихся по теме «Решение тригонометрических уравнений и неравенств»		Элективный курс. Выполнила учитель математики моу сош №29 г. Чебоксары Морушкина Вера Васильевна Решение линейных уравнений (и уравнений приводимых к линейным), содержащих параметр. 5
	Программа по формированию навыков безопасного поведения на дорогах... Развитие и совершенствование техники алгебраических преобразований, решения уравнений, неравенств, систем		Решение уравнений, содержащих параметры, один из труднейших разделов... Предлагаемый курс «Методы решения алгебраических задач с параметром» является предметно-ориентированным и предназначен для реализации...

Школьные материалы

Решение алгебраических и трансцендентных уравнений

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

Алгоритм симплекс-метода:

Пример.

Похожие: