15

Размещено на http://allbest.ru

Решение транспортных задач венгерским методом

ВВЕДЕНИЕ

транспортный задача венгерский

Развитие во всем мире компьютерных технологий вызвало появление нового объекта исследований в области управления, получившего название большие, или сложные системы. Одним из самых значительных классов «больших» систем являются системы организационного управления. К ним относятся промышленные предприятия, производственные объединения, отрасли, экономика целого государства, а также глобальные системы (макросистемы).

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

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

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

1. ОБЗОР АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ДАННОГО ТИПА

1.1 Венгерский метод

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

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

Итерация, в свою очередь, состоит из нескольких этапов, которым предшествует разметка:

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

2.Коррекция плана X и невязок путем построения цепочки.

3.Эквивалентные преобразования матрицы C. Итерация начинается первым этапом, а заканчивается вторым, между которыми может производиться несколько третьих.

Алгоритм заканчивается расчетом целевой функции для оптимального плана X.

1.2 Транспортная задача с ограниченными пропускными способностями

Реальное использование методов решения ТЗ на практике может столкнуться с физическими ограничениями на количество единиц товара, перевозимого от i-ого поставщика j-ому потребителю. Указанные ограничения могут быть связаны с лимитами на горючее, грузоподъёмностью транспортных средств, количеством рейсов, массой перевозимого груза в функции от расстояния, полосой частот в каналах связи и т.п. В этих случаях говорится о задачах с ограниченной пропускной способностью коммуникаций.

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

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

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

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

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

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

Отметим еще одну особенность задач транспортного типа [1]: переход от задачи минимизации к задаче максимизации можно выполнить формальным преобразованием вида



1.4 Метод потенциалов

При решении транспортной задачи методом потенциалов первостепенное значение имеют:

1) её сбалансированность;

2) определение начального ОПОРНОГО плана

Опорный план при решении ТЗ имеет такой же вес, как и система базисных векторов в Задачах Линейного Программирования. Для определения опорных планов распространены методы Северо-Западного угла, минимальной стоимости, штрафов (Фогеля). Для применения метода необходима невырожденность опорного плана.

Метод состоит из нескольких шагов:

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

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

3) Итерация, которая состоит из ряда этапов:

- определение коммуникации, вводимой в опорный план;

- построение цепочки по методу вычеркивания;

- коррекция опорного плана и, по необходимости, принятие мер по обеспечению его невырожденности;

- коррекция значения целевой функции;

- - преобразование матрицы C.

2. РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

Основные положения:

1. Существенным нулем матрицы С называется нуль, соответствующая коммуникация которого в плане Х положительна.

2. Элементы матрицы С, находящиеся в выделенных строках и столбцах называются выделенными.

Сам метод состоит из следующих этапов:

- предварительного этапа, на котором вычесляется начальный план;

- итерации, которая состоит из проверки оптимальности и 3-х этапов, которым предшествует разметка.

Этапы:

а) поисковый

б) этап эквивалентных преобразований

в) построение цепочки и коррекция плана

Этапы а) б) могут повторяться не однократно и завершаются итерации этапом в).

На предварительном этапе происходит построение начального плана и определение невязок.

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

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

2) В каждой строке матрицы С' отыскивается минимальный элемент, который вычитается из всех элементов стрки. В результате получается матрица С0.

3) Для нулей матрицы С0 двигаясь по столбцам строится матрица Х0 по известным правилам.

4) Расчитываются невязки по строкам и столбцам и суммарная невязка. По велечине суммарной невязки можно весьма приблизительно определить число итераций до получения оптимального плана. Если получилось, что суммарная невязка равна нулю, то это говорит об оптимуме.

Разметка:

Разметка матрицы С выполняется перед началом итерации и действет до ее окончания. Каждой итерации соответствует новая разметка. На этапе разметки 1-ое: символом "+" отмечаются столбцы с нулевыми невязками. После этого столбцы считаются выделенными.

2-ое: Отмечаются верхней чертой нули матрицы С, соответствующие положительным элементам плана Х. Такие нули называются существенными нулями.

Этапы:

1. Поисковый этап.

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

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

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

2. Этап эквивалентных преобразований.

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

3. Построение цепочки.

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

Выбирается минимальный элемент невязки, строки начала, невязки столбца конца цепочки и элементов плана Х, соответствующих нулям со * в цепочке. Полученный элемент прибавляется ко всем элементам цепочки, которые стоят на местах, соответствующих нулям со штрихом и вычитаются из элементов цепочки, соответствующих нулям со *. Элементы плана Х не вовлеченные в цепочку не меняются

3. ПОСТАНОВКА ЗАДАЧИ

В пунктах A_Jⁱ имеются запасы некоторого продукта, который необходимо перевезти потребителям B_J.

Требуется отыскать такой план перевозок, при котором весь продукт из пунктов А_Jⁱ будет вывезен, потребности потребителей полностью удовлетворены и суммарные транспортные затраты будут минимальны.

Потребности потребителей (В условных единицах), количество продукта (груза) в каждом пункте (В тех же условных единицах) и транспортные затраты на перевозки продукции (груза) из пункта А_Jⁱ и B_J заданы в таблицах.

Таблица 3.1 - Постановка задачи

AJ	B1	B2	B3	B4	Запасы
A1	2	4	5	1	60
A2	2	3	9	4	70
A3	3	4	2	5	20
Потребности	40	30	30	50	150

4. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ

Рассматриваемую в задаче ситуацию можно охарактеризовать следующим образом. Определить суточные объемы перевозок груза каждым из курьеров, доход от реализации с учетом ограничений на количество товара (60;70;20).

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

х₁ - объемы перевозки №1;

х₂ - объемы перевозки №2;

x₃ - объемы перевозки №3;

x₄ - объемы перевозки №4;

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

2x₁ + 4x₂ + 5x₃+ x₄ 60

2x₁ + 3x₂ + 9x₃+ 4x₄ 70

3x₁ + 4x₂ + 2x₃+ 5x₄ 20

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

Таким образом, математическую модель задачи можно записать в следующем виде: определить план X = (x₁, х₂), обеспечивающим минимальное значение функции:

min F(X) = min (40x₁ + 30x₂ + 30x₃+ 50x₄),

2x₁ + 4x₂ + 5x₃+ x₄ 60

2x₁ + 3x₂ + 9x₃+ 4x₄ 70

3x₁ + 4x₂ + 2x₃+ 5x₄ 20

x_i - целое, x_i 0, i=1…4.

5. РЕШЕНИЕ ЗАДАЧИ

5.1 Решение задачи вручную

					ai
	2	4	5	1	60
	2	3	9	4	70
	3	4	2	5	20
Bj	40	30	30	50

Проверяем условие баланса:

а_i = 60 +70+20 = 150;

b_j = 40 +30+30+50 = 150.

Условие баланса выполнено

Рассмотрим матрицу С:

2	4	5	1
2	3	9	4
3	4	2	5

В матрице С в каждом столбце ищем минимальный элемент и вычитаем его из остальных элементов данного столбца. И получаем матрицу C'.

0	1	3	0
0	0	7	3
1	1	0	4

В матрице С' в каждой строке ищем минимальный элемент и вычитаем его из остальных элементов данной строки. И получаем матрицу С_0.

Таблица

0	1	3	0
0	0	7	3
1	1	0	4

Для нулевых элементов С₀, перемещаясь по столбцам, строим матрицу Х₀, корректируя элементы векторов А и В по мере её заполнения:

40	-	-	20	60|20|0
-	30	-	-	70|40
-	-	20	-	20|0
40 0	30 0	30 10	50 30

Ход заполнения

x[1,2] = min{a₂.b₁}=b₁=40,

x[2,2] = min{a₂.b₂}=b₂=30,

x[3,3] = min{a₃.b₃}=a₃=20,

x[3,4] = min{a₁.b₄}=b₄=50.

1-ая итерация

Этап разметки. Отмечаем символом "+" 1-й, 2-й и 4-й столбцы матрицы С₀, а символом "" сверху нули этой матрицы, соответствующие ненулевым элементам плана Х₀, которые являются существенными.

+	+
	1	3
		7	3
1	1		4

Поисковый этап. В невыделенной части матрицы С₀, т.е. в 3-ем столбце и отмечаем невыделенный нуль С[3,3] апострофом Его невязка по строке нулевая. Строку выделим символом «+». В 4-м столбце отмечаем невыделенный ноль С[1,4]. Его невязка по строке нулевая. Строку выделим символом «+».В первом столбце данной строки стоит существенный ноль (), отмечаем его “”, а “+” этого столбца берем в «( )». В 1-м столбце так же находится невыделенный нуль, отмечаем его апострофом. Так как невязка по строке не равна нулю, строку не отмечаем.

(+)	+
*	1	3	'	+
'		7	3
1	1	'	4	+

Этап построения цепочки и коррекции плана.

(+)	+
*	1	3	'	+
'		7	3
1	1	'	4	+

Для коррекции плана выбираем корректирующий элемент . Выбираем его из невязки строки начала цепочки и из невязки столбца конца цепочки.

Коррекция плана:

Прибавляем к элементам , которым в цепочке соответствовал элемент , и отнимем от элементов , которым в цепочке соответствовал элемент .

Получаем новый план Х₁.

10	-	-	50	60|0
30	30	-	-	70|10
-	-	20	-	20|0
40 0	30 0	30 10	50 0

Так как суммарная невязка плана не равна 0 (?0), то переходим ко второй итерации.

2-ая итерация

Этап эквивалентных преобразований.

h=min{3;4}=3. Прибавим его к выделенным плюсом столбцам и отнимем от невыделенных строк, получим матрицу С₁, в которую переносится вся индексация из С₀.

0	1	0	0
0	0	4	3
4	4	0	7

Этап разметки. Отмечаем символом "+" 1-й, 2-й и 4-й столбцы матрицы С₀, а символом "" сверху нули этой матрицы, соответствующие ненулевым элементам плана Х₁, которые являются существенными.

Поисковый этап. В невыделенной части матрицы С₀, т.е. в 3-ем столбце и отмечаем нуль С[3,3] апострофом. В 3-ем столбце отмечаем невыделенный нуль С[1,3] апострофом Его невязка по строке нулевая. Строку выделим символом «+». В 1-й строке в 1-м столбце и в 4-м столбце отмечаем невыделенные нули С[1,1] и С[2,4]. В 1-м столбце 1-й строки стоит существенный ноль (), отмечаем его “”, а “+” этого столбца берем в «( )».

(+)	+		(+)
*	1	0'	*	+
'		4	3
4	4	'	7	+

Этап построения цепочки и коррекции плана.

(+)	+		(+)
*	1	0'	*	+
'		4	3
4	4	'	7	+

Для коррекции плана выбираем корректирующий элемент . Выбираем его из невязки строки начала цепочки и из невязки столбца конца цепочки.

Коррекция плана:

Прибавляем к элементам , которым в цепочке соответствовал элемент , и отнимем от элементов , которым в цепочке соответствовал элемент .

Получаем новый план Х₂.

Так как суммарная невязка плана равна 0 (?0), следовательно, оптимальное решение получено. Переходим к расчету целевой функции.

-	-	10	50	60|50
40	30	-	-	70|0
-	-	20	-	20|0
40 0	30 0	30 0	50 0

Для этого найдем сумму произведений ненулевых элементов плана Х2 на соответствующие им элементы исходной матрицы С:

F=40*2+30*3+10*5+20*2+50*1=190.

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

Рисунок 5.1 - Граф коммуникаций

5.2 Программное решение

Рисунок 5.2 - Входные данные



Рисунок 5.3 - Шаг № 1

Рисунок 5.4 - Шаг № 2

Рисунок 5.5 - Шаг № 3



Рисунок 5.6 - Шаг № 4

Рисунок 5.7 - Шаг № 5

Рисунок 5.8 - Шаг № 6



Рисунок 5.8 - Рисунок 5.9 - Оптимальное решение и значение целевой функции

6. АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ

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

Для данной задачи оптимальный план

-	-	10	50	60|50
40	30	-	-	70|0
-	-	20	-	20|0
40 0	30 0	30 0	50 0

План коммуникаций изображен на рис 5.1. Значение минимальных транспортных издержек составило F=310 у.е.

Выполним анализ модели.

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

Целевую функцию F можно представить в виде суммы

F = ,

где F_i - значения минимальных транспортных издержек, вычисленные по строкам матрицы X_opt.

F₁ = 5*10 + 1*50 =100 у.е.,

F₂ = 40*2+30*3=170 у.е.,

F₃ = 20*2=40 у.е.

Поэтому наиболее выгодно уменьшить объемы передачи продукции в пункте А₂, так как F₂ вносит наибольший вклад в значения целевой функции, увеличивать объемы передачи продукции выгоднее всего в пункте А₃ , так как перевозка продукта из данного пункта стоит дешевле, чем из других пунктов.

Установим ориентировочные, а затем уточненные пределы изменения объема производимого продукта.

Ориентировочные пределы устанавливаются из диапазона 0<max a_i(i=1,3), которые для нашего примера 0 < 70. Значение же , начиная с которого структура решения транспортной задачи изменяется, будет его уточненным верхним пределом.

Решение транспортной задачи будем определять для следующих векторов объема производства:

1) А = (60,70,20),

2) А = (60,65,25),

3) А = (60,60,30),

Остальные условия задачи остаются без изменения. Результаты вычислений показали, что, начиная с вектора А=(60,70,20), структура оптимального решения будет изменяться. Она будет определяться следующим планом

10	-	-	50	60|0
30	30	-	-	60|0
-	-	30	-	30|0
40 0	30 0	30 0	50 0

Оптимальное значение транспортных издержек составит F'=280у.е.. Поэтому уточненный диапазон будет находится в пределах 0 < < 10.

Найдем зависимость оптимального решения и оптимального значения целевой функции от изменений компонент вектора объемов производства.

При последующей проверке на компьютере были получены следующие результаты (рисунок 6.1)



Рисунок 6.1 - Компьютерный эксперимент

Таким образом, с уменьшением объема передачи информации в пункте a₂ на 10 единиц и увеличением на такую же величину объема передачи информации в пункте a₃, транспортные расходы на передачу удается сократить еще на 30у.е. При этом общая стоимость транспортных расходов составит 280у.е.

ЗАКЛЮЧЕНИЕ

На основании решения транспортной задачи и проведения анализа на чувствительность, можно сделать следующие выводы: минимальные затраты на перевозку всех грузов и удовлетворения всех потребностей заказчиков составляют 310 у.е., для уменьшения затрат на перевозки грузов необходимо увеличить емкость склада A₃ и уменьшить емкость склада A_1, при ?=10 транспортные расходы удаётся сократить на 30 условных единиц, при этом достигается оптимальный план перевозок.

Результаты вычислений проверены в программе MIO 2004.

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

Исследование операций./ Дегтярев Ю.И. - М.: Высшая школа, 1986. -320с.

Исследование операций: учебное пособие./ Зайченко Ю.П. - Киев: Вища школа, 1979. -392с.

Математическое программирование в примерах и задачах. / Акулич И.Л. -М.: Высшая школа, 1986. - 317с.

Методические указания к практическим занятиям по дисциплине «Исследование операций и методы оптимизации.» для студентов специальности 07.080401.- «Компьютеризированные системы обработки информации и управления».- Севастополь : Издательство СевГТУ, 1997.- 26с

Размещено на Allbest.ru

...