Автор работы: Пользователь скрыл имя, 16 Августа 2011 в 14:12, контрольная работа
Задание: Необходимо составить экономико-математическую модель задачи и с помощью распределительного или модифицированного метода линейного программирования найти вариант распределения емкостей телефонных станций между районами новой застройки, который обеспечивал бы минимальные затраты как на строительство, так и на эксплуатацию линейных сооружений телефонной сети. Естественно, что таким вариантом при прочих равных условиях будет такое распределение емкости, при котором общая протяженность абонентских линий будет минимальной.
Наконец вычитаем наименьший элемент в столбце из элементов своего столбца - получается приведенная матрица:
| А | Б | В | Г | Д | Е | |
| А | - | 4 | 0 | 0 | 5 | 5 |
| Б | 11 | - | 0 | 0 | 6 | 1 |
| В | 0 | 3 | - | 5 | 8 | 7 |
| Г | 0 | 0 | 1 | - | 13 | 0 |
| Д | 3 | 3 | 5 | 10 | - | 0 |
| Е | 8 | 0 | 5 | 1 | 0 | - |
Таблица 11 – Приведенная матрица.
Параллельно с расчетами в матрицах рисуется "дерево маршрута". Исходной вершиной дерева является вершина "все циклы", определяющая все множество возможных вариантов построения кольцевого маршрута по объезду (обходу) заданных пунктов. Для вершин дерева считаются "нижние границы". Нижняя граница вершины "все циклы" равна сумме наименьших элементов строк и столбцов, в результате вычитания которых получена приведенная матрица. Сумма констант приведения равна:
5+10+7+6+6+6+4+3=47
"Нижняя граница" обозначает: необходимое время на обслуживание маршрута при условии включения заданных пунктов в маршрут в любой произвольной последовательности будет не менее значения "нижней границы" вершины.
Выбор конкретной связи между пунктами производится с помощью характеристик, рассчитываемых для всех нулей приведенной матрицы. Характеристика считается как сумма наименьших элементов строки и столбца приведенной матрицы, в которых находится ноль. Сам ноль, для которого в данный момент считается характеристика, во внимание не берется.
Например, характеристика для нуля в строке А и столбце В складывается из минимума по строке А, равного 0 (РА,Г=0), и минимума по столбцу В, равного 0 (РБ,В=1), без учета самого РАВ
Итак,
запишем приведенную матрицу, указывая
рядом с каждым нулем его характеристики:
| А | Б | В | Г | Д | Е | |
| А | - | 4 | 0(0) | 0(0) | 5 | 5 |
| Б | 11 | - | 0(0) | 0(0) | 6 | 1 |
| В | 0(3) | 3 | - | 5 | 8 | 7 |
| Г | 0(0) | 0(0) | 1 | - | 13 | 0(0) |
| Д | 3 | 3 | 5 | 10 | - | 0(3) |
| Е | 8 | 0(0) | 5 | 1 | 0(5) | - |
Ноль с наибольшим значением характеристики находится в ячейке Е-Д, он указывает на связь между пунктами, которую следует оценить - включать ее в маршрут (РЕРД) или от нее следует отказаться .
От исходной вершины рисуется две ветви: одна к вершине РЕРД, другая к вершине . Чтобы оценить, что выгоднее, нужно для обеих вершин рассчитать "нижние границы". "Нижняя граница" с обязательным исключением связи считается как сумма "нижней границы" исходной вершины, откуда выходит ветвь, идущая к вершине , и характеристики нуля, указавшего на эту связь.
Чтобы
рассчитать "нижнюю границу" вершины
с обязательным включением связи
РЕРД нужно прежде вычеркнуть
Е строку и Д столбец и одновременно элемент,
соответствующий обратной связи этих
пунктов РЕРД.
| А | Б | В | Г | Е | |
| А | - | 4 | 0 | 0 | 5 |
| Б | 11 | - | 0 | 0 | 1 |
| В | 0 | 3 | - | 5 | 7 |
| Г | 0 | 0 | 1 | - | 0 |
| Д | 3 | 3 | 5 | 10 | 0 |
Теперь проанализируем оставшуюся матрицу. Это матрица приведенная, т.к. в каждой строке и каждом столбце ее содержит не менее одного нуля. Тогда сумму констант приведения для этой таблицы равна 0.
Сумма констант
приведения и нижней границы вершины
"все циклы" определяет значение
"нижней границы" вершины РЕРД.
Та вершина, которой соответствует наименьшая по величине "нижняя граница", определяет включить связь в маршрут или нет. Наименьшее значение нижней границы будет соответствовать вершине с обязательным включением в маршрут связи РЕРД, поэтому ветвление дерева продолжается от вершины РЕРД.
Очередная связь определяется аналогично - путем расчета характеристик для нулей последней матрицы. Итак, запишем приведенную матрицу, указывая рядом с каждым нулем его характеристики:
| А | Б | В | Г | Е | |
| А | - | 4 | 0(0) | 0(0) | 5 |
| Б | 11 | - | 0(0) | 0(0) | 1 |
| В | 0(3) | 3 | - | 5 | 7 |
| Г | 0(0) | 0(0) | 1 | - | 0(0) |
| Д | 3 | 3 | 5 | 10 | 0(3) |
Ноль с наибольшим значением характеристики находится в ячейке строки Д и столбца Е. Продолжаем рисовать «дерево маршрута»:
| А | Б | В | Г | |
| А | - | 4 | 0 | 0 |
| Б | 11 | - | 0 | 0 |
| В | 0 | 3 | - | 5 |
| Г | 0 | 0 | 1 | - |
| А | Б | В | Г | |
| А | - | 4 | 0(0) | 0(0) |
| Б | 11 | - | 0(0) | 0(0) |
| В | 0(3) | 3 | - | 5 |
| Г | 0(0) | 0(0) | 1 | - |
| Б | В | Г | |
| А | 4 | 0 | 0 |
| Б | - | 0 | 0 |
| Г | 0 | 1 | - |
| Б | В | Г | |
| А | 4 | 0(0) | 0(0) |
| Б | - | 0(0) | 0(0) |
| Г | 0(0) | 1 | - |
| В | Г | |
| А | 0 | 0 |
| Б | 0 |