78. Построение начального опорного плана транспортной задачи: методы Фогеля и минимального элемента.

	В1	В2	…	Вn	Запас, ai
А1	c11 x11	c12 x12	…	c1n x1n	a1
А2	c21 x21	c22 x22	…	c2n x2n	a2
…	…	…	…	…	…
Аm	cm1 xm1	cm2 xm2	…	cmn xmn	am
Потребность, bj	b1	b2	…	bn

Метод Фогеля.

В распределительной таблице по строкам и столбцам определ-ся разность между 2-мя наименьш. тарифами. В строке или столбце с наибольшей разностью заполняется клетка с наименьшим тарифом. Строки или столбцы с нулевыми остатками грузов/запасов в дальнейшем в расчет не принимаются. На каждом этапе загружается только одна клетка.

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

Здесь рассматриваются тарифы и в 1-ю очередь заполняется клетка с min значением тарифа. При этом в клетку записывается max возможное значение объема поставки. Затем из рассмотрения исключают строку, соотв. поставщику, запасы кот. полностью израсходованы, или столбец, соотв. потребителю, спрос кот. полностью удовлетворен.

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

В рез-те получаем опорный план, кот. должен содержать m+n-1 заполненных клеток. В процессе заполнения таблицы могут быть одновременно исключены столбец и строка. Тогда полученный опорный план будет вырожденным, т.к. не будет выполн-ся условие кол-ва занятых клеток m+n-1. В этом случае необх. в своб. клетку записать кол-во груза 0, условно считая эту клетку занятой («ноль-загрузка»). Число 0 записыв-ся в те свободные клетки, кот. не образуют циклов с ранее занятыми клетками. Циклом в матрице назыв-ся непрерывная замкнутая ломаная линия, вершины кот. находятся в клетках матрицы, а звенья расположены вдоль строк и столбцов. Если цикл образуется самопересекающейся ломаной, то точки ее самопересечения вершин не образуют. Число вершин в цикле д.б. четным; одна вершина -свободная клетка, остальные – занятые.

79 Транспортная задача: условия оптимальности опорного плана, метод потенциалов.

Методы решения транспортной задачи можно разбить на 2 группы:

1)методы последовательного улучшения опорного плана.

2) методы последовательного сокращения невязок.

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

Наиб. Эффективный метод 1-ой гр. Метод потенциала.

Приведем формулировку задачи двойственной к транспортной

Обозначим оценки ресурсов пунктов отправления как Ui i=1,m.

Оценки ресурсов пунктов потребления через Vj j=1,n

Прямая задача(ПЗ): Двойственная задача(ДЗ):

Min Z= ∑∑ Сij*Хij Max F= ∑аi +

∑ xij=аi i=1;m Ui+ Vj<= Сij

∑xij=вi j=1;n

Xij>=0 i=1;m j=1;n

Т.К. с-ма ограничений ПЗ имеет вид равенств, то на двойственной переменную условия не накладываются.

Пусть Х*- оптимальный план ПЗ тогда у*( Ui*, Vj*)-оптимальный план ДЗ.

На основании 1й теоремы двойственности(если одна из пары двойственных задач имеет оптим. решение, то и вторая также имеет оптим. решение, причём экстрем. значения их целевых функций совпадают ): Max F = Min Z

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

Учитывая случаи вырождения на основании второй теоремы двойт-сти получили признак оптимальности опорного плана транспортной задачи. Если план Х* оптимален, то ему соответствует с-ма условий:

Ui*+ Vj*= Сij, если Хij*>=0 Ui*+ Vj*<= Сij, если Xij* =0

Допустимый план транспортной задачи удовлетворяющий данном условию, называют потенциальным, а сами условия, условия потенциальности.

Потенциалы Ui и Мо приписываются каждому поставщику и потребителю. Общее кол-во потенциалов m+n , кол-во заполненных клеток в опорном плане m+n-1 . Для них выполняется условие Ui*+Мо*=Сij. Дан. условие служит уравнениями из которых находят значение потенциалов. Эта система уравнений имеет бесконечное множество решений, любое из которых составит искомую с-му потенциалов. Чтобы найти 1 решение, значение одного из потенциалов нужно выбрать произвольно. Остальные находятся из с-мы уравнений для заполненных клеток. Считают, что U1=0 и вычисляют остальные. Для каждой клетки вычисляем оценки Sij=Cij-(Ui+Vj). Если опорный допустимый план оптимален, то все Sij > =0. Если хоть одна отрицательная клетка, то план не оптимален, тогда в новый базисный план вводят клетку с минимальной оценкой Sij , дан. клетку наз-ют перспективной. Экономический смысл оценки Sij состоит в том, что она показывает на сколько можно уменьшить транспортные издержки при загрузке дан. клетки единицей груза. Для улучшения опорного плана, для перспективной клетки строится цикл, вершинам этого цикла приписываются знаки: свободной перспективной клетке знак + , следующей по часовой или против часовой стрелке клетки знак -, следующей + и т.д. В клетках с отрицательными вершинами выбирается минимальное кол-во груза α , которое будет перемещаться по циклу. Оно прибавляется к грузу в вершинах с положительным знаком и вычитается из поставок в отрицательных вершинах. В результате баланс транспортной задачи не нарушается.

Алгоритм метода потенциала:

1. Построить начальный опорный план по одному из способов.

2. вычислить потенциалы поставщиков и потребителей, решив с-му уравнений Ui+Мj=Сij

3. Вычислить оценки Sij для всех клеток транспортной задачи. Если все оценки Sij >= 0, то опор. план оптимален. Если для всех свободных клеток Sij>0 , то оптимал. план единственный. Если хоть для одной свободной клетки Sij=0, то имеется множество оптимал. планов с одним и тем же значением целевой функции.

4. В случае если есть Sij<0, то строится цикл, расчетная таблица заполняется заново и алгоритм начинается с пункта2.

Оптимальный план транспортной задачи яв-ся целочисленным. При любых целых значениях аi и bj задача имеет целочисленный оптимальный план независимо от коэффициентов целевой функции cij. Для док-ва достаточно проверить справедливость следующих двух предположений:

1.Исходный опорный план задачи целочисленен.

2. При переходе от одного опорного плана к другому целочисленность не нарушается Xij=min {ai ; bj} α=min{xij}.

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

1. При некоторых реальных условиях перевозки груза из определенного пункта отправления Аi в пункт назначения Bj не м.б. осуществлены. Для определения оптимальных планов таких задач предполагается, что тариф перевозки единицы груза из пункта Аi в пункт Вj яв-ся большой величиной М. далее решение задачи находят методом потенциала. При таком предположении исключается возможность перевозки груза по коммуникации(ij). Такой подход к решению задачи называется запрещением перевозок или блокированием клеток распределительной таблицы. 2. В отдельных транспортных задачах дополн. условием яв-ся обеспечение перевозки по соответствующим маршрутам определенного количества груза. Напр. Из пункта Ав пункт Вj требуется обязательно перевезти αij единиц груза, тогда в клетку распределительной таблицы, находящейся на пересечении i-й строки и j-го столбца записывают кол-во груза αij. При решении задачи эту клетку считают свободной со значением тарифа М. Полученный оптимальный план будет решением. 3. Иногда требуется найти решение транспортной задачи, при которой из пункта Аi в пункт Вj д.б. завезено не менее αij единиц груза. Для определения оптимального плана считают, что запасы пункта Аi и потребность пункта Вj меньше фактических на αij единиц.

4. В некоторых транспортных задачах требуется найти решение из условия , что из пункта Аi а пункт Вj перевозится не более чем Аij единиц. Тогда в таблице исходных данных для каждого такого j-го потребителя предусматривается дополнительный столбец. Матрица тарифов, такая же как и в первоначальном столбце bj, за исключением тарифа в i-й строке. Значение тарифа в этом случае равно большему положительному числу М. При этом потребность пункта Вj считается равной αij, а потребность введенного пункта назначения bj- αij.