Задача о назначении

Данный груз необходимо доставить к потребителям в объемах . [8]Известны и j = 1, 2, ..., n — стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков будут вывезены полностью, запросы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны.Для записи исходных данных транспортной задачи чаще всего пользуются транспортной таблицей (таблица 2).[3]Общий вид транспортной таблицыПотребители12…nПредложениеПоставщики1…2…………………k…СпросУчитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать следующим образом: [9];; ; ; ;, ; В ряде случаев оказывается удобным графический способ задания транспортной задачи. Для этого на плоскости отмечаются пункты производства и пункты потребления . Каждый пункт производства соединяется с каждым пунктом потребления направленным отрезком (коммуникацией).[10]На рисунке 1 изображено графическое представление транспортной задачи с двумя пунктами производства и тремя пунктами потребления. Около каждого пункта задачи указывается соответствующий объем производства или потребления.Рисунок 1 - Геометрическая интерпретация транспортной задачи Отрезок соединяющий пункты и направлен из пункта производства в пункт потребления, что указывает на возможность перевозки только в одном направлении. Составить план перевозок — это значит указать величину перевозки по каждой коммуникации таким образом, чтобы сумма перевозок, направляющихся в, была равна , а сумма перевозок, направляемых в составляла , единиц продукта. На рисунке1 отмечен один из планов перевозок. Величины перевозок находятся слева от соответствующих коммуникаций. Если около какой-то коммуникации величина перевозки не проставлена, то это указывает на отсутствие транспортировки по данной коммуникации. Графический способ изображения транспортной задачи может быть использован для выяснения геометрического смысла ряда ее свойств.Транспортная задача называется открытой транспортной задачей, если условие баланса нарушаются, т.е. При этом возможны два случая: [7]Суммарные запасы превышают суммарные потребности Суммарные потребности превышают суммарные запасыОткрытая модель транспортной задачи решается приведением к закрытой модели.В случае, если суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель, спрос которого определяются по формулеВ случае, когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик, запасы которого равныПостановка задачиВ распоряжении некоторой компании имеется 6 торговых точек и 6 продавцов. Из прошлого опыта известно, что эффективность работы продавцов в различных торговых точках неодинакова. Коммерческий директор компании произвел оценку деятельности каждого продавца в каждой торговой точке, результаты этой оценки представлены в таблице. Как коммерческий директор должен осуществить назначение продавцов по торговым точкам, чтобы достичь максимального объема продаж?Таблица 2 – Исходные данныеПродавецОбъем продаж, тыс. руб/тыс.штТорговые точкиIIIIIIIVVVIA607845652756B734987597437C285749795773D563848736484E656281488376F797852525962Математическая модельСоставим математическую модель задачи. Определим переменные:, если i-ый сотрудник не принимается на -ую вакансию ;, если i-ый сотрудник принимается на -ую вакансию .Введем ограничения:каждый сотрудник может занять только одну вакансию:переменные принимают только положительные значения и являются целыми числами:Целевая функция имеет вид:Таким образом, экономико-математическая модель задачи имеет вид: найти максимальное значение целевой функции при ограничениях:Решение задачи венгерским методомУмножим все элементы исходной матрицы на (-1) и сложим с максимальным элементом матрицы (87) так, чтобы матрица не содержала бы отрицательных элементов (таблица 3).Таблица 3 – Редуцирование матрицы по строкамIIIIIIIVVVIA27942226031B14380281350C59303883014D31493914233E2225639411F8935352825В каждом столбце определим минимальный элемент и вычтем его из каждого элемента столбца (таблица 4).Таблица 4 – Результаты редуцирования матрицы по строкамIIIIIIIVVVIminA180331351229B143802813500C51223002268D284636112003E1821235074F01272720178Аналогичную операцию редуцирования проведем по столбцам таблицы (таблица 5).Таблица 5 – Результаты редуцирования матрицы по столбцамIIIIIIIVVVIA18033135122B14380281350C5122300226D28463611200E182123507F0127272017min000000Выполним поискрешения, для которого все назначения имеют нулевую стоимость.Определим нулевое значение в ячейке (1, 2). Другие нули в строке 1 и столбце 2 вычеркиваются. Выполняем аналогичные операции для строки 2столбца 3, строки 3 столбца 4, строки 4 столбца 6, строки 5 столбца 5, строки 6 столбца 1. В результате указанных действий получим матрицу, представленную в таблице 6.Таблица 6 – Результаты пересчетаIIIIIIIVVVIA18033135122B14380281350C5122300226D28463611200E182123507F0127272017Количество нулей равно 6. По аналогичному расположению элементов исходной матрицы определим вариант распределения торговых точек между продавцами и вычислим максимальное значение целевой функции:продавец А принимается на торговую точку II;продавец B принимается на торговую точку III;продавец C принимается на торговую точку IV;продавец D принимается на торговую точку VI;продавец E принимается на торговую точку V;продавец F принимается на торговую точку I.При указанном распределении продавцов максимальный объем продаж составит:Решение задачи средствами табличного процессора ExcelДля решения задачи в табличном процессоре Excelсформируем исходные данные (рисунок 2).Рисунок 2 – Исходная форма данныхДля формирования оптимального плана распределения продавцов по торговым точкам используем инструментарий надстройки «Поиск решения».Результаты распределения представлены на рисунке 3.Рисунок 3 – Результаты поиска оптимального плана распределения продавцовАнализ показывает, что результаты, полученные венгерским методом и в табличном процессоре Excelсовпадают.ЗаключениеАнализ объектов, процессов, явлений и систем предполагает не только исследование понятийного аппарата, но и оценку изменений, что наиболее целесообразно проводить с применением методов математического и имитационного моделирования, что позволяет исследовать состояние объекта исследования в различных условиях.В рамках настоящего исследования для достижения цели и задач выполнен теоретический анализ особенностей построения математических моделей, изучены этапы моделирования и выявлены принципы построения моделей для различных систем.В практической части настоящего исследования реализовано построение математических моделей, в частности, рассмотрены примеры применения аппарата математического моделирования для решения задачи о назначениях.В частности, рассматривается задача о распределении продавцом между торговыми точками. Критерием оптимальности является получение максимального объема продаж.Для решения задачи о назначениях в работе выполнено построение экономико-математической модели задачи, выполнено ее решение венгерским методом, а также средствами табличного процессора Excel.По результатам расчетов получено следующее оптимальное решение задачи:продавец А принимается на торговую точку II; продавец B принимается на торговую точку III;продавец C принимается на торговую точку IV;продавец D принимается на торговую точку VI;продавец E принимается на торговую точку V;продавец F принимается на торговую точку I.При указанном распределении продавцов максимальный объем продаж составит:Анализ показал, что математическое моделирование обладают широким спектром методов и средств для анализа, оценки и исследования различных объектов, процессов, явлений и систем, что проявляется в универсальности их использования на практике.Список использованной литературыАгальцов, В.П. Математические методы в программировании: Учебник / В.П. Агальцов, И.В. Волдайская. - М.: ИД ФОРУМ, 2015. - 240 c.Баллод Б.А. Методы и алгоритмы принятия решений в экономике: учебное пособие/ Баллод Б.А., Елизарова Н.Н.— М.: Финансы и статистика, 2016.— 224 c.Духанов, А. В. Имитационное моделирование сложных систем: курс лекций / А. В. Духанов, О. Н. Медведева; Владим. гос. ун-т. – Владимир: Изд-во Владим. гос. ун-та, 2016. – 115 с.Девятко И.Ф. Методы социологического исследования/ И.Ф. Девятко. - Екатеринбург: Изд-во Урал.ун-та, 2016. – 208 с.Ильин А.А. Имитационное моделирование экономических процессов. Тула, 2015. 121 с.Лебедев В.В. Математическое моделирование социально-экономических процессов / В.В. Лебедев. - М.: Наука, 2016. – 229 с.Лавриненко В.Н. Исследование социально-экономических и политических процессов: Учеб.пособ./ В.Н. Лавриненко, Л.М. Путилова. - М.: Вузовский учебник, 2016. – 184 с.Лычкина Н.Н. Современные технологии имитационного моделирования и их применение в информационных бизнес-системах // Банковские технологии. 2015. № 9. С. 60-63.Федосеев В.В. Математическое моделирование в экономике и социологии труда. Методы, модели, задачи: учебное пособие/ Федосеев В.В.— М.: ЮНИТИ-ДАНА, 2015.— 167 c.Ядов В.А. Стратегия социологического исследования: Описание, объяснение, понимание социальной реальности / В.А. Ядов. - М.: Добросвет, 2016. – 316 с.