Курс лекций по линейному программированию

Построение критического пути – это второй этап оптимизации  проекта.

Следующий этап состоит в перераспределении  ресурсов v;le операциями проектов с целью уменьшения длины критического пути. При этом допускается возникновение нового критического пути, который отличается от уже построенного. 

Лекция № 7: «Динамическое  программирование».

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

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

Пример задачи распределения:

Для расширения трех предприятий фирма выделила 5000000$. Каждое предприятие предоставляет проект в котором С – суммарные издержки, R – доходы. Цель фирмы – получить максимальную прибыли от инвестиций.

1. Сетевая модель

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

х₁ – объем инвестиций, распределяемых на первом этапе

х₂ – объем инвестиций, распределяемых на первом и втором этапах

х₃ – объем инвестиций, распределяемых на первом, втором и третьем этапах.

Эначение х₁ и х₂ – заранее неизвестны, но они могут принимать значения из 1, 2, 3, 4, 5. х₃ = 5

Каждому из возможных  значений х₁, х₂, х₃ поставляется в соответствие узел, ассоциируемый с одним из этапов (j=1, j=2 j=3).

 Длины дуг,  соединяющие узлы на некотором  этапе с узлами на последующем  этапе численно равны доходам от реализации лучшего проекта. Величина (х₂ – х₁) = объему инвестиций, распределенных только на втором этапе, следовательно дуга х₁, х₂ является допустимой лишь для проектов, затраты на реализацию которых не превышают (х₂ – х₁) и длина этой дуги = max (R) для всех таких проектов.

Рассмотрим дугу   L          U

Из первого  этапа во второй, следовательно между 1 и 2 предприятиями распределяет 4000000$, из них 2000000$ во второе и 2000000$ в первое.

На последнем  этапе распределяется 5000000$. Из них 3000000 – в 1 и 2 предприятия; 2000000$ - в 3 предприятие.

По аналогии с сетевыми графиками максимальный доход соответствующий самому длинному пути с этапа G0 до этапа G3.

Регулентные соотношения.

Расчеты на некотором  этапе осуществляются на базе сводной информации о максимальном суммарном доходе (суммарном длинном пути, полученном в результате вычисления кроме всех предшествующих этапов). Все последующие решения строятся оптимальным образом, независимо от решений, полученных на предшествующих этапах.

Это отражает сущность принципа оптимальности Баумана  составляет основу вычисление схемы  ДП.