Учебное пособие 999
.pdfФГБОУ ВПО «Воронежский государственный технический университет»
Кафедра высшей математики и физико-математического моделирования
310 - 2011
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДИЧЕСКИЕ УКАЗАНИЯ для организации самостоятельной работы
по курсу "Высшая математика" для студентов специальностей 280103 "Защитавчрезвычайныхситуациях",
280101 "Безопасностьжизнедеятельностивтехносфере" и направления 280200 "Защитаокружающейсреды"
очной формы обучения
Воронеж 2011
Составители: канд. физ.-мат. наук И.Н. Пантелеев аспирант А.И. Пантелеев
УДК 51 (075)
Методы оптимизации: Методические указания для организации самостоятельной работы по курсу "Высшая математика" для студентов специальностей 280103 "Защита в чрезвычайных ситуациях", 280101 "Безопасность жизнедеятельности в техносфере " и направления 280200 "Защита окружающей среды" очной формы обучения / ФГБОУ ВПО «Воронежский государственный технический университет»; сост. И.Н. Пантелеев, А.И. Пантелеев. Воронеж, 2011. 50 с.
Настоящие методические указания предназначены в качестве руководства для организации самостоятельной работы
по курсу "Высшая математика" по разделу «Методы оптимизации» для студентов специальностей 280103 (ЧС), 280101 (БЖ) и направления 280200 (ЗС) во 2 семестре. В работе приведен теоретический материал, необходимый для выполнения заданий и решения типовых примеров.
Методические указания подготовлены на магнитном носителе в текстовом редакторе Microsoft Word 2003 и
содержатся в файле Vmfmm_Optimiz1.pdf.
Ил. 18. Библиогр.: 9 назв.
Рецензент канд. физ.-мат. наук, доц. В.В. Ломакин Ответственный за выпуск зав. кафедрой д-р физ.-мат. наук, проф. И.Л. Батаронов
Издается по решению редакционно-издательского совета Воронежского государственного технического университета
© ФГБОУ ВПО «Воронежский государственный технический университет», 2011
1. ОПТИМИЗАЦИЯ ПЛАНИРОВАНИЯ КОМПЛЕКСА РАБОТ
1°. Основным материалом для сетевого планирования является список или перечень работ, который называется структурной таблицей комплекса работ. В структурной таблице для нахождения αi должно быть указано, выполнение
каких работ она требует или на какие работы опирается.
Работа |
Опирается |
|
Обозначение |
|
αi |
на работу |
Ранг |
в новой |
|
|
|
|
нумерации |
|
α 1 |
- |
1 |
b1 |
|
α 2 |
α 1 ,α 3 |
b 3 |
||
2 |
||||
|
|
|
||
α 3 |
- |
1 |
b 2 |
|
|
|
|
||
α 4 |
α 1 ,α 2 ,α 3 |
3 |
b 4 |
|
α 5 |
α 1 ,α 2 ,α 4 |
4 |
b 6 |
|
α 6 |
α 2 ,α 3 |
3 |
b 5 |
|
|
|
|
|
Первая операция называется упорядочением. Для упорядочения все работы разделяют на ранги. Работа называется работой 1-го ранга, если для ее начала не требуется выполнение никаких других работ. Работа называется работой второго ранга, если она опирается на одну или несколько
работ первого ранга и т. д. |
|
Если задано ti −время выполнения работы |
αi , то |
минимально возможный срок окончания работы находится по формуле
T i = τi + t i , |
(1) |
где τi = max {Tj ,Tl ,Tk } - минимально возможный срок начала работы αi , которая опирается на работы α j , αl , αk и не может
начаться прежде, чем не будет завершена работа, которая заканчивается позже всех.
Работы αi , из длительностей которых составлено
минимальное время завершения комплекса работ Т, называются критическими работами. Чтобы найти критические работы, а следовательно и критический путь, надо найти работу αi , для которой время окончания T i
максимально; эта работа и будет критической. Далее следует
найти работу, |
для которой T i будет моментом начала |
αi . |
Величина τi |
представлена в виде максимума T j , T l , |
T k . |
Необходимо найти max. Это будет вторая критическая работа от конца и т. д.
2°. Пусть общее время выполнения работ T = ∑ti нас не
(kp)
устраивает и требуется его сократить до времени Т0 .
Очевидно, что надо форсировать критические работы. Вложение дополнительных средств x i в работу αi сокращает
время ее выполнения с t i |
до ti′ = fi (xi ) . |
Время выполнения |
|||
комплекса |
работ будет |
Τ′= |
∑ fi (xi ) ≤ T0 . |
Нахождение |
|
|
|
|
(kp) |
|
|
|
|
|
n |
|
|
минимума |
вложенных средств |
x = ∑xi |
= min |
разберем на |
i=1
примере 1.2.
3°. Рассмотрим задачу перераспределения уже имеющихся средств между отдельными работами. Известно, что количество средств x > 0, снятое с работы αi , увеличивает
время ее выполнения с t i до ti′ = fi (xi ) , а количество средств x , вложенных дополнительно в работу αl уменьшает время ее
2
выполнения до ti ″=ϕi (x) . Сумма средств, снимаемых с каких-
то работ, должна быть равна сумме средств, добавляемых к другим работам, так что
x 1 + x2 + …+ xn =0 |
(2) |
Для решения задачи необходимо, чтобы общий срок выполненного комплекса работ был минимален
T ′ = ∑ fi (x) + ∑ϕi (x) = min. |
(3) |
|
kp |
kp |
|
4°. Сетевое планирование при случайных временах выполнения работ. При сложении достаточно большого числа независимых случайных величин, распределенных по любым законам, закон распределения суммы близок к нормальному, поэтому МО времени равно сумме
|
mt = ∑mti |
, |
|
(4) |
|
|
|
kp |
|
|
|
где mti |
- МО времени выполнения i – й работы. |
|
|||
Среднеквадратическое отклонение, соответственно, будет |
|||||
|
σt = |
∑σti |
2 |
, |
(5) |
|
|
kp |
|
|
|
где σti |
- среднеквадратическое отклонение времени |
|
|||
выполнения i – й работы. |
|
|
|
|
|
Если величины (4), (5) известны, то вероятность |
|||||
выполнения комплекса в срок T 0 |
находится по формуле |
|
|||
|
|
|
|
|
|
|
T0 − mt |
|
|
||
|
P(T < T0 ) = Φ |
|
|
+ 0.5 , |
(6) |
|
σt |
|
|||
|
|
|
|
|
где Ф – функция Лапласа находится из таблицы.
1.1. Пусть дана упорядоченная структурная таблица
3
Работа |
Опирается |
Время |
Работа |
Опираетс |
Время |
αi |
на работу |
ti |
αi |
на работу |
ti |
α1 |
- |
10 |
α6 |
α4 |
18 |
α2 |
- |
5 |
α7 |
α5 ,α6 |
8 |
α3 |
- |
15 |
α8 |
α3 ,α5 ,α6 |
25 |
α4 |
α1 ,α2 |
18 |
α9 |
α7 |
30 |
α5 |
α2 ,α3 |
19 |
α10 |
α5 ,α8 |
8 |
Построить временный график и найти критические работы. Решение. Для работы первого ранга имеем:
τ1 = 0 ; τ2 = 0 ;τ3 = 0 ;T1 = t1 =10 ;T2 = t2 = 5 ;T3 = t3 =15 .
Работа α4 опирается на работы α1 ,α2 , т.е. она может
начаться |
тогда, когда закончится |
наиболее |
большая |
работа |
||||
τ4 |
= max{T1 ,T2 }= max{10,5}=10 . |
|
|
|
будет |
|||
|
Моментом |
окончания |
работы |
α4 |
|
|||
T4 |
=τ4 +t 4 =10 +18 = 28 . |
|
|
|
|
|||
|
Для работы α5 |
: |
|
|
|
|
||
|
τ5 |
= max{T2 ,T3 |
}= max{5,15}=15; T5 =τ5 +t5 =15 |
+19 = 34 . |
||||
|
α6 |
:τ6 |
= max{T4 }= 28 ; T6 =τ6 +t6 = 28 +18 = 46 . |
|
|
|||
|
α7 |
:τ7 |
= max{T5 ,T6 }= max{34,46}= 46 ; |
|
|
|
T7 =τ7 +t7 = 46 +8 = 54 .
α8 :τ 8= max{T3 ,T5 ,T6 }= max{15,34,46}= 46; T8 =τ8 +t8 = 46 + 25 = 71.
α9 : τ9 = max{T7 }= 54 ; T9 =τ9 +t9 = 54 +30 = 84 .
α10 :τ10 = max{T5 ,T8 }= max{34,71}= 71 ;
T10 =τ10 +t10 = 71 +8 = 79 .
Время окончания работы равно максимальному времени окончания T = 84 и α9 последняя критическая работа.
Поскольку α9 опирается на α7 , то следующая критическая
4
работа α7 . Так как большая работа, на которую опирается α7 будет α6 , то α6 следующая критическая работа, α6 - опирается
на α4 , а α4 - на α1 . Таким образом, α1 , α4 , α6 , α7 , α9 - критические работы. Сетевой график показан на рисунке
Рис. 1
1.2. Комплекс работ задан структурно-временной таблицей
Работа |
Опирается |
Время |
|
Работа |
|
Опирается |
|
Время |
αi |
на работу |
ti |
|
αi |
|
на работу |
|
ti |
α1 |
- |
20 |
|
α5 |
|
α1 ,α2 ,α3 |
|
10 |
α2 |
- |
10 |
|
α6 |
|
α1 ,α2 ,α3 |
|
5 |
α3 |
- |
8 |
|
α7 |
|
α6 |
|
5 |
α4 |
α1 ,α2 |
20 |
|
α8 |
|
α4 ,α5 ,α7 |
|
10 |
Находим |
время выполнения |
работ: |
Т1 = 20 ; Т2 |
=10 ; |
Т3 = 8 ; Т4 =Т1 +t4 = 40; T5 = T1 +t5 = 30 ; T6 = T1 +t6 = 25 ;
T7 = T6 +t7 = 30 ; T8 = T4 +t8 = 50.
Критические работы будут α1 , α4 , α8 . Время окончания комплекса работ равно Т = Т1 +Т4 +Т8 = 50.
Уменьшим это время до Т0 = 40 . Известно, что в работу αi
можно вложить xi в размере не более чем сi , т.е. |
|
xi ≤ ci , |
(1) |
5
при этом |
ti′ = ti (1 −bi xi ). |
(2) |
|
|
|||
Пусть для критических работ параметры будут |
|
||
|
b1 = 0,2; b4 = 0,3; b8 = 0,1; |
|
|
|
c1 = 2; |
c4 = 2; c8 = 5. |
|
Условия (1) примут вид: |
|
|
|
|
x1 − 2 ≤ 0; x4 − 2 ≤ 0; x5 −5 ≤ 0. |
(3) |
|
Новый срок выполнения работ находим по формуле (2) |
|
||
T ′ = t1′ +t4′ +t8′ = t1 (1 −0,2x1 ) +t4 (1 −0,3x4 ) +t8 (1−0,1x8 ) = |
|||
|
= 50 − 4x1 −6x4 − x8 . |
|
|
Поскольку |
Т0 = 40 , то 50 − 4x1 −6x4 − x8 =≤ 40, откуда |
|
|
|
4x1 +6x4 |
+ x8 ≥10. |
(4) |
Требуется |
найти минимум |
функции L =x1 +x4 + x8 |
при |
неравенствах ограничений (3), (4), т.е. налицо задача линейного программирования.
Решая задачу симплекс методом, находим, что Lmin = 5 / 3 и оптимальным решением будет вложение x4 = 5 / 3 в работу α4 .
2. ОПТИМИЗАЦИЯ РАЗМЕЩЕНИЯ УЗЛОВ ПОЧТОВОЙ СВЯЗИ
1°. При проектировании городской почтовой связи необходимо решить, где разместить узлы связи и как организовать их транспортные связи с опорными пунктами города (вокзалами, аэропортами, пристанями, типографиями и т.д.).
Пусть в городе имеется узел связи (У), два вокзала ( В1 , В2 ),
типография (Т) и аэропорт (А) (рис.2).
В качестве критерия оптимизации выберем минимум пробега транспорта между узлом и опорным пунктом. Обозначим за N1 − число рейсов за сутки между каждым из
6
вокзалов и узлом; N2 − между аэропортом и узлом; N3 − между узлом и типографией.
Рис. |
2 |
|
2°. Пусть транспортные |
магистрали |
образуют |
прямоугольную сеть. Протяженность каждого маршрута представим как сумму расстояний по оси x и по оси y.
Обозначим через x1 расстояния по горизонтали между каждым из вокзалов и узлом; x2 − между аэропортом и узлом; x3 − между типографией и узлом. Величины l1 и l2 заданы.
Целевая функция, минимум которой требуется найти, будет иметь вид
L1 = 2N1 x1 + N2 x2 + N3 x3 .
Система ограничивающих условий будет
x1 + x2 ≥ l1 +l2 ; x1 + x3 ≥ l2 ; x2 + x3 ≥ l1.
Полученная модель является моделью задачи линейного программирования.
Рассмотрим по оси y. Обозначим через y1 − расстояние между вокзалом 1 и узлом; y2 − между аэропортом и узлом;
7
y3 − между типографией и узлом; y4 − между вокзалом 2 и узлом. Целевая функция, минимум которой необходимо найти,
будет L2 = N1 ( y1 + y4 ) + N2 y2 + N3 y3 . |
||
Система ограничивающих условий, при заданных |
||
величинах h1 , h2 , h3 |
, имеет вид |
|
y1 + y2 ≥ h2 |
+ h3 ; y2 + y3 |
≥ h2 ; y1 + y4 ≥ h1 + h2 + h3 ; |
|
y2 + y4 |
≥ h1 + h2 . |
Поставленная |
задача решается симплекс-методом. В |
результате решения двух задач определяется общая
минимальная величина пробега L = L1 + L2 , |
а соответствующее |
|
значение переменных xi , yi определят координаты узла. |
||
2.1. Пример. Пусть N1 =10; |
N2 = 8; N3 |
= 6; l1 = 4 км; |
l2 = 8 км; h1 = 5 км; h2 = 6 км; h3 |
= 4 км. Найти Lmin . |
|
Решение. Математическая модель задачи относительно x |
||
примет вид |
|
|
L1 = 20x1 +8x2 + 6x3 ; |
|
|
x1 + x2 ≥12; x1 + x3 ≥ 8; x2 + x3 ≥ 4. |
|
Введем базисные переменные x4 , x5 , x6 |
и запишем решение |
|||||
в виде |
|
|
|
|
|
|
L = 0 −(−20x1 −8x2 −6x3 ); x4 = −12 −(−x1 − x2 ); |
|
|||||
x5 = −8 −(−x1 − x3 ); x6 = −4 −(−x2 − x3 ) . |
|
|||||
Базисные |
bi |
|
x1 |
|
x2 |
x3 |
переменные |
|
|
|
|
|
|
L1 |
0 |
-20 |
-12 |
-8 |
-8 |
-6 |
|
96 |
|
|
-6 |
||
x4 |
-12 |
-1 |
1 |
-1 |
-1 |
0 |
|
12 |
|
|
0 |
||
x5 |
-8 |
-1 |
-1 |
0 |
0 |
-1 |
|
-8 |
|
|
-1 |
||
x6 |
-4 |
0 |
1 |
-1 |
-1 |
-1 |
|
8 |
|
|
-1 |
8
|
Находим |
разрешающий |
элемент |
x1 |
и меняем x2 ↔ x4 . |
||||||
Заполним новую таблицу. |
|
|
|
|
|
|
|||||
|
|
|
bi |
|
|
x1 |
|
x4 |
|
x3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L1 |
|
96 |
|
|
-12 |
-8 |
|
-6 |
|
|
|
|
|
120 |
|
-6 |
|
-8 |
|
-6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 |
|
12 |
12 |
|
1 |
-1 |
|
0 |
|
|
|
|
|
|
|
1 |
|
-1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x5 |
|
-8 |
-8 |
|
-1 |
0 |
0 |
|
-1 |
|
|
|
|
|
|
1 |
|
|
-1 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
x6 |
|
8 |
0 |
|
1 |
-1 |
|
-1 |
|
|
|
|
|
|
|
0 |
|
-1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Далее заменим x3 |
↔ x5 |
|
|
|
|
|
|
|||
|
|
|
bi |
|
|
x1 |
|
x4 |
x5 |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
L1 |
144 |
|
-6 |
|
-8 |
|
-6 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 |
12 |
|
|
1 |
|
-1 |
|
0 |
|
|
|
x3 |
8 |
|
|
1 |
|
0 |
|
-1 |
|
|
|
x6 |
0 |
|
|
0 |
|
-1 |
|
1 |
|
|
|
Так как |
в первой |
строке все свободные переменные |
||||||||
отрицательны, то L1min |
=144 при x1 = 0 , |
x2 =12 , x3 |
= 8 . |
|
Математическая модель относительно оси y запишется в виде
L2 =10y1 +8y2 + 6 y3 +10 y4 ;
y1 + y4 ≥15; y1 + y3 ≥10; y2 + y3 ≥ 6; y2 + y4 ≥11.
Через базисные переменные
L2 = 0 −(−10 y1 −8y2 −6 y3 −10y4 ),
y5 = −15 −(−y1 − y4 ); y6 = −10 −(−y1 − y3 ); y7 = −6 −(−y2 − y3 ); y8 = −11 −(−y2 − y4 ).
Составим таблицу
9