Лабораторная работа № 7 Задача о назначениях
Цель: приобрести навыки в использовании настройки Поиск решения для эффективного использования трудовых ресурсов.
Задача о назначениях является частным случаем транспортной задачи, имеет такую же структуру, но обладает и своими особенностями. В простейшем случае задача о назначениях формулируется следующим образом. Имеется n различных работ и столько же работников, претендующих на выполнение этих работ. На выполнение каждого вида работ назначается только один работник, при этом каждый работник может выполнить любую работу, но за свою плату и свое время. Необходимо так распределить работы между работниками, чтобы минимизировать суммарные денежные затраты или суммарное время выполнения всех работ.
При решении задач о назначениях полезна табл. 7.1, подобная транспортной таблице.
В этой таблице коэффициенты сij равны стоимости назначения работника i на выполнение работы j. Эта стоимость может выражаться в денежном эквиваленте, длительности времени выполнения работы или может быть каким-либо другим показателем эффективности назначения именно этого работника на данный процесс. Переменные xij – это переменные будущего решения задачи. Они определяются так: xij = 1, если работник i назначается на выполнение работы j, и xij = 0, если работник i не назначается на выполнение работы j. Здесь двоичные переменные, которые могут принимать только два значения: 0 или 1.
Таблица 7.1
Таблица для задачи о назначениях
Работы Работники |
1 |
1 |
… |
n |
Сумма xij по строкам |
1 |
С11 Х11 |
С12 Х12 |
… |
С1n Х1n |
1 |
2 |
С21 Х21 |
С22 Х22 |
… |
С2n Х2n |
1 |
… |
… |
… |
… |
|
… |
n |
Сn1 Хn1 |
Сn2 Хn2 |
… |
Сnm Хnm |
1 |
Сумма xij по столбцам |
1 |
1 |
… |
1 |
… |
Если количества работников и работ равны, то такая задача о назначениях называется сбалансированной, в противном случае задача будет несбалансированной.
Сбалансированной также будет задача, если на некоторые процессы требуются несколько работников, но при этом общие количества требуемых и имеющихся работников совпадают. Назовем такую задачу задачей о назначениях для коллективной работы. В данном случае «транспортная» таблица будет иметь вид, представленный в табл. 7.2.
Чтобы задача была сбалансированной, требуется выполнение равенства
k1+ k2+…+ km= n.
Целевая функция тоже одинакова для всех моделей и записывается так же, как и в транспортной задаче:
Z = C11X11 + C12X12 + … + C1mX1n + C21X21 + C12X12 + … + C2nX2n + + …+ Cn1Xn1 + Cn2Xn2 +…+ CnnXnn.
Таблица 7.2
Таблица для задачи о назначениях для коллективной работы
Работы Работники |
1 |
1 |
… |
m |
Сумма xij по строкам |
1 |
С11 Х11 |
С12 Х12 |
… |
С1n Х1n |
1 |
2 |
С21 Х21 |
С22 Х22 |
… |
С2n Х2n |
1 |
… |
… |
… |
… |
|
… |
n |
Сn1 Хn1 |
Сn2 Хn2 |
… |
Сnm Хnm |
1 |
Сумма xij по столбцам |
k1 |
k2 |
… |
km |
… |
Эту целевую функцию следует минимизировать, если коэффициенты cij выражают стоимости назначения работника i на выполнение работы j.
Ограничения для сбалансированной задачи (без условия коллективной работы) следуют непосредственно из табл. 7.1: все суммы переменных по строкам и столбцам этой таблицы равны 1.
Имеем n ограничений в виде равенств для каждого работника (суммы по строкам):
х11 + х12 + … + х1n = 1;
х21 + х22 + … + х2n = 1;
………………………………..
Хn1 + хn2 + … + хnm = 1.
Аналогично имеем m ограничений в виде равенств для каждой работы (суммы по столбцам):
х11 + х21 + … + хm1 = 1;
х12 + х22 + … + хm2 = 1;
………………………………..
Х1m + х2m + … + хnm = 1.
Таким образом, математическая модель для сбалансированной задачи о назначениях при равном количестве работников и работ построена: имеется n2 переменных хij, целевая функция, которую необходимо минимизировать, и 2n ограничений в виде равенств, а также условия двоичности для переменных.
Теперь запишем ограничения для сбалансированной задачи о назначениях для коллективной работы. Ограничения основаны на условии, что суммы переменных по строкам и столбцам должны равняться числам, которые записаны в табл. 7.2 в ее правом столбце и нижней строке.
Отсюда имеем n ограничений в виде равенств для каждого работника (суммы по строкам):
х11 + х12 + … + х1n = 1;
х21 + х22 + … + х2n = 1;
………………………………..
Хn1 + хn2 + … + хnn = 1.
Аналогично имеем от ограничений в виде равенств для каждой работы (суммы по столбцам):
х11 + х21 + … + хn1 = k1;
х12 + х22 + … + хn2 = k2;
………………………………..
Х1m + х2m + … + хnm = km.
Задание 1. Строительной фирме «Спецстрой» необходимо выполнить бетонные работы на 4 строящихся объектах. В фирме имеется 4 бригады бетонщиков, которые могут выполнить эту работу. Бригадиры каждой бригады побывали на объектах, оценили объемы работ и рассчитали сроки, за которые они могут выполнить работы. Сроки (в рабочих днях) выполнения работ каждой бригадой приведены в табл. 7.3.
Таблица 7.3
Сроки выполнения работ
№ бригады |
Объект |
|||
1-й |
2-й |
3-й |
4-й |
|
1 |
30 |
40 |
50 |
60 |
2 |
36 |
41 |
52 |
58 |
3 |
28 |
44 |
49 |
57 |
4 |
35 |
39 |
49 |
63 |
Перед руководством фирмы стоит задача распределения бригад по объектам таким образом, чтобы суммарный срок выполнения всех работ был минимальным.
Методика выполнения. Поскольку количества бригад и объектов одинаковы, следовательно, имеем сбалансированную задачу о назначениях.
Составляем математическую модель сбалансированной задачи. Определяем 16 двоичных переменных хij (i и j изменяются от 1 до 4), которые будут равны 1, если бригада i назначается на объект j, и 0, если бригада i не назначается на объект j. Если принять за стоимости назначений cij сроки выполнения работ каждой бригадой, которые приведены в табл. 7.3, то целевую функцию можно записать так:
Z = 30x11 + 40x12 + 50x13 + 60x14 + 36x21 + 41x22 + 52x23 + 58x24 + + 28x31 + 44x32 + 49x33 + 57x34 + 35x41 + 39x42 + 49x43 + 63x44.
Определим ограничения. Задача сбалансированная, поэтому имеем 8 простых ограничений в виде равенств:
х11 + х12 + х12 + х14 = 1;
х21 + х22 + х23 + х24 = 1;
х31 + х32 + х33 + х34 = 1;
х41 + х42 + х43 + х44 = 1;
х11 + х21 + х31 + х41 = 1;
х12 + х22 + х32 + х42 = 1;
х13 + х23 + х33 + х43 = 1;
х14 + х24 + х34 + х44 = 1.
Далее на основе записанной математической модели создаем на рабочем листе Ехсеl табличную модель (рис. 7.1).
Значение целевой функции в ячейке F17 вычисляется по формуле СУММПРОИЗВ(В4:Е7;В11:Е14). В диапазонах F11:F14 и В15:Е15 по-прежнему вычисляются суммы значений переменных соответственно по строкам и столбцам матрицы решения.
Рис. 7.1. Табличная модель для сбалансированной задачи о назначениях
Запускаем средство Поиск решения. В одноименном диалоговом окне задаем адрес целевой ячейки F17, устанавливаем переключатель минимальному значению, указываем адрес диапазона изменяемых ячеек В11:Е14, задаем ограничения. Как задавать ограничения двоичности, налагаемые на переменные решения, показано на рис. 7.2.
Рис. 7.2. Задание условия двоичности для переменных решения
После всех установок диалоговое окно Поиск решения должно выглядеть так, как показано на рис. 7.3.
В диалоговом окне Параметры поиск решения устанавливаем флажки Линейная модель и Автоматическое масштабирование, флажок Неотрицательные значения можно не устанавливать. Наконец, в диалоговом окне Поиск решения щелкаем на кнопке Выполнить и получаем решение, приведенное на рис. 7.4.
Найденное решение показывает, что первую бригаду надо отправить на 2-й объект, вторую бригаду – на 4-й объект, третью бригаду – на 1-й объект и четвертую – на 3-й объект. Общая продолжительность всех работ составит 175 рабочих дней.
Рис. 7.3. Диалоговое окно Поиск решения для решения сбалансированной задачи о назначениях
Рис. 7.4. Решение сбалансированной задачи о назначениях
Рекомендуемая литература: [14, 16, 17].
ПРИЛОЖЕНИЕ 1
Основные приемы создания и оформления новой презентации
Поставленная задача |
Требуемые действия |
Создать презентацию без помощи мастера и применения шаблона |
В окне диалога PowerPoint в группе полей выбора Создание презентации выберите Новая презентация |
Выбрать разметку слайда |
В
окне диалога Создать
слайд
выберите требуемый вариант разметки.
После выбора Новая
презентация
появляется окно диалога Разметка
слайда.
Для изменения разметки имеющегося
слайда выполните команду Формат/Разметка
слайда или воспользуйтесь пиктограммой,
размещенной в панели Форматирование
|
Применить шаблон дизайна |
В
меню Формат
выберите команду Оформление
слайда
или воспользуйтесь пиктограммой,
размещенной в панели Форматирование
|
Вставить новый слайд |
Откройте
тот слайд, после которого вы хотите
вставить новый, и выполните команду
Вставка/Создать
слайд
(Ctrl
+ M)
или воспользуйтесь пиктограммой,
размещенной в панели Форматирование |
Ввести текст или добавить объект в метки-заполнители |
Чтобы добавить текст в метку-заполнитель, щелкните мышью, а чтобы добавить заданный объект, щелкните дважды. Метку-заполнитель любого объекта можно преобразовать в метку-заполнитель текста, набрав текст |
Ввести текст в произвольное место слайда |
Выберите
на панели Рисование
инструмент Надпись
|
Удалить текст вместе с меткой-заполнителем |
Щелкните по тексту, затем щелкните непосредственно по рамке метки-заполнителя и нажмите клавишу Delete |
Выровнять набранный текст относительно рамки метки-заполнителя |
Воспользуйтесь
командой Формат/Выравнивание
или кнопками панели инструментов
Форматирование
|
Выбрать цвет и тип линии для рамки метки-заполнителя, подобрать заливку |
Выделите
метку-заполнитель (или установите
курсор в текст, введенный в
метку-заполнитель) и выполните команду
Формат/ Также можно воспользоваться кнопками панели Рисование:
|
Активизировать панель Автофигуры |
Выберите
команду Вставка/Рисунок/Автофигуры
или воспользуйтесь кнопкой панели
Рисование
|
Нарисовать объект |
Активизируйте панель Рисование, выберите соответствующий инструмент (линия, овал, прямоугольник и т. д.) и «растяните» фигуру на слайде, протаскивая курсор |
и
установите текстовый курсор в нужное
место или меню Вставка/Надпись
…
В появившемся диалоговом окне
установите цвет заливки, тип линии и
ее цвет.
–
заливка;
–
цвет линии;
–
тип линии
Окончание прил. 1
Поставленная задача |
Требуемые действия |
Изменить цвет объекта |
Выделите объект и выполните команду Формат/ или воспользуйтесь кнопкой панели Рисование: – цвет линии |
Настроить тень (объем) объекта |
Выделите
объект и воспользуйтесь кнопкой
панели Рисование:
|
Повернуть объект на какой-либо угол |
Выделите объект и воспользуйтесь кнопкой панели Рисование Действия/Повернуть/отразить/Свободное вращение, а затем переместите мышью угол объекта в направлении вращения |
Сгруппировать объекты |
Выделите все объекты, подлежащие группировке, и выполните команду Группировка/Группировать контекстного меню выделенных объектов |
Выполнить художественную надпись |
Воспользуйтесь кнопкой панели Рисование:
|
Вставить звук |
Выберите команду меню Вставка/Фильмы и звук/Звук из коллекции картинок; Звук из файла |
Настроить анимацию |
В
режиме слайдов щелкните объект,
который хотите анимировать. В меню
Показ
слайдов
выберите команду
|
Способ представления документа (т. е. презентации .ppt) в окне приложения PowerPoint |
Документ Power Point может отображаться в окне приложения тремя способами: в виде слайдов, в режиме структуры, в режиме сортировщика слайдов. Для изменения способа представления достаточно выбрать соответствующую команду в меню Вид или щелкнуть по одной из трех кнопок в левой части горизонтальной полосы прокрутки:
– режим сортировщика слайдов |
Провести демонстрацию |
Выполните
команду Вид/Показ
слайдов
(F5)
или воспользуйтесь кнопкой
|
Перейти к следующему слайду в процессе демонстрации |
Воспользуйтесь щелчком мыши, клавишами Enter, Пробел; Page Down, Page Up или клавиши навигации курсора (): переход вперед/назад по галерее слайдов; Home – переход к самому первому слайду; End – переход к самому последнему слайду |
Провести демонстрацию, не запуская PowerPoint |
Найдите свой файл, выделите и вызовите контекстное меню нажатием правой кнопки мыши. В контекстном меню выберите команду Показать |
–
Стиль
тени.
–
Объем
– Добавить
объект WordArt
или
соответствующую команду контекстного
меню выбранного объекта. Выберите
нужные элементы панели Настройка
анимации
–
показ
слайдов (с текущего слайда);
–
обычный
режим;
ПРИЛОЖЕНИЕ 2
Основные приемы создания и оформления презентации по шаблону
Поставленная задача |
Требуемые действия |
Создать презентацию на основе готового шаблона |
В меню Файл выберите команду Создать; в группе полей выбора Создание с помощью шаблона откройте презентацию с соответствующей темой из группы Общие шаблоны. Измените заголовок шаблона и предлагаемое содержание в соответствии с вашими требованиями. В режиме слайдов измените по желанию цветовую схему, добавьте или измените элементы образца |
Создать собственный шаблон |
Подготовьте презентацию, которую вы хотите в дальнейшем использовать как шаблон. В меню Файл выберите команду Сохранить как; раскройте список Тип файла и выберите Шаблон презентации (*.pot); введите имя для нового шаблона и нажмите кнопку Сохранить |
Установить способ перехода слайда |
Находясь в режиме слайдов выберите команду Показ слайдов/Смена слайдов. В списке Применить к выделенным слайдам выберите нужный эффект |
Установить время перехода слайдов |
В окне диалога Смена слайдов в группе полей выбора Смена слайда выберите автоматически после и задайте время. Перед выполнением демонстрации выберите команду Показ слайдов/Настройка презентации, в группе полей выбора Смена слайдов установите по времени |
Изменить порядок слайдов |
Перейдите в режим Сортировщика слайдов и переместите мышью слайды, разместив их в требуемом порядке |
Вставить рисунок |
Выполните
команду Вставка/Рисунок/Из
файла или
щелкните
В открывшемся файлере выберите нужный файл |
Вставить графику из коллекции картинок |
Выполните
команду Вставка/Рисунок/Картинки
или
щелкните
Выберите команду Коллекция картинок. В открывшемся файлере выберите нужное изображение. Запомните в Clipbord: команда Копировать. Перейдите к слайду и вставьте изображение из буфера обмена |
Вставить символ Microsoft Office |
Для набора символов Microsoft Office удобно воспользоваться Таблицей символов. По кнопке Пуск на панели задач Windows выберите Программы. Далее перейдите в раздел Стандартные/Служебные /Таблица символов. Выберите нужный шрифт и символ, нажмите Копировать. Перейдите к слайду и вставить символ из буфера обмена. Окно Таблица символов можно закрыть |
на
панели Рисование
PowerPoint.
.