Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Задача построения оптимального маршрута

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

Пример. 6.1. Имеется план строительства дороги между пунктами А и В, на котором для любого промежуточного участка дороги известна предполагаемая стоимость его строительства (рисунок 9):

Рис. 9

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

Нарисуем еще раз план строительства, на котором промежуточные пункты изобразим в виде квадратиков (или кружков), куда в процессе решения будут заноситься некоторые числа (рисунок 10):

 

Рис. 10

Пронумеруем вертикальные линии (i = 0,1,2,3,4,5) и горизонтальные (j = 0,1,2,3). Тогда любой промежуточный пункт будет задаваться парой чисел (i, j), что соответствует координатам точки на плоскости (начальный пункт имеет координаты А(0,0), конечный В(5,3)). Обозначим через , который идет из пункта (i, j) вправо, то есть в пункт (i+1, j), а через - из пункта (i, j) в пункт (i, j+1) (рисунок 11).

Рис. 11

Пусть S(i, j) – это минимальная суммарная стоимость строительства маршрута, который идет из пункта (i, j) в конечный пункт В(5,3).

Очевидно, что в любом пункте (i, j) выбор одного из двух возможных направлений, вверх или вправо (это есть управления), должен осуществляться исходя из следующего функционального уравнения Беллмана:

.

Схема решения.

1. Очевидно, что

S(5,3)=0.

2. Определим значения , то есть для верхней строки по формуле

,

двигаясь по верхней строке справа налево:

, , ,
, .
(в процессе вычислений эти значения сразу заносим в соответствующие квадратики).

3. Аналогично определим значения , то есть для крайнего правого столбца двигаясь сверху вниз, по формуле:
,
, , .

4. Далее, определим все остальные значения S(i, j) пользуясь функциональным уравнением Беллмана, двигаясь справа налево и сверху вниз:
,
,
,
,
…, и т.д.
.

5. Заносим все вычисления в соответствующие квадратики (рисунок 12);

Рис. 12

таким образом, самый дешевый маршрут имеет стоимость
;

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

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

Задача распределения ресурсов

Важной экономической задачей, решаемой методом динамического программирования, является задача распределения ресурсов.

Пусть дан ресурс в объеме X, который необходимо распределить между N предприятиями. Известны также доходы от каждого предприятия номер k от получения ресурса в размере x = 0,…,N. Необходимо так распределить ресурс, чтобы совокупный доход был максимальным.

Обозначим - совокупный доход, получаемый r предприятиями от полученного ресурса в размере x, - количество ресурса, направляемое на предприятие номер k.

Величина определяется с помощью следующих рекуррентных отношений:

,

, .

Пример 6.2. Для развития трех торговых предприятий выделено 4 млн. руб. Известна эффективность капитальных вложений в каждое предприятие, заданное значением нелинейной функции . Требуется составить оптимальный план распределения капитальных вложений между предприятиями. Предполагается, что распределение денежных средств проводится в целых числах , = 0, 1, 2, 3, 4. Исходные данные приведены в таблице:

 

x
2,2 4,1 5,2
3,2 4,8 6,2
2,8 5,4 6,4 7,6

 

Производим вычисления, определяя тем самым и по аргументу функции .

r = 1: ;
x = 0: ;
x = 1: ;
x = 2: ;
x = 3:
  ;
x = 4:
  ;

 

r = 2: ;
x = 0: , ;
x = 1:
 
  , ;
x = 2:
 
  , ;
x = 3:
 
  , ;
x = 4:
 
 
  , ;
   
r = 3: ;
x = 0: , ;
x = 1:
 
  , ;
x = 2:
 
  , ;
x = 3:
 
  , ;
x = 4:
 
 
  , .

 

Результаты вычислений помещаем в таблицу:

 

 

x
2,2 4,1 5,2
2,2 4,2 5,4
2,8 5,4 7,6 9,6

 

Из таблицы видно, что при выделении x = 4 млн. руб. (первая строка, последний столбец) трем предприятиям максимальная прибыль составит млн. руб. (шестая строка, шестой столбец), при этом на долю третьего предприятия выделяется млн. руб. Осталось распределить

4 – 2 = 2 млн. руб. Согласно строке 5 таблицы при x = 2, . Следовательно, на долю первого предприятия приходится 2 – 1 = 1 млн. руб.

Итак, при распределении 4 млн. руб. максимальная прибыль в размере 9,6 млн. руб. достигается при выделении первому предприятию одного млн. руб., второму – одного млн. руб. и третьему – двух млн. руб.

 

Последнее изменение этой страницы: 2016-07-23

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...