Лабораторная работа № 4

Задание. Методом динамического программирования решить следующие задачи.

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

2. Внести самостоятельно изменения в таблице 1 из примера 2 и найти максимальную прибыль предприятия за 4 года.

3. Имеется некоторый механизм, который за один раз может переместить груз либо на 1 м вверх, либо на 1 м вправо. Зависимость расходов перемещения груза от высоты и расстояния от исходного положения A приведена в таблице:

						B
	A

Например, если груз находится в точке A, то стоимость его перемещения на 1 м вверх составляет 11 (у.е.), а на 1 м вправо – 12 (у.е.).

Определить стратегию перемещения груза из пункта A в пункт B с наименьшими расходами.

4. Внести самостоятельно изменения в приведённую выше таблицу и найти стратегию перемещения груза из A в B с максимальными расходами.

Сетевое планирование

Методы сетевого планирования используются для рационального планирования сложных, комплексных работ таких как:

· строительство больших промышленных объектов (заводы, ГЭС, АЭС и т.п.);

· перевооружение армии или отдельных видов вооружённых сил;

· развёртывание системы масштабных медицинских или профилактических мероприятий.

Характерной особенностью таких сложных работ является то, что они состоят из ряда отдельных взаимозависимых работ. Эта взаимозависимость выражается в том, что некоторые работы не могут быть начаты до тех пор, пока не будут завершены определённые другие работы. Например, нельзя возводить стены здания, если не готов фундамент.

Планирование комплекса работ производится с учётом следующих элементов:

- времени, необходимого на выполнение каждой работы и всего комплекса в целом;

- стоимости выполнения каждой работы и всего комплекса работ;

- наличия людских, энергетических и сырьевых ресурсов.

Рациональное планирование комплекса работ требует, в частности ответов на следующие вопросы:

Ö как распределить имеющие материальные средства и трудовые ресурсы между работами комплекса?

Ö когда начинать и заканчивать выполнение отдельных работ?

Ö какие препятствия могут возникнуть к своевременному завершению работ и как их устранить?

Этапы сетевого планирования

1. Создание структурно-временной таблицы:

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

2. Упорядочение структурно-временной таблицы:

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

работа называется работой первого ранга, если для её начала не требуется выполнения никаких других работ;

работа называется работой ранга k, если для её начала требуется выполнение работ ранга не выше k-1.

Нумерация работ одного ранга произвольная.

3. Создание сетевого графа:

создание ориентированного графа, вершины которого помечаются завершёнными работами, а дуги – работами.

4. Создание временнόго сетевого графа:

создание сетевого графа, начала дуг которого соответствуют времени начала работ, а концы – их завершению.

5. Анализ временнόго сетевого графа:

§ определение минимального времени завершения всех работ;

§ определение критических работ, то есть работ, из времени выполнения которых складывается минимальное время выполнения комплекса всех работ;

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

6. Оптимизация плана комплексных работ:

ответ на вопрос: можно ли привлечь и в каком объёме дополнительные ресурсы для сокращения времени выполнения критических работ?

Пример сетевого планирования

Предположим, что комплекс состоит из 10 работ и что структурно-временная таблица создана:

1. Структурно-временная таблица			2. Упорядоченная структурно-временная таблица
Работа	Время выполнения	Можно начать после работы	Ранг работы	Новая нумерация	Работа	Время выполнения	Можно начать после работы
a1		—		b1	b1		—
a2		a1, a3		b5	b2		—
a3		—		b2	b3		—
a4		a1, a2, a3		b6	b4		—
a5		—		b3	b5		b1, b2
a6		—		b4	b6		b1, b2, b5
a7		a1, a4, a10		b10	b7		b1, b5
a8		a1, a2		b7	b8		b2, b3, b6
a9		a3, a4, a5		b8	b9		b8
a10		a9		b9	b10		b1, b6, b9

3. Сетевой граф.

Примечание. Сплошная стрелка означает выполнение работы, а пунктирная – ожидание завершения работ, например, стрелки из вершин B₁ и B₅ можно прочитать так: после завершения работ b₁ и b₅ можно начинать работу b₇.

4. Временнόй сетевой граф.

5. Анализ временнόго сетевого графа.

Минимальное время выполнения комплекса: 86.

Критические работы: b₂ – b₅ – b₆ – b₈ – b₉ – b₁₀.

Резервы времени с началом выполнения некритических работ:

некритическая работа	задержка с началом выполнения
b1	£ 5 = 15 – 10,
b3	£ 66 = 86 – 20,
b4	£ 68 = 86 – 18,
b7	£61 = 86 – 25.