Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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


Методы построения начального опорного решения

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

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

1) если аi < bj , то хij = ai и исключается поставщик с номером i, xik = 0,

k =1, 2, ... , п, k≠ j, bj' = bj - аi ;

2) если ai > bj, то xij= bj и исключается потребитель с номером j, xkj = 0,

k=1, 2, ... , т, к≠ i, а'i = аi - bj ;

3) если ai = bj, то xij= ai =bj и исключается либо i -й поставщик, xik = 0,

k = 1, 2, ..., п, k≠ j , bj'=0, либо j -й потребитель, хкj = 0, k=1, 2, ... , т, к≠ i, аi =0.

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

Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно т + п — 1 и векторы-условия, соответствующие этим клеткам, линейно независимы.

Теорема. Решение транспортной задачи, построенное методом северо-западного угла, является опорным.



Доказательство. Число занятых опорным решением клеток таблицы должно быть равно N = т + п — 1. На каждом шаге построения решения по методу северо-западного угла заполняется одна клетка и исключается из рассмотрения одна строка (поставщик) или один столбец (потребитель) таблицы задачи. Через т + п — 2 шага в таблице будет занято т + п -2 клетки. В то же время останутся невычеркнутыми одна строка и один столбец, при этом незанятая клетка одна. При заполнении этой последней клетки число занятых клеток составит т + п — 2 + 1 = т + п — 1.

Проверим, что векторы, соответствующие занятым опорным решением клеткам, линейно независимы. Применим метод вычеркивания. Все занятые клетки можно вычеркнуть, если проделать это в порядке их заполнения. Ч.т.д.

Необходимо иметь в виду, что метод северо-западного угла не учитывает стоимость перевозок, поэтому опорное решение, построенное данным методом, может быть далеко от оптимального.

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

bj ai

Решение. Распределяем запасы 1-го поставщика. Так как его запасы а1=100 меньше запросов 1-го потребителя b1=150, то в клетку (1, 1) записываем перевозку х11=100 и исключаем из рассмотрения поставщика. Определяем оставшиеся неудовлетворенными запросы 1-го потребителя b1'=b1—а1=150-

-100=50.

Распределяем запасы 2-го поставщика. Так как его запасы а2 = 250 больше оставшихся неудовлетворенными запросов 1-го потребителя b1' = 50, то в клетку (2, 1) записываем перевозку х21 = 50 и исключаем из рассмотрения 1-го потребителя. Определяем оставшиеся запасы 2-го поставщика а'22— b1'=250- — 50 = 200. Так как а'2 = b2= 200, то в клетку (2, 2) записываем х22 = 200 и исключаем по своему усмотрению либо 2-го поставщика, либо 2-го потребителя. Пусть исключили 2-го поставщика. Вычисляем оставшиеся неудовлетворенными запросы 2-го потребителя b'2 = b2а'2 = 200 — 200 = 0.

Распределяем запасы 3-го поставщика. Так как а3 > b'2 (200 > 0), то в клетку (3, 2) записываем х32 = 0 и исключаем 2-го потребителя. Запасы 3-го поставщика не изменились а'3 = а3b'2 = 200 — 0 = 200. Сравниваем а'3 и b3 (200> 100), в клетку (3, 3) записываем х33 = 100, исключаем 3-го потребителя и вычисляем а''3 = а'3b3= 200 - 100 = 100. Так как а''3 = b4, то в клетку (3, 4) записываем х34 = 100. Ввиду того, что задача с правильным балансом, запасы всех поставщиков исчерпаны и запросы всех потребителей удовлетворены полностью и одновременно.


Результаты построения опорного решения приведены в таблице:

bj ai
 

Проверяем правильность построения опорного решения. Число занятых клеток должно быть равно N= т + п — 1 = 3 + 4— 1=6. В таблице занято шесть клеток. Применяя метод вычеркивания, убеждаемся, что найденное решение является «вычеркиваемым»:

(звездочкой отмечен базисный нуль).

Следовательно, векторы-условия, соответствующие занятым клеткам, линейно независимы и построенное решение является опорным.

<== предыдущая лекция | следующая лекция ==>
Метод вычеркивания | Метод минимальной стоимости

Дата добавления: 2014-01-04; Просмотров: 442; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.004 сек.