Эффективные назначения

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Эффективные назначения

Назначение разработки, область применения и её ограничения

Программно-методическая разработка по теме «Эффективные назначения» предназначена для студентов бакалавриата, обучающихся по направлениям «Государственное и муниципальное управление», «Менеджмент», «Экономика и управление промышленным предприятием» и др. Пособие может быть использовано для изучения предметов «Основы математического моделирования социально-экономических процессов», «Экономико-математические методы и модели», «Программные средства решения экономических задач», и т.п. Пособие содержит описание компьютерной технологии моделирования и оптимизации линейной системы с назначениями, в которой определен критерий оптимизации. Цель пособия - поддержка изучения базовых компьютерных технологий моделирования социально-экономических систем на уровне основных понятий теории оптимизации линейных систем с назначениями и практических методов решения задач оптимизации назначений в среде электронного табличного процессора EXCEL с применением программы «Поиск решения». Приведено детальное описание компьютерной модели задачи о назначениях в среде EXCEL, интерфейсы используемых программ EXCEL, схемы размещения исходных данных и промежуточных и окончательных результатов расчетов. Пособие может быть полезным также и для студентов магистратуры, аспирантов, преподавателей и всех, интересующихся применением компьютерных технологий для моделирования социально-экономических процессов и преподавания соответствующих дисциплин.

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

Пример формулировки. Фирма планирует организовать снабжение производства и сбыт производимой продукции. Отобраны четыре контрагента. На основе их предложений построена матрица эффективностей каждого контрагента по каждой позиции.

Все работы по поставкам и сбыту должны быть обеспечены договорами контрагентов, при этом за каждый вид работ должен отвечать только один контрагент. Все включенные в список контрагенты должны быть обеспечены заказами, но только по одному виду работ. Требуется найти оптимальное распределение контрагентов по видам договорных работ, обеспечивающее максимальный эффект от всего комплекса заключенных договоров в целом.

Математическая модель. Исходные данные задачи включают в себя два вектора - вектор готовности контрагентов, элементы которого равны 1, если данный контрагент готов принять участие в планируемых работах, и 0 , если не готов. И вектор потребности в услугах, элементы которого равны 1 для услуг, в которых в настоящий момент существует потребность, и 0 для услуг не актуальных. Также в состав исходных данных входит матрица коэффициентов эффективности контрагентов по услугам С.

Аргументом задачи является план назначений - матрица Х. Ее элементы - неизвестные, подлежащие определению величины ХIJ. Поскольку, по условию задачи совместительство и разделение обязанностей запрещены, то аргументы могут принимать только значения 0 или 1. Значение 1 аргумент XIJ принимает в случае, если контрагент номер I выбран для оказания услуги номер J. Значение 0 - если не выбран. Таким образом, аргументы задачи являются элементами множества бинарных переменных.

Если для контрагента I эффективность выполнения им услуги номер J равна CIJ, его назначение на оказание услуги J равно XIJ, то вклад данного назначения в общую эффективность плана будет равен произведению этих величин ZIJ=CIJ*XIJ. Рассматривая контрагента I в плане оказания им спектра услуг, можно определить его эффективность как сумму всех назначений

алгоритм компьютерный назначение двойственный

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

Теперь рассмотрим загрузку контрагента I. Его загрузка по услуге J равна XIJ. Общий расчетный (планируемый) объем загрузки XI для него представляет сумму этих величин, что можно записать в виде . Поскольку по условию задачи все контрагенты должны быть загружены в соответствии с их готовностью, а готовность каждого контрагента I равна 1, то планируемый объем загрузки для каждого контрагента должен быть равен 1. То есть должно выполняться N равенств .

Рассматривая услугу J, можно выразить суммарный объем назначений для нее в виде . По условию задачи расчетный суммарный объем назначений для услуги J должен быть равен 1. То есть должно выполняться равенство XJ=1. Совокупность этих условий для всех видов услуг структуры с назначениями можно теперь представить в виде системы равенств Таким образом, математическую модель оптимизации структуры с назначениями по критерию максимума эффективности при условиях обеспечения потребностей в услугах без разделения обязанностей и привлечения всех контрагентов без совместительства можно представить в виде

В данной модели задачи о назначениях прямые ограничения на аргументы задачи - объемы перевозок XIJ - описывают условие, что эти аргументы могут принимать значения, равные только 0 или 1. Это условие отражает требования запрета на совместительство и разделение функций.

В матричной форме компактной модели задачи о назначениях исходные данные, как описано выше, включают в себя два вектора-индикатора: вектор готовности контрагентов IR ={1}, IR BN и вектор потребности в услугах IP ={1}, IP BN и матрица эффективностей C. Аргументом задачи будет матрица Х, элементы которой - бинарные переменные, индикаторы эффективного назначения.

Мы можем записать совокупность левых частей системы ресурсных ограничений как произведение матрицы аргументов на вектор-индикатор поставщиков, то есть в виде XЧIR, а саму систему ресурсных ограничений - в виде XЧ IR =1. Аналогично, систему плановых ограничений можно записать в виде (IP )ТЧX =1.

Целевая функция задачи о назначениях в этих обозначениях будет иметь вид Z(X)= (IP )ТЧZЧ IR. Матрица Z в этом выражении - это матрица эффективности назначений, элементы которой - эффекты от назначения контрагента I на предоставление услуги J. Элементы матрицы Z вычисляются как произведения соответствующих элементов матриц С и Х, Z=C*X. Имеем

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

Компьютерная модель. Исходными данными компьютерной модели являются: вектор-индикатор готовности контрагентов IR и вектор-индикатор потребности в услугах IP, а также матрица эффективностей контрагентов по услугам С. Алгоритм компьютерной технологии моделирования назначений включает в себя следующие шаги

1. Разместить исходные данные - вектор-индикатор контрагентов IR[G7:G10], вектор-индикатор услуг IP[С11:F11] и матрицу С[C7:F10].

2. Отвести блок ячеек для матрицы плана назначений Х[K7:N10].

3. Отвести блок [O7:O10] для вычисления левых частей ресурсных равенств-ограничений DR= XЧ IP =МУМНОЖ(K7:N10;ТРАНСП($C$11:$F$11))

4. Отвести блок [K11:N11] для левых частей плановых равенств-ограничений DP=(IR)ТЧX =МУМНОЖ(ТРАНСП($G$7:$G$10);K7:N10)

5. Отвести блок ячеек для размещения матрицы эффективности назначений Z[C16:F19] =C7:F10*K7:N10

6. Отвести блок [G16:G19] для суммарных эффектов назначений каждого контрагента ZR=ZЧIP =МУМНОЖ(C16:F19;ТРАНСП($C$11:$F$11)).

7. Отвести блок [C20:F20] для суммарных эффектов назначений для каждой услуги ZP= (IR )ТЧZ . =МУМНОЖ(ТРАНСП($G$7:$G$10);C16:F19)

8. Выделить ячейку [G20] для значения целевой функции Z(X)=(IR)ТЧZЧIP =МУМНОЖ(МУМНОЖ(ТРАНСП($G$7:$G$10);C16:F19);ТРАНСП(C11:F11))

9. Настроить и запустить программу «Поиск решения».

Общий вид компьютерной модели задачи о назначениях показан на рисунке 2 в таблицах 1, 2, 3. В таблице 4 показана схема размещения элементов компьютерной модели двойственной задачи. Соответствующие блоки ячеек программируются по приведенным выше формулам. Настройки программы «ПОИСК РЕШЕНИЯ» для пары двойственных задач также показаны на рисунке 1.

Рис.1. Настройки программы "Поиск решения"

Рисунок 1. Компьютерная модель задачи о назначениях

2. Используемые технические и программные средства

Для создания данного электронного продукта использовался персональный компьютер типа Intel Pentium IV c операционной системой Microsoft Windows XP Professional версия 2005 Service Pack 2. Использовался пакет MS-OFFICE с текстовым редактором MS-Word 2003 и MS-Excel 2003.

Размещено на Allbest.ru