Этап первый

Если все коэффициенты строки целевой функции (исключая свободные члены) неположительные, то полученное ДБР является оптимальным. Таким образом, по коэффициентам элементов целевой функции можно определить достигнуто ли оптимальное решение. Если не все элементы строки целевой функции неотрицательны,то необходимо продолжить преобразования. И в качестве разрешающего элемента выбирается столбец с положительным коэффициентом в строке целевой функции. Для определения будем выбирать столбец с max коэффициентом. Для обеспечения перехода к новому ДБР дающему меньшее значение целевой функции в качестве разрешающей строки, как и при поиске ДБР строка выбирается по min для разрешающего столбца симплексному отношению.

Алгоритм поиска оптимального решения.

1)Анализ коэффициентов строки целевой функции.

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

2)Анализ ограниченности целевой функции.

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

3)Выбор разрешающего столбца.

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

4)Выбор разрешающей строки.

Для выбранного разрешающего столбца составляются симплексные отношения (0). Строка, для которой эти отношения min выбирается в качестве разрешающей.

5)Замена переменных.

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

Лекция 9. РЕШЕНИЕ ЗАДАЧИ СО СМЕШАННЫМИ ОГРАНИЧЕНИЯМИ.

Пусть задача имеет смешанные ограничения.

Исходная задача (1):

На предварительном этапе ищется какое-либо базисное решение.

Исходная задача (1) сводится к основной задаче линейного программирования. Для этого введем дополнительные переменные

Получим задачу (2):

Выбираем в качестве базисных переменных

Введем вспомогательную функцию Z (4).

Минимальное значение функции Z будет равно 0, тогда и только тогда, когда все

Необходимо решить вспомогательную задачу, т.е.минимизировать функцию Z (4).

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

замены переменных, вывести искусственные переменные

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

1.Z=0,т.е. получено базисное решение и можно переходить к поиску допустимого решения;

2.Z>0,т.е. система ограничений противоречива и задача не имеет решения.

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

После того как какая-то искусственная переменная выведена из числа

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

который должна вводиться, вычеркивается из таблицы.

Вычислительные аспекты симплексного метода.

1.Контроль вычисления при преобразовании симплексной таблицы.

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

ошибки при вычислении в ручную и ошибки при расчетах на ЭВМ. Поэтому необходимо контролировать результаты вычисления.

Разработано несколько алгоритмов контроля, рассмотрим один из них.

алгоритм контроля вычисления.

В симплексную таблицу добавляются 2 столбца-столбцы контрольных сумм. В

первом столбце записывается в верхней части клетки,а внижней -

А во второй столбец -

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

-для элементов разрешающей строки

- сумма всех элементов строки за исключением элемента, расположенного в разрешающем столбце и “+1”;

-для всех остальных элементов эта сумма равна сумме всех элементов,кроме элемента разрешающего столбца;

-2- Осуществляется симплексное преобразование элемента,т.е. по тем же правилам, что и над остальными элементами таблицы. Полученное значение записывается в нижнюю часть клетки.

Получаем

-3- В преобразованной таблице находятся значения.Значения

равны сумме преобразованных значений строки, за исключением элемента

-4- Для каждой строки попарно сравниваются элементы

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

2.Разрешение проблемы “зацикливания”.

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

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

ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ.

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

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

ПРЯМАЯ ЗАДАЧА

ДВОЙСТВЕННАЯ К НЕЙ ЗАДАЧА

Говорят, что двойственная задача развернута на 90 градусов по отношению к прямой.

ВЫВОД.

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

2. В прямой задаче функция максимизируется, а в двойственной – минимизируется.

3. Коэффициенты целевой функции двойственной задачи – свободные члены ограничений прямой задачи.

4. В прямой задаче ограничения имеют знак «£», в двойственной «³».

5. Свободные члены в ограничении двойственной задачи – коэффициенты целевой функции прямой задачи.

ПРИМЕР.

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

Связь между парой двойственных задач устанавливает ТЕОРЕМА ДВОЙСТВЕННОСТИ.

ТЕОРЕМА ДВОЙСТВЕННОСТИ.

Пусть имеется пара двойственных задач (1) и (2). Тогда:

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

-2- если по одной из задач целевая функция не ограничена, то двойственная ей задача противоречива.

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

Будем называть расширенной прямой задачей следующую задачу:

Лекция 10. Двойственный симплексный метод.

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

Рассмотрим 2 задачи:

Первая задача: ПРЯМАЯ ЗАДАЧА.

;

i=1,m; ; j=1,n.

Двойственная задача:

Запишем расширенную задачу к задаче :

=

Утверждение 1.

(Признак оптимальности псевдоплана)

Если среди компонент псевдоплана Х нет отрицательных, т.е. Х0, i=, то псевдоплан является оптимальным решением задачи (3).

Свяжем с каждым Бматрицу . Б={A, A, …, A}, где
- коэффициенты разложений векторов Aпо базису Б. Т.е. A=, j.

Утверждение 2.

(Признак отсутствия решения задачи)

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

Утверждение 3.

Если среди компонент псевдоплана Х имеются отрицательные и для каждой Х<0 существует номер j, для которого <0, то можно перейти к новому плану, для которого значение функции f лучше. Для этого нужно получить новый сопряженный базис. Т.е. исключить из числа базиса какой-то вектор и ввести новый вектор.

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

1. По исходной задаче формируется прямая задача (1).

2. По прямой задаче (1) формируется двойственная задача (2).

3. Формируется расширенная задача задачи (1) – задача (3).

4. Нахождение сопряженного базиса.

Для нахождения Бопределяется набор векторов {A, A, …, A}, которые должны входить в базис. Множество индексов базисных векторов I= {i,i,…, i}. Количество векторов, входящих в базис, равно количеству ограничений в задаче (3), т.е. = m. Для нахождения базиса необходимо из общего количества векторов: n+m выбрать произвольно m.

Для того, чтобы убедиться, что эти вектора составляют базаис, необходимо решить систему уравнений:

, i.

В результате решения этой системы получаем значения z, которые необходимо подставить в ограничения двойственной задачи (2): , z0.

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

5. Определение псевдоплана.

По найденному базису Бнаходятся значения переменных х, х, …, х, которые называются псевдопланом. Количество переменных равно m. Обозначим эти переменные через

6. Нахождение коэффициентов разложения aij

Для нахождения aij необходимо решить систему уравнений:

Aj=Σai * αij j Є I/Iб

В результате решения системы получим значения aij

Если окажется, что для некоторого Xi0 < 0 все aij >= 0,то задача не имеет решения (см. Утверждение 1). Иначе

7. Предположим, что первые m векторов составляют базис (для простоты). Заполним таблицу 1.

Таблица 1

Базис		Псевдо план	C1	C2	C3	…	Cm	…	Cn+m
A A1	A2	A3	…	Am		An+m
A1	C1	X10				...			αn+m
A2	C2	X20				...			αn+m
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
Am	Cm	Xm				...		…	αn+m
∆	-	-	-	-	-	-	-	…	∆n+m
Ǿ								…

∆0 = Σci * Xi i Є Iб

Δj = Σci * αij -Cj i Є Iб jЄI/Iб

8. Определяется разрешающая строка и разрешающий столбец.

Сначала определяем вектор Ar, который необходимо вывести из базиса, т. е. Определяется строка. Для этого в таблицу 1 среди элементов столбца Xi0 выбирается минимальный среди отрицательных элемент. Эта строка объявляется разрешающей.

Если в какой-то строке с отрицательным значением Xi0 все элементы этой строки положительны и не равны нулю, то задача не имеет решений (см. Утверждение 2).

Определяем вектор As, который должен быть введен в базис вместо Ar. Для этого в r-ой строке среди элементов, соответствующих небазисным векторам, находится множество отрицательных элементов αij <0, затем заполняется строка Q.

Значения этой строки:

Qj = - Δj\αrj j Є I/Iб

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

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

αij(k) – αrj(k) * αis(k)\αrs(k), i <>r

Αij(k+1) =

αij(k)\αrs(k), i = r

Элементы столбца Xi0 вычисляются по этой же формуле.

Замечание: После преобразования таблицы, в базис записывается вектор As, но Ar в верхнюю часть таблицы не записывается.

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

Лекция 11. Транспортные задачи.

Транспортная задача является одной из специальных задач линейного программирования. Она является одной из самых распространенных задач (70% от всех) линейного программирования.

Концептуальная постановка транспортной задачи.

Имеется m пунктов отправлений (поставщики) A1 … Am.

В каждом из этих пунктов сосредоточено a1…am единиц запасов однородного груза.

Имеется n пунктов назначения (потребители) B1 … Bn.

В каждый из этих пунктов необходимо доставить соответственно b1 … bn единиц груза.

Известна стоимость перевозки и доставки единицы груза из каждого пункта отправления, в каждый пункт назначения - Cij. Где Cij – стоимость доставки единицы груза из пункта Аi в пункт Вj.

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

Геометрическая интерпретация:

Если общая потребность груза равна общим запасам груза в пункте отправления, т.е.

Sai = Sbj (*)

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

Как можно несбалансированную задачу привести к сбалансированной?

Рассмотрим несбалансированную задачу, т.е.

Sаi ¹ Sbj

Нарушение баланса может быть двух видов: Sai > Sbj и Sai < Sbj.

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

В этом случае вводится фиктивный потребитель Bn+1. Его потребность составит: bn+1 = Sai - Sbj

Рассмотрим второй случай.

В этом случае вводится фиктивный поставщик Ai+1 и его запасы составят: ai+1=Sbj - Sai.

Стоимость перевозки в обоих случаях будет равна 0. Таким образом несбалансированная задача стала сбалансированной.

Математическая постановка задачи.

Обозначим через Хij – количество единиц груза перевозимого из пункта Ai в пункт Bj.

Тогда стоимость перевозки из Ai в Bj будет равна Cij * Xij.

Стоимость перевозки из пункта A1 во все остальные будет равна S Cij * Xij.

Со всех во все: F=SSCij * Xij ®min (1)

Ограничения:

SXij = ai, i=1,m

SXij = bj, j=1,n (2)

Xij > 0

Таким образом, имеем такую математическую постановку: Найти такое минимальное значение функции (1), при котором выполняются ограничения (2).

Анализ задачи оптимизации и выбор метода оптимизации.

Данная задача – задача линейного программирования. Как и любую задачу линейного программирования, ее можно решить любым из методов линейного программирования, но особенности постановки позволяют решить ее более простым методом. Особенности задачи:

- все коэффициенты в ограничениях равны 1;

- каждая переменная входит только в 2 ограничения;

- общее количество переменных равно m + n;

Однако если учитывать, что данная задача сбалансированная, то используя условие (*), можно убедиться, что число переменных равно m + n – 1. Следовательно, число базисных переменных в задаче равно m + n – 1, а число свободных переменных равно (n - 1)(m – 1). Свободные переменные равны 0, следовательно, в оптимизационном решении (n - 1)(m - 1)=0.

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

Если число базисных переменных в допустимом плане равно m + n – 1, то такой план будем называть невырожденным (опорным) планом.

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

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

Доказательство:

Докажем, что транспортная задача имеет решение. Пусть Sai =Sbj = M. Тогда докажем, что

Xij=ai *bj / M является решением. Просуммируем обе части уравнения:

SXij = Sai*bj / M = ai*Sbj / M = ai * M/M =ai SXij =ai

SXij =Sai*bj / M = bj*Sai/ M = bj * M/M =bj SXij =bj,

т.к. Хij=ai*bj/M > 0, то это удовлетворяет системе ограничений, а это значит, что Xij является решением.

Покажем, что транспортная задача имеет оптимальное решение.

Нужно показать, что функция F=SSCij Xij ®min ограничена. Выберем из всех Cij наименьшее и обозначим его С1, т.е. С1=min Cij. Далее заменим в функции все Сij на С1, тогда будем иметь:

F=SSСij*Xij >C1SSXij = C1SSai = C1SSbj = C1*M

Выберем из всех Сij максимальное, т.е. C2=maxCij. Тогда SSCij*Xij £C2*M. Таким образом, мы установили, что функция F ограничена на множестве решений: C1 £ F £ C2*M. Следовательно, любая транспортная задача имеет оптимальное решение.

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

Транспортные задачи могут быть решены 2 группами методов:

- распределительным методом, методом потенциалов, дельта-методом – требуют построения некоторого опорного плана и затем построение оптимального плана;

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

Построение оптимального плана:

Существует несколько методов построения опорного плана. Построение опорного плана проводится на транспортной таблице. Эта транспортная таблица имеет вид:

	В1	B2	...	Bj	...	Bn-1	Bn	Запасы ai
A1	C11 X11	C12 X12	...	C1j X1j	...	C1n-1 X1n-1	C1n X1n	a1
A2	C21 X21	C22 X22	...	C2j X2j	...	C2n-1 X2n-1	C2n X2n	a2
...	...	...		...		...	...	...
Ai	Ci1 Xi1	Ci2 Xi2	...	Cij Xij	...	Cin-1 Xin-1	Cin Xin	ai
Am	Cm1 Xm1	Cm2 Xm2	...	Cmj Xmj	...	Cmn-1 Xmn-1	Cmn Xmn	am
Потребности bj	b1	b2	...	bj	...	bn-1	bn

Необходимо расставить в клетках Х11 – Хmn груз, но некоторые клетки будут отличны от нуля. Число таких клеток будет равно: m+n-1. Будем называть клетки, в которых расположены Х>0, базисными, а незаполненные клетки - свободными. Если число базисных клеток равно: m+n-1, то план называется невырожденным.

Метод северо-западного угла (диагональный).

Заполнение таблицы начинается с верхнего левого угла и далее заполнение идет вдоль диагонали. Заполнение заканчивается в клетке (mn).

Алгоритм:

1. Значение базисной переменной Х11 полагают равной наименьшему из ai и bj. Здесь возможны 3 случая:

ai >bj; ai<bj; ai=bj, в зависимости от которых осуществляется переход на 2, 3, 4 этап соответственно. Если X11=a1, то переход на этап 2; X11=b1 – переход на этап 3 и т.д.

2. Находим величину неудовлетворенного спроса b1* = b1-a1 и переходим к клетке (2)(1).В нее записываем: X21=min(a2,b1*).

Вместо b1 используем b1*, все элементы (оставшиеся) строки заполняются 0 и переходим к клетке (2)(1). Переход на пункт 1. Вместо клетки (1)(1) теперь используется - (2)(1).

Лекция 12. МЕТОД НАИМЕНЬШЕЙ СТОИМОСТИ.

ИДЕЯ: В транспортной таблице отыскивается клетка с наименьшей стоимостью Cij. В эту клетку помещаются наименьшие из чисел ai, bj. Оставшиеся элементы либо строки, либо столбца, либо и строки и столбца заполняются нулями. Из оставшейся не заполненной таблицы опять выбирается клетка с наименьшей стоимостью. Для неё повторяется процедура заполнения таблицы.

АЛГОРИТМ МЕТОДА.

1. В качестве первой базисной клетки берется клетка с наименьшей стоимостью Cij. Тогда в эту клетку записывается число Xij = m:n{ai,bj}.

Здесь возможно три случая:

- ai < bj в этом случае i-ая строка, за исключением элемента (i,j), заполняется нулями и вычисляется величена неудовлетворенной заявки для пункта Bj:

bij=bj-ai

Переход на пункт 2.

- Если ai > bj, тогда j-ый столбец, строка, за исключением элемента (i,j), заполняется нулями и находится величина неизрасходованного запаса пункта Ai

aij=ai-bj

Переход на пункт 2.

- Если ai = bj, то все элементы i-ой строки и j-ого столбца заполняется нулями за исключением элемента (i,j).

Переход на пункт 2.

2. Проверяется все ли клетки таблицы заполнены. Если да, то конец алгоритма, если нет – переход на пункт 1.

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

НАХОЖДЕНИЕ ОПТИМАЛЬНОГО ПЛАНА ТРАНСПОРТНОЙ ЗАДАЧИ.

После того, как один из методов построен, невырожденный опорный план можно переходить к построению оптимального плана:

1. Распределительный метод.

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

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

ПРИМЕР:

_ +

- +

- +

_{+ -}

_­Означенным циклом называется цикл, вершинам которого последовательно переписаны знаки «+» или «-» по следующему правилу: любой начальной вершине приписывается «+», соседней вершине «-», следующей «+» и т.д.

СВОЙСТВА ОЗНАЧЕННОГО ЦИКЛА.

В каждой строке (столбце) количество вершин со знаком «+» равно количеству вершин со знаком «-».

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

СВОЙСТВА ЦИКЛА ПЕРЕСЧЕТА.

Для невырожденного плана, для каждой свободной клетке существует один и только один цикл пересчета.

Сдвигом по циклу перевозки k единиц называется увеличение величина перевозки на k единиц, если вершина помечена знаком «+» и уменьшение на k единиц, если вершина помечена знаком «-».

СВОЙСТВА СДВИГА ПО ЦИКЛУ.

- сдвиг по циклу k единиц не нарушает допустимого плана транспортной задачи;

- сдвиг по циклу изменяет стоимость плана.

Ценой цикла называется алгебраическая сумма стоимостей, входящих в вершины цикла, причем стоимости, расположены в клетках, помеченные «+» берутся также со знаком «+», а стоимости для клеток с «-» берутся также со знаком «-».

СВОЙСТВА ЦЕНЫ ЦИКЛА.

Цена цикла – это стоимость сдвига по циклу груза в одну единицу.

РАСПРЕДЕЛИТЕЛЬНЫЙ МЕТОД НАХОЖДЕНИЯ ОПТИМАЛЬНОГО ПЛАНА.

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

АЛГОРИТМ.

1. Последовательно для свободных клеток строятся циклы пересчета и определяется их цена.

Предположим для какой-то клетки Xij цена цикла <0, тогда переходим на пункт 2. Если все цены цикла >0, то конец алгоритма.

2. Определяем величину сдвига k. Она определяется из условия, что сдвиг по циклу не должен привести к появлению отрицательного значения перевозок. Количество едениц груза, которое можно переместить по циклу, определяется минимальным значением перевозок, расположенных в клетках с отрицательными вершинами цикла: k=m:n Xpr для любых pr, имеет отрицательную вершину цикла:

k = min {Xil, Xkj}.

Переход на пункт 3.

3. Осуществляется сдвиг по циклу груза k. Получаем новый опорный план, стоимость которого уменьшилась на величину произведения k и цены цикла. Переход на пункт 1.

Лекция 13. Венгерский метод решения транспортных задач.

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

Пусть имеется транспортная задача:

A=() – запасы;

B=() - потребности;

- матрица стоимостей перевозок;

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

;

1. Будем называть и соответствующими, если они имеют одинаковые индкексы.

2. Элементы матрицы С называются выделенными, если они расположены в столбцах или строках, помеченных знаком < + >.

3. Нуль матрицы С называется выделенным, если он помечен либо как < > либо как < >.

4. Нуль матрицы С называется существенным, если он расположен в столбце, помеченным < + >, и кроме того сответствующий ему элемент матрицы Х не равен нулю.

5. Цепочкой матрицы С называется совокупность из выделенных нулей (помеченных < ’ > или < * >), причём цепочка всегда начинается с < > затем < >, затем < >…….. На нечетных местах - < >, а на чётных –

< >.

-----

|

-----

|

6. Невязкой по строке i в матрице Х называется разность между запасом в пункте и распределённым из этого пункта грузом , i=1..m.

7. Невязкой по столбцу j в матрице Х называется разность между потребностью пункта и полученным распределённым грузом в этот пункт , j=1..n.

8. Суммарной невязкой называется сумма всех невязок по строчкам и по столбцам .

9. Элементарным эквивалентным преобразованием в матрице С называется одновременное прибавление (вычитание) ко всем элементам одной строки или одного столбца некоторого числа. Матрица , построенная в ходе такого преобразования – эквивалентна матрице С. Решения на эквивалентных матрицах совпадают.

Идея:

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

ПРЕДВАРИТЕЛЬНЫЙ ЭТАП:

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

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

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

3. По матрицеформируется матрица . В этой матрице полагаются равными нулю , для которых соответствующие элементы не равны нулю. , . Остальные элементы матрицы находятся метолом северо-западного угла.

Далее вычисляются невязки в по строкам и столбцам и вычисляется суммарная невязка . При этом может оказаться, что полученный план является недопустимым (,). План недопустим, если не равно нулю. Если , то полученный план является оптимальным. Если , то переходим к первой итерации. Допустим, проведено k итераций. На каждой итерации вычислялась невязка . И после проведения k итераций . В этом случае необходимо, используя матрицы и провести (k+1) итерацию. Перед началом итерации выделяются знаком <+> те столбцы матрицы , для которых невязка по столбцу равна нулю, т.е. .

1. Просматриваются, невыделенные знаком <+> столбцы матрицы . В них отыскиваются не выделенные знаком <’> нули. Если таких нулей нет, то переход к этапу 3. Если такой нуль найден, он отмечается знаком <’> и определяется невязка по строке в , в которой находится этот ноль. Если невязка этой строки больше нуля, то переход на этап 2. Если невязка равна нулю, то в матрице эта строка помечается <+>.

2. В выделенной строке ищется существенный ноль. Если он есть, то он помечается знаком <*>, а знак <+> над соответствующим столбцом матрицы аннулируется (отмечается ).

3. В этом столбце ищется невыделенный ноль, расположенный в строке, не помеченной <+>. Если такой ноль есть, он помечается <’>, а соответствующая строка помечается <+>. Далее определяется невязка этой строки. Если она больше нуля (), то переход на этап 2, если , то в этой строке ищется существенный ноль. Далее процесс выделения нулей может закончиться одним из двух исходов:

· Найден , для которого невязка по строке равна нулю. В этом случае переход к этапу 2.

· Все нули матрицы оказались выделенными, причём для всех невязки по строкам равны нулю.

Дата добавления: 2014-01-07