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

Табличный метод решения транспортной задачи



Читайте также:
  1. I Всебелорусский съезд (конгресс) в Минске в декабре 1917 г. и его решения. Провозглашение Белорусской народной республики и ее уставные грамоты
  2. I. Внесение сведений в форму ДТС-1 при использовании метода определения таможенной стоимости по цене сделки с ввозимыми товарами
  3. I. ЗАДАЧИ КОМИССИЙ ПО ДЕЛАМ НЕСОВЕРШЕННОЛЕТНИХ И ПОРЯДОК ИХ ОРГАНИЗАЦИИ
  4. I. ОСНОВНЫЕ ЗАДАЧИ ОРГАНОВ НАРОДНОГО КОНТРОЛЯ
  5. I. Флагелляция как метод БДСМ
  6. I.ЗАДАЧИ НАБЛЮДАТЕЛЬНЫХ КОМИССИЙ И ПОРЯДОК ИХ ОРГАНИЗАЦИИ
  7. II. Внесение сведений в форму ДТС-2 при использовании метода определения таможенной стоимости по цене сделки с идентичными товарами

Для решения транспортной задачи чаще всего используется табличный метод

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

Допустимый план - в котором по каждой строке и столбцу выполняется баланс. В этом случае удовлетворяются все ограничения.

Опорный план - в котором 0 только m+n-1 клетки, т.е. базисные клетки, все остальные должны быть пустыми.

Особенности заполнения таблицы транспортной задачи:

сначала заполняется левый столбец и верхняя строчка;

затем вносятся балансовые столбец и строчка и считается сумма;

в верхнем правом углу каждой клетки записывается соответствующая стоимость ;

для матрицы х нулевые значения не пишутся;

последними записываются стоимости (записывается общая стоимость всего плана).

Если в этой таблице поставить вместо , так что по строке и по столбцу суммы были равны балансовым, то говорят, что построен «план перевозок» (те цифры, которые сходятся по балансу). Иногда этот план наз. допустимым планом.

По аналогии с симплекс методом можно сформулировать правило подобное правилу вершин: оптимальным планом будет являться один из опорных планов.

Т.о. имеет смысл по аналогии с симплекс методом построить начальный опорный план, а затем переходить от одного опорного плана другому, смежному.

Для получения начального опорного плана есть 2 метода:

1) метод северо-западного угла;

2) метод наименьших затрат.

Для получения нового опорного плана:

метод циклических перестановок;

метод потенциалов Контаровича.


Дата добавления: 2015-07-11; просмотров: 222 | Нарушение авторских прав






mybiblioteka.su - 2015-2024 год. (0.005 сек.)