Пример решения задачи

Планируется деятельность четырех промышленных предприятий (системы) на очередной год. Начальные средства: s₀ = 5 усл. ед. Размеры вложения в каждое предприятие кратны 1 усл. ед. Средства х, выделенные k-му предприятию (k=1, 2, 3, 4), приносят в конце года прибыль f_k(х). Функции f_k (х) заданы таблично (табл. 7.1.1). Принято считать, что:

а) прибыль f_k(х) не зависит от вложения средств в другие предприятия;

б) прибыль от каждого предприятия выражается в одних условных единицах;

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

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

Таблица 7.1.1

Решение. Обозначим через х_k количество средств, выделенных k-му предприятию. (Нумерацию предприятий 1, 2, 3, 4 сохраняем в процессе решения неизменной.)

Суммарная прибыль равна

, х_k≥0,k=1,2,3,4.

Переменные х удовлетворяют ограничениям:

, х_k≥0,k=1,2,3,4.

Требуется найти переменные х₁, х₂, х₃, х₄, удовлетворяющие системе ограничений и обращающие в максимум функцию.

Особенности модели. Ограничения линейные, но переменные целочисленные, а функции f_k (х_k) заданы таблично, поэтому нельзя применить методы целочисленного линейного программирования.

Схема решения задачи методом ДП имеет следующий вид: процесс решения распределения средств s₀=5 можно рассматривать как 4-шаговый, номер шага совпадет с номером предприятия; выбор переменных х₁, х₂, х₃, х4 — управление соответственно на I, II, III, IV шагах. - конечное состояние процесса распределения — равно нулю, так как все средства должны быть вложены в производство, =0. Схема распределения показана на рис. 7.1.1.

Уравнения состояний в данной задаче имеют вид:

где s_k - параметр состояния - количество средств, оставшихся после k-го шага, т.е. средства, которые остается распределить между оставшимися
4 - k предприятиями.

Рис. 7.1.1

Введем в рассмотрение функцию - условную оптимальную прибыль, полученную от k-го,..., 4-го предприятий, если между ними распределялись оптимальным образом средства s_k-1(0≤ s_k-1≤5). Допустимые управления на k-м шаге удовлетворяют условию: 0≤x_k≤ s_k-1 (либо k-му предприятию ничего не выделяем, х_k=0, либо не больше того, что имеем к к-му шагу, x_k≤ s_k-1 .

Уравнения имеют вид:

k=4, (a)

(б)

(в)

(г)

Последовательно решаем записанные уравнения, проводя условную оптимизацию каждого шага.

IV ш а г. В таблице 7.1.1 f ₄(x) прибыли монотонно возрастают, поэтому все средства, оставшиеся к IV шагу, следует вложить в 4-е предприятие. При этом для возможных значений s₃=0, 1, ..., 5 получим:

и

III ш а г. Делаем все предположения относительно остатка средств s₂ к III шагу (т.е. после выбора х₁ и х₂). s₂ может принимать значения 0, 1, 2, 3, 4, 5. В зависимости от этого выбираем 0≤ х₃≤s₂, находим s₃=s₂-x₃ и сравниваем для разных х₃ при фиксированном s₂ значения суммы . Для каждого s₂ наибольшее из этих значений есть - условная оптимальная прибыль, полученная при оптимальном распределении средств s₂ между 3-м и 4-м предприятиями.

II ш а г. Условная оптимизация, согласно уравнению (в), проведена в таблице 7.1.2. при k=2.

I ш а г. Условная оптимизация (уравнение (г) проведена в табл. 7.1.2 при k=1 для s₀=5. Поясним решение подробно: если х=0, то s₁=5, прибыль, полученная от четырех предприятий при условии, что s₁=5 ед. средств между оставшимися тремя предприятиями будут распределены оптимально, равна . Если х₁=1, то s₂=4. Суммарная прибыль при условии, что s₂=4 ед. средств между оставшимися тремя предприятиями будут распределены оптимально, равна . Аналогично при х₁=2, s₂= 3 и ;

при х₁=3, s₂= 2 и ;

при х₁=4, s₂= 1 и ;

при х₁=5, s₂= 0 и .

Сравнивая числа, получим усл. ед. =Z_max при .

Максимум суммарной прибыли равен 24 усл. ед. средств при условии, что 1-му предприятию выделено 1 усл. ед.; 2-му предприятию — 2 усл. ед.; 3-му предприятию — 1 усл. ед.; 4-му предприятию — 1 усл.ед.

Таблица 7.1.2

S k-1	xk	sk	K=3	K=2	K=1
			0+1=1			0+4=4			0+6=6
			3+1=3			6+0=6			8+0=8
			0+6=6			0+7=7			0+10=10
			3+4=4			6+4=10			8+6=14
			4+0=4			9+0=9			10+0=10
			0+8=8			0+9=9			0+13=13
			3+6=9			6+7=13			8+10=18
			4+4=8			9+4=13			10+6=16

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

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

Событие – момент завершения какого-либо процесса, отражающий отдельный этап выполнения проекта.

Порядок построения сетевого графика.

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

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

3. В сети не должно быть замкнутых контуров и петель, т. е путей, соединяющих некоторые события с ними же самими.

4. Любые два события должны быть непосредственно связаны не более чем одной работой-стрелкой.

5. В сети рекомендуется иметь одно исходное и одно завершающее событие.

Путь – любая последовательность работ, в которой конечное событие каждой работы совпадает с начальным событием следующей за ней работы.

Критический путь – наиболее продолжительный полный путь в сетевом графике.

Временные параметры сетевых графиков

Оптимизация сетевого графика – процесс улучшения организации выполнения комплекса работ с учетом срока его выполнения.

Частная оптимизация – минимизация времени выполнения комплекса работ при заданной стоимости, минимизация стоимости комплекса работ при заданном времени выполнения проекта.

Комплексная оптимизация – нахождение оптимального соотношения величин стоимости и сроков выполнения проекта в зависимости от конкретных целей, ставящихся при его реализации.