Задача о назначениях

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

Модель в общем виде Необходимо распределить n работ между n исполнителями таким образом, чтобы их выполнение было наиболее эффективным. Каждый исполнитель может выполнять только одну работу, и каждая работа может быть выполнена только одним исполнителем. Известна эффективность выполнения i-й работы j-м исполнителем - cij, .

Пример Необходимо изготовить 4 образца изделий на 4 станках (n = 4), причем каждый образец может изготавливаться только на одном станке, а каждый станок быть занят изготовлением только одного образца. Задана матрица эффективности производства каждого образца на каждом станке (строки соответствуют образцам, а столбцы – станкам): (изготовление первого образца на первом станке вообще не эффективно - c11 = 0, на втором эффективность оценивается c12 = 10, …, эффективность изготовления четверного образца на четвертом станке оценивается c44 = 20). Составить наиболее эффективный план производства изделий.

Введем переменные

,

.

Тогда суммарная эффективность составит

Продолжение приложения А

- в этой сумме часть слагаемых будет равна 0 (для хij = 0), а другая часть будет представлять собой эффективность от выполнения конкретной работы конкретным исполнителем (для хij = 1). Каждая i –я работа должна быть выполнена одним исполнителем: . Каждый j–й исполнитель должен выполнить одну из работ:

(10х12 + 15х13 + 4х21 + 4х22 + 2х23 + +10х24 + 20х31 + 30х32 + 5х33 +10х41 + 20х44) Первый образец обязательно должен быть изготовлен на одном из станков: То же самое должно выполняться для остальных трех образцов: На первом станке должен изготавливаться один образец: То же самое должно выполняться для остальных трех станков:

Тогда модель примет вид

mах	mах (10х12 + 15х13 + 4х21 + 4х22 + 2х23 + 10х24 + 20х31 + 30х32 + 5х33 +10х41 + 20х44)

Продолжение приложения А

Построенная модель представляет собой особый случай целочисленных задач - переменные в ней могут принимать только одно из двух значений: 0 или 1 (это задача с булевыми переменными). Помимо метода потенциалов, такая задача может быть решена венгерским методом (он используется только для задачи о назначениях) либо аддитивным методом, специально разработанным для задач с булевыми переменными [11].

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

ПРИЛОЖЕНИЕ Б

(обязательное)

Введение в "Систему деловых задач"

Пакет прикладных программ "Quantitative Systems for Business" (или "Система деловых задач") позволяет строить различные экономико-математические модели и находить решение поставленных задач. При этом ход решения по желанию пользователя сопровождается наглядными иллюстрациями, отражающими используемый подход. Это делает программы пакета очень удобными для применения в учебном процессе.

Пакет предназначен для использования под управлением MS DOS. Все необходимые программы находятся в папке QSB. Для обращения к одной из программ пакета необходимо выбрать соответствующий файл с расширением.ехе и с его помощью запустить программу.

После запуска любой из программ пользователь попадает в главное меню. Выбор нужного режима осуществляется либо клавишами управления курсором (вверх/вниз; при этом перемещается подсветка строки меню режимов; подведя подсветку к нужному режиму, необходимо нажать клавишу <ввод>), либо вводом с клавиатуры номера нужного режима.

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

Программа решения транспортных задач запускается файлом tranрrob.exe. Она предназначена для решения транспортных задач размерности не более чем 50 х 50 (50 поставщиков («пунктов отправления») и 50 потребителей («пунктов назначения»)). Решение осуществляется методом потенциалов. Для задач небольшой размерности (до 4 х 5), возможен вывод на экран каждой итерации этого метода. Размерность задач указана для закрытой модели. Модель открытого типа может быть приведена к закрытому типу за счет введения как дополнительного (фиктивного) потребителя, так и поставщика; но при этом ее размерность соответственно возрастет.

Чтобы ввести и новую задачу, выбирают режим 2.

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

Перемещение между отдельными позициями ввода вперед осуществляется клавишей «ввод», а назад - клавишей «backspace». Исправление введенных значений осуществляют, просто печатая новые поверх старых. На некоторые вопросы программе необходимо ответить Y (yes, да), или N (no, нет), просто введя с клавиатуры нужную букву.

Продолжение приложения Б

Задача может быть поставлена как на минимум, так и на максимум.

Запасы поставщиков и потребности должны быть целыми числами, а коэффициенты затрат/прибыли - действительными. Таким образом, по теореме о целочисленности решения транспортной задачи в результате в оптимальном плане будут только целые числа.

Если используемые по умолчанию имена пунктов отправления и назначения не устраивают пользователя, то необходимо ввести эти имена (длиной не более 6 символов).

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

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

Обычно ввод задачи осуществляется в несколько этапов, после каждого из которых выдается сообщение: «Нажмите SPACE BAR [пробел], если данные правильны».

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

Исходные данные могут быть введены с диска (дискеты) или записаны на них (сохранены) с помощью режимов соответственно 3 и 6. При обращении к этим режимам пользователю задаются вопросы, из какого файла (в какой файл) записывать информацию, и где он находится. Студентам рекомендуется сохранять свои данные, указывая только имя файла. При этом задача будет сохранена в папке QSB, откуда ее впоследствии можно перенести в свою папку. При чтении сохраненной задачи рекомендуется вначале перенести ее в папку QSB, а затем также указать только имя файла.

Введенные данные можно просмотреть и/или распечатать в режиме 4. Студентам рекомендуется использовать этот режим только для просмотра, т.е. на вопрос, следует ли распечатать данные, отвечать всегда N.

Введенные данные можно откорректировать в режиме 7. При использовании этого режима можно изменить имя задачи, ответив на соответствующий вопрос программы. По умолчанию (т.е. если просто нажать «ввод») имя задачи останется тем же. На следующем этапе пользователю предлагается меню режимов коррекции, которое различается в разных программах.

Продолжение приложения Б

Решение задачи осуществляется в режиме 5 (решения). Здесь пользователю также предлагаются различные виды меню режимов решения. Для создания опорного плана можно выбрать метод аппроксимации Фогеля (МАФ) либо метод северо-западного угла (МСЗУ) (по умолчанию используется последний). В программах пакета можно просмотреть и распечатать не только конечные, но и промежуточные результаты. При просмотре решения по итерациям переход к следующей итерации осуществляется любой клавишей, а нажав G, можно сразу перейти к заключительной таблице.

На каждой итерации в правом верхнем углу каждой клетки таблицы указаны коэффициенты целевой функции. Значение целевой функции на очередном опорном плане указано внизу таблицы. Потенциалы обозначены u(i) и v(j). Суммы потенциалов для каждой клетки не указываются. Клетка, соответствующая той переменной, которая войдет в базис, помечается в таблице двумя звездочками, а остальные вершины цикла - более ярким белым цветом (им же помечены потенциалы, соответствующие новой базисной клетке). Внизу таблицы также указываются номер этой клетки и разность между коэффициентом целевой функции при соответствующей переменной и суммой потенциалов. Разметка цикла наглядно не отображается

Иногда программа выдает сообщение о том, что задача имеет множество решений. Это сообщение не всегда бывает верно. Недостатком данного пакета, как и многих других программных средств, в том числе и ориентированных под Windows, является то, что он не учитывает некоторых особенностей задач линейного программирования, связанных с вырожденностью базиса. В частности, случай, когда в оптимальном решении базис является вырожденным, программа принимает за случай, когда имеется альтернативный оптимальный план, т.е. множество решений.