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

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

Функция перехода состояний:

Обратная прогонка:

m-й шаг:

…………………………………………………………………………..

i-йшаг:

…………………………………………………………………………..

1-й шаг:

Прямаяпрогонка:

Динамическое программирование. Задача о рюкзаке (контейнере, задача о загрузке).

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

Если бы не требование целочисленности решения, то задача была бы обыкновенной задачей линейного программирования.

Нарисуем схему переходов состояний с отображением управлений и выигрышей:

Требование целочисленности решения не гарантирует того, что контейнер будет загружен «до упора», но тем не менее стоит отметить, что на последнем шаге следует потратить как можно больше оставшейся грузоподъемности. Функция перехода состояний в данной задачи: .

Обратная прогонка:

m-й шаг:

Квадратные скобки там, где дробь – целая часть числа.

…………………………………………………………………………..

i-й шаг:

…………………………………………………………………………..

1-й шаг:

Прямаяпрогонка:

Данную задачу можно усложнить, если кромеограничению по грузоподъемности контейнера ввести ограничение по объему.

 

СМО, типы задач.

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

 

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

 

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

 

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

 

Требование, поступившее в систему обслуживания в момент, когда все обслуживающие аппараты заняты, не обязательно должно покинуть систему, но и не обязательно будет ждать конца обслуживания. Оно покинет систему, если будут выполнены некоторые дополнительные условия. При этом в различных задачах условия, при которых требование должно покинуть обслуживающую систему, могут быть самыми разнообразными. Так, например, в некоторых задачах массового обслуживания таким условием является ограниченное время пребывания требования в системе обслуживания. Если суммарное время пребывания требования в системе обслуживания (которое складывается из времени ожидания начала обслуживания и времени обслуживания) превысит определенную величину, то требование покидает обслуживающую систему независимо от того, начато его обслуживание или нет; а если обслуживание начато — то независимо от того, закончено оно или нет.

 

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

 

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

 

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

 

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

 

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

 

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