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

Министерство общего образования

Российской федерации

Уральский государственный технический университет-УПИ

филиал в г.Краснотурьинске

Кафедра вычислительной техники

Курсовая работа

По численным методам

Решение линейных уравнений методом простой итерации

c помощью программы Microsoft Excel

Руководитель Кузьмина Н.В.

Студент Нигматзянов Т.Р.

Группа М-177Т

Тема: «Нахождение с заданной точностью корня уравнения F(x)=0 на промежутке методом простой итерации».

Контрольный пример: 0,25-х+sinx=0

Условия задачи: для заданной функции F(x) на интервале найти корень уравнения F(x)=0 методом простой итерации.

Корень вычислить дважды(с помощью автоматического и ручного расчета).

Предусмотреть построение графика функции на заданном интервале.

Введение 4

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

2.Описание хода работы 7

3.Входные и выходные данные 8

Заключение 9

Приложение 10

Библиографический список 12

Введение.

В ходе данной работы мне необходимо ознакомиться с различными методами решения уравнения и найти корень нелинейного уравнения 0,25-х+sin(x)=0 численным методом – методом простой итерации. Для проверки правильности нахождения корня необходимо решить уравнение графически,найти приближенное значение и сравнить его с полученным результатом.

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

Метод простой итерации.

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

Для использования этого метода исходное нелинейное уравнение записывается в виде: х=j(х), т.е. выделяется х; j(х) – непрерывна и дифференцируема на интервале (а; в). Обычно это можно сделать несколькими способами:

Например:

arcsin(2x+1)-x 2 =0 (f(x)=0)

Способ 1.

arcsin(2x+1)=x 2

sin(arcsin(2x+1))=sin(x 2)

x=0.5(sinx 2 -1) (x=j(x))

Способ 2.

x=x+arcsin(2x+1)-x 2 (x=j(x))

Способ 3.

x 2 =arcsin(2x+1)

x= (x=j(x)),знак берется в зависимости от интервала [а;b].

Преобразование должно быть таким, чтобы ½j(x)<1½ для всех принадлежащих интервалу .В таком случае процесс итерации сходится.

Пусть известно начальное приближение корня x=c 0 .Подставляя это значение в правую часть уравнения x=j(x),получаем новое приближение корня:c=j(c 0).Далее, подставляя каждый раз новое значение корня в x=j(x),получаем последовательность значений

c n =j(c n-1) n=1,2,3,…

Процесс итераций следует продолжать до тех пор,пока для двух последовательных приближений не будет выполнено условие: ½c n -c n -1 ½

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

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

у у=х

j(с 0)

с 0 с 2 с 4 с 6 с 8 корень с 9 с 7 с 5 с 3 с 1

2.Описание хода работы.

1. Запустил МЕ.

2. Построил график функции y=x и y=0,25+sin(x) на отрезке с шагом 0,1 назвал лист «График».

3. Выбрал команду Сервис ® Параметры.
Открыл вкладку Вычисления .
Включил режим Вручную .
Отключил флажок Пересчет перед сохранением . Сделал значение поля Пре-дельное число итераций равным 1,относительную погрешность 0,001.

4. Ввел в ячейку А1 строку «Решение уравнения x=0,25+sin(x) методом простой итерации».

5. Ввел в ячейку А3 текст «Начальное значение»,в ячейку А4 текст «Начальный флаг»,в ячейку В3 значение 0,5 ,в ячейку В4 слово ИСТИНА.

6. Присвоил ячейкам В3 и В4 имя «нач_зн» и «нач».
В ячейке В6 будет выполняться проверка,равна ли истина значению ячейки «нач».Если это так,х будет установлено равным начальному значению, в противоположном случае равным ячейке В7,т.е. 0,25+синуса х.В ячейке В7 выч-исляется 0,25-синуса ячейки В6,и тем организуется циклическая ссылка.

7. В ячейку А6 ввел y=x,и в ячейку А7 y=0,25+sin(x).В ячейку В6 формулу:
=ЕСЛИ(нач;нач_зн;В7).
В ячейку В7 формулу: y=0,25+sin(B6).

8. В ячейку А9 ввел слово Погрешность.

9. В ячейку В9 ввел формулу: =В7-В6.

10. С помощью команды Формат-Ячейки (вкладка Число ) преобразовал ячейку В9 в экспоненциальный формат с двумя цифрами после запятой.

11. Затем организовал вторую циклическую ссылку-для подсчета количества ите-раций.В ячейку А11 ввел текст «Количество итераций».

12. В ячейку В11 ввел формулу: =ЕСЛИ(нач;0;В12+1).

13. В ячейку В12 ввел =В11.

14. Для выполнения расчета установил табличный курсор в ячейку В4 и нажал клавишу F9(Вычислить) для запуска решения задачи.

15. Изменил значение начального флага на ЛОЖЬ,и снова нажал F9.При каждом нажатии F9 выполняется одна итерация и вычисляется следующее приближен-ное значение х.

16. Нажимал клавишу F9 до тех пор, пока значение х не достигло необходимой точности.
При автоматическом расчете:

17. Перешел на другой лист.

18. Повторил пункты с 4 по 7,только в ячейку В4 ввел значение ЛОЖЬ.

19. Выбрал команду Сервис ® Параметры (вкладка Вычисления ).Установил зна-чение поля Предельное число итераций равным 100,относительную погреш-ность равной 0,0000001.Включил ркжим Автоматически .

3.Входные и выходные данные.

Начальный флаг ЛОЖЬ.
Начальное значение 0,5

Функция y=0,25-x+sin(x)

Границы интервала

Точность вычисления при ручном расчете 0,001

при автоматическом

Выходные:

1. Ручной расчет:
число итераций 37
корень уравнения 1,17123

2. Автоматический расчет:
число итераций 100
корень уравнения 1,17123

3. Решение уравнения графическим способом:
корень уравнения 1,17

Заключение.

В ходе данной курсовой работы я ознакомился с различными методами решения уравнений:

· Аналитическим методом

· Графическим методом

· Численным методом

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

Нашел с заданной точностью корень уравнения 0,25-x+sin(x)=0 на промежутке методом простой итерации.

Приложение.

1.Ручной расчет.

2.Автоматический расчет.

3.Решение уравнения 0.25-x-sin(x)=0 графическим способом.

Библиографический список.

1. Волков Е.А. «Числовые методы».

2. Самарский А.А. «Введение в числовые методы».

3. Игалеткин И.И. «Числовые методы».

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

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

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

Рассмотрим симплексный метод на конкретном примере задачи о составлении плана.

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

Рассмотрим задачу о плане производства, предварительно построив модель и приведя ее к специальному виду.

Задача.

Для изготовления изделий А и В склад может отпустить сырья не более 80 единиц. Причем на изготовление изделия А расходуется две единицы, а изделия В - одна единица сырья. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль, если изделий А требуется изготовить не более 50 шт., а изделий В - не более 40 шт. Причем, прибыль от реализации одного изделия А - 5 руб., а от В - 3 руб.

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

Приведем задачу к каноническому виду, введя дополнительные переменные:

(3.10)

F = -5x 1 - 3x 2 → min.

Эта задача имеет специальный вид (с базисом, правые части неотрицательны). Ее можно решить симплекс-методом.

I этап. Запись задачи в симплекс-таблицу. Между системой ограничений задачи (3.10) и симплекс-таблицей взаимно-однозначное соответствие. Строчек в таблице столько, сколько равенств в системе ограничений, а столбцов - столько, сколько свободных переменных. Базисные переменные заполняют первый столбец, свободные - верхнюю строку таблицы. Нижняя строка называется индексной, в ней записываются коэффициенты при переменных в целевой функции. В правом нижнем углу первоначально записывается 0, если в функции нет свободного члена; если есть, то записываем его с противоположным знаком. На этом месте (в правом нижнем углу) будет значение целевой функции, которое при переходе от одной таблицы к другой должно увеличиваться по модулю. Итак, нашей системе ограничений соответствует таблица 3.4, и можно переходить ко II этапу решения.

Таблица 3.4

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

Данной таблице 3.4 соответствует следующий опорный план:

(х 1 , х 2 , х 3 , х 4 , х 5) = (0, 0, 50, 40, 80).

Свободные переменные х 1 , х 2 равны 0; х 1 = 0, х 2 = 0. А базисные переменные х 3 , х 4 , х 5 принимают значения х 3 = 50, х 4 = 40, х 5 = 80 - из столбца свободных членов. Значение целевой функции:

-F = - 5х 1 - 3х 2 = -5 · 0 - 3 · 0 = 0.

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

Возможны различные ситуации.

1. В индексной F -строке нет отрицательных элементов. Значит, план оптимален, можно выписать решение задачи. Целевая функция достигла своего оптимального значения, равного числу, стоящему в правом нижнем углу, взятому с противоположным знаком. Переходим к IV этапу.

2. В индексной строке есть хотя бы один отрицательный элемент, в столбце которого нет положительных. Тогда делаем вывод о том, что целевая функция F →∞ неограниченно убывает.

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

III этап . Улучшение опорного плана.

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

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

В нашем примере, , элемент 2 - разрешающий. Строка, соответствующая этому элементу, тоже называется разрешающей (табл. 3.5).

Таблица 3.5

Выбрав разрешающий элемент, делаем перечет таблицы по правилам:

1. В новой таблице таких же размеров, что и ранее, переменные разрешающей строки и столбца меняются местами, что соответствует переходу к новому базису. В нашем примере: х 1 входит в базис, вместо х 5 , которая выходит из базиса и теперь свободная (табл. 3.6).

Таблица 3.6

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

3. Элементы разрешающей строки делим на разрешающий элемент.

4. Элементы разрешающего столбца делим на разрешающий элемент и записываем с противоположным знаком.

5. Чтобы заполнить оставшиеся элементы таблицы 3.6, осуществляем пересчет по правилу прямоугольника. Пусть мы хотим посчитать элемент, стоящий на месте 50.

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

Итак, . Записываем 10 на место, где было 50. Аналогично:

, , , .

Таблица 3.7

Имеем новую таблицу 3.7, базисными переменными теперь являются переменные {x 3 ,x 4 ,x 1 }. Значение целевой функции стало равно -200, т. е. уменьшилось. Чтобы проверить данное базисное решение на оптимальность надо перейти опять ко II этапу. Процесс, очевидно, конечен, критерием остановки являются пункт 1 и 2 II этапа.

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

Таблица 3.8