Вычислительные методы и методы оптимизации в экономике

В качестве первого приближения выберем левую границу интервала: .

Вычислим первую производную функции  : , и используя рекуррентную формулу Ньютона находим :

.

Т.к. , то нужно выполнить ещё один шаг:

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

Вычисление в maple даёт тот же результат:

Ответ:

 

 

Задание 6

Составьте таблицы приближенных значений решения данного дифференциального  уравнения  , удовлетворяющего начальному условию на отрезке [1;2] с шагом h=0,2 с помощью методов Эйлера и Рунге-Кутта,  Сравните полученные результаты с точными, определив относительную погрешность в каждой точке (в %).

Решение:

Изобразим предложенные в условии методы с помощью блок-схем:

Точное решение задачи Коши найдём методом Лагранжа:

Решаем сначала однородное уравнение:

:

Составим искомую таблицу:

					Предиктор
1	0,000	0,000	0,000		0,100	0,000	0,000
1,2	0,192	0,200	0,044	1,1	0,298	0,191	0,002
1,4	0,397	0,396	0,000	1,3	0,507	0,399	0,006
1,6	0,642	0,618	0,037	1,5	0,750	0,641	0,001
1,8	0,943	0,881	0,066	1,7	1,037	0,930	0,014
2	1,313	1,194	0,091	1,9	1,379	1,273	0,030

Схема Рунге-Кутта имеет большую  степень точности, чем метод Эйлера.

С помощью Maple можно вычислить точное решение задачи Коши:

А вычисление сетки сделаем в Excel:

Ответ:

 

Задание 7

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

Решение:

Выразим из 1-го уравнения системы y и подставим во второе:

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

Суть метода:

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

Члены рекуррентной последовательности в методе простой итерации вычисляются  по закону:

Метод является одношаговым, и для начала вычислений достаточно знать одно начальное приближение x₀=a или x₀=b или x₀=(a+b)/2.

Для начала проверим сходимость метода для нашего уравнения: сходимость метода выполняется для любого x.

Судя по графику функции

Решение лежит в интервале [-1;0]. Выберем в качестве первого приближения середину этого интервала: . Далее проведём итерации, пока не добьёмся заданной точности:

Теперь выразим 

Maple выдаёт тот же результат, с поправкой на округление:

Ответ:

 

 

 

 

 

Задание 8

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

Найдите максимальное и минимальное  значения целевой функции.

Решение:

Графический метод решения ЗЛП  заключается в следующем: в одной системе координат строим область соответствующую набору ограничений, заданных в условии, и график уравнения . Далее сдвигаем прямую так, чтобы она имела только одну общую точку с областью ограничений. Координаты полученных точек и будут соответствовать оптимальным.

Из рисунка видно, что минимум  функции достигается в точках : ,

а максимум в точках : .

В Maple решение выглядит так:

Ответ: ; .

2) Предприятие выпускает два вида изделий П1 и П2, на изготовление которых идет три вида сырья: S1, S2, S3, запасы которых соответственно равны 200, 110, 120 кг. Расход сырья на 1000 ед. продукции составляет: S1 – 20, 10; S2 – 15, 5; S3 – 10, 10. Оптовая цена за 1000 шт. изделий соответственно равна:  15 и 17 тыс. руб. Себестоимость производства 1000 шт. изделий составляет 12 и  15 тыс. руб. Составить план выпуска продукции, обеспечивающий максимальную прибыль, предполагая, что сбыт неограничен.

Решение:

Для решения данной задачи нужно  составить соответствующую ЗЛП.

Количество выпущенных изделий (в тыс.шт.) П1 обозначим , а изделий П2 - .Естественно и не могут быть отрицательными и дробными.

Производство 1000шт. изделий П1 приносит прибыль: 15000-12000=3000, а производство 1000шт. изделий П2 приносит прибыль: 17000-15000=2000.   Функция, которую необходимо максимизировать будет такой:

.

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

Итак, нам нужно решить следующую  ЗЛП:

Решим данную ЗЛП методом симплексных таблиц:

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

Составим симплекс-таблицу и  по правилам преобразования, получим  оптимальное решение:

						b
	-3000	-2000	0	0	0	0
	20	10	1	0	0	200	10
	15	5	0	1	0	110	7,333
	10	10	0	0	1	120	12

 

						b
	0	-1000	0	200	0	22000
	0	3,333	1	-1,333	0	53,333	16
	1	0,333	0	0,0667	0	7,333	22
	0	6,667	0	-0,667	1	46,667	7

 

						b
	0	0	0	100	150	29000
	0	0	1	-1	-0,5	30
	1	0	0	0,1	-0,05	5
	0	1	0	-0,1	0,15	7

 

Получено оптимальное решение: .

 

Таким образом, предприятию следует  выпускать 5000 единиц изделия П1 и 7000 единиц изделия П2, при этом оно получит максимальную прибыль:

Вычисление в maple:

Ответ: 5000 единиц изделия П1 и 7000 единиц изделия П2.

 

 

 

 

 

 

Задание 9

  Найдите минимальное значение  функции   и точку ,  в которой оно достигается, методом золотого сечения.

Решение:

Золотое сечение – это такое  деление отрезка [a, b] на две неравные части при котором отношение большего отрезка ко всему интервалу равно отношению меньшего отрезка к большему. При этом имеет место следующее соотношение

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

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

 

Алгоритм метода.

Задаются a, b и погрешность e.

1. Вычисляются две точки золотого  сечения 

.

2. Если то ,

   иначе

3. Если  , то повторить  с п. 2.

4. Вычисляется  .

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

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

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

. С увеличением  значение увеличивается (возрастающая функция на ), также увеличивается значение . Поэтому, на промежутке функция . Соответственно возрастает на этом промежутке.

Исследуем теперь промежуток методом золотого сечения с точностью 0,001.

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

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

Вычислим теперь минимальное значение с помощью Maple:

Ответ: