Методы дискретной оптимизации.

Дисциплина Дискретная математика

Вид работы	Контрольная
Дата	06.06.2021
Вариант	23

ДЗ №1. Задача в графах.
Задача 1. Код Прюфера. Вычисление количества остовных деревьев.
1. Номер варианта d10 (запись в десятичной системе счисления). Запись d10 надо перевести в 5-ую запись числа, т.е. d5. Это значит надо найти числа q{0,..,4} (разряды числа в 5-ой системе счисления). К каждому разряду полученного числа (qi=1,2,3) добавляем 1. Полученная запись это код Прюфера r некоторого дерева.

2. По коду Прюфера r восстанавливаем дерево T. Приводится последовательность шагов, с помощью которых дерево T получено. Рисуется полученное дерево T=(V,E)

3. По дереву T строится граф G=T (т.е. вершины графа G е же, что и у T,  а ребра таковы, что при добавлении множества G ке дереву T в результате получается полный граф).

4. По полученному графу G строится матрица смежности A=A(G), матрица инцидентности I=I(G) и матрица Кирхгофа B=B(G)

5. По матрице Кирхгофа K определяется число остовных деревьев (остовов) графа G

ДЗ №2. Задача линейного программирования.
r=154, r1 = 1, r2 = 5, r3 = 4
Задача 1. ЗЛП решить графическим способом.
3x1 + 5x2 → max
-x1 + 5x2 ≤ 6
5x1 + 4x2 ≤ 9
4x1 - x2 ≤ 5
x1, x2 ≥ 0
x1 + 5x2+ 6x3 → max
4x1 + x2 + 5x3 ≤ 10
2x1 + 3x2 + x3 = 5
-4x1 + 3x2 + x3 = -1