Тема 29. Задача об оптимальном потоке

Сети. Пропускная способность. Поток в сети. Минимальный разрез. Алгоритм Форда-Фалкерсона построения оптимального потока.

7. Даны пропускные способности c как функции дуг (i, j) двухполюсной сети (i, j - номера вершин, инцидентных дуге). Требуется найти максимальный поток и указать минимальный разрез, используя метод пометок. В верхней строке таблицы - № варианта задачи:

№	1	№	2	№	3	№	4	№	5
i, j	c	i, j	c	i, j	c	i, j	c	i, j	c
1, 2 1, 3 1, 4 1, 5 2, 3 2, 4 3, 6 4, 6 4, 7 5, 7 5, 8 6, 8 7, 8	6 5 3 2 4 6 7 5 3 4 2 3 5	1, 2 1, 3 1, 4 2, 4 2, 5 3, 5 3, 6 3, 8 4, 6 5, 7 5, 8 6, 7 7, 8	4 7 3 5 2 3 6 6 4 3 5 4 8	1, 2 1, 3 2, 3 2, 5 3, 4 3, 6 4, 5 4, 7 5, 6 5, 7 6, 7 6, 8 7, 8	6 5 3 2 3 4 6 7 5 2 3 4 6	1, 2 1, 3 1, 4 2, 3 2, 6 3, 5 4, 5 4, 6 5, 7 5, 8 6, 7 6, 8 7, 8	5 4 5 3 2 3 4 5 6 2 6 7 5	1, 2 1, 3 2, 5 2, 6 3, 4 3, 5 4, 6 4, 8 5, 7 5, 8 6, 7 6, 8 7, 8	7 6 3 3 5 3 2 3 4 8 3 4 3

Литература: [15, 19]

Тема 30. Задача сетевого планирования

Сетевой график

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

Содержание работ	Работы			Длительности: tmax , tmin (дней)
	Обозначение ai	Опорные	Коэффи-циент ki д.е./день	Варианты
				I		II
				tmax	tmin	tmax	tmin
1	2	3	4	5	6	7	8
Отбор товара	a1	–	2	6	4	10	6
Подготовка к отправке	a2	a1	3	5	2	9	5
Выписка накладных	a3	a1	1	4	2	9	4
Определение объема отгрузки	a4	a2	4	6	2	7	4
Проверка цен	a5	a3	3	3	2	5	2
Оформление счета	a6	a3	4	5	2	5	3
Заказ автомашин	a7	a4, a5	3	3	1	4	2
Отправление счета покупателю	a8	a6, a7	1	7	4	6	3
Проверка товара по счету	a9	a8	2	6	3	6	4
Оплата счета	a10		5	16	10	8	6
Погрузка товара и проверка количества	a11	a9	2	7	3	6	4
Перевозка товара	a12	a10, a11	4	7	4	11	6
Выгрузка и сверка с документами	a13	a12	4	6	4	6	4

Литература: [4, 15, 17, 19]

Учебно-методическая литература: [8]