Навигация
Построение первоначального плана
25449
знаков
10
таблиц
1
изображение
1.2 Построение первоначального плана
Существует несколько простых схем построения первоначального опорного плана транспортной задачи.
1) Метод северо-западного угла.
Не учитывая стоимости перевозки единицы груза начинается удовлетворение потребностей первого потребителя за счет запаса первого поставщика. Далее переходим из одной клетки в другую по правилу «вниз и вправо», нагружая каждую клетку по максимуму.
2) Метод минимальной стоимости.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел 
или 
. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
3) Метод двойного предпочтения.
В каждом столбце отмечают знаком V клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку VV. В них находится минимальная стоимость как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз исключая из рассмотрения соответствующие столбцы и строки. Затем распределяют перевозки по клеткам, отмеченным знаком V. В оставшейся части таблицы перевозки распределяют по наименьшей стоимости. Опорный план, полученный таким образом, наиболее близок к оптимальному плану.
1.3 Метод потенциалов
Введем специальные показатели 
для каждой строки матрицы перевозок (каждого поставщика), где 
и показатели 
для каждого столбца (каждого потребителя), где 
. Эти показатели называются потенциалами поставщиков и потребителей, их удобно интерпретировать как цены продукта в соответствующих пунктах поставщиков и потребителей.
1) Построение системы потенциалов.
Для построения системы потенциалов используем условие
(5)
2) Проверка выполнения условия оптимальности для незанятых клеток.
Просматриваем строки и для каждой незанятой клетки проверяем выполнение условия
(6)
Если для всех незанятых клеток условие (6) выполняется, то план является оптимальным. Если для некоторых клеток 
, то план является неоптимальным.
3) Выбор клетки, в которую необходимо послать перевозку.
Загрузке подлежит в первую очередь клетка, которой соответствует 
. Но сначала необходимо определить сколько единиц груза должно быть перераспределено в нее.
4) Построение цикла и определение величины перераспределения груза.
Для определения количества единиц груза подлежащих перераспределению отмечается знаком «+» незанятая клетка, которую надо загрузить. Это означает, что клетка присоединяется к занятым клеткам. Появляется цикл, все вершины которого, за исключением клетки, отмеченной знаком «+», находятся в занятых клетках, причем этот цикл единственный. Отыскивается цикл и, начиная движение от клетки, отмеченной знаком «+», поочередно проставляются знаки «-» и «+». Затем находится 
, где
- перевозки, стоящие в вершинах цикла, отмеченных знаком «-». Величина 
определяет, сколько единиц груза можно перераспределить по найденному циклу и на эту величину увеличиваются поставки в вершинах со знаком «+» и уменьшаются поставки в вершинах со знаком «-».
5) В результате перераспределения получен новый опорный невырожденный план, который снова подлежит проверке на оптимальность.
Для проверки на оптимальность нового опорного плана вновь строится система потенциалов и проверяется выполнение условия оптимальности для каждой незанятой клетки.
Если полученный план снова окажется неоптимальным, то следует выполнить вычисления, приведенные в п. 4. процесс повторяется до тех пор, пока все незанятые клетки не будут удовлетворять условию (6).
Транспортные задачи, в базисном плане перевозок которых имеют место занятые клетки с нулевой поставкой (или в первоначальном распределении, или в процессе итераций), называются вырожденными. В случае вырожденной транспортной задачи существует опасность зацикливания, т.е. бесконечного повторения итераций (бесконечного перебора одних и тех же базисных комбинаций занятых клеток). Как правило, в практических задачах транспортного типа зацикливание не встречается. При отсутствии вырождения метод потенциалов конечен и приводит к оптимальному плану перевозок за конечное число шагов.
Похожие работы
... риски. Однако в случае активной и гибкой позиции государства, благоприятной рыночной конъюнктуры отрасль действительно может стать локомотивом экономического роста. 2 Эколого-экономические проблемы и природоохранные мероприятия в нефтегазовой отрасли Республики Казахстан 2.1 Нефтяная промышленность. Состав отрасли Современный мир не мыслим без заводов и фабрик, производящих продукцию, ...
... опытных партий топлива успешно завершены и дали положительные результаты [34]. 2. Экономический анализ и оценка конкурентной среды ОАО "ТАИФ-НК" 2.1 Технико-экономическая характеристика предприятия Историческая необходимость создания в Татарстане нефтеперерабатывающей отрасли диктовалась экономической целесообразностью. Республика, обладающая большими запасами углеводородного сырья и ...
... Сданные в бухгалтерию инвентаризационные описи должны тщательно проверяться и затем после проверки выводится результат инвентаризации. 4. Применение методов управления запасами в целях повышения экономической эффективности системы материально-технического снабжения предприятия 4.1 Регулирование параметров логистической концепции «точно в срок» на основе методов оценки надежности процесса ...
... эффективности использования оборотных средств представим в виде рис. 1.1. Рис.1.1 Объекты анализа эффективности использования оборотных активов 1.2 Цель, задачи и принципы бухгалтерского учета и анализа оборотных материальных активов Целью бухгалтерского учета оборотных материальных активов является получение информации, необходимой для контроля за затратами на их приобретение и ...
0 комментариев