Решение оптимизационных задач в управлении строительным производством
1. Рациональное
распределение трудовых ресурсов в строительных сетях
1.1 Задача о
назначениях
При рассмотрении задачи о
назначениях в стандартной форме предполагается, что количество рабочих равно
количеству работ.
Обозначения:
сij - показатель эффективности
назначения i-го рабочего на j-й работе, например издержки выполнения i-м рабочим j-й работы;
xij - переменная модели (хij = 1, если i-й рабочий используется на j-й работе, и xij = 0 в противном
случае).
Модель задачи о назначениях:
Здесь:
(1) - целевая функция (минимум
издержек на выполнение всех работ);
(2) - система ограничений,
отражающая следующие условия:
а) каждая работа должна быть
выполнена одним рабочим;
б) каждый рабочий может быть
привлечен к одной работе;
(3) - условия неотрицательности
переменных.
Оптимальный план задачи о
назначениях (1) - (3) можно представить в виде квадратной матрицы назначений, в
каждой строке и в каждом столбце которой находится ровно одна единица. Такую
матрицу иногда называют матрицей перестановок. Значение целевой функции (1),
соответствующее оптимальному плану, называют эффективностью назначений.
Исходные данные:
На предприятии ООО «Металлист»
имеется 5 рабочих каждый из которых может выполнять 5 различных операций по
обработке деталей. Известна затраты времени каждого рабочего при выполнении
каждой операции, заданная матрицей (табл. 1.1.1):
Таблица 1.1.1
|
|
1
|
2
|
3
|
4
|
5
|
|
1
|
9
|
2
|
5
|
9
|
6
|
|
2
|
8
|
7
|
5
|
3
|
4
|
|
3
|
4
|
3
|
8
|
8
|
4
|
|
4
|
5
|
6
|
7
|
9
|
2
|
|
5
|
5
|
2
|
8
|
3
|
4
|
Определить какую операцию и за каким
рабочим следует закрепить, чтобы суммарное время было минимальным при условии,
что за каждым рабочим закреплена только одна операция.
Шаг 1. Сначала приводим матрицу по
строкам, т.е. находим наименьшее значение в каждой строке и вычитаем эти
минимальные значения из соответствующих строк (табл. 1.1.2).
Таблица 1.1.2
|
|
1
|
2
|
3
|
4
|
5
|
|
|
1
|
9
|
2
|
5
|
9
|
6
|
2
|
|
2
|
8
|
7
|
5
|
3
|
4
|
3
|
|
3
|
4
|
3
|
8
|
8
|
4
|
3
|
|
4
|
5
|
6
|
7
|
9
|
2
|
2
|
|
5
|
5
|
2
|
8
|
3
|
4
|
2
|
Затем приводим матрицу по столбцам
(табл. 1.1.3).
Таблица 1.1.3
|
|
1
|
2
|
3
|
4
|
5
|
|
1
|
7
|
0
|
3
|
7
|
4
|
|
2
|
5
|
4
|
2
|
0
|
1
|
|
3
|
1
|
0
|
5
|
5
|
1
|
|
4
|
3
|
4
|
5
|
7
|
0
|
|
5
|
3
|
0
|
6
|
1
|
2
|
|
|
1
|
0
|
2
|
0
|
0
|
Имеем: 
Так как решение не
получается, то переходим ко второму этапу.
Проводим под прямым
углом прямые таким образом, чтобы исключить все нули. В не вычеркнутых
элементах наименьший - 
Вычитаем этот элемент
из каждого не вычеркнутого элемента прибавляем к каждому элементу, стоящему на
пересечении проведенных прямых. Переходим к таблице 1.1.4 и 1.1.5.
Таблица 1.1.4
|
|
1
|
2
|
3
|
4
|
5
|
|
1
|
7
|
0
|
3
|
7
|
4
|
|
2
|
5
|
4
|
2
|
0
|
1
|
|
3
|
1
|
0
|
5
|
5
|
1
|
|
4
|
3
|
4
|
5
|
7
|
0
|
|
5
|
3
|
0
|
6
|
1
|
2
|
Таблица 1.1.5
|
12345
|
|
|
|
|
|
|
1
|
6
|
0
|
2
|
6
|
3
|
|
2
|
5
|
5
|
2
|
0
|
1
|
|
3
|
0
|
0
|
4
|
4
|
0
|
|
4
|
3
|
5
|
5
|
7
|
0
|
|
5
|
2
|
0
|
5
|
0
|
1
|
Проводим операцию повторно и
переходим к таблице 1.1.6 и 1.1.7.
Таблица 1.1.5
|
12345
|
|
|
|
|
|
|
1
|
6
|
0
|
2
|
6
|
3
|
|
2
|
5
|
5
|
2
|
0
|
1
|
|
3
|
0
|
0
|
4
|
4
|
0
|
|
4
|
3
|
5
|
5
|
7
|
0
|
|
5
|
2
|
0
|
5
|
0
|
1
|
Таблица 1.1.6
|
12345
|
|
|
|
|
|
|
1
|
4
|
0
|
0
|
6
|
3
|
|
2
|
3
|
5
|
0
|
0
|
1
|
|
3
|
0
|
2
|
4
|
6
|
2
|
|
4
|
1
|
5
|
3
|
7
|
0
|
|
5
|
0
|
0
|
3
|
0
|
1
|
Таблица 1.1.7
|
12345
|
|
|
|
|
|
|
1
|
4
|
0
|
0
|
6
|
3
|
|
2
|
3
|
5
|
0
|
0
|
1
|
|
3
|
0
|
2
|
4
|
6
|
2
|
|
4
|
1
|
5
|
3
|
7
|
0
|
|
5
|
0
|
0
|
3
|
0
|
1
|
Данные таблицы (1.7 и 1.8) соответствует
оптимальному назначению (1,2), (2,3), (3,1), (4,5) и (5,4) или (1,3), (2,4),
(3,1), (4,5) и (5,2). Соответствующие суммарные затраты:
z’=
+
+
=12+3+1=16 ед. времени.
В таблице 1.1.7 и 1.1.8
находим суммарные затраты времени по клеткам (1,2), (2,3), (3,1), (4,5) и (5,4)
и (1,3), (2,4), (3,1), (4,5) и (5,2)
z’=2+5+4+2+3=16=5+3+4+2+2,
т.е. результаты совпали.
Ответ: минимальные
затраты времени будут составлять 16 ед. времени.
1.2 Оптимальное
распределение рабочих по захваткам
Пусть имеется n видов работ и несколько специализированных бригад рабочих.
Необходимо распределить рабочих между отдельными видами работ таким путем,
чтобы в строительный поток включить максимальное количество рабочих. Такая
задача близка к транспортной. В научной литературе она известна как задача о
максимальном потоке в матричной постановке или задача назначения (выбора).
Рассмотрим постановку задачи в общем виде. Пусть заданы количества единиц
ресурса а: 
,
,
, направляемые в пункты
назначения, в которых потребности b:
, 
, 
в этом ресурсе.
Отличительной особенностью этой задачи является закрепление каждого пункта
отправления за некоторыми пунктами назначения. Итак, имеется матрица 
, в которой
, если нельзя перевозить
ресурс из i-го пункт 
отправления
в j-пункт назначения, 0, если перевозка возможна.
Задача составляется в
составлении плана перевозок максимального количества ресурса.
Такой план определяется
числами 
(i=1, m, j=1, n);
.
Если 
=0, то 
=0, т.е. нельзя
перевозить ресурс из i-го
пункта отправления в j-ый
пункт назначения.
При этом должны
соблюдаться условия:
1 
, i=1, m, то есть из i-го пункта отправления вывозится ресурс не более чем 
.
2 
, j=1, n, то есть в j-ый пункт назначения можно ввести не больше потребности 
-го ресурса.
При этом количество перевозимого
ресурса
Ф=
max.
Исходные данные:
На строительном объекте
имеется 4 вида работ и 4 групп рабочих. Рабочие каждой группы выполняют одни и
те же работы. Необходимо, чтобы работы выполняло максимальное количество
рабочих. Условия задачи приведены в таблице 1.2.1, в столбцах которой указано
требуемое количество рабочих для выполнения соответствующей работы, а строки
отдельные виды рабочих. В клетках таблицы приведены нули, если рабочий i-ой группы может выполнять j-ю
работу, и единицы, если рабочие i-ой
группы не могут выполнять j-ю
работу.
Таблица 1.2.1
|
1
|
2
|
3
|
4
|
|
1
|
4
|
5
|
3
|
7
|
|
2
|
6
|
2
|
8
|
5
|
|
3
|
4
|
7
|
9
|
6
|
2
|
3
|
5
|
4
|
Помножаем каждый элемент матрицы на
-1 и прибавляем 10. Переходим к таблице 1.2.2.
|
1234
|
|
|
|
|
|
1
|
6
|
5
|
7
|
3
|
|
2
|
4
|
8
|
2
|
5
|
|
3
|
6
|
3
|
1
|
4
|
|
4
|
8
|
7
|
5
|
6
|
Преобразовываем матрицу по строкам.
Переходим к таблице 1.2. 3,1.2.4, 1.2.5 и 1.2.6
Таблица 1.2.3
|
1
|
2
|
3
|
4
|
|
|
1
|
6
|
5
|
7
|
3
|
3
|
|
2
|
4
|
8
|
2
|
5
|
2
|
|
3
|
6
|
3
|
1
|
4
|
1
|
|
4
|
8
|
7
|
5
|
6
|
5
|
Таблица 1.2.4
|
1
|
2
|
3
|
4
|
|
1
|
3
|
2
|
4
|
0
|
|
2
|
2
|
6
|
0
|
3
|
|
3
|
5
|
2
|
0
|
3
|
|
4
|
3
|
2
|
0
|
1
|
Таблица 1.2.5
|
1234
|
|
|
|
|
|
1
|
3
|
2
|
4
|
0
|
|
2
|
2
|
6
|
0
|
3
|
|
3
|
5
|
2
|
0
|
3
|
|
4
|
3
|
2
|
0
|
1
|
Таблица 1.2.6
|
1234
|
|
|
|
|
|
1
|
3
|
2
|
5
|
0
|
|
2
|
1
|
5
|
0
|
2
|
|
3
|
4
|
1
|
0
|
2
|
|
4
|
2
|
1
|
0
|
0
|
Проводим под прямым
углом прямые таким образом, чтобы исключить все нули. В не вычеркнутых
элементах наименьший - Вычитаем этот элемент
из каждого не вычеркнутого элемента прибавляем к каждому элементу, стоящему на
пересечении проведенных прямых. Проводим повторно операцию до конечного
результата. Переходим к таблице 1.2.7 и 1.2.8.
Таблица 1.2.7
|
1234
|
|
|
|
|
|
1
|
3
|
2
|
6
|
0
|
|
2
|
0
|
4
|
0
|
1
|
|
3
|
3
|
0
|
0
|
1
|
|
4
|
2
|
1
|
1
|
0
|
Таблица 1.2.8
|
1234
|
|
|
|
|
|
1
|
2
|
1
|
6
|
0
|
|
2
|
0
|
4
|
1
|
2
|
|
3
|
3
|
0
|
1
|
2
|
|
4
|
1
|
0
|
1
|
0
|
Таблица 1.2.9
|
1234
|
|
|
|
|
|
1
|
1
|
1
|
5
|
0
|
|
2
|
0
|
5
|
2
|
3
|
|
3
|
2
|
0
|
0
|
2
|
|
4
|
0
|
0
|
0
|
0
|
Таблица 1.2.10
|
1234
|
|
|
|
|
|
1
|
1
|
1
|
5
|
0
|
|
2
|
0
|
5
|
2
|
3
|
|
3
|
2
|
0
|
0
|
2
|
|
4
|
0
|
0
|
0
|
0
|
Ответ: На первый станок отправляем
2-го рабочего, на 2-й станок 3-его или 4-го рабочего; на 3-й станок 4-го или
3-его рабочего; на 4-й станок 1-го рабочего.
1.3 Транспортная задача
(метод Фогеля)
Рассмотрим задачу транспортировки
продукта, который в определенных количествах предлагается различными
производителями. Известны потребности нескольких потребителей в этом продукте.
Требуется определить, от каких производителей и в каких объемах должны получать
продукт потребители. Поставки должны осуществляться таким образом, чтобы
совокупные издержки на транспортировку продукта были минимальными.
Общее предложение равно общему
спросу:
Таблица 1.3.1
|
|
j
|
1
|
2
|
3
|
4
|
5
|
|
i
|
  36
|
23
|
26
|
34
|
20
|
|
|
1
|
32
|
13
|
15
|
21
|
11
|
7
|
|
2
|
17
|
22
|
21
|
35
|
38
|
13
|
|
3
|
19
|
10
|
21
|
28
|
24
|
28
|
|
4
|
31
|
25
|
19
|
22
|
29
|
17
|
|
5
|
40
|
18
|
17
|
33
|
41
|
25
|
Таблица 1.3.2
|
|
j
|
1
|
2
|
3
|
4
|
5
|
|
|
|
i
|
37
|
23
|
26
|
34
|
20
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
|
1
|
32
|
13
|
15
|
21
|
11
32
|
7
|
4
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
2
|
18
|
22
|
21
|
35
|
38
|
13
18
|
8
|
8
|
8
|
8
|
8
|
-
|
-
|
-
|
-
|
|
3
|
19
|
10 19
|
21
|
28
|
24
|
28
|
11
|
11
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
4
|
31
|
25
|
19
1
|
22
26
|
29 2
|
17 2
|
2
|
2
|
2
|
2
|
2
|
6
|
19
|
-
|
|
5
|
40
|
18
18
|
17
22
|
33
|
41
|
25
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
17
|
17
|
|
|
1
|
3
|
2
|
1
|
13
|
4
|
|
|
|
2
|
8
|
2
|
6
|
5
|
4
|
|
|
|
3
|
4
|
2
|
11
|
9
|
4
|
|
|
|
4
|
4
|
2
|
-
|
9
|
4
|
|
|
|
5
|
4
|
2
|
-
|
-
|
4
|
|
|
|
6
|
7
|
2
|
-
|
-
|
8
|
|
|
|
7
|
7
|
2
|
-
|
-
|
-
|
|
|
|
8
|
-
|
2
|
-
|
-
|
-
|
|
|
|
9
|
-
|
17
|
-
|
-
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Шаг первый: Находим в строчках
минимальные два числа и вычитаем из большего меньшее. Останавливаемся на той
строке, где разность будет больше. Аналогично проводим эту операции и со
столбцами.
Шаг второй: выбираем
столбец 4, где разность равна 13. Направляем максимальный поток в клетку 
.
Шаг третий: вычеркиваем
строку 1.
Проводим повторно
операции без учета клеток 1-ой строки до получения конечного результата.
Ответ: груз направляют
по оптимальному маршруту с грузооборотом 2157 ткм.
Вводные данные:
Таблица 1.3.3
|
|
j
|
1
|
2
|
3
|
4
|
5
|
|
i
|
28
|
42
|
43
|
27
|
20
|
|
|
1
|
41
|
13
|
15
|
21
|
11
|
7
|
|
2
|
29
|
22
|
21
|
35
|
38
|
13
|
|
3
|
33
|
10
|
21
|
28
|
24
|
28
|
|
4
|
27
|
25
|
19
|
22
|
29
|
17
|
|
5
|
30
|
18
|
17
|
33
|
41
|
25
|
Таблица 1.3.4
|
|
j
|
1
|
2
|
3
|
4
|
5
|
|
|
|
i
|
28
|
42
|
43
|
27
|
20
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
|
1
|
41
|
13
|
15
|
21 14
|
11
27
|
7
|
4
|
6
|
8
|
8
|
8
|
6
|
21
|
21
|
21
|
-
|
|
2
|
29
|
22
|
21 9
|
35
|
38
|
13
20
|
8
|
8
|
8
|
8
|
14
|
-
|
-
|
-
|
-
|
-
|
|
3
|
33
|
10 28
|
21
3
|
28
2
|
24
|
28
|
11
|
11
|
7
|
7
|
7
|
7
|
28
|
-
|
-
|
-
|
|
4
|
27
|
25
|
19
|
22
27
|
29
|
17
|
2
|
2
|
2
|
2
|
3
|
3
|
22
|
22
|
-
|
-
|
|
5
|
30
|
18
|
17
30
|
33
|
41
|
25
|
1
|
1
|
8
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
|
1
|
3
|
2
|
1
|
13
|
4
|
|
|
|
2
|
3
|
2
|
1
|
-
|
4
|
|
|
|
3
|
-
|
2
|
1
|
-
|
4
|
|
|
|
4
|
-
|
4
|
1
|
-
|
6
|
|
|
|
5
|
-
|
4
|
1
|
-
|
-
|
|
|
|
6
|
-
|
4
|
1
|
-
|
-
|
|
|
|
7
|
-
|
-
|
1
|
-
|
-
|
|
|
|
8
|
-
|
-
|
21
|
-
|
-
|
|
|
|
9
|
-
|
-
|
21
|
-
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Шаг первый: Находим в строчках
минимальные два числа и вычитаем из большего меньшее. Останавливаемся на той
строке, где разность будет больше. Аналогично проводим эту операции и со
столбцами.
Шаг второй: выбираем
столбец 4, где разность равна 13. Направляем максимальный поток в клетку 
.
Шаг третий: вычеркиваем
столбец 4.
Проводим повторно
операции без учета клеток 4-го столбца до получения конечного результата.
Ответ: груз направляют по
оптимальному маршруту с грузооборотом 2543 ткм.
Определение минимальной
продолжительности работ с использованием алгоритм Джонсона-Афанасьева и
многошаговых процессов принятия решений (метод динамического программирования).
Таблица 1.4.1
|
A
|
B
|
C
|
D
|
|
1
|
5
|
4
|
7
|
2
|
|
2
|
9
|
3
|
6
|
4
|
|
3
|
7
|
5
|
8
|
3
|
|
4
|
4
|
6
|
2
|
1
|
max A {10; 14; 13}=14B
{0; - 1; - 3}=0C {11; 15; 14}=15
T=14+0+15+10=39 у. е.
Продолжительность выполнения
комплексов потоков равна T=39 у. е.
Шаг 1:
На место первой строки
устанавливаем первую строку исходной матрицы. Незафиксированные работы
переформируются в оптимальные очередности по алгоритму Джонсона и
пересчитывается продолжительность выполнения комплекса работ.
Таблица 1.4.2
|
A
|
B
|
C
|
D
|
|
1
|
5
|
4
|
7
|
2
|
|
3
|
7
|
5
|
5
|
8
|
8
|
3
|
|
4
|
4
|
6
|
6
|
2
|
2
|
|
2
|
9
|
3
|
3
|
6
|
6
|
4
|
max A {8; 7; 10}=10
max B {2; 0; 1}=2
max C {13; 12; 17}=17
T=10+2+17+10=39 у. е.
Продолжительность выполнения
комплексов потоков равна Т=39 у.е.
На место первой строки
устанавливаем вторую строку исходной матрицы. Незафиксированные работы
переформируются в оптимальные очередности по алгоритму Джонсона и
пересчитывается продолжительность выполнения комплекса работ.
Таблица 1.4.3
|
A
|
B
|
C
|
D
|
|
2
|
9
|
3
|
6
|
4
|
|
3
|
7
|
5
|
5
|
8
|
8
|
3
|
|
4
|
4
|
6
|
6
|
2
|
2
|
1
|
|
1
|
5
|
4
|
4
|
7
|
7
|
2
|
max A {13; 12; 11}=13B
{2; 0; 2}=2
max C {10; 9; 15}=15
T=13+2+15+10=40 у. е.
Продолжительность выполнения
комплексов потоков равна Т=40 у. е.
На место первой строки
устанавливаем третью строку исходной матрицы. Незафиксированные работы
переформируются в оптимальные очередности по алгоритму Джонсона и
пересчитывается продолжительность выполнения комплекса работ.
Таблица 1.4.4
|
A
|
B
|
C
|
D
|
|
3
|
7
|
5
|
8
|
3
|
|
1
|
5
|
4
|
4
|
7
|
7
|
2
|
|
4
|
4
|
6
|
6
|
2
|
2
|
1
|
|
2
|
9
|
3
|
3
|
6
|
6
|
4
|
max A {7; 7; 10}=10B {1;
0; 1}=1
max C {11; 12; 17}=17
T=10+1+17+10=38 у. е.
Продолжительность выполнения
комплексов потоков равна Т=38 у. е.
На место первой строки
устанавливаем четвертую строку исходной матрицы. Незафиксированные работы
переформируются в оптимальные очередности по алгоритму Джонсона и
пересчитывается продолжительность выполнения комплекса работ.
Таблица 1.4.5
|
A
|
B
|
C
|
D
|
|
4
|
4
|
6
|
2
|
1
|
|
1
|
5
|
4
|
4
|
7
|
7
|
2
|
|
3
|
7
|
5
|
8
|
3
|
3
|
7
|
|
2
|
9
|
3
|
3
|
6
|
6
|
4
|
max A {3; 4; 10}=10B {8;
6; 1}=8
max C {8; 14; 17}=17
T=10+8+17+10=45 у. е.
Продолжительность выполнения
комплексов потоков равна Т=45 у.е.
После подсчета
продолжительности выполнения комплекса работ определяем матрицу с минимальной
продолжительностью. Это матрица М3 (таб. 1.4.4.) она подлежит дальнейшему
ветвлению. Итак, на месте первой строки фиксируется выявленная на первом шаге
расчета третья строка исходной матрицы, а на место второй строки поочередно
устанавливаем 1,2,4 строки и вычисляем продолжительность выполнения комплекса
работ.
Шаг 2:
1 На место второй строки
устанавливается первая строка исходной матрицы. Незафиксированные работы переформируются
в оптимальные очередности по алгоритму Джонсона и пересчитывается
продолжительность выполнения комплекса работ.
Таблица 1.4.6
|
A
|
B
|
C
|
D
|
|
3
|
7
|
5
|
8
|
3
|
|
1
|
5
|
4
|
4
|
7
|
7
|
2
|
|
4
|
4
|
6
|
6
|
2
|
2
|
1
|
|
2
|
9
|
3
|
3
|
6
|
6
|
4
|
max A {7; 7; 10}=10B {1;
0; 1}=1
max C {11; 12; 17}=17
T=10+1+17+10=38 у. е.
Продолжительность выполнения
комплексов потоков равна Т=38 у.е.
2 На место второй строки
устанавливается вторая строка исходной матрицы. Незафиксированные работы
переформируются в оптимальные очередности по алгоритму Джонсона и
пересчитывается продолжительность выполнения комплекса работ.
Таблица 1.4.7
|
A
|
B
|
C
|
D
|
|
3
|
7
|
5
|
8
|
3
|
|
2
|
9
|
3
|
3
|
6
|
6
|
4
|
|
4
|
4
|
6
|
6
|
2
|
2
|
1
|
|
1
|
5
|
4
|
4
|
7
|
7
|
2
|
max A {11; 12; 11}=12B
{0; 0; 2}=2
max C {11; 915}=15
T=12+2+15+10=39 у. е.
Продолжительность выполнения
комплексов потоков равна Т=39 у.е.
На место второй строки
устанавливается четвертая строка исходной матрицы. Незафиксированные работы
переформируются в оптимальные очередности по алгоритму Джонсона и
пересчитывается продолжительность выполнения комплекса работ.
Таблица 1.4.8
|
A
|
B
|
C
|
D
|
|
3
|
7
|
5
|
8
|
3
|
|
4
|
4
|
6
|
6
|
2
|
2
|
1
|
|
2
|
9
|
3
|
3
|
6
|
6
|
4
|
|
1
|
5
|
4
|
4
|
7
|
7
|
2
|
max A {6; 9; 11}=11B {3;
4; 2}=4
max C {7; 12; 15}=15
T=11+4+15+10=40 у. е.
Продолжительность выполнения
комплексов потоков равна Т=40 у. е.
Шаг 3:
Рассмотрим матрицу М3142
Таблица 1.4.6
|
A
|
B
|
C
|
D
|
|
3
|
7
|
5
|
8
|
3
|
|
4
|
4
|
6
|
2
|
1
|
|
2
|
9
|
3
|
6
|
4
|
|
1
|
5
|
4
|
7
|
2
|
max A {7; 7; 10}=10B {1;
0; 1}=1
max C {11; 12; 17}=17
T=10+1+17+10=38 у. е.
Продолжительность выполнения
комплексов потоков равна Т=38 у. е.
Оптимальной очередностью при минимальном
значении продолжительности строительства (Т=38 у.е.) является очередность
строительства объектов 3,4,2,1. В результате решения задачи продолжительность
выполнения комплекса работ была снижена на 1.
2. Транспортная задача
по минимуму общего времени распределения материальных ресурсов
2.1
Метод северо-западного угла
Построение оптимальных транспортных
потоков состоит из двух этапов. На первом этапе мы выбираем некоторый
необязательный оптимальный план перевозок. На втором этапе мы последовательно
шаг за шагом улучшаем этот план, для достижения минимум затрат.
Шаг 1:
Для того чтобы система заработала,
заполненные клетки плана должны образовать «лесенку с не распадающимися
ступеньками».
Таблица 2.1.1
|
|
j
|
1
|
2
|
3
|
4
|
5
|
|
|
i
|
36
|
23
|
26
|
34
|
20
|
|
|
|
1
|
32
|
13 32
|
15
|
21
|
11
|
7
|
V
|
|
2
|
17
|
22 4
|
21 13
|
35
|
38
|
13
|
V
|
|
3
|
19
|
10
|
21 10
|
28 9
|
24
|
28
|
V
|
|
4
|
31
|
25
|
19
|
22 17
|
29 14
|
17
|
V
|
|
5
|
40
|
18
|
17
|
33
|
41 20
|
25 20
|
V
|
|
|
V
|
V
|
V
|
V
|
V
|
|
Направляем в первую
клетку максимальный поток грузов (
, закрываем строку 1. В
клетку (
направляем 4 и тем
самым закрываем столбец. Аналогично проводим такие же операции с другими
стоками и столбцами и закрываем их. Таким образом, сумма затрат равна:
Ответ: при использовании
диагонального (северо-западного угла) метода, сумма затрат составила 3339 ткм.
Таблица 2.1.2
|
j12345
|
|
|
|
|
|
|
|
|
i
|
28
|
42
|
43
|
27
|
20
|
|
|
|
1
|
41
|
13 28
|
15 13
|
21
|
11
|
7
|
V
|
|
2
|
29
|
22
|
21 29
|
35 0
|
38
|
V
|
|
3
|
33
|
10
|
21
|
28 33
|
24
|
28
|
V
|
|
4
|
27
|
25
|
19
|
22 10
|
29 17
|
17
|
V
|
|
5
|
30
|
18
|
17
|
33
|
41 10
|
25 20
|
V
|
|
|
V
|
V
|
V
|
V
|
V
|
|
Аналогично проводим те же операции,
что и в первом примере. «0» - дефективная (пустая) перевозка.
Таким образом, сумма затрат равна:
Ответ: при использовании
диагонального (северо-западного угла) метода, сумма затрат составила 
ткм.
2.2
Метод минимума элемента по строке
При использовании данного метода
явление выраженности не наблюдается. Смысл данного метода заключается в
направлении максимального потока в минимальный элемент строки.
Выбираем в первой строке
минимальный элемент (
и направляем
максимальный поток 20, закрываем столбец 5. Так как строка еще не закрыта, то в
клетку с минимальным элементом 11, направляем максимальный поток (
. Закрываем первую
строчку и переходим ко второй строке. Аналогичные операции проводим с
оставшимися строчками до получения конечного результата (таблица 2.2.1).
Таблица 2.2.1
|
j12345
|
|
|
|
|
|
|
|
|
i
|
36
|
23
|
26
|
34
|
20
|
|
|
|
1
|
32
|
13
|
15
|
21
|
11
12
|
7
20
|
V
|
|
2
|
17
|
22
|
21 17
|
35
|
38
|
13
|
V
|
|
3
|
19
|
10 19
|
21
|
28
|
24
|
28
|
V
|
|
4
|
31
|
25
|
19
6
|
22 25
|
29
|
17
|
V
|
|
5
|
40
|
18
17
|
17
|
33
1
|
41 22
|
25
|
V
|
Таким образом, сумма затрат равна:
Ответ: при использовании
метода минимального элемента по строке, сумма затрат составила 
Таблица 2.2.2
|
j12345
|
|
|
|
|
|
|
|
|
i
|
28
|
42
|
43
|
27
|
20
|
|
|
|
1
|
41
|
13
|
15
|
21
|
11
21
|
7
20
|
V
|
|
2
|
29
|
22
|
21 29
|
35
|
38
|
13
|
V
|
|
3
|
33
|
10 28
|
21
5
|
28
|
24
|
28
|
V
|
|
4
|
27
|
25
|
19
8
|
22 19
|
29
|
17
|
V
|
|
5
|
30
|
18
|
17
|
33
24
|
41
6
|
25
|
V
|
Таким образом, сумма затрат равна:
Ответ: при использовании
метода минимального элемента по строке, сумма затрат составила 
Список источников
1 Афанасьев М.Ю., Суворов Б.П. Исследование операций в
экономике: модели, задачи, решения: Учеб. пособие. - М.: ИНФА-М, 2003. - 444 с.
2 Вагнер Г. Основы исследования операций. Т.1-3. - М.: Мир,
1973. - 632 с.
3 Васильев Ф.П. Иваницкий А.Ю. Линейное программирование. -
М.: Факториал Пресс. 2003. - 352 с.
Васин А.А. Морозов В.В. Теория игр и модели
математической экономики (учебное пособие). - М.: МАКС Пресс, 2005 г. - 272 с.
Вентцель Е.С. Исследование операций. Задачи, принципы,
методология. Учебное пособие для вузов. Изд-во: Дрофа, 2006 г.
Данилов Н.Н. Курс математической экономики. Новосибирск.
Изд-во СО РАН, 2002. - 444 с.
7 Интрилигатор М. Математические методы оптимизации и
экономическая теория. Изд-во: Айрис-Пресс, 2002 г. - 576 с.
8 Коробов П.Н. Математическое программирование и
моделирование экономических процессов. Изд-во: ДНК, 2003 г.-555 с.
9 Кремер Н.Ш., Путко Б.А., Тришин И.М. и др. Исследование
операций в экономике. Учебное пособие для вузов. Изд-во: Юнити, 2005 г. - 407
с.
10 Кузнецов Б.Т. Математические методы и модели исследования
операций. Изд-во: Юнити-Дана, 2005 г. - 462 с.
Летова Т.А., Пантелеев А.В. Методы оптимизации в примерах
и задачах. Учебное пособие. 2-е изд., испр. Изд-во: Высшая школа. 2005 г., 544
с.
12 Основы математики и ее приложения в экономическом образовании:
Учебник. - 4-е изд., испр. - М.: Дело, 2003. - 688 с.
13 Печерский С.Л. Яновская Е.Б. Кооперативные игры: решения и
аксиомы. СПб.: Изд-во Европейского ун-та в Санкт-Петербурге, 2004. - 459 с.
14 Протасов И.Д. Теория игр и исследование операций. Изд-во:
Гелиос АРВ, 2006 г. 368 с.
Розен В.В. Математические модели принятия решений в
экономике. Изд-ва: Университет, Высшая школа, 2002 г., 288 с.
строительный фогель
транспортный ресурс