Министерство образования Российской Федерации

Тверской Государственный университет

Факультет прикладной математики и кибернетики

Н. Д. Дроздов

Алгоритмы дискретного программирования

Учебное пособие

Тверь. 2000 г.

УДК 519. 854 (075.8)

ББК В 183. 43я731-1

Д 75

Алгоритмы дискретного программирования. Учебное пособие. /

Н.Д.Дроздов. Твер. Гос. ун-т. Тверь. стр.82

Изложены методы дискретного программирования (оптимизации):

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

Рекомендовано советом факультета прикладной математики и кибернетики ТвГУ для использования в учебном процессе студентами по специальностям "Прикладная математика и информатика", "Математические методы и исследование операций в экономике".

Рис. 16. Библиогр. 14 назв.

Печатается по решению редакционно-издательского совета Тверского государственного университета.

Рецензенты: доктор технических наук, профессор Неффа В. М, доктор технических наук, профессор Гриднев В. Р.

Тверской Государственный Университет. 2000 г.

Содержание стр.

1. Предмет дискретного программирования ……………………………. 2. Модели задач дискретного программирования …………………….... 3. Методы отсечения ……………………………………………………. 3.1. Теоретические основы метода …………………………………… 3.2. 1-ый алгоритм Гомори. Построение правильного отсечения ….. 3.3. Пример решения 1-м алгоритмом Гомори задачи ЦЛП ………... 3.4. Правильное отсечение в алгоритме Дальтона-Ллевилина ……... 4. Венгерский алгоритм решения задачи о назначении ………………. 4.1. Математическая модель задачи о назначении…………………... 4.2. Пример решения задачи о назначении венгерским алгоритмом 5. Метод ветвей и границ ……………………………………………….. 5.1. Теоретические основы метода ветвей и границ ………………... 5.2. Общая схема метода ветвей и границ (задача на минимум) …... 6. Решение методом ветвей и границ задачи целочисленного линейного программирования - метод Лэнд и Дойг ………………… 6.1. Алгоритм метода Лэнд и Дойг …………………………………... 6.2. Пример решения задачи ЦЛП методом Лэнд и Дойг …………. 7. Решение методом ветвей и границ задачи о коммивояжере ……… 7.1. Алгоритм метода ВиГ в задаче о коммивояжере ……………… 7.2. Пример решения задачи о коммивояжере методом ВиГ ……… 8. Динамическое программирование ………………………………….. 8.1. Теоретические основы динамического программирования …... 8.2. Примеры задач, решаемых методом динамического программирования …………………………….. 8.2.1. Задача о наборе самолетом высоты и скорости………….. 8.2.2. Решение методом динамического программирования

8.2.3. Задача о распределении кредита …………………………… 8.2.4. Задача об оценке эффективности системы по критерию ……………………………………... 9. Динамическое программирование в стохастических задачах …….. 9.1. Задача о ремонте ………………………………………………… 9.2. Задача о выпуске партии консервов …………………………… 10. Метод построения последовательности планов …………………… 10.1. Общая схема метода …………………………………………….. 10.2. Схема упорядочения планов.

Метод ветвления - элиминаций ………………………………… 10.3. Упорядочение планов одной вспомогательной задачи ……... 10.4. Решение методом ППП одно-продуктовой задачи размещения производства ……………………………………… 10.4.1. Постановка задачи ………………………………………… 10.4.2. Алгоритм решения однопродуктовой задачи размещения производства ……………………………………………………… 10.4.3. Пример решения задачи размещения производства …….. 11. Приближенные методы ……………………………………………. 11.1. Общие положения ……………………………………………… …………………………………. 11.3. Пожирающие алгоритмы (методы последовательного назначения единиц) ……………………………………………. 11.4. Статистически эффективные алгоритмы ……………………… ………………………………. 11.5.1 Теоретические основы методов ……………………………. 11.5.2. Алгоритм локальной оптимизации (вариант) ……………. …………………………………….. ………………………………………………….. Литература ……………………………………………………………….. 1.Предмет дискретного программирования Задачей дискретного программирования (ДП) будем называть задачу отыскания экстремума (max, min) скалярной функции, заданной на дискретном (несвязном) множестве, т.е. такую задачу математического программирования (МП), у которой на все или на часть переменных, определяющих область допустимых решений, наложено требование дискретности.

Запишем задачу МП в виде:

(1) где x = (x1,…, xj,.., xn) - n - мерный вектор;

Если - конечное (или счетное) множество или декартово произведение конечного (счетного) множества на множество мощности континуума, то будет иметь место задача ДП. В этом случае условие принадлежности x некоторому множеству может быть записано в виде:

(2) При n1 < n - задача частично дискретного программирования.

Если k - множество всех целочисленных векторов, то имеет место при n1 = n задача целочисленного программирования (ЦП). А при n1 < n задача частично целочисленного программирования (ЧЦП).

В наибольшей степени изучены методы решения задач целочисленного линейного программирования (ЦЛП):

(3) целых чисел, Частный случай задач ЦЛП - задачи с булевыми переменными, где в (3) В ряде задач ЦП требование целочисленности накладывается и на целевую функцию.

';

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

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

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

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

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

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

«Последний» рекорд и является оптимальным решением задачи.. Этот подход составляет основу метода ВиГ и реализован для задач ЦЛП и ЧЦЛП в алгоритме Ленд и Дойг.

2). Ставится цель наискорейшего извлечения оптимального плана из множеств допустимых планов задачи. С этой целью:

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

- последовательно производится просмотр и оценка каждого элемента последовательности, отсеиваются неперспективные планы, уточняется рекорд:

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

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

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

Задача о рюкзаке. Турист должен упаковать в рюкзак предметы nнаименований, известны вес каждого предмета и максимально допустимый вес снаряженного рюкзака.

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

Математическую постановку задачи можно сформулировать следующим образом.

Обозначим:

x - количество j - ых предметов (предметов j-го наименования), qj - вес одного j - го предмета, cj - ценность j - го предмета, Q - предельно допустимый вес рюкзака.

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

Если каждый предмет следует взять не более, чем в одном экземпляре запишем:

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

К задаче о рюкзаке сводится большое число прикладных задач.

Вопросы и упражнения.

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

В. 2.1. Задача о назначениях. Имеется n работ и n кандидатов на выполнение этих работ. Каждый "кандидат" может выполнить только одну работу. Известно, что выполнение i-м кандидатом j-ой работы связана с затратами, равными ci,j (или, приведет к прибыли ci,j ). Все значения: ci,j известны. Необходимо так распределить работы между кандидатами на их выполнение, чтобы минимизировать суммарные затраты (или максимизировать суммарную прибыль).

Как изменится математическая постановка задачи, если i-й кандидат может быть назначен только на некоторое подмножество работ Si?

В. 2.2. Задача о коммивояжере. Коммивояжер должен посетить n городов и вернуться в тот город, из которого выехал. Каждый i-й город ( i =1, n ) коммивояжер должен посетить только один раз. ci,j - затраты на переезд из i-го города в j-ый.

Необходимо составить такой маршрут, чтобы минимизировать суммарные затраты.

В. 2.3. Задача о покрытии. Задано множество S, состоящее из m элементов, S = (,...,,..., ) и конечное множество его подмножеств Необходимо найти минимальное покрытие множества S, т.е. такой минимальный набор подмножеств Si,, при котором каждый элемент множества S принадлежал хотя бы одному подмножеству из набора.

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

производственной программы. На предприятии выпускается n наименований неделимой продукции, j =1, n. При выпуске которой используется m наименований сырья i =1, m.

Известно: cj - стоимость единицы j-ой продукции;

bi - имеющееся в расположении предприятия количество i-го сырья;

ai,j - количество i-го сырья, расходуемое на единицу j-го продукта.

Необходимо максимизировать суммарную стоимость.

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

В.2.6. В приведенных ниже примерах сравнить два метода решения:

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

2) Нахождение оптимума задачи ДП.

Пример 2. Садовнику необходимо приобрести 107 кг. удобрений, которые продаются мешками весом 35 кг. по 14 руб. за мешок и весом кг. по 12 руб. за мешок. Необходимо минимизировать стоимость покупки.

3.1 Теоретические основы методов отсечения Алгоритмы методов отсечения разработаны для решения полностью или частично целочисленных и дискретных задач линейного программирования. Общая схема методов отсечения заключается в переходе от решения задачи целочисленного (дискретного) линейного программирования (ЦЛП) последовательности задач линейного программирования (ЛП) – “ kF – задач”, k=0,1,2,… 0F - задача получается из цF - задачи снятием требования целочисленности (дискретности).

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

После решения каждой k-ой задачи ЛП (k = 0,1,2,...) проверятся удовлетворяет ли полученное оптимальное решение условиям исходной цF - задачи. При положительном ответе итерационный процесс решения kF - задач прекращается - полученное оптимальное решение задачи ЛП является и решением исходной задачи.

Решение каждой k-ой задачи ЛП называется k-ой большой итерацией.

Доказывается, что при выполнении определенных условий решение исходной задачи будет получено через конечное число итераций. Если задачи ЛП не имеют решения, не имеет решения и исходная задача. Блоксхема алгоритма показана на рис. 3.1.

k:=k+ отсечение Рис. 3. Дополнительные ограничения - правильные отсечения - должны:

- быть линейными;

- являться “отсечением”, т.е. отсекать от области допустимых решений ту ее часть, которая содержит оптимальное решение задачи ЛП, не удовлетворяющее требованиям исходной задачи;

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

Известны три алгоритма отсечения:

1). 1-ый алгоритм Гомори решения целочисленной задачи ЛП.

2). 2-ой алгоритм Гомори решения частично целочисленной задачи ЛП.

3). Алгоритм Дальтона-Ллевилина решения дискретной задачи ЛП.

Общая формула построения правильного отсечения для всех алгоритмов запишется в следующем виде:

где xj - небазисные переменные оптимального решения k-ой задачи ЛП – “ kF – задачи”, 0 j - определяются по коэффициентам разложения базисной переменной, не удовлетворяющей требованиям целочисленности (дискретности) исходной задачи по небазисным переменным в последней симплекс-таблице kF - задачи ЛП (строка симплекс-таблицы с найденным оптимальным значением задачи ЛП).

3.2. 1- ый алгоритм Гомори. Построение правильного отсечения Запишем задачу ЦЛП в виде Пусть xi - нецелая координата в оптимальном решении задачи ЛП.

Обозначим: НБ - совокупность небазисных переменных в последней (соответствующей оптимальному решению) симплекс-таблицы задачи ЛП.

Разложение xi по небазисным переменным имеет вид Обозначим: [xi] - целое число, не превосходящее xi, { xi }= xi -[ xi].

Справедлива следующая теорема Теорема 3.1.

1-го алгоритма Гомори, (3.5) 3.3 Пример решения 1-м алгоритмом Гомори задачи ЦЛП Отбрасывая требования целочисленности, решаем задачу ЛП с помощью симплекс-алгоритма. Последняя симплекс-таблица имеет вид:

Таким образом, оптимальное решение 0F - задачи правильного отсечения координату x3.

Тогда согласно (3.5) [x3,0] = 0, {x3,0} = 7/10;

Будем обозначать новую переменную (zi) как xn+k+1, здесь k - номер kF - задачи. Тогда для правильного отсечения получим Записав новое ограничение в последнюю симплекс-таблицу 0F задачи, получим первую симплекс-таблицу 1F - задачи.

Решение 1F – задачи. Вводим вектор А7 поскольку -7/10 не допустимое решение. Вводим А5.

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

Оптимальное решение исходной задачи x={2,2,1}, f(x) = 19.

3.4. Правильное отсечение в алгоритме Дальтона-Ллевилина В задачах, решаемых алгоритмом Дальтона-Ллевилина, область допустимых значений задается следующим образом Полагаем, что коэффициенты Aj проранжированы, т.е. Аj1 < Аj2 < …< Аjmj.

Если x( kF) не удовлетворяет требованиям исходной задачи и Aiv < x i 0 < Aiv+1 тогда, используя i-ю строку симплекс-таблицы, запишем правильное ограничение в виде Замечания Для того, чтобы при вводе правильных отсечений ограничить размеры 1.) симплекс-таблицы, Гомори предложил после решения очередной задачи ЛП вычеркивать из таблицы переменную, по которой построено правильное ограничение.

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

Вопросы и упражнения.

3.1. Доказать теорему 3.1.

3.2. Произвести все большие итерации в задаче п. 3.3.

3.3. Найти оптимальное решение следующей задачи 4.Венгерский алгоритм решения задачи о назначении 4.1. Математическая модель задачи о назначении Задачу (4.1.)-(4.4.) можно рассматривать как частный случай транспортной задачи. Ввиду очевидных особенностей задачи о назначении для ее решения могут быть использованы более простые алгоритмы, чем алгоритм решения транспортной задачи. Далее рассматривается венгерский алгоритм.

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

Пусть C = (cij) - матрица эффективности (затрат) в задаче о назначении.

Определение. Две матрицы C = (cij) и D=(dij) назовем здесь эквивалентными, если одна из них получается из другой путем прибавления к элементам каждой строки (столбца) одного и того же числа, причем для разных строк (столбцов) эти числа могут быть разными.

Например, cij = dij + fi+ ej, i,j = 1, n Теорема. Множество оптимальных назначений двух задач с эквивалентными матрицами совпадают.

В венгерском алгоритме осуществляется переход от поставленной задачи с матрицей С к задаче с эквивалентной матрицей D, к которой предъявляются следующие требования:

эта матрица должна быть матрицей задачи на минимум;

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

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

Этапы алгоритма.

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

а) Если С - матрица задачи на максимум, перейти к задаче на минимум:

(cij ) (-cij ).

б) Вычесть из всех элементов каждого j - го столбца минимальный элемент этого столбца.

в) Вычесть из всех элементов каждой i -ой строки минимальный элемент этой строки.

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

2) Проверяем, является ли полученный правильный набор полным. Если "да" - процесс закончен, "нет" - переходим к п.3.

3) Отмечаем (например, знаком "+" сверху) столбцы, в которых имеется 0*. Считаем эти столбцы занятыми. Будем называть элементы матрицы, находящиеся в занятых столбцах и строках, "занятыми". В противном случае - элементы "незанятые".

4) Ищем незанятые нули, просматривая матрицу в принятом (п.1) порядке.

Если незанятых нулей нет, переходим к п.6.

Если незанятый нуль найден, отмечаем его штрихом, например, 0' и 5) Проверяем, есть ли 0* в строчке, в которой появился 0'. Если "да", то занимаем (знаком "+") эту строчку и "освобождаем" (убираем знак "+") столбец, в котором находится 0* вновь занятой строки. Возвращаемся к п.4. Если "нет", то переходим к п.7.

6) Находим минимальный среди незанятых элементов, вычитаем его из всех элементов незанятых строк и прибавляем ко всем элементам занятых столбцов. Все знаки сохраняются. Возвращаемся к п.4.

7) Строим цепочку от 0' по столбцам к 0* и от 0* по строчкам к 0'.

Цепочка начинается от 0', стоящего в строчке, в которой не оказалось 0* и заканчивается 0', стоящим в столбце, где нет 0*.

Заменяем в цепочке штрих у нулей на звездочку: 0' 0*, а у 0* звездочку стираем. Убираем в матрице все отметки, кроме "*" у нулей и переходим к п.2.

В примере на рис. 4.1. п.7 иллюстрируется на двух матрицах, вначале строится цепочка, а в следующей матрице корректируются отметки у нулей. В пятой по порядку матрице цепочка включает один 0 (элемент d3,2 ). В примере получено решение:

Вопросы и упражнения В.4.1. Доказать теорему 2.1. об эквивалентных матрицах В.4.2. Построить блок-схему венгерского алгоритма.

В.4.3. "Объяснить" п.6, 7 алгоритма.

Кроме того, объяснить, как связаны дополнительные преобразования п.6 и оптимальное значение целевой функции. Почему в "цепочке" нулей со штрихом всегда больше (на один) нулей со звездочкой? Как уточнить п.1, чтобы сделать алгоритм более быстрым?

В.4.4. Можно ли с помощью венгерского алгоритма получить все множества оптимальных значений?

В.4.5. Решить венгерским алгоритмом задачи о назначениях на максимум со следующими матрицами эффективности:

Задача дискретного программирования записывается в общем виде, как:

R - конечное множество, f(x) - целевая функция, x = (x1,…,xn).

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

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

Алгоритмом ветвления (дробления) назовем правило разбиения исходного множества на несколько подмножеств, затем разбиение каждого из полученных подмножеств до тех пор, пока после каждого конечного числа шагов элементами разбиения будут отдельные точки множества. Таким образом, если Hk - список (множество) подмножеств, подлежащих анализу на k-ом шаге алгоритма, то предполагается существование некоторой функции ветвления, определенной на совокупности Hk всех подмножеств множества, и ставящей в конечное число подмножеств l : ( i)={ l }, таких, что:

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

Разбиению будет подвергаться множество. Разбиение множества на подмножества l с помощью правила порождает разбиение множества допустимых решений на подмножества l = l.

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

Схемы полного и одностороннего ветвления иллюстрирует рис.5.1.

3-й шаг На рис. цифры у кружков являются оценками (в данном примере "нижними границами") соответствующих множеств.

При полном ветвлении на очередном шаге для дальнейшего ветвления берется множество 1, как имеющее минимальное значение из всех оценок концевых множеств i, i= 1,3,21,22,23.

При одностороннем ветвлении на очередном шаге ветвлению подлежит множество 21, имеющее минимальную оценку среди множеств, получившихся при ветвлении на предыдущем шаге: 21, 22, 23.

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

Числовую функцию, определенную на множестве Н подмножества, назовем системой оценки ветвления. Значение этой функции на подмножестве, полученном при ветвлении, назовем оценкой этого множества.

После того, как введены понятия "ветвление" и "оценка множества" можно дать формальное определение метода В и Г.

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

Оценка любого подмножества, полученного при ветвлении, не больше минимального значения целевой функции f на этом подмножестве Для любого множества l, полученного при ветвлении, его оценка не меньше оценки того множества i, разбиением которого оно получено, т.е.

3. Оценка множества, состоящего из одной точки, равна значению функции в этой точке: ( i) = f(xi), если =1, т.е. i =xi.

Оценки ( i) в задачах минимизации являются нижними границами для значений функции f(x) на оцениваемом множестве i.

В задачах максимизации для функции необходимо заменить в условии (1) "не больше" на "не меньше" и в (2) - "не меньше" на "не больше". Соответственно, получаемые оценки будут верхними границами.

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

Для вычисления ( i), как правило, строится и решается некоторая оптимизационная задача простой структуры, являющаяся оценочной для требованиям для.

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

Кроме нижней границы (оценки) в задаче минимизации вычисляется рекорд для оптимального значения функции f(x) на. Рекордом называется функция f*(Hk), определенная для любой совокупности (списка) Hk подмножеств i и удовлетворяющая таким соотношениям:

а) f*(Hk) min{f(x):x };

Условие б) гарантирует, что f*(Hk) не больше значений целевой функции при наилучшем допустимом решении, отвечающем висящей вершине xi на Hk.

Допустимое решение x*, обладающее этими свойствами f(x*) = f*(Hk) называется рекордным решением.

В задачах на максимум при определении рекорда необходимо в а) и б) заменить знаки неравенства на обратные и "min" на "max".

Рекорд характеризует приближение к оптимальному решению.

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

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

Основной элиминирующий тест. Если для некоторого множества i Hk справедливо (в задаче на минимум) ( i) > f*(Hk), то множество i исключается из списка Hk (в задачах на максимум тест имеет вид Для конкретных задач строятся и другие элиминирующие тесты. Во многих модификациях метода В и Г используют несколько способов вычисления оценок. Если не сработал приведенный выше критерий, ищут более точную нижнюю границу.

Замечание. Если f(Hk) min{f(x):x };, но f(Hk) > ( i), то на основе приведенного теста нельзя исключить множество i. Отсюда и следует желательность приближения нижней границы к оптимальному значению f(x) на i.

5.2. Общая схема метода ветвей и границ (задача на минимум) а) Формирование начального списка множеств Полагаем x0- в общем случае произвольная точка, принадлежащая 0 или точка оптимума, найденная приближенным методом, таким, что обеспечено условие (для задачи на минимум): f*(Hk) min{f(x):x };, Может быть также принято f*(Hk) =.

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

1) Анализ списка Если Hk-1 пуст, то работа закончена, причем, в противном случае задача не имеет решения.

2) Уточнение рекорда. Выбор кандидата для ветвления.

а) Из списка Hk-1 выбирается кандидат k.

Возможное правило выбора k: ( k ) = min ( p ).

б) Производится ветвление множества k согласно принятому правилу ( k)={ l} и вычисление нижних границ l. Некоторые l могут быть одноэлементными l = xl и ( l) = f(xl).

в) Уточняется рекорд f*(Hk ) =min{ f*(Hk-1 ), minf(x),xl } 3) Формирование нового списка.

Все множества списка проверяются по основному тесту. Множества r такие, что ( r) > f*(Hk-1) из списка исключаются.

осуществляется переход к k+1 шагу.

6. Решение методом ветвей и границ задачи целочисленного линейного программирования -метод Лэнд и Дойг программирования Задачу (1-4) будем называть F задачей, а задачу (1-3), не содержащую требования целочисленности, - 0F задачей.

В алгоритме Ленд и Дойг при решении задачи ЦЛП методом В и Г:

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

2) В качестве оценочной функции (верхней границы) принимается для множества - 0 и его разбиений - к оптимальные решения задачи (1Правило выбора множеств - к для ветвления (в случае задачи на максимум):

4) Правило ветвления:

Пусть для множества k получено оптимальное значение целевой функции x k = ( x k,1,..., x k, j,..., x k,n ).

Выбираем по какому-либо правилу одну из нецелочисленных координат. Например: x k,r = min x k, j.

[x *, j ] - целая часть j -ой координаты оптимального решения задачи ЛП.

5) Основной элиминирующий тест 6) На 0-ом шаге, если при решении 0F -задачи (задачи 1-3) будет получено целочисленное решение, то это будет и решением цF - задачи.

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

6.2. Пример решения задачи целочисленного линейного Для уяснения метода Лэнд и Дойг проанализируем шаги метода на следующем простом примере.

Для наглядности задачи ЛП решаются графически (рис. 6.1 (а,б)), 6.3.(а,б).

Последовательные шаги решения иллюстрируются также деревом решений (рис.6.2).

0-й шаг. Решаем задачу ЛП (5-8). На рис. 6.1.а видно, что максимум целевой функции будет достигнут в точке А.

Принимаем в качестве верхней границы ( 0 ) = 29 и рекорд f(H0) = В списке H0 одно множество 0 - рис 6.1а I-й Шаг. Разбиваем 0 на два подмножества по правилу (10) по координате x1 (рис. 6.1б).

Множество 0 из списка исключается, включаются множества 1 и 2, которые определяют две задачи ЛП. В первой задаче к (5-7) добавляется условие x1 1, во второй задаче - условие x1 2. Ясно, что при принятом правиле ветвления ни одна целая точка исходной задачи не будет потеряна и что алгоритм вычисления верхней границы удовлетворяет всем требованиям. После решения задачи ЛП имеем:

Так как (2 ) > ( 1 ), то для дальнейшего ветвления выбирается множество 2.

2-й Шаг. Разбиваем 2 на два подмножества по нецелочисленной координате x2 (рис. 4.4a).

Решаем задачу линейного программирования, в которой к (5-7) исходной задачи добавим условия x1 2 и x2 2, т.е. определим область допустимых решений 21.

Получим для максимума (точка "D" на рис. 6.3а):

Так как Добавляя к ограничениям множества 21 ограничения x1 2 и x (рис.6.3б), получим две новые задачи ЛП, оптимальное решение которых:

x * = 2; x * = 2; 211 = 4 (точка Е для множества допустимых решений 211), x * = 3; x * = 1; 212 = 4 (точка F для множества допустимых решений 212) Соответственно, f*(H3) = 4.

В списке есть еще множество 1. Так как ( 1) < f*(H3), то 1 из списка исключается. Список исчерпан.

В допустимых множествах 212 и 212 получены два решения, которые и являются оптимальными решениями исходной ЦF задачи.

Оптимальное значение целевой функции f(x*) = max f(x) = 4, x ц.

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

Введем дополнительные определения С = (сij) - матрица издержек (затрат);

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

(ik il) - звено цикла, каждая пара городов, входящая в цикл;

- множество допустимых планов, содержащее все возможные циклы.

Математическая постановка задачи - модель Таккера (7.1) (7.2) (7.3) (7.5) Метод В и Г в задаче коммивояжера содержит приведение матриц и алгоритм ветвления и вычисления оценок. Концевые множества и их ветвление будут определяться приведенными матрицами, связанными с концевыми множествами.

А. Приведение матриц.

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

Сумма всех вычитаемых в процессе приведения элементов называется приводящей константой. Обозначим эту константу.

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

где c ij -элемент приведенной матрицы.

Оптимальные маршруты в задаче с приведенной матрицей ( c ij ) совпадут с оптимальными маршрутами исходной задачи. Приводящая константа исходной матрицы и явится нижней границей всего множества возможных маршрутов Б. Ветвление множества маршрутов и вычисление нижних границ Введем обозначение. Если маршрутов (допустимых решений), то к = {(i1,i2),…,(ik,ik+1)|| (ik+1,ik+2,),…, (ir,ir+1)} такое множество маршрутов, в которое обязательно входят звенья (i1,i2),…,(ik,ik+1), а включение звеньев (ik+1,ik+2,),…,(ir,ir+1) запрещено.

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

Из матрицы множества i выбираются звенья, для которых. Для всех таких звеньев вычисляется в такое звено, для которого имеет место Алгоритм включает "большую итерацию", в результате которой получаем новый k-й замкнутый маршрут и, соответственно, издержки этого маршрута z(k), а также этапы (шаги) последовательного ветвления Укрупненная блок-схема приведена на рис.7.1. Подробная блоксхема на рис. 7.2. Далее номера всех этапов приводятся в соответствии с блок-схемой алгоритма - рис. 7.2.

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

информации Приведение Ветвление 2) Приведение матрицы k и вычисление нижней границы ( k) 8) После получения k-го замкнутого маршрута и его оценки z(k) 10) Анализ списка. Если список пуст, полученный k*-ый маршрут, для которого zk = f*(Hk), оптимальный. В противном случае переход к Восстанавливается матрица множества k и переход к п.2.

1.Ввод информации 2. Приведение матрицы n.

Вычисление (k) l. Вычисление (l )= (k)+ *kr Если (l ) f*(Hk), то l заносится в 5. Приведе- 6.Составля (l)= (k )+ l f*(Hk) Рис. 7.2. Блок-схема алгоритма задачи коммивояжера.

3) По приведенной матрице множества k находится звено (k,r) для включения в множество k и соответственно разбиения множества k Если ( ) f ( H ), множество включается в список, в противном случае множество отбрасывается.

Формируется матрица множества l, путем вычеркивания k-й строки и r-го столбца, а также запрещения звена, которое может сформировать частный замкнутый маршрут.

4) Проверяется, имеет ли матрица l размер 2 2. Если "нет", то переходим к п.5. Если "да" - к п.6.

5) Матрица l приводится. Вычисляется нижняя граница множества 7) Множество l проверяется по основному тесту Если "нет", то возвращаемся к п.3. Если "да", то переходим к п.10.

6) Добавляется к числу звеньев, обязательно включаемых в множество l, еще два звена. Пусть это будут звенья (p,q) и (l,m).

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

1) Исходная информация: матрица издержек для задачи коммивояжера с Знак "" означает запрет на переезд - т.е это некоторое настолько большое число, что при минимизации затрат, этот переезд заведомо не будет выбран.

Приведение матрицы c(i,j ) и вычисление приводящей константы.

Соответственно, (0 ) = 0 = Выбираем из (i,j) первое по списку, т.е. (i,j) =(1,2).

Сформируем перспективное множество 1, включив в него звено 1 ={(1,2)} Соответственно зачеркнем в матрице 0 строку 1 и столбец 2 и, чтобы исключить "местную петлю", запретим переезд из города 2 в Процесс ветвления на этом и последующих шагах показан на рис.7.3.

Вычисление нижней границы множества 4) Множество имеет размерность более, чем (2 2), поэтому переходим к п.5 основного алгоритма.

* За повторяющимися процедурами сохраняется и тот же номер.

Матрица множества 4) Так как матрица имеет размерность 2 2, процесс ветвления прекращается.

6,8) Формируется множество, состоящее из одного маршрута 9) Проверка концевых множеств списка по основному тесту Ветвление множества Ветвление множества на всех этапах показано на рис.7.4.

К рис. 7.4: ={(1, 3) (1, 2)}; = {(1, 3), ( 2,4) (1, 2)} ;

(1,3) 4) Матрица множества Из вида матрицы следует, что 4 = множества В множество включаем звено (2,4).

исключается из списка.

5) Получен маршрут t2 ={(1,3),(3,2),(2,4),(4,1)}.

8) z2 = f*(H1) 9,10) Других множеств в списке нет.

Маршруты (1)и (2) являются оптимальными, z1 =z2 =16.

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

В.7.2. Решить методом ветвей и границ задачи коммивояжера со следующими матрицами затрат В.7.3. Составить алгоритм метода В и Г для решения задачи о назначении. Решить, используя разработанный алгоритм, задачи о назначении, приведенные в п.4.2. Сравнить результаты решения задач о назначении венгерским алгоритмом и алгоритмом метода В и Г.

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

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

1). Задача должна допускать интерпретацию в виде n-этапного (шагового) процесса принятия решения. Решение начинается с последнего n-го этапа и продолжается до 1-го. В процессе решения происходит переход от k-го этапа к k-1-му.

2). Должны быть заданы:

а) Zk - вектор переменных, описывающих возможные состояния системы (процесса) на каждом этапе - вектор фазовых состояний системы, k =1, n, z i,k Z k i-ое - одно из возможных состояний системы на k-ом этапе;

б). X i,k - вектор управлений - набор возможных управлений при нахождений системы на k-м этапе в i-м состоянии, x l,i,k - l-ое, одно из возможных, управлений;

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

W = Wk, где Wk - выигрыш (потери) на k- этапе.

Таким образом, на каждом k-м этапе система (процесс) может находиться в одном возможном для этого этапа состояний - z Z. Вi,k k каждом состоянии системы может быть принято одно из возможных, согласно условиям задачи (операции), решений (управлений).

В результате принятия решения система (процесс) переходит в одно из Zk+1 состояний - zk+1,p(xl,i,k), при этом имеет место приращение выигрыша (потерь), равное Wk ( x l,i,k ).

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

После нахождения условных оптимумов для всех состояний системы на всех этапах от n-го до 1-го определяется безусловный оптимум, для чего необходимо пройти последовательно по всем этапам в обратном направлении от 1-го этапа до последнего Основное рекуррентное соотношение метода имеет вид Wk (zi,k ) = extrem{ Wk (zi,k,xl,i,k ) + Wk 1(zp,k+ 1)}, где при выборе управления xr,i,k, доставившего экстремум (минимум, максимум) функции W ( z ), имеет место: k i,k Wk ( z i,k ) - условный экстремум при нахождении системы на k-м этапе в состоянии zi,k ;

Wk +1 ( z p,k +1 ) - условный экстремум при нахождении системы на k+1м этапе в состоянии zp,k+1, причем управление xj,i,k, доставившее экстремум функции, Wk ( z i,k ), перевело систему из соcтояния zi,k на kм этапе в состояние zp,k+1 на k+1-м этапе Wk ( z i,k, x j,i,k ) приращение целевой функции на этапе k при выборе управления xj,i,k.

Примеры задач, решаемых методом динамического 8.2.1. Задача о наборе самолетом высоты и скорости Необходимо найти минимальный расход горючего при наборе самолётом заданных скорости Vn и высоты Hn, если в начальный момент самолёт находится в точке S0, характеризующейся значениями V=V0, H=H0.

Предполагается, что процесс набора заданных Vn и Hn может рассматриваться как пошаговый. Если самолёт находится в точке Sk={Vk,Hk}, то он может перейти в одну из точек Расход горючего при возможных переходах в другую точку (состояние) для каждого Sk приведён на рис. 8.1.

Решение начинаем с рассмотрения перехода в точку (состояние) Sn={Vn,Hn} из состояний S n-1, минимизирующие расход горючего – Q.

Затем рассматриваются переходы из предыдущих состояний S n-2 в S n-1 и т.д. Процесс для первых двух шагов показан на рис.8.2. В кружках показано значение min Q [S k Sn].

При переходе из S n-2 в S n- суммарный расход горючего Q (S”n-2S’n) = Q*расх. = minQ = 8.2.2. Решение методом ДП задачи дискретного линейного программирования Рассматривается задача а) Вывод основного рекуррентного соотношения В рассматриваемой задаче множество состояний системы на каждом kом этапе динамического программирования – это множество возможных значений ограничений (z =0, 1, 2, …, b), которые следует учитывать при поиске управлений, обеспечивающих условные экстремумы, а множество управлений – это множество значений Для k = 1 – 1-го шага динамического программирования запишем Здесь нумерация ведется по этапам динамического программирования.

Основное рекуррентное соотношение для произвольного k-го шага запишется в виде где: z = 0, 1, 2, …, b;

Для последнего шага динамического программирования:

б) Алгоритм решения задачи 1) Начинаем с вычисления W1(z).

Результаты записываются в таблицу 1 (см далее на примере).

2) Вычисляем W2 ( z ), также для всех z = 0, 1, 2, …, b, используя при этом данные табл.1.

возможные для этого z значения x2. Одновременно находим x*2, обеспечивающий max W2(z). Результаты заносим в таблицу для W2(z) и x*2(z).

Аналогично используя предыдущие таблицы, получаем таблицы значений Wk(z), k=2,3,…,n-1.

Функцию Wn(z) табулировать не нужно, достаточно найти одновременно находим x*n и, используя предыдущие таблицы для (n-1)– ых шагов, определим остальные x*k, k=1,…,n-1.

Так, из таблицы для (n-1) – ого шага определим x*n-1 = x (b-anx*n).

Аналогично для (n-2)–ого шага x*n-1 = x (b-anx*n-an-1x*n-1).

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

В табл. 3 показан поиск max W3 для z=b.

W(x*) = max W(x) = 10, x*3=3, (b-a3x*3)=1, из табл. из табл.1 для W1 получаем x*1=0.

Итак, x* = (0,1,3), Wmax = 10.

8.2.3. Задача о распределении кредита В этом примере реализуются положения метода, изложенные в предыдущем пункте Пусть сумма в 5 млрд. может быть вложена (инвестирована) в четыре предприятия. Эта сумма может быть разделена произвольно с зависимости от суммы вложения для каждого предприятия показана в табл. 1.

Из данных таблицы следует, что инвестиция в 1 млрд. в предприятие даст прибыль в 5 млн., в пр. 2 - 4 млн., в пр. 3 - 3 млн., в пр. 4 - 6млн.

Аналогично интерпретируются данные остальных столбцов таблицы.

Необходимо так распределить 5 млрд., чтобы получить максимум суммарной прибыли.

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

Поскольку здесь номер предприятия условен на конечном этапе можно рассмотреть любое предприятие. Пусть это будет предприятие №1.

Для конечного 4-го этапа (нумерация этапов ведется от начала процесса) возможны шесть состояний системы z: осталось для выделения 1-му предприятию 0, 1, 2, 3, 4, 5 млрд. Управление единственное для каждого состояния - оставшаяся сумма передается предприятию №1.

Полученная прибыль приведена в табл.2.

W4* На этапе 3 производится распределение средств между 1-м и 2-м предприятиями. Возможны те же шесть состояний, что и в предыдущем случае, однако для каждого состояния возможны шесть решений: 2-му предприятию выделяется 0, 1, 2, 3, 4, 5млрд., соответственно. Результаты распределения - прибыль, полученная при распределении оставшихся сумм между предприятиями 1 и 2, показаны в табл.3. В таблице значения x3 -управления - суммы, выделяемые предприятию 2.

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

W3 = max(W3 + W4 ) Тогда прибыль от 2-х млрд. составит 10 млн., оставшейся 1млрд.

передается предприятию 1 и даст прибыль в 5 млн. Суммарная прибыль при таком решении о распределении 3 млрд. составит 15 млн., что и показано в таблице. Для каждого состояния системы определяется решение, обеспечивающее максимум прибыли. Соответствующие цифры выделены в столбцах и перенесены на последнюю строчку. Таким образом, получен результат оптимального распределения средств между 1-м и 2-м предприятиями, т.е. получены условные оптимумы для 3-го этапа.

W2 = max(W2 + W3 ) Информация относительно следующего 2-го этапа содержится в табл.4.

На этом этапе происходит распределение вложений между 1, 2 и предприятиями. Состояний системы по-прежнему шесть (верхняя строка таблицы). Управление для каждого состояния заключается в выделении 3му предприятию от 0 до 5 млрд.(левый столбец таблицы). При выделении какой либо суммы 3-му предприятию результат оптимального распределения остатка между 1 и 2 предприятиями берется из последней строки таблицы 3. Например, в состоянии 4 (делятся 4 млрд.) принимается решение выделить 3-му предприятию 1 млрд., что обеспечит прибыль в млн., распределение оставшихся 3-х млрд. даст прибыль в 15 млн.

Суммарный результат в таблице - 18 млн. Максимизируя прибыль для каждого состояния системы (по столбцам), получим на последней строчке таблицы результат оптимального распределения выделяемой суммы между 1, 2 и 3 предприятиями (условные оптимумы для каждого состояния системы).

Последний (1-ый с начала нумерации) этап. Распределяется вся сумма.

Управление заключается в том, какую часть этой суммы выделяется 4-му предприятию. Результат оптимального распределения остатка берется из последней строки таблицы 4. Информация относительно 1-го этапа содержится в табл. Как следует из анализа табл.5, максимальная прибыль в 26 млн. будет получена при выделении 4-му предприятию 2 млрд. Чтобы выяснить, как при этом должна распределяться оставшаяся сумма в 3 млрд., возвратимся назад последовательно к таблицам 4, 3, 2.

Из табл.4 следует, что для состояния 3 оптимум будет получен, если 3му предприятию ничего не выделяется, т.е. сохраняется состояние 3.

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

Таким образом, оптимальное управление обеспечивается вектором (1, 2, 0, 2), что соответствует прибыли в 26 млн. Действительно, если обратиться для проверки к таблице 1, получим, что выделение предприятиям 1, 2, 3, 4, соответственно 1, 2, 0, 2 млрд. даст суммарную прибыль 5+10+0+11=26 млн.

8.2.4. Задача об оценке эффективности системы по критерию "затраты-эффект" Задача оценки эффективности функционирования предприятия по критерию «затраты - эффект» возникает, когда появляется необходимость выбора совокупности реализуемых мероприятий в условиях ограниченных инвестиций таким образом, чтобы максимизировать эффект этого выбора.

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

Для оценки возможности предприятия наиболее эффективно использовать имеющиеся средства строится зависимость “затраты – эффект” по каждому критерию. Рассмотрим метод ее построения на примере, предложенном в (Л).

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

Далее расположим мероприятия по эффективности, соответственно изменив их номера, как это показано в таблице 2.

Таблица 2 затрат и эффекта нарастающим итогом и является зависимостью “затраты – эффект” по соответствующему критерию.

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

240x1 + 300x2 + 80x3 + 50x4 max, при ограничениях:

xj = 1, если мероприятие j реализуется;

xj = 0, в противном случае.

Алгоритм поиска оптимального набора мероприятий для любого объема финансирования.

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

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

Предложенный подход имеет и преимущество, при определенных значениях переменных Si (i = 1, n ) он позволяет значительно сократить объем последующих расчетов.

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

Если объем финансирования z меньше затрат S1, необходимых для реализации 1 –го мероприятия, то мероприятие не может быть выполнено и, следовательно, оно не приносит эффекта, т.е.

W1(z) = 0, в противном случае выполнение 1 –го мероприятия дает эффект Q1, т.е. W1(z) = Q1.

Результаты записываем в таблицу 2.1.

Для k = 2, 3, …, n вычислим максимальный эффект от реализации k мероприятий Wk(z) для всех z, используя при этом результаты таблицы 2. и основное соотношение динамического программирования для Wk-1(z).

Результаты заносим в таблицу 1. Задаем объем финансирования R.

Определяем максимальный эффект Qmax при объеме финансирования R.

Находим последнее z, для которого выполняется неравенство z R и одновременно находим Qmax = Wn(z).

финансирования R. Для этого используем результаты таблицы 2.1, построенной на предыдущих шагах.

Если Wk(z) = Wk-1(z), то не следует выполнять k –ое мероприятие, т.е.

неизрасходованных средств. Расчет производим для k = n, n-1, …, 2.

Вычислительная схема предложенного алгоритма, по существу, дает решение не одной задачи, а множества задач с любыми значениями объема финансирования R. Поэтому при изменении R не надо решать задачу заново, а следует сразу перейти к п. 5 алгоритма. В результате получаем не единственное значение Qmax, а функцию Qmax (z) = Wn(z) (зависимость «затраты - эффект»), которую можно использовать для исследования чувствительности Qmax к вариации исходного параметра R (например, определить ) и для решения задач привлечения финансовых ресурсов.

Таким образом, вычислительный процесс оказывается гибким и удобно приспосабливается к изменению R без перестройки ранее выполненных Результаты (таблица и график) вычислений, проведенных для рассматриваемого примера, показаны на рис 8.2.

При наличии зависимости «затраты – эффект» можно решать задачи привлечения дополнительных ресурсов, в частности взятия кредита Рассмотрим пример.

Пусть имеется 90 единиц ресурса, а кредит можно взять под 300%.

Какой величины кредит взять, чтобы получить максимальный финансовый результат?

Из графика на рис. 3 видно, что следует рассмотреть 4 варианта – взять кредит 10, 70, 110 и 160 единиц.

При взятии кредита 10 единиц дополнительный эффект составит 300 – 240 = 60 единиц, т.е. эффективность составит 600%, что выше ставки кредита. Это значит, что брать кредит целесообразно.

Кредит в размере 70 единиц даст дополнительный эффект 540 – 240 = 300 единиц, эффективность 430%, что также выше ставки процента.

Кредит в 110 ед., доп. эффект 620 – 240 = 380, эффективность 345%,что также выше ставки процента.

Кредит в 160 ед., доп. эффект 670 – 240 = 430, эффективность 281%, ниже ставки процента.

Таким образом, оптимальная величина кредита равна 70 единиц, что дает эффект 540 единиц и, за вычетом процентов за кредит 540 – 3 70 = единиц.

Зависимость «затраты – эффект» характеризует потенциал предприятия по соответствующему критерию. Зная эту зависимость, можно определить минимальный уровень финансирования, достаточный для достижения поставленных целей. Или, при ограниченных финансах определить максимальный уровень, который можно достичь по заданному критерию.

Так например, если поставлена цель обеспечить по данному критерию эффект в 600 единиц, то при заданном множестве мероприятий для этого потребуется не менее 200 единиц финансовых ресурсов. Из графика видно, что эффект будет 620 единиц, но при уменьшении финансирования он сразу падает до 540 единиц и цель не будет достигнута. Если же имеется всего 150 единиц финансовых ресурсов, то максимальный уровень достижимого эффекта составит 380 единиц и для этого достаточно всего 140 единиц финансовых ресурсов.

Задача формирования программы развития - выбора набора мероприятий при наличии определенных средств - с учетом всех целей:

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

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

На рис 8.3. для примера приведена такая структура для трех критериев оценки программы развития: экономической эффективности (Э), уровня жизни (Ж), и экологической безопасности (Б). Из понятия уровень жизни здесь выделена экология. Далее естественно объединить критерии уровня жизни и экологической безопасности в один агрегированный критерий, названный здесь социальный уровень (С). Далее, при объединении критериев Э и С получим комплексную оценку социально-экономического уровня, который обеспечивается анализируемой программой. На каждом узле дерева агрегируются только две оценки.

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

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

экологии приоритет имеет показатель "уровень жизни".

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

Далее показана комплексная оценка социально-экономического уровня.

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

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

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

Пусть при работе на некотором станке в течение недели будет получен доход Q = 100 р., а при выходе на этом отрезке времени станка из строя доход Q = 0 р. Если будет предварительно проведена профилактика, то вероятность выхода станка из строя равна q = 0,4, в противном случае, профилактики 20 р. Целесообразно или не целесообразно проводить профилактику?

Для решения этой задач методом динамического программирования построим дерево решения (рис.9.1.). На рисунке кружками показаны узлы (состояния системы), где решение принимает человек, квадратами - узлы, где решение носит вероятностный характер.

На 1 этапе принимается решение проводить или нет профилактику.

На 2 этапе для одного состояния системы станок выходит из строя с вероятностью 0,4, исправен в течение недели с вероятностью 0,6. Для другого состояния эти вероятности равны 0,7 и 0,3 соответственно. Выбор проводит природа.

Анализ начинается с последнего этапа. На последнем этапе возможны 4-ре состояния. Соответствующий выигрыш W3 показан в кружках. Оценку 2-го этапа проведем по математическому ожиданию.

Для одного состояния эта оценка W 2 = 100 0,6 + 0 0,4 = 60, для другого W 2 = 100 0,3 + 0 0,7 = 30. Эти оценки помещены в квадраты. Оценка последнего этапа (1-го по нумерации): в случае профилактики выигрыш равен W1-= 60 - 20 = 40 р., без профилактики W1 = 30 р. Решение:

проводить профилактику W = 40р.

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

Результат Массового Выпуска Итак, возможны решения.

1) Отказаться от выпуска.

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

Дерево решений имеет вид, показанный на рис 9.2.

Последовательно, начиная с последнего этапа, вычисляются условные оптимумы.

Узлы (7),(8),(9). Чтобы подсчитать максимальные значения целевой функции на 1-м шаге, необходимо знать условные вероятности – условную вероятность события “У”, если имело место событие “а”