Пример нахождения наиболее поздних сроков

Таблица 2

i=1,…,7	1	2	3	4	5	6	7
	0	5	25	31	19	10	15
	16	23	29	31	19	13	21
	3	15	29	31	19	13	15
	3	15	29	31	19	13	15
	3	10	4	0	0	3	0

Так как резервы времени , то события 4, 5, 7 являются критическими.

Н апряженные работы s={3,8,11}: s=3→(1,7): ; s=8→(7,5): ; s=11→(5,4): ;

На орграфе соответствующие дуги выделены синим цветом. Путь, содержащий эти дуги – критический. Длина критического пути равна 31.

Классическая транспортная задача (пример)

Исходная информация Таблица 1

= 100	15	30	30	30
=120	20	10	35	50
=80	40	15	30	30
	=70	=90	=85	=55

Выполнено условие: 100+120+80=70+90+85+55; р =3; q =4, размерность задачи:

(р+ q) x (р ·q)= 7 x 12

Классическая транспортная задача (пример)

При условии , k=1,2,3; l=1,2,3,4 найти план перевозок , удовлетворяющий условиям:

≥0, k=1,2,3; l=1,2,3,4

Матричная запись ограничений

Двойственная задача (пример)

Найти вектор

:

1. –

2. 3.

МПУ для классической транспортной задачи (метод потенциалов)

1 этап (Построение допустимого базисного множества К). Для построения исходного д.б.м. К применяется метод северо-западного угла .При этом полностью используются возможности поставщиков и полностью удовлетворяются потребности потребителей

Пример.

Исходные данные Метод северо-западного угла

= =100 15 30 30 30 = =120 20 10 35 50 =80 40 15 30 30 = =70 = =90 = =85 = =55

(1,1): , (1,2): , (2,2): , (2,3): , (3,3): , (3,4):

Исходное допустимое решение, д.б. м. К

1 этап. Получили исходное допустимое решение по методу северо-западного угла:

100	70 занятая клетка1	30	_ свободная клетка	_
120	_	60	60	_
80	_	_	25	55
	70	90	85	55

К={(1,1); (1.2); (2,2); (2,3); (3,3); (3,4)} – допустимое базисное множество

, остальные элементы матрицы равны 0. Количество ненулевых компонент (занятых клеток) р+q-1=6, µ(x)=-7875

Двойственный вектор

2 этап.

Находится двойственный вектор y(K):

К={(1,1); (1.2); (2,2); (2,3); (3,3); (3,4)} – допустимое базисное множество (6 уравнений, 5 неизвестных, полагаем )

Проверка двойственной допустимости б.м. К

2 этап.

Если вектор y(K) – допустимый в двойственной задаче, т.е. , то соответствующее ему д.б.м. К является д.д.б.м.

К={(1,1); (1.2); (2,2); (2,3); (3,3); (3,4)} – допустимое базисное множество y(K)=(30,50,55,45,60,85,100) Условие нарушается для (1,3) и (1,4)

Выбор элемента для ввода в д.б.м. К

2 этап.

Условие нарушается для (1,3) и (1,4) Выбираем ( ): , ( )=(1,4) Вычисляем коэффициенты разложения вектора по базисным векторам:

= Элемент (1,4) вводится в д.б.м. К Среди есть положительные, определим элемент, выводимый из базиса.

Определение элемента, выводимого из базиса

2 этап.

Т.к. среди есть положительные, вычисляем: .

Элемент ( )=(1,2)- выводим из базиса.

Подготовка к следующему шагу

2 этап.

В ка­честве нового допустимого базисного множества принимаем K' = (K\{( )}) {( )} , (kj,lj) K' \{( )}

К={(1,1); (1,2); (2,2); (2,3); (3,3); (3,4)} ( )=(1,4), ( )=(1,2) K' ={(1,1); (1,4); (2,2); (2,3); (3,3); (3,4)} Продолжая процесс, на 4 шаге получим оптимальный план перевозок: µ(x)=-5450

1 если количество занятых клеток получится меньше p+q-1, то их надо довести до этого значения при помощи фиктивных нулевых значений, соблюдая ступенчатую структуру занятых клеток

18