Экономические задачи, сводящиеся к транспортной модели, страница 3
Тема: Решение транспортных задач венгерским методом
7.2.1.2 Венгерский метод
Добавить в избранное О проекте. Решение транспортных задач венгерским методом Вид работы:. Все дипломные по информационному обеспечению. И д Костенко К. Севастополь АННОТАЦИЯ транспортная задача решение венгерский метод В данной пояснительной записке приводится постановка задачи, её экономическая интерпретация и математическая модель. Рассматривается общая методика постановки, построения алгоритмов и решения транспортных задач. Особое внимание уделяется решению транспортных задач венгерским методом. Здесь также представлен текст программы, реализующей решение транспортных задач венгерским методом, описание работы программы, результаты проведения вычислительного эксперимента и сравнительная характеристика полученных результатов. В заключительной части пояснительной записки проводится анализ математической модели на чувствительность к изменению экономических аспектов. Описание интерфейса программы Приложение Б. Задача данной курсовой работы состоит в следующем: Тема курсовой работы - решение транспортных задач венгерским методом - является актуальной на сегодняшний день. Венгерский метод наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления. Достоинством венгерского метода является возможность оценивать близость результата каждой из итераций к оптимальному плану перевозок. Это позволяет контролировать процесс вычислений и прекратить его при достижении определенных точностных показателей. Данное свойство существенно для задач большой размерности. Так как венгерский метод решения Т-задачи является сравнительно простым, то его можно широко применять на предприятиях, где требуется вести подсчет минимальных затрат на перевозку груза, например, со скалада на предприятие. Первый точный метод решения Т-задачи разработан советскими учеными Л. Предположим, что из каждого пункта производства возможна транспортировка продукта в любой пунт потребления. Задача состоит в определении такого плана перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт из пунктов производства вывезен и суммарные транспортные издержки минимальны. Существуют следующие методы решения транспортных задач: Общая схема метода такова. В данном начальном опорном плане каждому пункту ставят в соответствие некоторое число, называемое его предварительным потенциалом. Предварительные потенциалы выбирают так, чтобы их разность для любой пары пунктов Аi и Вj, связанных основной коммуникацией, были равна cij. Если окажется, что разность предварительных потенциалов для всех других коммуникаций не превосходит cij, то данный план перевозок - оптимальное решение задачи. В противном случае указывают способ улучшения опорного плана Т-задачи. Опорный план можно найти следующими методами: Рассмотрим подробнее каждый из этих методов. Начиная с северо-западного угла в естественном порядке осуществляется заполнение матрицы. Заполнение осуществляется по следующему правилу: Так как при корректировке один из элементов, либо а, либо b, становится равным нулю, то соответствующая строка или столбец исключаются в дальнейшем из рассмотрения. Процесс заполнения продолжается до тех пор, пока все элементы векторов производства и потребления не станут равными нулю. Проверяется вырожденность полученного плана. Согласно индексам, полученным на 1-ом этапе роизводится заполнение элементов опорного плана. При этом элементы и правила коррекций вычисляются также как и метод северо-западного угла. Расчитываются штрафы для всех строк и столбцов матрицы. Заполнение опорного плана начинается с минимального элемента строки или столбца с максимальным штрафом. Выбор элементов плана Х и коррекция векторов потребления и постановок осуществляется как рассмотрено выше. Строка или столбец матрицы С, которым соответствует нулевое значение потребности или поставки при дальнейшем вычислении не участвуют в формировании штрафов. Процесс продолжается до тех пор, пока не обнулятся все вектора. Нахождение оптимального плана происходит по следующему алгоритму: Выполняется пересчет матрицы С по правилу: Если все компоненты матрицы С0 не отрицательны, то мы достигли оптимального решения. В противном случае план можно улучшить. Среди элементов матрицы С0 отыскивается минимальный отрицательный, который обозначается d. Соответствующая ему коммуникация будет вводится в базис. Для определения коммуникации, выводимой из базиса необходимо построить цепочку. Цепочка строится следующим образом. Начиная со строк матрицы Х вычеркиваются те из них, в которых один не нулевой элемент. Подобную операцию повторяют затем по столбцам, следом по строкам и т. В результате проведенной процедуры не вычеркнутыми оказываются элементы, которые состовляют цепочку. При этом элементы, стоящие на нечетных местах помечаются минусом, а на четных - плюсом. Среди элементов, отмеченных знаком минус выбирается минимальный элемент Q. При этом коммуникация, значение которой равной нулю оказывается выведенной из базиса. Появление в результате вычитания более одного нуля черевато потерей опорности плана. Чтобы этого не произошло, все нули, кроме одного помечают символом 0 с эпсилом все входящие только в цепочку и соответствующие коммуникации считаются условно существующими. Коррекция значения целевой функции: Если в процесс вычеркивания строки оказались задетыми существенные или ранее отмеченные нули мытрицы С, то вычеркивают столбцы, на которых они находятся. Если в процесс вычеркивания столбца оказались задетыми ранее отмеченные нули матрицы С, то вычеркивают строки, на которых они находятся. Переходим в пункт 3. Требуется отыскать такой план перевозок, при котором весь продукт из пунктов Аi будет вывезен, потребности потребителей полностью удовлетворены и суммарные транспортные затраты будут минимальны. Потребности потребителей в условных единицах , количество продукта груза в каждом пункте в тех же условных единицах и транспортные затраты на перевозки продукции груза из пункта Аi и Вj заданы в таблице 1. Эта фабрика имеет 4 завода, расположенных в разных частях Украины, - в Киеве, Запорожье, Харькове и Виннице. Объем производства каждого завода составляет , , и килограмм черного шоколада в месяц. Реализация продукции производится в трех крупых городах Украины - Донецке, Одессе и Львове. Объемы потребления в каждом городе различны и составляют , и килограмм черного шоколада в месяц соотвественно. Известна стоимость доставки продукции из каждого завода фирмы "Рошен" в названные города. Данные представлены в виде таблицы таблица 1. Суммарной невязкой плана называется величина Суммарная невязка по строкам: Структурная схема алгоритма приведена на рисунке 4. Величина невязки определяет наихудшее из возможных случаев итераций, которое необходимо выполнить для достижения оптимального решения. Поэтому число итераций подчиняется следующему неравенству: Существенным нулем называется нуль матрицы С, соответствующая коммуникация которого в плане Х больше 0. В итоге получаем матрицу С. Аналогичная операция проделывается по строкам матрицы С. В пезультате получаем матрицу С0. Для нулей матрицы С0, перемещаясь по столбцам сверху вниз и меняя столбцы слева направо строим начальный план Х0 и определяем невязку этого плана. Если невязка равна нулю, то рассчитывается целевая функция плана, в противном случае переходят к итерационной части алгоритма. Разметка выполняется в начале итерации и сохраняется до ее конца. В ходе эквивалентных преобразований матрицы С разметка переносится. Прочие элементы разметки добавляются в ходе итерации. Если в процессе поиска обнаруживается, что таких нулей нет, то прибегают к эквивалентным преобразованиям матрицы. Если ноль найдется, то строят цепочку и корректируют план. Поиск выполняют, двигаясь по невыделенным столбцам сверху вниз. Первый найденный ноль отмечают штрихом и анализируют его невязку по строке. Если невязка положительна, то это искомый ноль. Поиск заканчивается, когда найден искомый ноль, либо когда все нули матрицы находятся либо в выделенных строках, либо в выделенных столбцах. Построение цепочки происходит в следующей последовательности: Далее выбирается корректирующий элемент по правилу: Из элементов, которые соответствуют нулям со звездочкой, вычитают Q , а к элементам соответствующим нулям со штрихом прибавляют Q. Поэтому в качестве переменной следует взять элемент плана Хij, который является количеством груза в килограммах транспортированного с некоего предприятия на оптовый склад. Обозначив суммарные затраты через L, можно дать следующую математическую формулировку целевой функции: Все вышеперечисленное приводит к построению линейной модели вида: Так как условие баланса выполняется, то в матрицу С нечего не добавляется. В каждой строке матрицы С отыскиваем минимальный элемент, который вычитается из всех элементов строки. В результате получем матрицу С0. Матрица С0 имеет вид: Символами - отметим существенные нули матрицы. Анализируем невязку такого нуля по строке: Продолжаем данную процедуру до тех пор, пока не будет найден ноль в строке с положительной невязкой - в данном случае это ноль в строке 4. Теперь переходим к этапу построения цепочки. Полученная цепочка показана в таблице: Этап коррекции плана Х Этот этап начинается сразу после построения цепочки. Для коррекции плана находим корректирующий элемент. В данном случае полученная цепочка показана в таблице: Ввод загрузка данных отображен на рисунке 5. Каждая вкладка описывает 1 шаг. Сверху находится матрица С, снизу матрица Х. Результаты програмных подсчётов на ЭВМ показаны на рисунках 5. Соответствующая структура коммуникаций имеет вид: Определим пункт, изменение запасов груза в котором является наиболее выгодным с точки зрения минимизации затрат на его перевозку потребителям. Целевую функцию L можно представить в виде суммы где Li - значения минимальных транспортных издержек, вычисленные по строкам матрицы Хopt. Поэтому наиболее выгодно уменьшить объем производимого продукта в пункте А1, так как L1 вносит наибольший вклад в целевую функцию, а увеличивать его выгоднее всего в пункте А2, так как перевозка из данного пункта стоит дешевле, чем из других пунктов. Установим ориентировочные, а затем уточненные пределы изменения запаса груза. Решение транспортной задачи будем определять для следующиих векторов объема производства: Она определяется следующим планом Х opt: Найдем зависимость оптимального решения и оптимального значения целевой функции от изменений компонент вектора запаса груза. Условия и результаты вычислительного эксперимента приведены в таблице 6. При этом общая стоимость транспортных расходов составит евро в месяц. Венгерский метод решения транспортной задачи является сравнительно простым, и его можно широко применять на предприятиях, где требуется вести подсчет минимальных затрат на перевозку груза, например, с заводов в пункты потребления. Была приведена экономическая интерпретация аздачи, построена ее математическая модель. С помощью алгоритма венгерского был получен оптимальный план перевозок и рассчитано оптимальное значение целевой функции. С помощью разработанной программы был проведен анализ модели на чувствительность. В ходе этого анализа выяснилось, что затраты на перевозку товара, которые оптимально составили евро в месяц, можно уменьшить на евро, если в самом затратном пункте производства уменьшить объем выпускаемого продукта на кг, а в наименее затратном настолько же увеличить. Реализованная программа имеет удобный и простой интерфейс, наглядно представляет решение задачи венгерским методом и может быть использована для дальнейших расчетов стоимостей перевозок и построения оптимальных планов. Методические указания к вы-полнению лабораторных и контрольных работ для студентов дневной и заочной форм обучения специальности 7. На рисунках 1 и 2 преведенны элементы интерфейса до решения поставленной задачи и после соотвественно. Рисунок 1 - Интерфейс программы до выполнения Весь интерфейс состоит из 9 кнопок. Стрелочки предназначены для увеличения размерности исходной матрицы. Рисунок 2 - Интерфейс программы после выполнения После нажатия кнопки Решить появляются вкладки в которых отображается каждый этап шаг решения транспортной задачи. Транспортная задача с ограничениями возможных транспортных средств Дальнейший расчет будет выполнен с помощью венгерского метода решении транспортного алгоритма. Скачать Скачать документ Читать online Читать online. Математическая постановка транспортной задачи линейного программирования Венгерский метод. Идея метода была высказана венгерским математиком Эгервари и состоит в следующем. Если эти условия являются равенствами, то матрица Хo - решение транспортной задачи. Если среди условий имеются неравенства, то осуществляется Постановка и основные свойства транспортной задачи Теорема 1. Описание алгоритма Венгерского метода. В каждом из столбцов матрицы транспортных издержек отыскивают минимальный элемент Решение транспортной задачи в Excel После этого оставшаяся система имеет единственное решение. Пример решения Транспортной задачи. Задача о назначениях Венгерский метод Имеется n видов работ и n рабочих. Каждый рабочий может выполнить любую из n работ за некоторое время цена Нужна качественная работа без плагиата? Другие дипломные по информационному обеспечению. Не нашел материала для курсовой или диплома? Наш проект для тех, кому интересно, для тех, кто учится, и для тех, кто действительно нуждается!
Венгерский метод наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления. Достоинством венгерского метода является возможность оценивать близость результата каждой из итераций к оптимальному плану перевозок. Это позволяет контролировать процесс вычислений и прекратить его при достижении определенных точностных показателей. Данное свойство существенно для задач большой размерности. На практике задачи имеют большую размерность, поэтому решаются с использованием пакетов прикладных программ. Рассмотрим на примере один из возможных вариантов - задачу о назначении служащих на рабочие места. Фирма набирает штат сотрудников и располагает 4 группами различных должностей, а в каждой группе 15, 8, 11, 10 вакансий. Данная задача соответствует транспортной модели. В роли поставщика выступают группы кандидатов, а в роли потребителей - группы должностей. Предложением является число кандидатов в каждой группе, спросом - число вакансий в каждой группе должностей. В качестве тарифов на перевозки рассматриваются затраты на обучение. Решим задачу с помощью алгоритма решения транспортной задачи. Составим матрицу всех клеток таблицы поставок. Для этого у каждой строки и каждого столбца РЧТ ставят потенциал. Найдем минимальные затраты на обучение кандидатов. В настоящее время разработано множество различных алгоритмов решения транспортной задачи: Они относительно просты, по ним составлены десятки программ для различных вычислительных машин. Транспортная модель и ее варианты используется для составления наиболее экономичного плана перевозок одного вида продукции из нескольких пунктов например, заводов в пункты доставки например, склады. Транспортную модель можно применять при рассмотрении ряда практических ситуаций, связанных с управлением запасами, составлением сменных графиков, оборотом наличного капитала, регулированием расхода воды в водохранилищах и многими другими. Кроме того, модель можно видоизменить, с тем, чтобы она учитывала перевозку нескольких видов продукции. Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Статья создана при содействии компании "Центр Научной Литературы", которая представляет вашему вниманию широкий спектр различной профессиональной литературы, в том числе книги по экономике , маркетингу, менеджменту, психологии и многих других дисциплин. Войти Регистрация Общий Оценки Социальный Просмотры Рекомендации Новости Статьи Работы Исследования Заметки Комменты Общественные Гуманитарные Естественные О науке Точные Прикладные. Apelsinka , 21 October Задача Фирма набирает штат сотрудников и располагает 4 группами различных должностей, а в каждой группе 15, 8, 11, 10 вакансий. Требуется распределить кандидатов на должности, затратив минимальные средства на их обучение. Решение Матрица расходов на обучение у. Проверим критерий оптимальности задачи когда оценки всех свободных клеток неотрицательны. Фирма затратит на обучение у. Основная статья - Мебель. Мебель для сидячей работы - тип мебели по назначению , основным предназначением которого является обеспечение возможности выполнения каких-либо профессиональных рабочих функций ее пользователя с наибольшей функциональностью Интересная, но сложная дисциплина Учебная дисциплина Теория механики , не спорим, интереснейшая в своём роде, но не лёгкая. Преподаватели, объясняя материал этой дисциплины, хотят видеть понимание темы студентами, и с целью обратной связи дают решать Экстракция это нечто средневзвешенное. Метод рыночной экстракции для однородной модели средняя ставка капитализации по аналогам. Метод экстракции для разнородных тоже самое плюс учет износа. Метод связанных инвестиций - расчет коэффициентов заемных и Программное обеспечение является неотъемлемой частью компьютерной вычислительной системы ВС. Программное обеспечение ПО выполняет основные функции управления всеми аппаратными средствами ВС в процессе обработки информации. ПО разделяют на систем Возможны различные подходы к определению ценности информации. При копировании материалов ссылка на Book-Science обязательна.
Лохии после родов сколько длятся форум норма
Showthread php спортмастер спб каталог товаров
Набор кеглей детский
Результаты медик лаборатория
Алекс фитнес расписание