Экономико-математические методы в логистике: линейное программирование

Экономико-математические методы в логистике К.Э.Н., ДОЦЕНТ БОРИСОВА ВИКТОРИЯ ВЛАДИМИРОВНА Л ИНЕ ЙНОЕ ПР ОГ РА ММИР ОВА НИЕ ЗАДАЧА О НАЗНАЧЕН ИЯХ Задача о назначениях Вид транспортной задачи Возможные варианты задачи о назначениях Ресурсы Пот ребители (объ ект ы ) Критерий эф ф ект ивност и Рабочие (сотрудники) Работа (рабочее место, вакансия) Время выполнения Автомобили Маршруты Объем перевозимой продукции Работа (участки) Производительность Время Станки Институт получил гранты на выполнение 4х научноисследовательских проектов. В качестве научных руководителей рассматриваются 4 ученых. Каждый из претендентов провел оценку возможного времени на выполнение каждого гранта. Результаты оценок приведены в таблице. Задача о назначения х Проект 1 Проект 2 Проект 3 Проект 4 Ученый А 3 7 5 8 Ученый Б 2 4 4 5 Ученый В 4 7 2 8 Ученый Г 9 7 3 8 Необходимо за каж ды м учены м закрепить 1 научно-исследовательский проект, исходя из критерия минимума затраченного времени на вы полнении всех проектов. Особенности задачи о назначениях Бинарное решение (назначается - не назначается, 1-0)  Количество назначаемых работ (сотрудников, водителей, аудиторий, научных тем и т.д.) должно быть равно количеству выполняемых работ (автомобилей, маршрутов, студенческих групп, исследовательских групп и т.д.)  Каждый работник обязательно должен получить работу. Все работы обязательно должны быть распределены Любой работник может выполнять любую работу Математическая постановка задачи M – работников … N – работ … , - матрица эффективности выполнения работ Требуется построить план назначений , который максимизирует суммарную эффективность выполнения комплекса работ. При этом Решение задачи на минимум – частный случай транспортной задачи Задача должна быть сбалансирована Общая математическая постановка задачи о назначениях Целевая функция Ограничение по работам Ограничение по работникам Каноническая постановка задачи о назначениях Целевая функция Ограничение по работам: работнику может быть назначена 1 работа Ограничение по работникам: каждый работник назначается на 1 работу Решение задачи о назначениях Венгерский метод. Венгерский метод решения задачи о назначениях Находим минимальные элементы по строкам в матрице и вычитаем минимальный элемент из каждого элемента соответствующей строки Проект 1 Проект 2 Проект 3 Проект 4 Минимальный элемент Ученый А 3 7 5 8 3 Ученый Б 2 4 4 5 Ученый В 4 7 2 Ученый Г 9 7 3 Проект 1 Проект 2 Проект 3 Проект 4 Ученый А 4 2 5 2 Ученый Б 2 2 3 8 2 Ученый В 2 5 6 8 3 Ученый Г 6 4 5 Венгерский метод решения задачи о назначениях Находим минимальные элементы по столбцам в матрице и вычитаем минимальный элемент из каждого элемента соответствующего столбца Проект 1 Проект 2 Проект 3 Проект 4 Проект 1 Проект 2 Проект 3 Проект 4 Ученый А 4 2 5 Ученый А 2 2 2 Ученый Б 2 2 3 Ученый Б 2 Ученый В 2 5 6 Ученый В 2 3 3 Ученый Г 6 4 5 Ученый Г 6 2 2 Миним. элемент 2 3 Венгерский метод решения задачи о назначениях Используя минимальное число линий (горизонтальных или вертикальных) зачеркиваем все нулевые элементы матрицы Проект 1 Проект 2 Проект 3 Проект 4 Ученый А 2 2 2 Ученый Б 2 Ученый В 2 3 2 Ученый Г 6 2 2 Количество линий должно совпадать с количеством назначений Венгерский метод решения задачи о назначениях Находим наименьший элемент среди незачеркнутых и вычитаем его из всех незачеркнутых элементов матрицы и прибавляем к зачеркнутым дважды. Проект 1 Проект 2 Проект 3 Проект 4 Проект 1 Проект 2 Проект 3 Проект 4 Ученый А 2 2 2 Ученый А 2 4 2 Ученый Б 2 Ученый Б 4 Ученый В 2 3 3 Ученый В 1 1 Ученый Г 6 2 2 Ученый Г 4 Венгерский метод решения задачи о назначениях (решение 1) Проводим зачеркивание Проект 1 Проект 2 Проект 3 Проект 4 Ученый А 2 4 2 Ученый Б 4 Ученый В 1 1 Ученый Г 4 Проводим закрепление начиная с вычеркнутых дважды нулей Ученый A - Проект 1 Ученый Б - Проект 4 Ученый В - Проект 3 Ученый Г - Проект 2 Общее время выполнения = 17 Венгерский метод решения задачи о назначениях (решение 2) Проводим зачеркивание Проект 1 Проект 2 Проект 3 Проект 4 Ученый А 2 4 2 Ученый Б 4 Ученый В 1 1 Ученый Г 4 Проводим закрепление начиная с вычеркнутых дважды нулей Ученый A - Проект 1 Ученый Б - Проект 2 Ученый В - Проект 3 Ученый Г - Проект 4 Общее время выполнения = 17 Решение задачи в MS Excel =СУММПРОИЗВ(C3:F6;C10:F13) =СУММ(C10:F10) =СУММ(C10:C13) Решение задачи в MS Excel Решение задачи в MS Excel Дополнительны е условия решения задачи о назначениях  Максимизация целевой функции: после окончания формирования первой таблицы все ее элементы умножаются на (— 1) + максимальный элемент в матрице, чтоб не было минусов.  Недопустимые назначения: задание стоимости выше максимального значения из условий.  Несоответствие числа пунктов назначений и производства: следует включить дополнительные фиктивные строки и столбцы, необходимые для приведения ее к квадратной форме. Значения стоимости, соответствующие фиктивным клеткам, как правило, равны нулю. Вопросы ?