Метод потенциалов решения ТЗ.

Если опорный план Х=(хij) транспортной задачи является оптимальным, то существуют потенциалы поставщиков ui, i = 1, ….., m и потребителей vj, j=1,….,n, удовлетворяющие условиям :

ui+vj = cij при xij > 0 (для занятых клеток), (2.2)

Δij = ui + vj – cij ≤ 0 при xij = 0 (для свободных клеток) (2.3)

Условия (2.2) образуют систему с m+n неизвестными ui, vj и, в общем случае, m+n -1 уравнений. Так как число неизвестных системы на единицу больше числа уравнений, то одну из неизвестных можно задать произвольно, а остальные найти из системы.

 

8. Оценки опорного плана. Условия оптимальности опорного плана.

Числа Δij = ui + vj – cij называют оценками свободных клеток. Таким образом, согласно теореме: Если опорный план Х=(х ij ) транспортной задачи является оптимальным, то существуют потенциалы поставщиков ui , i = 1, ….., m и потребителей vj , j =1,…., n , удовлетворяющие условиям :

ui + vj = cij при xij > 0 (для занятых клеток), (2.2)

Δ ij = ui + vj – cij ≤ 0 при xij = 0 ( для свободных клеток) (2.3)

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

9. Цикл. Перестановка по циклу.

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

В таблице выбираем свободную клетку с максимальной положительной оценкой и формируем цикл, одной из вершин которого является выбранная клетка, а остальные клетки занятые. Кроме того, сопоставим каждой вершине цикла знак и перевозку, при этом свободной клетке сопоставляем знак «+», а для остальных клеток знаки чередуются. Дальше делаем перестановку по циклу, а именно: из всех вершин, отмеченных минусом, вычтем минимум из всех перевозок, означенных этим знаком, т.е вычитаем Δ, а ко всем вершинам с «+» прибавим Δ. Таким образом с помощью цикла получаем новый опорный план.

 

10.  Открытая модель ТЗ. Сведения открытой модели к закрытой.

Транспортная задача m*n называется задачей с неправильным балансом, а её модель

открытой, если:                                 m         n

å ai ≠ å bj

                                                                            i=1     j=1

т.е суммарные запасы не равны суммарным потребностям.

Открытую задачу можно свести к закрытой:

1) Если: m   n

     åai >åbj , то вводят фиктивного потребителя Вn+1, с потребностью

                        i=1      j=1  

 

                           m      n

   b n+1 =  åai -å bj и нулевыми тарифами перевозок в столбце.

                   i=1   j=1

 

2) Если: m        n

     åai < åbj , то вводят фиктивного поставщика Аm+1, с запасом

                        i=1   j=1  

 

                           n      m

   a m+1 =  åbj -å ai и нулевыми тарифами перевозок в строке.

                   i=1   j=1

 

 

11.  Фиктивные потребитель и поставщик.

1) Если: m   n

          åai >åbj , то вводят фиктивного потребителя Вn+1, с потребностью

                               i=1  j=1  

 

                           m      n

   b n+1 =  åai -å bj и нулевыми тарифами перевозок в столбце.

                   i=1   j=1

 

2) Если: m        n

          åai < åbj , то вводят фиктивного поставщика Аm+1, с запасом

                               i=1   j=1  

 

                           n      m

   a m+1 =  åbj -å ai и нулевыми тарифами перевозок в строке.

                   i=1   j=1

 

Дополнительные ограничения в транспортной задаче.

1) Если в закрытой транспортной задаче перевозки от поставщика Аi к потребителю Bj не могут быть осуществлены (блокировка), то для определения оптимального решения задач предполагают, что тариф перевозки единицы груза от Ai к Bj равен сколь угодно большому числу М.

2) Если дополнительным условием в транспортной задаче является обеспечение перевозки от поставщика Ai к потребителю Bj в точности aij единиц груза, то в клетку AiBj записывают указанное число aij, а эту клетку считают свободной со сколь угодно большим тарифом М.

3) Если от поставщика Аi к потребителю Bj должно быть перевезено не менее aij единиц груза, что запасы пункта Ai и потребности пункта Bj полагают меньше фактических на aij единиц. После нахождения оптимального плана перевозку, стоящую в клетке AiBj, увеличиваются на aij единиц.

4) Если от поставщика Ai к потребителю Bj требуется перевезти не более aij единиц груза, то вводят дополнительного потребителя Bn+1 = Bij, которому записывают те же тарифы, что и для Bj, за исключением тарифа в i-й строке, который считают равными сколь угодно большому числу М. Потребности пункта Bj считают равными aij, а потребности Bij полагают равными bj-aij.

Постановка задачи многокритериальной оптимизации.

Задача вида

fi (x) -> max (min)

x ÎD

где, I>1, DÎR n – допустимое множество, а f i(x) – гладкие функции на D, называется задачей многокритериальной оптимизации.