Контрольная работа Постановка и основные свойства транспортной задачи

Работа добавлена на сайт bukvasha.net: 2015-10-25

Поможем написать учебную работу

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

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Принимаю Политику конфиденциальности

Скидка 25% при заказе до 23.11.2024

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

Транспортная задача (Т-задача) является одной из наиболее распространенных специальных задач ЛП. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О.Н. Толстым [18; 59].

Первая строгая постановка Т-задачи принадлежит Ф. Хичкоку, поэтому в зарубежной литературе ее называют проблемой Хичкока.

Первый точный метод решения Т-задачи разработан Л.В. Канторовичем и М.К. Гавуриным.

Постановка Т-задачи. Пусть в пунктах А₁,…,A_m производят некоторый однородный продукт, причем объем производства в пункте A_i составляет a_i единиц, i = 1,…, m. Допустим, что данный продукт потребляют в пунктах B₁., B_n, a объем потребления в пункте В_j составляет b_j одиниць j = 1., n. Предположим, что из каждого пункта производства возможно транспортировка продукта в любой пунктпотребления. Транспортные издержки по перевозке единицы продукции из пункта A_i в пункт В_j равны c_ij (i = 1., m; j = 1., n). Задача состоит в определении такого плана перевозок, при котором запросы всех потребителей В_j полностью удовлетворены, весь продукт из пунктов производства вывезен и суммарные транспортные издержки минимальны.

Условия Т-задачи удобно представить в виде табл. 1.1.

Таблица. 1.1.

Пункт потребления Пункт производства	B₁	B₂	.	B_n	B_j a_i
A₁	C₁₁	C₁₂	.	C_1n	a₁
A₂	C₂₁	C₂₂	.	C_2n	a₂
A_m	C_m1	C_m2	.	C_mn	a_m
A_i b_j	b₁	b₂	.	b_n	Объем производства Объем потребления

Пусть количество продукта, перевозимого из пункта A_i в пункт В_j.

Требуется определить множество переменных , i = 1., m, j = 1., n, удовлетворяющих условиям
(1.1)

(1.2)
и таких, что целевая функция
(1.3)
достигает минимального значения.

Условие (1.1) гарантирует полный вывоз продукта из всех пунктов производства, а (1.2) означает полное удовлетворение спроса во всех пунктах потребления.

Таким образом, Т-задача представляет собой задачу ЛП с числом переменных, и (m + n) числом ограничений равенств.

Переменные удобно задавать в виде матрицы
(1.4)
Матрицу X, удовлетворяющую условиям Т-задачи (1.1) и (1.2) называют планом перевозок, а переменные – перевозками. План , при котором целевая функция минимальна, называется оптимальным, а матрица С= – матрицей транспортных затрат.

Графический способ задания Т-задач показан на рис. 1

Рис. 1
Отрезок A_iB_j называют коммуникацией. На всех коммуникациях ставят величины перевозок x_ij.

Вектор P_ij, компоненты которого состоят из коэффициентов при переменных x_ij в ограничениях (3.1.1) и (3.1.2), называют вектором коммуникаций:

Вводят также вектор производства-потребления P₀, где
.
Тогда ограничение (3.1.1) и (3.1.2) можно записать в векторной форме

, (1.5)

Свойства транспортной задачи

1. Для разрешимости Т-задачи необходимо и достаточно, чтобы выполнялось условие баланса
, (1.6)
то есть, чтобы суммарный объем производства равнялся объему потребления.

Доказательство. Пусть переменные x_ij, i = 1., m; j = 1., n удовлетворяют условиям (1.1), (1.2). Суммируя (1.1) по , а (1.2) по , получим:
.я
Отсюда , что и доказывает необходимость условия баланса Т-задачи.

Пусть справедливо условие (1.6). Обозначим , где .

Нетрудно доказать, что х_ij составляет план задачи. Действительно

Таким образом, доказана достаточность условия баланса для решения Т-задачи.

2. Ранг системы ограничений (1.1), (1.2) равен

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

Очевидно

Так как
_,то

_,отсюда

,
Учитывая условие баланса (1.6), получим
,
т.е. первое уравнение системы (1.1) тоже удовлетворяется.

Таким образом, ранг системы уравнений (1.1), (1.2) .

Докажем, что ранг системы уравнений (1.1), (1.2) равен точно . Для этого составим матрицу из первых () компонентов векторов

Очевидно, что эта матрица не вырождена. Поэтому векторы {} образуют базис. Так как базис системы состоит из () векторов, то и ранг системы (1.1), (1.2) .

Двойственная транспортная задача ( – задача). Для Т-задачи, как и для любой задачи ЛП, существует двойственная задача к ней -задача.

Переменные -задачи обозначим v₁, v₂., v_n, – u₁, – u₂., – u_m…

Теорема 1. -задача имеет решение и если X_опт = ,

– оптимальные решения T и -задачи соответственно, то
. (1.7)
Если учесть, что u_i – стоимость единицы продукции в пункте А_і, а v_j – стоимость после перевозки в пункт B_j, то смысл теоремы будет такой:

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

Переменные u_iиv_j называют потенциалами пунктов A_iиB_j для Т-задачи.

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

Справедливость теоремы 1. следует из основной теоремы двойственной ЛП (теорема 2.5).

Сформулируем необходимые и достаточные условия оптимальности плана Т-задачи.

Теорема 2. Для оптимальности плана Х₀ Т-задачи необходимо и достаточно существование таких чисел v₁, v₂., v_n, – u₁, – u₂., – u_m, что
v_j – u_i c_ij, i = 1., m; j=1., n… (1.8)
При этом, если
это v_j – u_i = c_ij.
Cправедливость этой теоремы вытекает из общих идей теории двойственности линейного программирования (в частности, теоремы 2.5, 2.7).

Дадим экономическую интерпретацию условий теоремы 2.

Разность между потенциалами пунктов B_jиA_i, т.е. величину v_j – u_i, можно рассматривать как приращение ценности единицы продукции при перевозке из пункта A_i в пункт B_j. Поэтому, если v_j – u_i < c_ij, то перевозка по коммуникации A_i B_j нерентабельна, и . Если v_j – u_i = c_ij, то такая перевозка рентабельна, и (см. Теорему 2.7).

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

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

Пусть - пропускная способность коммуникации A_i B_j.
Тогда (1.9)
Т-задача состоит в минимизации Ц.Ф. (1.3) при условиях (1.1), (1.2), (1.9). Даже в случае разрешимости Т-задачи, Т_d – задача может оказаться неразрешимой, поскольку величины пропускных способностей будут недостаточны для полного вывоза продукта из п. А_і, и полного ввоза продукта в п. В_j. Поэтому для Т_d – задачи вводят еще два условия:
(1.10)

(1.11)
Но и при добавочных условиях (1.10), (1.11) Т_d – задача не всегда разрешима. Для установления совместимости всех условий делают попытку построить любой план Т-задачи. Если удается, то система уравнений (1.1), (1.2), (1.9) – (1.11) совместна. В противном случае Т_d – задача неразрешима.

Теорема 3. Для оптимальности плана Х₀ Т_d – задачи необходимо и достаточно существование таких чисел v₁, v₂., v_n, – u₁, – u₂., – u_m, при которых
если , (1.12)

если 0 <, (1.13)

если. (1.14)
Смысл условий оптимальности (1.12) – (1.14) состоит в следующем:

если приращение стоимости продукта v_j – u_j меньше транспортных расходов c_ij, то такая перевозка убыточна, а потому . Если же приращение стоимости продукта v_j – u_j больше транспортных расходов c_ij (3.1.14), то эта перевозка прибыльна, а потому ее величина должна быть максимальной, т.е. .

Таким образом, теорема 3.3 по существу выражает принцип рентабельности для T_d – задачи.

Открытые транспортные модели. Существует ряд практических задач, в которых условие баланса не выполняется. Такие модели называются открытыми. Возможные два случая:
1)

2)
В первом случае полное удовлетворение спроса невозможно.

Такую задачу можно привести к обычной транспортной задаче следующим образом. Обозначим через величину штрафа из-за неудовлетворения запросов на единицу продукта в пункте B_j.

Тогда требуется минимизировать
(1.15)
при условиях

где - неудовлетворенный спрос.

Задачу (3.1.15) приводят к обычной Т-задаче введением фиктивного пункта производства А_m+1, с объемом производства и транспортными издержками В таком случае Т-задача будет иметь вид

минимизировать

при условиях

В найденном решении х_опт полагаем все перевозки из фиктивного пункта А_m+1 равными нулю, т.е. .

Рассмотрим теперь второй случай. Введем фиктивный пункт B_n+1 с объемом спроса . Пусть - это убытки (штраф) в пункте А_і за единицу невывезенного продукта. Обозначим через сии_,n+1 = удельные транспортные издержки на перевозку единицы продукта с А_і в В_n+1. Тогда соответствующая Т-задача запишется так:
минимизировать (1.16)
при условиях
(1.17) – (1.18)

В найденном решении все перевозки в фиктивный пункт В_n+1 считают равными нулю.

Опорные планы Т-задачи

Опорным (базисным) планом Т-задачи называют любое ее допустимое, базисное решение. Понятие опорного плана имеет наглядную геометрическую интерпретацию.

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

…

.

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

В процессе этого движения коммуникации, стоящие на четных местах в (1.19), будут пройдены в противоположном направлении.

Маршрут (1.19), к которому добавлена коммуникация называется замкнутым маршрутом или циклом.

Способ проверки произвольного плана Т-задачи на опорность, основан на следующих двух теоремах (прямой и обратной).

Теорема 4. Система, составленная из векторов Т-задачи, является линейно независимой тогда и только тогда, когда из коммуникаций, соответствующих этим векторам, нельзя составить замкнутый маршрут.

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

Достаточность. Допустим, что из коммуникаций, отвечающих векторам системы R, нельзя составить замкнутый маршрут. Докажем, что в таком случае R – линейно независимая система. Если предположить противное, т.е. линейную зависимость векторов системы R, то существуют такие числа , среди которых не все нули, для которых выполняется условие
. (1.21)
Пусть, например . Перенесем тогда соответствующий вектор вправо и получим
, (1.22)
где Е₁ образуется вычеркиванием в Е пары индексов (). Компонента с номером в правой части (3.1.22) не равна нулю.

Следовательно, это же относится и к левой части этого равенства, т.е. среди

векторов найдется хотя бы один вектор вида с

коэффициентом . Перенеся его в правую чатсть равенства (1.22), получим
, (1.23)
где . Но поскольку , компонента с номером правой части (1.23) отлична от нуля. Поэтому среди векторов левой части (1.23) найдется хотя бы один вектор вида , для которого . Перенося его в правую часть (1.23), находим

(1.24)

где
Этот процесс переноса векторов в правую часть можно продолжить аналогичным образом и дальше. Допустим, что уже проведено (2k-1) шагов. Тогда имеет место соотношение
(1.25)
где

Возможные два случая:

1) при некотором

2) .

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

Во втором случае процесс переноса продолжается, и поскольку , среди векторов Р_ij, где (i, j) обязательно найдется вектор с коэффициентом .

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

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

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

Назовем коммуникацию Т-задачи основной коммуникацией плана Х, если Тогда, используя теорему 3.4, можно сформулировать следующий признак проверки произвольного плана на опорность.

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

Теорема 5. Вектор является линейной комбинацией векторов системы R тогда и только тогда, когда из векторов этой системы можно составить маршрут, соединяющий пункты A_k и . Если этот маршрут имеет вид

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

Тогда
.

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

	1	2	3	4	5	6	i /j
	1					+	1
	1	1					2
X =		1	1				3
			1	1			4
				1	1	1	5

	Рис. 3.3.

Рассмотрим произвольную матрицу . Между позициями матрицы Х и векторами можно установить следующее соответствие. Вектор соответствует элементу матрицы Х. Тогда можно задать систему из векторов , выделив единицами соответствующие элементы матрицы Х. Рассмотрим матрицу на рис3. Здесь единицами отмечена система векторов R:
.
При использовании матрицы Х критерий проверки линейной независимости формулируется так: для линейной независимости системы векторов необходимо и достаточно, чтобы из ненулевых элементов матрицы Х, отвечающих этим векторам, невозможно было составить замкнутый маршрут (цикл).

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

Введем теперь в систему вектор , отметив его знаком '+'. Чтобы разложить по векторам системы R, составим цепочку из выделенных элементов, которая замыкается на элементе :
.
При небольших размерах матрицы Х визуальное отыскание замкнутых цепочек в ней представляет значительные трудности. В таком случае прибегают к формализованному методу вычеркивания. Метод вычеркивания позволяет выделить в произвольном плане Х Т-задачи замкнутую цепочку, если она существует.

Этот метод состоит в следующем. Выделив в плане Х множество ненулевых элементов, обозначаемое через S, выясним, существуют ли во множестве элементов S циклы. Для этого просматриваем одну за другой строки плана Х и вычеркиваем строки, не содержащие элементов S, и строки, которые содержат не более одного элемента S (ненулевой элемент). Просмотрев все строки плана Х, переходим к столбцам и вычеркиваем те из них, которые содержат не более одного элемента S.

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

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

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

Во втором случае множество S содержит цикл (циклы) и соответствующий план Х не является опорным (базисным). На рис. 4 показаны два плана Т-задачи: небазисный (рис. 4, а) и базисный (рис. 4, б). Номера линий указывают порядок вычеркивания. Звездочками отмечены элементы, которые вычеркнуть нельзя. Они образуют цикл.

1* *1

1* 1*

1 1

*1 *1

Рис. 4. а)

5 6 11 7 8

1 1

9 1 1

2 1

10 1 1 1

3 1

4 1

Рис. 4. б)

Нахождение начальных опорных планов

Существует несколько методов построения начальных опорных планов Т-задачи. Из них самый распространенный метод северо-западного угла и метод минимального элемента.

Метод северо-западного угла. Основную идею метода рассмотрим на конкретном примере.

Пусть дана Т-задача с четырьмя пунктами производства А₁, А₂, А₃, А₄ с объемами производства и пунктами потребления с объемами потребления соответственно .

Построим матрицу Х размером 4х4, причем для удобства вычислений снизу от нее оставим строку b_j, справа столбец a_i. Кроме того, снизу от b_j образуем строки , где будем записывать неудовлетворенные потребности, а справа от a_i – столбцы , где будем записывать остатки невывезенного продукта (табл. 2).

Заполнение таблицы начинают с левого верхнего элемента таблицы X – x₁₁, что и обусловило название метода. Сравнив с и выбрав меньшее из них, получим x₁₁=1. Записываем это значение в матрицу Х₀. Так как первый выбор произведен по строке, то остальная часть первой строки должна быть заполнена нулями. Во вспомогательном столбце записываем остатки невывезенного продукта, , а в строке – неудовлетворенные потребности после одного шага заполнения.

Переходим к второй строке и начинаем заполнение с элемента (новый северо-западный угол незаполненной части таблицы 2). Сравнивая выбираем меньшее из них, и потому . Остальную часть второй строки заполняем нулями. Далее заполняем таблицу аналогично. После окончания процесса заполнения будем иметь начальный план Х₀. Полученный план является базисным (опорным), так как из его ненулевых элементов нельзя составить цикл. Кроме того, он удовлетворяет условиям задачи, так как
.

Таблица 2

Х
	1	0	0	0	1	0	0	0	0	0	0
	2	0	0	0	2	2	0	0	0	0	0
	2	1	0	0	3	3	3	1	0	0	0
	0	0	2	2	4	4	4	4	4	2	0
	5	1	2	2
	4	1	2	2
	0	1	2	2
	0	0	2	2
	0	0	0	2
	0	0	0	0

Формальное описание алгоритма. I. Определяют верхний левый элемент матрицы Х:
.
Возможные три случая: а) если то и всю первую строку, начиная со второго элемента, заполняют нулями; б) если , то , а все оставшиеся элементы первого столбца заполняют нулями; в) если
то
и все оставшиеся элементы первых столбцов и строки заполняют нулями.

Находим

на этом один шаг метода заканчивается.

2. Пусть уже проделано k шагов. (k+1) – й шаг состоит в следующем. Определяют верхний левый элемент незаполненной части матрицы Х. Пусть это будет элемент

причем
, (1.27)
где
(1.28)
Если , то заполняем нулями строку , начиная с ( +1) – го элемента. В противном случае заполняем нулями столбец , начиная с элемента ( +1). Если , то заполняем нулями остаток строки и столбца . Далее вычисляем . На этом (k+1) – й шаг заканчивается. Описанный процесс повторяется до тех пор, пока матрица Х не будет заполнена полностью.

Метод минимального элемента

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

Формальное описание алгоритма. Элементы матрицы нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х₀.

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

Дале этот процесс повторяют с незаполненной частью матрицы Х₁.

Пример 1. Найти начальный базисный план методом минимального элемента для Табл. 3. следующей задачи.

Таблица. 3.

A_i \ B_j	1	2	3	4	B_j / a_i
1	7⁽¹⁰⁾	8⁽¹¹⁾	5⁽⁷⁾	3⁽⁵⁾	11
2	2⁽³⁾	4⁽⁴⁾	5⁽⁸⁾	9⁽¹²⁾	11
3	6⁽⁹⁾	3⁽⁴⁾	1⁽¹⁾	2⁽²⁾	8
A_i / b_j	5	9	9	7	b_j \ a_i

Цифры в скобках указывают порядок заполнения элементов в матрице Х₀ (табл. 3.4).

Соответствующее значение целевой функции равно
3*8 + 1*5 + 3*7 + 5*2 + 6*4 + 8*1 = 92

Таблица 4

Х₀
	0	3	1	7	11	4	3	0
	5	6	0	0	11	6	0
	0	0	8	0	8	0
	5	9	9	7
	0	3	1	0
		0	0

Решение транспортной задачи при вырожденном опорном плане

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

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

1. Вырожденный план является начальным Х₀. Тогда выбирают некоторые нулевые элементы матрицы Х₀ в качестве базисных так, чтобы при этом не нарушалось условие базисного плана. Число этих элементов равняется . Далее данные элементы заменяют на (где – произвольное, бесконечно малое число) и рассматривают их как обычные базисные элементы плана. Задачу решают как невырожденную, а в последнем оптимальном плане Х_k вместо пишут нули.

2. Вырожденный план получается при построении плана Х_k+1 на базе Х_k, если цепочка в плане Х_k содержит не менее двух минимальных нечетных элементов. В таком случае в матрице Х_k+1 полагают равным нулю только один из этих элементов, а остальные заменяют на , и далее решают задачу как невырожденную. Если на k-м шаге , то при переходе от Х_k к Х_k+1 значение целевой функции не изменяется, а в базис вводится элемент , для которого перевозка станет равной .

Пример 2. Решим Т-задачу со следующими условиями (см. Табл.6)

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

Предварительный этап. Методом минимального элемента строим начальный базисный план Х₀ (Табл. 5)

Таблица 5

C =	a_ib_j	4	6	8	6
	6	2⁽⁵⁾	2⁽⁴⁾	3⁽⁶⁾	4⁽¹¹⁾
	8	6⁽¹²⁾	4⁽¹⁰⁾	3⁽⁹⁾	1⁽³⁾
	10	1⁽¹⁾	2⁽⁶⁾	2⁽⁷⁾	1⁽²⁾

Так как m + n – 1 = 6; k = 4, то план х₀ – вырожденный; l = m+ n -1 – k = 2.

Два нулевых элемента Х₀ делаем базисными так, чтобы не нарушить условие опорности. Выберем в качестве базисных элементов , и положим их равными .

Схема перевозок для плана Х₀ показана на рис. 6.

Рис. 6.
Для вычисления предварительных потенциалов выберем начальный пункт А₁ и допустим, что . Потенциалы всех остальных пунктов вычисляем по формулам
,

Для проверки оптимальности плана х₀ строим матрицу С₁, элементы которой вычисляем по соотношению

Так как в матрице С₁ элемент С₂₃= – 3 < 0, то план Х₀ – неоптимальный.
Первая итерация. Второй этап.


	^*	6^*	0	0				6	0	0
X₀=	0^*	^*	8	0⁺		X₁ =	0	0	6	
	4	0	0	6^*	₁ = 		4	0	0	6

В результате построения Х₁ в базис вводим. План Х₁ является вырожденным (в цепочке есть два минимальных элемента). Поэтому один из этих элементов, например , в плане Х₁ заменяем на .
Вторая итерация. Первый этап


		0	2	2			0	0	-1	2
С₁=	2	0		-3	+3	С₂ =	5	3	0	0
	0	1	2	0			0	1	-1	0
			-3

Второй этап.


		6	0	0				6	0	0
X₁=	0	0	8^*	^*		X₂ =	0	0	2	6
	4	0	0⁺	6^*	₃ =min {8, 6}= 6		4	0	6	0

Третья итерация. Первый этап.


			-1	2	+1		0	0	0	3
С₂=	5	3				С₂ =	4	2	0	0
		1	-1	0	+1		0	1	0	1
	-1	-1

Так как в матрице С₃ нет отрицательных элементов, план Х₂ – оптимальный.

Венгерский метод для транспортной задачи

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

Пусть требуется решить Т-задачу следующего вида

минимизировать

при условиях

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

В результате предварительного этапа вычисляют матрицу , элементы которой удовлетворяют следующим условиям:
, (1.3.1)

. (1.3.2)
Если в условиях (1.3.1), (1.3.2) строгие равенства, то матрица Х₀ является решением Т-задачи.

Матрицу, построенную в результате k-й итерации, обозначим . Обозначим также
. (1.3.3)

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

Описание алгоритма Венгерского метода

Предварительный этап. В каждом из столбцов матрицы транспортных издержек отыскивают минимальный элемент, который вычитают из всех элементов этого столбца. Получают матрицу С'. Далее в каждой строке матрицы С' выбирают минимальный элемент и вычитают его из всех элементов рассматриваемой строки. Приходят к матрице С₀ (С₀ ~ C), все элементы которой неотрицательны, причем в каждой строке и столбце С₀ имеем по крайней мере, один нуль. Строят матрицу Х₀ так, чтобы ее ненулевые элементы были расположены в позициях нулей матрицы С₀.

Пусть - номер строки, в которой расположен k-й нуль j-го столбца матрицы С₀. Тогда элементы первого столбца матрицы Х₀ определяют по рекуррентной формуле
(3.3.4)
Т.е. все элементы первого столбца , которым соответствуют ненулевые элементы в матрицы С₀, заполняют нулями, а остальные элементы этого столбца заполняют по методу северо-западного угла.

Допустим, что столбцы Х₀ от первого до (j-1) – го включительно уже заполнены. Тогда элементы j-го столбца определяют в соответствии с формулой
(3.3.5)

Если , то Х₀ – оптимальный план Т-задачи. Если , то переходим к первой итерации.

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

Допустим, что уже проведено k итераций, причем . В этом случае необходимо, используя матрицы С_k и Х_k, провести следующую (k+1) – ю итерацию. Перед началом итерации выделяют знаком '+' те столбцы матрицы С_k, для которых невязки по столбцам равны
.
Первый этап. Если все ненулевые элементы матрицы С_k окажутся в выделенных столбцах, то переходят к третьему этапу. В противном случае пусть некоторый невыделенный нуль находится в -й строке и в -м столбце. Тогда вычисляют значения невязки -й строки:
.
Возможен один из двух случаев: 1), 2). В первом случае -ю строку С_k отмечают знаком '+' справа от нее, а сам невыделенный нуль отмечают штрихом. Далее просматривают элементы -й строки, которые лежат в выделенных столбцах и ищут среди них существенные нули (напомним, что существенным нулем С_k называется такой элемент , для которого ). Если таким существенным нулем оказался элемент , а сам столбец  – выделен, то знак выделения '+' над столбцом  уничтожают, а сам этот нуль отмечают звездочкой.

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

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

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

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

Во втором случае, отметив этот нуль штрихом, сразу переходим к третьему этапу.

Второй этап. Состоит в построении цепочки из нулей матрицы С_k, отмеченных штрихами и звездочками, и в последующем переходе к новой матрице Х_k+1

Пусть для некоторого нуля со штрихом матрицы С_k, расположенного, например, в позиции (), невязка строки . Начиная с этого элемента , строят цепочку из отмеченных нулей матрицы С_k: двигаясь по столбцу , выбирают нуль со звездочкой , далее двигаясь от него по строке , находят нуль со штрихом . Потом движутся от него по столбцу ₂ к следующему нулю со звездочкой и т.д. Такой последовательный переход от 0' к 0^* по столбцу и от 0^* к 0' по строке осуществляют до тех пор, пока это возможно.

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

После того как цепочка вида

построена, осуществляют переход к матрице от матрицы Х_k по формулам
(1.3.7)

где (1.3.8)
Таким образом, -минимальный элемент среди совокупности четных элементов цепочки, невязки строки, где начинается цепочка, и столбца, где она заканчивается.

Вычисляем невязку для

На этом (k+1) – я итерация заканчивается.

Третий этап. Итак, допустим, что все нули выделены. Третий этап заключается в переходе от матрицы С_k к эквивалентной матрице С′_k, в которой появляется новый невыделенный нуль (или нули). Пусть , где минимум выбирают из всех невыделенных элементов матрицы С_k. Тогда из всех элементов невыделенных строк матрицы С_k вычитают h, а ко всем элементам выделенных столбцов прибавляют h. В результате получают матрицу С'_k(С'_k~ C_k), в которой все существенные нули матрицы С_k остаются нулями, и кроме того, появляются новые невыделенные нули.

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

Если после выполнения второго этапа то Х_k+1 – оптимальный план. В противном случае переходим к (k+2) итерации.

Отметим некоторые важные особенности венгерского метода.

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

Метод позволяет на каждой итерации по величине невязки оценить близость Х_k к оптимальному плану, а также верхнюю границу необходимого числа оставшихся итераций N_ост:
. (1.3.9)
Эта формула справедлива для целочисленных значений всех переменных и .

Список литературы
1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа.

2. Вентцель Е.С. Исследование операций. – М.: Наука, 1976.

3. Горелик В.А., Ушаков И.А. Исследование операций. – М: Машиностроение, 1986. – 286 с.

4. Давыдов Э.Т. Исследование операций: Учебное пособие для студентов вузов. – М.: Высшая школа, 1990. – 383 с.

5. Ермолаев Ю.М. Математические методы исследования операций. – К.: Наука, 1979.

6. Кузнецов Ю.Н. Математическое программирование. – М.: Наука, 1976.

7. Минц М. Математическое программирование. Теория и алгоритмы. – М.: Наука, 1990.

8. Таха Х. Введение в исследование операций. – м.: Мир, 1985.

9. Толбатов Ю.А. Эконометрика в Excel. – К.: Четверта хвиля, 1997.

Bukvasha