База знаний студента. Реферат, курсовая, контрольная, диплом на заказ

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

Транспортная задача (Т-задача) является одной из наиболее распространенных специальных задач ЛП. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О.Н. Толстым [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.

Пункт потребления Пункт производства	B1	B2	.	Bn	Bj ai
A1	C11	C12	.	C1n	a1
A2	C21	C22	.	C2n	a2
Am	Cm1	Cm2	.	Cmn	am
Ai bj	b1	b2	.	bn	Объем производства Объем потребления

Пусть  количество продукта, перевозимого из пункта 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.

Ai \ Bj	1	2	3	4	Bj / ai
1	7(10)	8(11)	5(7)	3(5)	11
2	2(3)	4(4)	5(8)	9(12)	11
3	6(9)	3(4)	1(1)	2(2)	8
Ai / bj	5	9	9	7	bj \ ai

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

Соответствующее значение целевой функции равно

 3*8 + 1*5 + 3*7 + 5*2 + 6*4 + 8*1 = 92

Таблица 4

Х0
	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 =	ai bj	4	6	8	6
	6	2(5)	2(4)	3(6)	4(11)
	8	6(12)	4(10)	3(9)	1(3)
	10	1(1)	2(6)	2(7)	1(2)

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

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

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

Рис. 6.

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

,

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

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

Первая итерация. Второй этап.

		*	6*	0	0						6	0	0
X0 =		0*	*	8	0+			X1 =		0	0	6	
		4	0	0	6*		1 = 			4	0	0	6

 

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

Вторая итерация. Первый этап

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

Второй этап.

			6	0	0						6	0	0
X1 =		0	0	8*	*			X2 =		0	0	2	6
		4	0	0+	6*		3 =min {8, 6}= 6			4	0	6	0

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

				-1	2		+1			0	0	0	3
С2 =		5	3					С2 =		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.

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

 

• 14:21 05 Июля 2016
  Российско-китайский медуниверситет откроет магистерскую программу по TCM
• 01:21 05 Июля 2016
  На форуме МГУ Россия и Китай обсудят научно-образовательное сотрудничество
• 11:00 04 Июля 2016
  Реморенко: "ЕГЭ-туризм" в России сходит на нет
• 10:52 04 Июля 2016
  Летняя российско-австрийская школа откроется в Москве
• 15:31 01 Июля 2016
  В СПбГУ могут воссоздать географический факультет

Заказать уникальную работу