Автор работы: Пользователь скрыл имя, 21 Января 2012 в 11:50, контрольная работа
На территории города имеется три телефонных станции А, Б и В. Незадействованные емкости станций составляют на станции А - QА, Б - QБ, В - QВ номеров (таблица 1.1). Потребности новых районов застройки города в телефонах составляют: 1 - q1, 2 - q2, 3 - q3, 4 - q4 номеров (таблица 1.2).
Необходимо составить экономико-математическую модель задачи и с помощью распределительного или модифицированного метода линейного программирования найти вариант распределения емкостей телефонных станций между районами новой застройки, который обеспечивал бы минимальные затраты как на строительство, так и на эксплуатацию линейных сооружений телефонной сети. Естественно, что таким вариантом при прочих равных условиях будет такое распределение емкости, при котором общая протяженность абонентских линий будет минимальной.
H(2*,3*) = 36 + 3 = 39
Исключение ребра (2,3) проводим путем замены элемента d23 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,3*), в результате получим редуцированную матрицу.
| i j | 1 | 2 | 3 | 5 | 6 | di |
| 1 | M | 0 | 8 | 0 | 0 | 0 |
| 2 | 5 | M | M | 1 | 12 | 1 |
| 4 | 0 | 9 | M | 5 | 0 | 0 |
| 5 | 0 | 0 | 2 | M | 4 | 0 |
| 6 | 0 | 5 | 7 | 1 | M | 0 |
| dj | 0 | 0 | 2 | 0 | 0 | 3 |
Включение ребра (2,3) проводится путем исключения всех элементов 2-ой строки и 3-го столбца, в которой элемент d32 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
После операции приведения сокращенная матрица будет иметь вид:
| i j | 1 | 2 | 5 | 6 | di |
| 1 | M | 0 | 0 | 0 | 0 |
| 4 | 0 | 9 | 5 | 0 | 0 |
| 5 | 0 | 0 | M | 4 | 0 |
| 6 | 0 | 5 | 1 | M | 0 |
| dj | 0 | 0 | 0 | 0 | 0 |
Нижняя граница подмножества (2,3) равна:
H(2,3) = 36 + 0 = 36 < 39
Чтобы исключить подциклы, запретим следующие переходы: (4,2),
Поскольку нижняя граница этого подмножества (2,3) меньше, чем подмножества (2*,3*), то ребро (2,3) включаем в маршрут.
Шаг №3.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
| i j | 1 | 2 | 5 | 6 | di |
| 1 | M | 0(0) | 0(1) | 0(0) | 0 |
| 4 | 0(0) | M | 5 | 0(0) | 0 |
| 5 | 0(0) | 0(0) | M | 4 | 0 |
| 6 | 0(1) | 5 | 1 | M | 1 |
| dj | 0 | 0 | 1 | 0 | 0 |
d(1,2) = 0 + 0 = 0; d(1,5) = 0 + 1 = 1; d(1,6) = 0 + 0 = 0; d(4,1) = 0 + 0 = 0; d(4,6) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,2) = 0 + 0 = 0; d(6,1) = 1 + 0 = 1;
Наибольшая сумма констант приведения равна (0 + 1) = 1 для ребра (1,5), следовательно, множество разбивается на два подмножества (1,5) и (1*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(1*,5*) = 36 + 1 = 37
Исключение ребра (1,5) проводим путем замены элемента d15 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,5*), в результате получим редуцированную матрицу.
| i j | 1 | 2 | 5 | 6 | di |
| 1 | M | 0 | M | 0 | 0 |
| 4 | 0 | M | 5 | 0 | 0 |
| 5 | 0 | 0 | M | 4 | 0 |
| 6 | 0 | 5 | 1 | M | 0 |
| dj | 0 | 0 | 1 | 0 | 1 |
Включение ребра (1,5) проводится путем исключения всех элементов 1-ой строки и 5-го столбца, в которой элемент d51 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
После операции приведения сокращенная матрица будет иметь вид:
| i j | 1 | 2 | 6 | di |
| 4 | 0 | M | 0 | 0 |
| 5 | M | 0 | 4 | 0 |
| 6 | 0 | 5 | M | 0 |
| dj | 0 | 0 | 0 | 0 |
Нижняя граница подмножества (1,5) равна:
H(1,5) = 36 + 0 = 36 < 37
Чтобы исключить подциклы, запретим следующие переходы: (4,2),
Поскольку нижняя граница этого подмножества (1,5) меньше, чем подмножества (1*,5*), то ребро (1,5) включаем в маршрут.
Шаг №4.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
| i j | 1 | 2 | 6 | di |
| 4 | 0(0) | M | 0(4) | 0 |
| 5 | M | 0(9) | 4 | 4 |
| 6 | 0(5) | 5 | M | 5 |
| dj | 0 | 5 | 4 | 0 |
d(4,1) = 0 + 0 = 0; d(4,6) = 0 + 4 = 4; d(5,2) = 4 + 5 = 9; d(6,1) = 5 + 0 = 5;
Наибольшая сумма констант приведения равна (4 + 5) = 9 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(5*,2*) = 36 + 9 = 45
Исключение ребра (5,2) проводим путем замены элемента d52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.
| i j | 1 | 2 | 6 | di |
| 4 | 0 | M | 0 | 0 |
| 5 | M | M | 4 | 4 |
| 6 | 0 | 5 | M | 0 |
| dj | 0 | 5 | 0 | 9 |
Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d25 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
После операции приведения сокращенная матрица будет иметь вид:
| i j | 1 | 6 | di |
| 4 | 0 | 0 | 0 |
| 6 | 0 | M | 0 |
| dj | 0 | 0 | 0 |
Информация о работе Экономико-математические методы и модели в отрасли связи