Задача о наборе высоты и скорости самолетов.

↑

⇐ ПредыдущаяСтр 23 из 28Следующая ⇒

Задача о наборе высоты и скорости самолетов.

Постановка. Самолет находится на высоте  и имеет некоторую скорость . Требуется найти минимальные затраты топлива, которые позволили бы ему подняться на высоту  и приобрести скорость . Для ее решения также применим метод динамического программирования. При инвариантном погружении вводится декартова система координат на плоскости. При инвариантном погружении отрезки [ , ] и [ , ] разбиваются на некоторое количество равных частей и делается предположение, что в результате отдельной операции самолет может набирать скорость, т.е. двигаться по оси , либо только набирать высоту.

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

29. Теория расписаний. Задача обслуживания заявок на одном приборе

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

Постановка задачи. Имеется некоторый прибор и имеется n-заявок на этом приборе. На каждой заявке указано время t_i  и c_i - штраф за единицу времени ожидания в очереди. Требуется задать такую последовательность обслуживания всех заявок, чтобы суммарный штраф был минимальным.

Математическая модель                         

Обозначим через                         - последовательность обслуживания. Это и будет план задачи. Множество всех планов последовательности обслуживания – это множество перестановок из n-чисел – будем обозначать через  . Ясно, что всего планов будет n!. Посчитаем суммарный штраф для последовательности :

(2.6.1)

Математическую модель задачи получаем в виде:

(2.6.2)

Пусть  - оптимальный план. Тогда  т. е. получаем необходимое условие оптимальности  ,  

 Это соотношение можно переписать в виде:

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

Пример 2.6.2. Имеется матрица Т запросов заявок:

n

Оптимальная последовательность: = (2, 5, 1, 4, 3).

Минимальный суммарный штраф в итоге будет равным:

     .

Познавательные статьи:



Техника прыжка в длину с разбега

Тактические действия в защите

История Олимпийских игр

История развития права интеллектуальной собственности