Принцип построения опорных планов, Метод северо-западного угла - Транспортная задача линейного проектирования

Существует несколько способов построения опорного плана. Это метод северо-западного угла, метод наименьшей стоимости, приближенный метод Фогеля. Суть всех этих методов состоит в том, что опорный план составляется последовательно, в несколько шагов. На каждом из этих шагов для одного из заказчиков заполняется одна клетка, притом так, что, либо полностью удовлетворяется один из заказчиков (тот, в столбце которого находится заполняемая клетка), либо полностью расходуется все номерная емкость одной из АТС (той, в строке которой находится заполняемая клетка).

Метод северо-западного угла

При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного х 11 и заканчивается в клетке неизвестного xmn, т. е. идет как бы по диагонали таблицы.

Заполнение таблицы начинаем с северо-западного угла, т. е. с клетки с координатами 1I. первая АТС не может полностью удовлетворить потребность первого района. Вписываем значение 25 в клетку х 11=25. Остаются неудовлетворенными еще 5 заявок. Полагаем х 21=5 и исключаем из рассмотрения первый район. На АТС 2 остается измененный запас в 25 номеров, а во втором районе как раз 25 заявок. Заполняем клетку 2II и исключаем из рассмотрения второй столбец. Далее северо-западным углом будет клетка 3III. На АТС 3 свободных 40 номеров. Она может частично удовлетворить заявки третьего заказчика. Полагаем х 33=40 и вписываем это значение в клетку 3III и исключаем из рассмотрения третью строку. На АТС 4 есть 55 свободных номеров. Третьему району не хватает 5 номеров, поэтому в клетку 4III записываем это значение и исключаем из рассмотрения третий столбец. На АТС 4 есть еще 50 свободных номеров. Району IV нужно 30 номеров, поэтому полагая х 44=30, вписываем это значение в клетку 4IV. Исключаем четвертый столбец из рассмотрения. Пятому району нужно 35 номеров. Частично удовлетворяем его потребность с помощью АТС 4 и исключаем четвертый столбец из рассмотрения. Затем вводим фиктивную строку 5 с нулевыми расстояниями и для пятого района выполняем недостающие 15 заявок, помещая их в клетку с координатами 5V. Число базисных переменных должно быть n+m-1=5+5-1=9. У нас получается 8, поэтому в одну из клеток добавим 0 номеров. Например, в 1III. И тогда получается 9 базисных переменных. Таким образом, опорный план составлен. Базис образован неизвестными х 11,x13,х 21,х 22,х 33,х 43,х 44,х 45,х 55.

Таблица 2

Телефонные станции

Районы

Свободные номера

I

II

III

IV

V

1
    1 25

2
    6 0

3

2

25

2
    6 5
    2 25

2

1

3

30

3

2

1
    2 40

1

3

40

4

2

5
    6 5
    4 30
    6 20

55

5

0

0

0

0
    0 15

15

Заявки

30

25

45

30

35

Стоимость плана:

S=1*25+6*0+6*5+2*25+2*40+6*5+4*30+6*20+0*15=455

Похожие статьи




Принцип построения опорных планов, Метод северо-западного угла - Транспортная задача линейного проектирования

Предыдущая | Следующая