Методы оптимальных решений

 

 

 

 

В полученной двойственной задаче n·m ограничений, соответствующих каждой переменной x_ij ТЗ. Вспоминая, что невязка между левой и правой частью в ограничений двойственной задачи есть оценка для соответствующей переменной исходной задачи , запишем условия оптимальности текущего плана перевозок в ТЗ:

 

Неизвестные потенциалы u_i и v_j (их общее количество равно m + n) могут быть найдены (и именно так отыскиваются) из условия равенства нулю оценок для базисных переменных (заполненных клеток таблицы) ТЗ (таких равенств (m+n - 1), что следует из замечания ниже).

 

 

 

для заполненных клеток (i,j) таблицы ТЗ.

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

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

ШАГ 1. Построение начального плана перевозок.

ШАГ 2. Проверка текущего плана  на оптимальность.

Если план оптимален, то алгоритм завершен.

ШАГ 3. Улучшение плана  перевозок. Переход к шагу 1.

Опишем алгоритм по шагам, иллюстрируя каждый шаг

ШАГ 1. Построение начального плана перевозок.Построение начального решения (как и последующие расчеты) проводят в таблице, имеющей следующий вид:

 

 

цены перевозок
			n-столбцов
запасы	1	120	5	10	12	m-строк
	2	70	8	6	4
	3	50	0	0	0
			60	100	80
			1	2	3
			потребности

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Метод штрафных функций

 

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

Легко  увидеть,  что  можно  построить  различные  функции,  удовлетворяющие  этому  определению.  Например,  самой  простой  штрафной  функцией  может  служить  следующая  функция, где   – некоторая  положительная  константа.  Эта  функция  имеет  недостатки,  затрудняющие  использование  ее  на  практике:  она  не  является  непрерывной,  и  величина  штрафа  не  зависит  от  величины  нарушения  ограничений,  задающих  множество  .  Учитывая  информацию  о  системе  ограничений,  определяющих  ,  можно  построить  штрафные  функции,  лишенные  этих  недостатков.

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

Линейная  комбинация  нескольких  штрафных  функций с  положительными  коэффициентами  также  является  штрафной  функцией.

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

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

Доказательство. Тогда по  теореме Куна-Таккера  найдётся  вектор    такой,  что   – седловая  точка функции Лагранжа.

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

 

Применение методов штрафных функций

 

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

Параметрические методы характеризуются  наличием одного или нескольких надлежащим образом подобранных параметров, входящих в структуру штрафной функции (которая строится с помощью функций-ограничений) в качестве весовых коэффициентов. К числу типичных параметрических  методов относится метод последовательной безусловной минимизации (МПБМ), предложенный Фиакко и Мак-Кормиком, а также метод Зангвилла. С другой стороны, в непараметрических методах, таких как "метод центров" Гуарда и предложенный Фиакко и Мак-Кормиком непараметрический МПБМ, целевая функция рассматривается как функция, задающая дополнительное искусственное ограничение, постепенно "уплотняемое" по мере получения информации в ходе решения задачи.

Параметрические методы распадаются  на три категории:

1) методы внутренней точки;

2) методы внешней точки;

3) комбинированные методы.

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

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

J(u)->inf; uU (1)к последовательности задач минимизации k(u)->inf; u U0, k=0,1,…, (2)

где k(u) - некоторая вспомогательная функция, а множество U0 содержит U.

При этом функция k(u) подбирается так, чтобы она с ростом номера k мало отличалась от исходной функции J(u) на множестве U и быстро возрастала на множестве

 

U0\U.

 

Можно ожидать, что быстрый  рост функции k(u) вне U приведет к тому, что при больших k нижняя грань этой функции на U0 будет достигаться в точках, близких ко множеству U, и решение задачи (2)будет приближаться к решению задачи (1). Кроме того, как увидим ниже, и меняться достаточно широкий произвол в выборе функций k(u) и множества U0 для задач (2), и можно надеяться на то , что задачи (2) удастся составить более простыми по сравнению с задачей (1) и допускающими применение несложных методов минимизации.

Определение 1: Последовательность функций

 

{Рk(u), k=0,1,..},

 

определенных и не отрицательных  на множестве U0, содержащем множество U, называют штрафом или штрафной функцией множества U на множестве U0, если

Из этого определения  видно, что при больших номерах  k за нарушение условия uU приходится "платить" большой штраф, в то время как приu

U штрафная функция представляет собой бесконечно малую величину при k->. Для любого множества UЕn можно указать сколько угодно различных штрафных функций.

Например, если {Аk} - какая-либо положительная последовательность, Аk, то можно взять

 

Рk(u)= Аk(u,U), uEnU0, k=0,1,…

 

(здесь U предполагается замкнутым) или

здесь (u,U)=|u-v| - расстояние от точки до множества U, а - какая либо точка из U.

 Другие примеры штрафных  функций будут приведены ниже. Допустим, что некоторое множество  U, содержащее U,а также штрафная функция {Р(u)} множества U на U0 уже выбраны . Предполагая, что функция J(u) определена на U0, введем функции

 

(u)=J(u)+P(u), uU0, k=0,1,... (3)

 

и рассмотрим последовательность задач (2) с функциями (3). Будем считать,

 

что =(u)>-, k=0,1,…

может и не достигаться. Поэтому  будем считать, что при каждом k=0,1,… с помощью какого-либо метода минимизации найдена точка uk, определяемая условиями:

 

ukU0, (uk) (6),

 

где - некоторая заданная последовательность, , k=0,1,…, (если uk удовлетворяет условиям (5), то в (6) допускается возможность =0). Отметим, что, вообще говоря, ukU. Метод штрафных функций описан. Дальнейшее изложение не зависит от того, каким конкретным методом будет найдена точка

 

uk из (6).

 

Поэтому мы здесь можем  ограничиться предположением, что имеется  достаточно эффективный метод определения  такой точки.