Задачи по теории графов. Основные понятия и решения задач, страница 5

= В2-В4 – В5 + В7 + В6,    ,..(т. В)

= В3 + В5 – В7 - В8,           ,……(т. D)

= В8 – В6,                           ……………….(т. С)

5.Откроем диалоговое окно «Поиск решения» и установим соответствующие параметры.

В результате получим следующее решение.

Ответ: А→D→С→В; min Z(X) = 9.

Аналогично находим кратчайший путь между вершинами BA, AC, CA, AD, DA, BC, CB, BD, DB, CD соответственно. Целевая функция

= 18*C2 + 4*C3 + C4 + 6*C5 + 2*C6 + 8*C7 + 3*C8.

Ограничения

= C4 + С5 - C2 – C6 – С7,   , (т. В)

= C4 – C2 – C3,                   ,………….(т. А)

= C3 + C5 – C7 - C8,           ,........(т. D)

= C8 – C6,                           ……………….(т. C)

Ответ: В→А; min Z(X) = 1.

Целевая функция

= 18*D2 + 4*D3 + D4 + 6*D5 + 2*D6 + 8*D7 + 3*D8.

Ограничения

= D2 + D3 – D4,                  ,………… (т. A)

= D8 – D6,                           ,……………… (т. C)

= D2 + D6 + D7 – D4 – D5, ,. (т. В)

= D3 + D5 – D7 – D8,         ,..…..(т. D)

Ответ: А→D→С; min Z(X) = 7.

Целевая функция

= 18*E2 + 4*E3 + E4 + 6*E5 + 2*E6 + 8*E7 + 3*E8.

Ограничения

= -E8 + E6,                  ,……………..... (т. C)

= E4 – E2 – E3,                    ,………….. (т. A)

= E6 + E7 – E5 + E2 – E4,   ,..(т. В)

= E3 + E5 – E7 – E8,           ,…....(т. D)

Ответ: C→B→A; min Z(X) = 4.

Предлагаем читателям найти остальные кратчайшие пути.

A→D,                 min Z(X) = 4;

D→C→B→A;    min Z(X) = 6;

B→A→D→C;    min Z(X) = 8;

C→B,                 min Z(X) = 2;

B→A→D; min Z(X) = 5;

D→C→B; min Z(X) = 5;

C→B→A→D;    min Z(X) = 7;

D→C,                 min Z(X) = 3.

Решение задачи 4 на ЭВМ

Для решения этой задачи достаточно прибавить к предыдущему решению задачи 3 кратчайший путь между вершинами АА, ВВ, СС, DD следующим образом.

1.Вводим в ячейку N9 целевую функцию

= 18*N2 + 4*N3 + N4 + 6*N5 + 2*N6 + 8*N7 + 3*N8, которая соответствует уравнению

Z(X) = 18x₁ + 4x₂ + x₃ + 6x₄ + 2x₅ + 8x₆ + 3x₇.

2.Вводим в ячейки N10:N14 формулы

= N2 + N3 - N4,                                   ,                (т. А)

= -N2 – N3 + N4,                         ,             (т. А)

= N2 + N7 + N6– N4+N5,                    , (т. B)

= N3 +N5-N7-N8,                                ,        (т. D)

= N8-N6,                                              .                        (т. С)

Ответ: А→D→C→B→А; min Z(X) = 10.

Аналогично находим d(B,B), d(C,C), d(D,D).

В→А→D→C→B; min Z(X) = 10,

C→B→A→D→C; min Z(X) = 10,

D→C→B→A→D; min Z(X) = 10.

Результат представлен на рис. 4.

Рис. 4

Решение задачи 5 на ЭВМ

1.Каждому ребру графа сопоставляем булевую (альтернативную) переменную хi, , значение которой равно 1, если ребро входит в кратчайший путь, и равно 0 в противном случае.

2.Отводим под булевые переменные ячейки В2:В13.

3.Вводим в ячейку В14 целевую функцию

= 2*В2 + 9*В3 + 6*В4 + 4*В5 + 7*В6 + +3*В7 + 8*В8 + 7*В9 + 2*В10 + 7*В11 + +9*В12+ 7*В13, которой соответствует уравнение

.

4.Вводим в ячейки В15:В21 формулы соответствующих уравнений

= В2 + В3 + В4 +B5,

= В2 + В6 + В7 + В8,         

= В5 + В9,         

= В3 + В6 + B10 + B11,

= В7 + В12,       

= B4 + B9 + B10 + B13,

= B8 + B11 + B12 + B13.

Чтобы не было изолированных вершин, каждая сумма должна быть не менее 1, т.е.

,                                                (т. А)

,                                                 (т. В)

,                                                                (т. С)

,                                               (т. D)

,                                                               (т. E)

,                                                (т. F)

.                                             (т. G)

5.В ячейку В22 вводим формулу = СУММ (В2:В13). Эта формула означает количество ребер в минимальном дереве, меньшее количества точек, т.е. количество ребер равно 6.

6.Откроем диалоговое окно «Поиск решения» и установим соответствующие параметры.

В результате получим следующие значения.