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

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

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

Пункт потребления

Пункт производства

C11

C12

C1n

C21

C22

C2n

Cm1

Cm2

Cmn

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

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

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

/>/>1

/>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 1 2 2 2 2 1 3 3 3 1 2 2 4 4 4 4 4 2

5 1 2 2

4 1 2 2

1 2 2

2 2

Формальное описание алгоритма. 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

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)

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

3 1 7 11 4 3 5 6 11 6 8 8

5 9 9 7

3 1

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

Опорный план называется вырожденным, если число его ненулевыхперевозок 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)

6(12)

4(10)

3(9)

1(3)

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

X0 =

/>0*

*

X1 =

6  4

1 = 

4 6

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

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

2 2 -1 2

/>С1 =

-3

/>+3

С2 =

5 3 1 2 1 -1 -3

Второй этап.

/>

6  6

X1 =

*

X2 =

2 6 4

3 =min {8, 6}= 6

4 6

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

/>/>

-1 2 +1 3

С2 =

5 3

С2 =

4 2

1 -1 +1 1 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.