16.Достаточное условие минимальности стоимости перевозок

Выпишем ограничения ТЗ

=

=

…………………………………………………………………..

+ =

+ + … + =

…………………………………………………………….

+ + + … + =

Умножим эти ограничения на вектора , и полученное выражение вычтем из целевой функции (1)

Величины называются потенциалами соотв. ограничениям-строкам, - потенциалами, соотв. ограничениям-столбцам.

Подстав. в рав-во (1) значение начального плана перевозок. Если является небазисной т.е. =0, то соотв. слагаемое в (1) =0. Если же базисная, то для невырожденного плана >0, но тогда коэф-т положим =0 путем выбора потенциалов. =0, , поэтому для нахождения потенциалов можно любой из потенциалов положить =0 а остальные определить из системы линейных уравнений в кол-ве . Вычислим величины по небазисному множеству клеток.

Т. Выполнение нер-ва по небазисному множеству клеток (i,j) является достат. для оптимальности плана перевозок.

Док-во. Из рав-ва (1) следует, что если значения небазисных перевозок для которых >0 изменить на положит., то ст-ть перевозок увеличится. С другой стороны, если существует <0, (i,j) , то путем увеличения соотв. значения перевозки с нулев. на положит. стоимость перевозок можно уменьшить.

Изменяя знач. Небазисной перевозки, для кот. <0 необходимо изменить другие значения базисных перевозок т.о. чтобы выполнялись все ограничения задачи и кол-во базисных перевозок осталось равным .

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

1. Проверит условие баланса. В случае открытой модели ввести фиктивного поставщика или потребителя.

2. Заполнить транспортную таблицу.

3. Составить начальный план перевозок.

4. Вычислить потенциалы по базисному множеству клеток

5. Вычислить по . Проверить достаточное условие оптимальности.

6. Найти min , если <0, (i,j) . Начиная с выбранн. клетки по базисному мн-ву строится цикл. Этот цикл дает возможность построить новый план перевозок. Перейти к п.4

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

(1) (2)

Если функция является выпуклой на выпуклом множестве X, то задача (1), (2) называется задачей выпуклого программирования.

Опр: Мн-во наз выпуклым, если для любых двух точек отрезок, соединяющий эти точки полностью принадлежит этому множеству, т.е. Опр: Функция , определенная на выпуклом множестве Х, называется выпуклой, если для выполняется

Т1: Пусть функция является выпуклой, дифференцируемой на выпуклом множестве Х, тогда выполняется

Док-во: Т.к. функция является выпуклой, то .

Т.к. функция является дифференцируемой, то приращение этой функции можно разложить в ряд Тейлора:

(!!!!!)= Последнее неравенство делим на и устремим к 0. Т.док-на.

Замечание: Теорема1 называется свойством неотрицательности остатка.