Эквивалентное преобразование. Условия оптимальности

1037
0
15 мая 2009
Основное внимание уделяется определению критерия параметра оптимальности в соответствии с наличием определенных требований и условий.
Разберем преобразование функции цены22_html_m2cd7cb46.gif, от которого не зависит оптимальность потока.

Предположим, что22_html_240d0fde.gifявляется случайным числом, которое определяется для всякой вершины сети. Значение функции цены каждой заходящей в вершину22_html_68e154f9.gifдуги увеличим на22_html_m23cf4ed9.gifи отнимем это же число из стоимости каждой исходящей дуги. Иными словами, вместо22_html_me2f755c.gifбудем работать с функцией22_html_m18aacbb1.gif. Для произвольного потока22_html_m6d6d7ad9.gifхарактерно

 

22_html_14a0d837.gif

 

Очевидно,

 

22_html_m3e018779_show.gif

 

Итак, для всякого потока значение функционала цели начальной задачи не эквивалентно значению функционала задачи, для которой было осуществлено преобразование. Разница между значениями равна постоянной величине 22_html_2dad88e6.gif. Следовательно, при использовании обозначенного преобразования, решение задачи останется прежним.

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

Утверждение 6.4. Оптимизация потока22_html_m6d6d7ad9.gifзависит от требования — чтобы каждой вершине22_html_6985b4ad.gifбыло представлено такое число22_html_1eca36bf.gif, что

 

22_html_1e8ad21c.gif

 

Следует отметить, что значения22_html_1eca36bf.gifопределены с точностью до постоянного слагаемого. Они являются неотрицательными. При условии, что22_html_m60fb43a7.gif сущность утверждения 6.4 будет заключаться в следующем.

Утверждение 6.5. Оптимальность потока22_html_m23cf4ed9.gif, что

 

(6.20)

22_html_m648daf5d.gif

 

Значения 22_html_m23cf4ed9.gif, а ценами — числа22_html_1eca36bf.gif. Лучше всего эти числа называть узловыми.

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

Представим доказательство дополнительному утверждению.

Утверждение 6.6. Для всякого потока22_html_m6d6d7ad9.gifи таких чисел22_html_1eca36bf.gif,22_html_7af1218.gif, для которых

 

(6.21)

22_html_m51f56fa5.gif

 

справедливо неравенство

 

(6.22)

22_html_m51609003.gif

 

Неравенство (6.12) характеризует функционал цели снизу. Если для некоторого потока действительно выполняется равенство, то такой поток можно назвать оптимальным. Сейчас представим доказательство утверждения 6.4.

Допустим, что для потока22_html_m8379e2e.gifвыполняются условия (6.20), это означает, что определены числа22_html_m7e82c2cb.gif, для которых

 

22_html_19226ee8.gif

 

Следовательно, представляется возможным определение таких чисел 22_html_3c95f470.gif, что

 

22_html_401cdb7d.gif

 

Числа 22_html_m4df84b08.gifудовлетворяют условиям утверждения 6.6. Тем не менее, учитывая, что 22_html_m54ca151.gifпри22_html_2a05131d.gif, уместно следующее выражение

 

22_html_1bdd1fb0.gif

 

Итак, в соответствии с утверждением 6.6, для потока22_html_m8379e2e.gifможно представить как оптимальный поток. Подобным образом может быть доказано противоположное утверждение: если поток22_html_m8379e2e.gifявляется оптимальным, то существуют цели-потенциалы, которые удовлетворяют условиям (6.20).

Через22_html_m50b4f89a.gifпредставим множество дуг22_html_m4139866b.gif, которые подразумевают

 

22_html_m9769e2.gifили 22_html_m5c6ff5ca.gif

 

Разберем частичный граф22_html_3be5887a.gif.

При построении вершин сети учтем следующее.

Для случайной вершины22_html_m5c4d7a25.gifположим22_html_6d424f5c.gif. При условии, что для вершины22_html_6c05095e.gifхарактерно22_html_6533636b.gif, то

 

22_html_31bd9efe.gif,

 

а при условии, что22_html_m3c238950.gif, то

 

22_html_4bd56d0c.gif

 

Найдя потенциал некоторой вершины22_html_68e154f9.gifграфа22_html_m597d98ce.gif, подобным образом можно определить потенциал всех смежных вершин 22_html_4ae7ac2d.gif, где он еще неизвестен.

При22_html_m2ccf5fce.gif, то

 

22_html_3d8c85c7.gif

 

При22_html_m2ccf5fce.gif, то

 

22_html_m24ebb1d6.gif

 

Поскольку граф22_html_m597d98ce.gifявляется связным, то можно найти потенциал для каждой вершины сети. Представим доказательство — новые потенциалы удовлетворяют условиям (6.20).

Пусть существует дуга 22_html_m5c4d7a25.gifи22_html_m5c4d7a25.gifцепью, с помощью которой был найден потенциал22_html_m5c4d7a25.gifцикле вида

 

22_html_500a55a.gif

 

здесь 22_html_m4d9c9ea6.gifили 22_html_1c9eb1ce.gif.

Допустим, что22_html_m71cb4397.gif Через 22_html_m58c6c858.gifпредставим множество дуг22_html_m1b0698e6.gif, направление которых обозначено в обход цикла, а через22_html_m1b0698e6.gif, ориентация которых предполагает обратное направление. Запишем функцию22_html_m37fc18ee.gif так:

 

22_html_5f8ee696.gif

 

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

 

22_html_m6e08b9e1_show.gif

 

что не соответствует оптимальности22_html_3be5887a.gif.

При условии, что22_html_m39762530.gif, следует разобрать функцию

 

 

22_html_m10117deb.gif

 

Здесь22_html_3be5887a.gif. Итак,

 

22_html_51066277_show.gif

 

а это снова не соответствует оптимальности22_html_3be5887a.gif.

Итак,

 

22_html_m7c80a9d.gif

 

Предположим, что имеется дуга22_html_64dffde5.gifпредставляется возможным осуществить соединение с помощью цепи вершин22_html_m77f1d7ba.gif,22_html_m7818696f.gifи22_html_ec64d8e.gifпринадлежит проходящему через22_html_7ecddeb2.gifциклу вида

 

22_html_m38fceb0a.gif

 

здесь 22_html_m4d9c9ea6.gifили22_html_1c9eb1ce.gifпри 22_html_1ce06bba.gif.

В очередной раз разберем множества 22_html_ec64d8e.gif, которая предполагает, что

 

22_html_m20c93b0c.gif

 

или

 

22_html_6095867d.gif

 

Для обоих случаев представляется возможным, действуя по аналогии с предыдущим пунктом доказательства, ввести соответствующие функции22_html_m8379e2e.gif.

 



(38.4.) Сформулируем понятие конечного автомата, обозначим входной алфавит, выходной алфавит, алфавит состояний, функцию переходов, функцию выходов, на рисунке изобразим граф переходов.
3035 0
(38.3.) Большинство графов, которые используются в приложениях (например, графы сортировок, классификаций) предполагают наличие диаграмм, именуемых деревьями. Связный неориентированный граф без циклов, в частности, предполагающий отсутствие петель и кратных ребер, именуют деревом. Несвязный неориентированный граф без цикла — лес, его связные компоненты являются деревьями.
8224 0
(38.2.) В рамках обозначенной темы рассмотрим случай определения связного неориентированного мультиграфа в качестве эйлерова и гамильтонова графа.
11130 0

    Вы должны авторизоваться, чтобы оставлять комментарии.

    При использовании материалов данного сайта прямая и явная ссылка на сайт radiomaster.ru обязательна. 0.2280 s