double arrow

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

Определение переменных хij. начинают с левой верхней клетки таблицы (это отвечает северо-западному углу на географической карте - отсюда и название метода).

Значения х11 определяют из условия х11 =min(a1,b1). Возможны три варианта:

а) если a1<b1, то х11 =a1; строка i =1 исключается из последующего рассмотрения, а потребность первого потребителя (столбец j =1) уменьшается на величину a1;

б) если a1>b1, х11 =b1 столбец j =1 исключается из рассмотрения, а наличие груза у первого поставщика a1 (строка i =1) уменьшается на величину b1;

в) если a1=b1, х11 =a1= b1 строка i =1 и столбец j =1 исключаются из последующего рассмотрения; такой вариант приводит к вырождению исходного плана (количество положительных перевозок хij. будет менее m+п—1, т.е. часть хij. превратится в нуль).

Затем аналогичные операции осуществляются с оставшейся частью таблицы, начиная с юго-западного угла.

На последнем шаге процесса остается одна строка и один столбец. После заполнения клетки, которая находится на их пересечении, процесс завершается. Это означает, что весь груз или вывезен от поставщиков к потребителям, или у поставщиков остается часть груза, который нужен поставщикам.

Найденный исходный план проверяется на вырожденность: если количество заполненных клеток (полученных значений базисных перевозок хij) равняется m+п—1, то план не вырожден; в вырожденном плане количество положительных перевозок меньше т+п-1. По заполненным клеткам таблицы рассчитываются транспортные расходы — целевая функция Z.

Пример. Определить исходный план перевозок для транспортной задачи, данные для которой приведены в таблице, и отобразить его в таблице.

Таблица

       
                   
х11     х12     х13    
                   
х21     х21     х23    

Таблица

    7
    10 8 7
1 11                  
                 
7 14                  
                 

Шаг 1. х11 =min(11;10) =10. Столбец 1 исключается из рассмотрения, а наличие груза у первого поставщика (строка 1) уменьшается на 10 ед. и принимается равным 1 ед.

Шаг 2. х12 =min(1;8) =8. Строка 1 исключается из рассмотрения, а потребность второго потребителя (столбец 2) уменьшается на 1 ед. и принимается равным 7 ед.

Шаг 3. Х22 =min(14;7) =7. Столбец 2 исключается из рассмотрения, а наличие груза у второго поставщика (строка 2) уменьшается на 7 ед. и принимается равным 7 ед.

Шаг 4. Поскольку в таблице изменилась одна строка (строка 2) и один столбец (столбец 3), то это последний шаг, Х23 =7.

Проверка:

а) весь груз поставщиков вывезен потребителям, так как слева и вверху таблицы чисел не осталось;

б) количество заполненных базисных клеток равняется 4: m+n-1= 2+3-1=4; поэтому получен план невырожденный.

Значения базисных переменных равняются: Х11 =10; Х12 =1; Х22 =7; Х23 =7. Другие переменные хij - небазисные и их значения равняются нулю (в клетках нули не проставляются).

Определим транспортные расходы (значение целевой функции Z) перемножением стоимости ненулевых перевозок cij, на соответствующее им количество груза xij и следующее суммируем:

Z= 8*10+6*1+5*7+7*7=170 ден. ед.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: