Студопедия

КАТЕГОРИИ:

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



Метод северо-западного угла. Сущность этого метода становится понятной при рассмотрении следующеего примера




Читайте также:
  1. Amp; Методичні вказівки
  2. Amp; Методичні вказівки
  3. Amp; Методичні вказівки
  4. Amp; Методичні вказівки
  5. Amp; Методичні вказівки
  6. Amp; Методичні вказівки
  7. Amp; Методичні вказівки
  8. B. Искусственная вентиляция легких. Методики проведения искусственной вентиляции легких
  9. Cтруктуры внешней памяти, методы организации индексов
  10. FDDI. Архитектура сети, метод доступа, стек протоколов.

Сущность этого метода становится понятной при рассмотрении следующеего примера. Пусть условия транспортной задачи заданы табл. 8.4

Таблица 8.4

Постав-щики Потребители Запасы
B1 B2 B3 B4 B5
А1 10 7 4 1 4 a2
100 - - - - 100
А2 2 7 10 6 11 a2
100 150 - - - 250
А3 8 5 3 2 2 a1
- 50 100 50 - 200
А4 11 8 12 16 13 a2
- - - 50 250 300
спрос 200   200   100   100   250   850

 

Не учитывая стоимости перевозки единицы груза, начинаем удовлетворение потребностей первого потребителя B1 за счет запаса поставщика А1 (северо-западный угол). В левый нижний угол клетки А1B1 записываем меньший из располагаемых[ объемов min (a1,b1)=min(100,200)=100 ед. После данной операции запасы первого поставщика полностью израсходованы, поэтому остальные клетки первой строки прочеркиваем. Потребности B1 остались неудовлетворенными на 200-100 = 100 ед. Сравниваем этот остаток с запасами поставщика А2: так как 100 < 250, то 100 ед. записываем в клетку А2B1, чем полностью удовлетворяем потребности потребителя B1, а оставшиеся клетки в первом столбце прочеркиваем.

У поставщика А2 осталось 150 ед.груза. Частично удовлетворяем потребителя B2 за счет оставшегося у поставщика А2 груза. Для этого сравниваем этот остаток с потребностями потребителя В2: 150 < 200, записываем 150 ед. в клетку А2В2, так как запасы А2 полностью израсходованы, прочеркиваем остальные клетки второй строки. Читателю рекомендуется довести данный процесс до конца и получить табл. 8.4.

На этом построение первоначального опорного плана заканчивается.

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



Проверим, является ли план, построенный в табл. 8.4, опорным. Видим, что, начиная движение от занятой клетки A1B1, двигаясь только по занятым клеткам, вернуться в нее, невозможно. Аналогичная ситуация с другими начальными клетками. Следовательно, план является опорным, и в то же время он является невырожденным, поскольку содержит точно m+n-1= 4 + 5-1=8 занятых клеток.

При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы груза не учитывалась, поэтому построенный план далек от оптимального.

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

Z = 100·10+100·2+150·7+50·5+100·3+50·2+50·16+250·13=6950 (ед. стоимости).

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


Дата добавления: 2015-04-16; просмотров: 8; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.023 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты