Навигация
МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА
29598
знаков
7
таблиц
4
изображения
1.2.4 МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА
Согласно данному методу запасы очередного поставщика используются для обеспечения запросов очередных потребителей до тех пор, пока не будут исчерпаны полностью, после чего используется запасы следующего по номеру поставщика.
Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель. При этом нулевые перевозки принято заносить в таблицу только в том случае, когда они попадают в клетку (i,j), подлежащую заполнению, т.е. в таблицу заносятся только базисные нули 
, остальные клетки с нулевыми перевозками остаются пустыми.
Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно m+n-1 и векторы условий, соответствующие этим клеткам, линейно независимы.
Необходимо иметь в виду, что метод северо-западного угла не учитывает стоимость перевозок, поэтому, опорное решение, построенное по данному методу, может быть далеким от оптимального.
Пример 3:
Составить опорное решение методом северо-западного угла транспортной задачи, в которой 5 поставщиков и 5 потребителей. данные записаны в таблице 6
Таблица 6
| | В1 50 | В2 40 | В3 30 | В4 20 | В5 10 |
| А1 10 | |||||
| А2 20 | |||||
| А3 30 | |||||
| А4 40 | |||||
| А5 50 |
Решение:
Распределяем запасы первого поставщика. Так как его запасы 
меньше запросов первого потребителя 
, то в клетку (1,1) записываем перевозку 
и исключаем из рассмотрения первого поставщика. Определяем оставшиеся неудовлетворенными запросы первого потребителя 
.
Распределяем запасы второго поставщика. Так как его запасы 
, меньше запросов первого потребителя 
, то записываем в клетку (2,1) перевозку 
и исключаем из рассмотрения второго поставщика. Определяем оставшиеся неудовлетворенными запросы первого потребителя 
.
Распределяем запасы третьего поставщика 
. Так как его запасы больше запросов первого потребителя 
, то записываем в клетку (3,1) перевозку 
и исключаем из рассмотрения первого потребителя. Определяем оставшиеся неудовлетворенными запросы третьего поставщика 
.
Распределяем запасы третьего поставщика 
. Так как его запасы меньше запросов второго потребителя 
, то в клетку (3,2) записываем перевозку 
и исключаем из рассмотрения третьего поставщика. Определяем оставшиеся неудовлетворенными запросы второго потребителя 
.
Распределяем запасы четвертого поставщика 
. Так как его запасы больше запросов второго потребителя 
, то записываем в клетку (4,2) перевозку 
и исключаем из рассмотрения второго потребителя. Определяем оставшиеся неудовлетворенными запросы четвертого поставщика 
.
Распределяем запасы четвертого поставщика 
. Так как его запасы меньше запросов третьего потребителя 
, то в клетку (4,3) записываем перевозку 
и исключаем из рассмотрения четвертого поставщика. Определяем оставшиеся неудовлетворенными запросы третьего потребителя 
.
Распределяем запасы пятого поставщика. Так как его запасы 
больше запросов третьего потребителя 
, то в клетку (5,3) записываем перевозку 
и исключаем из рассмотрения третьего потребителя. Определяем оставшиеся неудовлетворенными запасы пятого поставщика
.
Распределяем запасы пятого поставщика. Так как его запасы 
больше запросов четвертого потребителя 
, то в клетку (5,4) записываем перевозку 
и исключаем из рассмотрения четвертого потребителя. Определяем оставшиеся неудовлетворенными запасы пятого поставщика
.
Распределяем запасы пятого поставщика. Так как его запасы 
равны запросам пятого потребителя 
, то в клетку (5,5) записываем перевозку 
и исключаем из рассмотрения пятого поставщика и пятого потребителя.
Ввиду того, что задача с правильным балансом, запасы всех поставщиков исчерпаны и запросы всех потребителей удовлетворены.
Результаты построения опорного решения приведены в таблице 7.
| | В1 50 | В2 40 | В3 30 | В4 20 | В5 10 |
| А1 10 | 10 | - | - | - | - |
| А2 20 | 20 | - | - | - | - |
| А3 30 | 20 | 10 | - | - | - |
| А4 40 | - | 30 | 10 | - | - |
| А5 50 | - | - | 20 | 20 | 10 |
Похожие работы
... пункт отправления Am+1 с запасов am+1 равным недостающему запасу и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю. 5. Составление опорного плана. Решение транспортной задача начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ "северо-западного угла", способ минимальной стоимости по строке, способ ...
... сразу же составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является опорным решением транспортной задачи. Составленный нами план перевозок, не является оптимальным по стоимости, так как при его построении мы совсем не учитывали стоимость перевозок Сij . 3. Метод потенциалов. Пусть имеется транспортная таблица, соответствующая начальному решению, хil= для ...
... . При этом значения cij соответствуют коэффициентам целевой функции исходной замкнутой транспортной задачи (1) и в последующем не изменяются. Элементы xij соответствуют значениям переменных промежуточных решений транспортной задачи линейного программирования и изменяются на каждой итерации алгоритма. Если в некоторой ячейке xij=0, то такая ячейка называется свободной, если же xij>0, то такая ...
... ). Требуется распределить все работы между всеми рабочими так, чтобы время выполнения работ было минимальным, а каждую работу выполнял только один рабочий. §4. Решение транспортной задачи в Excel В качестве примера я рассмотрел транспортную задачу для 2 складов и 5 магазинов. · В ячейки C4:C5 записал объемы продукции, имеющиеся на 2 складах. · В ячейки E5:I5 - заявки на продукцию, ...
0 комментариев