Презентация по теме "Задачи о назначениях"

• 1 слайд

  Задачи о назначениях
  Технология решения задач о назначениях в ЭТ Excel
  
  дисциплина
  «Моделирование экономических процессов»
  преподаватель Камышова Галина Алексеевна
  
  

• 2 слайд

  Условие задачи
  Пусть имеется n работников и n рабочих мест (работ).
  
  Известно время, которое затрачивает каждый работник на выполнение каждого вида работ.
  
  Требуется так распределить работников по рабочим местам, чтобы каждый работник был назначен на одну работу, каждая работа выполнялась одним работником при минимальном времени выполнения всеми работниками всех работ.
  

• 3 слайд

  Время выполнения заданий
  

• 4 слайд

  Время выполнения заданий
  

• 5 слайд

  Математическая модель
  Количество переменных в задаче о назначениях, как и в транспортной задаче, определяется произведением числа строк в таблице на число столбцов.
  Введем переменные С1 : С16.
  Каждая переменная соответствует определенной клетке в таблице и принимает значение = 1, если данный работник выполняет данную работу, или = 0 если данный работник не выполняет данную работу.
  

• 6 слайд

  Смысл переменных
  С1 – признак того, что М1 выполняет задание Т1;
  С2 – признак того, что М1 выполняет задание Т2;
  С3 – признак того, что М1 выполняет задание Т3;
  С4 – признак того, что М1 выполняет задание Т4;
  С5 – признак того, что М2 выполняет задание Т1;
  С6 – признак того, что М2 выполняет задание Т2;
  С7 – признак того, что М2 выполняет задание Т3;
  С8 – признак того, что М2 выполняет задание Т4;
  С9 – признак того, что М3 выполняет задание Т1;
  С10 – признак того, что М3 выполняет задание Т2;
  С11– признак того, что М3 выполняет задание Т3;
  С12 – признак того, что М3 выполняет задание Т4;
  С13 – признак того, что М4 выполняет задание Т1;
  С14– признак того, что М4 выполняет задание Т2;
  С15 – признак того, что М4 выполняет задание Т3;
  С16 - признак того, что М4 выполняет задание Т4;
  

• 7 слайд

  Целевая функция
  (минимальное общее время)
  f = 1 0*C1 + 5*C2 + 9*С3 + 18*С4
  + 13*С5 + 19*С6 + 6*С7 + 12*С8
  + 3*С9 + 2*С10 + 4*С11 + 4*С12
  + 18*С13 + 9*С14 + 12*С15 +17*С16
  
  

• 8 слайд

  Ограничения
  Количество ограничений = сумме числа строк и числа столбцов в таблице.
  Ограничения, которые отражают то, что каждый сотрудник выполняет только одну работу:
  
  С1+С2+С3+С4=1
  С5+С6+С7+С8=1
  С9+С10+С11+С12=1
  С13+С14+С15+С16=1
  

• 9 слайд

  Ограничения
  Ограничения, которые отражают то, что каждая работа выполняется только одним сотрудником:
  
  С1+С5+С9+С13=1
  С2+С6+С10+С14=1
  С3+С7+С11+С15=1
  С4+С8+С12+С16=1
  

• 10 слайд

  Двоичные числа
  Условия того, что каждая переменная является двоичным признаком выполнения данной работы данным исполнителем (1 – выполняется, 0 – не выполняется) выразим в виде:
  
  С1 : С16 – двоичные числа.
  

• 11 слайд

  Подготовка листа Excel
  Занесем в ячейки С1:С16 нулевые значения
  Занесем в ячейку А1 формулу целевой функции
  В ячейки, начиная с А3 по А10 занесем формулы левых частей ограничений
  
  После этого вызовем Поиск Решения, который находится в меню Сервис
  

• 12 слайд

  Вид рабочего листа
  

• 13 слайд

  Окно «Поиск Решения»
  

• 14 слайд

  Результаты поиска решения
  

• 15 слайд

  Ответ (решение задачи)
  В результате решения получилось, что признаки С1, С7, С12 и С14 = 1
  
  Сотрудник М1 выполняет работу Т1
  Сотрудник М2 выполняет работу Т3
  Сотрудник М3 выполняет работу Т4
  Сотрудник М4 выполняет работу Т2
  Общее время при этом = 29
  

• 16 слайд

  Оформление отчета
  Единицы в ячейках А3:А10 гарантируют, что каждый сотрудник выполняет один вид работы, а каждый вид работы выполняется одним человеком
  

• 17 слайд

  Способ решения с помощью функций
  

• 18 слайд

  Используемые функции
  Для выражения цели задачи при этом способе была использована функция =СУММПРОИЗВ(D3:G6;D11:G14);
  Эта функция вычисляет сумму попарных произведений
  Данные она берёт из двух таблиц
  

• 19 слайд

  Используемые функции
  В ячейки А3:А6 вводятся формулы:
  =СУММ(D11:G11);
  =СУММ(D12:G12);
  =СУММ(D13:G13);
  =СУММ(D14:G14);
  В ячейки А7:А10 вводятся формулы:
  =СУММ(D11:D14);
  =СУММ(E11:E14);
  =СУММ(F11:F14);
  =СУММ(G11:G14);
  

• 20 слайд

• 21 слайд

  Решение найдено
  

• 22 слайд

  Проверка модели
  

• 23 слайд

  Результаты (выводы)
  Мы видим, что сумма желтых цифр равна 29
  Это действительно минимальный результат
  Вспомните, что результаты, которые мы могли предложить, не решая задачу были 35 (черные цифры) и 32 (красные цифры)
  

• 24 слайд

  Области применения
  распределение изделий между предприятиями
  распределение самолетов между воздушными линиями
  рациональное использование машинно-транспортного парка
  распределение башенных кранов между строительными площадками
  планирование работы речного флота
  распределения посевной площади между сельскохозяйственными структурами
  распределение работников на курсы повышения квалификации
  

• 25 слайд

  Вариант № 1. Необходимо распределить нагрузку преподавателям, закрепив каждого преподавателя за определенным предметом. Имеются данные о том, сколько лет тот или другой преподаватель ведет данный предмет. Несомненно, это свидетельствует о накопленном опыте. Предпочтение будет отдано тому преподавателю, который посвятил данному предмету больше времени. Данные из отдела кадров приведены в таблице:
  

• 26 слайд

  Вариант № 2. Секретарю учебной части необходимо распределить преподавателей по кабинетам. Для этого каждый преподаватель указывает, какой кабинет для него предпочтительнее по следующей системе приоритетов:
  1 приоритет означает, что для преподавателя было бы наилучшим вариантом провести занятие в этом кабинете (самый лучший для преподавателя вариант); 2 приоритет означает, что если нужный кабинет занят, то он может провести и в этом (не самый лучший, но и не самый плохой для преподавателя вариант); 3 приоритет означает, что если нет других вариантов, то преподаватель согласен и на этот кабинет (самый худший вариант для преподавателя).
  

• 27 слайд

  Литература
  Куликов Ю.Г. Экономико-математические методы и модели (раздел «Линейное программирование») Учебное пособие для практических занятий. М.: Московский психолого-социальный институт; Воронеж: Издательство НПО «МОДЭК», 2000 г. (Серия «Библиотека экономиста»)
  Малик Г.С. «Основы экономики и математические методы в планировании»: Учебник для техникумов - М.: Высшая школа, 1988.
  Цисарь И.Ф. Лабораторные работы на персональном компьютере. Учебное пособие для студентов экономических специальностей. – М.: Издательство «Экзамен», 2002.
  Шапкин А.С., Мазаева Н.П. Математические методы и модели исследования операций: Учебник – 3-е изд. – М.: Издательско-торговая корпорация «Дашков и К», 2006.