Расчетная работа - Решение задач о назначении - файл n1.doc

приобрести
Расчетная работа - Решение задач о назначении
скачать (251 kb.)
Доступные файлы (1):
n1.doc251kb.13.09.2012 18:16скачать

n1.doc

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

Стоимость производства детали на станке определяется коэффициентом . Найти одно из оптимальных распределений станков и суммарную стоимость производства.



Решение

Воспользуемся алгоритмом Куна (венгерским алгоритмом).

1. Преобразуем матрицу весов. Вычтем из каждой строки минимальный элемент. В каждой строке появится по одному нулю



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

2. По преобразованной матрице весов построим матрицу смежности двудольного графа , так, что , если и , если . Получим



3. Находим наибольшее паросочетание полученного двудольного графа . Для этого можно воспользоваться алгоритмом Форда-Фалкерсона. Изображаем граф (рис. 1) и одно (любое) из его наибольших паросочетаний (рис. 2)



Рис. 1



Рис. 2



Рис. 3





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

Найдем вершины, достижимые из множества . Эти вершины образуют два множества и (на рис. 3 помечены +). В соответствии с номерами находим минимальный элемент в строках 1,2 и столбцах матрицы . Это . Вычитаем 1 из строк и добавляем 1 к столбцу



Возвращаемся к п. 2.

2'. Находим матрицу смежности двудольного графа



3'. Находим наибольшее паросочетание полученного двудольного графа. Очевидно, паросочетание состоит из элементов , , , с общим весом 4+2+2=8. Это и есть минимальная стоимость работы.




Кирсанов М.Н. 2004

Опечатки исправил Седов А.


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

Продавец Объемы продаж по торговым точкам, USD/тыс. шт
I II III IV V VI
A 68 72 75 - 75 69
B 56 60 58 63 61 59
C 35 38 40 45 25 27
D 40 42 47 45 53 36
E 62 70 68 67 69 70
F 65 63 69 70 72 68

(Назначение первого продавца на четвертую торговую точку недопустимо по медицинским показаниям, т.е. в матрице объемов продаж проставлен запрет- «-». )
Как коммерческий директор должен осуществить назначение продавцов по торговым точкам, чтобы достичь максимального объема продаж?

РЕШЕНИЕ

Экономико-математическая модель задачи.

Переменные:

0, если продавец i не назначен на торговую точку j;
1, если продавец i назначен на торговую точку j.

Целевая функция - распределение продавцов по определенным торговым точкам, для достижения максимального объема продаж

Задачи динамического программирования являются многоэтапным и многошаговым. Рассматриваемая система S находится в некотором начальном стоянии S0 ? S и является управляемой. Система переходит из состояния S0 в состояние Sкон благодяря управлению U. Качество управления U характеризуется соответствующим значением функции W(U).



Система S

Начальное сост. - S0

Конечное сост. - SR

Управление - U

Качество управления - W(U)

Будем считать, что состояние системы S на k-ом шаге (k=1, n) определяется совокупностью чисел X(k)=(x1(k), x2(k), …, xn(k)), которые получены в результате управления uk, обеспечивающего переход системы S из состояния X(k-1) в состояние X(k). При этом будем предполагать, что состояние X(k), в которое перешла система S, зависит от данного состояния X(k-1) и выбранного управления uk и не зависит от того, каким образом система пришла в состояние X(k-1).

Будем считать, что если в результате k-го шага обеспечен определенный доход или выигрыш, также зависящий от исходного состояния системы X(k-1) и выбранного управления uk и равный Wk(X(k-1), uk), то общий доход или выигрыш за n шагов составляет



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

Определение. Под оптимальной стратегией будем понимать совокупность управлений U*=(u1*, u2*, …, un*), в результате реализации которых система S за n шагов переходит из начального состояния X(0) в конечное состояние X(n) и при этом функция принимает наибольшее значение.

Принцип оптимальности Беллмана. Каково бы нибыло состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальный.

Для этого нужно сделать различные предположения о том, как мог окончиться пред-последний шаг, и с учет этого выбрать управление un0, обеспечивающее максимальное зна-чение функции Wn(X(n-1), un). Такое управление, выбранное при определенных предположениях о том, как окончился предыдущий шаг, называется условно оптимальным управлением. Следовательно, принцип оптимальности требует находить на каждом шаге условно оптимальное управление для любого из возможных исходов предыдущего шага.

Fn(X(0)) - максимальный доход, получаемый за n шагов при переходе системы S из начального состояния X(0) в конечное состояние X(n) при реализации оптимальной стратегии управления U*=(u1*, u2*, …, un*), а через Fn-k(X(k)) – максимальный доход, получаемый при переходе из любого состояния X(k) в конечное состояние X(n) при оптимальной стратегии управления на оставшихся n-k шагах. Тогда




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

Определение 1. Ситуация называется конфликтной, если в ней участвуют стороны, интересы которых полностью или частично противоположны.

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

Определение 3. Допустимые действия каждого из игроков, направленные на достижение некоторой цели, называются правилами игры.

Определение 4. Количественная оценка результатов игры называется платежом.

Определение 5. Игра называется парной, если в ней участвуют только две стороны (два лица).

Определение 6. Парная игра называется игрой с нулевой суммой, если сумма платежей равна нулю, т.е. если проигрыш одного игрока равен выигрышу другого.

Далее мы будем рассматривать только игры с нулевой суммой.

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

Определение 8. Стратегия игрока называется оптимальной, если при многократном повторении игры она обеспечивает игроку максимально возможный выигрыш (или, что тоже самое, минимально возможный средний проигрыш).

Пусть имеются два игрока, один из которых может выбрать i-ю стратегию из m возможных стратегий (i=1,m), а второй, не зная выбора первого, выбирает j-ю стратегию из n возможных стратегий (j=1,n) В результате первый игрок выигрывает величину aij, а второй проигрывает эту величину.

Из чисел aij составим матрицу



Строки матрицы A соответствуют стратегиям первого игрока, а столбцы - стратегиям второго. Эти стратегии называются чистыми.

Определение 9. Матрица A называется платежной ( или матрицей игры).

Определение 10. Игру, определяемую матрицей A, имеющей m строк и n столбцов, называют конечной игрой размерности m x n.

Определение 11. Число называется нижней ценой игры или максимином, а соответствующая ему стратегия (строка) - максиминной.

Определение 12. Число называется верхней ценой игры или минимаксом, а соответствующая ему стратегия (столбец) - минимаксной.

Определение 13. Если ?=?=v, то число v называется ценой игры.

Определение 14. Игра, для которой ?=?, называется игрой с седловой точкой.

Для игры с седловой точкой нахождение решения состоит в выборе максиминной и минимаксной стратегией, которые являются оптимальными.

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

Определение 15. Вектор, каждая из компонент которого показывает относительную частоту использования игроком соответствующей чистой стратегии, называется смешанной стратегией данного игрока.

Из данного определения непосредственно следует, что сумма компонент указанного вектора равна единице, а сами компоненты не отрицательны. Обычно смешанную стратегию первого игрока обозначают как вектор U=(u1, u2, ..., um), а второго игрока - как вектор



Если U* - оптимальная стратегия первого игрока, а Z* - оптимальная стратегия второго игрока, то число



является ценой игры.

Определение оптимальных стратегий и цены игры и составляет процесс нахождения решения игры.

Продолжим рассмотрение задачи, состоящей в определении максимального значения функции



Как и при решении сформулированной задачи методом Гомори, первоначально находим симплексным методом оптимальный план задачи без учета целочисленности переменных. Пусть им является план X0. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и Fmax= F(X0).

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

Предполагая, что найденный оптимальный план X0 не удовлетворяет условию целочисленности переменных, тем самым считаем, что среди его компонент есть дробные числа. Пусть, например, переменная xi приняла в плане X0 дробное значение. Тогда в оптимальном целочисленном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу Ki, либо больше или равно ближайшему большему целому числу Ki+1. Определяя эти числа, находим симплексным методом решение двух задач линейного программирования.



Найдем рассмотренным решение задач линейного программирования (I) и (II). Возможен один из четырех случаев:

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

2. Одна из задач неразрешима, а другая имеет оптимальный план среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам (I) и (II).

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

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

4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбираем одну из компонент, значение которой является дробным числом, и строим две задачи, аналогичные (I) и (II).

Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану X0 задачи, а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (I) и (II). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий только целочисленные компоненты, и значение целевой функции на нем окажется больше или равно значения целевой функции в других возможных для ветвлениях вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является оптимальным.


Рассмотрим пример решения задачи о назначениях. Четверо рабочих могут выполнять четыре вида работ. Стоимости сi, выполнения i-м рабочим j-й работы приведены в ячейках диапазона A1:D4.



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

Для решения этой задачи с помощью средства поиска решений отведем под неизвестные диапазон ячеек F2:I5. В ячейку J1 введем целевую функцию

=СУММПРОИЗВ ( F2 :I5 ; Al : D4 )

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



Затем выберем команду Сервис, Поиск решения (Tools, Solver) и заполним открывшееся диалоговое окно Поиск решения (Solver).

Не забудьте в диалоговом окне Параметры поиска решения (Solver) установить флажок Линейная модель (Assume Linear Model). После нажатия кнопки Выполнить (Solve) средство поиска решений найдет оптимальное решение.

Заметим, что флажок Формулы диалогового окна Параметры (Options), открываемого командой Сервис, Параметры (Tools, Options), обеспечивает отображение формул в ячейках, если они там находятся.



Задача о назначениях
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации