Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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




Доверь свою работу кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Будем строить допустимое решение задачи, начиная с заполнения левой верхней клетки («северо-западный угол») исходной таблицы. Примем соответствующий объем перевозок x11 = min (a1,b1), т. е. максимальному значению, допускаемому ограничениями на спрос и объем предложений. Если a1>b1, то потребности первого потребителя полностью удовлетворены, и он может быть исключен из дальнейшего рассмотрения, а ресурсы первого поставщика равны a1 b1. Если a1<b1, то первый поставщик полностью использовал свои ресурсы и в дальнейшем его можно не учитывать, а потребности первого потребителя считать равными b1a1. Если a1 = b1, то можно исключить и потребителя, и поставщика, но договоримся в этом случае исключать поставщика, а потребности первого потребителя считать равными нулю.

После установления объема перевозок по маршруту (1,1) мы получаем задачу, в которой суммарное число поставщиков и потребителей на единицу меньше, чем в исходной задаче. Соответствующая таблица для нее получается вычеркиванием первого столбца или первой строки, фиксируя этим, что остальные переменные вычеркнутого столбца (строки) полагаются равными нулю. Продолжая этот процесс, мы придем к допустимому решению, т. к. .

Пример 2.12. Рассмотрим закрытую транспортную задачу с тремя поставщиками и четырьмя потребителями. Количество груза, имеющееся у каждого поставщика и требующееся каждому потребителю, а также соответствующие стоимости перевозки единицы груза (тариф) приведены в таблице 2.8.

Таблица 2.8

 

Потребители 1-й 2-й 3-й 4-й
Поставщики
1-й
2-й
3-й

 

По плану X0, представленному на рис. 2.10, спрос первого потребителя полностью удовлетворен за счет первого поставщика, т. е. x11 = 200, и, следовательно, x21 = 0, x31 = 0. Оставшиеся у первого поставщика 50 ед. груза направляются второму потребителю, т. е. x12 = 50, и у этого поставщика оказывается вывезенным весь груз, следовательно, x13 = 0, x14 = 0. Недостающие второму потребителю 250 ед. груза вывозятся от второго поставщика, т. е. x22 = 250, и, следовательно, x32 = 0. Оставшиеся у второго поставщика 100 ед. направляются третьему потребителю, т. е. x23 = 100, и, следовательно, x24 = 0. Недостающие 250 ед. третий потребитель получает от третьего поставщика, т. е. x33 = 250. И, наконец, остаток в 200 ед. третий поставщик направляет четвертому потребителю, т. е. x34 = 200. Таким образом, весь груз оказался вывезенным у поставщиков и доставлен в нужных количествах потребителям.

                 
                    u1
                         
                 
                    u2
                         
                 
                    u3
                         
  v1     v2     v3     V4    

 

Рис. 2.10

 

Стоимость перевозок по плану X0 составляет

f(X0) = 2×200+4×50 + 3×250 + 6×100+ 4×250 + 5×200 = 3950.

 







Дата добавления: 2014-11-10; просмотров: 580. Нарушение авторских прав; Мы поможем в написании вашей работы!

Studopedia.info - Студопедия - 2014-2022 год . (0.015 сек.) русская версия | украинская версия