Решение задачи о назначениях в программе Microsoft Excel

Ответ на теоретический вопрос:

Решение задачи о назначениях  в программе Microsoft Excel

Задача  о назначениях – это так  называемая распределительная задача, в которой на выполнение каждой работы требуется только один ресурс и каждый ресурс может быть использован только на одной работе. То есть ресурсы неделимы между работами, а работы неделимы между ресурсами. К задачам о назначениях относятся задачи распределения людей на должности или работы, автомашин на маршруты, групп по аудиториям, тематики работ по лабораториям и т.д. 

Задача 

Для выполнения n работ могут быть использованы n работников. Эффективность i-го работника i = 1, …, n при выполнении им j-ой работы j = 1, …, n равна сij . Предполагается, что  каждый работник может быть использован  только на одной работе, а каждая работа может выполняться только одним работником. Определить, какую работу необходимо поручить каждому работнику, чтобы достичь максимальной эффективности по выполнению всех работ. 
 

Математическая  модель. 

Введем  переменную xij значение которой равно 1, если выполнение j-ой работы поручено i-му работнику, и равно 0, в противном случае. Тогда, поскольку на работе j может быть задействован только один работник, то справедливо равенство: 

   

Так как  один работник может выполнять только одну работу, то справедливо следующее равенство: 

   

Целевая функция определяет эффективность  всех работников при выполнении всех работ, которая должна быть максимальной 

   

По своей  постановке эта задача относится  к целочисленной транспортной задаче закрытого типа (суммарная мощность поставщиков равна суммарной мощности потребителей). 

2. Задача  коммивояжера. 

Имеется n городов. Расстояния между любой  парой городов i и j известны и составляют cij . Коммивояжер выезжает из какого-либо города и должен  посетить все города побывав в каждом только один раз и вернуться в исходный город. Ставится задача определить такую последовательность объезда городов, или маршрут, при которой суммарная длина маршрута была бы минимальной. 

Математическая  модель. 

Определим булевы переменные задачи: 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. 

Целевая функция, выражает суммарные расходы доставки по всем выбранным маршрутам и должна быть минимальной.

Ограничения

выражают  условия, согласно которому клиент обслуживается  только один раз. 

Решение задач средствами Excel. 

Приведенные типы задач решаются средствами Excel также как и обычные транспортные задачи, за одним исключением: так как переменные по смыслу задачи могут принимать только двоичные значения 0 или 1, то в ограничениях, задаваемых в диалоговом окне Поиск решения, необходимо указать, что переменные имеют булевы значения.  

Для этого  необходимо нажать в окне Поиск решения  кнопку Добавить (добавить ограничения) и в открывшемся диалоговом окне Добавление ограничения в левом  поле занести ячейки с изменяемыми  переменными, а в среднем поле, нажать на среднюю кнопку и выбрать в предложенных видах ограничений требование двоичности (рис. 1). Дальнейший алгоритм действий остается без изменений (см. Методические пособия к 1-ой и 2-ой Лабораторным работам). 

Решение задачи коммивояжера на Excel. 

Имеется 5 городов, расстояния Cij между которыми приведены в табл.

 

В диагональных клетках таблицы стоят значки ∞ (любое большое число, значительно превосходящее остальные числа в таблице), так как прямого маршрута между одноименными городами не существует. 

Коммивояжер выезжая из города 1, должен посетить все города, побывав в каждом из них только по одному разу и вернуться  в исходный город. Необходимо определить такой маршрут объезда городов, при которой длина маршрута будет минимальной. 
 
 

2. Математическая  модель 

Переменные  xij могут принимать значения равные либо 0, либо 1 

  – целевая функция 

ограничения: 

 – условие въезда в город  j только один раз 

 – условие выезда из города  i только один раз 

, где n = 5, т.е. , i ≠ j, i, j = 2,…, n .  

Исходные  данные в рабочей книге Excel приведены на рис. 2. Здесь же приведены формулы для вычисления ограничений и целевой функции.

 

      На  панели Поиск решения установить следующие параметры решения задачи: 

Целевую ячейку – $B$10 

Равной минимальному значению 

Изменяя ячейки: $B$4:$F$8;$C$11:$F$11 – здесь заносятся не только ячейки, которые будут изменяться, и в которых будут занесены решение задачи (ячейки с адресами $B$4:$F$8), но и ячейки $C$11:$F$11, содержащие переменные ui , которые также являются изменяемыми. 

Ограничения: 

$B$21:$E$24≤3 

$B$4:$F$8 = двоичное 

$B$9:$F$9=1 

$G$4:$G$8=1 

$B$4=0 

$C$5=0 

$D$6=0 

$E$7=0 

$F$8=0 

Параметры: линейная модель, неотрицательные значения, автоматическое масштабирование 

После нажатия  кнопки Выполнить на диалоговой панели Поиск решения. На рабочем листе Excel появляются результаты решения задачи. 
 
 
 
 
 
 
 
 
 
 
 
 

Список  литературы 
 

1. Гельман В. Я. Решение математических задач средствами Excel. – СПб.: Питер, 2003;

 

2. Гарнаев А.. Excel, VBA, internet в экономике и финансах. – СПб.: БХВ – Петербург, 2003.