Численные методы и оптимизация. Численные методы и методы оптимизации


Численные и вычислительные методы, оптимизация

 Темы   Автор   Ответы   Просмотры   Последнее сообщение 
Объявления
ВАЖНО! Прочтите перед написанием сообщения в этот раздел!

PAV

1

1514

12.02.2012, 16:34

PAV

Темы
Учебники и задачники по методам оптимизации

samson4747

5

2698

08.12.2013, 18:45

roman_slepnev

Учебники и сборники задач по вариационному исчислению

Bridgeport

4

1754

30.01.2013, 16:42

Bridgeport

Получить второй порядок аппроксимации (разностная схема)

[ На страницу: 1, 2 ]

netang

15

928

13.10.2018, 15:39

Eugeen1948

Неявный метод Рунге Кутта для решения жесткой системы ДУ

Antistas

13

2596

13.10.2018, 15:23

Eugeen1948

Транспортная задача и NP

[ На страницу: 1, 2 ]

max(Im)

17

1528

14.09.2018, 08:22

Gregory G

Извлечение квадратного корня вручную

Энер

4

3869

15.08.2017, 02:36

GAA

Помогите с зацикливанием симплекс-метода

[ На страницу: 1, 2 ]

slimsaw

21

2770

03.05.2017, 00:47

Andrey_Kireew

Максимальная площадь

[ На страницу: 1, 2 ]

alcoholist

21

1389

31.12.2016, 10:11

atlakatl

Симплекс-метод и ЛП в целом..

PeanoJr

5

948

20.09.2016, 13:11

falazure123

"Метод Лобачевского-Греффе" для решения алгебраических уравн

[ На страницу: 1, 2 ]

Sverest

15

2100

22.05.2016, 16:54

ansh

Аппроксимация ортогональными полиномами

[ На страницу: 1, 2 ]

tgv

15

3485

24.12.2015, 16:17

Евгений Машеров

Помогите придумать апроксимацию

[ На страницу: 1, 2, 3 ]

[email protected]

40

5541

11.08.2015, 22:16

Yahot

Приближённое вычисление смешанной производной 2-го порядка

Mr. Demetrius

8

1758

07.08.2015, 11:07

Pumpov

Алгоритм решения уравнения методом прогонки для 3х многого

[ На страницу: 1, 2 ]

IRIKA

16

912

12.06.2015, 19:54

vasya321

Промерзание грунта

[ На страницу: 1, 2 ]

RAEman

28

1206

02.06.2015, 18:29

RAEman

Разностная схема для уравнения переноса. Монотонность

Challenger

8

486

30.05.2015, 21:05

Challenger

Операции с матрицами

Aarnikotka

4

369

22.05.2015, 10:14

ИСН

Асимптотическая нормальность

vlad_light

0

185

21.05.2015, 14:42

vlad_light

Неравноточные измерения

vlad_light

2

226

20.05.2015, 21:42

vlad_light

МНК для f=A*sin(2*pi*f*t + phi) + b

[ На страницу: 1, 2 ]

kolchenkov

23

1044

20.05.2015, 08:36

Евгений Машеров

LASSO

Vandaler

3

327

06.05.2015, 21:09

мат-ламер

Квадратичная интерполяция-экстраполяция для экстремума

robot80

14

662

04.05.2015, 14:37

robot80

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

[ На страницу: 1, 2 ]

integer

25

1090

03.05.2015, 19:47

one man

Есть ли способы уменьшить погрешность измерений

Learner

8

509

29.04.2015, 23:25

Евгений Машеров

Измерения

Learner

3

293

28.04.2015, 19:53

grizzly

Нахождение экстремумов функции нескольких переменных

Aiyyaa

7

553

27.04.2015, 20:16

mihailm

Слабая формулировка уравнений мелкой воды

[ На страницу: 1, 2, 3 ]

VMMF

31

1906

26.04.2015, 18:26

VMMF

Подскажите где найти оценку Метода Монте-Карло.

yaneblinchik

4

290

25.04.2015, 21:16

dsge

Исследовать устойчивость явной схемы

netang

8

500

12.04.2015, 17:27

мат-ламер

Решение кубического уравнения аналитическим способом.

Punisher174

8

886

10.04.2015, 22:25

Punisher174

МНК

[ На страницу: 1, 2, 3, 4 ]

rlsp

55

2201

01.04.2015, 22:05

Евгений Машеров

Уравнение

VladQ

7

592

30.03.2015, 01:08

VladQ

Погрешность наклона аппроксимирующей прямой?

bastak

13

939

26.03.2015, 07:04

Евгений Машеров

Метод наименьших квадратов

cool.phenon

5

490

22.03.2015, 10:59

profrotter

Посоветуйте литературу по вариационному исчислению

tpm01

8

1941

14.03.2015, 22:25

tyrjoy

Уравнения с переменной в показателе степени

Anton_Peplov

6

474

12.03.2015, 23:10

Евгений Машеров

Найти экстремумы, определитель матрицы Гессе вырожден

integral2009

14

2841

10.03.2015, 23:04

ewert

численное решение уравнения теплопроводности

molblox

5

348

04.03.2015, 20:36

Vince Diesel

Система СДУ (метод Эйлера-Маруямы)

Smoker

1

276

01.03.2015, 19:00

Brukvalub

ЗЛП про карандаши

Baskura

3

347

23.02.2015, 15:01

ИСН

Аппроксимация с нормой L1

renegator

7

574

12.02.2015, 14:14

Евгений Машеров

Задача на условный экстремум

izirekter

6

447

05.02.2015, 22:53

izirekter

Метод сопряженных направлений нулевого порядка

netang

6

598

02.02.2015, 21:30

netang

Ошибка полиномиальной интерполяции

[email protected]

2

390

23.01.2015, 15:01

[email protected]

Применение численных методов

MOEVM

7

573

22.01.2015, 17:53

dsge

Модифицированный симплекс-метод

Damir(2)

3

399

20.01.2015, 15:24

Damir(2)

Разностные производные

SteelRend

6

626

19.01.2015, 22:44

Утундрий

Метод дробления шага

netang

7

769

14.01.2015, 08:53

netang

Аппроксимация данных.

fizik_ku

2

483

16.12.2014, 21:12

mserg

Аппроксимация рядом экспонент.

fizik_ku

5

708

16.12.2014, 00:25

fizik_ku

dxdy.ru

Численные методы оптимизации и их виды.

Введение

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

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

1) Линейное программирование;

2) Нелинейное программирование;

3) Динамическое программирование.

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

Построение математических моделей.

Задача использования сырья.  Для изготовления двух видов продукции Р1,Р2  используют три вида сырья: S1,S2 и S3. Запасы сырья, количество единиц сырья, затрачиваемых  на изготовление единицы   продукции, а также величина прибыли, получаемая от реализации единицы продукции, приведены в табл.1. Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.

Обозначим через x1 количество единиц продукции P1, а через x2 - количество единиц продукции P2. Тогда, учитывая количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также запасы сырья, получим систему ограничений

2x1+5x2 £ 20,

8x1+5x2 £ 40,

5x1+6x2 £ 30,

которая показывает, что количество сырья, расходуемое на изготовление продукции, не может превысить имеющихся запасов. Если продукция  P1 не выпускается, то x1=0 ; в противном случае x1>0. То же самое получаем и для продукции P2. Таким образом,на неизвестные x1 и x2  должно быть наложено ограничение неотрицательности:  x1 ³ 0 , x2³ 0 .

Таблица 1.

Виды сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции
Р1 Р2
S1 20 2 5
S2 40 8 5
S3 30 5 6
Прибыль от единицы продукции,   руб 50 40

Конечную цель решаемой задачи - получение максимальной прибыли при реализации продукции - выразим как функцию двух переменных  x1 и  x2. Реализация х1  единиц продукции вида Р1 и х2 единиц продукции вида  дает соответственно 50 х1 и 40 х2 сум. прибыли, суммарная прибыль  Z =50 x1+40 x2 (сум).

Условиями не оговорена неделимость единицы продукции, поэтому x1 и  x2 (план выпуска продукции) могут быть и дробными числами, следовательно, задача имеет бесконечное множество вариантов планов (значений  x1 и x2, которые удовлетворяют системе ограничений). Необходимо найти такие неотрицательные значения x1 и x2 ,при которых функция Z достигает максимума, т.е. найти максимальное значение линейной функции Z=50х1+40x2 при ограничениях

2x1+5x2 £20,

8x1+5x2 £40, x1 ³0,   x2 ³ 0.

5x1+6x2 £30,

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

Задачу использования сырья можно легко обобщить, если при выпуске n видов продукции используются m видов сырья. Обозначим через Si(i=1,2,…,m) виды сырья; bi - запасы сырья, i -го вида; Pi (i=1,2,…,n) -виды продукции; aij -количество единиц i - го сырья, идущего на изготовление единицы j - й продукции; Cj - величину прибыли, получаемой при реализации единицы j - продукции. Условия задачи запишем в табл.2.

Таблица 2.

Виды сырья Запас сырья Количество единицы i-го сырья идушего  на изготовление единицы j-й продукции
Р1 Р2 Pn
S1 b1 a11 a12 a1n
S2 b2 a21 a22 a2n
Sm bm am1 am2 amn
Прибыль С1 С2 Сn

Пусть xj - количество единиц j-й продукции, которое необходимо произвести. Тогда математическую модель задачи можно представить в следующем виде.

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

Z=C1x1+C2x2 +…+Cnxn при ограничениях

a11x1+a12x2+…+a1nxn£b1,

a21x1+a22x2+…+a2nxn£b2,

. . . . . . . . . . . . . . . . . . .       bi³0 (i=1,2,…,m),

am1x1­+am2x2+…+amnxn£bm,    xj³ (j=1,2,…,n).

Задача составления рациона.  При откорме каждое животное ежедневно должно получить не менее 9 ед. питательного вещества S1, не менее 8 ед. Вещества S2 и не менее 12 ед. вещества  S3. Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в табл.3.

Т а б л и ц а 3.

Питательные вещества Кол-во единиц питательных  веществ в 1 кг  корма
Корм I Корм II
S1 3 1
S2 1 2
S3 1 6
Стоимость 1кг корма , коп.

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

Для составления математической модели обозначим через x1 и   x2 cсоответственно количество килограммов корма I  и II в дневном рационе. Принимая во внимание значения, приведенные в табл.3. и условие, что дневной рацион удовлетворяет требуемой питательности только в случае, если количество единиц питательных веществ не меньше предусмотренного, получаем систему ограничений

3x1+x2 ³9,

x1+2x2 ³8,  x1³0,x2³0.

        

Если корм I не используется в рационе, то x1­=0 в противном случае x1>0. Аналогично имеем x2³0 т.е. должно выполнятся условие неотрицательности переменных: x1­³0,x2³0 .

Цель данной задачи - добиться минимальных затрат на дневной рацион, поэтому общую стоимость рациона можно выразить в виде линейной функции  Z=4x1+6x2 (коп). Задача является многовариантной, x1 и x2 могут принимать бесконечное множество значений. Из этого множества следует выбрать такие x1 и x2 , при которых функция  Z принимает минимальное значение. Таким образом, необходимо найти минимальное значение линейной функции Z=4x1+6x2 при

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

3x1+x2 ³9,

x1+2x2 ³8,  x1³0, x2 ³0.

X1+6x2 ³12,

Задачу составления рациона можно обобщить, если предусмотреть в рационе  m видов питательных веществ количестве не менее bi (i=1,2,…,m) (ед) и использовать n видов кормов. Для составления математической модели задачи обозначим через aij (i=1,2,…,m;j=1,2,…,n) кол-во единиц  i-го питательного вещества, содержащегося в единице j-го корма; Cj - стоимость единицы j-го корма; xj - кол-во единиц j-го корма в дневном рационе.

Необходимо найти минимальное значение линейной функции Z=C1x1+C2x2+…+Cnxn  при ограничениях

a11x1+a12x2+…+a1nxn³b1,

a21x1+a22x2+…+a2nxn³b2,

…………………………    xj³0 (j=1,2,…,n),

am1x1+am2x2+…+amnxn³bm, bi³0 (i=1,2,…,m).

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

Таким образом, системы ограничений в зависимости от условий задачи могут содержать не только линейные неравенства, но и линейные уравнения. При решении систем линейных неравенств с n неизвестными приходится сталкиваться с большими трудностями, поэтому от неравенств переходят к равенствам и решают систему линейных уравнений. Этот метод широко применяют при решении задач линейного программирования.

aim.uz

Численные методы и оптимизация

Московский  технический университет по связи и информатике

Заочная форма обучения

Курсовая работа по предмету:

Информатика

Тема: Численные методы и оптимизация

Студента 2 курса

Специальности 201000

Студенческий билет

Преподаватель:

2004 год

Задание

1. Для заданной функции y(x) методом наименьших квадратов для степенного базиса получить линейную F1(x) = a0 + a1x и квадратичную F2(x) = a0 + a1x + a2x2 аппроксимирующие функции:

-  составить и решить систему нормальных уравнений;

-  определить параметры аппроксимирующих функций;

-  вычислить значения аппроксимирующих функций в узлах аппроксимации;

-  построить график заданной функции (множество точек) и графики функций линейной и квадратичной аппроксимации;

-  оценить качество аппроксимации.

2. Найти два корня уравнения F2(x) = 0 с заданной точностью Е:

-  отделить корни;

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

-  выбрать начальное приближение;

-  записать рекуррентную формулу для уточнения корня;

-  оценить погрешность.

3. Вычислит dx при разбиении отрезка интегрирования на

n1 = 10 и  n2 = 20 подынтервалов , x1,  x2 - корни уравнения :

-  оценить погрешность.

4. Определить точку экстремума функции F2(x) методами одномерной оптимизации (с точностью Е):

-  проверить условие унимодальности и выбрать начальный отрезок оптимизации;

-  записать условие окончания поиска минимума (максимума) функции.

Задание 1. Функция y = y(x) задана таблицей.

Таблица 1

I

0

1

2

3

4

5

xi

0

2

4

6

8

10

y(x)

1

1.386

0.406

-0.939

-1.286

-0.266

Запишем параметры линейной аппроксимации:

x = = 4.285                      y =   = 0.043

a0 = y – a1x = 1.170952

a1 =   = -0.2241571

Искомая линейная аппроксимирующая функция:

F1(x) =-0.2241571х+1.170952

Составим и решим систему нормальных уравнений для определения параметров многочлена второй степени           F2(x) = a0 + a1x + a2x2

 

 (n+1)a0 + ( Σxi )a1 + ( Σxi2)a2  = Σ  yi

 ( Σxi )a0 + ( Σxi2)a1 + ( Σx3)a2   = Σ  xi yi

 (Σxi2)a0 + ( Σxi3 )a1 + ( Σxi4)a2  = Σ  xi2 yi .

Система нормальных уравнений:

 6а0      30а1         +  220а2   = 0.301

30а0  +  220а1      -  1800а2  =  -14.186

220а0  - 1800а1   +  15664а2 = -130.668

Решение системы нормальных уравнений:

а2 = 2.545535Е-02   а1 = -0.4787107   а0 = 1.510357

Искомая аппроксимирующая функция:

F2(x) = 2.545535E-02x2– 0.4787107 x1.510357

Значения аппроксимирующих функций F1{x} и F2{x} в узлах аппроксимации приведены в таблице 3:

X

0

2

4

6

8

10

F1{x}

1.170952

0.722638

0.274323

-0.1739

-  0.6223

-1.0706

F2{x}

1.51035

0.65475

2.799E-03

-0.4455

-0.6901

-0.7312

Таблица3

Графики  функций  линейной  и  квадратичной  аппроксимации  показаны  на рисунке

Оценим качество аппроксимации:

ρ = sqr(1/(n+1)* ∑ (Fm(xi) – y(xi))2)  

Для линейной функции: р1=0.5999658

Для квадратичной функции: р2=0.5435526

      p2<p1, значит аппроксимация квадратичной функции более качкственная.

Задание 2.  Решение уравнения F2(x) с точностью Е = 10-4. Для отделения корней уравнения F2(x)

составим таблицу знаков функции F2(x).

                                                                                                                     Таблица 4

X

-1

1

3

5

7

9

11

13

15

Sign F2(x)

+

+

+

-

-

-

-

-

+

На отрезках [3 5] и [12 15] функция F2(x) меняет знаки, т.е. существует, по крайней мере, по одному корню.

Производная F2'(x) = 0.051x-0.4787107,

F2"(x) = 0.051 > 0, следовательно, производная F2'(x) - монотонно возрастающая функция.

Составим таблицу знаков функции Аэ(ч) на выбранных отрезках:

X

3

5

13

15

Sign F2’(x)

-0.32571

-0.2237

0.18423

0.2863

vunivere.ru


Prostoy-Site | Все права защищены © 2018 | Карта сайта