Планування кроку 1. Приклад застосування алгоритму АПП по дуга, що входять х

Приклад застосування алгоритму АПП по дуга, що входять х

Алгоритмом прямої прогонки розв’яжемо ЗЗНШ для мережі, що представлена на рис. 10.

Оскільки при розв’язанні задачі застосовується пряма прогонка, то першим будемо планувати крок 1. Вважаємо, що .

Виділимо всі можливі стани, які можуть мати місце наприкінці кроку 1, тобто визначимо множину : . Для вершин знайдемо умовні оптимальні розв’язки , і відповідно. Тут – довжина найкоротшого шляху на кроці 1 (на кроках від 1-го до ( 1)-го включно), за умови, що наприкінці цього кроку система перебуває в стані (вершині) 2. Аналогічно визначаються й . Відповідно до виразу (2) отримаємо:

;

;

.

!	У цьому випадку, у кожну вершину, що аналізується, входить тільки по одній дузі. Тому мінімум не шукається. У кожному випадку умовний оптимальний розв’язок відповідає переходу з вершини 1 ( =1). Така ситуація завжди має місце, якщо в слої є тільки одна вершина (у нас – вершина 1).

Таблиця заповнюється таким чином:

Крок	Можливі стани наприкінці кроку (вершини )	Варіанти розв’язків (управлінь) (попередня вершина)	Вартість розв’язку	Умовний оптимальний розв’язок
Вхідна дуга	Попередня вершина
		a		0+2=2
	b		0+5=5
	c		0+3=3

У стовпчику вказується вершина , перехід з якої у вершину забезпечує мінімум виразу (2). У стовпчику f^* вказується значення цього мінімуму – довжина найкоротшого шляху від вершини 1 до вершини .

Дата добавления: 2014-11-29