7453

1.Этап j ставится в соответствии типу j, j=1,2,…,N.

2.Состояние y j на этапе j выражает суммарный вес вопросов, количество от-

ветов на которые приняты на этапах j, j+1,…,N; при этом y1 W и yi 0,1, ,W при j=2,3,…,N.

3. Варианты решения k j на этапе j описываются количеством вопросов типа j.

Значение k j заключено в пределах от нуля до [Ww j ], где [Ww j ] – целая часть числа (Ww j ).

Пусть fi ( yi ) – максимальный суммарный вес вопросов, ответы на которые приняты на этапах j, j+1,…,N при заданном состоянии y j .

Рекуррентное соотношение (для процедуры обратной прогонки) имеет сле-

Оптимальное решение определяется теперь следующим образом. Из условия

W=30 следует, что первый этап решения задачи при y1 =30 дает оптимальное реше-

ние k1=0, которое означает, что на 0 (нуль) вопросов 1-го типа будут даны ответы.

Далее находим:

Соответственно оптимальным решением задачи является (0,0,4,1,0,0,5,7), соот-

ветственно максимальное количество баллов, которое студент может набрать за от-

веденное время, равно 46.

Анализ чувствительности решения.

В таблице для первого этапа нам, по существу, необходимо получить опти-

мальное решение лишь для y1 =30, так как это последний этап, подлежащий рас-

смотрению. Однако в таблицу включены вычисления для y1 =0,1,…,30, которые по-

зволяют провести анализ чувствительности решения.

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

дет 20, вместо 30?

Соответственно максимальное количество баллов, которое студент может на-

52

брать за отведенное время, равно 34.

Что произойдет, если время, отводимое на контрольную работу, будет 5 вместо

30?

Соответственно максимальное количество баллов, которое студент может на-

брать за отведенное время, равно 39.

Пример 9. Для двух предприятий выделено 1400 у.е. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от

х единиц, вложенных в первое предприятие, равен f1(x) 3x , а доход от у единиц,

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

Решение Процесс распределения средств разобьем на 4 этапа по соответствующим го-

дам.

Обозначим k xk yk – средства, которые распределяются на k-м шаге как сумма средств по предприятиям.

Суммарный доход от обоих предприятий на k-м шаге:

Zk f1(xk ) f2 (Sk xk ) 3xk 4(Sk xk ) 4Sk xk .

Остаток средств от обоих предприятий на k-м шаге:

Sk 1 g1(xk ) g2 (Sk xk ) 0,5xk 0,3(Sk xk ) 0,3Sk 0,2xk .

Обозначим zk* (Sk ) – максимальный доход, полученный от распределения средств Sk между двумя предприятиями с k-го шага до конца рассматриваемого пе-

риода.

Рекуррентные соотношения Беллмана для этих функций:

убывающая функция достигает максимума в начале рассматриваемого промежутка, т. е. при x4 0 .

3-й шаг.

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

промежутка, т. е. при x3 0 .

54

2-й шаг.

к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т. е. при x2 S2 .

1-й шаг.

линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т. е. при x1 S1.

Результаты оптимизации:

Z3* (S3 ) 5,2 S3 , х3* 0

Z4* (S4 ) 4S4 , х4* 0

Определим количественное распределение средств по годам.

Представим распределение средств в виде таблицы:

55

4.Методические указания по организации самостоятельной работы

4.1Общие рекомендации для самостоятельной работы

Самостоятельная работа студентов является основным способом овладения учебным материалом в свободное от обязательных учебных занятий время.

Целями самостоятельной работы студентов являются:

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

-углубление и расширение теоретических знаний;

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

-развитие познавательных способностей и активности студентов:

-формирования самостоятельности мышления, способностей к саморазвитию,

самосовершенствованию и самореализации.

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

либо с подготовкой к курсовой, дипломной работе, а также к защите ВКР. В данном разделе рассматривается только самостоятельная работа первого вида.

Самостоятельная работа выполняется в два этапа: планирование и реализация.

Планирование самостоятельной работы включает:

-уяснение задания на самостоятельную работу;

-подбор рекомендованной литературы;

-составление плана работы, в котором определяются основные пункты предстоящей подготовки.

Составление плана дисциплинирует и повышает организованность в работе.

На втором этапе реализуется составленный план. Реализация включает в себя:

-изучение рекомендованной литературы;

-составление плана (конспекта) по изучаемому материалу (вопросу);

-взаимное обсуждение материала.

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

56

Оставшийся восполняется в процессе самостоятельной работы. В связи с этим работа с рекомендованной литературой обязательна.

Работа с литературой и иными источниками информации включает в себя две группы приемов: техническую, имеющую библиографическую направленность, и

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

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

-поиск через систематический каталог в библиотеке;

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

-использование материалов, размещенных в сети Интернет.

Для того, чтобы не возникало трудностей понимания текстов учебника,

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

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

В процессе взаимного обсуждения материала закрепляются знания, а также приобретается практика в изложении и разъяснении полученных знаний,

развивается речь.

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

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

Ведение записей способствует превращению чтения в активный процесс. У

57

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

Можно рекомендовать следующие основные формы записи: план, конспект,

тезисы, презентация.

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

Конспект – это систематизированное, логичное изложение материала источника. Объем конспекта не должен превышать 10 страниц. Шрифт Times New Roman, кегль 14, интервал 1,5. Список литературы должен состоять из 5-8

источников, по возможности следует использовать последние издания учебных пособий и исследований.

Тезисы – это последовательность ключевых положений из некоторой темы без доказательств или с неполными доказательствами. По объему тезисы занимают одну страницу формата А4 или одну – две страницы в ученической тетради. В конце тезисов студент должен сделать собственные выводы.

Презентации по предложенной теме составляются в программе Power Point или

Impress. Количество слайдов должно быть не менее 15 и не превышать 20 слайдов.

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

4.2Темы для самостоятельного изучения

1.Методы прямого поиска. Методы случайного многомерного поиска.

2.Методы минимизации многомодальных функций. Метод ломаных.

58

3.Минимизация функций по правильному (регулярному) симплексу (метод Нелдера-Мида).

4.Метод параллельных касательных. Метод Пауэлла.

5.Метод сопряженных градиентов (Флетчера-Ривса).

6.Многомерный поиск. Метод вращающихся координат (Розенброка).

7.Метод Давидона-Флетчера-Пауэлла (DFP-формула).

8.Спуск с ограничениями. Метод возможных направлений Метод Зойтендейка.

9.Сравнение эффективности различных численных методов. (тест Розенброка,

Пауэлла и др.).

10.Многомерный поиск. Метод Хука-Дживса.

11.Метод внешних штрафных функций.

12.Внутренние штрафные функции. Метод Фиакко и Маккормика

13.Метод барьерных функций.

14.Внутренние штрафные функции. Метод Эрроу –Гурвица.

15.Метод Левенберга-Марквардта.

16.Метод обобщенного координатного спуска.

17.Метод Брента.

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

19.Модификация многомерных методов нулевого порядка для случая ограничений типа a<=x<=b.

20.Проблема овражности и её решение. Сравнительный анализ поведения некоторых методов.

21.Метод штрафной функции без параметров.

22.Метод точной штрафной функции (Пауэлл-Хестенс-Рокафеллар).

23.Обзор последних англоязычных работ по методам нелинейной оптимизации.

Анализ развития теории нелинейной оптимизации после классических работ

(Зангвилл, Зойтендейк, Гилл и проч.).

24. Реализация методов линейного поиска и их сравнительный анализ (золотое сечение, Брент и т.д.) на примере метода градиентов Коши.

59

4.3Учебно-методическое обеспечение самостоятельной работы

1.Кремер Н.Ш. Исследование операций для экономистов. – М.: ЮНИТИ,

2006.

2.Таха Х. Введение в исследование операций. – М.: Вильямс, 2007.

3.Гончаров В.А. Методы оптимальных решений: учеб. пособие для студентов вузов по спец. 010501(010200) "Приклад. математика и информатика", 230105(220400) "Програм. обеспечение вычислит. техники и автоматизир.

систем" / В. А. Гончаров. – М. : Юрайт : Высш. образование, 2010.

4. Базара, Шетти. Нелинейное программирование. Теория и алгоритмы. –М.:

Мир, 1982.

5. Бейко И.В., Бублик Б.Н., Зинько П.Н. Методы и алгоритмы оптимизации. –

М.: Высш. шк., 1983.

6.Пантелеев А. В., Летова Т.А. Методы оптимальных решений в примерах и задачах: учебное пособие, 2-е издание – М.: Высш. шк. , 2005 – 544 с.

7.Аттетков А. В. , Зарубин В. С., Канатников А. Н. Введение в Методы опти-

мальных решений : учебное пособие. – М. : Финансы и статистика, 2014.

8.Васильева О. А. , Ларионов Е. А., Лемин А. Ю., Макаров В. И. Методы оп-

тимальных решений : учебное пособие. – М. : Московский государственный строительный университет, ЭБС АСВ, 2014.

9.Ф. Гилл, У. Мюррей, М. Райт: Практическая оптимизация .– М.: Мир, 1985.

10.Пантелеев А.В., Летова Т.А. Методы оптимальных решений в примерах и задачах: Учебное пособие. – М.: Высш. шк., 2002. -544с.

11.Лесин В.В., Лисовец Ю.П. Основы методов оптимизации: Учебное посо-

бие. – СПб.: Издательство «Лань», 2011. – 352 с.

12.Ларин Р.М., Плясунов А.В., Пяткин А.В. Методы оптимальных решений.

Примеры и задачи: Учебное пособие. – Новосибирск: Новосибирский госу-

дарственный университет, 2003. – 120 с.

13.Мудров А.Е. Название: Численные методы для ПЭВМ на языках Бейсик,

Фортран и Pascal. – Томск: Издательство «Раско», 1991.

60