Файл: Контрольная работа по Методам оптимизации.docx

Добавлен: 19.10.2018

Просмотров: 3539

Скачиваний: 56

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

Оглавление

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

1.Исследование функции на безусловный экстремум

2. Численные методы безусловной минимизации

Метод конфигураций (Хука-Дживса)

Метод деформируемого многогранника (Нелдера-Мида)

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

Метод наискорейшего градиентного спуска

Метод сопряженных направлений (Флетчера – Ривса)

Метод Ньютона

Порядок выполнения лабораторной работы

Пример выполнения лабораторной работы

3. Решение задачи минимизации со смешанными ограничениями

Седловые точки функции Лагранжа

Метод седловой точки в задачах квадратичного программирования

Метод проекции градиента для задачи условной оптимизации

Метод условного градиента для задачи условной оптимизации

Метод возможных направлений для задачи условной оптимизации

Порядок выполнения лабораторной работы

Пример выполнения лабораторной работы

4. Основные понятия линейного программирования

Модель задачи линейного программирования

Свойства задачи линейного программирования

Двойственность в линейном программировании

5. Задача транспортного типа

Построение модели транспортной задачи

Методы нахождения начального плана перевозок.

Метод потенциалов

Контрольные задания

Задание 1. Линии уровня

Задание 2. Числовые характеристики симметричной квадратной матрицы.

Задание 3. Формула Тейлора для функции нескольких переменных

Задание 4. Нахождение локальных экстремумов

Задание 5. Одномерная оптимизация

Задание 6. Многомерная оптимизация по направлению

Задание 7. Методы безусловной оптимизации

Контрольные вопросы

Задание 8. Методы условной оптимизации

Контрольные вопросы

Задание 9. Задача линейного программирования и симплекс-метод

Задание 10. Транспортная задача

Литература

Приложение. Рекомендации по использованию EXCEL и MATLAB

П1. Построение графиков

П2. Действия с матрицами

Вариант 5. Проектируется бак-кессон крыла самолета. Он состоит из уголков (26 шт.), гнутиков (14шт.), нервюр (7 шт.), лонжеронов (2 шт.), дополнительных лонжеронов (6 шт.), обшивки (2 шт.).

По ТУ заданы определенные ограничения на веса компонент. Вес уголков, гнутиков, нервюр и дополнительных лонжеронов с запасом в 10 кг не должен превышать общего веса обшивок. Для стапельных работ необходимо, чтобы вес нервюр, дополнительных лонжеронов и гнутиков был не более 20 кг. Вес каркаса одного отсека (две нервюры и один дополнительный лонжерон) должен составлять 10% от веса одной обшивки. Вес основных и дополнительных лонжеронов не может быть менее 30 кг. Необходимо найти согласованные веса всех составляющих так, чтобы общий вес пустого бака-кессона крыла самолета был минимален.

Вариант 6. Стандартом предусмотрено, что октановое число автомобильного бензина А-76 не должно быть ниже, чем 76, а содержание серы в нем не должно превосходить 0,3%. Для изготовления этого бензина используется смесь из 4 компонентов I, II, III и IV, имеющих разное октановое число и содержание серы:


I

II

III

IV

Октановое число

68

72

80

80

Содержание серы, %

0,35

0,35

0,3

0,2

Ресурсы, тонн

700

600

500

300

Себестоимость, руб.

40

45

60

90



Составить план получения бензина А-76 с минимальной себестоимостью.

Вариант 7. Нефтеперерабатывающий завод получает четыре полуфабриката: 400 тыс. л алкилата, 250 тыс. л крекинг-бензина, 350 тыс. л бензина прямой перегонки и 100 тыс. л изопентона.

В результате смешивания этих четырёх компонентов в разных пропорциях образуется три сорта авиационного бензина: бензин А – 2:3:5:2, бензин B – 3:1:2:1 и бензин C – 2:2:1:3.

Стоимость 1 тыс. л указанных сортов бензина характеризуется числами: 120 руб., 100 руб. и 150 руб.

Определить план смешения компонентов, при котором будет достигнута максимальная стоимость всей продукции.

Вариант 8. Из четырёх видов основных материалов (медь, цинк, свинец, никель) составляют три вида сплавов латуни: обычный, специальный и для художественных изделий. Цены единицы веса меди, цинка, свинца и никеля составляют 0,8 руб., 0,6 руб., 0,4 руб. и 1,0 руб., а единицы веса сплава, соответственно, 2 руб., 3 руб., 4 руб.

Сплав для художественных изделий должен содержать не менее 6% никеля, не менее 50% меди и не более 30% свинца; специальный – не менее 4% никеля, не менее 70% меди, не менее 10% цинка и не более 20% свинца. В обычный сплав компоненты могут входить без ограничений.

Производственная мощность предприятия позволяет выпускать не более 400 ед. веса обычного сплава, не более 700 ед. веса специального сплава и не более 100 ед. веса декоративного сплава.

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

Задание 10. Транспортная задача

Решить транспортные задачи, заданные матрицами перевозок



Вар.1


В1

В2

В3

В4

В5

В6

В7



115

200

60

40

75

50

120

А1

240

2

М

8

11

3

1

5

А2

180

7

4

3

12

5

9

М

А3

90

1

10

5

1

4

6

2

А4

45

4

4

4

4

4

4

4

А5

100

9

6

5

3

2

1

5


Вар.2


В1

В2

В3

В4

В5

В6

В7



250

40

100

170

80

100

65

А1

35

2

5

8

11

3

1

5

А2

60

7

4

3

12

5

9

8

А3

120

1

10

5

1

4

6

2

А4

250

4

4

4

М

4

4

4

А5

180

9

6

5

3

2

1

5

Учесть, что по маршруту 3-7 должно быть перевезено ровно 50 единиц груза


Вар.3


В1

В2

В3

В4

В5

В6

В7



30

115

45

80

75

80

120

А1

30

2

М

8

11

3

1

5

А2

100

7

4

3

12

5

9

2

А3

200

1

10

5

1

4

6

2

А4

55

4

4

4

4

4

4

4

А5

175

9

6

5

3

2

1

5

Учесть, что из пункта А1 весь груз должен быть вывезен


Вар.4


В1

В2

В3

В4

В5

В6

В7



30

115

45

80

75

80

120

А1

240

2

7

8

11

3

1

5

А2

180

7

М

3

12

5

9

2

А3

90

1

10

5

1

4

6

2

А4

45

4

4

4

4

4

4

4

А5

100

9

6

5

3

2

1

5

Учесть, что из пункта А2 весь груз должен быть вывезен



Литература

  1. Стандарт предприятия: Общие требования и правила оформления дипломных и курсовых проектов (работ). СТП УГТУ-УПИ 1-96. Екатеринбург, 1996.

  2. Акулич И.Л. Математическое программирование в примерах и задачах. – М.; Высшая школа, 1993. – 335 с.

  3. Аттетков А.В., Галкин С.В., Зарубин В.С. Методы оптимизации - М.; Издательство МГТУ им. Н.Э. Баумана, 2004. - 432 с

  4. Васильев В.П. Численные методы решения экстремальных задач. - М.: Наука, 1980. - 518 с.

  5. Габбасов Р., Кириллова Ф.М. Методы оптимизации. – Минск: Изд-во БГУ, 1981. -

  6. Дьяконов В. Matlab: учебный курс / В. Дьяконов. СПб.: Питер, 2001. 560 с.

  7. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. – М.; Высшая школа, 2005. – 544 с.

  8. Васин В.В., Еремин И.И. Операторы и итерационные процессы фейеровского типа (теория и приложения). Москва-Ижевск: Институт компьютерных исследований, НИЦ «Регулярная и хаотическая динамика», 2005. – 200 с.

  9. Визильтер Ю.В., Горбацевич В.С. Описание формы объектов на изображениях при помощи гибких структурирующих элементов // Сборник трудов научно-технической конференции «Техническое зрение в системах управления 2011». М.: ИКИ РАН. 2011. С. 162-167.

  10. Горбацевич В.В. Современное линейное программирование (Сборник задач с решениями на MAPLE5). М.: 1999 – 34 с.

  11. Калихман И.Л. Сборник задач по математическому программированию. Изд. 2-е доп. и перераб. М., «Высш. школа», 1975. 270 с. с ил.

  12. Схрейвер А. Теория линейного и целочисленного программирования: В 2-х т. Т. 1: Пер. с англ. – М.: Мир, 1991. – 360 с., ил.

  13. Филатов А.Ю. Развитие алгоритмов внутренних точек и их приложение к системам неравенств: Автореф. дис. ... канд. физ.-матем. наук. Иркутск, 2001. 19 с.



Приложение. Рекомендации по использованию EXCEL и MATLAB

П1. Построение графиков

Для построения графика функции y=f(x1,x2) могут быть использованы следующие инструменты:

  1. В EXCELМастер диаграмм, подтип Поверхность.

  • Используя автозаполнение, на листе EXCEL в столбец А и первую строку с выбранным шагом ввести соответственно значения переменных x1 и x2, для которых будут вычисляться значения функции.

  • В ячейку В2 ввести выражение для вычисления функции f(x1,x2) в точках $A2, B$1 (знак $ - признак абсолютной адресации, при которой будут зафиксированы первый столбец– перебор значений переменной x1 и первая строка – перебор значений переменной x2) и нажать одновременно три клавиши Ctrl, Shift, Enter, поскольку формула используется для обработки массивов. В строке формул должны появиться фигурные скобки.

  • Выделить ячейку В2 и, протянув маркер заполнения сначала вниз, пробегая все ячейки, заполненные в столбце А. а затем вправо, пробегая все ячейки, заполненные в строке 1, заполнить массив значений функции в узловых точках области построения графика.

  • На вкладке Стандартные Мастера диаграмм выбрать Поверхность. Поверхностная диаграмма дает 3-мерное изображение функции, а Контурная диаграмма представляет вид сверху на поверхностную диаграмму и является аналогом линий уровня исследуемой функции.

  • В MATLAB – функции plot3, mesh, surf, surfl.

    • С помощью функции meshgrid получить двумерные массивы координат узловых точек области построения графика: u=a:∆1:b; v=c: 2:d; [x,y]=meshgrid(u,v);

    • Задать исследуемую функцию: f= f(х,у);

    • Применяя указанные выше функции, получить трехмерное изображение: plot3(x,y,f) или mesh(x,y,f), surf(x,y,f), surfl(x,y,f).

    П2. Действия с матрицами

    Для нахождения собственных значений и собственных векторов матрицы Гессе могут быть использованы следующие инструменты MATLAB

    • λ = eig(a) - функция eig(a) возвращает собственные значения заданной матрицы a. Пример задания матрицы 4х4: a = [16 3 2 13; 5 10 11 8; 9 6 7 12; 4 15 14 1] .

    • [v,d] = eig(a) – при таком обращении функция возвращает собственные векторы v и собственные значения как элементы диагональной матрицы d.

    Для нахождения матрицы, обратной матрице Гессе могут быть использованы следующие инструменты:

    1. В EXCEL – функция МОБР возвращает обратную матрицу для матрицы, хранящейся в массиве.

    2. В MATLAB – функция y=inv(a) возвращает обратную матрицу для матрицы a.





    60