Файл: Васильев, В. В. Гибридные модели задач оптимизации.pdf

тп

Очевидно, что при подобных конфигурациях транспортной сети и электронной цепи и выполнении масштабных соотношений

токи цепи будут пропорцио­ нальны оптимальным в смыс­ ле (3.5) объемам перевозок транспортной сети, а мощ­ ность (3.10) пропорциональна стоимости перевозок всего продукта, т. е.

Для схемы рис. 16, б спра­ ведливы также неравенства

ѵі "СУі + Е а.

причем напряжения ѵ{ и Vj пропорциональны переменным двойственной к (3.1) — (3.5) задачи, так называемым эко­ номическим потенциалам уз­

лов. Эти неравенства составлены в предположении идеальности характеристик диодов (нулевые — обратная проводимость и прямое сопротивление).

Приведенная выше транспортная задача является закрытой или сбалансированной вследствие выполнения условия (3.4). Анало­ гичное (3.4) условие в. электронной цепи (3.9) выполняется всегда, так как является записью первого закона Кирхгофа для замкнутой поверхности S. Поэтому при технических реализациях схем с регу­ лируемыми источниками тока необходимо предусматривать путь для тока

тп

определяемого установкой токов It и j) с погрешностями; в про­ тивном случае нормальные режимы работы для источников тока обеспечить невозможно. Одним из возможных способов выполнения этого требования является заземление одного из узлов схемы (на рис. 16, б пунктиром показано заземление узла п).

52-

Часто на практике возникает открытая или несбалансированная транспортная задача [168], для которой не выполняется условие (3.4). Рассмотрим особенности моделирования таких задач. Пусть

/= 1 Условие (3.15) может быть реализовано по крайней мере двумя

способами. Первый связан с моделированием неравенств (3.15) ди­ одными цепями. На рис. 17, а показана модель одного из пунктов производства, для которого справедливо указан­ ное выше ограничение. Пер­ вый закон Кирхгофа для узла і будет иметь вид

мом потребления, равным пре­ вышению производства над

ким образом задача формально сводится к сбалансированной. Фрагмент схемы электронной модели с фиктивным пунктом по­ требления показан на рис. 17, б. Электронная модель поз­ воляет найти оптимальный план перевозок и тогда, когда су­ ществуют приоритетные ограничения по вывозу продукта с опре­ деленных пунктов производства. В этом случае величины стоимости перевозки единицы продукта из пунктов производства в фиктивный пункт потребления будут неодинаковы, и в ветвях модели рис. 17, б с токами /,-ф должны быть включены различные по величине источ­ ники напряжения £Ѵф.

Совершенно аналогичный случай открытой транспортной задачи,

тп

когда 2 ай< 2 bj, сводящийся к появлению фиктивного пункта про-

1=1 У=1

изводства, можно не рассматривать.

53

Интересной разновидностью транспортной задачи является за­ дача с дополнительными ограничениями по вывозу продукта. Осо­ бенность ее заключается в следующем [168]. Пусть все пункты про­ изводства разбиты на группы так, что каждая группа обеспечивается одним предприятием с ограниченной мощностью, и поэтому появля­ ются дополнительные ограничения

где k — номер обеспечивающего предприятия; г — число обеспе­ чивающих предприятий; Nk — множество пунктов производства,

обеспечиваемых k-м предприятием; S k — максимальный объем производства пунктов производства fe-й группы, обеспечиваемой fe-м предприятием.

Фрагмент электронной модели для этого случая показан на рис. 18, а. С целью упрощения в первую группу включены первые три пункта производства N і = (1 , 2 , 3), во вторую ЛГ2 = (4, 5, 6 )

ив последнюю Nr = (т — 2, т — 1, т).

Вбольшинстве практических случаев транспортных задач вели­ чины перевозок ограничены пропускными способностями соответст­ вующих транспортных маршрутов, т. е. существуют дополнитель­ ные к (3.1) — (3.4) ограничения вида

54

Вэлектронной модели эти ограничения реализуются естествен­ ным образом путем включения в модель транспортной ветки огра­ ничителя тока (рис. 18, б).

Врассмотренных выше разновидностях транспортных задач предполагалось отыскание планов перевозок, минимизирующих сум­ марные транспортные издержки по системе вида (3.5).

Вряде случаев [168], например при перевозках скоропортящих­ ся продуктов или перевозках в условиях военного времени, опти­ мальными считаются перевозки, которые производятся в макси­ мально короткий срок с учетом или без учета минимума издержек (3.5). При этом наряду с величинами стоимостей перевозок еди­ ницы продукта по транспортным маршрутам сц должны быть за­ даны времена выполнения перевозок по тем же маршрутам хң, ко­ торые могут быть связаны с ctj или независимы от последних. Математически эта задача формулируется в виде (3.1) — (3.4) с целе­ вой функцией вида

Транспортная задача с целевой функцией (3.19) получила назва­ ние транспортной задачи по критерию минимума общего времени. Разновидностью этой задачи является транспортная задача по сме­ шанному критерию вида (3.1) — (3.5) с требованием, чтобы макси­ мальное время перевозки было меньше заданного значения:

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

Пусть на электронной модели линейной транспортной задачи получено оптимальное решение по критерию минимума транспорт­ ных издержек. Анализируя множество маршрутов с ненулевыми объектами перевозок N' {хц Ф 0), можно найти один или несколько маршрутов, для которых xtj максимально. Исключим из рассмотре­ ния маршруты транспортной сети k — I, для которых %k > т маКсНа электронной модели такое исключение можно осуществить путем разрыва соответствующих ветвей модели или вследствие значитель­ ного увеличения стоимости Сы- Электронная модель выдаст опти­ мальное решение задачи, но с выполнением наложенных ограничений Xki — 0. Проанализируем измененное множество маршрутов с не­

55

зом, мы на каждом его шаге будем получать оптимальные варианты перевозок со все меньшими значениями максимального времени перевозки, причем транспортная сеть, вследствие наложенных за­ претов, будет сокращаться. Нетрудно видеть, что на вполне опре­ деленном шаге исключение очередных ветвей с максимальным временем перевозки приведет к невозможности выполнения плана пе­ ревозок, т. е. выполнения соотношений (3.1), (3.2). Это будет сви­ детельствовать о том, что на предыдущем шаге получено оптималь­ ное в смысле (3.20) решение задачи.

Для определения момента получения оптимального решения на электронной модели необходимо предусмотреть индикацию наруше­ ния условий (3.1) и (3.2). На рис. 19 показана скелетная схема моде­ ли, позволяющая произвести индикацию такого нарушения. Нару­ шение условия (3.1) приведет к появлению тока /а, а нарушение условия (3.2) — к появлению тока 1Ъ. Величины напряжений источ­ ников Еа и Еь выбираются настолько большими, чтобы подключен­ ные к модели схемы индикаторов они были эквивалентны дополни­ тельным пунктам производства и потребления с неограниченными объемами производства и потребления, но стоимости перевозок из (в) этого (этот) дополнительного пункта были велики и приводили бы в обычных условиях к нецелесообразности перевозок ha, Іы-

3.2. АНАЛОГОВЫЕ МОДЕЛИ ЗАДАЧ О ПОТОКАХ В СЕТЯХ

Типичной задачей об оптимальном распределении потока в сети является сетевая транспортная задача. Узел транспортной сети будет ассоциироваться с пунктом производства при а{ > 0 , с перевалочным пунктом при а, = 0 и с пунктом потребления при а, < 0 .

Электронная модель транспортной задачи в сетевой постановке, основанная на использовании диодной аналогии Денниса, будет

56

представлять собой электронную цепь (рис. 2 0 , б), топологически1 подобную транспортной сети, в которой моделями транспортных коммуникаций (маршрутов) есть электрические двухполюсники вида, показанного на рис. 2 0 , а, а моделями узлов — источники, величи­ ны токов которых пропорциональны объемам продукта, вывозимого из узла или привозимого в узел. На рис. 20, а показана модель двух­ направленной ветви, величины потоков по которым ограничены с двух сторон. При этом, естественно, предполагается, что система* величин mtj, Мц, щ совместима

с ограничениями, накладываемыми на модель сети первым законом Кирхгофа, так как в противном слу­ чае задача не может иметь решения.

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

чае сетевой транспортной задачи эти напряжения будут опреде­ ляться величинами вида ± ус 2 сц. Это приводит к необходи­

м ее мости построения источников тока, обладающих идеальной внешней,

(нагрузочной) характеристикой в широком диапазоне напряжений,

своей постановке отличается от общей задачи об оптимальном рас­ пределении потока в сети тем, что отсутствует требование миниму­

57

а максимизируемой величиной является количество продукта (величина потока), вывозимое из первого узла (пункта):

т. е. ставится задача определения максимально возможного потока из первого узла сети в узел'N, совместимого с ограничениями про­ пускных способностей ветвей и узлов сети.

Электронная модель задачи о максимальном потоке сети, опи­

Между полюсами этой цепи / и N подключается идеальный источ­ ник напряжения Е (рис. 21). В соответствии с экстремальным прин­ ципом для цепей, токи в цепи распределяются таким образом, что мощность этого источника Р = E J будет максимально возможна среди значений. Так как Е = const и

в соответствии с первым законом Кирхгофа, то величина тока J будет моделировать значение искомого максимального потока.

Аналогично можно построить электронную модель обобщенной задачи о максимальном потоке, состоящей в определении макси­ мально возможного количества продукта из г пунктов Р с в I пунктов

Соответствующая схема электронной модели приведена на рис. 2 2 . Задача об экстремальном (минимальном или максимальном) пу­ ти [189, 191, 193] возникает, когда необходимо определить маршрут оптимальной перевозки всего одной единицы потока из пункта в

58