- •Руководство по эксплуатации программного комплекса
- •1. Для решения ктз.
- •Варианты заданий.
- •Пример выполнения работы
- •2. Для решения задачи поиска кратчайшего пути на транспортной сети.
- •Варианты заданий.
- •Пример выполнения работы
- •3. Для решения задачи нахождения максимального потока на сети.
- •Варианты заданий.
- •Пример выполнения работы
- •4 Задача о загрузке рюкзака
- •5. Задача дискретного целочисленного программирования Описание работы с программой ldpTechs.
- •Варианты заданий.
- •Пример выполнения работы
- •6. Решение матричной игры () среди смешанных стратегий
- •Варианты заданий.
- •Пример выполнения работы
- •Лабораторная работа №7 Варианты заданий.
Пример выполнения работы
Содержательная постановка задачи. Некоторое оборудование эксплуатируется в течение 5-ти лет (от капитального ремонта до капитального ремонта). В начале каждого года эксплуатации (кроме первого) можно провести профилактический средний ремонт. Эксплуатационные расходы зависят от количества лет t , в течение которых оборудование эксплуатируется без ремонта, и от количества лет , прошедших с начала эксплуатации. Эти расходы заданы в виде таблицы.
Составить план профилактических средних ремонтов (в какие годы их проводить), чтобы получить минимальный суммарный расход по эксплуатации за все пять лет.
Расходы на эксплуатацию оборудования (у.е.)
-
t
0
1
2
3
4
1
10
12
11
12
17
2
23
21
20
19
-
3
39
34
33
-
-
4
54
51
-
-
-
5
72
-
-
-
-
Построение математической модели. Схему проведения капитальных ремонтов можно представить в виде ориентированного графа:
Здесь узлы графа обозначают начало соответствующего года эксплуатации (узел №6 означает начало 6-го года, т.е. окончание эксплуатации). Дуга из узла i в узел j означает, что оборудование ремонтируется в начале i-того года (кроме первого) и в дальнейшем эксплуатируется без ремонта до начала j-того года. Определим веса дуг графа, исходя из таблицы расходов на эксплуатацию.
(1,2)- Оборудование эксплуатируется без ремонта в течение 1-го года, и до этого не эксплуатировалось. Данной ситуации соответствует клетка таблицы t = 1, = 0. Следовательно, вес дуги l12 = 10.
(1,3)- Оборудование эксплуатируется без ремонта в течение двух лет, и до этого не эксплуатировалось. Данной ситуации соответствует клетка таблицы t=2, = 0. Следовательно, вес дуги l13= 23.
Аналогично:
l14= 39
l15= 54
l16= 72
Рассмотрим дуги, исходящие из узла №2. Например, дуга (2,3) соответствует ситуации, когда оборудование эксплуатируется 1 год без ремонта, а до этого проработало 1 год. Следовательно, обращаемся к клетке таблицы со значениями t =1, =1. Следовательно, имеем вес дуги: l23=12.
Руководствуясь подобными рассуждениями, определяем веса всех дуг. Полученные результаты заносим в новую таблицу, отражающую длины дуг, соединяющие соответствующие узлы построенного графа:
i j |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
- |
10 |
23 |
39 |
54 |
72 |
2 |
- |
- |
12 |
21 |
34 |
51 |
3 |
- |
- |
- |
11 |
20 |
33 |
4 |
- |
- |
- |
- |
12 |
19 |
5 |
- |
- |
- |
- |
- |
17 |
6 |
- |
- |
- |
- |
- |
- |
Затраты за все 5 лет эксплуатации складываются из затрат за каждый период, когда оборудование не ремонтировалось. Следовательно, задачу минимизации затрат можно рассматривать как задачу поиска кратчайшего пути на построенном графе из узла 1 в узел 6.
Обозначим: .
В терминах поставленной задачи вхождение дуги (i,j) в кратчайший путь означает, что оборудование ремонтируется в начале i-того года и эксплуатируется в дальнейшем без ремонта до начала j-того.
Тогда математическая модель задачи будет иметь вид:
(1)
(2)
(3)
(4)
(5)
В этой модели r-начальный узел пути, s- конечный узел пути, D- множество всех дуг графа, lij-вес дуги (i,j), целевая функция (1) определяет длину пути, которая должна быть минимальной. Ограничение (2) требует, чтобы в рассматриваемый путь из r в s входила только одна дуга, исходящая из r. Условие (3) говорит о том, что путь кончается в s, т.е. в рассматриваемый путь из r в s входит только одна дуга, входящая в s. Условие (4) представляет собой условие непрерывности пути, означающее, что если путь входит в какой-либо узел пути (кроме начального и конечного), то он обязательно должен из него выходить. Или, если путь не заходит в узел, то он и не должен из него выходить.
Запишем математическую модель применительно к нашей конкретной задаче:
L=10x12+23x13+39x14+54x15+72x16+12x23+21x24+34x25+51x26+11x34+20x35+33x36+
+12x45+19x46+17x56min
x12+x13+x14+x15+x16=1
x16+x26+x36+x46+x56=1
x12-(x23+x24+x25+x26)=0
(x13+x23)-(x34+x35+x36)=0
(x14+x24+x34)-(x45+x46)=0
x15+x25+x35+x45-x56=0
Решение данной задачи при помощи программы Крат_путь даёт следующие результаты:
x12=1, x24=1, x46=1, L=50. Или: узлы кратчайшего пути: 1,2,4,6. Длина пути = 50. В терминах поставленной задачи ответ выглядит следующим образом: текущие ремонты следует проводить в начале второго и четвертого годов эксплуатации. При этом общие затраты на эксплуатацию оборудования составят 50 у.е.