23. Что такое задача о размещении?

Задача о размещении (транспортная задача)– это распределительная задача, в которой работы и ресурсы измеряются в одних и тех же единицах. В таких задачах ресурсы могут быть разделены между работами, и отдельные работы могут быть выполнены с помощью различных комбинаций ресурсов. Примером типичной транспортной задачи является распределение (транспортировка) продукции, находящейся на складах, по предприятиям-потребителям.

Стандартная ТЗ определяется как задача разработки наиболее экономичного плана перевозки продукции одного вида из нескольких пунктов отправления в пункты назначения. При этом величина транспортных расходов прямо пропорциональна объему перевозимой продукции и задается с помощью тарифов на перевозку единицы продукции.

24. Какова постановка задачи о назначениях?

Имеется n должностей и n претендентов на эти должности. Если i-го человека определить на j-ю должность, то полезность его деятельности оценивается числом cij .

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

25. В чем отличие модели задачи о назначениях от модели ТЗ?

Задача о назначениях представляет собой частный случай транспортной задачи с числом строк (поставщиков), равным числу столбцов (потребителей). Каждый "поставщик" (это может быть рабочий) предлагает самого себя одному из "потребителей" (это может быть операция, станок или напарник). Поэтому все "запасы" и "заказы" в задаче о назначениях равны 1.

26. Запишите математическую модель задачи о назначениях.

27. Что такое "сетевое планирование"?

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

28. Как обозначается на сетевых моделях понятие "событие"?

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

На графиках обозначается кружочками или квадратиками.

29. Объясните физический смысл понятия "время позднего окончания работы".

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

30. Приведите основные формулы для расчёта сетевых моделей.

Решение приведенных задач требует применения различных сетевых оптимизационных алгоритмов:

1. Алгоритм нахождения минимального остовного дерева.

2. Алгоритм поиска кратчайшего пути.

3. Алгоритм определения максимального потока.

4. Алгоритм минимизации стоимости потока в сети с ограниченной пропускной способностью.

5. Алгоритм определения критического пути.

Задачи, вытекающие из приведенных примеров, можно решать как задачи линейного программирования. Однако специфическая структура задач позволяет использовать алгоритмы более эффективные, чем симплекс-метод.