Целочисленные задачи оптимизации: метод ветвей и границ.

Вершины графа слева – разработчики, вершины справа – технологии (задачи). Ребра, их соединяющие – означают степень, насколько разработчик в разбирается в технологии. Данные цифры, т.е. уровень владения разработчиком данной технологией, являются очень важными, Далее определим порядок решения задачи посредством графового метода. Двудольный граф – граф, который имеет такое разбиение множества вершин на две части (доли), что окончания каждого из ребер принадлежат разнличным долям. В рассматриваемой задаче также имеется четкое разделение: одни вершины модель разработчиков, другие являются задачами, и связями. Паросочетаниями неориентированного графа G являются подмножества M его ребер E, выбранные так, что никакие два ребра из M не являются смежными, т.е. не имеют общей вершины. В терминах задачи о назначениях синонимом этому будет «назначение», чтобы каждый задействованный разработчик брал на себя отдельную задачу. Запрещено взятие двух задач одним исполнителем.В теории графов данная проблема носит называние задачи о Назначениях (ЗН). Она представляет собой частный случай задачи нахождения оптимального паросочетания, что предполагает нахождение максимального уровня задействования ресурсов, чтобы одновременно проводилась проработка максимального числа технологий, поэтому в терминах теории графов — нахождение «максимального паросочетания», составление максимального количества пар типа "разработчик-задача".Необходимо: оптимальным способом задействовать наибольшее количество технологий, назначив каждому разработчику свою задачу. т.е. оптимально распределить между ними области ответственности за технологии, принимая во внимание их личные способности.Решение проводится через выбор незадействованного разработчика, которому еще не назначена задача. Далее проводится анализ, какие задачи могут быть ему назначены, т.е. знакомые ему технологии. Если среди них найдена свободная, то проводится назначение сотрудника. Если данная задача занята кем-либо, то занявшему сотруднику ищется другая свободная технология. В общем, из вершины незадействованного разработчика или разработчика, которому проводится переназначение задачи, проводится просмотр всех знакомых ему технологии на наличие свободной:если нашли свободную – поиск завершенесли задача уже кому-то назначена, то через проход по этому ребру паросочетаний, проводятся попытки «переназначения» технологии разработчику, участвующему в данном назначенииНа рисунке 3 показан пример поиска решения задачи о назначениях методом ветвей и границ.Рисунок - Пример поиска решения задачи о назначениях методом ветвей и границНа рисунке 3 показан пример постановки задачи о назначениях в матричной форме.Рисунок - Пример постановки задачи о назначениях в матричной формеДалее приведем модель транспортной задачи.Транспортная задача используется в системах, где необходимо найти решение об оптимальном распределении транспортных потоков, что предполагает максимальную эффективность использования транспорта. Решение задачи предполагает нахождение плана перевозок, обеспечивающего минимальные параметры пробега, либо накладных расходов, при этом все заявки на получения продукции были бы удовлетворены. Рациональное распределение транспортных потоков позволяет максимально сократить издержки на перевозку продукции, что сделает возможным снижение стоимости товара при его реализации, либо снизит себестоимость продукции в том случае, когда в транспортной задаче рассматривается перевозка комплектующих для производства продукции. Таким образом, использование данного алгоритма при планировании перевозок позволит получить производителям и продавцам продукции значительные конкурентные преимущества в силу того, что стоимость ГСМ постоянно возрастает.2.2. Решение задачи целочисленного программированияПусть необходимо найти минимум функцииПри ограничениях:Параметры поиска решения MSExcelприведены на рисунке 5.Рисунок – Параметры поиска решенияФормулы, связывающие ячейки, приведены на рисунке 6.Рисунок – Режим формулНа рисунке 7 приведен результат решения.57453012210328460234537111237814Целевая функция5-812-6-14Решение0101Рисунок – Результат решенияИнтерпретация результата:В рамках поставленной задачи наиболее эффективно использование ресурсов 2 и 4. Величина издержек составляет 14 ед.3.Решение задачи с использованием MatLabПроведем решение задачи целочисленного программирования с использованием MatLab.На рисунке 8 приведен режим решения задачи.Программный код:f = [5; -8; 12; -6]; A = [5 7 4 5; 2 1 0 3; 6 0 2 3; 7 11 12 3];b = [30; 28; 45; 78];x = bintprog(f,A,b)Результат:Optimization terminated.x = 0 1 0 1Такимобразом, решения, полученные с использованием систем Matlabи Excelидентичны.Решение задачи нелинейного программирования в среде MatLab.Необходимо найти минимум функцииПри ограничениях:H = [1 -1; -1 2]; f = [-8; -2];A = [-6 7; -4 7; 6 -3];b = [20; 14; 3];lb = zeros(2,1);options = optimoptions('quadprog',...'Algorithm','interior-point-convex','Display','off');[x,fval,exitflag,output,lambda] = ...quadprog(H,f,A,b,[],[],lb,[],[],options);int16(x),fval,exitflagОтвет:ans = 2 3fval = -17.4750exitflag = 1Нарисунках 8-9 показано решение задачи в среде MatLab.Рисунок – Режим кода MatLabРисунок – Результаты расчетовТаким образом, в рамках данной работы проведено решение задач методов ветвей и границ с использованием Matlab.ЗаключениеЛинейное программирование - это область науки о методах исследования и поискаоптимальных значений линейной функции, на параметры которой накладываются линейные ограничения. Таким образом, к задачам линейного программирования включают такжепоиск условного экстремума функции. Для исследования линейных функций многих переменных на условный экстремум достаточно применения хорошо разработанных методов математического анализа, при этом невозможность их использования можно довольно просто проиллюстрировать.В рамках данной работы было проведен анализ методов решения задачи о назначениях методом ветвей и границ аналитическими методами, а также с использованием табличного процессора, а также в системе Matlab. В первой части работы проведен анализ использования алгоритмов целочисленного программирования, обоснованы области их применимости. Показано, что обеспечение конкурентоспособности выпускаемой продукции связано с сокращением производственных издержек, что предполагает необходимость оптимальной загрузи имеющихся производственных мощностей. Во второй части работы проведен анализ теоретических аспектов решения задач целочисленного программирования, проведена постановка задачи, проведено описание процесса решения задачи с использованием табличного процессора. В практической части работы проведено решение задачи целочисленного программирования средствами matLab, проведено сопоставление полученных результатов с решением, полученным в табличном процессореПоказано, что результаты, полученные с использованием всех способов идентичны. Таким образом, использование информационных технологий при решении оптимизационных задач является оптимальным решением, так как не требует больших временных затрат и при этом позволяет получать решение поставленных задач.При постановке и решении задачи о назначениях в реальных условиях, проведенной в рамках данной работы, необходимо иметь в виду, что классическая постановка задачи предполагает некоторую идеализацию в силу того, что стоимость выполнения работ (сij) не является постоянной величиной и зависит от множества внешних факторов.Список использованных источниковКаверина В. К. Задачи оптимизации и планирования : учебное пособие / В. К. Каверина. - Воронеж : Воронежский ГАСУ, 2015. - 62 с. Дорофеев В. Ю., Савинов Г. В. "Mathematica" для линейных экономических моделей : учебное пособие / В. Ю. Дорофеев, Г. В. Савинов. - Санкт-Петербург: Изд-во Санкт-Петербургского государственного экономического университета, 2018. - 109 с. Маслова В. М. Управление персоналом предприятия: учеб.пособие для студентов вузов, обучающихся по специальностям экономики и управления ДАНА, 2012. –с.4 159 с.Минанков И. А., Куликов Н. И., Соколов О. В. и др.; Экономика отраслей АПК // М. :КолосС, -2011. –с.90 464 с.Пархомчук М. Трудовые ресурсы //Международный сельскохозяйственный журнал. -2013. -№ 2. –с.12 С. 12.Райзберг Б. А. Современный экономический словарь. 6-е изд., перераб. и доп. -М. : ИНФРА-М, 2014. –с.438 512 с.Рой О.М. Исследование социально-экономических и политических процессов: Учебник для вузов / О.М. Рой. - СПб.: Питер, 2011. – 364 с.Статистика Всемирного банка [Электронный ресурс]. — Режим доступа: http://databank.worldbank.org/data/reports.aspx?source=world-development-indicatorsШаталова Н. И. Трудовой потенциал работника : учеб. пособие. -М. : ЮНИТИ ДАНА, 2013. –с.3 399 с.TheGlobalEnablingTradeIndex 2016 [Электронный ресурс]. — Режим доступа: http://reports.weforum.org/global-enabling-trade-report-2016/economy-profiles/#economy=CHNКлимова С.В. Применение методов вычислений к решению экономических задач. Т. 1. − М.: Наука, 2015. - 363с.Березин И.С., Жидков Н.П. Вычислительная математика. Т. 2. − М.: Наука, 2015. - 123с.Ратушных Б. П. Применение оптимизационных задач в планировании производства. − М.: Изд-во Моск. Ун-та, ЧеРо, 2017. − 609 с. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Вычислительная математика. М.: Инфра-М, 2017. 434 с.Вержбицкий В.М. Численные методы. Практическое использование методов анализа и обыкновенных дифференциальных уравнений. М.: высшая школа, 2016. 381 с.Формалёв В.Ф., Ревизников Д.Л. Численные методы. М.: ФИЗМАТЛИТ, 2014. 400 с.Дьяконов В.П. Решение оптимизационных задач оптимизации с использованием электронных таблиц. М.: СК Пресс, 2015 – 592 с.Дьяконов В.П. Справочник по MSExcel. – М,: «СК Пресс», 1998.Унру Н.Э. Информатика. Часть II. Методические указания к лабораторным работам. № 2981. Новосибирск, изд-во НГТУ, 2015. 46 с.