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

Тип работы:
Контрольная
Предмет:
Экономические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

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

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

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

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

Постановка Т-задачи. Пусть в пунктах А1,…, Am производят некоторый однородный продукт, причем объем производства в пункте Ai составляет ai единиц, i = 1,…, m. Допустим, что данный продукт потребляют в пунктах B1., Bn, a объем потребления в пункте Вj составляет bj одиниць j = 1., n. Предположим, что из каждого пункта производства возможно транспортировка продукта в любой пунктпотребления. Транспортные издержки по перевозке единицы продукции из пункта Ai в пункт Вj равны cij (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

Объем производства

Объем потребления

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

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

Вектор Pij, компоненты которого состоят из коэффициентов при переменных xij в ограничениях (3.1. 1) и (3.1. 2), называют вектором коммуникаций:

Вводят также вектор производства-потребления P0, где

.

Тогда ограничение (3.1. 1) и (3.1. 2) можно записать в векторной форме

, (1. 5)

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

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

, (1. 6)

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

Доказательство. Пусть переменные xij, 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).

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

Переменные -задачи обозначим v1, v 2., v n, — u1, — u2., — um

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

 — оптимальные решения T и -задачи соответственно, то

. (1. 7)

Если учесть, что ui — стоимость единицы продукции в пункте Аі, а vj — стоимость после перевозки в пункт Bj, то смысл теоремы будет такой:

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

Переменные ui и vj называют потенциалами пунктов Ai и Bj для Т-задачи.

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

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

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

Теорема 2. Для оптимальности плана Х0 Т-задачи необходимо и достаточно существование таких чисел v1, v2., vn, — u1, — u2., — um, что

vj — ui cij, i = 1., m; j=1., n… (1. 8)

При этом, если

это vj — ui = cij.

Cправедливость этой теоремы вытекает из общих идей теории двойственности линейного программирования (в частности, теоремы 2. 5, 2. 7).

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

Разность между потенциалами пунктов Bj и Ai, т. е. величину vj — ui, можно рассматривать как приращение ценности единицы продукции при перевозке из пункта Ai в пункт Bj. Поэтому, если vj — ui < cij, то перевозка по коммуникации Ai Bj нерентабельна, и. Если vj — ui = cij, то такая перевозка рентабельна, и (см. Теорему 2. 7).

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

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

Пусть — пропускная способность коммуникации Ai Bj.

Тогда (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. Для оптимальности плана Х0 Тd — задачи необходимо и достаточно существование таких чисел v1, v2., vn, — u1, — u2., — um, при которых

если, (1. 12)

если 0 <, (1. 13)

если. (1. 14)

Смысл условий оптимальности (1. 12) — (1. 14) состоит в следующем:

если приращение стоимости продукта vj — uj меньше транспортных расходов cij, то такая перевозка убыточна, а потому. Если же приращение стоимости продукта vj — uj больше транспортных расходов cij (3.1. 14), то эта перевозка прибыльна, а потому ее величина должна быть максимальной, т. е..

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

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

1)

2)

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

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

Тогда требуется минимизировать

(1. 15)

при условиях

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

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

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

при условиях

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

Рассмотрим теперь второй случай. Введем фиктивный пункт Bn+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)

где Е1 образуется вычеркиванием в Е пары индексов (). Компонента с номером в правой части (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 тогда и только тогда, когда из векторов этой системы можно составить маршрут, соединяющий пункты Ak и. Если этот маршрут имеет вид

то

. (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. б)

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

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

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

Пусть дана Т-задача с четырьмя пунктами производства А1, А2, А3, А4 с объемами производства и пунктами потребления с объемами потребления соответственно.

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

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

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

.

Таблица 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) — й шаг заканчивается. Описанный процесс повторяется до тех пор, пока матрица Х не будет заполнена полностью.

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

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

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

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

Дале этот процесс повторяют с незаполненной частью матрицы Х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

Цифры в скобках указывают порядок заполнения элементов в матрице Х0 (табл. 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. Вырожденный план является начальным Х0. Тогда выбирают некоторые нулевые элементы матрицы Х0 в качестве базисных так, чтобы при этом не нарушалось условие базисного плана. Число этих элементов равняется. Далее данные элементы заменяют на (где - произвольное, бесконечно малое число) и рассматривают их как обычные базисные элементы плана. Задачу решают как невырожденную, а в последнем оптимальном плане Хk вместо пишут нули.

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

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

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

Предварительный этап. Методом минимального элемента строим начальный базисный план Х0 (Табл. 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, то план х0 — вырожденный; l = m+ n -1 — k = 2.

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

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

Рис. 6.

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

,

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

Так как в матрице С1 элемент С23 = - 3 < 0, то план Х0 — неоптимальный.

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

?*

6*

0

0

?

6

0

0

X0 =

0*

?*

8

0+

X1 =

0

0

6

?

4

0

0

6*

?1 = ?

4

0

0

6

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

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

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

Так как в матрице С3 нет отрицательных элементов, план Х2 — оптимальный.

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

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

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

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

при условиях

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

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

, (1.3. 1)

. (1.3. 2)

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

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

. (1.3. 3)

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

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

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

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

(3.3. 4)

Т.е. все элементы первого столбца, которым соответствуют ненулевые элементы в матрицы С0, заполняют нулями, а остальные элементы этого столбца заполняют по методу северо-западного угла.

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

(3.3. 5)

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

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

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

.

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

.

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

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

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

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

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

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

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

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

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

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

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

(1.3. 7)

где (1.3. 8)

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

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

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

Третий этап. Итак, допустим, что все нули выделены. Третий этап заключается в переходе от матрицы Сk к эквивалентной матрице С?k, в которой появляется новый невыделенный нуль (или нули). Пусть, где минимум выбирают из всех невыделенных элементов матрицы Сk. Тогда из всех элементов невыделенных строк матрицы Сk вычитают h, а ко всем элементам выделенных столбцов прибавляют h. В результате получают матрицу С'k(С'k ~ Ck), в которой все существенные нули матрицы С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.

ПоказатьСвернуть
Заполнить форму текущей работой