АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. VIII. Дополнения из самого раннего детства. Разрешение
  2. А теперь мое решение проблемы
  3. А ты? Кому ты доверяешь и что надо, чтобы ты доверял? Кому не доверяешь и почему? На каких критериях основано твое собственное решение о доверии и недоверии? Перечисли их.
  4. А) Решение задачи Коши для ОДУ
  5. автентическое разрешение плагальное разрешение
  6. Аналитическое решение дифференциальных уравнений
  7. АРБИТРАЖНОЕ РЕШЕНИЕ
  8. Архитектурно-конструктивное решение здания.
  9. Б) Решение краевой задачи для ОДУ
  10. БЕСЕДУЮЩИЙ-С-СОЛНЦАМИ. ЛОРАНА ПРИНИМАЕТ РЕШЕНИЕ
  11. В Красноярском крае единый налог на вмененный доход для отдельных видов деятельности устанавливается решением муниципального или районного Совета депутатов каждой территории.
  12. В63. Гомеровский вопрос, его возникновение, развитие и современное решение. «Илиада» и «Одиссея» как исторический источник.

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

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

Алгоритм венгерского метода.

Обозначим через X и Y множество работников и работ соответственно, через m – номер шага в алгоритме.

1. Преобразуем исходную матрицу , таким образом, чтобы в каждой строке и каждом столбце был нулевой элемент. Получим матрицу . После этого шага будем полагать, что m= 1.

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

3. Если это паросочетание является совершенным, то искомое назначение найдено.

4. Если это паросочетание не является совершенным, строим множество вершин Xm и Ym из X и Y, не входящих в паросочетание.

5. Строим новую матрицу , используя значения Xm и Ym . Увеличиваем m на единицу и переходим к п.2.

Реализуем указанный алгоритм на рассматриваемом примере

Преобразование исходной матрицы , в соответствии с п.1 приведено на рис. 4.2. Сначала найдем минимальный элемент в каждой строки и вычтем его из элементов соответствующей строки. Преобразованная матрица расположена в интервале А10:Е14. В результате такого преобразования каждая строка содержит, по крайней мере, один нулевой элемент. Найдем минимальный элемент в каждом столбце и вычтем его из элементов соответствующего столбца. Преобразованную матрицу обозначим , она расположена в интервале Н10:К14. В результате такого преобразования каждый столбец и каждая строка матрицы содержит, по крайней мере, один нулевой элемент.

Рис.4.2

Выполним п.2 алгоритма. Для этого сопоставим матрице двудольный граф, у которого ребра определяются нулевыми элементами (рис.4.3. а). Сопоставим этому двудольному графу паросочетание, изображенное на рис.4.3. б толстыми ребрами. Это сочетание является максимальным, но не является наибольшим.

Рис.4.3

 

Введем в рассмотрение понятие чередующейся цепи.

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

Заметим, что цепь на рис.4.3. б определяемая последовательностью вершин { x 3, y 3, x 4, y 4} является чередующейся. Ребра, соединяющие вершины x 3 и y 3 , а также x 4 и y 4 – тонкие, а ребро y 3 и x 4 – толстое. Поменяем тонкие и толстые ребра в цепи. Получим граф, показанный на рис. 4.3. в, в котором нет чередующейся цепи, поэтому данное паросочетание является наибольшим. Поскольку число толстых ребер равно 3, что меньше числа работников (равно 4), то паросочетание не является совершенным. Переходим к выполнению п.4.

Выделим множества вершин, не входящие в паросочетание. Это Xm = { x 2}, Ym = { y 2}. Составим множества вершин Pm, которые входят в цепи, соединяющие Xm и X (при этом от X к Y можно двигаться по тонким ребрам, в обратном направлении — по толстым.

Pm = { x 2, x 1}, Qm = { y 1}.

Переходим к выполнению п.5. Преобразуем матрицу . Будем рассматривать строки с номерами элементов множества Pm и столбцы с номерами элементов множества Y \ Qm (столбцы, которые не входят в Qm), т.е. в матрице, которая получается путем удаления указанных строк и столбцов (на рис.4.4 удаляемые элементы заштрихованы). Найдем минимальный элемент в не заштрихованной части, он равен двум.

 

Рис.4.4

Продолжим преобразование матрицы (рис.4.5). Из всех элементов первых двух строк вычтем найденный минимальный элемент, равный 2, получим промежуточную матрицу, которая расположена в интервале А25:Е29. Прибавим это же значение равное двум ко всем элементам первого столбца матрицы. Получим матрицу , которая расположена в интервале Н10:К14.

 

Рис.4.5

Переходим к п.2. матрице соответствует свой двухдольный граф, показанный на рис.4.6.а. Для этого графа можно построить паросочетание рис.4.6.б. Поскольку число толстых ребер равно 4, что равно числу станков и работ (равны 4), то паросочетание является совершенным. Т.о. этому совершенному соответствует оптимальное назначение.

Рис.4.6

В соответствии с этим паросочетанием, первую работу x 1 следует выполнять на первом станке y 1, стоимость этой работы 68;

работу x 2 - на станке y 2, стоимость - 60;

работу x 3 - на станке y 3, стоимость - 35;

работу x 4 - на станке y 4, стоимость - 45.

Суммарная стоимость выполненных работ равна 208.

Заметим, что указанное паросочетание является не единственным совершенным. Другое совершенное паросочетание показано на рис.4.6 ., а суммарная стоимость выполненных работ также равна 208.

Решим данную задачу в MS Excel, используя надстройку «Поиск решения». Схема решения этой задачи совпадает с общей схемой решения транспортной задачи линейного программирования, которая была рассмотрена ранее.

Заполним лист MS Excel, как показано на рисунке 4.7. На рис. 4.8. показан тот же лист в режиме отображения формул. Диалоговое окно надстройки «Поиск решения» было заполнено с учетом специфики задачи – искомые переменные являются двоичными переменными (рис.4.8).

Рис.4.7

Рис.4.8

Рис.4.9

Полученное решение приведено на рис.4.7

В соответствии с этим решением, первую работу x 1 следует выполнять на первом станке y 1, стоимость этой работы 68;

работу x 2 - на станке y 4, стоимость - 63;

работу x 3 - на станке y 3, стоимость - 35;

работу x 4 - на станке y 2, стоимость - 42.

Суммарная стоимость выполненных работ равна 208.

Полученное назначение соответствует графу, приведенному на рис.4.6. в.

Задание

Каждый вариант состоит из одного примера.

В цехе предприятия имеются семь универсальных станков С1, С2, С3 … С7, которые могут выполнять 7 видов работ: Р1, Р2, Р3 …. Р7. Каждую работу единовременно может выполнять только один станок, и каждый станок можно загружать только одной работой.

В таблицах 4.2-4.3 даны затраты времени при выполнении станком определённой работы. Определить наиболее рациональное распределение работ между станками, минимизирующее суммарные затраты времени. Значение k задаёт преподаватель.

  1. Решить задачу средствами MS Excel (Надстройка “Поиск решения”).
  2. Решить задачу аналитически.

Отчет должен содержать:

a. Условие задачи.

b.Постановку задачи. Формулировку задачи линейного программирования.

c. Решение задачи на MS Excel с использованием надстройки «Поиск решения»

d.Аналитическое решение задачи о назначении с помощью венгерского метода.

Варианты заданий

Вариант 1

Таблица 4.2

Затраты времени на выполнение работ

  P1 P2 P3 P4 P5 P6 P7
C1              
C2   39+k          
C3              
C4       50+k      
C5              
C6           60+k  
C7             74-k

 

Вариант 2

Таблица 4.3

Затраты времени на выполнение работ

 

  P1 P2 P3 P4 P5 P6 P7
C1             45-k
C2         38+k    
C3     42+k        
C4           54-k  
C5         42+k    
C6              
C7             75-k

 

Библиографический Список

1. Кирсанов М.Н. Графы в Maple. Задачи, алгоритмы, программы: учебное пособие / М. Н. Кирсанов. - М.: Физматлит, 2007. - 168 с

2. Курицкий Б.Я. Поиск оптимальных решений средствами EXCEL 7.0.- СПб.: BHV- СПб., 1997.

3. Резниченко С.С., Подольский М.П., Ашихмин А.А. Экономико-математические методы и моделирование в планировании и управлении горным производством, М., «Недра» 1991.

 


Приложение 1. Паросочетание в двудольном графе

Основные определения. Граф G(V,E) — совокупность двух множеств: вершин V и ребер E, между которыми определено отношение инцидентности. Каждое ребро e из E инцидентно двум вершинам, v0 и v1, которые оно соединяет. При этом вершина v0 и ребро e называются инцидентными друг другу, а вершины v0 и v1 называются смежными. Принято обозначение n — число вершин графа (мощность множества V): |V (G)| = n, и m — число его ребер: |E(G)| = m. В этом случае говорят, что граф G есть (n,m) граф, где n — порядок графа, m — размер графа.

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

Маршрут — последовательность ребер, в которой каждые два соседних ребра имеют общую вершину.

Маршрут в неографе, в котором все ребра разные, — цепь.

Граф связен, если любые две вершины соединены хотя бы одним маршрутом. Число ребер маршрута определяет его длину.

Цепь в графе называется полуэйлеровой (эйлеровой), если она содержит все ребра и все вершины графа.

Ребра, инцидентные одной паре вершин, называются параллельными или кратными.

Граф с кратными ребрами называется мультиграфом.

Ребро (v, v) называется петлей (концевые вершины совпадают).

Граф, содержащий петли (и кратные ребра), называется псевдографом.

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

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

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

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

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

 

 


 

 

СОДЕРЖАНИЕ

 

Введение. 4

ЛАБОРАТОРНАЯ РАБОТА 3. 4

3. Транспортная задача. 4

3.1. Постановка задачи. основные формулы.. 4

3.2. Решение транспортной задачи. 6

3.2.1. Определение исходного опорного решения. 6

3.2.2. Построение оптимального решения. 7

3.2.3. Решение транспортной задачи в MS Excel 16

Задание. 19

Каждый вариант состоит из одного примера. 19

Варианты заданий. 20

ЛАБОРАТОРНАЯ РАБОТА 4. 24

4. Задача о назначениях. 24

4.1. Постановка задачи. основные формулы.. 24

Задание. 34

Варианты заданий. 34

Библиографический список. 35

Приложение 1. Паросочетание в двудольном графе. 36

ё


1 | 2 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.014 сек.)