Составление опорного плана

Составление опорного плана. Решение транспортной задачи начинается с нахождения опорного плана. Для этого существуют различные способы.

Например, способ северо-западного угла, способ минимальной стоимости по строке, способ минимальной стоимости по столбцу и способ минимальной стоимости таблицы.

Рассмотрим простейший, так называемый способ северо-западного угла. Пояснить его проще всего будет на конкретном примере: Условия транспортной задачи заданы транспортной таблицей. Таблица № 1 ПН ПО В1 В2 В3 В4 В5 Запасы аi А1 10 8 5 6 9 48 А2 6 7 8 6 5 30 А3 8 7 10 8 7 27 А20 Заявки bj 125 Будем заполнять таблицу перевозками постепенно начиная с левой верхней ячейки ("северо-западного угла" таблицы). Будем рассуждать при этом следующим образом.

Пункт В1 подал заявку на 18 единиц груза.

Удовлетворим эту заявку за счёт запаса 48, имеющегося в пункте А1 , и запишем перевозку 18 в клетке (1,1). После этого заявка пункта В1 удовлетворена, а в пункте А1 осталось ещё 30 единиц груза. Удовлетворим за счёт них заявку пункта В2 (27 единиц), запишем 27 в клетке (1,2); оставшиеся 3 единицы пункта А1 назначим пункту В3. В составе заявки пункта В3 остались неудовлетворёнными 39 единиц. Из них 30 покроем за счёт пункта А2, чем его запас будет исчерпан, и ещё 9 возьмём из пункта А3. Из оставшихся 18 единиц пункта А3 12 выделим пункту В4; оставшиеся 6 единиц назначим пункту В5, что вместе со всеми 20 единицами пункта А4 покроет его заявку.

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

Полученное решение является опорным решением транспортной задачи: Таблица № 2 ПН ПО В1 В2 В3 В4 В5 Запасы аi А1 10 18 8 27 5 3 6 9 48 А2 6 7 8 30 6 5 30 А3 8 7 10 9 8 12 7 6 27 А20 Заявки bj 125 Составленный нами план перевозок, не является оптимальным по стоимости, так как при его построении мы совсем не учитывали стоимость перевозок Сij. Другой способ - способ минимальной стоимости по строке - основан на том, что мы распределяем продукцию от пункта Ai не в любой из пунктов Bj, а в тот, к которому стоимость перевозки минимальна.

Если в этом пункте заявка полностью удовлетворена, то мы убираем его из расчетов и находим минимальную стоимость перевозки из оставшихся пунктов Bj. Во всем остальном этот метод схож с методом северо-западного угла. В результате, опорный план, составленный способом минимальной стоимости по строке выглядит, так как показано в таблице № 3. При этом методе может получиться, что стоимости перевозок Cij и Cik от пункта Ai к пунктам Bj и Bk равны.

В этом случае, с экономической точки зрения, выгоднее распределить продукцию в тот пункт, в котором заявка больше. Так, например, в строке 2: C21 = C24, но заявка b1 больше заявки b4, поэтому 4 единицы продукции мы распределим в клетку (2,1). Таблица № 3 ПН ПО В1 В2 В3 В4 В5 Запасы аi А1 10 8 5 42 6 6 9 48 А2 6 4 7 8 6 5 26 30 А3 8 7 27 10 8 7 0 27 А20 Заявки bj 125 Способ минимальной стоимости по столбцу аналогичен предыдущему способу. Их отличие состоит в том, что во втором способе мы распределяем продукцию от пунктов Bi к пунктам Aj по минимальной стоимости Cji. Опорный план, составленный способами минимальных стоимостей, обычно более близок к оптимальному решению.

Так в нашем примере общие затраты на транспортировку по плану, составленному первым способом F0 = 1039, а по второму F0 = 723. Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными. Их число должно равняться m + n - 1. Необходимо отметить также, что встречаются такие ситуации, когда количество базисных клеток меньше чем m + n - 1. В этом случае распределительная задача называется вырожденной.

И следует в одной из свободных клеток поставить количество перевозок равное нулю. Так, например, в таблице № 3: m + n - 1 = 4 + 5 - 1 = 8, а базисных клеток 7, поэтому нужно в одну из клеток строки 3 или столбца 2 поставить значение “0”. Например в клетку (3,5). Составляя план по способам минимальных стоимостей в отличии от плана по способу северо-западного угла мы учитываем стоимости перевозок Cij, но все же не можем утверждать, что составленный нами план является оптимальным. 4.