Задачи динамического программирования.

1. Решение задачи набора высоты и скорости. Самолет, находящийся на высоте H₀ и летящий со скоростью V₀, должен быть поднят на высоту H₁, а его скорость доведена до V₁. Известны удельные расходы горючего для подъема на высоту при неизменной скорости, для увеличения скорости при неизменной высоте, для одновременного увеличения высоты и скорости. Найти траекторию, обеспечивающую минимальный расход горючего.

(Вентцель Е.С. Введение в исследование операций. Москва: Изд-во «Советское радио», 1964.)

Метод Литтла

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

(Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для ВУЗов/ Под ред. В.С. Зарубина, А.П. Крищенко. – М.: Изд-во МГТУ им Н.Э. Баумана, 2000 – 436 с.)

2. Решение задачи коммивояжера с помощью метода Литтла. Путешественник выбрал n мест, которые намеревался посетить, получил информацию о стоимости проезда самолетом в каждый из выбранных городов и стоимость проезда из одного города в другой. Учел все льготы, предоставляемые авиакомпаниями, и составил матрицу стоимостей  проезда в выбранные города и обратно. Зная матрицу стоимостей, путешественнику надо так составить маршрут путешествия, чтобы затраты на путешествие были минимальными и чтобы каждый пункт посещался только один раз.

(Грешилов А.А. Прикладные задачи математического программирования. Учебное пособие. – 2-е изд. – М.: Логос, 2006. – 288.: ил.)

Графы

1. Решение задачи о максимальном потоке. Найти максимальное количество информации, которое может быть передано из источника I в сток S по сети, имеющей m пунктов, пропускные способности ребер которой равны .

(Грешилов А.А. Прикладные задачи математического программирования. Учебное пособие. – 2-е изд. – М.: Логос, 2006. – 288.: ил.)

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

(Косоруков О.А,, Мищенко А.В. Исследование операций: Учебник / Косоруков О.А., Мищенко А.В. // Под общ. ред. д.э.н., проф. Н.П. Тихомирова. — М: Издательство «Экзамен», 2003. — 448 с.)

3. Решение задачи о нахождении минимального остова на графе. Дана страна, в которой имеется n городов. Необходимо соединить все города телефонной сетью так, чтобы общая длина телефонного кабеля была минимальной. Расстояние между городами равно .