Учебное пособие 764
.pdf
|
Находим разрешающий элементx1 |
и меняемx2 « x4 . |
||||||||||
Заполним новую таблицу. |
|
|
|
|
|
|
|
|||||
|
|
|
|
bi |
|
x1 |
|
|
x4 |
|
x3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L1 |
|
96 |
|
-12 |
-6 |
-8 |
-8 |
-6 |
|
||
|
|
|
|
120 |
|
|
|
-6 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 |
|
12 |
|
1 |
1 |
-1 |
-1 |
0 |
|
||
|
|
|
|
12 |
|
|
|
0 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x5 |
|
-8 |
|
-1 |
1 |
0 |
0 |
-1 |
|
||
|
|
|
|
-8 |
|
|
|
-1 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x6 |
|
8 |
|
1 |
0 |
-1 |
-1 |
-1 |
|
||
|
|
|
|
0 |
|
|
|
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 = 10 y1 + 8 y2 + 6 y3 +10 y4 ; |
|
|
|
||||||||
|
|
|
|
|
|
|
||||||
|
y1 + y4 |
³ 15; y1 + y3 |
³ 10; |
y2 + y3 ³ 6; y2 + y4 ³ 11. |
||||||||
|
Через базисные переменные |
|
|
|
|
|
|
L2 = 0 - (-10 y1 - 8 y2 - 6 y3 -10 y4 ),
y5 = -15 - (-y1 - y4 ); y6 = -10 - (-y1 - y3 ); y7 = -6 - (-y2 - y3 ); y8 = -11 - (-y2 - y4 ).
Составим таблицу
9
|
|
|
bi |
|
|
|
y1 |
|
y2 |
y3 |
|
y4 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L2 |
0 |
|
-10 |
-10 |
|
-8 |
-8 |
|
-6 |
|
|
-10 |
|
||
|
|
100 |
|
|
|
|
|
4 |
|
-10 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y5 |
-15 |
|
-1 |
-1 |
|
0 |
0 |
|
0 |
|
|
-1 |
|
||
|
|
-5 |
|
|
|
|
|
1 |
|
-1 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y6 |
-10 |
|
-1 |
-1 |
|
0 |
0 |
|
-1 |
|
|
0 |
|
||
|
|
10 |
|
|
|
|
|
1 |
|
0 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y7 |
-6 |
|
0 |
0 |
|
-1 |
-1 |
|
-1 |
|
|
0 |
|
||
|
|
-6 |
|
|
|
|
|
-1 |
|
0 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y8 |
-11 |
|
0 |
0 |
|
-1 |
-1 |
|
0 |
|
|
-1 |
|
||
|
|
-11 |
|
|
|
|
|
0 |
|
-1 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Делаем замену y1 |
« y6 |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
bi |
|
|
|
y6 |
|
y2 |
|
y3 |
|
|
y4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
L2 |
|
100 |
|
-10 |
0 |
-8 |
-8 |
|
4 |
|
-10 |
|
|||
|
|
|
150 |
|
|
|
|
-6 |
|
-10 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
y5 |
|
-5 |
5 |
|
-1 |
1 |
0 |
0 |
|
1 |
|
-1 |
|
||
|
|
|
|
|
|
|
|
|
-1 |
|
-1 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
y1 |
|
10 |
|
|
-1 |
-1 |
0 |
0 |
|
1 |
|
0 |
|
||
|
|
|
10 |
|
|
|
|
1 |
|
0 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
y7 |
|
-6 |
-6 |
0 |
0 |
-1 |
-1 |
|
-1 |
|
0 |
|
|||
|
|
|
|
|
|
|
|
-1 |
|
0 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
y8 |
|
-11 |
-6 |
0 |
1 |
-1 |
-1 |
|
0 |
|
-1 |
|
|||
|
|
|
|
|
|
|
|
-1 |
|
-1 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10
Еще раз заменяем y4 « y5
|
|
bi |
|
y6 |
y2 |
|
y3 |
|
|
y5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
L2 |
|
150 |
|
0 |
-8 |
-2 |
-6 |
6 |
-10 |
|
|
|
|
186 |
|
0 |
|
|
|
-10 |
|
||
y4 |
|
5 |
|
1 |
0 |
1 |
-1 |
-1 |
-1 |
-1 |
|
|
|
11 |
|
1 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
y1 |
|
10 |
|
-1 |
0 |
-1 |
1 |
1 |
0 |
0 |
|
|
|
4 |
|
-1 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
y7 |
|
-6 |
|
0 |
-1 |
1 |
-1 |
-1 |
0 |
0 |
|
|
|
6 |
|
0 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
y8 |
|
-6 |
|
1 |
-1 |
0 |
-1 |
1 |
-1 |
-1 |
|
|
|
0 |
|
1 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
Отсюда |
имеем: |
L = 186 |
при y1 = |
4; y2 |
= 0; |
|
y3 = 6; |
|
|||
y4 = 11. |
Следовательно, минимум |
пробега |
транспорта в |
||||||||
горизонтальном и |
вертикальном |
направлениях |
составляет |
L = 144 +186 = 330 км.
3. РАСЧЕТ ОПТИМАЛЬНОГО ЧИСЛА РАБОТНИКОВ НА ПРЕДПРИЯТИИ
1 °. Характерной особенностью ряда предприятий является неравномерность поступления нагрузки по часам суток, дням
недели и месяцам года. В условиях постоянного штата необходимо, с одной стороны, обеспечить выполнение всей работы, а с другой— обеспечить выполнение работы минимальным количеством работников.
Обозначим через x j — число работников, работающих
по j - му графику, |
bi - нагрузку в i - й |
рабочий день, |
||
выраженную |
в |
числе |
требуемых |
работников; a - |
|
|
|
|
ij |
11
коэффициент, равный единице, если по j - му графику предусматривается работа в i - й день, и нулю, если в тот день предусматривается выходной. Задача может быть сформулирована так: требуется найти минимум целевой функции L = x1 + x2 + ... + xn при выполнении следующих ограничений
a11 x1 + a12 x2 + ... + a1n xn ³ b1 ;
a21 x1 + a22 x2 + ... + a2n xn ³ b2 ;
……………………………….
am1 x1 + am 2 x2 + ... + amn xn ³ bm .
|
2°. Для |
простоты |
вычислений |
рассмотрим |
|
пример |
||||
четырехдневной |
рабочей |
недели |
с |
двумя |
выходным, |
|||||
исходные данные для которого приведены в таблице |
|
|
||||||||
|
Число |
|
|
|
Дни недели |
|
|
|
||
|
работников |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
2 |
|
3 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
|
В |
|
В |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 |
|
|
|
|
|
В |
В |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x3 |
|
В |
|
|
|
|
В |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x4 |
|
|
|
В |
|
В |
|
|
|
|
x5 |
|
В |
|
|
|
В |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x6 |
|
|
|
В |
|
|
В |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bi |
|
100 |
|
80 |
|
40 |
60 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Запишем задачу линейного программирования следующим образом
12
|
|
|
|
L = x1 + x2 + x3 + x4 + x5 + x6 |
|
|
|||||||
|
при следующих ограничениях |
|
|
|
|
|
|||||||
|
|
|
|
x2 + x4 + x6 ³ 100; x2 |
+ x3 + x5 |
³ 80; |
|
||||||
|
|
|
x1 + x3 + x6 |
³ 40; x1 + x4 |
+x5 ³ 60; |
x j |
³ 0. |
|
|||||
|
Введем базисные переменные и перепишем ограничения в |
||||||||||||
виде, удобном для использования симплекс-метода |
|
||||||||||||
|
y1 = -100 - (-x2 - x4 |
- x6 ); |
y2 = -80 - (-x2 |
- x3 - x5 ); |
|
||||||||
|
|
y5 = -40 - (-x1 - x3 - x6 ); y4 = -60 - (x1 - x4 - x5 ); |
|
||||||||||
|
|
|
|
L = 0 - (-x1 - x2 - x3 - x4 - x5 - x6 ). |
|
||||||||
|
Запишем решение в виде таблицы |
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bi |
|
x1 |
|
x2 |
|
x3 |
|
|
x4 |
x5 |
x6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
-1 |
|
-1 |
|
-1 |
|
-1 |
|
-1 |
-1 |
L |
|
60 |
|
0 |
|
-1 |
|
|
-1 |
|
-1 |
0 |
-1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-100 |
|
0 |
|
0 |
|
-1 |
|
-1 |
|
0 |
-1 |
y1 |
|
-40 |
|
1 |
|
0 |
|
|
-1 |
|
-1 |
0 |
-1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-80 |
|
0 |
|
-1 |
|
-1 |
|
0 |
|
-1 |
0 |
y2 |
|
-80 |
|
0 |
|
-1 |
|
|
-1 |
|
0 |
-1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-40 |
|
-1 |
|
0 |
|
-1 |
|
0 |
|
0 |
-1 |
y3 |
|
-40 |
|
-1 |
|
0 |
|
|
-1 |
|
0 |
0 |
-1 |
|
|
-60 |
|
-1 |
|
0 |
|
0 |
|
|
|
-1 |
0 |
y4 |
|
60 |
|
1 |
|
0 |
|
|
0 |
-1 |
1 |
0 |
Выбираем разрешающий элемент, находим l = -1и
переводим базисную переменную y4 в разряд свободной
x4 .Перепишем таблицу заменяя y4 « x4 .
13
|
|
|
|
bi |
|
|
x1 |
|
|
x2 |
|
x3 |
|
|
|
y4 |
|
x5 |
|
x6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L |
|
60 |
|
0 |
|
|
-1 |
-1 |
|
|
-1 |
0 |
-1 |
||||||
|
|
|
120 |
|
|
|
1 |
-1 |
-1 |
|
|
0 |
1 |
0 |
||||||
|
y1 |
|
-40 |
|
1 |
|
1 |
-1 |
-1 |
|
|
-1 |
0 |
-1 |
||||||
|
|
|
40 |
|
|
|
-1 |
-1 |
|
|
-1 |
1 |
-1 |
|||||||
|
y2 |
|
-80 |
|
0 |
|
1 |
-1 |
-1 |
|
|
0 |
-1 |
0 |
||||||
|
|
|
-40 |
|
|
|
-1 |
-1 |
|
|
0 |
-1 |
0 |
|||||||
|
y3 |
|
-40 |
|
-1 |
1 |
0 |
-1 |
|
|
0 |
0 |
-1 |
|||||||
|
|
|
40 |
|
|
|
0 |
|
|
0 |
0 |
1 |
||||||||
|
x4 |
|
60 |
|
1 |
|
1 |
0 |
1 |
|
|
-1 |
1 |
0 |
||||||
|
|
|
60 |
|
|
|
0 |
-1 |
|
|
-1 |
1 |
0 |
|||||||
|
Выберем разрешающий элемент и перепишем таблицу, |
|||||||||||||||||||
заменяя |
|
y3 « x3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bi |
|
|
|
x1 |
|
x2 |
|
y3 |
|
|
|
y4 |
|
x5 |
|
x6 |
|
L |
|
100 |
|
|
|
1 |
|
-1 |
|
-1 |
|
|
|
0 |
|
1 |
|
0 |
|
|
|
|
|
140 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
||
|
y1 |
|
-40 |
0 |
|
1 |
|
-1 |
|
0 |
|
|
|
-1 |
|
1 |
|
-1 |
||
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
||
|
y2 |
|
-40 |
40 |
1 |
-1 |
|
-1 |
|
-1 |
1 |
|
0 |
|
-1 |
|
0 |
|||
|
|
|
|
|
|
|
|
|
|
0 |
|
-1 |
|
0 |
||||||
|
x3 |
|
40 |
40 |
|
1 |
|
0 |
|
-1 |
|
|
|
0 |
|
0 |
|
1 |
||
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
||
|
x4 |
|
60 |
60 |
|
1 |
|
0 |
|
0 |
|
|
|
-1 |
|
1 |
|
0 |
||
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
||
|
Выберем разрешающий элемент и перепишем таблицу, |
|||||||||||||||||||
заменяя |
|
y2 « x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
14
|
bi |
|
x1 |
|
y2 |
y3 |
|
y4 |
|
x5 |
x6 |
|
|
|
|
|
|
|
|
|
|
|
|
L |
140 |
|
2 |
|
1 |
0 |
|
0 |
|
2 |
0 |
y1 |
0 |
|
2 |
|
1 |
1 |
|
-1 |
|
1 |
-1 |
x2 |
40 |
|
-1 |
- 1 |
- 1 |
|
0 |
|
-1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
x3 |
40 |
|
1 |
|
0 |
-1 |
|
0 |
|
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
x4 |
60 |
|
1 |
|
0 |
0 |
|
- 1 |
|
1 |
0 |
Целевая |
функция |
Lmin =140 при |
x2 = 40, |
x3 |
= 40, |
||||||
x4 = 60, x1 = x5 = x6 =0. |
|
|
|
|
|
|
|
4. ЗАДАЧА НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ
1°. Граф задается конечным множеством вершин или узлов ( a1 , a2 ,..., an ) и множеством дуг или ребер ( l1 , l2 ,...,lm ),
соединяющих некоторые или все вершины. Если ребра ориентированы, что обычно показывают стрелками, то они называются дугами, а граф с такими ребрами называется
ориентированным графом. Если ребра графа не имеют ориентации, то граф называютнеориентированным. Каждая
дуга может быть задана упорядоченной парой вершин(ai a j ) ,
где ai - называется начальной, а a j — конечной вершиной дуги.
Сетью называется граф, каждой дуге которого поставлено в соответствие некоторое неотрицательное число. Эти числа могут выражать длину, пропускную способность, стоимость перевозки и т.п. Иногда сеть ассоциируется с транспортной сетью или сетью связи.
Путем в графе называют |
последовательность дуг |
или |
||
вершин, в |
которой каждая |
конечная вершина |
является |
|
начальной вершиной следующего ребра. Простым путем |
||||
называется |
путь, в котором каждая вершина обходится не |
|||
более одного раза. Если в простом пути ориентации |
дуг |
не |
15
совпадают, то такой путь называетсяпростой цепью. Граф, в котором каждая пара вершин соединена некоторой цепью, называется связным. Задача нахождения кратчайшего пути между двумя заданными вершинами представляет одну из главных задач теории сетей.
2°. Пусть требуется найти кратчайшие пути от одной вершины ко всем остальным вершинам сети.
Алгоритм Флойда. 1) Введем матрицу Cij , в которой
записаны длины всех дуг сети
ì0, если i=j
ï
С = íдлине дуги между вершинами ai и a j
ïî¥, если дуги между ai и a j нет.
Положим k = 1 .
2)Для всех i ¹ k и j ¹ k осуществить операцию
Cij := {Cij , Cik + Ckj }.
3)Если k = m, вычисления закончены, иначе перейти к п. 4.
4) k := k +1 и перейти к шагу 2.
Алгоритм применим и для отрицательных длин ребер.
3°. Алгоритм Дейкстры. Алгоритм позволяет найти
кратчайшие |
пути |
от |
заданной |
вершины |
до |
||
остальных. Обозначим: Сij - расстояние от узла ai до a j |
; |
||||||
li¢ — временная |
пометка |
для |
вершиныai , li |
— |
|||
постоянная пометка для вершины ai ; |
m — число вершин |
||||||
в сети. |
|
|
|
|
|
|
|
Полагаем: |
|
|
|
|
|
|
|
1. ls = 0, li |
= ¥ для i = 1,..., m; |
|
i ¹ s; |
k = 1; p = s. |
|
2. Для всех соседей вершины a p с временными пометками
16
изменить пометки по формуле
li¢ = min( li¢, l p + C pi ).
3. Для всех вершин, имеющих временные пометки, найти lr = min li¢.
4. Положить p = r, k := k +1. Если k = m , вычисления закончены, иначе перейти к шагу 2.
4.1. Пусть дана сеть (рис. 31.3). Найти кратчайшие пути между всеми узлами.
Рис. 3 Решение. Составим исходную матрицу
|
1 |
2 |
3 |
|
4 |
5 |
6 |
1 |
0 |
1 |
¥ |
|
¥ |
¥ |
5 |
2 |
1 |
0 |
3 |
¥ |
6 |
2 |
|
3 |
¥ |
3 |
0 |
5 |
1 |
3 |
|
4 |
¥ |
¥ |
5 |
0 |
1 |
¥ |
|
5 |
¥ |
6 |
1 |
1 |
0 |
3 |
|
6 |
5 |
2 |
3 |
¥ |
3 |
0 |
При k =1 матрица не меняется, поэтому рассмотрим
случай, когда k = 2. |
|
|
C13 |
= min( C13 ,C12 |
+ C23 ) = min( ¥,1 + 3) = 4; |
C14 |
= min( C14 ,C12 |
+ C24 ) = min(¥,1 + ¥) = ¥; |
C15 |
= min(C15 , C12 |
+ C25 ) = min( ¥,1 + 6) = 7; |
C16 |
= min( C16 ,C12 |
+ C26 ) = min(5,1 + 2) = 3. |
Найдем элементы матрицы во второй строке матрицы |
||
C21 |
= min(C21 , C22 |
+ C21 ) = min(1,1) = 1; |
C22 |
= 0; |
|
17
C23 = min(C23 ,C22 + C23 ) = min(3,3) = 3;
C24 |
= min(C24 ,C22 |
+ C24 ) = min( ¥, ¥) = ¥; |
C25 |
= min(C25 , C22 |
+ C25 ) = min( 6,6) = 6; |
C26 |
= min(C26 ,C22 |
+ C26 ) = min( 2,2) = 2. |
Для третьей строки найдем |
||
C31 |
= min( C31 ,C32 |
+ C21 ) = min( ¥,3 +1) = 4; |
C32 |
= min(C32 ,C32 |
+ C22 ) = min(3,3) = 3; |
C33 = 0 ; |
|
|
C34 |
= min(C34 ,C32 |
+ C24 ) = min(5,3 + ¥) = 5; |
C35 |
= min(C35 ,C32 |
+ C25 ) = min(1,3 + 6) = 1; |
C36 |
= min(C36 ,C32 |
+ C26 ) = min(3,3 + 2) = 3; |
Для четвертой строки |
||
C41 |
= min(C41 , C42 |
+ C21 ) = min( ¥, ¥ +1) = ¥; |
C42 |
= min(C42 ,C42 |
+ C22 ) = ¥; |
C43 |
= min(C43 ,C42 |
+ C23 ) = min(5, ¥ + 3) = 5; |
C44 |
= 0; |
|
C45 |
= min(C45 , C42 |
+ C25 ) = min(1, ¥ + 6) = 1; |
C46 |
= min(C46 ,C42 |
+ C26 ) = min( ¥, ¥ + 2) = ¥. |
Пятая строка примет вид |
||
C51 |
= min( C51 , C52 |
+ C21 ) = min( ¥,6 +1) = 7; |
C52 |
= min(C52 ,C52 |
+ C22 ) = min( 6,6) = 6; |
C53 |
= min(C53 ,C52 |
+ C23 ) = min(1,6 + 3) = 1; |
C54 |
= min(C54 ,C52 |
+ C24 ) = min(1,6 + ¥) = 1; |
C55 |
= 0; |
|
C56 |
= min(C56 ,C52 |
+ C26 ) = min(3,6 + 2) = 3. |
Элементы шестой строки |
||
C61 |
= min(C61 , C62 |
+ C21 ) = min(5,2 +1) = 3; |
C62 |
= min(C62 , C62 |
+ C22 ) = min( 2,2) = 2; |
C63 |
= min(C63 ,C62 |
+ C23 ) = min(3,2 + 3) = 3; |
18