Примечание. В столбце V вместо двух рёбер из каждой вершины изображены по одной, которые соответствуют максимальным прибылям предприятия за пятый год. Например, эксплуатируя оборудование пять лет, предприятие получит прибыль 0 тыс. руб., что меньше прибыли 20 тыс. руб., если предприятие купит новое оборудование.

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

Таким образом, максимальная прибыль предприятия составит 175 тыс. руб.

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

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

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

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

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

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

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

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

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

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

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

• строительство больших промышленных объектов (заводы, ГЭС, АЭС и т.п.);
• перевооружение армии или отдельных видов вооружённых сил;
• развёртывание системы масштабных медицинских или профилактических мероприятий.

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