Способ наименьшего элемента в столбце. Метод "ветвей и границ". Расчета характеристик для нулей последней матрицы

Министерство Российской Федерации по связи и информатизации

Сибирский Государственный Университет Телекоммуникаций и Информатики

Межрегиональный центр переподготовки специалистов

      "Экономико-математические методы и модели в отрасли связи"

Контрольная работа

В-2

Выполнила: 

ЭДВ-53

Проверил:

Новосибирск  2007

ЗАДАЧА 1.

На территории города имеется три телефонных станции А, Б и В. Незадействованные емкости станций составляют на станции А - 1000, Б - 1500, В - 500 номеров. Потребности новых районов застройки города в телефонах составляют: 1 - 400, 2 - 800, 3 - 1200, 4 - 600 номеров.

Среднее расстояние от станции до районов застройки, км

Необходимо составить экономико-математическую модель задачи и с помощью распределительного или модифицированного метода линейного программирования найти вариант распределения емкостей телефонных станций между районами новой застройки, который обеспечивал бы минимальные затраты как на строительство, так и на эксплуатацию линейных сооружений телефонной сети. Естественно, что таким вариантом при прочих равных условиях будет такое распределение емкости, при котором общая протяженность абонентских линий будет минимальной.

Данная задача относится к типу транспортных задач линейного программирования. В качестве поставщиков выступают автоматические телефонные станции, а в качестве потребителей - абоненты микрорайонов города. Решение следует начать с проверки соотношения между суммарной возможностью поставщиков и суммарным спросом потребителей.

Исходя их условий задачи общая потребность новых районов численно равна общей незадействованной емкости АТС ,

1000+1500+500 = 3000 не задействовано номеров на существующих АТС;

400+800+1200+600 = 3000 номеров общей потребности новых районов.

Задачи, в которых соблюдается равенство суммарной возможности пунктов отправления суммарному спросу пунктов назначения, называются транспортными задачами закрытого типа.

Решить задачу рекомендуется распределительным или модифицированным распределительным методом. Эти алгоритмы предусматривают выполнение всех расчетов в матрицах. В таблице показана незаполненная матрица для m-пунктов отправления (поставщиков) и n-пунктов назначения (потребителей).

Существует несколько способов получения исходного плана. Наиболее простым является способ "северо-западного угла".

При использовании этого способа прикрепление пунктов потребления к пунктам отправления груза производится без учета затрат на перевозку. Заполнение клеток начинается с верхней левой ("северо-западной") клетки.

Если Q₁>q₁ , то потребность первого пункта назначения полностью удовлетворяется за счет первого пункта отправления груза, в клетку 1-1 ставим число 400. Второй, в этом случае, заполняется клетка 1-2. В эту клетку в нашем примере нужно отнести 600, так как возможность пункта отправления Q₁=1000 номеров.

Спрос пункта 2 больше оставшейся возможности пункта 1, т.е. q₂>600 , поэтому заполняется клетка 2-2, в нее относим 200. Заполненные клетки плана образуют ступенчатую фигуру, начинающуюся в верхнем левом углу и заканчивающуюся в нижнем правом углу.

Следует заметить, что при заполнении исходного плана способом "северо-западного угла" зачастую получается план, весьма далекий от оптимального.

Лучшим способом получения исходного плана является способ "наименьшего