10. Построение опорной задачи: метод северо-западного угла и наименьших стоимостей

Пример 1. Условия ТЗ заданы транспортной табл. 3.2.

2. Требуется найти опорное решение ТЗ (построить опорный план).

Решение. Будем заполнять табл.3.2 перевозками постепенно, начиная с левой верхней клетки (1,1) ("северо-западного угла" таблицы). Будем рассуждать при этом следующим образом. Пункт подал заявку на 18 единиц груза. Удовлетворим эту заявку за счет запаса 48, имеющегося в пункте A₁, и запишем перевозку 18 в клетке (1,1). После этого заявка пункта В₁, удовлетворена, а в пункте A₁ осталось еще 30 единиц груза. Удовлетворим за счет их заявку пункта В₂ (27 единиц), запишем 27 в клетку (1,2); оставшиеся 3 единицы груза пункта A₁ назначим пункту B₃. В составе заявки пункта B₃ остались неудовлетворенными 39 единиц. Из них 30 покроем за счет пункта A₂, чем его запас будет ис­черпан, и еще 9 возьмем из пункта А₃. Таблица 3.2

ПО ^ПН	B1	B2	B3	B4	B5	Запасы
A1	^10	^8	^5	^6	^9	48
A2	^6	^7	^8	^6	^5	30
A3	^8	^7	^10	^8	^7	27
A4	^9	^5	^4	^6	^8	20
Заявки bj	18	27	42	12	26	125

Из оставшихся 18 единиц пункта A₃ 12 выделим пункту B₄; ос­тавшиеся 6 единиц назначим пункту B₅, что вместе со всеми 20 единицами пункта A₄ покроет его заявку (табл.3.3). Таблица 3.3

ПО ^ПН	B1	B2	B3	B4	B5	Запасы
A1	18 ^10	27 ^8	3 ^5	^6	^9	48
A2	^6	^7	30 ^8	^6	^5	30
A3	^8	^7	9 ^10	12 ^8	6 ^7	27
A4	^9	^5	^4	^6	20 ^8	20
Заявки bj	18	27	42	12	26	125

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

Таким образом, нами сразу же составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является не только допустимым; но и опорным решением транспортной задачи. Действительно, число базисных клеток таблицы, в которых стоят ненуле­вые перевозки, удовлетворяет условию m+n-1=8. Остальные клетки - свободные (пустые), в них стоят нулевые перевозки и их число равно 12. Значит, наш план - опорный и по­ставленная задача построения опорного плана решена.

Однако полученный опорный план не является оптимальным, по­скольку при его построении мы совсем не учитывали стоимостей пе­ревозок С_ij. Стоимость этого плана, которая найдется, если умножить каждую перевозку на соответствующую стоимость, равна

18.10+ 27.8 + 3.5 + 30.8 + 9.10 + 12.8 + 6.7 + 20.8 = 1039.

Прежде чем рассматривать способы улучшения опорного плана и обеспечения его оптимальности, опишем еще один способ нахожде­ния опорного плана называемый способом "минимальных стоимостей перевозок". В этом случае в матрице стоимостей перевозки (матрице затрат) отыскиваем минимальный элемент и в первую очередь включа­ем в план самую дешевую перевозку, притом в максимально возмож­ном объеме. Обращаясь к исходным данным табл.3.2, в план включаем перевозку 20 единиц груза из ПО А₄ в ПН B₄ со стоимостью 4, что полностью исчерпывает запас ПО A₄. Следующий по величине элемент матрицы затрат (5), расположенный в нескольких клетках таблицы, определяет включение в план перевозки между пунктами A₂ и B₅ , где объем перевозки наибольший (26), и затем перевозки между пунктами A₁ и В₃ объемом 22 единицы, что удовлетворяет заяв­ки пунктов B₃, и В₅. Далее планируются перевозки со стоимостью 6 между пунктами A₁ и B₄ объемом 15 единиц и пунктами A₂ и B₁ объемом 4 единицы. Продолжая действовать аналогичным образом и дальше, придем к плану перевозок табл.3.4.

В том, что полученный план перевозок допустимый, легко убе­диться, проверив, что суммы элементов в каждой отроке табл. 3.4 равны соответствующим запасам, а суммы по столбцам - заявкам. По­скольку число базисных (ненулевых) клеток равно m+n-1=8, а число свободных (нулевых) равно (n-1)(m-1)=12, где m=4, n=5, построенный план перевозок является не только допустимым, но и опорным. Затраты на реализацию этого плана составляют

11.10 + 4.6 + 3.8 + 24.7 + 22.5 + 2074 + 26.5 = 736.

Таблица 3.4

ПО ^ПН	B1	B2	B3	B4	B5	Запасы
A1	11 ^10	^8	22 ^5	15 ^6	^9	48
A2	4 ^6	^7	^8	^6	26 ^5	30
A3	3 ^8	24 ^7	^10	^8	^7	27
A4	^9	^5	20 ^4	^6	^8	20
Заявки bj	18	24	42	15	26	125

Рассмотренный способ построения опорного плана прост, но в ряде случаев приводит к опорному" решению, которое значительно от­личается от оптимального. Лучшего результата можно добиться c по­мощью метода наименьшей стоимости. Из всех цен за единицу перевоз­ки выбираем наименьшую – 4 (A₄-B₃). В эту клетку включаем максимально возможную перевозку из пункта A₄- 20. Во всех ос­тальных клетках этой отроки будут нули, т.к. в пункте A₄ ниче­го не осталось. Пункт B₃ нуждается в 42 ед., 20 он уже получил. В этом столбце следующая минимальная стоимость перевозки – 5(A₁-B₃). В это место нужно поставить недостающее количество груза (22), поставив в остальных клетках этого столбца нули. Продолжая в этом же духе, получим следующую таблицу.

Таблица 3.5

ПО ^ПН	B1	B2	B3	B4	B5	Запасы
A1	0	14	22	12	0	48
A2	4	0	0	0	26	30
A3	14	13	0	0	0	27
A4	0	0	20	0	0	20
Заявки bj	18	27	42	12	26	125