Решение. Построим математическую модель данной задачи

Построим математическую модель данной задачи.

Вычислим суммарные запасы:

и суммарные потребности: .

Поскольку суммарные запасы и суммарные потребности равны , то это задача закрытого типа.

Построим опорное решение методом «северо-западного» угла.

Для этого заполним ячейку (1,1). Занесем меньшее из чисел a₁ и b₁, т.е. x₁₁ = min{ a₁; b₁ }= min{ 90; 30 } =30 и т.д. (рис.3.4).

В результате имеем таблицу с шестью заполненными клетками, что соответствует теории: m+n-1 =3+4-1=6.

Рис.3.4. Опорное решение, построенное методом «северо-западного» угла.

Заметим, что суммарная стоимость перевозок равна

.

Рассчитаем систему потенциалов для этого решения.

Для определения ; имеем следующую систему уравнений:

Имеем 6 уравнений и 7 неизвестных. Значение одной из неизвестных величин (любой!) можно задать произвольным образом (любое число). Положим U₃ равным 0. Тогда остальные величины будут равны:

U₁=1_, U₂= -1_, V₁= 8_, V₂= 7_, V₃= 4_, V₄= 6 _.

Припишем значения потенциалов соответствующим строкам и столбцам. Введем дополнительный столбец U_i и дополнительную строку V_j (рис.3.5) и занесем вычисленные значения потенциалов в полученные клетки.

Рис. 3.5. Транспортная таблица с вычисленными значениями потенциалов

Вычислим значения невязок для всех клеток без перевозок по формуле (3.7). Запишем их в правый верхний угол каждой клетки (жирный курсив). В ряде клеток (2,1), (2,3), (2,4) и (3,1) наблюдаются нарушения (невязки больше нуля). Выберем клетку (2,4), в которой наблюдается наибольшее превышение, равное 4. Построим замкнутый цикл с началом в этой клетке. В качестве остальных вершин выберем клетки (3,4), (3,2) и (2,2). Пронумеруем клетки (рис.3.4).

Нечетные вершины (2,4) и (3,2) образуют положительную полуцепь. Четные вершины (3,4) и (2,2) образуют отрицательную полуцепь. Величина q = min{90;130}=90.

Вычислим новые значения для узлов контура. В четных вершинах значения уменьшаются на q=90, в клетке (2,2) значение перевозки станет равным 90-q = 0; в клетке (3,4) - равным 130 -q = 130-90 = 40. В нечетных вершинах значения увеличатся на q=90, так в клетке (3,4) значение равно 0+q=0+90=90, а в клетке (3,2) значение равно 50+q=50+90=140.

Получим новое опорное решение (рис.3.6).

Рис. 3.6

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

.

Уменьшение стоимости перевозок по сравнению с начальным планом составило F₀ - F₁=2700 - 2340= 360.

Теоретически это уменьшение равно (q умножить на соответствующее превышение), т.е. те же 360 (произведение 90 на 4).

Рассчитаем новую систему потенциалов.

Для определения ; имеем следующую систему уравнений:

Имеем 6 уравнений и 7 неизвестных. Значение одной из неизвестных величин (любой!) можно задать произвольным образом (любое число). Положим U₃ равным 0. Тогда остальные величины будут равны

U₁=1_, U₂=3_, V₁=8_, V₂=7_, V₃=4_, V₄=6 _.

Припишем значения потенциалов соответствующим строкам и столбцам в столбец U_i и строку V_j (рис.3.6).

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

Нечетные вершины (3,1) и (1,2) образуют положительную полуцепь. Четные вершины (1,1) и (3,2) образуют отрицательную полуцепь. Величина q = min{30;140}=30.

Вычислим новые значения для узлов контура.

В четных вершинах значения уменьшается на q=30: в клетке (1,1) значение перевозки станет равным 30-q=0; в клетке (3,2) - равным 140 - q=140-30=110.

В нечетных вершинах значения увеличатся на q: в клетке (3,1) значение станет равным 0+q=0+30=30, а в клетке (1,2) - 60+q=60+30=90.

Получим новое опорное решение (рис.3.7).

Рис.3.7

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

.

Уменьшение стоимости перевозок по сравнению с предыдущим планом составило F₁ -F₂ = 2340 – 2250 = 90.

Теоретически это уменьшение равно (q умножить на соответствующее превышение), т.е. те же 90 (произведение 30 на 3).

Рассчитаем очередную систему потенциалов для полученного опорного решения. Для определения ; имеем следующую систему уравнений:

Имеем 6 уравнений и 7 неизвестных. Положим U₃ = 0, тогда остальные величины будут равны

U₁=1_, U₂=3_, V₁=5_, V₂=7_, V₃=4_, V₄=6_.

Запишем значения потенциалов соответствующим строкам и столбцам в столбец U_i и строку V_j (рис. 3.6).

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

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

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

Заполним лист MS MS Excel, как показано на рисунке 3.8. На рисунке 3.9. показан тот же лист в режиме отображения формул.

Рис.3.8.

Рис.3.9.

Далее заполняем диалоговое окно надстройки «Поиск решения» (рис.3.10).

Рис.3.10.

Результат решения приводится на рис.3.11.

Рис.3.11

 

Оптимальные объемы перевозок содержатся в интервале ячеек В13:Е15. Заметим, что результаты полностью совпадают с результатами, полученными ранее методом потенциалов.

 

Задание

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

Имеется четыре карьера, производящих строительные материалы, и четыре потребителя сырья строительных материалов. Известны объемы производства на каждом карьере, потребности в их продукции каждого из потребителей, а также стоимость перевозки 1 т продукции с i -го карьера к j -му потребителю. Определить, при каких объемах грузоперевозок от i -го поставщика к j -му потребителю суммарная стоимость перевозок будет минимальной.

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

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

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

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

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

4). Аналитическое решение транспортной задачи:

· определение исходного опорного решения;

· построение оптимального решения методом потенциалов.

 

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

Вариант 1

Поставщик	Потребители	Запасы
Потребность

Вариант 2

Поставщик	Потребители	Запасы
Потребность

Вариант 3

Поставщик	Потребители	Запасы
Потребность

Вариант 4

Поставщик	Потребители	Запасы
Потребность

Вариант 5

Поставщик	Потребители	Запасы
Потребность

 

 

Вариант 6

Поставщик	Потребители	Запасы
Потребность

 

Вариант 7

Поставщик	Потребители	Запасы
Потребность

Вариант 8

Поставщик	Потребители	Запасы
Потребность

 

Вариант 9

Поставщик	Потребители	Запасы
Потребность

Вариант 10

Поставщик	Потребители	Запасы
Потребность

 

Вариант 11

Поставщик	Потребители	Запасы
Потребность

Вариант 12

Поставщик	Потребители	Запасы
Потребность

 

Вариант 13

Поставщик	Потребители	Запасы
Потребность

Вариант 14

Поставщик	Потребители	Запасы
Потребность

 

Вариант 15

Поставщик	Потребители	Запасы
Потребность

 

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

4.ЗАДАЧА О НАЗНАЧЕНИЯХ

 

Цель работы:

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

 

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

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

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

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

Суммарная стоимость при данном варианте назначения работников на работы выразится суммой: .

Таким образом, математическая модель задачи о назначениях будет такой:

	(4.1)
	(4.2)
	(4.3)

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

Эта задача имеет простую геометрическую интерпретацию, показанную на рис.(4.1). На нем изображен граф, у которого вершины слева обозначают работников, а вершины справа изображают работы. Вершины соединены ребрами с указанием их веса, при этом вес равен стоимости соответствующей работы.

 

Рис.4.1

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

Паросочетанием неориентированного графа G называется подмножество M его ребер E, выбранное так, что никакие два ребра из M не являются смежными, т.е. не имеют общей вершины. В терминах нашей задачи синонимом этому будет «назначение», чтобы каждый задействованный работник взял на себя отдельную работу. И не получилось такого, что два работника выполняет одну работу, или один работник отвечал за две работы.

Она является частным случаем задачи нахождения совершенного паросочетания (см.приложение).

Решение этой задачи может быть получено венгерским методом. Алгоритм был разработан и опубликован Гарольдом Куном (Harold Kuhn) в 1955 г. Сам Кун дал алгоритму название "венгерский", потому что он был в значительной степени основан на более ранних работах двух венгерских математиков: Денеша Кёнига (Dénes Kőnig) и Эйгена Эгервари (Jenő Egerváry). Основную идею метода рассмотрим на примере.

 

 

Пример

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

В таблице 4.1 даны затраты времени при выполнении станком определённой работы. Определить наиболее рациональное распределение работ между станками, минимизирующее суммарные затраты времени.

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

Решение:

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

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

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

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

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

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

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

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

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

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

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

Рис.4.2

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

Рис.4.3

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

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

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

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

P_m = { x ₂, x ₁}, Q_m = { y ₁}.

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

Рис.4.4.

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

Рис.4.5.

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

Рис.4.6.

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

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

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

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

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

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

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

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

Рис.4.7.

Рис.4.8.

Рис.4.9.

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

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

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

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

работу x ₄ - на станке y ₂, стоимость - 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 Затраты времени на выполнение работ

Вариант 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

СОДЕРЖАНИЕ

Введение. 4

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

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

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

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

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

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

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

Задание. 22

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

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

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

4.ЗАДАЧА О НАЗНАЧЕНИЯХ.. 26

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

Задание. 37

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

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