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

Страницы работы

15 страниц (Word-файл)

Фрагмент текста работы

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

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

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

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

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

В-2

Выполнила: 

ЭДВ-53

Проверил:

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

ЗАДАЧА 1.

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

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

Станции

РАЙОНЫ

1

2

3

4

А

4

5

6

4

Б

3

2

1

4

В

6

7

5

2

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

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

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

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

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

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

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

Наименование поставщиков

Наименование потребителей

Возможности пунктов отправления

1

2

-

j

-

n

1

С11

С12

С1j

C1n

Q1

2

С21

С22

С2j

C2n

Q2

-

i

Сi1

Сi2

Сij

Cin

Qi

-

m

Сm1

Сm2

Сmj

Cmn

Qm

Потребности пунктов назначения

q1

q2

qj

qn

ΣQi=Σqj

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

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

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

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

Наименование поставщиков

Наименование потребителей

Возможности пунктов отправления

1

2

3

4

1

400

600

1000

2

200

1200

100

1500

3

500

500

Потребности пунктов назначения

400

800

1200

600

3000

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

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

Похожие материалы

Информация о работе