Решение транспортных задач венгерским методом - Контрольная работа

Решение транспортных задач венгерским методомРазвитие во всем мире компьютерных технологий вызвало появление нового объекта исследований в области управления, получившего название большие, или сложные системы. К ним относятся промышленные предприятия, производственные объединения, отрасли, экономика целого государства, а также глобальные системы (макросистемы). Исследование операций представляет собой комплекс научных методов для решения задач эффективного управления организационными системами, которые состоят из большого числа взаимодействующих между собой подразделений, причем интересы подразделений не всегда согласуются между собой и могут быть противоположны.В общем случае, классический вариант венгерского метода предусматривает наличие предварительного этапа и итерации, которая может многократно повторяться. На предварительном этапе определяется начальный план, и рассчитываются невязки этого плана по строкам, столбцам и суммарная невязка. В противном случае, план необходимо улучшать, для чего и выполняется итерационная часть алгоритма. В этих случаях говорится о задачах с ограниченной пропускной способностью коммуникаций. Задача о назначениях, как частный случай транспортной задачи, решается аналогично ей венгерским методом.Существенным нулем матрицы С называется нуль, соответствующая коммуникация которого в плане Х положительна. Элементы матрицы С, находящиеся в выделенных строках и столбцах называются выделенными. итерации, которая состоит из проверки оптимальности и 3-х этапов, которым предшествует разметка. Этапы а) б) могут повторяться не однократно и завершаются итерации этапом в). 3) Для нулей матрицы С0 двигаясь по столбцам строится матрица Х0 по известным правилам.Требуется отыскать такой план перевозок, при котором весь продукт из пунктов AJI будет вывезен, потребности потребителей полностью удовлетворены и суммарные транспортные затраты будут минимальны. Потребности потребителей (В условных единицах), количество продукта (груза) в каждом пункте (В тех же условных единицах) и транспортные затраты на перевозки продукции (груза) из пункта AJI и BJ заданы в таблицах.Рассматриваемую в задаче ситуацию можно охарактеризовать следующим образом. Определить суточные объемы перевозок груза каждым из курьеров, доход от реализации с учетом ограничений на количество товара (60;70;20). Так как нужно определить объемы перевозки каждого вида продукции, переменными в модели являются, в соответствии с традициями математики: х1 - объемы перевозки №1; При определении плана передачи товара должны быть учтены ограничения на количество товара, которое может перевезти курьер, и на количество товара, которое могут принять потребители.В матрице С в каждом столбце ищем минимальный элемент и вычитаем его из остальных элементов данного столбца. В матрице С’ в каждой строке ищем минимальный элемент и вычитаем его из остальных элементов данной строки. В невыделенной части матрицы С0, т.е. в 3-ем столбце и отмечаем невыделенный нуль С[3,3] апострофом Его невязка по строке нулевая. Строку выделим символом « ».В первом столбце данной строки стоит существенный ноль (), отмечаем его “*”, а “ ” этого столбца берем в «( )». Коррекция плана: Прибавляем к элементам , которым в цепочке соответствовал элемент , и отнимем от элементов , которым в цепочке соответствовал элемент .Для данного типа задач должна быть исследована чувствительность модели применительно к изменению объемов производства одного продукта. Значение минимальных транспортных издержек составило F=310 у.е. Определим пункт, изменение объема производства в котором является наиболее выгодным с точки зрения минимизации затрат на его передачу потребителям. Поэтому наиболее выгодно уменьшить объемы передачи продукции в пункте А2, так как F2 вносит наибольший вклад в значения целевой функции, увеличивать объемы передачи продукции выгоднее всего в пункте А3 , так как перевозка продукта из данного пункта стоит дешевле, чем из других пунктов. Решение транспортной задачи будем определять для следующих векторов объема производства: 1) А = (60,70,20), 2) А = (60,65,25), 3) А = (60,60,30), Остальные условия задачи остаются без изменения.На основании решения транспортной задачи и проведения анализа на чувствительность, можно сделать следующие выводы: минимальные затраты на перевозку всех грузов и удовлетворения всех потребностей заказчиков составляют 310 у.е., для уменьшения затрат на перевозки грузов необходимо увеличить емкость склада A3 и уменьшить емкость склада A1, при ?=10 транспортные расходы удается сократить на 30 условных единиц, при этом достигается оптимальный план перевозок.