Практическое применение ГИС: решение задачи коммивояжера. 3 страница

Термин «дерево» подразумевает формирование иерархической структуры (см.), получаемой расчленением общей цели на под­цели, а их - на более детальные составляющие, для наименования которых в конкретных приложениях используют разные назва­ния: направления, проблемы, программы, задачи, а начиная с не­которого уровня - функции.

Такая процедура получила в последующем название струк­туризации (см.) цели.

Как правило, термин «дерево целей» используется для древо­видных иерархических структур (см.), имеющих отношение строго древовидного порядка, но иногда применяется и в случае «слабых» иерархий (см. Структура). Поэтому более правильно для наз­вания структур целей было бы использовать термин В.М. Глушко-ва «прогнозный граф» [2]. Однако в силу истории возникновения терминов более распространен исходный термин «дерево целей».

Термин «дерево целей» в конкретных приложениях заменяют более удобными для этих приложений терминами: в ситуациях принятия решений применяют термин «дерево решений»; при вы­явлении и уточнении функций системы управления говорят о «де­реве целей и функций» [3, 4]; при структуризации тематики науч­но-исследовательской организации пользуются термином «дерево проблемы», а при разработке прогнозов - «дерево направлений развития (прогнозирования развития)» или «прогнозный граф» [2].

Поэтому в настоящее время более распространено понятие «методы типа «дерева целей».

Метод «дерева целей» ориентирован на получение полной и относительно устойчивой структуры целей, проблем, направле­ний, т.е. такой структуры, которая на протяжении какого-то пе­риода времени мало изменялась бы при неизбежных изменениях, происходящих в любой развивающейся системе. Для достижения этого при построении вариантов структуры следует учитывать закономерности целеобразования (см.) и использовать принципы и методики формирования структур целей и функций или мето­дики структуризации целей и функций (см.).

• 1. Волкова В.Н. Основы теории систем и системного анализа: учеб. для
вузов / В.Н. Волкова, А.А. Денисов. - СПб.: Изд-во СПбГТУ, 1997. Изд. 2-е.,
1999.-С. 133-134.2. Методика совместного прогнозирования заинтере­
сованными странами-членами СЭВ развития науки и техники. - М.: Меж­
дународный центр НТИ, 1975. 3. Основы системного подхода и их при­
ложение к разработке территориальных АСУ/Под ред. Ф.И. Перегудова. -
Томск: Изд-во ТГУ, 1976.4.Перегудов Ф.И. Введение в системный ана­
лиз: учеб. пос. / Ф.И. Перегудов, Ф.П. Тарасенко. - М.: Высш. школа, 1989.
5. Системный анализ в экономике и организации производства: учеб.
для вузов / Под ред. С.А. Валуева, В.Н. Волковой. - Л.: Политехника, 1991.
- С. 90-91.6. Черчмен У. Введение в исследование операций / У. Черчмен
и др. - М.: Наука, 1968. 7. Я н ч Э. Прогнозирование научно-технического
прогресса / Э. Янч. - М.: Прогресс, 1974. В.Н. Волкова

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ - раздел теории оптимизации, посвященный исследованию и решению экстре­мальных задач специального вида, в которых целевая функция (целевой функционал) имеет вид суммы слагаемых (соответствен­но - интеграла). В основе метода динамического программиро­вания лежит идея разбиения исходной задачи на последователь­ный ряд более простых задач. Основной областью приложения динамического программирования являются многошаговые про­цессы, т.е. процессы, протекающие во времени (дискретном или непрерывном).

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

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

Основные особенности дискретной модели динамического программирования состоят в следующем:

1) задача оптимизации интерпретируется как многошаговый процесс управления;

2) общая целевая функция равна сумме целевых функций для каждого шага;

3) выбор управлений х_к на к-м шаге определяется только со­стоянием системы S_k__{ на предыдущем шаге и не зависит от со­стояния системы на более ранних этапах управления;

4) состояние S_k на к-м шаге зависит только от предшествую­щего состояния S^i и управления х_к, принимаемого на данном шаге, т.е.

где /_к - заданная векторная функция соответствующих переменных, к = 1, 2,..., в,...

Схематически модель динамического программирования ил­люстрируется следующей схемой:

_5o_JL_>s,^2->S₂-^->... s^-Sl.^ _итд>

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

Следует иметь в виду, что принцип Беллмана справедлив толь­ко для задач, у которых целевые функции можно описать в виде аддитивных функций от траектории, т.е. для процессов с опреде­ленной структурой зависимости управлений.

Это означает, что критерий оптимальности (целевая функция) F имеет вид

И

F = F(S_a,x_],S....... £)= E<P*№t-b**).

^v ' " k=l

где числовая функция q>_k оценивает качество управленческого решения на к-м шаге.

Оптимальное управление удовлетворяет следующему прин­ципу оптимальности Беллмана: предположим, что, осуществляя управление, уже выбрана последовательность оптимальных уп­равлений х_{, х₂,..., х на первых р шагах, которой соответствует последовательность состояний (т.е. траектория) S_v S₂, ■•■, S. Требуется завершить процесс, т.е. выбрать х_+[,..., х_п(а значит, и 5,,..., S_n). Тогда если завершающая часть процесса не будет максимизировать функцию

П

^Fp+\= X Ф*(⁵*-1»**)> П)

к=р+1 ^К '

то и весь процесс управления не будет оптимальным. В част­ности, при р = п - 1 получаем требование максимизации функции

^п ~ Ф_и(^д-|' *")' зависящей от переменной х_п.

На основе принципа оптимальности Беллмана строится сис­тема рекуррентных соотношений (уравнения Беллмана):

4h-iW = 0. ₍₂₎

^w^-i) = ^maxW⁵^h x) + (o_fr+1(4 (S_A_p *))], к = п, п - 1,..., 1,

Х

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

Максимум в правой части равенства (2) берется по всем уп­равлениям х, допустимым на шаге к. Тем самым при вычислении w*(S_t_i) на каждом шаге приходится решать семейство задач мак­симизации функции переменной х, зависящих от состояния S_kA на предыдущем (к-\)-м шаге. При этом величина o),(s₀) есть оп­тимальное значение критерия оптимальности.

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

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

• 1. Б е л л м а н Р. Динамическое программирование; пер. с англ. / Р. Белл-ман. - М.: Иностр. лит., 1960.2. Беллман Р. Динамическое программиро­вание и современная теория управления / Р. Беллман, Р. Калаба. - М.: Наука, 1969. 3. Исследование операций в экономике / под ред. Н.Ш. Кремера. -М.: Банки и биржи, ЮНИТИ, 1997. 4. Н о г и н В. Д. Основы теории оптими­зации/В.Д. Ногин и др. -М.: Высшая школа, 1986. 4. Рихтер К. Динами­ческие задачи дискретной оптимизации / К. Рихтер. - М.: Радио и связь, 1985.

В.А. Кузьменков, В.Д. Ногин

ДИСКРЕТНАЯ МАТЕМАТИКА - это класс методов математи­ки, сформировавшийся в последней четверти XX в.

Вообще-то дискретные модели в математике существовали всегда. С них математика начиналась. Дискретные составляющие занимают большую часть в арифметике, алгебре, геометрии.

В то же время есть некоторые принципиальные особенности, которые привели к вычленению этих составляющих и формирова­нию дискретной математики как самостоятельного направления.

Исходным материалом для формирования этого направления явились комбинаторные знания.

Элементарная комбинаторика, характерная для древней мате­матики, включала: фигурные числа, «магические» квадраты, гно­моны, комбинаторные правила отыскания многоугольных фигур­ных чисел, формировании числовых магических квадратов и т.п. Позднее появились матричные построения, правила подсчета числа сочетаний, перестановок, размещений с повторениями и т.п.

Все эти результаты элементарной комбинаторики развивались первоначально в рамках теории чисел.

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

Другим важным направлением математики, которое в насто­ящее время является основой объединения не только направле-

ний дискретной математики, но и основой новой трактовки мно­гих математических понятий, является теория множеств (см. Те­оретико-множественные представления).

Создателем теории множеств считается представитель немецкой шко­лы математиков Г. Кантор (Georg Cantor, 1845-1918), который препода­вал в Галле с 1869 по 1905 г. Его работа «Основы общего учения о много­образии» («Grundlagen einer allgemeinen Mannigfaltigkeitslehre») была издана в 1883 г.

Независимо от Кантора теорию бесконечных множеств создал чеш­ский математик Б. Больцано (Bernhard Bolzano, 1781-1848), но его идеи были опубликованы позднее, после смерти.

В теории множеств есть ряд понятий {безразмерное множество, кон­тинуум, появление нового смысла при помещении рядом элементов из разных исходных множеств, парадоксы), которые отличают теорию множеств от классической математики. Поэтому теория Кантора не сразу была принята. Математики первоначально отказывались включить те­орию множеств в состав математики.

Для признания теории множеств полноправным математическим направлением много сделала группа французских математиков, рабо­тавшая под псевдонимом Н. Бурбаки [1].

В XIX в. параллельно с теорией множеств стали развиваться математическая логика, математическая лингвистика, теория гра­фов, а в XX в. - и семиотика.

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

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

настоящее время обозначают возникшие независимо разделы ма­тематики - теорию множеств, комбинаторику, математическую логику, математическую лингвистику, семиотику, теорию графов.

Каждое из указанных направлений имеет свою историю. Но обобщающий аппарат теоретико-множественных представлений сказался удобным средством пояснения основных понятий, а час­то - и доказательства теорем в математической логике, математи­ческой лингвистике и даже в теории графов, и постепенно все эти методы стали объединять в единую область - дискретную матема­тику [5-8].

В настоящее время на базе дискретной математики развивает­ся ряд прикладных направлений кибернетики и теории систем -от разработки методов кодирования-декодирования информации до синтеза схем и некоторых классов управляющих систем [8].

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

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

В принципе для отражения в алгоритме эвристик допустимы любые неформальные отображения. Однако такие эвристические алгоритмы широкого класса - от ГСН-алгоритмов (ГСН - «гру­бая сила и невежество») до «хитрых», «жадных» и аналогичных алгоритмов (название их соответствует виду эвристики, опреде­ляющей способ борьбы с перебором при моделировании реше­ния) - часто оказываются далеко не эффективными. И здесь боль­шую помощь в предварительной оценке реализуемости алгоритма, во введении некоторых формальных правил преобразования, по­зволяющих применить ЭВМ и ускорить получение решения, мо­гут оказать методы дискретной математики.

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

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

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

Для прикладных целей удобны справочные материалы, что и делается в [2-4] и в статьях данного издания по названным на­правлениям в форме таблиц, в которых собраны основные отно­шения теории множеств, функции и теоремы математической логики и т.д.

• 1.БурбакиН. Теория множеств / Н. Бурбаки. - М.: Мир, 1965. 2. В о л -
к о в а В.Н. Методы формализованного представления'(отображения) систем:
текст лекций / В.Н. Волкова, Ф.Е. Темников. - М.: ИПКИР, 1974. - С. 43-55.
3. Волкова В.Н. Методы формализованного представления систем: учеб.
пос. / В.Н. Волкова, А.А. Денисов, Ф.Е. Темников. - СПб.: Изд-во СПбГТУ,
1993. - С. 51-60. 4. Волкова В.Н. Основы теории систем и системного
анализа: учеб. для вузов / В.Н. Волкова, А.А. Денисов. - СПб.: Изд-во
СПбГТУ, 1997.-С. 109-117. 5.Горбатов В.А. Основы дискретной мате­
матики /В.А. Горбатов.-М.: Высш. школа, 1986. 6. Кузнецов О.П. Дис­
кретная математика для инженеров / О.П. Кузнецов, Г.М. Адельсон-Вельс­
кий. - М.: Энергоатомиздат, 1988. 7. Москинова Г.И. Дискретная
математика. Математика для менеджера в примерах и упражнениях: учеб.
пос. /Г.И. Москинова. -М.: Логос, 2000. 8. Я б л о некий СВ. Введение в
дискретную математику: учеб. пособие / СВ. Яблонский. - М.: Высшая шко-
ла, 2001. В.Н.Волкова

ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ - раздел теории оп­тимизации, посвященный исследованию и решению экстремаль­ных задач минимизации (максимизации) функции нескольких переменных на конечном или бесконечном дискретном подмно­жестве точек конечномерного векторного пространства. В слу­чае конечного допустимого множества число его элементов обыч­но настолько велико, что их прямой перебор с целью поиска экстремума оказывается практически нереализуемым.

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

Каноническая задача целочисленного линейного программи­рования в матричной форме записи имеет вид:

'С(Х) = (С,Х)^>тях.

Ах = Ь xj>0

Xj- целые числа, j=l,2,...,n Здесь A^Ot,,*,,•••,*„) есть вектор переменных, принимающих

п

целые значения; (С, X) = ll^ci^xi - скалярное произведение векто-

1=1

ра С~(Су, с₂,..., с_п) на вектор X; А=(а.) - матрица системы огра­ничений размера т х п; Ъ - вектор размерности т свободных членов системы ограничений.

Если j = 1,л,, где п₁ < и, то соответствующая задача называ­ется частично-целочисленной, при этом (л - л,) переменных могут принимать любые вещественные значения.

В задачах дискретного программирования переменные при­нимают дискретные вещественные значения.

Много экономических задач содержат целочисленные пере­менные. Эти задачи имеют устоявшуюся классификацию.

1. Задачи с неделимостями. Сюда относятся задачи планиро­вания дискретного производства, например планирование выпус­ка станков, турбин, морских судов, атомных реакторов и т.д.;

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

Классический пример задачи с неделимостями - задача о ран­це, которая формулируется следующим образом^ Имеется п пред­метов, объем каждого предмета равен v., i = l,n, объем ранца - V, Cj - ценность Лго предмета. Все предметы не помещаются в ранец. Требуется определить такой набор предметов, которые следует поместить в ранец, чтобы при этом их суммарная цен­ность была максимально возможной. Вместо объема может быть использован вес предмета (упаковки товара). Соответствующая математическая модель имеет следующий вид:

С(Х) = X t-jXj -»■ max i=i

i=i

где *,■ = ■

1, если 1-й предмет отбирается для укладки в ранец, О в обратном случае.

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

Задача о назначениях состоит в назначении п кандидатов на заданные п работ, при котором суммарные затраты минимальны (или общий экономический эффект максимален). При этом каж­дого кандидата можно назначить только на одну работу, а каж­дая работа должна быть выполнена только одним кандидатом. Пусть время выполнения /-й работы У-м исполнителем равно г... Вводятся переменные

^xiJ=

1, если i'-я работа выполняется j -м исполнителем, О в обратном случае.

Задача о коммивояжере формулируется следующим образом: минимизировать целевую функцию

Математическая модель задачи о назначениях имеет следую­щий вид:

С(Х) = X X UjXij -> ^max> мм

Х*#⁼¹> j-ln,

i=\ и

X>y=I, i-l_tn.

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

Пусть имеется и+1 город (пункт). Известна матрица расстоя­ний между городами inj, которую обозначим С =(^с^_пхп-

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

_ fl, если коммивояжер переезжает из города iв городу, ^ij [0 в обратном случае.

п п

^С(Х) = X X ^cij '^хи -»^min (2)

/=о/=о ^v '

при условиях:

п __

Х*,у =l_f j = \,n (3)

(=0

п

Х*у=1» ' ^{= 1}'" (4)

₇=0 ^V '

Uj -uj+tt- Xjj < и -1, i,j = 1, л; 1Ф j. (5)

Переменные и, и и. в ограничениях (5) принимают произволь­ные вещественные значения (не умаляя общности, их можно счи­тать и целыми неотрицательными числами). Условия (3) означа­ют, что коммивояжер выезжает из каждого города ровно один раз. Условия (4) показывают, что коммивояжер въезжает в каждый город только один раз. Если ограничиться условиями (3) и (4), то эта задача превращается в задачу о назначениях, решение которой не обязательно будет цикличным. Иначе говоря, путь коммивоя­жера может распасться на несколько не связанных между собой подциклов. Для устранения такой возможности служит условие (5).

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

3. Задачи о покрытии и другие задачи дискретной оптимизации сетей связаны с нахождением минимального подмножества ре­бер заданного графа, содержащего все его вершины. Эти задачи находят применение при синтезе логических сетей, в задачах оп­ределения кратчайшего пути в графе и др.

_1Г115Э

4. Задачи оптимального размещения производства, специализа­ции и кооперирования. Так как объекты производства продукции являются неделимыми, то в таких задачах возникает требование целочисленности переменных. Размещение предприятий должно учитывать расположение источников сырья, рынков сбыта това­ров и других факторов.

Существуют два основных класса методов решения задач дис­кретного программирования. Рассмотрим их на примере цело­численного линейного программирования.

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

• данное ограничение не выполняется для нецелочисленного оптимального плана;

• оно выполняется для любого допустимого целочисленно­го плана.

Далее решается расширенная задача с добавленным ограни­чением. В результате получается либо целочисленный план, либо нецелочисленный. Если план нецелочисленный, то опять вводится новое линейное ограничение, и так далее, пока не будет найден оптимальный план или будет показано, что таких планов нет.

Геометрически вводимое линейное ограничение представляет собой гиперплоскость, поэтому данный метод и назван методом отсечения, или методом отсекающих плоскостей. Впервые метод отсечения был предложен Р. Гомори. Для решения частично диск­ретных задач линейного программирования методом отсечения может быть использован алгоритм Дальтона и Ллевелина.

2. Комбинаторные методы основываются на конечности чис­
ла допустимых планов задачи, используя ее комбинаторный ха­
рактер. Главная идея таких методов заключается в замене полно­
го перебора всех планов задачи их частичным (неполным)
перебором. Это осуществляется отбрасыванием некоторых под­
множеств вариантов, заведомо не дающих оптимума. Дальней­
ший перебор ведется лишь среди оставшихся вариантов, являю­
щихся перспективными в отношении получения оптимального
плана. По своему характеру комбинаторные методы весьма раз-

нообразны. При этом центральное место среди них занимают методы, объединенные под названием «метод ветвей и границ».

Фактическое появление метода ветвей и границ связано с ра­ботой Литтла, Мурти, Суини и Кэрел, посвященной задаче ком­мивояжера, причем в этой же работе впервые было предложено общепринятое название «метод ветвей и границ».

В основе этого метода при решении задачи на максимум ле­жат следующие построения, позволяющие существенно умень­шить объем перебора.

• Вычисление верхней границы (оценки). Вычисляется верх­няя оценка целевой функции на множестве допустимых планов D.

• Разбиение на подмножества (ветвление). Данная процеду­ра связана с разбиением множества планов D на дерево подмно­жеств. Схематически процесс ветвления множества планов пока­зан на рис. 2.

Рис.2

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

11*

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

• 1.Гилл Ф. Практическая оптимизация /Ф.Гилл, Н. Мюррей, М.Райт. -
М.: Мир, 1985.2. К о р б у т А.А. Дискретное программирование / А.А. Кор-
бут, Ю.Ю. Финкельштейн.-М.: Наука, 1969.3.Саати Т. Целочисленные
методы оптимизации и связанные с ними экстремальные проблемы / Т. Саа­
ти. - М.: Мир, 1973. В.Д. Ногин, В.Н. Юрьев

ДИФФЕРЕНЦИАЛЬНЫЕ ИГРЫ - направление теории игр (см.), ориентированное на моделирование стратегий поведения не­скольких динамических управляемых объектов, эволюция состо­яний которых может быть описана дифференциальными уравне­ниями.

В качестве примера простейшей дифференциальной игры можно привести задачу о преследовании одного управляемого объекта другим.

Пусть в одном и том же л-мерном пространстве рассматриваются управляемый объект-преследователь

х'=Лх,и),ие U.QE_r, x(/₀) = x° (1)

и управляемый объект

y' = g(y,v),v<= VqE_s, у(/₀) = х°. (2)

---

Дата добавления: 2015-11-04