Материал: Методы оптимизации. методические указания для организации самостоятельной работы по курсу «Высшая математика». Пантелеев И.Н
Работа |
Опирается |
Время |
Работа |
Опираетс |
Время |
ai |
на работу |
ti |
ai |
на работу |
ti |
a1 |
- |
10 |
a6 |
a4 |
18 |
a2 |
- |
5 |
a7 |
a5 ,a6 |
8 |
a3 |
- |
15 |
a8 |
a3 ,a5 ,a6 |
25 |
a4 |
a1 ,a2 |
18 |
a9 |
a7 |
30 |
a5 |
a2 ,a3 |
19 |
a10 |
a5 ,a8 |
8 |
Построить временный график и найти критические работы. Решение. Для работы первого ранга имеем:
t1 = 0 ; t 2 = 0 ;t 3 = 0 ;T1 = t1 = 10 ;T2 = t2 = 5 ;T3 = t3 = 15 .
Работа a4 опирается на работыa1 ,a2 , т.е. она может начаться тогда, когда закончится наиболее большая работа t 4 = max{T1 ,T2 } = max{10,5}= 10 .
Моментом |
окончания |
|
работыa |
будет |
||||
T4 = t 4 +t 4 = 10 +18 = 28 . |
|
|
4 |
|
||||
|
|
|
|
|||||
Для работы a5 : |
|
|
|
|
||||
t 5 = max{T2 ,T3 }= max{5,15}= 15; T5 |
= t5 |
+ t5 = 15 +19 = 34 . |
||||||
a6 |
:t 6 |
= max{T4 }= 28 ; T6 = t 6 + t6 = 28 +18 = 46 . |
|
|||||
a7 |
:t 7 |
= max{T5 ,T6 } = max{34,46}= 46 ; |
|
|
||||
T7 = t 7 + t7 = 46 + 8 = 54 . |
|
|
|
|
||||
a8 :t 8= max{T3 ,T5 ,T6 }= max{15,34,46}= 46; |
|
|||||||
T8 = t8 + t8 = 46 + 25 = 71. |
|
|
|
|
||||
a9 : t 9 |
= max{T7 }= 54 ; T9 |
= t 9 + t9 |
= 54 + 30 = 84 . |
|
||||
a10 : t10 |
= max{T5 ,T8 }= max{34,71}= 71 ; |
|
|
|||||
T10 |
= t10 + t10 = 71 + 8 = 79 . |
|
|
|
|
|||
Время окончания работы равно максимальному времени |
||||||||
окончания |
|
T |
= 84 и a9 |
последняя |
критическая |
работа. |
||
Поскольку |
|
a9 |
опирается на |
a7 , то |
следующая критическая |
|||
4
работа a7 . Так как большая работа, на которую опирается a7
будет a6 , то a6 |
следующая критическая работа, |
a6 - опирается |
на a4 , а a4 - |
на a1 . Таким образом, a1 , a4 , |
a6 , a7 , a9 - |
критические работы. Сетевой график показан на рисунке
Рис. 1
1.2. Комплекс работ задан структурно-временной таблицей
Работа |
Опирается |
Время |
Работа |
Опирается |
Время |
ai |
на работу |
ti |
ai |
на работу |
ti |
a1 |
- |
20 |
a5 |
a1 ,a2 ,a3 |
10 |
a2 |
- |
10 |
a6 |
a1 ,a2 ,a3 |
5 |
a3 |
- |
8 |
a7 |
a6 |
5 |
a4 |
a1 ,a2 |
20 |
a8 |
a4 ,a5 ,a7 |
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.
Критические работы будут a1 , a4 , a8 . Время окончания
комплекса работ равно Т = Т1 + Т 4 + |
Т8 = 50. |
|
Уменьшим это время до Т 0 = 40 |
. Известно, что в работу ai |
|
можно вложить 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 в работу a4 . |
|
|||||||||||
2. ОПТИМИЗАЦИЯ РАЗМЕЩЕНИЯ УЗЛОВ |
|
|
|
|
||||||||
ПОЧТОВОЙ СВЯЗИ |
|
|
|
|
|
|
|
|
|
|||
1°. |
При |
проектировании |
городской |
почтовой |
свя |
|||||||
необходимо |
решить, |
где |
разместить |
|
узлы |
связи |
и |
ка |
||||
организовать их транспортные связи с опорными пунктами города (вокзалами, аэропортами, пристанями, типографиями и т.д.).
Пусть в городе имеется узел связи (У), два вокзала ( В1 , В2 ),
типография (Т) и аэропорт (А) (рис.2). |
|
|
|
В |
качестве критерия оптимизации |
выберем |
минимум |
пробега |
транспорта между узлом и |
опорным |
. пункт |
Обозначим за N1 - число рейсов за сутки между каждым из
6
вокзалов и узлом; N 2 - между аэропортом и узлом; N 3 - между узлом и типографией.
2°. |
|
Рис. 2 |
|
|
||
Пусть |
транспортные |
магистралиобразуют |
||||
прямоугольную |
сеть. Протяженность |
каждого |
маршрута |
|||
представим как сумму расстояний по оси x и по оси y. |
||||||
Обозначим через x1 расстояния |
по горизонтали между |
|||||
каждым из вокзалов и узлом; |
x2 - между аэропортом и узлом; |
|||||
x3 - между типографией |
и |
узлом. Величины l1 и |
l2 заданы. |
|||
Целевая функция, минимум которой требуется найти, будет |
||||||
иметь вид |
|
L1 = 2N1 x1 + N 2 x2 + N3 x3 . |
|
|||
|
|
|
||||
Система ограничивающих условий будет |
|
|||||
|
x1 + x2 ³ l1 + l2 ; x1 + x3 ³ l2 ; x2 + x3 ³ l1. |
|||||
Полученная модель является моделью задачи линейного |
||||||
программирования. |
|
|
|
через y1 - |
|
|
Рассмотрим по осиy. Обозначим |
расстояние |
|||||
между вокзалом 1 |
и узлом; |
y2 |
- между аэропортом и узлом; |
|||
7
y3 - между типографией и узлом; y4 - между вокзалом 2 и узлом. Целевая функция, минимум которой необходимо найти,
будет L2 = N1 ( y1 + y4 ) + N 2 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; |
N 2 |
= 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 |
96 |
|
-20 |
-12 |
-8 |
|
-8 |
|
-6 |
|
|
|
|
|
|
|
|
|
|
|
-6 |
|
|
||||
x4 |
|
-12 |
12 |
|
-1 |
|
1 |
-1 |
|
-1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|||
x5 |
|
-8 |
-8 |
|
-1 |
-1 |
0 |
|
0 |
|
-1 |
|
|
|
|
|
|
|
|
|
|
|
-1 |
|
|
||||
x6 |
|
-4 |
8 |
|
0 |
1 |
-1 |
|
-1 |
|
-1 |
|
|
|
|
|
|
|
|
|
|
|
-1 |
|
|
||||
8