Ответ на теоретический вопрос:
Решение задачи о назначениях в программе Microsoft Excel
Задача о назначениях – это так называемая распределительная задача, в которой на выполнение каждой работы требуется только один ресурс и каждый ресурс может быть использован только на одной работе. То есть ресурсы неделимы между работами, а работы неделимы между ресурсами. К задачам о назначениях относятся задачи распределения людей на должности или работы, автомашин на маршруты, групп по аудиториям, тематики работ по лабораториям и т.д.
Задача
Для выполнения n работ могут быть использованы n работников. Эффективность i-го работника i = 1, …, n при выполнении им j-ой работы j = 1, …, n равна сij . Предполагается, что каждый работник может быть использован только на одной работе, а каждая работа может выполняться только одним работником. Определить, какую работу необходимо поручить каждому работнику, чтобы достичь максимальной эффективности по выполнению всех работ.
Математическая модель.
Возможно вы искали - Курсовая работа: Моделирование физических процессов
Введем переменную xij значение которой равно 1, если выполнение j-ой работы поручено i-му работнику, и равно 0, в противном случае. Тогда, поскольку на работе j может быть задействован только один работник, то справедливо равенство:
Так как один работник может выполнять только одну работу, то справедливо следующее равенство:
Целевая функция определяет эффективность всех работников при выполнении всех работ, которая должна быть максимальной
Похожий материал - Реферат: Классификация компьютеров и их систем 2
По своей постановке эта задача относится к целочисленной транспортной задаче закрытого типа (суммарная мощность поставщиков равна суммарной мощности потребителей).
2. Задача коммивояжера.
Имеется n городов. Расстояния между любой парой городов i и j известны и составляют cij . Коммивояжер выезжает из какого-либо города и должен посетить все города побывав в каждом только один раз и вернуться в исходный город. Ставится задача определить такую последовательность объезда городов, или маршрут, при которой суммарная длина маршрута была бы минимальной.
Математическая модель.
Очень интересно - Реферат: Системные требования программы Adobe Premiere Pro 2.0
Определим булевы переменные задачи: xij = 1, если коммивояжер переезжает из города i в город j, и xij = 0, если коммивояжер не переезжает из города i в город j.
Тогда задача заключается в определении минимума целевой функции
при ограничениях
– только один въезд в город j,
Вам будет интересно - Реферат: Технические решения личного труда менеджера
– только один выезд из города i .
В задаче коммивояжера необходимо еще одно условие, а именно:
, i ≠ j, i, j = 2,…, n
Это специальное условие обеспечивает устранение нескольких несвязанных между собой маршрутов и циклов, попросту означающих перемещение коммивояжера по замкнутому частичному маршруту.
3. Задача о доставке.
Похожий материал - Курсовая работа: Побудова і використання класів
Фирма обслуживает m клиентов. Каждый день фирма поставляет своим клиентам товары на автомобилях (или на любом транспортном средстве). Существует n маршрутов доставки, каждый из которых позволяет обслужить определенное количество клиентов с использованием только одного транспортного средства. Каждый маршрут характеризуется определенными параметрами, которыми могут быть длина маршрута, стоимость расходуемого топлива на маршруте и т.д. Необходимо выбрать такое множество маршрутов, которое обеспечивало бы обслуживание каждого клиента и только один раз в день, при минимальных суммарных расходах.
Математическая модель.
Введем переменные xj с условиями: xj = 1, если выбран j-ый маршрут, и xj = 0 в противном случае, j = 1, … , n. Введем величины aij так, что aij = 1, если i-ый клиент обслуживается по маршруту j, и aij = 0 в противном случае i = 1, … , m, j = 1, … , n. Стоимость доставки по маршруту j обозначим как сj.
Целевая функция, выражает суммарные расходы доставки по всем выбранным маршрутам и должна быть минимальной.