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

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

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

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

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

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

Таблица 8

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

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

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

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

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

Схема решения задачи методом ДП имеет следующий вид: процесс решения распределения средств s₀=5 можно рассматривать как 4-шаговый, номер шага совпадет с номером предприятия; выбор переменных - управление соответственно на i, ii, iii, iv шагах. - конечное состояние процесса распределения - равно нулю, так как все средства должны быть вложены в производство, =0. схема распределения показана на рис. 6.

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

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

Рис. 6

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

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

(a)

(б)

(в)

(г)

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

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

и

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

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

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

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

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

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

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

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

Таблица 9

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. В сети рекомендуется иметь одно исходное и одно завершающее событие.

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

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

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

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

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

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