Метод Фогеля

На каждом шаге метода Фогеля для каждой i–й строки вычисляются штрафы d_i как разность между двумя наименьшими тарифами строки. Таким же образом вычисляются штрафы d_i для каждого j–го столбца. После чего выбирается максимальный штраф из всех штрафов строк и столбцов. В строке или столбце, соответствующем выбранному штрафу, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом min c_ij

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

Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i–й строке и j–му столбцу.

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

Если величина фиктивных тарифов превышает максимальный из реальных тарифов задачи [c^ф > max c_ij (i=1,n; j=1,m)], то методы минимального элемента и Фогеля позволяют получить более дешевые планы перевозок, чем в случае с нулевыми фиктивными тарифами.

На каждом шаге метода Фогеля для каждой i-й строки вычисляются штрафы   как разность между двумя наименьшими тарифами строки. Таким же образом вычисляются штрафы   для каждого j-го столбца. После чего выбирается максимальный штраф из всех штрафов строк и столбцов. В строке или столбце, соответствующем выбранному штрафу, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом  .

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

Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.

Транспортная таблица с опорным планом Фогеля

						Штрафы строк,
	5	8	110 1	100 2	210/110/0	1	1	1	7
	125 2	25 5	20 4	9	170/45/25/0	2	1	1	1
	9	65 2	3	1	65/0	1	1	–	–
	125/0	90/25/0	130/20/0	100/0
Штрафы столбцов,	3	3	2	1
	–	3	2	1
	–	3	3	7
	–	3	3	–

На первом шаге нахождения опорного плана методом Фогеля возникает ситуация равенства значений максимальных штрафов транспортной матрицы (см. табл. 5.3)

.

Минимальные тарифы в этих столбцах также совпадают

.

Поэтому необходимо сравнить суммарные штрафы   клеток (2,1) и (3,2)

;

.

Т.к.  , то выбираем на первом шаге для заполнения клетку (2,1).

Опорный план  , найденный методом Фогеля

 [ед.товара],   [руб.].

Метод аппроксимации Фогеля.

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

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

Алгоритм решения транспортной задачи методом аппроксимации Фогеля следующий:

I этап. Определение начального допустимого плана.

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

2. Для каждого столбца таблицы необходимо упорядочить элементы стоимости перевозок c_ij по возрастанию. Далее необходимо определить величину штрафа столбца.

3. Определить строку (или столбец), имеющую (имеющий) наибольший штраф по всем штрафам строк и столбцов, а в ней (в нем) — элемент с минимальной величиной стоимости перевозок с_ij. Зафиксировать индексы (i, j) этого элемента.

4. Присвоить наибольшее значение из допустимых (с учетом ограничений) переменной х_ij, индексы которой соответствуют шагу 3.

5. Скорректировать величины а_i и b_j и вычеркнуть строку i, если а_i = 0, или столбец j, если b_j = 0.

6. Проверить, все ли величины а_i и b_j. равны нулю, если да, то окончить вычисления; в противном случае взять в качестве исходной оставшуюся часть таблицы и перейти к шагу 3.

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

Билет 17.Сравнение методов

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

Метод северо-западного угла

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

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

Если существующий запас позволяет перевезти всю потребность, то

        в клетку (i,j) в качестве перевозки вписывается значение потребности  ;

        j-й столбец вычеркивается, поскольку его потребность уже исчерпана;

        от существующего запаса в i-й строке отнимается величина сделанной перевозки, прежний запас зачеркивается, а вместо него записывается остаток, т.е.  .

Если существующий запас не позволяет перевезти всю потребность, то

        в клетку (i,j) в качестве перевозки вписывается значение запаса  ;

        i-я строка вычеркивается, поскольку ее запас уже исчерпан;

        от существующей потребности в j-й строке отнимается величина сделанной перевозки, прежняя потребность зачеркивается, а вместо нее записывается остаток, т.е. .

Нахождение опорного плана продолжается до тех пор, пока не будут вычеркнуты все строки и столбцы.

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

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

Метод Фогеля

На каждом шаге метода Фогеля для каждой i-й строки вычисляются штрафы   как разность между двумя наименьшими тарифами строки. Таким же образом вычисляются штрафы   для каждого j-го столбца. После чего выбирается максимальный штраф из всех штрафов строк и столбцов. В строке или столбце, соответствующем выбранному штрафу, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом  .

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

Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.

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

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

Всякий потенциальный план является оптимальным.

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

Общая схема отдельной итерации такова.

По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj:

Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.

Рассмотрим подробнее процесс определения потенциалов текущего плана транспортной задачи. Потенциал первого пункта потребления принимаем равным нулю.

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

Для свободных клеток транспортной таблицы вычисляются величины

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

Разность потенциалов можно трактовать как увеличение цены продукта при его перевозке из пункта i в пункт j.

Процесс «улучшения» плана состоит в определении вводимой и выводимой клеток, в чем прослеживается содержательная аналогия с соответствующими пунктами симплекс-процедур.

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

В построенной цепочке, начиная с вводимой клетки (которая считается первой), помечаются вершины: нечетные — знаком «+», а четные знаком «—». Знаком «+» отмечаются те клетки, в которых объемы перевозок должны увеличиться (таковой, в частности, является клетка, вводимая в план, поскольку она должна стать базисной). Знаком «—» — те клетки, в которых перевозки уменьшаются с целью сохранения баланса. Среди множества клеток, помеченных знаком «—», выбирается клетка с наименьшим значением.

Она и становится кандидатом на вывод, т. к. уменьшение объема перевозок на большую величину может привести к отрицательным значениям x_i,j в других «минусовых» клетках. Затем производится пересчет плана по цепочке: к объемам перевозок в клетках, помеченных знаком «+», добавляется объем q, а из объемов клеток, помеченных знаком «—», он вычитается. В результате ввода одной клетки и вывода другой получается новый базисный план, для которого на следующей итерации описанные выше действия повторяются.

Завершая разговор о методе потенциалов, следует отдельно остановиться на ситуации возникновения вырожденного плана. Возможность получения вырожденного плана уже отмечалась при описании метода северо-западного угла. Нетрудно заметить, что вырожденный план также может получиться на этапе преобразования текущего плана по цепочке: если одинаковое минимальное значение будет достигнуто сразу на нескольких клетках, помеченных знаком «—», то при вычитании перемещаемого по цепочке объема в новом плане будет меньше чем m + n-1 ненулевых компонент.

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

Билет 19. Построение оптимального решения для задачи с неправильным балансом

До сих пор рассматривались транспортные задачи с правильным балансом. Однако на практике чаще встречаются задачи с неправильным балансом. Каковы особенности их решения? 1. Пусть суммарные запасы поставщиков превосходят суммарные запросы потребителей, т.е. . Очевидно, что в этом случае при составлении оптимального плана перевозок часть запасов поставщиков, равная =, останется не вывезенной. Поэтому в системе ограничений транспортной задачи первую группу уравнений (2) следует заменить неравенствами , i=1,2,...,m. (15) Вторая группа уравнений остается без изменения, так как запросы всех потребителей удовлетворяются полностью. Для приведения к канонической форме в неравенства (15) вводят дополнительные переменные . В результате первые m ограничений задачи принимают вид , i=1,2,...,m. В целевую функцию дополнительные переменные не входят (входят с нулевыми коэффициентами). Математическая модель задачи принимает вид , (16)  , i=1,2,...,m , (17)  , j=1, 2, ... , n, (18) , i=1,2,,...,m, j=1,2,...,n+1. (19) Запишем необходимое и достаточное условие разрешимости задачи (см. теорему1): . Отсюда . Следовательно, чтобы задача в рассматриваемом случае имела решение, необходимо ввести фиктивного потребителя с запросами , равными разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза . 2. Аналогично в случае, когда суммарные запросы потребителей превосходят суммарные запасы поставщиков, т.е. , часть запросов потребителей, равная =, останется не удовлетворенной. Поэтому вторая группа уравнений системы ограничений (3) транспортной задачи заменяется неравенствами , j=1, 2, ... , n.  После введения дополнительных переменных в эти неравенства математическая модель задачи примет вид , (20)  , i=1,2,...,m , (21)  , j=1, 2, ... , n, (22) , i=1,2,,...,m+1, j=1,2,...,n. (23) Для того чтобы задача имела решение, необходимо и достаточно, чтобы . Отсюда . Следовательно, чтобы в этом случае задача имела решение, необходимо ввести фиктивного поставщика с запасами , равными разности суммарных запросов потребителей и запасов поставщика, и нулевыми стоимостями перевозок единиц груза . Необходимо отметить, что при составлении начального опорного решения в последнюю очередь следует распределять запасы фиктивного поставщика и удовлетворять запросы фиктивного потребителя, несмотря на то, что им соответствует наименьшая стоимость перевозок, равная нулю.

Билет 20. Транспортная задача с усложненными условиями. Блокировка.

1. Транспортная задача с избытком запасов: Для отыскания оптимального плана вводят фиктивный (n+1)-й пункт назначения B_n+1 с потребностью b_n+1 и полагают стоимости перевозок грузов в B_n+1 равными нулю. Полученная новая транспортная задача является закрытой. Найдя оптимальный план x_ij   этой транспортной задачи и отбрасывая в полученной таблице последний столбец, получим оптимальный план исходной транспортной задачи.

2. Транспортная задача с избытком заявок: Эта задача несколько сложнее предыдущей: дело в том, что как ни развози грузы, все потребности удовлетворить все равно не удается. Поэтому постановка задачи нуждается в уточнении.

1. Все пункты назначения требуется удовлетворить пропорционально поданным заявкам. В этом случае, подсчитав коэффициент пропорциональности

и «подправив» заявки:  получим закрытую модель транспортной задачи.

2. Если не заботиться о «справедливости» удовлетворения заявок, а по-прежнему интересоваться лишь минимизацией транспортных расходов, то для отыскания оптимального плана вводят фиктивный пункт (m+1)-й отправления A_m+1 с запасом груза a_m+1 и полагают стоимости перевозок грузов из A_m+1равными нулю. Полученная транспортная задача является закрытой. Найдя оптимальный план x_ij  этой транспортной задачи и отбрасывая в полученной таблице последнюю строку, получим оптимальный план исходной транспортной задачи.

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

3. Транспортная задача с поиском максимума целевой функции. Перейдем к целевой функции Z=-F и найдем план ( , доставляющий ей минимум. Тогда (  будет оптимальным и для исходной задачи, причем  ( .

4. Транспортная задача с запретными маршрутами. Речь идет о задачах, в которых нельзя перевозить груз из некоторых пунктов отправления A_i в некоторые пункты назначения B_j. В этом случае стоимости соответствующих перевозок полагаем равными достаточно большому числу. Тогда при отыскании оптимального плана соответствующие перевозки будут блокированы.

5. Транспортная задача с обязательными поставками.

Иогда приходится решать транспортную задачу, в которой дополнительным условием в ограничениях является обязательное обеспечение конкретных перевозок по определенным маршрутам. В этом случае каждую обязательную перевозку x_ij=d_ij реализуем условно, уменьшая на d_ij запасы в A_i и потребности в B_j. Если это не удается сделать, то исходная задача не имеет решения. В противном случае стоимости обязательных поставок полагаем равными достаточно большому числу, решаем полученную задачу и от ее оптимального плана переходим к оптимальному плану исходной задачи.

6. Транспортная задача с ограничениями снизу. Пусть требуется решить транспортную задачу, в которой некоторые из перевозок ограничены снизу x_ij p_ij. Организуем условные перевозки, уменьшив на p_ij запасы в A_i и потребности в B_j. Если это сделать не удается, то исходная задача решения не имеет, в противном случае решаем полученную задачу и от ее оптимального плана переходим к оптимальному плану исходной транспортной задачи.

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

Пусть  - пропускная способность коммуникации A_i B_j.

                                   Тогда                            (3.1.9)

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

                          (3.1.10)

                          (3.1.11)

Но и при добавочных условиях (3.1.10), (3.1.11) Т_d - задача не всегда разрешима. Для установления совместимости всех условий делают попытку построить любой план Т-задачи. Если удается, то система уравнений (3.1.1), (3.1.2), (3.1.9) - (3.1.11) совместна. В противном случае Т_d- задача неразрешима.

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

 если  ,                          (3.1.12)

 если 0 <  ,                  (3.1.13)

 если  .                        (3.1.14)

Смысл условий оптимальности (3.1.12) - (3.1.14) состоит в следующем:

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

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

Билет 21. Распределительные задачи: постановка и построение оптимального решения

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

1. Постановка задачи

От каждого i-го производителя произведенный им ресурс A_i может перемещаться к j-му потребителю ресурса в объеме, не превышающие B_i. Таким образом, x_ij будет означать перемещение некоторого числа единиц ресурса от i-го производителя к j-му потребителю.

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

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

Таблица 1 - Исходные данные

Матрица стоимости	А1	А2	А3	А4	Производители
В1	6	5	8	7	14
В2	3	6	4	2	12
В3	9	1	3	6	8
Потребители	10	14	6	4

Этапы решения задачи

Математическая модель

При решении транспортной задачи необходимо:

а) обеспечить всех потребителей ресурсами;

б) распределить все произведенные ресурсы;

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

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

Транспортная задача всегда разрешима и имеет:

а) единственное решение;

б) несколько допустимых решений, одно из которых оптимально;

в) несколько допустимых решений и все оптимальны.

Через С_ij обозначим стоимость перемещения единицы ресурса, от i-го производителя к j-му потребителю. Тогда матрица X={x_ij} называется матрицей перевозок или планом перевозок, а матрица C={c_ij} - матрица стоимости.

2.2 Разработка алгоритма

1) Задать количество производителей и потребителей;

2) Произвести ввод данных, данные берутся из таблицы 1;

3) следующим шагом строится опорный план для задачи. В программе рассмотрено построение опорного плана методом "северо-западного" угла и методом минимальных элементов;

4) выбирается первый незаполненный элемент опорного плана;

5) от выбранного элемента строится кратчайший прямоугольный замкнутый контур, остальные вершины проходят через заполненные элементы опорного плана. Поворот осуществляется только на 90⁰ и только в заполненных элементах;

6) каждой вершине контура присваивается коэффициент равный соответствующему значение элементу из С={c_ij};

7) каждому коэффициенту в вершине контура строго поочередно присваивается знак "+" или "-" начиная с пустой клетки;

8) выполняется алгебраическое суммирование коэффициентов по всему контуру;

9) пункт 4-8 выполняется для каждого пустого элемента опорного плана;

10) проверяются результаты суммирования по всем контурам на оптимальность;

11) если план перевозок не оптимальный то выполняется перераспределение ресурсов и возвращаемся к пункту 4.

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

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

Если план перевозок не оптимальный, то перераспределение выполняется следующим образом:

а) выбирается контур, для которого нарушено условие оптимальности, если целевая функция стремится к min, то выбирается отрицательный контур. Если таких контуров несколько, то выбирается тот, который больше по модулю;

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

в) проверяется сбалансированность перевозок по столбцам и строкам;

г) заново рассчитывается алгебраические суммы (по стоимости) для всех контуров;

Билет 22. Постановка и оптимальное решение задачи о перевозке неоднородного груза

Билет 23. Задача об оптимальном назначении

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