- •1.Основные понятия и этапы са
- •2. Операция и ее составляющие. Этапы исо
- •Этапы операционного проекта
- •Виды математических моделей ио, примеры.
- •4. Состязательные задачи. Решение игры 2-х лиц
- •7. Примеры задач лп: игра 2-х лиц как задача лп, транспортная задача
- •В общем случае модель задачи лп имеет вид
- •Сбалансированная транспортная задача
- •8 Формы представления задач лп и способы приведения к ним
- •1. Каноническая форма задач лп
- •2. Стандартная форма задачи лп
- •9. Основные понятия лп. Свойства задач лп
- •10. Геометрия задач лп, базисные решения, вырожденность.
- •4.7. Выделение вершин допустимого множества
- •11. Понятие базиса. Переход от одного базисного решения к другому
- •12. Признак оптимальности. Определение начального базисного решения.
- •13. Алгоритм симплекс-метода
- •14. Двойственность задач лп
- •4.11.1. Запись двойственной задачи в симметричном случае
- •4.11.3. Запись двойственной задачи в общем случае
- •15.Экономическая интерпретация двойственной задачи
- •16. Теоремы двойственности
- •17. Двойственный и модифицированный симплекс-метод Модифицированный алгоритм
- •18. Параметрический анализ. Параметрирование вектора ограничениий
- •Параметрирование вектора ограничениий
- •19. Параметрирование коэффициентов линейной формы
- •20. Модели транспортных задач и их характеристика, условия разрешимости.
- •Простейшая транспортная задача (т-задача)
- •Транспортная задача с ограниченными пропускными способностями (Td - задача)
- •Транспортные задачи по критерию времени
- •21. Построение начального плана перевозок т-задачи
- •5.2.1. Построение начального плана перевозок
- •Правило северо-западного угла
- •Правило минимального элемента.
- •22.Обоснование метода потенциалов
- •5.2.3. Признак оптимальности
- •23. Алгоритм метода потенциалов.
- •24. Двойственная пара транспортных задач
- •25. Метод потенциалов для Td-задачи
- •5.5. Решение задачи по критерию времени
- •26. Приведение открытой транспортной задачи к закрытой
- •27. Транспортные задачи в сетевой постановке (транспортные сети)
- •28. Задача о максимальном потоке
- •29. Метод декомпозиции Данцига - Вулфа
- •30. Решение транспортной задачи методом Данцига-Вулфа (метод декомпозиции тз)
- •32. Целочисленное программирование
- •7.1. Проблема целочисленности
- •33. Метод отсечений
- •Пример 7.1. Выведем условие отсечения для задачи
- •34. Метод ветвей и границ
- •35. Аддитивный алгоритм
- •36. Нелинейное программирование
- •Теорема
- •37. Квадратичное программирование
- •38. Сепарабельное программирование (сп) и дробно-линейное программирование
- •8.5. Задачи дробно-линейного программирования
- •39. Метод покоординатного спуска и Хука-Дживса Метод первого порядка
- •8.8. Многомерный поиск безусловного минимума
- •8.8.1. Метод Гаусса-Зейделя (покоординатного спуска)
- •Метод Хука-Дживса (метод конфигураций) Метод первого порядка
- •Метод Хука-Дживса (метод конфигураций)
- •40. Симплексный метод поиска
- •41. Градиентные методы
- •Методы сопряженных направлений
- •43. Методы случайного поиска
- •Алгоритм с возвратом при неудачном шаге
- •Алгоритм с обратным шагом
- •Алгоритм наилучшей пробы
- •Алгоритм статистического градиента
- •44. Метод проектирования градиента
- •Метод проектирования градиента
- •45. Генетические алгоритмы
- •46. Метод штрафных функций и барьерных функций
- •Метод барьерных функций
- •47. Динамическое программирование
- •48. Распределение одного вида ресурса
- •49. Дп: задачи о кратчайшем пути и с мультипликативным критерием
- •Задача с мультипликативным критерием.
- •52. Многомерные задачи динамического программирования
- •53. Снижение размерности с помощью множителей Лагранжа
- •56. Многокритериальные задачи: постановка, проблемы, осн. Понятия, методы
- •Многокритериальная задача математического программирования
- •Где искать оптимальное решение
- •Определения
- •Условия оптимальности
- •57. Многокритериальные задачи: функция полезности, лексикографический анализ
- •Методы первой группы
- •Функция полезности
- •Решение на основе лексикографического упорядочения критериев
- •58. Методы главного критерия, свертки, идеальной точки, целевого прогр. Метод главного критерия
- •Линейная свертка
- •Максиминная свертка
- •Метод идеальной точки
- •Целевое программирование (цп)
- •59. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
Задача с мультипликативным критерием.
В качестве примера рассмотрим задачу о надежности некоторого устройства, состоящего из N последовательно соединенных блоков. Повышение надежности устройства обеспечивается включением дублирующих элементов в отдельные блоки. В общем случае ограничивающими факторами могут выступать затраты на дублирование, вес и/или объем устройства, надежность переключательных схем и др. Пусть основным ограничением являются затраты на дублирование Q и, кроме того, известны Сj - стоимость одного дублирующего элемента для блока j и jj(mj) - вероятность безотказной работы j-го блока с mj дублирующими элементами. Задача состоит в определении оптимальной стратегии дублирования в пределах выделенных средств.
Очевидно, что в качестве критерия следует взять вероятность безотказной работы всего устройства P, которая при последовательном соединении блоков равна произведению вероятностей этих блоков. Поэтому модель задачи будет иметь вид
, (9.25)
. (9.26)
В этой модели целевая функция является мультипликативной, что, однако, не мешает применению метода ДП. Действительно, и в критерии, и в ограничении можно выделить составляющие их функции, описывающие отдельные блоки, хотя операторы, примененные к этим частным функциям в (9.25) и (9.26), разные. Поэтому задача представима как многошаговая, а шагом является определение числа дублирующих элементов для одного блока. В последовательности шагов расположение блоков может не соответствовать реальной схеме их соединения в устройстве. Порядок расположения фиксируется исходя из соображений, которые были приведены в разделе 9.3.
Пронумеруем шаги, как и ранее, справа налево. Очевидно, что для принятия решения нужно знать свои возможности, которые в данной задаче определяются средствами на дублирование. Поэтому в качестве параметра состояния следует взять допустимый уровень затрат на дублирование q, который на любом шаге может принимать любые значения из диапазона [0,Q].
Теперь можно ввести последовательность функций {fk(q)}, k=1,N. Каждая функция имеет смысл максимальной вероятности безотказной работы k оставшихся блоков при допустимом уровне затрат на дублирование q:
. (9.27)
Для получения функционального уравнения рассмотрим k блоков, на дублирование которых можно затратить q средств. Если в k-й блок включить mk дублирующих элементов, а оставшиеся после этого средства (q-Сkmk) использовать оптимально на дублирование k-1 блоков, то с учетом (9.27) и последовательного соединения k-го блока с остальными k-1 блоками вероятность безотказной работы k блоков будет равна
[jk(mk)fk-1(q-Сkmk)]. Максимизируя это выражение по mk, приходим к искомому рекуррентному соотношению
(9.28)
где [q/Сk] означает целую часть от q/Сk.
Условная оптимизация начинается с вычисления первой функции последовательности
и затем продолжается по формуле (9.28). Безусловная оптимизация проводится в обратном порядке, то есть от fN к f1, с исходного состояния qN=Q и последующим пересчетом по уравнению состояния
qk-1 = qk - Сkmk .
Таким образом, мультипликативность целевой функции не изменяет процедуру динамического программирования. Отличие от ранее рассмотренных задач лишь в том, что выражение в правой части рекуррентного соотношения не аддитивное, а мультипликативное. Очевидно, что мультипликативность ограничения или одновременно ограничения и целевой функции также не вызовет осложнений.
50. Задача организации выпуска m видов продукции
Фирма ежемесячно выпускает m видов продукции, на которые имеется равномерный спрос. По каждому виду продукции известны:
С1i - затраты на хранение единицы продукции i-го вида в единицу времени;
С2i - затраты на запуск в производство одной партии i-го вида;
Ri - месячный спрос на продукцию i-го вида.
Для выпуска одной партии требуется один цикл производства. Изменение числа партий приводит к изменению затрат на производство одного и того же количества продукции. В течение месяца фирма может организовать не более N циклов. В этих условиях нужно так организовать производство, чтобы при полном удовлетворении спроса обеспечить минимальные затраты фирмы.
При построении модели примем одно допущение, обусловленное отсутствием необходимых данных и не имеющее принципиального значения: время выпуска партии много меньше продолжительности цикла и поэтому им можно пренебречь. График изменения уровня готовой продукции на фирме представлен на рис.9.9,
Рис. 9.9
где - объем партии продукции i-го вида; ti - продолжительность цикла по i-му виду продукции (в долях месяца).
Критерий, суммарные затраты на все виды продукции, определим следующим образом. Затраты на хранение и выпуск партии i-го вида продукции за время одного цикла составят
а так как количество циклов, необходимое для выпуска продукции в объеме Ri
то затраты на весь объем продукции i-го вида запишутся в виде
.
Суммируя затраты по всем видам продукции, получим критерий задачи
. (9.14)
Добавив к выражению критерия очевидные ограничения
, (9.15)
завершаем построение модели задачи.
По структуре эта модель аналогична рассмотренной в предыдущем разделе, так что применимость метода ДП к задаче (9.14),(9.15) не требует дополнительных доказательств. В качестве параметра состояния здесь следует взять n - максимальное количество циклов, которое может быть организовано для выпуска продукции (1nN), а за шаг примем организацию выпуска одного вида продукции. Построив из видов продукции последовательность, порядок следования в которой определяется из соображений, приведенных в предыдущем разделе, приходим к m-шаговой задаче.
Введем последовательность функций {fn(n)}, так, что каждая функция определяется как минимальные затраты на выпуск k видов продукции в заданных количествах при условии, что можно организовать до n циклов, то есть
. (9.16)
Здесь опущен индекс у параметра состояния n, так как он совпадает с индексом функции и поэтому не обязателен. Как и в предыдущей задаче, выделив из k видов (k>1) k-й и все остальные k-1 видов продукции и применив принцип оптимальности, получим затраты на k видов
Qk(uk) + fk-1(n-uk).
В этом выражении новое состояние определяется через исходное n и число циклов uk на выпуск k-го вида продукции: на k-1 видов остается n-uk циклов (имеем очевидное уравнение состояния nk-1=nk –uk ).
Так как для фиксированного n затраты зависят только от uk, то минимизируя их по uk в области допустимых значений, приходим к рекуррентному соотношению
. (9.17)
Почему же в этой формуле такое ограничение сверху на uk? Дело в том, что выпуск продукции оговорен величиной Ri, поэтому, чтобы обеспечить выпуск k-1 видов продукции, нужно иметь хотя бы по одному циклу на каждый вид и, следовательно, максимальное число циклов на k-й вид равно n-(k-1).
Первая функция вычисляется непосредственно по определению (9.16):
. (9.18)
Для численного примера ограничимся тремя видами продукции и N=7. Остальные данные следующие:
-
1
2
3
1
2
1
10
8
5
320
200
490
Условная оптимизация начинается с вычисления функции f1 согласно формуле (9.18). При этом можно воспользоваться классическим методом, так как требуется найти минимум дифференцируемой функции на интервале. Приравняв первую производную выражения в скобках правой части (9.18) нулю, найдем стационарную точку
.
С учетом ограничений на u1 оптимальное решение будет иметь вид
(9.19)
где [ ]- целая часть . По исходным данным получаем =9. Подставив в (9.18) исходные данные и оптимальное u1, приходим к расчетной формуле
,
по которой с учетом (9.19) составляем табл. 9.1.
Таблица 9. 1
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
1 |
2 |
3 |
4 |
4 |
4 |
4 |
|
170 |
100 |
83,3 |
80 |
80 |
80 |
80 |
На втором шаге расчет ведем по рекуррентной формуле (9.17):
(9.20)
где .
Находить минимум в (9.20) будем перебором допустимых u2. Для удобства ручных расчетов в промежуточную таблицу (табл. 9.2п) предварительно внесем во второй столбец значения Q2(u2) для всех возможных u2 и во вторую строку значения f1(n), взятые из табл. 9.1. Для отыскания минимума сначала фиксируем состояние, то есть значение n, а затем ведем перебор u2. Начнем с n=1. Расчет выпуска двух видов продукции в этом случае теряет смысл, так как на 2-й вид не остается ни одного цикла - во всех клетках столбца с этим значением n ставим прочерк. Берем n=2. При этом возможен только один вариант: на 2-й вид продукции отводится один цикл. Соответствующие затраты составят
Q2(1) + f1(2-1)=208+170=378,
они записываются в клетку на пересечении строки с u2=1 и столбца с n=2. Очевидно, что эти значения затрат и числа циклов являются оптимальными относительно состояния n=2 и поэтому их записываем в клетки нижних строк как значения u2* и f2(n). Теперь фиксируем n=3 и вычисляем затраты для двух допустимых значений u2:
при u2=1 Q2(1) + f1(3-1)=208 + 100=308,
при u2=2 Q2(2) + f1(3-2)=116 + 170=286.
Минимальными являются затраты при u2=2, поэтому f2(3)=286 и u2*=2, что и записываем в соответствующие клетки нижних строк.
В табл. 9.2п обнаруживается свойство, обусловленное структурой формулы (9.20), которое позволяет вести расчет по простой схеме прямо в таблице, не обращаясь каждый раз к формуле (9.20): для подсчета затрат в текущей клетке нужно складывать значение из 2-го столбца данной строки со значением, взятым из строки f1 в клетке, в которую попадаем, двигаясь по диагонали от текущей клетки.
Таблица 9.2п
|
|
n |
||||||||
U2 |
Q2(u2) |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
||
|
|
f1(n) |
||||||||
|
|
170 |
100 |
83,3 |
80 |
80 |
80 |
80 |
||
1 |
208
|
- |
208 170 378 |
208 100 308 |
208 83,3 291,3 |
208 80 288 |
208 80 288 |
208 80 288 |
||
2 |
116 |
|
- |
116 170 286 |
116 100 216 |
116 83,3 199,3 |
116 80 216 |
116 80 216 |
||
3 |
90,7 |
|
|
- |
90,7 170 260,7 |
90,7 100 190,7 |
90,7 83,3 174,0 |
90,7 80 170,7 |
||
4 |
82 |
|
|
|
- |
82 170 252 |
82 100 182 |
82 83,3 165,3 |
||
5 |
80 |
|
|
|
|
- |
80 170 250 |
80 100 180 |
||
6 |
81,3 |
|
|
|
|
|
- |
81,3 170 251,3 |
||
|
|
- |
1 |
2 |
2 |
3 |
3 |
4 |
||
|
|
- |
378 |
286 |
216 |
190,7 |
174 |
165,3 |
Аналогично проводим расчет для n от 4 до 7 включительно, занося получающиеся значения в табл. 9.2п. Этим завершается расчет на втором шаге. Результаты сохраняются в виде табл. 9.2.
Таблица 9.2
-
1
2
3
4
5
6
7
-
1
2
2
3
3
4
-
378
286
216
190,7
174
165,3
Теперь переходим к третьему шагу расчета, которому соответствует рекуррентная формула
(9.21)
где .
Как и на предыдущем шаге, вычисления выполним в промежуточной таблице (табл. 9.3п), в которую переносятся значения f2 из табл. 9.2 и предварительно рассчитанные значения Q3(u3). Схема расчета полностью идентична 2-му шагу, но расчет по трем видам продукции приобретает смысл начиная с n=3.
Таблица 9.3п
|
|
n |
|||||
U3 |
Q3(u3) |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
f2(n) |
|||||
|
|
378 |
286 |
216 |
190,7 |
174 |
165,3 |
1 |
250
|
- |
250 378 628 |
250 286 536 |
250 216 466 |
250 190,7 440,7 |
250 174 424 |
2 |
132,5 |
|
- |
132,5 378 510,5 |
132,5 286 418,5 |
132,5 216 348,5 |
132,5 190,7 323,2 |
3 |
96,7 |
|
|
- |
96,7 378 474,7 |
96,7 286 382,7 |
96,7 216 312,7 |
4 |
81,2 |
|
|
|
- |
81,2 378 459,2 |
81,2 286 367,2 |
5 |
74 |
|
|
|
|
- |
74 378 452 |
|
|
- |
1 |
2 |
2 |
2 |
3 |
|
|
- |
628 |
510,5 |
418,5 |
348,5 |
312,7 |
Как и выше, можно пользоваться формальным правилом подсчета затрат без обращения к рекуррентной формуле. Из табл. 9.3п получаем табл. 9.3, которую необходимо сохранить. На этом заканчивается расчет 3-го шага и весь этап условной оптимизации.
-
1
2
3
4
5
6
1
2
2
2
2
3
-
628
510,5
418,5
348,5
312,7
Далее следует безусловная оптимизация. Пусть для выпуска трех видов продукции можно организовать 5 циклов (N=5). Тогда по начальному состоянию n=5 входим в табл. 9.3 (показано стрелкой). Из нее устанавливаем, что минимальные затраты на три вида продукции составляют 418,5, при этом по 3-му виду должно быть организовано 2 цикла, то есть весь заказ выполняется двумя запусками. Согласно уравнению состояния на остальные два вида остается 3 цикла. Поэтому по состоянию n=3 входим в табл. 9.2, как указывает стрелка, и извлекаем из нее u2*=2, то есть весь заказ тоже делится на 2 партии. Соответствующая величина f2(3)=286 означает затраты на 1-й и 2-й виды продукции при оптимальной организации производства. Новое состояние n=3-2=1 определяет вход в табл. 9.1, из которой берем u2*=1, и тем самым завершаем нахождение оптимального решения.
Действуя аналогично, нетрудно убедиться, что при N=7 оптимальное решение будет таким: минимальные затраты, равные 312,7, достигаются при u1*=2, u2*=2, u3*=3. Теперь ясно, что мы можем получить оптимальное решение для любых n в диапазоне от 3 до 7. Если же 3-й вид продукции будет исключен, то нам не потребуется делать полный пересчет: достаточно с заданным значением n=N войти в табл. 9.2, а затем по пересчитанному состоянию в табл. 9.1, чтобы получить соответствующее оптимальное решение. Например, для N=7 будем иметь u2*=4, u1*=3, а минимальные затраты составят 165,3. Однако, если из системы будет исключен 2-й или 1-й вид продукции, без пересчета этапа условной оптимизации уже не обойтись. Что именно надо считать заново в каждом из этих случаев, предлагается определить самостоятельно.
Анализ табл. 9.3 показывает, что с увеличением N уменьшаются минимальные затраты. Поэтому интересно посмотреть, что будет при значениях N, превышающих 7. Если расширить табл. 9.1-9.3 до n=20 по тем же формулам (9.18)-(9.21), то увидим, что наименьшие минимальные затраты равны 230 и достигаются они при N³16. Таким образом, увеличение возможного числа циклов с 7 до 16 могло бы привести к снижению затрат на 82,7. Естественно возникает вопрос: правомерно ли рекомендовать производству перейти на организацию 16 циклов? На первый взгляд кажется, что такой вариант явно выгоден и потому правомерен. Однако произойдет ли при этом реальное снижение затрат? Чтобы ответить на эти вопросы, нужно обратиться не к рекуррентным соотношениям, а к модели задачи. При построении модели предполагалось, что в пределах возможного числа циклов N используемое число циклов не влияет на затраты. Очевидно, что организация циклов сверх N потребует дополнительных ресурсов (оборудования, оснастки и пр.), то есть увеличения затрат, чего модель не учитывает. Следовательно, модель адекватна только в пределах справедливости указанного допущения и делать по ней выводы за этими пределами неправомерно. Чтобы выяснить, возможно ли снижение затрат при переходе на большее число циклов, нужно ввести в критерий статью затрат, связанную с организацией дополнительного количества циклов, и заново решить задачу.
Второй численный пример, рассматриваемый ниже, близок к задаче о лабиринте, описанной в начале главы, но имеет и свои отличия от всех ранее приведенных задач.