Метод северо-западного угла
На каждом шаге метода северо-западного угла из всех не вычеркнутых клеток выбирается самая левая и верхняя (северо-западная) клетка. Другими словами, на каждом шаге выбирается первая из оставшихся не вычеркнутых строк и первый из оставшихся не вычеркнутых столбцов. Для того, чтобы заполнить клетку (i,j), необходимо сравнить текущий запас товара в рассматриваемой i-й строке с текущей потребностью в рассматриваемом j-м столбце . Если существующий запас позволяет перевезти всю потребность, то · в клетку (i,j) в качестве перевозки вписывается значение потребности ; · j-й столбец вычеркивается, поскольку его потребность уже исчерпана; · от существующего запаса в i-й строке отнимается величина сделанной перевозки, прежний запас зачеркивается, а вместо него записывается остаток, т.е. . Если существующий запас не позволяет перевезти всю потребность, то · в клетку (i,j) в качестве перевозки вписывается значение запаса ; · i-я строка вычеркивается, поскольку ее запас уже исчерпан; · от существующей потребности в j-й строке отнимается величина сделанной перевозки, прежняя потребность зачеркивается, а вместо нее записывается остаток, т.е. . Нахождение опорного плана продолжается до тех пор, пока не будут вычеркнуты все строки и столбцы. Метод минимального элемента На каждом шаге метода минимального элемента из всехне вычеркнутых клеток транспортной матрицы выбирается клетка с минимальной стоимостью перевозки . Заполнение выбранной клетки производится по правилам, описанным выше. Метод Фогеля На каждом шаге методаФогеля для каждой i-й строки вычисляются штрафы как разность между двумя наименьшими тарифами строки. Таким же образом вычисляются штрафы для каждого j-го столбца. После чего выбирается максимальный штраф из всех штрафов строк и столбцов. В строке или столбце, соответствующем выбранному штрафу, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом . Если существует несколько одинаковых по величине максимальных штрафов в матрице, то в соответствующих строках или столбцах выбирается одна не вычеркнутая клетка с минимальным тарифом . Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.
Формально и реальные и фиктивные столбцы и строки в транспортной матрице абсолютно равноправны. Поэтому при нахождении опорных планов фиктивные строки, столбцы и тарифы необходимо анализировать и использовать точно так же как и реальные. Но при вычислении значения целевой функции фиктивные перевозки не учитываются, поскольку они реально не были выполнены и оплачены. Если величина фиктивных тарифов превышает максимальный из реальных тарифов задачи [ ], то методы минимального элемента и Фогеля позволяют получить более дешевые планы перевозок, чем в случае с нулевыми фиктивными тарифами. II. Для отыскания оптимального решения транспортной задачи используется метод потенциалов.
Популярное: Почему стероиды повышают давление?: Основных причин три... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (241)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |