Черненко В.Д. Высшая математика в примерах и задачах (том 3)
Подождите немного. Документ загружается.
420
Гпава
31
1.1. Пусть дана упорядоченная структурная таблица
Работа
а,
а,
^2
^
^4
1
^5
Опирается
на
работу
-
-
-
a^Mj
а^,а,
Время
10
5
15
18
19
Работа
а.
0-6
а,
^
^9
«,0
Опирается
на
работу
а.
а^,а^
а^,а^,а.
«7
a^,ag
Время
18
8
25
30
8
Построить временной график и найти критические работы.
Решение. Для работы первого ранга имеем:
т^=:0;Т2=0;Гз=0;7;=/, =10;Г2=/2=5;Гз=^з=15.
Работа а^ опирается на работы
Oj, Оз,
т. е. она может на-
чаться тогда, когда закончится наиболее большая работа
Т4
=max{7J,72} =
max{10,5}
= 10.
Момент окончания работы а^ будет
7^
=T^+t^
=10+18
= 28.
Для работы «3:
Т5=тах{72,7з} = тах{5,15} =
15;
T^=r^+t^=l5
+
l9
=
34,
а^: Тб=тах{74} =
28;
T^=T^+t^=2S'hlS
=
46.
а,:т^
=ГШК{Т^,%}=ГШК{34,46}=46; Tj=i:,+t^=46-hS
=
54,
Оз*. Tg
=
max{73,75,7g}
= max{15,34,46} = 46;
7з=Т8 + ^з=46 +
25
=
71.
o^: T9=max{77} =
54;
79 =Т9 +
/9
=54+30 = 84.
O^Q',
TJO
=
max{75,7g}
= max{34,71} =
71;
Tio-^10 + ^0=71 +
8
= 79.
Время окончания работы равно максимальному времени
окончания Т= 84и
Од
последняя критическая работа. Посколь-
ку
Од
опирается на О;, то следующая критическая работа cij.
Так как большая работа, на которую опирается
Оу,
будет а^, то
ЭЛЕМЕНТЫ ТЕОРИИ ОПТИМИЗАПИИ
421
а, следующая критическая работа,
а^
— опирается
из,
а^,з.а^
—
на
Oj.
Таким образом, а^, а^, а^, а^, а^ — критические работы.
Сетевой график показан на рис. 31.1.
Рис. 31.1
1.2. Комплекс работ задан структурно-временной таблицей
Работа
а-
а,
^
^
а.
Опирается
на работу
-
-
-
а^,а^
Время
20
10
8
20
Работа
а,
а.
^б
а.
«8
Опирается
на работу
Oj , ^2 , Оз
а^.а^.Оъ
^6
^4,0^5'^
Время
10
5
5
10
Находим время выполнения работ: 7] = 20;
Tj
=
10;
7^
= 8;
T,=T,+t,
=40;
T,=T,+t,
^30;T,=T,+t,=25:
T,=T,+t,
=30;
7,
=7; +
^,
=50.
Критические работы будут: а^, а^, а^. Время окончания
комплекса работ равно 7 =
7]
+
7^
+
Tg
= 50.
Уменьшим это время до
Т^
=
40.
Известно, что в работу а-
можно вложить средствах, в размере не более чем с^, т.е.
х,<с,,
(1)
при этом
422 Г
пава
31
t:=t,(\-b,xj.
(2)
Пусть для критических работ параметры будут
&,
=0,2; Ь,=0,3;
&8=0,1;
L/J Z, С^ Z, Cg J.
Условия (1) примут вид
JCi-2<0; Х4-2<0; Х5-5<0. (3)
Новый срок выполнения работ находим по формуле (2)
r=^;+^;+/;=^/i-o,2xj+^/i-o,3xj+^gn-o,ixj =
= 50-4Xi -6X4-Xg.
Поскольку
7Q
=
40,
ТО
50
-
4х^
-
6х^"~ ^8
^ 40, откуда
4x,+6x4
+
Xg>10.
(4)
Требуется найти минимум функции L = х, + ^4 +
Xg
при не-
равенствах ограничений (3), (4), т. е. налицо задача линейного
программирования.
Решая задачу симплекс методом, находим, что
L^.^
= 5/3 и
оптимальным решением будет вложение
Х4
= 5/3 в работу а^.
31.2.
Оптимизация размещения узлов
почтовой связи
1"^.
При проектировании городской почтовой связи необхо-
димо решить, где разместить узлы связи и как организовать их
транспортные связи с опорными пунктами города (вокзалами,
аэропортами, пристанями, типографиями и
т.
д.).
Пусть в городе имеется узел связи (У), два вокзала (Bj, В2),
типография (7) и аэропорт
{А)
(рис. 31.2).
В
качестве критерия оптимизации выберем минимум пробега
транспорта между узлом
и
опорными
пунктами.
Обозначим за
Л^^
—
число рейсов за сутки между каждым из вокзалов и узлом; Nj —
между аэропортом и узлом; Л^з—между узлом и типографией.
ЭПЕМЕНТЫ ТЕОРИИ ОПТИМИЗАиИИ
423
©7
у
Рис. 31.2
'В,
'в.
^
1 ''
X,
х,
Xj 1
^/ Т
^2 1
1
1
У4
I
• 1
Т
1
У2
1
Уз
1 1
i
т
' 1
[ 4 1
^3
,
h.
1
л,
2°.
Пусть транспортные магистрали образуют прямоуголь-
ную сеть. Протяженность каждого маршрута представим как
сумму расстояний по оси х и по оси у.
Обозначим через х^ расстояние по горизонтали между каж-
дым из вокзалов и узлом;
х^
— между аэропортом и узлом; Хз —
между типографией и узлом. Величины /j и
1^
заданы. Целевая
функция, минимум которой требуется найти, будет иметь вид
Lj =
IN^x^
+ N^x^ +
Л^з^з
•
Система ограничивающих условий будет
XI+A:2 >/i+/2; Xj+X3>/2; л:2+Хз>/,.
Полученная модель является моделью задачи линейного
программирования.
Рассмотрим по оси у. Обозначим через у^ — расстояние
между вокзалом
1 и
узлом;
у^
— между аэропортом
и
узлом;
у^—
между типографией и узлом; у^ — между вокзалом 2 и узлом.
Целевая функция, минимум которой необходимо найти, будет
L^=N,(y,+yJ
+
N^y^+N,y,,
424
Гпава 31
Система ограничивающих условий, при заданных величи-
нах /ij, /г^,
/^3,
примет вид
y^+y^>h,+h^.
Поставленная задача решается симплекс-методом.
В
резуль-
тате решения двух задач определяется общая минимальная ве-
личина пробега L = Lj+L2, а соответствующие значения
переменных х.,
у-
определят координаты узла.
2.1.
Пример. Пусть Л^, = 10;
Л^2
= 8;
Л^з
= 6;
/j
= 4 км;
и =
8/сж;/Zj
=
5км;^2
= бкж;
1ц
=4км. Найти L^.„.
Решение. Математическая модель задачи относительно оси
X примет вид
Lj =20X1+8X2+6X3;
Xi+X2>12; Xi+X3>8; Х2+Хз>4.
Введем базисные переменные Х4,Х5,х^ и запишем решение
в виде
L =0~(-20х,-8х2-6х)з;
Х4=-12-(-х,-х)^;
Хз
=-8-(-х,-Хз); х^ =-4-(-Х2-Хз).
Запишем таблицу
Базисные
переменные
А
X,
X,
[_
^6
6,
0
96
-12
12
-8
-8
-4
8
X,
-20
-12
-1
1
-1
-1
0
1
Х2
-' [^
е^
"
г^
Kd
Х3
' -6
0
0
' -1
' -1
ЭПЕМЕНТЫ ТЕОРИИ ОПТИМИЗАиИИ
425
Находим разрешающий элемент -1 и меняем Xj
<->
JC^.
За-
полним новую таблицу
А
х^
X,
Хб
&,
96
120
12
12
-'(Г
8
0
X,
-12
-6
1
1
"'гГ
1
0
X,
-8
-8
-1
-1
'гГ
-1
-1
X,
"'(^
°
И
©rd
._:'г^
Далее заменим х^
<г^
х^
^
Хг
Хг
Хб
6,
144
12
8
0
^1
-6
1
1
0
X,
-8
-1
0
-1
X,
-6
0
-1
1
Так как в первой строке все свободные переменные отри-
цательны, то Ц
^i„
=
144
при
Xj
=
0; ^2
=
12;
Х3
= 8.
Математическая модель относительно оси у запишется в
виде
L^=l0y,+Sy^+6y^+\0y^;
у,+у^>15;
у,+у,>10; у^+у,>6; y,+y^>U.
Через базисные переменные
L2=0-(-10i/,-8i/2-6i/3-10i/,),
426
Гпава 31
Г/5 =-15-(-//,-Г/4 ); ^б=-10-(-^1-^з)/
Составим таблицу
^
Уь
Уь
У1
Уг
ь.
0
100
-15
-5
-10 ^^..^
fio
-6
-6
-и
-11
Ух
-10 ^.^
Г^о
-1 ^
@^
v
0 ^..-^
Го
У2
-8
-8
0
0
0 ^
[о
-1
-1
-1
-1
Уз
-6
4
0
1
-1 -
1 1
-1
-1
0
0
УА
-10 1
-10
-1
-1
[ 0
0
0
-1
-1
Делаем замену г/, <-> i/^
^
^5
^1
^7
^8
6,
100
150
-5 ^
[5
10
10
-6
-6
-11
-6
Уб
-10
0
V
-1
-1
0
0
0
1
У2
-8
-8
0 ^^.^
[О
0
0
-1
-1
-1
-1
Уз
4
-6
'г^
1
1
-1
-1
0
-1
У4
®н
O^J
Го
0
J
-'d
Еще раз заменяем у^
<-^
у^
ЭЛЕМЕНТЫ ТЕОРИИ ОПТИМИЗАиИИ
427
^
Ул
У^
Уп
Уг
ь.
150
186
5
11
10
4
•V
-6
0
Уь
0
0
1
1
-1
-1
1
1
Уг
-8 -
2
0
1
0
-1
V
-1
0
Уз
-'(<
-'г^
V
%
-.г^
i/5
-10
-10
-1
0
0
1
"Н
Последняя замена
у^,
<->
y-j
L,
Ул
У^
Уг
Уг
6,
186
11
4
6
0
г/б
0
1
-1
0
1
Уг
-2
1
-1
1
0
Уп
-6
-1
1
-1
-1
ys
-10
-1
0
0
-1
Отсюда имеем: L = 186 при у^ = 4; у^
=
0;
у^=(>;
у^=\\.
Следовательно, минимум пробега транспорта
в
горизонтальном
и вертикальном направлениях составляет L =
144
+186 = 330 км .
31.3.
Расчет оптимального числа
работников на предприятии
1 °. Характерной особенностью ряда предприятий является
неравномерность поступления нагрузки по часам суток, дням
428
Гпава
31
недели и месяцам
года.
В условиях постоянного штата
необхо-
димо,
с одной
стороны,
обеспечить выполнение всей
работы,
а с
другой — обеспечить выполнение работы минимальным
коли-
чеством
работников.
Обозначим через
х-^
— число
работников,
работающих
по
/ -му
графику,
I),
— нагрузку в
/-й
рабочий
день,
выраженную
в числе требуемых
работников;
щ.—коэффициент,
равный
еди-
нице,
если по
/ -му
графику предусматривается работа в
/-й
день,
и
нулю,
если в этот день предусматривается
выходной.
Задача может быть сформулирована
так:
требуется найти
минимум целевой функции L
=
Xj + Х2
+...
+ х^
при
выполнении
следующих
ограничений:
а^,х.
+а^.х^
+...-ьа„х„
>й .
ml 1 ml L тп п т
2°.Для простоты вычислений рассмотрим пример
четырех-
дневной рабочей недели с двумя
выходными,
исходные данные
для которого приведены в таблице
Число
работников
X,
Ч
X,
^4
^Ь
Хб
6,
День недели
1
В
В
В
100
2
В
в
в
80
3
в
в
в
40
4
в
В
в
60
ЭЛЕМЕНТЫ ТЕОРИИ ОПТИМИЗАЦИИ
429
Запишем задачу линейного программирования следующим
образом
При
следующих ограничениях
^2 +
Х4
+
х^
> 100; ^2 +
^3
+
Хз
> 80;
Xj
+
Хз
+
Xg
> 40;
X,
+
Х4
+
Х5
> 60;
х^-
> 0.
Введем базисные переменные и перепишем ограничения в
виде, удобном для использования симплекс-метода
г/, =-100-(~Х2-Х4-х,); г/2 =-80-(-Х2-Хз~Х5);
у^
=
-40 - (-Х, -
Хз
-
Хб);
У4
= -60 - (-Xj -
Х4
- Х5);
L =
у) —
v^"~Xj
—
Х2 ~ Х3
—
Х^
—
Х3
—
Xg j.
Запишем решение в виде таблицы
L
У1
У 2
\Уз
\УА
6.
0
60
-100
-40
-80
-80
-40
-40
-60^.^
|б0
X,
- 1
0
0
1
« 0
-1
-1
I'n:
Х2
-1
-1
0
0
-1
-1
0
0
:г^
Хз
-I
-1
-1
-1
-1
-1
-1
-1
1.к
X,
-f^
-1 г-"^
|-1
"Г
V
(^)
Хз
0
0
0
0
0
-1 ^^
ч
-1
-1 1
-1
-1
0
0
-1
-1
!
"l^
Выбираем разрешающий элемент, находим
Я
= -l и пере-
водим базисную переменную ^/4 в разряд свободной Х4. Пере-
пишем таблицу, заменяя
у^<г^
х^.