2020-07-12
1541
Планируется деятельность четырех промышленных предприятий (системы) на очередной год. Начальные средства: s0 = 5 усл. ед. размеры вложения в каждое предприятие кратны 1 усл. ед. средства х, выделенные k -му предприятию (k =1, 2, 3, 4), приносят в конце года прибыль 
. Функции 
заданы таблично (табл. 8). Принято считать, что:
а) прибыль 
не зависит от вложения средств в другие предприятия;
б) прибыль от каждого предприятия выражается в одних условных единицах;
в) суммарная прибыль равна сумме прибылей, полученных от каждого предприятия.
Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей.
Таблица 8
| x | f1(x) | f2(x) | f3(x) | f 4(x) |
| 1 | 8 | 6 | 3 | 4 |
| 2 | 10 | 9 | 4 | 6 |
| 3 | 11 | 11 | 7 | 8 |
| 4 | 12 | 13 | 11 | 13 |
| 5 | 18 | 15 | 18 | 16 |
Решение. Обозначим через хk количество средств, выделенных k -му предприятию (нумерацию предприятий 1, 2, 3, 4 сохраняем в процессе решения неизменной.)
Суммарная прибыль равна
Переменные х удовлетворяют ограничениям:
Требуется найти переменные х1, х2, х3, х4, удовлетворяющие системе ограничений и обращающие в максимум функцию.
|
|
|
Особенности модели. Ограничения линейные, но переменные целочисленные, а функции 
заданы таблично, поэтому нельзя применить методы целочисленного линейного программирования.
Схема решения задачи методом ДП имеет следующий вид: процесс решения распределения средств s0=5 можно рассматривать как 4-шаговый, номер шага совпадет с номером предприятия; выбор переменных 
- управление соответственно на i, ii, iii, iv шагах. 
- конечное состояние процесса распределения - равно нулю, так как все средства должны быть вложены в производство, 
=0. схема распределения показана на рис. 6.
Уравнения состояний в данной задаче имеют вид:
где sk - параметр состояния - количество средств, оставшихся после k -го шага, т.е. средства, которые остается распределить между оставшимися 4 - k предприятиями.
Рис. 6
Введем в рассмотрение функцию 
- условную оптимальную прибыль, полученную от k-го,..., 4-го предприятий, если между ними распределялись оптимальным образом средства 
. Допустимые управления на k -м шаге удовлетворяют условию: 
(либо k -му предприятию ничего не выделяем, хk =0, либо не больше того, что имеем к k -му шагу, xk≤ sk-1 .
Уравнения имеют вид:
(a)
(б)
(в)
(г)
Последовательно решаем записанные уравнения, проводя условную оптимизацию каждого шага.
iv шаг. В таблице 8 
прибыли монотонно возрастают, поэтому все средства, оставшиеся к iv шагу, следует вложить в 4-е предприятие. При этом для возможных значений s3=0, 1,..., 5 получим:
|
|
|
и 
iii шаг. Делаем все предположения относительно остатка средств s2 к iii шагу (т.е. после выбора х1 и х2). s2 может принимать значения 0, 1, 2, 3, 4, 5. В зависимости от этого выбираем 
находим 
и сравниваем для разных х3 при фиксированном s2 значения суммы 
. Для каждого s2 наибольшее из этих значений есть 
- условная оптимальная прибыль, полученная при оптимальном распределении средств s2 между 3-м и 4-м предприятиями.
ii шаг. Условная оптимизация, согласно уравнению (в), проведена в таблице 9 при k=2.
i шаг. Условная оптимизация (уравнение (г) проведена в табл. 9 при k=1 для s0=5. поясним решение подробно: если х=0, то s1=5, прибыль, полученная от четырех предприятий при условии, что s1=5 ед. средств между оставшимися тремя предприятиями будут распределены оптимально, равна 
. Если х1=1, то s2=4. Суммарная прибыль при условии, что s2=4 ед. средств между оставшимися тремя предприятиями будут распределены оптимально, равна 
. Аналогично при 
и 
;
при х1=3, s2= 2 и 
;
при х1=4, s2= 1 и 
;
при х1=5, s2= 0 и 
.
сравнивая числа, получим 
усл. ед. =zmax при 
.
Максимум суммарной прибыли равен 24 усл. ед. средств при условии, что 1-му предприятию выделено 1 усл. ед.; 2-му предприятию - 2 усл. ед.; 3-му предприятию - 1 усл. ед.; 4-му предприятию - 1 усл.ед.
Таблица 9
| s k-1 | xk | sk | k=3 | k=2 | k=1 | ||||||
| 
| 
| 
| 
| 
| 
| 
| 
| |||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0+1=1 | 0+4=4 | 0+6=6 | 8 | 1 | ||||
| 1 | 0 | 3+1=3 | 4 | 0 | 6+0=6 | 6 | 1 | 8+0=8 | |||
| 2 | 0 | 2 | 0+6=6 | 0+7=7 | 0+10=10 | ||||||
| 1 | 1 | 3+4=4 | 7 | 1 | 6+4=10 | 10 | 1 | 8+6=14 | 14 | 1 | |
| 2 | 0 | 4+0=4 | 9+0=9 | 10+0=10 | |||||||
| 0 | 3 | 0+8=8 | 0+9=9 | 0+13=13 | |||||||
| 3 | 1 | 2 | 3+6=9 | 9 | 1 | 6+7=13 | 13 | 1 | 8+10=18 | 18 | 1 |
| 2 | 1 | 4+4=8 | 9+4=13 | 2 | 10+6=16 | ||||||
СЕТЕВАЯ МОДЕЛЬ
Сетевая модель – план выполнения некоторого комплекса взаимосвязанных работ, заданного в специфической форме сети, графическое изображение которого называется сетевым графиком.
Событие – момент завершения какого-либо процесса, отражающий отдельный этап выполнения проекта.
Порядок построения сетевого графика.
1. В сетевой модели не должно быть “тупиковых” событий, т.е. событий, из которых не выходит ни одна работа, за исключением завершающего события.
2. В сетевом графике не должно быть событий (кроме исходного), которым не предшествует хотя бы одна работа.
3. В сети не должно быть замкнутых контуров и петель, т. е путей, соединяющих некоторые события с ними же самими.
4. Любые два события должны быть непосредственно связаны не более чем одной работой-стрелкой.
5. В сети рекомендуется иметь одно исходное и одно завершающее событие.
Пут ь – любая последовательность работ, в которой конечное событие каждой работы совпадает с начальным событием следующей за ней работы.
Критический путь – наиболее продолжительный полный путь в сетевом графике.
Временные параметры сетевых графиков
| элемент сети, характеризуемый параметром | наименование параметра | условное обозначение параметра |
| событие i | ранний срок свершения события поздний срок свершения события резерв времени события | tp(i) tn(i) r(i) |
| работа (i,j) | продолжительность работы ранний срок начала работы ранний срок окончания работы поздний срок начала работы поздний срок окончания работы полный резерв времени работы частный резерв времени работы первого вида частный резерв времени работы второго вида иди свободный резерв времени работы независимый резерв времени работы | t(i,j) tрн(i,j) tро(i,j) tпн(i,j) tпо(i,j) rп(i,j) r1(i,j) rс(i,j) rн(i,j) |
| путь l | продолжительность пути продолжительность критического пути резерв времени пути | t(l) tкр r(l) |
Оптимизация сетевого графика – процесс улучшения организации выполнения комплекса работ с учетом срока его выполнения.
|
|
|
Частная оптимизация – минимизация времени выполнения комплекса работ при заданной стоимости, минимизация стоимости комплекса работ при заданном времени выполнения проекта.
Комплексная оптимизация – нахождение оптимального соотношения величин стоимости и сроков выполнения проекта в зависимости от конкретных целей, ставящихся при его реализации.
