35441

Исследование операций. Курс лекций

Конспект

Информатика, кибернетика и программирование

2 Многокритериальные задачи . Задачи принципы методология. Математическая модель задачи ИСО включает в себя: 1 описание переменных которые необходимо найти 2 описание критериев оптимальности 3 описание множества допустимых решений ограничений накладываемых на перемен ные. Математическая модель задачи ИСО составляется в соответствии с представлениями ЛПР об этой задаче т.

Русский

2013-09-10

286.86 KB

135 чел.

Исследование операций

Курс лекций подготовлен профессором кафедры экономической информатики и математической экономики

Ковалевым Михаилом Яковлевичем.

Рассчитан на студентов 2 курса экономических  специальностей. Продолжительность лекций – 34 часа (17 занятий). Такое же количество практических занятий.

Минск

200?


Содержание

1 Литература  3

2 Основные понятия исследования операций (ИСО). Классификация задач 4

2.1 Классификация  задач ИСО . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Многокритериальные задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Основы линейного программирования 8

3.1 Графический  метод решения задач ЛП  . . . . . . . . . . . . . . . . . . . . . . 11

3.2

Возможные варианты решения задач ЛП .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

11

3.3

Эквивалентные постановки задач ЛП . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

12

3.4

Симплекс-метод . . . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

15

3.5

Транспортная  задача ЛП  . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

18

3.6

Задача о назначениях . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

21

4 Основы теории графов 23

4.1 Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.2 Алгоритм построения эйлерова цикла для неориентированного графа . . . . 25

4.3

Задание графов . . . . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

25

4.4

Топологическая сортировка . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

25

4.5

Остовное дерево (остов) минимального веса

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

26

4.6

Кратчайшие пути   . . . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

27

5 Сетевое планирование и управление проектами  29

6 Задача коммивояжера и метод ветвей и границ  31

7 Имитационное моделирование на примере метода Монте-Карло 34

8 Основы теории сложности вычислений 36

9 Динамическое программирование 40


1 Литература

Основная:

1. Вентцель Е.С. Исследование операций. - М., Советское радио, 1972. - 552 с.

2. Волков И.К.,  Загоруйко Е.А. Исследование операций:  учебное пособие для вузов. 2-е изд. / Под ред. В.С. Зарубина, А.П. Крищенко. - М. Изд-во МГТУ  им. Н.Э. Баумана,

2002. - 436 с.

3. Taha H. Operations research: an introduction. - Prentice Hall, Upper Saddle River, New

Jersey, 1977.

4. М.М. Кавалеу, М.М. Пiсарук. Сучаснае лiнейнае праграмаванне. - Мiнск, Выдавецкi цэнтр Белдзяржунiверсiтэта,  1998. - 260 с.

Дополнительная:

5. Вентцель Е.С. Исследование операций. - М., Знание, 1976.

6. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. - М., Наука,

1988.

7. Соболь И.С. Метод Монте-Карло. - М., Наука, 1972.

8. Nahmias S. Production and operations analysis. 3rd edition. - The McGraw-Hill Companies, Inc., 1997. - 858 pp.

9. Dilworth  J.B. Production and operations management:  manufacturing and services.  5th edition. - Mcgraw-Hill, Inc., 1993. - 742 pp.

10. Ritzman L.P., Krajewski L.J. Foundations of operations management. - Prentice Hall, Upper

Saddle River, NJ, 2003. - 473 pp.

11. Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные си- стемы. – М.: Наука, 1984.

12. Танаев В.С., Cотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные си- стемы. – М.: Наука, 1987.

13. Танаев В.С., Ковалев М.Я., Шафранский Я.М. Теория расписаний. Групповые техно- логии. – Минск: ИТК  НАН Беларуси, 1998.

14. Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – Минск: Университетское, 1995.


2   Основные понятия  исследования операций (ИСО).

Классификация задач

Исследование операций – это комплексная математическая дисциплина,  занимаю- щаяся построением, анализом и применением математических  моделей принятия опти- мальных решений при проведении операций.

Операция – система управляемых действий, объединенная единым замыслом и направ- ленная на достижение определенной цели.

Примеры  операций.

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

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

– число точек,

– их размещение,

– количество персонала и их зарплату,

– цены на товары.

Пример  3. Требуется организовать строительство железнодорожного вокзала. При этом необходимо указать порядок выполнения работ во времени и распределить требуемые ресурсы между работами так, чтобы завершить строительство во время и минимизировать его стоимость.

Набор управляющих параметров (переменных) при проведении операции называется ре-

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

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

Целевая функция  – это количественный  показатель предпочтительности  или эффек- тивности решений.

Направление оптимизации – это максимум (минимум), если наиболее предпочтитель- ным является наибольшее (наименьшее) значение целевой функции. Например, критерием может быть максимизация прибыли либо минимизация расходов.

Математическая  модель задачи ИСО включает в себя:

1) описание переменных, которые необходимо найти,

2) описание критериев оптимальности,

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

Цель ИСО – количественно  и качественно  обосновать принимаемое  решение.  Оконча- тельное  решение принимает ответственное лицо (либо группа лиц), называемое лицо, принимающее решение (ЛПР).

Математическая модель задачи ИСО составляется в соответствии с представлениями ЛПР об этой задаче, т.е. в соответствии с его информационным состоянием. При этом важно, чтобы математическая  модель задачи была наиболее адекватной, т.е. наиболее правиль-


но отражала информационное  состояние ЛПР.  Для этого разработчик математической модели должен работать в тесном контакте с ЛПР.

Основной принцип разработчика:  “Разрабатывай не то, что заказчик просит, а то, что ему нужно.”  (М. Гэри и Д. Джонсон “Вычислительные машины и труднорешаемые зада- чи”)

Проверка адекватности  представлений ЛПР о задаче не является предметом ИСО. Из- менение информационного  состояния ЛПР может привести к изменению математической модели задачи.

2.1    Классификация  задач ИСО

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

1. Статическая  задача. Принятие решения происходит при условии, что все парамет- ры задачи заранее известны и не изменяются во времени. Процедура принятия решения осуществляется один раз.

2.  Динамическая  задача. В процессе принятия решения параметры  задачи изменя- ются во времени. Процедура принятия решения осуществляется поэтапно и может быть представлена в виде процесса, зависящего от времени, в том числе непрерывно. Пример – навигационная задача.

Классификация  в зависимости от достоверности информации о задаче.

1. Детерминированная задача. Все параметры задачи заранее известны. Для решения детерминированных задач в основном применяются  методы математического програм- мирования.

2. Недетерминированная задача. Не все параметры задачи заранее известны. Напри- мер, необходимо принять решение об управлении устройством, некоторые узлы которого могут непредсказуемо  выходить из строя. Оптимальное  решение недетерминированной задачи ИСО отыскать практически невозможно. Однако некоторое “разумное”  решение отыскать можно.

“Исследование  операций  представляет  собой искусство  давать  плохие ответы на те практические  вопросы, на которые даются  еще худшие ответы  другими методами”. (Т.Л. Саати)

2,а). Стохастическая задача. Не все параметры задачи заранее известны, но имеются статистические данные о неизвестных параметрах (вероятности, функции распределения, математические ожидания и т.д.).

Для отыскания оптимального решения стохастической задачи применяется один из сле- дующих приемов:

– искусственное  сведение к детерминированной задаче (неизвестные параметры заменя- ются их средними значениями),

– “оптимизация в среднем” (вводится и оптимизируется некоторый статистический крите- рий).

2,б). Задача в условиях (полной) неопределенности. Статистические  данные о неиз- вестных параметрах отсутствуют. Задачи ИСО в условиях неопределенности в основном изучаются в рамках теории игр.


Классификация  по виду критерия оптимальности.

Критерий оптимальности может иметь любой вид, в том числе неформализуемый (“Хочу, чтобы все было хорошо"). Наиболее распространенные  формализуемые критерии опти- мальности заключаются в оптимизации (минимизации либо максимизации) одной либо нескольких  скалярных целевых функций.

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

Задачи линейного программирования.  Целевая функция – линейная, множество допусти- мых решений – выпуклый многогранник.

Задачи   квадратичного программирования.  Целевая   функция    –    квадратичная

(

 n i=1

 j=1 cij xixj ), а множество допустимых решений – выпуклый многогранник.

 n

Задачи стохастического программирования.  Это задачи линейного программирования  с неизвестными числовыми параметрами, о которых имеются статистические данные. Задачи дискретного программирования.  Множество допустимых решений – дискретное множество.

Задачи целочисленного программирования.  Множество допустимых решений – точки це- лочисленной решетки.

Задачи булева программирования.  Множество допустимых решений – 0-1 матрицы.

2.2    Многокритериальные  задачи

В задачах ИСО, как правило, присутствует  не один, а несколько признаков предпочтения

(критериев). Такие задачи называются многокритериальными.

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

В случае противоречивых критериев, ИСО предлагает следующие подходы к отысканию подходящего решения.

1) Замена некоторых критериев ограничениями вида или . Например, минимизация

стоимости f (x) min, может быть заменена ограничением вида f (x) A, где A – неко-

торая верхняя оценка стоимости, т.е. максимально допустимая стоимость.

2) Свертка критериев. Создается один глобальный скалярный критерий, целевая функция которого является некоторой функцией от исходных целевых функций. Наиболее упо- требимыми являются линейные свертки вида αf (x) + βg(x) (в случае двух критериев). Нетривиальной  является задача отыскания адекватных значений коэффициентов α и β, отражающих относительную важность целевых функций f (x) и g(x).

3) Ранжирование критериев. Критерии ранжируются по степени важности.

4) Отыскание решений, лучших хотя бы по одному критерию.


Подходы 1) и 2) приводят к однокритериальной  задаче. Подход 3) приводит к задаче с упорядоченными критериями. В задаче с упорядоченными критериями критерии упоря- дочиваются по важности и требуется найти оптимальное решение для наименее важного критерия на множестве решений, оптимальных для более важного критерия (см. Рис. 1). Самое большое – множество всех допустимых  решений, в него вложено множество реше-

 

 

✬ ✩

Оптимальные по самому неважному критерию среди оптимальных по

...

 

Оптимальные по самому важному критерию

 

Все допустимые решения

 

Рис. 1: Решение задачи с упорядоченными критериями

ний, оптимальных по самому важному критерию, далее вложено множество оптимальных решений по второму по важности критерию среди оптимальных  по первому критерию, и т.д.

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

Пример  многокритериальной  задачи с независимыми критериями.  Фирма по разработке программного  обеспечения должна выполнить проекты 1 и 2 в последователь- ности (1,2). Для выполнения каждого проекта можно привлечь oт одного до трех испол- нителей. Пусть x1  и x2  – число исполнителей, привлеченных для выполнения проектов

1 и 2 соответственно. Время выполнения проекта i равно ti(xi) месяцев, а соответствую-

щая стоимость – ci(xi) млн. рублей. Требуется минимизировать общее время выполнения проектов при минимальной стоимости.

Значения функций заданы следующим образом:

x

1

2

3

t1(x)

2

1

1

t2(x)

3

1

1

c1(x)

1

2

3

c2(x)

4

4

5

Общее время выполнения  проектов равно T (x1, x2) = t1(x1) + t2(x2), а стоимость их вы- полнения равна C (x1, x2) = c1(x1) + c2(x2).

Определим все возможные значения пар (T , C )  = (T (x1, x2), C (x1, x2))  

{(2, 6), (2, 7), (2, 8), (3, 5), (3, 6), (4, 6), (4, 7), (5, 5)}. Соответствующие значения аргу-


ментов (x1, x2)   ∈  {(2, 2), {(2, 3), (3, 2)}, (3, 3), (1, 2), (1, 3), (2, 1), (3, 1), (1, 1)},  см. Рис. 2. Задача отыскания множества Парето в случае двух критериев вида F1(x)  min и

F2

8

7 • •

6 • • •

5 • •

2 3 4 5 F1

Рис. 2: Отыскание множества Парето

F2(x) min может быть решена графически  следующим образом. Находим  все точки с наименьшим значением F1(x). Если их несколько, выбираем из них точку с наименьшим значением F2(x).  Включаем ее  в множество Парето. Отсекаем точки с большими либо равными значениями F1(x)  и F2(x)  (cеверо-восточный  угол с вершиной в выбранной точке). Повторяем процедуру для оставшейся части допустимой области.

Из рисунка видно, что для нас представляют  интерес пары (F1, F2)  ∈ {(2, 6), (3, 5)} и соответствующие решения (x1, x2) ∈ {(2, 2), (1, 2)}, которые являются недоминируемыми

и образуют множество Парето рассматриваемой задачи.

3   Основы линейного программирования

Задачи линейного программирования (ЛП)  и методы их решения широко используются в промышленном  производстве, экономике, логистике, военном  деле и других областях целенаправленной деятельности человека. Напомним,  что задача ИСО называется зада- чей ЛП, если множество ее допустимых решений – выпуклый многогранник, а целевая функция – скалярная линейная.

Примеры задач ЛП. Макроэкономические  линейные модели

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

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


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

Допустим, что для отрасли i известно, что aij   единиц продукции этой отрасли исполь- зуется для производства единицы (!) продукции отрасли j и ci   единиц продукции этой отрасли используется в непроизводственной  сфере (накопление,  потребление). Величина ci   также  называется внешним спросом. Требуется  определить xi   – валовый  объем (ко- личество единиц) продукции отрасли i, i = 1, . . . , n, так, чтобы выполнялось условие межотраслевого баланса:

n

 aij xj  + ci  = xi,  xi  0, i = 1, . . . , n,

j=1

или в матричной форме

 

x Ax = c, x 0.

Приведенные соотношения называются  моделью Леонтьева.  Соотношение x Ax  = c

можно ослабить: x Ax  c (в этом случае c определяет  нижнюю границу внешнего

спроса). С моделью Леонтьева связаны некоторые задачи оптимизации.

1) Задача максимизации суммарного валового выпуска при ограниченных тру- довых ресурсах.

Пусть для выпуска единицы продукции отрасли j требуется tj  единиц трудовых ресурсов. Обозначим t = (t1, . . . , tn). Пусть T – общее количество трудовых ресурсов, имеющееся в наличии. Тогда модель задачи максимизации  суммарного валового выпуска при ограни- ченных трудовых ресурсах состоит в следующем:

n

 xj  max,

j=1

x Ax c

n

j=1 tj xj  T

x 0

2)  Задача минимизации требуемых трудовых ресурсов при заданном уровне суммарного валового выпуска:

n

 tj xj  min,

j=1

x Ax c

n

j=1 xj  V

x 0,

где V – заданный уровень суммарного валового выпуска.

Микроэкономические  линейные модели

Модель оптимальной программы предприятия. Предприятие выпускает n видов продукции. Для выпуска единицы продукции вида j требуется aij  единиц ресурса i, кото- рый имеется в объеме bi, i = 1, . . . , m (всего имеется m видов ресурсов). Выпуск единицы


продукции вида j приносит прибыль в объеме pj . Требуется определить программу вы- пуска продукции x = (x1, . . . , xn),  где xj   – количество  выпускаемой продукции вида j, такую, что выполнены ограничения на ресурсы и суммарная прибыль максимальна. Со- ответствующая задача ЛП имеет вид:

n

j=1

( n

 

pj xj  max,

j=1 aij xj  bi,  i = 1, . . . , m,

xj  0, j = 1, . . . , n

Модель распределения ресурсов. Имеется n видов деятельности и m видов ресур- сов. Ресурс i имеется в объеме bi, i = 1, . . . , m. С помощью единицы i-го ресурса можно выполнить dij -ю часть j-го вида деятельности и при этом затраты будут составлять cij . Введем переменные xij , показывающие какое количество ресурса i направлено для вида деятельности j. Задача состоит в следующем.

m  n

cij xij  min,

i=1 j=1

m

n

 i=1 dij xij  = 1, j = 1, . . . , n,

j=1 xij  bi,  i = 1, . . . , m,

 xij  0, i = 1, . . . , m, j = 1, . . . , n.

Модель оптимальной купли-продажи валюты. Рассмотрим ситуацию, когда бро- кер осуществляет куплю-продажу валюты с целью получения прибыли за счет разницы в курсах валют. Пусть n – количество доступных валютных рынков, m – количество опе- раций купли-продажи. Обозначим через rij количество денежных единиц i-го валютного рынка, которые можно купить (rij   > 0) либо продать (rij   < 0) в результате операции j стандартного объема. Например, при проведении операции номер 2 стандартного  объема, продавая 2 доллара, можно купить 1 евро и 2000 бел.рублей. Пусть xj  – объем операции j. В этом случае соответствующие величины rij умножаются на xj . Например, продавая

2x2 долларов, можно получить x2  евро и 2000x2  бел.рублей.

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

глядит следующим образом.

n

j=1

n

 r1j xj  max,

j=1

 rij xj  0, i = 1, . . . , m.


3.1    Графический  метод решения задач ЛП

Вначале  рассмотрим  наиболее простой метод решения, применимый  для случая, когда количество переменных не превосходит двух. Рассмотрим следующий пример.

Компания производит погрузчики и тележки. От одного погрузчика компания получает доход в размере $80 и от одной тележки в размере $40. Имеется три обрабатывающих цен- тра, на которых выполняются операции металлообработки, сварки и сборки, необходимые для производства любого из продуктов. Для интервала планирования, равного месяцу, за- дана предельная производственная мощность каждого обрабатывающего центра в часах, а также количество часов, необходимое на этом центре для производства одного погрузчика

и одной тележки. Эта информация задана в таблице.

Центр\Изделие

Погрузчик  Тележка

(часы на ед.) (часы на ед.)

Общая мощность

(часы)

Мет.обработка

Сварка

Сборка

6 4

2 3

9 3

2400

1500

2700

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

80x1 + 40x2 max,

6x1

 + 4x2

 2400

 2x1 + 3x2 1500

1 2

9x  + 3x  2700

x1 0, x2 0

где x1  и x2  – количества производимых погрузчиков и тележек соответственно.

Представим ограничения в виде следующего графика, где по осям (0x1) и (0x2) отклады- вается количество произведенных погрузчиков и тележек соответственно, а линии пред- ставляют ограничения на производственные мощности. Допустимая  область задачи пред- ставлена в виде многоугольника.

Представим  целевую функцию 80x1 + 40x2 = z с переменным значением z прерывистой линией. Любая точка (x1, x2) на линии 80x1 + 40x2 = z соответствует доходу в размере z. Перемещая ее параллельно  себе самой, получаем  разные значения  дохода.

При x1 = 0 значение z = 40x2. Следовательно, значение z увеличивается при увеличении x2, т.е. при перемещении  целевой функции вверх. При этом линия 80x1 + 40x2  = z не должна покинуть допустимую область.

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

соответствующих ограничениям на металлообработку и сборку, x= 200, x= 300.

1 2

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

3.2  Возможные варианты решения задач ЛП

1) ЗЛП имеет единственное решение


x2

900

600

❏ ❇

500 ❏    ❇

◗    ❇

❏◗

❏◗❇ ◗

❏   ◗

❏❇ ◗

❇ ◗

❆ ✟✟✯

 ❏ ◗

❇ ❏ ◗

❇  ❏ ◗

❇   ❏ ◗

❆ ❇ ❏ ◗

300 400 750 x1

2) Не существует допустимого решения ЗЛП

3) ЗЛП имеет много оптимальных решений, которые называются альтернативными

4) Целевая функция ЗЛП неограничена (в допустимой области).

3.3  Эквивалентные постановки задач ЛП

Общая постановка:

n

j=1

n

 cj xj  max(min),

j=1 aij xj  bi, i I1

n

n

j=1 aij xj  = bi, i I2

 j=1 aij xj  bi, i I3

   j 1

x  0, j N ,

xj  R, j N2,

xj  0, j N3,

где cj , aij , bi  – заданные числовые параметры, множества I1, I2  и I3  попарно не пересе- каются, I1  I2  I3  = {1, . . . , m}, R – множество действительных чисел, множества N1, N2  и N3  попарно не пересекаются, и N1  N2  N3  = {1, . . . , n}. Cуществует несколько

эквивалентных постановок задач ЛП:

– Задачи максимизации и минимизации. Для перехода от одной задачи к другой коэффи- циенты целевой функции можно умножить на -1.

– Задачи с ограничениями типа ”=”, ” ” и ” ”. Для перехода от ограничения ” ” к ограни-

чению ” ” и наоборот достаточно домножать соответствующее ограничение на -1. Огра-

ничение типа ”=”  может быть представлено в виде двух ограничений ” ” и ” ” с той же

левой и правой частью. Для перехода от ограничений типа ”=”  к ограничениям типа

можно применить метод Гаусса. Например, рассмотрим задачу

x1 x2 + x5 min


x1 + x2 = 1

 x2 2x3 = 3

x3  x4 + x5 = 1

xj  0

При помощи метода Гаусса выделяем единичную подматрицу  в матрице ограничений.

1

1

0

0

0

1

1

0

2

0

0

4

1

0

0

2

-2

2

0

1

-2

0

0

-3

0

1

-2

0

0

-3

0

1

0

-2

2

-1

0

0

1

-1

1

1

0

0

1

-1

1

1

0

0

1

-1

1

1

Эквивалентная задача

  x1 = 2 (2x4 2x5) 0

x2 = 1 (2x4 + 2x5) 0

 x3 = 1 (x4 + x5) 0

2 + 2x4 2x5 1 + 2x4 2x5 + x5 = 3 + 4x4 3x5 min

2x4

 2x5 2

 2x4 + 2x5 ≤ −1

 x4 + x5 1

x4, x5 0

Для перехода от ограничений типа к ограничениям типа = достаточно ввести дополни- тельные неотрицательные переменные, по одной для каждого ограничения . Эти пере-

менные войдут в целевую функцию с нулевыми коэффициентами.

Переменная xj  R может быть представлена в виде двух новых неотрицательных пере-

менных: xj  = x+ x, x+ 0, x0.

j j j j

Для каждой задачи ЛП можно сформулировать  двойственную ей задачу. Рассмотрим задачу максимизации с ограничениями ” ”. Представим эту задачу в матричной форме:

cx max, Ax b,

где c = (c1, . . . , cn) – вектор-строка, x = (x1, . . . , xn)T  – вектор-столбец, A = ||aij || – матрица размерности m × n, b = (b1, . . . , bm)T   – вектор-столбец. Отметим, что ограничения x 0 отсутствуют. Они могут быть войти в ограничения Ax b путем  введения эквивалентных ограничений x 0. Введем в рассмотрение двойственную ей задачу:

yb min,

yA = c, y 0,

где y = (y1, . . . , ym) – вектор-строка  двойственных переменных или потенциалов. Пусть Ai  обозначает строку i матрицы A, а Aj  – столбец j этой же матрицы. Соответствие между компонентами прямой и двойственной задач представлено в следую- щей таблице.


Прямая задача

Двойственная задача

max{cx}

Aix bi,  i I1

Aix = bi,  i I2

xj  0, j N1

xj  R, j N2

xj  0, j N3

min{yb}

yi  0, i I1

yi  R, i I2

yAj  cj , j N1

yAj  = cj , j N2

yAj  cj , j N3

Теорема 1 (Теорема двойственности) Справедливо одно из следующих утверждений:

а) обе задачи,  прямая и двойственная ей, имеют допустимые решения и

max{cx} = min{yb},

б) если одна из задач, прямая и двойственная ей, не имеет допустимого решения а другая имеет, то целевая функция  другой задачи не ограничена.

в) обе задачи  не имеют допустимых решений.

Теорема 2 (О дополняющей нежесткости) Пусть x и y – допустимые решения прямой и двойственной задач соответственно. Тогда следующие условия а), б) и в) эквивалент- ны:

а) x и y оптимальные решения прямой и двойственной задач, б) cx = yb,

в) (условие дополняющей нежесткости)  yi(Aix bi) = 0 i = 1, . . . , m, и (yAj  cj )xj  = 0,

j = 1, . . . , n.

Из этой теоремы, например, следует, что если решения прямой и двойственной задач допу- стимы и выполняется условие в) дополняющей нежесткости, то эти решения оптимальны. Оптимальное  решение прямой задачи может быть получено из оптимального решения двойственной задачи. Например, рассмотрим задачу

4x1 3x2 6x3 x4 max,

2x1 x2 + 5x3 + 2x4 2

3x1 + x2 x3 x4 1

xi  0, i = 1, 2, 3, 4

Построим двойственную ей задачу

2y1 + y2 min,

2y1 3y2 4

y1 + y2 ≥ −3

5y1 y2 ≥ −6



2y1 y2 ≥ −1

yj  0, j = 1, 2

Решим двойственную задачу графически: y= (9/4, 21/4), z= 39/4. Оптимальное

решение определяется  пересечением линий, соответствующих ограничению 2 и 3 двой-

1

ственной задачи. Эти ограничения выполняются как  строгие равенства, а остальные - как нестрогие. Тогда по условию дополняющей нежесткости должно выполняться x= 0,

4  = 0, x2  и x3  могут быть найдены из равенств x2 + 5x3  = 2 и x2 x3  = 1 (рассмат-

x∗ ∗ ∗

 ∗ ∗ ∗ ∗

риваем подматрицу матрицы прямой задачи, состоящую из столбцов 2 и 3). Получаем

x= (0, 7/4, 3/4, 0).


3.4    Симплекс-метод

Симплекс-метод  является методом решения задач ЛП. Он впервые использовался лауре- атом Нобелевской премии советским ученым Канторовичем в 1939 г. и описан в том виде, в котором существует сейчас, Данцигом в 1947 г.

Описание метода проведем для задачи ЛП в стандартной форме:

Также должно выполняться b 0.

 z = cx max,

Ax = b, x 0.

Рассмотрим следующий пример. Фирма производит краску для наружных и внутренних

работ из исходных материалов М1 и М2. Расход материалов и их запасы представлены в таблице.

Исх.мат./Краска

Для наруж. раб.

(тонн на 1 тонну)

Для внутр. раб.

(тонн на 1 тонну)

Суточные запасы

(тонн)

М1

6

4

24

М2

1

2

6

Рынок накладывает следующие ограничения: краски для внутренних работ можно произ- вести в день не более, чем на 1 тонну больше, чем краски для наружных работ, и краски для внутренних работ требуется не более 2 тонны в день. Доход от производства 1 тонны краски для наружных (внутренних) работ равен 5 (4) млн. рублей. Требуется составить оптимальный план выпуска красок на день.

Математическая модель:

z = 5x1 + 4x2 max,

6x1 + 4x2 24,

x1 + 2x2 6,

x1 + x2 1,

x2 2,

x1, x2 0.

Приведем построенную задачу к стандартной форме:

z = 5x1 + 4x2 + 0x3 + 0x4 + 0x5 + 0x6 max,

6x1 + 4x2 + x3 = 24, x1 + 2x2 + x4 = 6,

x1 + x2 + x5 = 1,

x2 + x6 = 2, x1, . . . , x6 0.


Выделим единичную подматрицу в матрице ограничений.  Соответствующие переменные называются базисными. Они образуют базис. Остальные переменные называются небазис- ными или свободными.

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

Представим задачу в виде симплексной таблицы:

Базис

z

x1  x2  x3  x4  x5  x6

Значение

z

1

-5 -4 0 0 0 0

0

x3

x4

x5

x6

0

0

0

0

6 4 1 0 0 0

1 2 0 1 0 0

-1 1 0 0 1 0

0 1 0 0 0 1

24

6

1

2

Таблица 1: Симплекс-таблица 1

Симплекс-метод.

Шаг 0. Находим начальное допустимое базисное решение.

Шаг 1. Определяем вводимую переменную xin (ведущий столбец): это небазисная пере- менная с наименьшим отрицательным коэффициентом в строке z. Если все коэффициенты в строке z неотрицательны, то построенное базисное решение оптимально.

Если существует  небазисная переменная с отрицательным коэффициентом  в строке  z, все коэффициенты которой в матрице ограничений неположительны (столбец в симплекс- таблице), то значение целевой функции неограничено (может быть бесконечно большим). Шаг 2. Определяем выводимую переменную xout  (ведущую строку): это базисная пере- менная с наименьшим неотрицательным значением отношения bout/aout,in. Элемент aout,in на пересечении ведущей строки и ведущего столбца называется ведущим.

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

– модифицированная ведущая строка = ведущая строка, деленная на ведущий элемент,

– (любая другая строка, включая строку z): модифицированная строка = (строка) - (ее коэффициент в ведущем столбце)×(модифицированная  ведущая строка).

Повторяем Шаг 1.

Отметим, что выбор ведущего  столбца и ведущей строки может быть неоднозначным. Пока будем считать, что в таком случае выбор произволен.

В нашем примере вводимая переменная - x1, выводимая переменная - x3, и новая симплекс- таблица имеет вид (пересчитали таблицу и обозначение x3  в первом столбце заменили на x1):

Далее, вводимая переменная - x2, выводимая переменная - x4, и новая симплекс-таблица имеет вид: Поскольку все коэффициенты строки z неотрицательны,  полученное решение (x1, . . . , x6)  = (3, 3/2, 0, 0, 5/2, 1/2)  со значением  целевой функции z = 21 оптимально.


Базис

z

x1  x2  x3  x4  x5  x6

Значение

z

1

0 -2/3  5/6  0 0 0

20

x1

x4

x5

x6

0

0

0

0

1 2/3  1/6  0 0 0

0 4/3  -1/6  1 0 0

0 5/3  1/6  0 1 0

0 1 0 0 0 1

4

2

5

2

Таблица 2: Симплекс-таблица 2

Базис

z

x1  x2  x3  x4  x5  x6

Значение

z

1

0 0 3/4  1/2  0 0

21

x1

x2

x5

x6

0

0

0

0

1 0 1/4  -1/2  0 0

0 1 -1/8  3/4  0 0

0 0 3/8  -5/4  1 0

0 0 1/8  -3/4  0 1

3

3/2

5/2

1/2

Таблица 3: Симплекс-таблица 3

Таким образом, оптимальный план выпуска красок на день включает производство 3 тонн красок для наружных работ и 1.5 тонны краски для внутренних работ.

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

ному числу M. Такой метод получения  начального допустимого  базиса называется M -

методом.

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

щаться к нему число раз. Эта ситуация, например, может возникнуть, когда при n = 2

в вершине многогранника ограничений пересекается  более 2 прямых, т.е. когда некоторые

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

- в качестве ведущего выбирать столбец с отрицательным коэффициентом (необязательно наименьшим!) с наименьшим номером в строке z.

- в качестве ведущей выбирать строку с наименьшим неотрицательным значением отно- шения bout/aout,in  с наименьшим номером.

Указанное правило делает выбор ведущего элемента однозначным.


3.5    Транспортная  задача ЛП

Транспортная задача (ТЗ) ЛП может быть сформулирована следующим образом. Имеет- ся m пунктов отправления (производства) A1, . . . , Am, в которых имеется товар в количе- стве a1, . . . , am  соответственно. Кроме того, имеется n пунктов назначения (потребления) B1, . . . , Bn, в которых имеются заявки на этот товар в количестве b1, . . . , bn  соответственно. Предполагается, что

m

i=1

 

ai  =

 n

j=1

 

bj ,

т.е. все, что произведено, должно быть получено. Приведенное уравнение называется усло- вием баланса.

Известна стоимость cij  перевозки единицы товара из пункта отправления Ai  в пункт по- требления Bj . Требуется составить такой план перевозок товара, при котором весь товар из пунктов производства  вывезен, все заявки в пунктах потребления  удовлетворены  и общая стоимость перевозок минимальна.

Математическая  модель ТЗ состоит в следующем. Обозначим через xij  количество товара, перевозимого из Ai  в Bj . Составим задачу ЛП:

m  n

cij xij  min,

i=1 j=1

n

j=1

m i=1

 

xij  = ai,  i = 1, . . . , m,

xij  = bj , j = 1, . . . , n, xij  0, i, j.

На практике условие баланса может не выполняться. Что делать? Если

m

i=1

 

ai  >

 

n

j=1

 

bj ,  (производится  больше, чем потребляется),

то вводим новый пункт потребления Bn+1 с запросом

Полагаем

 

bn+1  =

 

m i=1

 

ai

 

n j=1

 

bj .

Если же

 

m i=1

 

ai  <

 

n j=1

 ci,n+1  = 0, i = 1, . . . , m.

bj ,  (потребляется больше, чем производится),

то вводим новый пункт производства Am+1 с предложением

am+1  =

 

n j=1

 

bj  

 

m i=1

 

ai.


Полагаем

 

cm+1,j  = 0, j = 1, . . . , n.

В дальнейшем будем считать, что условие баланса выполнено.

Отметим, что ранг системы ограничений ТЗ равен m + n 1 (на 1 меньше m + n за счет

связующего условия баланса). Поэтому количество базисных  переменных также  равно

m + n 1.

Исходные данные ТЗ удобно представлять в виде транспортной  таблицы (ТТ),  см. ниже.

Ai/Bj

B1

B2

...

Bn

Запасы ai

A1

c11

c12

...

c1n

a1

A2

c21

c22

...

c2n

a2

...

...

...

...

...

...

Am

cm1

cm2

...

cmn

am

Заявки bj

b1

b2

...

bn

ai  = bj

Опорным планом ТЗ называется такое распределение объемов перевозок в ТЗ, что

– это распределение является допустимым,

– число базисных переменных (xij  > 0) равно m+n1, все остальные (свободные) перемен-

ные равны нулю. Отметим, что некоторые базисные переменные также могут равняться

нулю,

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

Метод потенциалов решения ТЗ. Основные этапы:

Этап 1. Отыскание начального опорного плана.

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

Этап 3. Переход к лучшему опорному плану.

Этап  1.  Известны 2 основных метода отыскания начального опорного плана: метод северо-западного угла и метод минимальной  стоимости.

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

мо, полагаем xij  = 0. Поясним на примере.

Ai/Bj

B1

B2

B3

B4

B5

Запасы ai

A1

1810

278

35

6

9

48

A2

6

7

308

6

5

30

A3

8

7

910

128

67

27

A4

7

5

4

6

208

20

Заявки bj

18

27

42

12

26

= 125

c = 1039

В методе минимальной стоимости каждый раз определяется максимальный  объем перево- зок, соответствующий допустимой клетке таблицы с наименьшей стоимостью cij . Поясним на примере.


Ai/Bj

B1

B2

B3

B4

B5

Запасы ai

A1

1410

8

225

126

9

48

A2

46

7

8

6

265

30

A3

8

277

10

8

7

27

A4

7

05

204

6

8

20

Заявки bj

18

27

42

12

26

= 125

c = 745

В базис ввели 7 < m + n 1 = 8 положительных  переменных. Нужно ввести  еще одну переменную, равную нулю, так, чтобы не образовался цикл. Например, x42 = 0.

Этап 2. Проверка на оптимальность В методе потенциалов вводятся в рассмотрение двойственные  переменные  – потенциалы ui,  i = 1, . . . , m, (дополнительный  столбец в матрице ТЗ) и vj , j = 1, . . . , n, (дополнительная строка в ТТ).

Для клеток, соответствующих базисным переменным, должно выполняться

ui + vj  = cij .

Вначале один из потенциалов можно выбрать произвольно, например, u1 = 0, остальные подсчитать по формуле ui + vj  = cij  для клеток, соответствующих базисным переменным.

Ai/Bj

B1

B2

B3

B4

B5

Запасы ai

Потенциалы ui

A1

+ 10

148

+ 225

126

+ 9

48

0

A2

46

+ 7

+ 8

+ 6

265

30

-3

A3

148

137

+ 10

+ 8

+ 7

27

-1

A4

+ 7

2 + 5

204

+ 6

+ 8

20

-1

Заявки bj

18

27

42

12

26

= 125

Потенциалы vj

9

8

5

6

6

Критерий оптимальности: если

ij = cij  (ui + vj ) 0 для всех клеток ТТ,

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

Этап 3. Переход к лучшему опорному плану Если существует ∆ij < 0, то переходим

к лучшему опорному плану следующим образом.

Определяем переменную, которая будет введена в базис, и переменную, которая будет из него выведена. В базис введем переменную  xi0 j0   такую, что

i0 j0   = min{ij |∀i, j}.

Ai/Bj

B1

B2

B3

B4

B5

Запасы ai

Потенциалы ui

A1

+ 10

8

365

126

+ 9

48

0

A2

46

+ 7

+ 8

+ 6

265

30

-1

A3

148

137

+ 10

+ 8

+ 7

27

1

A4

+ 7

145

64

+ 6

+ 8

20

-1

Заявки bj

18

27

42

12

26

= 125

Потенциалы vj

7

6

5

6

6


c = 721 (8 + 4 5 5) · 14 = 693

Обозначим клетку (i0, j0)  знаком “+”.  Рассмотрим цикл, образованный этой клеткой и клетками,  соответствующими базисным переменным. Припишем клеткам цикла знаки “+” и “-” так, что они чередуются при каком-либо обходе этого цикла. Вычислим

xij∗  = Q = min{xij | клетка (i, j) отмечена “-” }.

Переменную xij∗  выводим из базиса.

Если минимум достигается на нескольких переменных, то выводим из базиса только одну переменную.

Пересчитываем новые объемы перевозок для элементов цикла:

xij  = xij  + Q, если клетка (i, j) помечена ”+”, и

xij  = xij  Q, если клетка (i, j) помечена ”-”.

Для нового опорного плана определяем новые потенциалы и проверяем его на оптималь-

ность. Процесс повторяем до тех пор, пока условие оптимальности  не будет выполнено.

В нашем примере меняется лишь v2 = 6. Все ∆ij 0. Следовательно, построенное решение

оптимально.

3.6    Задача о назначениях

Задача о назначениях может быть сформулирована  следующим образом. Имеется n ра- бочих и m работ и задана стоимость назначения рабочего i на работу j для всех i и j. Каждый рабочий может быть назначен не более, чем на одну работу, и каждая работа мо- жет выполняться не более, чем одним рабочим. Требуется найти допустимое назначение, при котором суммарная стоимость F минимальна.

Если рабочий не может выполнять какую-то работу, соответствующая стоимость равна бесконечности. Не ограничивая общности, можно считать, что n = m. Иначе можно ввести фиктивных рабочих или фиктивные работы с нулевыми стоимостями.

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

Рассмотрим задачу о назначениях,  заданную следующей матрицей стоимостей назначе-

ния.

1

4

6

3

9

7

10

9

4

5

11

7

8

7

8

5

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


0

3

5

2

2

0

3

2

0

1

7

3

3

2

3

0

Найдем сумму вычтенных чисел ∆ = 17. Далее вычтем из каждого элемента столбца

наименьший элемент этого столбца по всем столбцам. Получим матрицу

0

3

2

2

2

0

0

2

0

1

4

3

3

2

0

0

Найдем новую сумму ∆ = 20. Задача о назначениях с полученной матрицей стоимостей эквивалентна исходной задаче о назначениях. Для получения стоимости оптимального на- значения исходной задачи необходимо к стоимости оптимального назначения новой задачи прибавить сумму вычтенных чисел: F = F + ∆.

Последняя полученная матрица называется приведенной.

Общий  шаг.  Если в приведенной матрице можно выбрать n нулевых элементов так, что все они расположены в разных строках и столбцах, то такой выбор определяет оп- тимальное  назначение.  Иначе, находим минимальное число линий - строк и столбцов, покрывающих все нули. В нашем случае таких линий 3 - это столбец 1 и строки 2 и 4. Среди элементов, не покрытых этими линиями, находим наименьший элемент. Вычитаем его из непокрытых элементов и прибавляем к дважды покрытым (строкой и столбцом). Получаем матрицу

0

2

1

1

3

0

0

2

0

0

3

2

4

2

0

0

Повторяем Общий шаг. На этот раз существуют n нулевых элементов в разных строках и

столбцах:

0

2

1

1

3

0

0

2

0

0

3

2

4

2

0

0

Они и определяют оптимальное назначение: рабочий 1 на работу 1, рабочий 2 на работу

3 и т.д. Стоимость назначения равна 21.

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

Алгоритм решения упрощенной задачи о назначениях


Шаг 0. Строим любое допустимое назначение. Например, в каждой строке отмечаем ноль в столбце с наименьшим номером, не содержащем отмеченный ноль.

1 2 3 4

1

2

3

4

0 3 2 2

2 0 0 2

0 1 4 3

3 2 0 0

Шаг 1. Помечаем знаком “-” все строки, не содержащие отмеченных нулей.

3

1 2 3 4

1

2

3

4

0 3 2 2

2 0 0 2

0 1 4 3

3 2 0 0

1

-

а) В каждой помеченной строке, например i, находим неотмеченные нули. Столбцы, со- ответствующие этим нулям, отмечаем номером строки (i). Однажды помеченный столбец далее не помечается. Просматриваем  все помеченные строки.

б) В каждом помеченном столбце, например  j,  отыскиваем отмеченный нуль. Если он найден, помечаем строку, где он расположен,  номером столбца (j).  Просматриваем все помеченные столбцы. Возвращаемся к а), так как появились новые помеченные строки. Шаг  1 завершается,  когда помечен столбец, не содержащий  отмеченного нуля. В этом случае количество отмеченных нулей может быть увеличено следующим образом. В поме- ченном столбце, не содержащем отмеченного нуля, отмечаем ноль в строке, указываемой пометкой этого столбца. Затем в этой строке делаем неотмеченным  нуль в столбце, ука- зываемым пометкой этой строки. Процесс повторяется до тех пор, пока не отметим нуль в строке, первоначально помеченной знаком “-” (не содержащей отмеченных нулей). Повторяем Шаг 1. Алгоритм завершается, когда невозможно сделать ни одной пометки. Помеченные столбцы и непомеченные строки образуют минимальное количе-

ство линий, покрывающий все нули.

4   Основы теории графов

Граф – это математическое понятие, которое служит для моделирования  связей между объектами. Различают ориентированные и неориентированные графы. Точные определе- ния даны ниже.

4.1    Основные понятия

(Неориентированным) графом называется пара конечных множеств (V, E), где V – произ- вольное множество объектов, называемых вершинами, и E ⊆ {{i, j}|i, j V } – множество неупорядоченных пар вершин, где {i, j} ∈ E называется ребром.


Ориентированным  графом (орграфом) называется пара конечных множеств (V, A), где V

– множество вершин, и A ⊆ {(i, j)|i, j V } – множество упорядоченных пар вершин, где (i, j) A называется дугой.

Мультиграфом (ориентированным мультиграфом) называется граф с кратными ребрами

(кратными дугами).

Примеры: рисунки графов с 3 вершинами.

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

неориентированном графе вершины i и j называются концами ребра {i, j}. Количество

ребер, инцидентных  вершине i, называется степенью вершины i.

Маршрутом в неориентированном графе G = (V, E)  называется такая последователь- ность вершин W = (v0, v1, . . . , vk ), k 0, что {vi1, vi} ∈ E, i = 1, . . . , k. Граф называется

связным,  если существует маршрут, связывающий любые его две вершины.  Говорят, что маршрут W связывает вершины v0  и vk , а вершины v1, . . . , vk1  являются внутренними

вершинами этого маршрута. Количество вершин маршрута называется его длиной. Марш-

рут W называется замкнутым,  если k > 0 и vk = v0. Маршрут называется цепью, если в нем нет повторяющихся вершин. Замкнутый маршрут, в котором никакие вершины, кроме первой и последней, не повторяются, называется циклом.

Аналогами  приведенных выше определений для орграфов являются следующие.

Граф

Маршрут

Цепь

Цикл

Орграф

Путь

Простой путь

Цикл

Цикл, который включает  все вершины графа, называется гамильтоновым. Граф, который содержит гамильтонов цикл, называется гамильтоновым.

Замкнутый маршрут, который включает каждое ребро графа ровно один раз, называется эйлеровым маршрутом, а граф, который содержит такой маршрут, называется эйлеровым графом. Задачу, является ли граф эйлеровым, впервые поставил и решил Эйлер. В 1736 г. он писал: ”В городе Кенигсберге  есть два острова, которые соединяются между собой и

с берегами реки семью мостами (см. Pис. 3).

b

✟✟✟

✟✟✟

a c

❍❍❍

d

❍❍❍

Рис. 3: Граф "Кенигсбергские мосты". a и c - острова,  b и d - берега.


Можно ли спланировать прогулку так, чтобы, начиная с одного из 4 участков суши a, b, c, d,

пройти по каждому из этих мостов один раз и вернуться в начальный пункт?

Теорема 3 (Эйлер, 1736 г) Связный мультиграф  является эйлеровым тогда и только тогда, когда все его вершины имеют  четную  степень.

4.2  Алгоритм построения эйлерова цикла для неориентированно- го графа

Шаг 0. Проверяем, является ли граф G = (V, E) связным и четны ли степени его вершин. Если это не так, эйлерова цикла не существует.

Шаг 1. Выбираем произвольную вершину v1 и полагаем частичный эйлеров цикл C =

{v1}. В графе G будем двигаться от некоторой вершины частичного цикла и помечать

пройденные  ребра. Помеченное ребро будем включать в эйлеров цикл. Полагаем i = 1.

Шаг 2. Двигаемся от вершины vi  по непомеченным ребрам и помечаем их до тех пор, пока не вернемся в vi. Пусть при этом построен цикл C.

Цикл C включаем в C так, что вначале идут ребра C до вершины vi, затем ребра цикла

C и затем оставшиеся ребра C .

Если все ребра исходного  графа помечены, то эйлеров цикл построен. Если есть непоме- ченные ребра, то существует вершина vj  C , которая является концом непомеченного ребра. Пусть vj  – последняя из таких вершин, входящая в C .

Шаг 3. Удаляем из графа ребра цикла C. Полагаем i = j и переходим к Шагу  2, т.е. строим новый цикл на непомеченных ребрах, начиная с вершины vj .

Примеры. Два треугольника, имеющие общую вершину. Два четырехугольника, имею- щие общую сторону, вершины которой дополнительно соединены цепью.

4.3    Задание графов

Матрицей смежности графа G = (V, E) называется матрица A = ||aij ||n×n  с элементами aij  = 1, если {i, j} ∈ E, и aij  = 0, если {i, j} /∈ E. Для мультиграфов aij  равно кратности ребра {i, j}.

Аналогично вводится матрица смежности для орграфов. Для неориентированных графов матрица смежности полностью  определяется своей правой верхней либо левой нижней треугольной подматрицей, поскольку aij  = aji  для всех i и j.

Орграфы могут быть также  представлены одним или несколькими списками непосред-

ственных последователей A0(i) и непосредственных предшественников B0(i) каждой вер- шины i.

4.4    Топологическая сортировка

Предположим, что фирме необходимо выполнить n проектов, на множестве V = {1, . . . , n}

которых задано отношение предшествования такое, что из i j следует, что проект j

не может начаться раньше, чем закончится проект i (проект j использует информацию или


продукцию, получаемую в результате выполнения проекта i). Нужно найти допустимый порядок выполнения проектов во времени.

Рассмотрим орграф G = (V, A)  отношения  предшествования. Дуга (i, j)  A тогда и

только тогда, когда i j.

Решение задачи существует,  если орграф отношения порядка не содержит циклов. Если

есть цикл, то ни один из проектов, принадлежащих циклу, нельзя начинать.

Пусть перестановка (i1, . . . , in) определяет порядок выполнения проектов. Этот порядок является допустимым,  если из ij ik следует, что ij предшествует ik в указанной пере-

становке.

Введем понятие номера вершины – label(i)  ∈ {1, . . . , n}. Задача сводится к отысканию нумерации вершин графа G такой, что из (i, j)  A следует  label(i)  < label(j).  Тогда

последовательность проектов в порядке возрастания их номеров label(i) будет являться решением задачи. Указанная нумерация называется топологической сортировкой вершин графа.

Алгоритм топологической сортировки.

Предположим, что граф задан списками непосредственных  последователей A0(i),  i =

1, . . . , n, и, кроме того, задано количество  непосредственных предшественников  bi   каж- дой вершины i : bi  = |B0(i)|.

Шаг 1. Просматриваем список (b1, . . . , bn)  и создаем список J  = {j|bj   = 0} вершин,  у

которых нет предшественников. Если J = φ, то в графе есть цикл.

Шаг 2. Присваиваем текущий номер j (вначале j = 1) любой вершине из J . Далее рас- сматриваем всех ее непосредственных  последователей i A0(j) и преобразуем bi  = bi 1.

Если bi  = 0, то вершину i включаем в J. После того, как все множество A0(j) просмотрено, удаляем j из J. Если текущий номер не равен n, увеличиваем его на единицу. Повторяем Шаг 2.

4.5    Остовное дерево (остов) минимального веса

Граф, не имеющий циклов, называется лесом. Связный граф, не имеющий циклов, назы- вается деревом.

Пусть n и m – количества вершин и ребер графа соответственно.

Теорема 4 (Свойства деревьев) Пусть G – неориентированный  граф. Тогда следую- щие условия эквивалентны:

1) G – дерево,

2) G – связный  граф и m = n 1,

3) G – граф без циклов  и m = n 1,

4) между любой парой вершин существует единственная цепь,

5) G не имеет циклов, но при добавлении произвольного  ребра в G в нем возникает един- ственный цикл.

В ориентированном графе вводятся понятия входящего и выходящего дерева. Это орграф, неориентированный аналог которого является деревом, и,

в случае выходящего  дерева, в каждую вершину входит не более одной дуги, а


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

Подграф неориентированного графа G = (V, E) называется остовным деревом (остовом)

и обозначается T , если T – дерево и множество его вершин совпадает с V.

Граф называется (реберно) взвешенным, если каждому его ребру {i, j} приписан некото-

рый вес wij .

Весом остовного дерева называется сумма весов всех его ребер.

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

Ниже приводятся два алгоритма, которые строят остовное дерево минимального веса Tn1.

Напомним, что Tn1  не содержит циклов и имеет n 1 ребер.

Алгоритм Краскала

Шаг 1. Полагаем T0 = (V, φ), |V | = n.

Шаг 2. Для i = 0, . . . , n 1 полагаем Ti+1  = Ti e, где e – ребро G с минимальным весом

такое, что оно не является ребром Ti  и не образует цикла с ребрами Ti.

Алгоритм Прима

Шаг 1. Полагаем T1 = (V1, E1), где V1 = {a, b}, E1 = {a, b}, и wab = min{we|e E}.

Шаг 2. Для i = 1, . . . , n 1 полагаем Ti+1  = Ti e, где e – ребро G с минимальным весом

такое, что оно не является ребром Ti  и связывает Ti  с вершиной G, не принадлежащей  Ti.

Пример. Любой неориентированный  реберно взвешенный граф.

4.6    Кратчайшие пути

Рассмотрим орграф со взвешенными дугами и путь из вершины i в вершину j в этом графе. Сумма весов дуг этого пути называется его длиной. Путь минимальной длины из i в j называется кратчайшим путем из i в j.

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

Рассмотрим орграф G = (V, A) с выделенной вершиной s и весами wij , (i, j) A. Алго-

ритм присваивает вершинам временные и постоянные метки. Постоянная метка вершины

равна длине кратчайшего пути из s в эту вершину. Кроме того, формируется  массив P red, в котором P red(v) содержит номер непосредственного предшественника  вершины v в кратчайшем пути из s в v. Таким образом s, . . . , P red(P red(v)), P red(v), v является кратчайшим путем из s в v.

Алгоритм  Дейкстры  (построения кратчайших путей из вершины s во все остальные вершины орграфа в случае неотрицательных  весов дуг)

Шаг 1. (Начало). Помечаем вершину s постоянной меткой Length(s) = 0. Все осталь- ные вершины v /= s помечаются временными метками Length(v) = . Полагаем номер

итерации i = 1 и номер текущей вершины, помеченной постоянной меткой, u = s.


Шаг 2. (Рекурсия). Полагаем i = i+1. Рассмотрим вершину u. Для всех ее непосредствен- ных последователей v с временной меткой вычисляем M  = min{Length(v), Length(u) + wuv }. Если M меньше временной метки Length(v), то вычисляем новую метку Length(v) =

M и полагаем P red(v) = u.

Далее среди всех вершин с временными метками выбираем вершину k с наименьшей мет- кой и делаем ее постоянной.  Если i < n 1, то полагаем u = k и повторяем Шаг 2. Иначе

стоп: все кратчайшие  пути из s в остальные вершины могут быть восстановлены по мас- сиву Pred.

Алгоритм  построения кратчайших путей между  всеми парами вершин и проверки наличия цикла отрицательного веса (дополнительный материал). Приводимый ниже алгоритм предложен Флойдом.

Рассмотрим орграф G = (V, A). Пусть W 0 = ||wij || n × n матрица весов дуг этого графа. Полагаем wij  =

, если дуга (i, j) отсутствует, и wii  = 0 для всех i V. Алгоритм Флойда строит последовательность

ij

матриц W 1 , W 2 , . . . , W n такую, что элемент wn

 матрицы W n равен длине кратчайшего пути из i в j в

графе G. Матрица W k  определяется по матрице W k−1 :

wk k−1

 k−1

 k−1

ij = min{wij     , wik + wkj    }. (1)

ij

Пусть P k  – кратчайший путь из i в j с внутренними вершинами из множества {1, 2, . . . , k}. Справедлива

ij

Теорема 5  Для 0 k n, величина wk

 является длиной пути P k .

ij

В алгоритме Флойда одновременно с длинами кратчайших путей отыскиваются сами пути с помощью

ij

матриц Z 0 , Z 1 , . . . , Z n , где элемент zk

 матрицы Z k  указывает на вершину, непосредственно следующую

ij

за i в P k . Тогда ясно, что

 

z0

ij =

 

ij

( j, если w0

ij

0,   если w0

 

/= ,

= .

Матрица Z k  получается из Z k−1  следующим образом. Пусть M = min{wk−1 , wk−1 + wk−1 }. Тогда

( zk−1

 

k−1

 ij  ik kj

zk  ij  ,   если M = wij     ,

ij =

 zk−1

 k−1

ik   ,   если M < wij     .

Если M = wk−1 , то длина пути P k  равна длине пути P k−1 . Иначе P k  получается в результате склеивания

ij

путей P k−1  и P k−1  и zk

 ij

= zk−1 .

 ij ij

ik kj

 ij  ik

Очевидно, что кратчайший путь из i в j определяется последовательностью вершин i, i1 , i2 , . . . , ip , j, где

i1  = zn , i2  = zn

 

, i3  = zn

 

, . . . , j = zn  .

ij i1 j

 i2 j

 ip j

Отметим, что в (1) если wk−1  или wk−1  равно , то wk

 = wk−1 .

ik kj

 ij ij

Алгоритм  Флойда (построения кратчайших путей между всеми парами вершин и проверки наличия

цикла отрицательного веса)

(В процессе вычислений матрицу W k  записываем на место W k−1 , а матрицу Z k  – на место Z k−1 , k =

1, . . . , n. Таким образом, используем одно и то же обозначение W для всех W k  и Z для всех Z k .)

Шаг 1. (Начало). Полагаем k = 0. Строим матрицы W = W 0 и Z = Z 0 .

Шаг 2. (Рекурсия). Полагаем k = k + 1. Для всех таких вершин i /= k, что wik /= и всех таких вершин

j /= k, что wkj  /= , вычисляем M = min{wij , wik + wkj }. Если M < wij , то полагаем zij  = zik  и wij  = M.

Если появляется wii  < 0, то стоп: вершина i принадлежит некоторому циклу отрицательного веса.

Если все wii  0 и k = n, то стоп: wij  – длины всех кратчайших путей, а zij  – первая после i вершина в

кратчайшем пути из i в j.

Если все wii  0 и k < n, то повторяем Шаг 2.


5   Сетевое планирование и управление проектами

На практике довольно часто встречаются задачи планирования и управления сложными работами или проектами.

Примерами таких проектов могут быть

– строительство большого объекта,

– разработка комплекса компьютерных программ,

– производство самолета, ракеты или другого большого изделия,

– выпуск нового продукта,

– передислокация фирмы или производства.

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

Наиболее распространенными методами планирования и управления проектами являются

сетевые методы.

Сетевая модель проекта включает  следующее:

а) Элементарные работы (иногда называемые требованиями или операциями), которые должны быть проведены для выполнения проекта.

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

Сетевые методы включают следующее:

а) Определение или оценивание длительности pj  выполнения каждой элементарной рабо- ты j.

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

в) Использование знания критического пути для получения более экономичного и эффек- тивного расписания.

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

Некоторые работы не могут выполняться до тех пор, пора не завершится  выполнение некоторых других работ. Это может быть обусловлено технологией процесса, физически- ми ограничениями или использованием информации,  порождаемой  другими работами. Как  отмечалось в разделе ”Топологическая  сортировка”, такие ограничения называются ограничениями предшествования. Работы, не связанные ограничениями предшествования, могут выполняться независимо друг от друга, параллельно во времени.

Отношения предшествования отражаются в сетевой модели проекта.


Наиболее распространены два типа сетевых моделей, называемые 1) действие-на-вершине

и 2) действие-на-дуге.

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

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

Рассмотрим  модель 2) ”действие-на-дуге”. Как  уже  отмечалось, длительность выполне- ния проекта определяется длиной критического пути. Проект не может быть выполнен быстрее, чем длина критического (самого длинного) пути.

Алгоритм отыскания критического пути (применяется для отыскания критического пути между выделенными вершинами s и t ацикличного орграфа G = (V, A) с неотрица-

тельными весами дуг pij , (i, j) A.)

Метка вершины Length(v) соответствует длине самого длинного пути из s в v.

Шаг 1. (Начало). Помечаем вершину s меткой Length(s) = 0. Полагаем множество по- меченных вершин S = {s}.

Шаг 2. (Рекурсия). Находим непомеченную вершину v, в которую входят дуги толь-

v

ко из помеченных вершин (все вершины множества  B0

 помечены). Помечаем v меткой

v

Length(v) = max{Length(u) + puv |u B0} и включаем v в S. Если максимум достигается

0 0 0

на вершине u

 Bv , то самый длинный путь в вершину v пришел из вершины u .

Если помечена вершина t, то стоп: длина критического пути (длительность выполнения

проекта) равна Length(t) и сам путь может быть восстановлен с помощью поиска с воз- вратом. Иначе повторяем Шаг 2.

После того, как критический путь построен, для каждой работы j могут быть вычислены наиболее ранний ESj  и наиболее поздний LSj  моменты ее начала  такие, что начало работы в промежутке [ESj , LSj ] не приводит к увеличению длительности всего проекта. Начало работы ранее ESj  невозможно из-за ограничений предшествования, а ее начало  после LSj приведет к увеличению длительности проекта.

Знание указанных моментов  позволяет  реализовать  расписание  более гибко, поскольку есть возможность задержки начала выполнения некоторых работ без ущерба для дли- тельности выполнения всего проекта.

Наиболее ранние моменты начала работ ESj   равны меткам соответствующих вершин в приведенном выше алгоритме.

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

LSi  = min{LSj  p(ij)|j A0, все вершины  A0  помечены}.

i i

Значение LSi  равно T минус длина наиболее длинного  пути из вершины i в вершину t.


6   Задача коммивояжера и метод ветвей и границ

Предположим, что фирма должна провести рекламную кампанию во всех областных го- родах Беларуси, в каждом городе ровно по одному разу. Известно, сколько стоит переезд между двумя любыми городами. Фирма желает снизить свои дорожные расходы. Математическая  модель такой ситуации  называется задачей коммивояжера, которая со- стоит в следующем. Задан полный орграф. Орграф называется полным, если каждая пара вершин i и j соединена дугами (i, j) и (j, i). Известна стоимость cij  каждой дуги (i, j). Тре- буется построить гамильтонов цикл (т.е. цикл, проходящий  через каждую вершину ровно по одному разу) такой, что суммарная стоимость всех его дуг была минимальной. Отметим, что есть взаимно однозначное соответствие между гамильтоновыми  циклами (т.е. маршрутами коммивояжера) в полном графе с n вершинами и перестановками  n элементов. Перестановка  σ = (i1, . . . , in) соответствует маршруту коммивояжера, прохо- дящему через вершины i1, . . . , in и включающему дуги (i1, i2), (i2, i3), . . . , (in1, in), (in, i1). Основным методом решения задачи коммивояжера является метод ветвей  и границ (МВиГ). Этот метод является универсальным и может применяться для решения практи- чески всех задач оптимизации.

Основные принципы МВиГ для решения задачи минимизации состоят в следующем.

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

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

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

числа LB и U B такие, что

LB F U B,

где F – минимальное значение целевой функции в задаче или подзадаче, LB и U B – его нижняя и верхняя оценки соответственно.

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

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


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

3) Отсеивание вариантов. Если для некоторой  подзадачи  ее нижняя оценка превосхо- дит либо равна рекорду, такую подзадачу можно далее не ветвить, так как ее решение будет заведомо хуже либо не лучше решения, соответствующего рекорду.

4) Оптимальное решение. Процесс вычислений прекращается, когда нет ни одной под- задачи, которая может продолжать ветвиться. В этом случае оптимальное решение соот- ветствует текущему рекорду.

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

Различают методы ветвления в глубину и в ширину.

При ветвлении в глубину всегда ветвят одну из подзадач наибольшего уровня. Это быстрее приводит к построению полного допустимого решения.

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

Пример. Пусть матрица (таблица) стоимостей переезда между городами выглядит сле-

дующим образом:

город(i, j)

Минск(1)

Брест(2)

Витебск(3)

Гомель(4)

Гродно(5)

Могилев(6)

1

350

250

350

320

200

2

400

650

500

100

700

3

300

600

320

400

150

4

370

580

280

710

180

5

400

100

550

800

670

6

220

650

170

210

590

Будем решать задачу методом ветвления вглубь. Вначале построим ”приведенную задачу”, эквивалентную исходной. Используем процедуру ”приведение таблицы”, состоящую в вы- читании наименьшего числа в каждом столбце (строке), затем наименьшего числа в каж- дой строке (столбце). Суммируя эти числа (из каждого города нужно выехать и в каждый город нужно въехать), получаем ∆0  = (220 + 100 + 170 + 210 + 100 + 150) + (30 + 50) = 1030. Далее можно работать с приведенной матрицей. Для получения реальной стоимости лю- бого маршрута необходимо добавить к получаемой из приведенной таблицы стоимости величину ∆0.

Приведенная таблица:


(i, j)

1

2

3

4

5

6

1

200(250)

30(80)

90(140)

170(220)

0(50)

2

180

480

290

0

550

3

80

500

110

300

0

4

120(150)

450(480)

80(110)

580(610)

0(30)

5

180

0

380

590

520

6

0

550

0

0

490

Для элементов приведенной таблицы оставим обозначения cij .

Очевидно, что нижняя оценка для приведенной задачи равна LB(0) = 0. Для отыскания верхней оценки построим какой-нибудь маршрут коммивояжера. Например, разумным бу- дет включить в этот маршрут дугу минимальной стоимости, скажем, (2,5). Далее выбрать

дугу минимальной стоимости вида (5, j), j /= 2. Это (5,1). Далее, выбрать дугу минималь-

ной стоимости вида (1, j), j /= 2, 5. Поступая аналогично,  (1,6), (6,3), (3,4), и, без вариантов,

(4,2). Получаем верхнюю оценку U B(0) = 740. Она является рекордом R.

Далее разветвим  исходную задачу. Ветвление  будем осуществлять по вхождению или невхождению некоторой дуги в маршрут. Будем выбирать дугу нулевой стоимости,  ко- торая дает наибольшее значение  нижней оценки для подзадачи при ее невхождении   в маршрут. Дуги нулевой стоимости: (1,6), (2,5), (3,6), (4,6), (5,2), (6,1), (6,3), (6,4).

В подзадаче P (1, 6) (P (1, 6)) дуга (1,6) не входит (входит) в маршрут.

Рассмотрим подзадачу P (1, 6). Полагаем стоимость дуги (1,6) равной . Какая-то дуга из

1 должна выйти и какая-то дуга должна войти в 6. Можно добавить к нижней оценке сум-

му наименьших чисел в указанных строке и столбце, обозначаемую ∆16 = 30. Аналогично вычисляем ∆2,5, ∆3,6, ∆4,6, ∆5,2, ∆6,1, ∆6,3, ∆6,4. Наибольшее значение равно ∆5,2 = 380. Выбираем дугу (5,2) для дальнейших ветвлений. Вычисляем LB(5, 2) = LB(0)+∆5,2 = 380. Нарисуем  начальное дерево ветвлений,  состоящее из 3 вершин - начальной 0 и вершин, обозначенных (5, 2) (соответствующая дуга не входит в маршрут коммивояжера) и (5,2) (входит), см. рис.

Припишем вершинам соответствующие значения LB.

Рассмотрим подзадачу P (5, 2). Поскольку дуга (5,2) входит в маршрут, другие дуги не могут выйти из 5 и войти в 2. Вычеркиваем строку 5 и столбец 2. Кроме того, дуга

(2,5) войти в маршрут не может. Полагаем стоимость этой дуги равной . Вычисляем

5,2 = 350. После приведения таблица имеет вид:

(i, j)

1

3

4

5

6

1

30

90

0

0

2

0

300

110

370

3

80

110

130

0

4

120

80

410

0

6

0

0

0

320

Вычисляем LB(5, 2) = LB(0) + c5,2 + ∆5,2 = 350.

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


R0 = U B = c(2, 5, 1, 6, 3, 4) = 740

R1 = c(1, 5, 2, 4, 3, 6) = 540

 

LB = 46 0

24  

 LB = 540 = R1

36

✣✢

 ✒ ❅

LB = 46 0

 ✣✢

 LB = 540

15  

✒ ❅

 ❅❘ 36

LB = 35 0

 ✣✢

 LB = 650 ✣✢

52  

✒ ❅

 ❅❅❘ 24

LB = 0  

 ✣✢

 LB = 480 ✣✢

0 ❅❘

 15 ❳❳

 LB =??

✣✢

 LB = 380

 

✣✢

 ❳❳③ ??

❅❘ 52 ❳❳ LB= 580 ✣✢

✣✢

 ❳❳③ 12

 

LB =??

✣✢❆❯ ??

❆❆LB = 630 ✣✢

12

✣✢

Ответ: c= c(1, 5, 2, 4, 3, 6) = 540 + ∆0  = 540 + 1030 = 1570

Наибольшее значение ∆i,j при записи в указанные клетки равно ∆1,5 = 130. Выбира- ем дугу (1,5) для дальнейших ветвлений. В дерево ветвлений добавляем вершины  (1,5) и (1, 5), следующие за вершиной (5,2).

В подзадаче P (1, 5) дуга (1,5) не входит в маршрут. Полагаем стоимость этой дуги равной

. Вычисляем ∆1,5 = 130 и LB(1, 5) = LB(5, 2) + ∆1,5 = 480.

Рассмотрим подзадачу P (1, 5). Вычеркиваем строку 1 и столбец 5 из матрицы для под-

задачи P (5, 2). Дуга (1,5) образует путь с уже  введенной в маршрут дугой: (1,5),(5,2). Поэтому можно положить c2,1 = . Вычисляем ∆2,1.

Процесс останавливается для матриц 2 × 2. В этом случае можно найти решение либо

определить, что оно не существует. Получив новый рекорд, можно отсечь некоторые вет-

ви.

7   Имитационное  моделирование на  примере  метода

Монте-Карло

Рассмотрим ситуацию, когда операция  представляет  собой случайный процесс и пока- зателем эффективности  является вероятность какого-либо события или математическое ожидание какой-либо случайной величины. Более того, предположим, что процесс невоз- можно описать аналитически. В этом случае для моделирования  процесса применяется имитационное  моделирование, наиболее ранним представителем которого является ме- тод Монте-Карло.

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


таты которого интерпретируются с позиций математической статистики.  Рассмотрим ими- тационное моделирование на примере метода Монте-Карло  (М-К).

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

Для сложных операций, в которых участвует много элементов (машин, систем, людей, коллективов) и в которых случайные факторы сложным образом взаимодействуют  друг с другом, метод М-К как правило оказывается проще и адекватнее аналитического. Рассмотрим пример, типичный для применения  метода М-К.  На плоскости нарисована некоторая фигура. Команда из n человек (участников операции) должна выполнить сле- дующее. Каждый человек, не видя фигуры и не зная действий других участников, должен нарисовать на плоскости круг заданного радиуса r. Операция считается успешной, если круги покрыли не менее 50% площади  фигуры. Требуется определить вероятность того, что операция будет успешной.

Решение этой задачи аналитически с помощью методов теории вероятностей чрезвычайно сложно. Значительно проще решить эту задачу методом М-К.

Для этого проведем следующий эксперимент. Разыграем координаты n точек на плоскости с помощью какого-либо механизма случайного выбора. Например, пусть m – количество точек на плоскости. Разобьем интервал [0, 1] на m последовательных непересекающихся частей одинаковой длины (события выбора центра круга независимы и равновероятны). С помощью ЭВМ или по таблице выберем n (псевдо)случайных  чисел из [0, 1]. Интервалы, в которые попали эти числа, указывают координаты n точек на плоскости. Нарисуем соответствующие круги  и определим площадь покрытия фигуры. Если эта площать не менее 50%, то будем считать эксперимент успешным.

При большом количестве экспериментов N вероятность W успеха операции может быть приближенно  оценена как частота успешных экспериментов:

M

W , где M – число успешных экспериментов.

N

С помощью метода М-К можно получать не только вероятности событий, но и математи- ческие ожидания случайных величин. Например, если в рассматриваемом примере требу- ется найти не вероятность успеха операции, а математическое ожидание M [S] площади S покрытия фигуры кругами, то можно воспользоваться следующим.

В соответствии с законом больших чисел (теорема Чебышева) при большом количестве независимых  опытов среднее арифметическое полученных значений случайной величины почти наверняка мало отличается от ее математического  ожидания. Пусть Si  – площать покрытия фигуры в эксперименте i. Тогда

S

N

M [S]     i=1   i .

N


Аналогично может быть найдена дисперсия случайной величины, т.е. мат.ожидание квад- рата отклонения случайной величины от ее мат.ожидания. В нашем примере дисперсия D[S] площади покрытия фигуры может быть приближенно вычислена по формуле

N  2

N

D[S] = M [(S M [S])2]    i=1(Si M [S]) .

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

вероятности – как частоты событий,

математические ожидания – как средние арифметические значения соответствующих  слу- чайных величин,

дисперсии – как среднеквадратичные отклонения случайных величин от их среднеариф- метического значения.

Недостатком  метода является необходимость проведения большого числа розыгрышей.

8   Основы теории сложности вычислений

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

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

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

Экстремальная комбинаторная задача состоит в следующем. На конечном множестве X 1

определен функционал  F (x), x X 1. Необходимо в заданном подмножестве X множества X 1   отыскать такой элемент x, что F (x) = min{F (x)|x X } (задача минимизации),  либо такой x0, что F (x0) = max{F (x)|x X } (задача  максимизации).

Сопоставим  экстремальной  задаче B следующую задачу распознавания B1: определить,

существует ли такой элемент x1  в заданном множестве X, что F (x1) y (либо F (x1) y

в случае задачи максимизации)  для данного действительного числа y. Очевидно, если x

решение задачи минимизации B, то элемент x1  X  такой, что F (x1)  y, существует


тогда и только тогда, когда F (x) y. Таким образом, экстремальная  задача не проще

соответствующей задачи распознавания.

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

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

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

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

(а) Код примера задачи должен быть компактным и не должен содержать необязатель- ную информацию или символы.

(б) Числа из примера задачи должны  быть представлены в двоичной, либо какой-нибудь иной системе счисления с основанием, отличным от единицы.

Система счисления с основанием, равным 1, называется унарной. В этой системе число 3 представляется в виде 111, число 4 в виде 1111 и т.д. (как зарубки у древних людей). В унарной системе счисления для представления целого числа x требуется x единиц памяти. В двоичной системе счисления все числа представляются в виде последовательностей двух чисел: 0 и 1. Число 3 представляется в виде 11, число 4 в виде 100, число 5 в виде 101 и т.д. Для представления целого числа x требуется O(log2 x) нулей и единиц (единиц памяти).

Функция O(x) определяется следующим образом:

lim

x→∞

 O(x)

x

 

= const.

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

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

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


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

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

Для любого примера I некоторой задачи введем в рассмотрение две функции:

– функция Length[I ], определяющая длину кода примера I при использовании разумной схемы кодирования и

– функция M ax[I ], определяющая величину наибольшего числового параметра в I . Если задача не содержит чисел, то полагаем M ax[I ] = 1 для любого примера I .

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

Алгоритм решения задачи называется полиномиальным,  если его временная сложность не превосходит некоторого  полинома от функции Length[I ] для любого примера I этой задачи. Соответствующая задача называется полиномиально разрешимой.

Полиномиально разрешимые задачи образуют класс P.

Алгоритм решения задачи называется псевдополиномиальным, если его временная слож-

ность не превосходит некоторого полинома от двух функций: Length[I ] и M ax[I ], - для любого примера I этой задачи. Соответствующая задача называется псевдополиномиально разрешимой.

Класс  N P задач. NP-полные  и NP-трудные  задачи. Задача принадлежит классу

N P, если она может быть решена за полиномиальное время на так называемой недетер-

минированной машине Тьюринга, которая реально не существует. На такой машине за

полиномиальное время можно реализовать как полиномиальные так и некоторые неполи- номиальные алгоритмы.

Задача Π называется NP-трудной,  если любая задача из класса N P полиномиально сво-

дится к ней, т.е. имея полиномиальный алгоритм решения NP-трудной задачи, можно получить полиномиальный алгоритм решения любой задачи из класса N P. Задача рас- познавания Π называется NP-полной,  если она NP-трудна и принадлежит N P.

Понятие полиномиальной  сводимости  транзитивно. Поэтому для доказательства  NP- трудности некоторой задачи достаточно полиномиально  свести к  ней некоторую NP- трудную задачу:

для любого примера известной NP-трудной задачи за полиномиальное от его размерно- сти время построить  пример нашей задачи и показать, что решение NP-трудной задачи


существует тогда и только тогда, когда существует решение построенного примера нашей задачи.

Экстремальная  задача называется NP-трудной, если соответствующая  ей задача распо- знавания является NP-трудной.

Из существования полиномиального алгоритма решения какой-нибудь NP-трудной задачи следует существование полиномиальных  алгоритмов  решения для всех задач из класса

N P, включая все NP-полные  задачи.

Как уже отмечалось, все полиномиально разрешимые задачи полиномиально разрешимы

на недетерминированной машине Тьюринга. Поэтому

Однако неясно P = N P или P /= N P.

 P ⊆ N P.

Поскольку ни для одной NP-трудной задачи не разработан полиномиальный  алгоритм

решения, в настоящее время общепринятой является гипотеза о том, что

P /= N P.

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

За разработку полиномиального алгоритма решения любой NP-трудной задачи установлен приз в 1.000.000 долларов.

NP-трудные  в сильном смысле задачи. Наряду с разделением задач на NP-трудные и полиномиально разрешимые, NP-трудные задачи, в свою очередь, подразделяются  на NP-трудные в сильном смысле задачи и задачи, имеющие псевдополиномиальные  алго- ритмы решения. NP-трудные в сильном смысле задачи не имеют псевдополиномиального алгоритма решения.

Примеры NP-трудных задач.

NP-трудная задача, имеюшая псевдополиномиальный алгоритм решения: РАЗБИЕНИЕ:

j=1

Заданы целые положительные числа a1, a2, . . . , ar  и A такие, что r

 aj  = 2A. Требуется

определить, существует ли множество X N = {1, 2, . . . , r} такое, что jX aj  = A.

NP-трудная в сильном смысле задача:

3-РАЗБИЕНИЕ:

Заданы целые положительные  числа a1, a2, . . . , a3r   и A  такие, что A/4  < aj    < A/2,

j=1

j = 1, . . . , 3r, и 3r

 aj  = rA. Требуется определить, существует ли разбиение множества

{1, 2, . . . , 3r} на r непересекающихся подмножеств X1, X2, . . . , Xr такое, что jXl  aj  = A,

l = 1, . . . , r.

Нетрудно  заметить, если решение задачи 3-РАЗБИЕНИЕ существует, то каждое из мно- жеств X1, . . . , Xr содержит в точности три элемента.


9   Динамическое программирование

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

f (x) min, x X.

Будем формировать множества X0, X1, . . . , Xn   частичных решений, где множество Xk+1

получается из множества Xk  путем ”достраивания” каждого решения из Xk . Оптимальное решение xвыбирается из множества Xn.

С каждым частичным решением x Xk   будем связывать  некоторый набор параметров

B = (k, b1, . . . , bi), называемых переменными состояния. Набор B переменных состояния

называется состоянием.

Пусть Xk (B) обозначает множество частичных решений x Xk  в состоянии (соответству-

ющих состоянию) B. Пусть B(x) обозначает состояние частичного  решения x.

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

Из определения функции F (B) следует, что в каждом множестве Xk (B) достаточно вы- брать доминирующее решение для дальнейших построений.

Обозначим через S множество всех возможных состояний. Это множество называется

пространством состояний.

В методе ДП рекуррентно вычисляют значения F (B) и находят состояние, соответствую- щее оптимальному  решению. Затем восстанавливают  само оптимальное решение.

Для применения метода ДП необходимо корректно определить

1) пространство состояний S,

2) функцию доминирования F (B), B S,

3) способ построения частичных решений x1 Xk+1 из частичных решений x Xk ,

4) метод вычисления состояния B(x1), используя состояние B(x), если x1 Xk+1 ”достроен”

из x Xk , и

5) рекуррентную формулу для вычисления значений F (B).

Пример  алгоритма ДП. В качестве примера рассмотрим следующую задачу. Служа- щий должен выполнить n работ к заданному сроку d, начиная с момента времени ноль. Для каждой работы j задана длительность выполнения pj  и штраф wj , выплачиваемый с случае завершения j после d. Все параметры являются неотрицательными целыми чис- лами. Требуется найти такую последовательность выполнения работ, чтобы суммарный штраф был наименьшим.


При заданной последовательности работ (i1, . . . , in) легко определить момент завершения

j

выполнения каждой работы ij : Cij   =

 k=1  pik .

Введем в рассмотрение переменные Uj : Uj   = 1, если работа j является запаздывающей

(Cj  > d), и Uj  = 0, если j является ранней (Cj  d). Требуется найти такую последова-

j=1

тельность работ, что значение n

 wj Uj  минимально.

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

Тогда задача может быть сформулирована следующим образом:

при условиях

 n j=1

n

 wj Uj  min

j=1

и

 pj (1 Uj ) d,

Эта задача NP-трудна.

 Uj  ∈ {0, 1},  j = 1, . . . , n.

Пусть U = (U , . . . , U ) – оптимальный вектор для этой задачи и W – соответствующее

1 n

значение целевой функции.

Сформулированная задача, в свою очередь, может быть проинтерпретирована в терминах

ДП следующим образом.

Будем формировать частичные решения,  определяя переменные Uj   = 0 либо Uj   = 1 для j = 1, . . . , n. Будем говорить, что частичное решение (U1, . . . , Uk ) находится в со- стоянии (k, a), если определены значения переменных U1, . . . , Uk  и значение ограничения

k

j=1 pj (1 Uj ) = a.

Переменные состояния могут принимать значения k = 0, 1, . . . , n и a = 0, 1, . . . , d.

Из начального состояния (0, 0) можно перейти в состояние (1, 0), при котором U1 = 1, либо в состояние (1, p1), где U1 = 0, если p1 d.

Рассмотрим  некоторое  состояние (k, a), k ∈ {2, . . . , n}. В это состояние можно перейти только из состояния (k 1, a), если Uk = 1, либо из состояния (k 1, a pk ), если Uk = 0.

j=1

Определим функционал доминирования F (k, a) как значение целевой функции k

 wj Uj ,

вычисленное для решений в состоянии (k, a). Из определения функционала F (k, a) следует,

что

W = min{F (n, a)|a = 0, 1, . . . , d}.

Значения F (k, a) могут быть вычислены рекуррентно. Для инициализации рекуррентных вычислений положим F (0, 0) = 0 и F (k, a) = для всех (k, a) /= (0, 0).

Из определения функции F (k, a) следует, что общее рекуррентное  соотношение  может быть записано как

F (k, a) = min{F (k 1, a) + wk , F (k 1, a pk )},  (2)


k = 1, . . . , n, a = 0, 1, . . . , d.

При этом, если F (k, a) = F (k 1, a) + wk , то в частичном решении, соответствующем состоянию (k, a), переменная Uk = 1. Если же F (k, a) = F (k 1, a pk ), то в этом решении

Uk = 0.

Обратный ход. Оптимальное  решение U может быть найдено с помощью следующей

процедуры,  называемой обратный ход. Эта процедура использует таблицу размерности

n × (d + 1), в каждой ячейке (k, a) которой хранится информация о том, на первой или

второй компоненте достигается минимум в (2) для указанных значений k и a. На каж-

дой итерации этой процедуры проверяется, на первой или второй компоненте достигается минимум в (2) для определенных значений k и a. На первой итерации полагаем k = n и a = a, где aопределяется из W = F (n, a). Если минимум в (2) достигается на пер-

k

вой компоненте, то полагаем U = 1, k := k 1, оставляем a без изменений  и переходим

k

к следующей итерации процедуры обратного хода. Если минимум достигается на второй компоненте, то полагаем U = 0, a := apk , k := k 1, и переходим к следующей итерации. После выполнения n итераций будет построен оптимальный  вектор U = (U , . . . , U ).

1 n

Время работы и требуемая память. Эффективность алгоритма ДП определяется его временной сложностью  и объемом требуемой памяти. Анализ алгоритма для рассматри- ваемой задачи показывает, что вычисление F (k, a) требует выполнения одной операции сложения и одной операции сравнения для каждой пары (k, a). Таким образом, временная сложность этого алгоритма равна O(nd).

Что касается объема памяти, то следует отметить, что для вычисления оптимального зна- чения целевой функции W на каждом шаге k достаточно хранить таблицу размерности

2 × (d + 1) со значениями F (k 1, a) и F (k, a), a = 0, 1, . . . , d. Для отыскания оптимального вектора U достаточно применить процедуру обратного хода, которая требует n(d + 1)

дополнительных единиц памяти.

Из приведенного анализа можно сделать вывод, общий для всех алгоритмов ДП: времен- ная сложность и объем требуемой  памяти алгоритма ДП непосредственно зависят от мощности  соответствующего пространства состояний.

k

Выбор пространства состояний. Прямые  и обратные алгритмы  ДП. Как  пра- вило, существует несколько вариантов для выбора пространства  состояний.  Например, для рассматриваемой  задачи можно ввести состояния (k, w) такие, что частичное ре- шение находится в состоянии (k, w), если определены значения переменных U1, . . . , Uk  и

i=1 wiUi  = w. В этом случае функционал F (k, w) определяется как наименьшее значение

i=1

ограничения k

 pi(1 Ui) для решений в состоянии (k, w). Рекуррентное соотношение

можно записать в виде

F (k, w) = min

 

( F (k 1, w) + pk , если F (k 1, w) + pk d, F (k 1, w wk )

k=1

Соответствующий алгоритм ДП требует O(n  n

 

wk ) единиц времени и памяти.

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


состояний (k, a) следующим образом. Полагаем F (n + 1, 0) = 0, все остальные  начальные значения F (k, a) равными бесконечности и вычисляем

F (k, a) = min{F (k + 1, a pk ), F (k + 1, a) + wk }

для k = n, n 1, . . . , 1 и a = 0, 1, . . . , d. Оптимальное значение целевого функционала  равно

W = min{F (1, a)| a = 0, 1, . . . , d}.

Числовой пример решения задачи о рюкзаке методом ДП.

F (x) = x1 + 2x2 + x3 + x4 + 2x5 + x6 + 2x7 max,

B(x) = 2x1 + x2 + 2x3 + 2x4 + x5 + x6 + x7 5, xi  ∈ {0, 1}.

X0

(0)

F (x)

0

B(x)

0

X1

(0)

(1)

F (x)

0

1

B(x)

0

2

X2

(0,0)

(0,1)

(1,0)

(1,1)

F (x)

0

2

1

3

B(x)

0

1

2

3

X3

(0,0,0)

(0,0,1)

(0,1,0)

(0,1,1)

(1,0,0)

(1,0,1)

(1,1,0)

(1,1,1)

F (x)

0

1

2

3

1

2

3

4

B(x)

0

2

1

3

2

4

3

5

3 предпоследние частичные  решения решения можно дальше не рассматривать, так как

есть доминирующие.  Далее достраиваем только доминирующие.

X4

(0,0,0,0)

(0,0,0,1)

(0,0,1,0)

(0,0,1,1)

(0,1,0,0)

(0,1,0,1)

(0,1,1,0)

(0,1,1,1)

(1,1,1,0)

(1,1,1,1)

F (x)

0

1

1

2

2

3

3

4

4

5

B(x)

0

2

2

4

1

3

3

5

5

7

X5

(0,0,0,0,0)

(0,0,0,0,1)

(0,0,0,1,0)

(0,0,0,1,1)

(0,1,0,0,0)

(0,1,0,0,1)

(0,1,1,1,0)

(0,1,1,1,1)

F (x)

0

2

1

3

2