Лекция: Уфа 2008

Федеральное агентство по образованию

Государственное образовательное учреждение высшего

Профессионального образования

Уфимский государственный авиационный технический университет

МАТЕМАТИЧЕСКИЕ МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

Для самостоятельной работы студентов по дисциплинам

«Математические методы и модели исследования операций»,

«Методы оптимизации», «Комбинаторные алгоритмы»

Часть 3

Элементы динамического программирования

Уфа 2008

Составители: Э.А. Мухачева, А.С. Филиппова, Т.Д. Тарасова

УДК 519.8 (07)

ББК 22.18 (я7)

Математические методы исследования операций: методические указания для самостоятельной работы студентов по дисциплинам «Математические методы и модели исследования операций», «Методы оптимизации», «Комбинаторные алгоритмы». Часть 3. Элементы динамического программирования. / Уфимск. гос. авиац. техн. ун-т; Сост.: Э.А. Мухачева, А.С. Филиппова, Т.Д. Тарасова. – Уфа, 2008. – 18 с.

Методические указания посвящены элементам динамического программирования: задачам о рюкзаке и другим прикладным проблемам, допускающим динамическое представление. Рассмотрены неограниченная, ограниченная и (0-1)-рюкзак задачи, приведены рекуррентные соотношения для их решения, описаны прямой и обратный подходы динамической шкалы. Все типы задач иллюстрированы практическими расчетами. Приведен большой перечень задач для самостоятельного решения.

Указания предназначены для выполнения домашних заданий, практических работ и самостоятельной работы студентов математико-экономических специальностей, в том числе «Математические методы в экономике» и по направлению подготовки бакалавров «Математика. Компьютерные науки» при изучении дисциплин «Математические модели и методы исследования операций», «Методы оптимизации», «Комбинаторные алгоритмы».

Табл. 8. Библиогр.: 5 назв.

Рецензенты: канд. физ.-мат. наук, доц. Шерыхалина С.М. (УГАТУ)

канд. физ.-мат. наук, доц. Авдюшева С.М. (БГУ)

авиационный технический университет, 2008

СОДЕРЖАНИЕ:

Введение…………………………………………………………………………...4

1. Элементы динамического программирования...……….…………..…..…5

2. Вложение капитала в предприятие ..………………………………………5

3. Задача о разгрузке рюкзака...………………………………………………8

3.1. Неограниченная задача о загрузке рюкзака...………………………..9

3.2. Ограниченная задача о загрузке рюкзака...………………………...12

3.3. Задача 0-1 рюкзак ……………………………………………………16