ТОП 10:

Расчет потенциалов и проверка критерия оптимальности, переход к новому базису



Для базисных переменных должно выполняться vj:=ui+cij. Положим u1=0, тогда по этой формуле по клетке (1,2) v2=0+2=2, по клетке (1,2) v2=0+7=7. Из клетки (2,2) u2=7–4=3. Продолжая аналогичным образом, получим информацию, приведенную в следующей таблице

  j=1 j=2 j=3 j=4  
b1 b2 b3 b4
i=1 a1     u1
         
i=2 a2     u2
–7            
i=3 a3     u3
–6   –2      
   
v1 v2 v3 v4

Подсчитываем значения dij по формуле dij=vj–ui–cij и заносим в таблицу. Для базисных клеток dij =0. В клетке (1,4) dij>0, поэтому включаем эту клетку в базис, но нам нужно определить клетку, выходящую из базиса. Выполним это на следующей таблице, в ней клетка (1,4) затемнена. Легко видеть, что затемненные клетки образуют цикл (1,4)Þ(3,4)Þ(3,3)Þ(2,3)Þ(2,2,)Þ(1,2)Þ(1,4)

  j=1 j=2 j=3 j=4  
b1 b2 b3 b4
i=1 a1   «+» u1
    «–»    
i=2 a2     u2
–7   «+»   «–»    
i=3 a3     u3
–6   –2   «+» «–»
   
v1 v2 v3 v4

Заносим в позицию q клетки значения «+» и «–». В каждой строке и в каждом столбце их должно быть ровно по одному значению. Начинаем с клетки (1,4), далее идет чередование. В соответствии с этим, положим x1,4=x1,4+Q, x 3,4=x 3,4 Q, x3,3=x3,3+ Q, x2,3=x2,3Q, x2,2=x2,2+ Q, x 1,2=x 1,2 Q. Увеличиваем значение от нуля до значения, когда одна из этих переменных обратится в 0, это будет при Q=min(x34, x23, x12)=1. Этот минимум достигается на клетке (1,2), поэтому она исключается из базиса (если минимум достигнут на нескольких клетках, то исключается из базиса только одна). Выполним преобразования и данные внесем в таблицу

  j=1 j=2 j=3 j=4  
b1 b2 b3 b4
i=1 a1     u1
               
i=2 a2       u2
               
i=3 a3       u3
             
           
v1 v2 v3 v4

Значение функционала на этом решении будет равно

F=2´10+4´1+4´16+3´1+3´13+7´11=191.

Этот алгоритм повторяем до тех пор, пока не окажется, что все значения dij£0. Оптимальным решением будут значения xij последней таблицы.

Самостоятельная работа 14.

Решить транспортную задачу при m=3, n=4. Значения векторов a и b, матрицы С взять из таблицы в соответствии с номером варианта:


 

Вариант a b C

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Динамическое программирование и потоки в сетях

 

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

Задача оптимизации многошаговых процессов, задача о ранце.

Задача оптимизации многошаговых процессов имеет вид

(7.1)
при ограничениях  
x0=a0ÎX0={a0}, (7.2)
xi=f i(xi–1, ui), i=1,2,3,...,n, (7.3)
xiÎXi , i= 1,2,3,...,n, (7.4)
uiÎUi , i=1,2,3,...,n, (7.5)
где Xi, Ui , i=1,2,3,...,n, – конечные множества.

Обозначим через Wi(xi) максимум в следующей задаче:

 
при ограничениях  
xiÎXi,  
xk=f k(xk–1, uk), k=i+1,2,3,...,n,  
xkÎXk , k=i+1,2,3,...,n,  
ukÎUk , k=i+1,2,3,...,n,  
где Xk, Uk , k=i+1,2,3,...,n, – конечные множества.

 

Справедливо следующее функциональное соотношение Беллмана:

Для того, чтобы решение ((xi) i=0,1,2,...,n, (ui)i=1,2,3,...,n),удовлетворяющее ограничениям (7.1) – (7.5) было оптимальным, необходимо и достаточно, чтобы

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

Алгоритм.

Первый этап.

1. Для всех xÎXn положить Wn(x)=0;

2. Последовательно для i=n–1, n–2, n–3,…,0 выполнить:

для всех xÎXi положить:

Второй этап.

1. Положить x0:=a0;

2. Последовательно для i=1, 2,3,…, n положить :

Полученное в результате работы алгоритма решение ((xi) i=0,1,2,...,n, (ui)i=1,2,3,...,n)будет оптимальным для задачи (7.1) – (7.5). Оптимальное значение функционала будет равно W0(a0).

Задача о ранце имеет вид

(7.6)
при ограничениях  
(7.7)

где ui целые числа i =1,2,3,...,n. Числа ai также будем рассматривать целыми, i=1,2,3,...,n.

Введем переменные x0=0, . Из задачи (7.6) – (7.7) получим эквивалентную задачу

, (7.8)
при ограничениях  
x0=0, (7.9)
xi=f(xi–1, ui)=xi–1+ai ´ ui, i=1,2,3,..., n, (7.10)
xiÎXi={0,1,2,...,b}, i=1,2,3,..., n, (7.11)
uiÎUi={0,1,2,...,b}, i=1,2,3,..., n. (7.12)

 

Задача (7.8) – (7.12) имеет такой же вид, как и задача (7.1) – (7.5), поэтому для ее решения можно применить алгоритм, описанный выше. Легко показать, что для задачи о ранце

 
при ограничениях  
 

Соотношение Беллмана примет вид

где [a] – целая часть числа a.

Пример.Решить задачу:

u1 +2u2 Þ max
2u1 +u2 £
u1, u2целые.

В этой задаче n=2, b=3, поэтому таблица с результатами вычислений будет иметь вид:

  i
W0 u1 W1 u2 W2
x

Приведем пояснения к заполнению этой таблицы в соответствии с выполнением алгоритма.

Первый этап.

Заполнение столбца W2 понятно, оно соответствует выполнению пункта 1 первого этапа алгоритма. Покажем, как заполнялась клетка (x,i)=(0,1). Ее заполнение соответствует вычислению

для x=0, i=0,

или

В соответствии с этим, Так как W2(x)º0 (см. таблицу), то

Аналогично получены все остальные элементы этого столбца.

Покажем вычисления для клетки (0,0). Для нее

При u=0 ,

При u=1 ,

Таким образом, W0(0)=6, u1(0)=0.

Остальные клетки столбца 0 не заполняем, так как X0={0}.

Второй этап.

1. x0=0. (в следующей таблице клетка (0,0) выделена )

2. u1=u1(x0)= u1(0)=0, x1=x0+2´ u1=0 (клетка (0,1) выделена )

3. u2=u2(x1)= u2(0)=3, x2=x1+1´ u2=3 (клетка (3,2) выделена )

  i
W0 u1 W1 u2 W2
x

Ответ. Максимальное значение функционала в задаче равно 6, u1=0, u2=3.

Самостоятельная работа 15.

Решить задачу о ранце при n=5, b=8, значения c(i) , a(i), i=1,2,3,...,n,взять из следующей таблицы в соответствии с номером варианта.

Вариант Вектор a Вектор с

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Результаты представить ввиде таблицы

  i
W0 u1 W1 u2 W2 u3 W3 u4 W4 u5 W5
x                      
                 
                 
                 
                     
                 
                 
                 
                     

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

 







Последнее изменение этой страницы: 2016-06-29; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.228.10.64 (0.035 с.)