Алгоритм метода потенциалов решения транспортных задач

Наиболее распространенным методом решения транспортных задач является метод потенциалов. Решение задачи методом потенциалов включает следующие этапы: разработку начального плана; расчет потенциалов; проверку плана на оптимальность; поиск максимального звена неоптимальности; составление контура перераспределения ресурсов; определение минимального элемента в контуре перераспределения и перераспределение ресурсов по контуру; получение нового плана. Описанная процедура повторяется несколько раз, пока не будет найдено оптимальное решение. Для транспортной задачи существует несколько методов отыс­кания начального плана: метод северо-западного угла; метод минимальной стоимости;

метод двойного предпочтения. Расчет потенциалов выполняют по загруженным клеткам, для которых должно выполняться следующее равенство: где αi, – потенциал i-и строки; βj — потенциал j-го столбца. Проверяем план на оптимальность по незагруженным клеткам, используя следующее неравенство: Контур перераспределения ресурсов составляют по следующим правилам: этот контур представляет замкнутый многоугольник с вершина­ми в загруженных клетках, за исключением клетки с вершиной максимальной неоптимальности, и звеньями, лежащими вдоль строк и столбцов матрицы; ломаная линия должна быть связанной в том смысле, что из лю­бой ее вершины можно попасть в любую другую вершину по звеньям ломаной цепи; в каждой вершине контура встречаются только два звена, одно
из них располагается по строке, другое — по столбцу;

число вершин контура четное, все они в процессе перераспреде­ления делятся на загружаемые и разгружаемые;

в каждой строке (столбце) имеются две вершины: одна — загру­жаемая, другая — разгружаемая. Получе­ние нового плана осуществляется по загруженным клеткам (в соответствии с новой загрузкой) вычисляются потенциалы αi, и βj; по незагруженным клеткам производится проверка плана на оп­тимальность; находится вершина максимальной неоптимальности и строится новый контур перераспределения, и т. д., до тех пор, пока не бу­дет найдено оптимальное решение.

 

Теория принятия решений. Основные понятия.

При принятии управленческих решений о функционировании и развитии экономического объекта необходимо учитывать важную характеристику внешней среды — неопределенность - отсутствие, неполно­та, недостаточность информации об объекте, процессе, явлении или неуверенность в достоверности информации. Неопределенность обусловливает появление ситуаций, не име­ющих однозначного исхода. Среди различных видов си­туаций, с которыми в процессе производства сталкиваются пред­приятия, особое место занимают ситуации риска - сочетание, совокупность различных обстоятельств и условий, создающих обстановку того или иного вида деятельности. Ей сопутствуют три условия. Это наличие неопределенности; необходимость выбора альтернативы; возможность оценить вероятность осуществления выбираемых
альтернатив. Таким образом, если существует возможность количественно и качественно определить степень вероятности того или иного вари­анта, то это и будет ситуация риска.

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

Теория, в которой рассматриваются задачи принятия решений в условиях неопределенности при нали­чии противника, известна как теория игр.