Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
74. Вырожденный случай.
Рассмотрим задачу:
z=3x1 + 9x2max
x1 + 4x2 8 ,
x1 + 2x2 4 ,
x1, x2 0.
Введя балансовые переменные x3и x4, решим обычный симплекс метод:
|
Х1 |
Х2 |
Х3 |
Х4 |
Ci |
|
|
X3 |
1 |
4 |
1 |
0 |
8 |
|
X4 |
1 |
2 |
0 |
1 |
4 |
|
L |
-3 |
-9 |
0 |
0 |
|
Х1 |
Х2 |
Х3 |
Х4 |
Ci |
|
|
X2 |
1/4 |
1 |
1/4 |
0 |
2 |
|
X4 |
1/2 |
0 |
-1/2 |
1 |
0 |
|
L |
-3/4 |
0 |
9/4 |
0 |
18 |
|
Х1 |
Х2 |
Х3 |
Х4 |
Ci |
|
|
X2 |
1 |
1/2 |
-1/2 |
2 |
|
|
X1 |
1 |
0 |
-1 |
2 |
0 |
|
L |
0 |
0 |
3/2 |
3/2 |
18 |
На начальной итерации в качестве исключаемой переменной можно выбрать как x3 , так и x4. Выбрана переменная x3 , тогда переменная x4, оставаясь базисной на итерации 1, принимает нулевое значение, а это приводит к получению вырожденного базисного решения. Оптимальное решение задачи получается на следующей итерации. Сравнивая итерации 1 и 2, заметим следующее: хотя состав базисных и небазисных переменных на этих итерациях различен, значения всех переменных и целевой функции не изменяются:
x1 = 0, x2 = 2, x3 = 0, x4 = 0, L= 18.
Это обстоятельство может привести к выводу о целесообразности прекращения вычислений на итерации 1 (когда впервые обнаруживается вырожденность), хотя полученное решение не является оптимальным.
75. Нахождение исходного (опорного) базисного решения задачи ЛП.
Каноническая задача линейного программирования в векторной форме имеет вид:
Положительным координатам допустимых решений ставятся в соответствие векторы условий. Эти системы векторов зависимы, так как число входящих в них векторов больше размерности векторов.
Базисным решением системы называется частное решение, в котором неосновные переменные имеют нулевые значения. Любая система уравнений имеет конечное число базисных решений, равное , где – число неизвестных, – ранг системы векторов условий. Базисные решения, координаты которых удовлетворяют условию неотрицательности, являются опорными.
Опорным решением задачи линейного программирования называется такое допустимое решение , для которого векторы условий, соответствующие положительным координатам , линейно независимы.
Число отличных от нуля координат опорного решения не может превосходить ранга системы векторов условий (т.е. числа линейно независимых уравнений системы ограничений).
Если число отличных от нуля координат опорного решения равно , то такое решение называется невырожденным, в противном случае, если число отличных от нуля координат опорного решения меньше , такое решение называется вырожденным.
Базисом опорного решения называется базис системы векторов условий задачи, в состав которой входят векторы, соответствующие отличным от нуля координатам опорного решения.
Теорема. Любое опорное решение является угловой точкой области допустимых решений.
Теорема. Любая угловая точка области допустимых решений является опорным решением.
76. Свойство двойственности задач ЛП.
С каждой задачей ЛП связана другая задача, которая называется двойственной или сопряженной. Первоначальная задача ЛП называется исходной или прямой. Связь между прямой и двойственной задачами заключается в том, что решение одной из них может быть получено из решения другой.
77. Несимметричные двойственные задачи.
Исходная задача имеет вид:
|
(5) |
,
или, в матричной форме,
|
(6) |
Двойственная задача в несимметричной форме имеет вид
|
(7) |
или, в матричной форме,
|
(8) |
Обратите внимание на то, что в несимметричной двойственной задаче не накладывается условие неотрицательности переменных. Если исходная задача линейного программирования записана в произвольной форме, то для записи двойственной задачи следует сначала записать исходную задачу в канонической или стандартной форме, а затем выписать двойственную задачу.
78. Симметричные двойственные задачи
Рассмотрим задачу линейного программирования в стандартной форме
|
(1) |
,
или, в матричной форме,
|
(2) |
Рассмотрим теперь следующую задачу
|
(3) |
,
или, в матричной форме,
|
(4) |
Пара задач (1) и (3) (или, в матричной форме, пара задач (2) и (4)) называются двойственными друг другу задачами в симметричной форме.
79. Теоремы двойственности.
Теорема 1: Если одна из двойственных задач имеет оптимальное решение, то другая также имеет оптимальное решение, причем для любых оптимальных решений выполняется равенство
Если одна из двойственных задач неразрешима из-за(или, то другая задача также не имеет допустимых решений.
Теорема 2: Для оптимальности допустимых решений и пары двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений
=0
0
Если в оптимальном решении одной из двойственных задач какая-либо переменная строго больше нуля, то соответствующее ей ограничение в другой двойственной задаче выполняется как строгое равенство, и наоборот, если при оптимальном решении одной из двойственных задач какое-либо ограничение выполняется как строгое неравенство, то соответствующая ему переменная в оптимальном решении другой задачи равна нулю.
80. Виды математических моделей двойственных задач
На основании рассмотренных несимметричных и симметричных двойственных задач можно заключить, что математические модели пары двойственных задач могут иметь один из следующих видов.
Н е с и м м е т р и ч н ы е з а д а ч и
(1) Исходная задача Двойственная задача
Zmin = CX; fmax = YA0;
AX = A0; YA С.
X 0.
(2) Исходная задача Двойственная задача
Zmax = CX; fmin = YA0;
AX = A0; YA С.
X 0.
С и м м е т р и ч н ы е з а д а ч и
(3) Исходная задача Двойственная задача
Zmin = CX; fmax = YA0;
AXA0; YA С.
X 0. Y 0.
(4) Исходная задача Двойственная задача
Zmax = CX; fmin = YA0;
AXA0; YA С.
X 0. Y 0.
Таким образом, прежде чем записать двойственную задачу для данной исходной, систему ограничений исходной задачи необходимо привести к соответствующему виду.
81. Транспортная задача.
Транспортная задача – одна из распространенных задач линейного программирования. Её цель – разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д. Транспортные задачи бывают открытые и закрытые.
Если сумма запасов груза равна суммарной потребности в нем, то транспортная задача называется закрытой. Если сумма запасов груза не равна суммарной потребности в нем, то транспортная задача является открытой.
Транспортная задача называется закрытой, если выполняется условие баланса : суммарный объем производства равен суммарному объему потребления:
. (3.1)
Следнет обратить внимание на то, что математическая модель задает закрытую транспортную задачу.
Открытая ТЗ имеет место в двух случаях.
Первый случай. Суммарный объем производства меньше суммарного объема потребления:
. (3.2)
Известно, что для существования допустимого решения транспортной задачи необходимо и достаточно, чтобы задача была закрытой. Поэтому транспортную задачу открытого типа предварительно необходимо свести к закрытой, для чего вводится фиктивный пункт производства с номером m+1 с объемом производства:
, (3.3)
при этом полагают .
Второй случай. Суммарный объем производства больше суммарного объема потребления:
. (3.4)
Для сведения ТЗ к закрытому типу вводят фиктивный пункт потребления с номером n+1 с объемом потребления:
, (3.5)
при этом полагают .
82. Математическая постановка основной ТЗ по критерию стоимости
Поставщики A1, A2, A3, A4, имеют 20, 20, 20, 20 единиц однотипной продукции, которую необходимо доставить потребителям B1, B2, B3, B4, B5 в количестве 19, 19, 19, 19, 4 единиц. Стоимость доставки единицы продукции от поставщика A1 к данным потребителям равна 15, 1, 22, 19, 1 денежных единиц; от поставщика A2 – 21, 18, 11, 4, 3 денежных единиц.; от поставщика A3 26, 29, 23, 26, 24 денежных единиц. и от поставщика A4 21, 10, 3, 19, 27 денежных единиц. Необходимо найти оптимальное решение доставки продукции от поставщиков к потребителям, минимизирующие стоимость перевозки.
Если сложить запасы поставщиков и запросы потребителей обнаружим, что запасы поставщиков равны 20 + 20 + 20 + 20 = 80 единиц продукции. Потребности потребителей равны 19 + 19 + 19 + 19 + 4 = 80 единиц продукции. Следовательно, нет необходимости вводить фиктивного поставщика.
Таблица 1.1.1
|
B1 |
B2 |
B3 |
B4 |
B5 |
Запасы |
|
|
A1 |
15 |
1 |
22 |
19 |
1 |
20 |
|
A2 |
21 |
18 |
11 |
4 |
3 |
20 |
|
A3 |
26 |
29 |
23 |
26 |
24 |
20 |
|
A4 |
21 |
10 |
3 |
19 |
27 |
20 |
|
Потребности |
19 |
19 |
19 |
19 |
4 |
В т пунктах отправления , которые в дальнейшем будем называть поставщиками, сосредоточено определенное количество единиц некоторого однородного продукта, которое обозначим (i = 1, 2, ..., т). Данный продукт потребляется в п пунктах , которые будем называть потребителями; объем потребления обозначим (j = 1, 2, ..., п). Известны расходы на перевозку единицы продукта из пункта Ai в пункт Bj, которые равны и приведены в матрице транспортных расходов .
Требуется составить такой план прикрепления потребителей к поставщикам, т.е. план перевозок, при котором весь продукт вывозится из пунктов в пункты в соответствии с потребностью и общая величина транспортных издержек будет минимальной.
Обозначим количество продукта, перевозимого из пункта в пункт , через , тогда условие задачи можно записать в виде таблицы (табл.1), которая называется матрицей планирования. Совокупность всех переменных для краткости обозначим . Тогда целевая функция задачи будет иметь вид
а ограничения выглядят следующим образом:
Необходимым и достаточным условием разрешимости задачи является условие баланса:
83. Задача о назначениях.
Задача о назначениях – это распределительная задача, в которой для выполнения каждой работы требуется один и только один ресурс (один человек, одна автомашина и т.д.), а каждый ресурс может быть использован на одной и только одной работе. То есть ресурсы не делимы между работами, а работы не делимы между ресурсами. Таким образом, задача о назначениях является частным случаем транспортной задачи. Задача о назначениях имеет место при назначении людей на должности или работы, автомашин на маршруты, водителей на машины, при распределении групп по аудиториям, научных тем по научно-исследовательским лабораториям и т.п.
Исходные параметры модели задачи о назначениях
Искомые параметры
Задача о назначениях является типичным примером оптимального
принятия управленческих решений. Эта задача позволяет
распределить объекты из некоторого множества по группе субъектов
из другого множества и это распределение должно соответствовать
оптимальности одного или нескольких итоговых показателей.
Пусть имеется n работ и n механизмов и задана производительность i-го механизма на j-ой работе. Требуется установить взаимно однозначное соответствие между механизмами и работами так, чтобы общая производительность была максимальной.
Для построения математической модели введем переменные , принимающие значения 0 или 1 в зависимости от того, назначен или нет i-ый механизм на j-ую работу. Получаем следующую задачу:
=1 (j=1,2,…,n)
=1 (i=1,2,…,n)
84. Нахождение опорного плана.
Существует несколько простых схем построения первоначального опорного плана транспортной задачи.
1) Метод северо-западного угла.
Не учитывая стоимости перевозки единицы груза начинается удовлетворение потребностей первого потребителя за счет запаса первого поставщика. Далее переходим из одной клетки в другую по правилу «вниз и вправо», нагружая каждую клетку по максимуму.
2) Метод минимальной стоимости.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел или . Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
3) Метод двойного предпочтения.
В каждом столбце отмечают знаком * клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку **. В них находится минимальная стоимость как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз исключая из рассмотрения соответствующие столбцы и строки. Затем распределяют перевозки по клеткам, отмеченным знаком V. В оставшейся части таблицы перевозки распределяют по наименьшей стоимости. Опорный план, полученный таким образом, наиболее близок к оптимальному.
85. Метод потенциалов.
Введем специальные показатели для каждой строки матрицы перевозок (каждого поставщика), где и показатели для каждого столбца (каждого потребителя), где . Эти показатели называются потенциалами поставщиков и потребителей, их удобно интерпретировать как цены продукта в соответствующих пунктах поставщиков и потребителей.
1) Построение системы потенциалов.
Для построения системы потенциалов используем условие (5)
2) Проверка выполнения условия оптимальности для незанятых клеток.
Просматриваем строки и для каждой незанятой клетки проверяем выполнение условия
(6) Если для всех незанятых клеток условие (6) выполняется, то план является оптимальным. Если для некоторых клеток , то план является неоптимальным.
Транспортные задачи, в базисном плане перевозок которых имеют место занятые клетки с нулевой поставкой (или в первоначальном распределении, или в процессе итераций), называются вырожденными. В случае вырожденной транспортной задачи существует опасность зацикливания, т.е. бесконечного повторения итераций (бесконечного перебора одних и тех же базисных комбинаций занятых клеток). Как правило, в практических задачах транспортного типа зацикливание не встречается. При отсутствии вырождения метод потенциалов конечен и приводит к оптимальному плану перевозок за конечное число шагов.
86. Определение потенциалов пунктов
Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций.
Метод потенциалов является модификацией симплекс-метода, в котором базисная матрица представлена в виде дерева.
Двойственные переменные симплекс-метода для транспортной задачи называются потенциалами.
Потенциалы вычисляются по формуле , что эквивалентно
Для дуги потенциалы дуг связаны формулой .
Таким образом, потенциал потребителя равна потенциалу производителя + стоимость перевозки. С экономической точки зрения это можно трактовать как стоимость продукта в точке потребления.
Проверка оптимальности плана легко трактуется с экономической точки зрения - если стоимость продукта в точке потребления больше стоимости в точке производства + цена перевоза, по этой дуге следует везти. Величина называется невязкой дуги.
Добавление дуги приводит к возникновению цикла в дереве. Увеличение провоза по вводимой дуге приводит к пересчету потоков в цикле, провоз по одной из дуг при этом уменьшится до нуля. Дугу с нулевым потоком удаляем из базиса, при этом базисный граф остается деревом (цикл разрывается).
Остается только пересчитать потенциалы - добавить (или вычесть - зависит от направления дуги) ко всем вершинам "повисшей ветки" величину невязки
Процесс завершается, когда для всех дуг условие оптимальности выполняется для всех дуг.
87. Открытая модель ТЗ.
Открытая и закрытая транспортные задачи. Выделяют два типа ТЗ: открытая ТЗ и закрытая ТЗ. Транспортная задача называется закрытой, если выполняется условие баланса: суммарный объем производства равен суммарному объему потребления:
. (3.1)
Открытая ТЗ имеет место в двух случаях. Первый случай. Суммарный объем производства меньше суммарного объема потребления:
. (3.2)
Известно, что для существования допустимого решения транспортной задачи необходимо и достаточно, чтобы задача была закрытой. Поэтому транспортную задачу открытого типа предварительно необходимо свести к закрытой, для чего вводится фиктивный пункт производства с номером m+1 с объемом производства:
, (3.3)
при этом полагают .
Второй случай. Суммарный объем производства больше суммарного объема потребления:
. (3.4)
Для сведения ТЗ к закрытому типу вводят фиктивный пункт потребления с номером n+1 с объемом потребления:
, (3.5)
при этом полагают .
88. Венгерский метод
Алгоритм венгерского метода.
Алгоритм ищет значения, которые надо вычесть из всех элементов каждой строки и каждого столбца (разные для разных строк и столбцов), такие, что все элементы матрицы останутся неотрицательными, но появится нулевое решение. Алгоритм основан на двух идеях:
Найдем начальное решение венгерским методом. Если начальное решение окажется оптимальным, то задача решена. Если начальное решение окажется не оптимальным, используя метод потенциалов, будем последовательно получать решение за решением, до тех пор, пока не получим оптимальное решение.
89. Транспортная задача по критерию времени
В такой транспортной задаче решающую роль играет не стоимость перевозок, а время, которое затрачивается на доставку груза. Оптимальным планом считается план, который минимизирует время перевозок. Задача решается в следующем порядке. Находится начальное опорное решение Х1. Определяется значение целевой функции Т(Х1)=max{tij}=tl1k1. Все свободные клетки, которым соответствует значение tij>T(X1), исключается из рассмотрения (перечеркиваются). Занимать эти клетки нецелесообразно, так как увеличивается значение целевой функции. Чтобы уменьшить ее значение, необходимо освободить клетку (l1, k1), в которой tij достигает максимума. Для этого строят так называемые разгрузочные циклы, которые могут включать в свой состав несколько свободных клеток. В каждом разгрузочном цикле, начиная с разгружаемой клетки (l1, k1), расставляются поочередно знаки «-» и «+» и осуществляется сдвиг на величину min {xij}. Если удается эту клетку разгрузить, то она исключается из рассмотрения (зачеркивается). Получается новое опорное решение Х2 , на котором значение целевой функции меньше, чем на Х1. Далее снова пытаются разгрузить клетку, соответствующую Т(Х2)=max{tij}=tl2k2. Процесс продолжается до тех пор, пока возможность разгрузить соответствующую клетку не исчезнет.
|
B1 |
B2 |
B3 |
B4 |
B5 |
Запас |
|
|
A1 |
15 |
19 1 |
22 |
19 |
1 1 |
20 |
|
A2 |
21 |
18 |
11 |
19 4 |
1 3 |
20 |
|
A3 |
19 26 |
29 |
1 23 |
26 |
24 |
20 |
|
A4 |
21 |
10 |
18 3 |
19 |
2 27 |
20 |
|
Потребность |
19 |
19 |
19 |
19 |
4 |
Найдем Т(х1) = max{1, 1, 3, 3, 4, 23, 26, 27} = 27. Следовательно, перечеркиваем клетки, значения которых превышают 27:
Таблица 1.8.2
|
B1 |
B2 |
B3 |
B4 |
B5 |
Запас |
|
|
A1 |
15 |
19 1 |
22 |
19 |
1 1 |
20 |
|
A2 |
21 |
18 |
11 |
19-2 4 |
1+2 3 |
20 |
|
A3 |
19 26 |
29 |
1 23 |
26 |
24 |
20 |
|
A4 |
21 |
10 |
18 3 |
+2 19 |
2-2 27 |
20 |
|
Потребность |
19 |
19 |
19 |
19 |
4 |
Необходимо разгрузить ячейку А4В5:
Таблица 1.8.3
|
B1 |
B2 |
B3 |
B4 |
B5 |
Запас |
|
|
A1 |
15 |
19 1 |
22 |
19 |
1 1 |
20 |
|
A2 |
21 |
18 |
11 |
17 4 |
3 3 |
20 |
|
A3 |
19 26 |
29 |
1 23 |
26 |
24 |
20 |
|
A4 |
21 |
10 |
18 3 |
2 19 |
27 |
20 |
|
Потребность |
19 |
19 |
19 |
19 |
4 |
Новое Т(х2) = max{1, 1, 3, 3, 4, 19, 23, 26} = 26. Необходимо вычеркнуть все элементы, которые больше 26:
Таблица 1.8.4
|
B1 |
B2 |
B3 |
B4 |
B5 |
Запас |
|
|
A1 |
15 |
19 1 |
22 |
19 |
1 1 |
20 |
|
A2 |
21 |
18 |
11 |
17 4 |
3 3 |
20 |
|
A3 |
19 26 |
29 |
1 23 |
26 |
24 |
20 |
|
A4 |
21 |
10 |
18 3 |
2 19 |
27 |
20 |
|
Потребность |
19 |
19 |
19 |
19 |
4 |
Дальше разгрузить ячейку А3В1 невозможно, а это значит, что оптимизация завершена. Максимальное время перевозки будет равно Т(х2) = 26 ед.
90. Целочисленное программирование
Целочисленное программирование — раздел математического программирования, в котором на все или некоторые переменные дополнительно накладывается ограничение целочисленности. Простейший метод решения задачи целочисленного программирования — сведение её к задаче линейного программирования с проверкой результата на целочисленность. раздел математического программирования, в котором исследуется задача оптимизации (максимизации пли минимизации) функции нескольких переменных, связанных рядом уравнений и (или) неравенств и удовлетворяющих условию целочисленности (используются также термины дискретное программирование, дискретная оптимизация). Источником задач Ц. п. является техническая, экономическая и военная проблематика.
Условие целочисленности переменных формально отражает: а) физич. неделимость объектов (напр., при размещении предприятий или выборе варианта боевых действий); б) конечность множества допустимых вариантов, на к-ром проводится оптимизация (напр., множества перестановок в задачах упорядочения); в) наличие логич. условий, выполнение или невыполнение к-рых влечет изменение вида целевой функции и ограничений задачи.
Наиболее изученной и распространенной задачей Ц. п. является т. н. задача целочисленного линейного программирования: максимизировать.
Форма записи:
при условиях
j = 1, 2, . .., п, xj - целые для j = 1, ..., р, где а ij, bi, cj- заданные целые числа, xj- переменные.
91. Примеры задач целочисленного программирования
Примеры задач целочисленного линейного программирования. При решении многих задач нецелочисленное решение не имеет смысла. Раздел математического программирования, в котором на экстремальные задачи налагается условие дискретности переменных при конечной области допустимых решений, называется дискретным программированием. При наличии условия целочисленности имеется в виду подраздел дискретного программирования - целочисленное программирование. В экономике много задач с физической неделимостью объектов, предметов и факторов расчета. К примеру, нельзя построить 1,7 здания, 6,1 завода, 1,07 автомобиля, произвести 1,7 замера, осуществить 3,4 путешествия, купить 4,5 туристических путевок.
Задача о рюкзаке
Контейнер оборудован m отсеками вместимостью для перевозки n видов продукции . Виды продукции характеризуются свойством неделимости, т.е. их можно брать в количестве 0, 1, 2, ... единиц. Пусть - расход i-го отсека для перевозки единицы j-ой продукции. Обозначим через полезность единицы j-ой продукции. Требуется найти план перевозки, при котором максимизируется общая полезность рейса.
Задача о назначении
Пусть требуется выполнить n различных работ и имеется n механизмов (машин) для их выполнения, причем каждый механизм может использоваться при любом типе работ. Производительность каждого механизма на различных работах может быть различной. Пусть каждый механизм может выполнять только одну какую-либо работу. Задача заключается в таком распределении механизмов по работам, при котором общая производительность будет максимальной.
Задача коммивояжера
Коммивояжер должен посетить один, и только один, раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен минимизировать суммарную длину пройденного пути. Добавляется условие прохождение маршрута через все города, т.е. так называемое условие цикличности. Иначе, маршрут должен представлять собой замкнутую ломаную, без пересечений в городах-точках.
92. Методы решения задач целочисленного программирования
Методы решения задач Ц. п. (релаксация, отсечения, динамическое программирование, метод ветви и границы)
Графический метод
При наличии в задаче линейного программирования двух переменных, задача может быть решена графическим методом.
В системе координат X10X2 находят область допустимых решений, строят вектор С и линию уровня. перемещая линию уровня по направлению С для задач на максимум, определяют наиболее удаленную от начала координат точку и ее координаты.
В случае, когда координаты этой точки нецелочисленные, в области допустимых решений строят целочисленную решетку и находят на ней такие целые числа x1 и x2, которые удовлетворяют системе ограничений и при которых значение целевой функции наиболее близко к экстремальному нецелочисленному решению. Координаты такой вершины являются целочисленным решением.
Аналогично решается задача на минимум. Целочисленному минимуму целевой функции будет соответствовать координаты вершины целочисленной решетки, лежащей в области допустимых решений, наиболее близкой к началу координат в направлении вектора С.
L = 11x1 + 12x2 →max
12x1 + 11x2 ≤ 132;
10x1 + 15x2 ≤ 150;
x1 ≥ 0, x2 ≥ 0,
x1, x2 Z.
Метод ветвей и границ
Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи.
Если среди компонент плана имеются дробные числа, то необходимо осуществить переход к новым планам, пока не будет найдено решение задачи.
Метод ветвей и границ основан на предположении, что новый оптимальный нецелочисленный план дает значение функции, большее, чем всякий последующий план перехода
Пусть переменная xi в плане дробное число. Тогда в оптимальном план ее значение будет , по крайней мере:
Определяя эти числа симплексным методом решения двух задач линейного программирования:
1) F=∑cjxj → max
∑aijxj ≤ bi
xi ≤Ki*
xj≥0, xj – целые, j=1..n
2) F=∑cjxj → max
∑aijxj ≤ bi
xi ≥Ki*+1
xj≥0, xj – целые, j=1..n
Возможны четыре случая при решении этой пары задач:
1) Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции и дают решение исходной задачи.
2) Одна из задач неразрешима, а другая имеет нецелочисленный оптимальный план. Тогда рассматривается вторая задача и в ее оптимальном плане выбирается одна из компонент, значение которой равно дробному числу и строятся две новые задача, аналогично предыдущим.
3) Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значение целевой функции от планов и сравниваем их между собой. Если на целочисленном оптимальном план значение целевой функции больше или равно ее значению в плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и дает искомое решение.
4)Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда рассматриваем ту из задач, для которой значение целевой функции является наибольшим. Строятся новые две задачи.
Алгоритм метода ветвей и границ
L = 11x1 + 12x2 →max
12x1 + 11x2 ≤ 132;
10x1 + 15x2 ≤ 150;
x1 ≥ 0, x2 ≥ 0,
x1, x2 Z
L = 134; x1 = 4; x2 = 6.
Начинаем вводить ограничения:
|
x2 12 x1 + 11*6 = 132; x1 = 5; x2 = 6; L = 132; Решений нет |
x2 10 x1 +15*7 = 150 x1=4; x2 = 7; L = 133 >132 , значит продолжаем ветвление здесь. |
|
x1 10*4 +15x2 = 150; x1 = 4; x2 = 7 ; L=132; Продолжаем ветвление здесь. |
x1 15х2=100 х1=5; х2=6 ; L=135; Решений нет |
|
х2 Решений нет. |
x2 10х1 + 15*8 = 150 х1 = 3; х2 = 8; L=129 Получено целочисленное решение, прекращаем ветвление.. |
Итак, оптимальное целочисленное решение равно 129 при x1 = 3; x2 = 8.
93. Методы отсекающих плоскостей
Методы отсечений относятся к численным методам решения дискретных задач оптимизации (методам дискретного программирования). Они предназначены для решения целочисленных задач линейного программирования (ЛП).
Идея методов отсечения состоит в следующем. Первоначально решается обычная ("непрерывная") задача ЛП, полученная из исходной задачи отбрасыванием требования целочисленности. Если полученное решение является целочисленным, то оно будет также решением исходной задачи. Если нет, то к ограничениям исходной задачи добавляется новое линейное по формуле:
.
обладающее двумя свойствами:
Такое ограничение называется правильным отсечением. Затем решается расширенная непрерывная задача ЛП, т.е. непрерывная задача с добавленным ограничением. Если полученное решение не является целочисленным, добавляется новое правильное отсечение и т.д. Процесс повторяется до тех пор, пока решение очередной расширенной непрерывной задачи ЛП не окажется целочисленным. Таким образом, решение целочисленной задачи ЛП сводится к решению некоторой последовательности обычных задач ЛП. Геометрически добавление каждого такого линейного ограничения означает проведение гиперплоскости, отсекающей от многогранника допустимых решений очередной непрерывной задачи ЛП оптимальную точку с нецелочисленными координатами, но не затрагивающей ни одной из целочисленных точек этого многогранника. Поэтому методы, опирающиеся на эту идею, получили название методов отсечений.
Решение: За основу берем уже решенный прямой симплекс-метод.
Таблица 2.9.1
|
Базисные переменные |
Свободные члены |
Свободные переменные |
|||
|
|
- |
|
- |
||
|
-
|
- |
||||
|
L |
- |
- |
- |
- |
- |
Так как решение не является целочисленным, вводим дополнительное ограничение по формуле: .
- - + - + =
- + - + + =
Решаем задачу ЛП с дополнительным условием. Составляем симплекс-таблицу.
Таблица 2.9.2
|
Базисные переменные |
Свободные члены |
Свободные переменные |
|||
|
|
- |
-
|
1 |
-
|
|
|
|
|
-
|
- |
- - |
- |
|
-
|
- 1 |
- |
- - |
- |
|
|
L |
|
-
|
- - |
- - 3 |
- - |
Так как решение не является целочисленным, вводим дополнительное ограничение по формуле: .
- + - =
+ + =
|
Базисные переменные |
Свободные члены |
Свободные переменные |
|||
|
0 |
0 |
0
|
0 |
0
|
|
|
|
- |
0 0 |
- |
-
|
1 |
|
|
1 0 |
-
|
- - |
- -11 |
|
|
|
0
|
- 1 |
-
- 10 |
-15 |
|
|
L |
-132 4 |
0 0 |
-
|
-3 -8 |
- -12 |
Таблица 2.9.4
|
Базисные переменные |
Свободные члены |
Свободные переменные |
|||
|
|
0 |
0 |
|||
|
|
0 |
0 |
|||
|
|
1 |
0 |
- |
- |
|
|
|
0 |
1 |
|
- |
|
|
L |
-128
|
0
|
0 |
-11
|
-
|
= 4, = 7, L = 128
Полученное решение является целочисленным. Расчет закончен.
94. Метод ветвей и границ
Суть метода ветвей и границ состоит в последовательном переборе вариантов, рассмотрении лишь тех из них, которые по определенным признакам оказываются перспективными, и отбрасывании бесперспективных вариантов. При использовании метода ветвей и границ область допустимых решений (ОДР) исходной задачи определенным способом разбивается на непересекающиеся подмножества, и решаются подзадачи, т.е. задачи на этих подмножествах с той же ЦФ и без учета условия целочисленности (как задачи ЛП). Если в результате получено оптимальное нецелочисленное решение, ОДР подзадачи снова разбивается на части и этот процесс продолжается до тех пор, пока не будет найдено оптимальное целочисленное решение исходной задачи. Если в задаче на максимум при решении подзадач получаются оптимальные целочисленные решения, то запоминаются те из них, которым соответствуют возрастающие значения ЦФ. Если полученное «непрерывное» решение подзадачи оказывается не лучше сохраненного целочисленного решения, то такая подзадача исключается из списка задач. Название этого метода объясняется тем, что в процессе решения задача последовательно «ветвится», разбиваясь на более простые подзадачи.
L = 11x1 + 12x2 →max
12x1 + 11x2 ≤ 132;
10x1 + 15x2 ≤ 150;
x1 ≥ 0, x2 ≥ 0,
x1, x2 Z
L = 134; x1 = 4; x2 = 6.
Начинаем вводить ограничения:
|
x2 12 x1 + 11*6 = 132; x1 = 5; x2 = 6; L = 132; Решений нет |
x2 10 x1 +15*7 = 150 x1=4; x2 = 7; L = 133 >132 , значит продолжаем ветвление здесь. |
|
x1 10*4 +15x2 = 150; x1 = 4; x2 = 7 ; L=132; Продолжаем ветвление здесь. |
x1 15х2=100 х1=5; х2=6 ; L=135; Решений нет |
|
х2 Решений нет. |
x2 10х1 + 15*8 = 150 х1 = 3; х2 = 8; L=129 Получено целочисленное решение, прекращаем ветвление.. |
Итак, оптимальное целочисленное решение равно 129 при x1 = 3; x2 = 8.
95. Алгоритм метода ветвей и границ
Алгоритм решения:
1)
2)
Решение заканчивается если ветви являются отмеченными. Если все отмечены, выбираем ту, где получено целочисленное решение и наибольшее значение функции.
96. Задача коммивояжёра
Постановка задачи. Коммивояжер должен объехать N городов. Известны затраты (стоимостные, временные, расстояния) на переезд между i – м и j – м городом, которые заданы в виде матрицы . Коммивояжер, выехав из исходного города, должен объехать все города, посетив каждый один раз, и вернуться в исходный. Требуется определить в каком порядке следует объезжать города, чтобы суммарные затраты были минимальными.
Если затраты на переезд между каждой парой городов не зависят от направления движения, то задача называется симметричной, в противном случае – несимметричной.
К задаче коммивояжера сводится ряд практических задач. Она решается во многих областях, связанных с замкнутыми и при этом жестко связанными по времени системами. Например, конвейерное производство (в этом случае величины означают затраты времени, или стоимостные затраты на переналадку конвейера при переходе от выполнения операции i к операции j), многооперационные обрабатывающие комплексы (определяется оптимальный порядок обработки различных изделий на одном и том же оборудовании), судовые и железнодорожные погрузочные системы, перевозки грузов по замкнутому маршруту, расчет авиационных линий.
Модель. В качестве переменных выбираются элементы матрицы переездов:
.
Пусть .
- переезд из i-го города в j-ый включается в маршрут;
- в противном случае.
Ограничения группы (а) задают условие: в каждый город коммивояжер въезжает только один раз. Ограничения группы (b) задают условие: из каждого города коммивояжер выезжает только один раз.
Математическая модель задачи
N - число городов.
Ci j , i, j=1..N - матрица затрат, где Ci j - затраты на переход из i-го города в j-й.
Xi j - матрица переходов с компонентами:
Xi j = 1, если коммивояжер совершает переход из i-го города в j-й,
Xi j = 0, если не совершает перехода,
где i, j = 1..N и i¹j.
Критерий:
(1)
Ограничения:
, i = 1..N (2)
, j = 1..N (3)
Ui - Uj + N × Xi j £ N-1, i, j = 1..N, i ¹ j. (4)
Доказательство, что модель (1-4) описывает задачу о коммивояжере:
Условие (2) означает, что коммивояжер из каждого города выезжает только один раз; условие (3) - въезжает в каждый город только один раз; условие (4) - обеспечивает замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутренних петель.
Рассмотрим условие (4). Применим метод доказательства от противного, то есть предположим, что условие (4) выполняется для некоторого подцикла T из R городов, где R<N. Сложив все неравенства (4) вдоль этого подцикла получим
.
Так как
,
то N × R £ (N -1), где R<N, R ¹ 0.
Следовательно, не существует замкнутого подцикла с числом городов меньшим, чем N.
Покажем, что существует Ui, которое для замкнутого цикла, начинающегося в некотором начальном пункте, удовлетворяют условию (4). При всех Xi j (j-й город не посещается после i-го) в (4) имеем Ui - Uj £ N - 1, что допустимо в силу произвольных Ui и Uj.
Пусть на некотором R-ом шаге i-й город посещается перед j-м, то есть Xi j = 1. В силу произвольности значений Ui и Uj положим Ui = R, а Uj = R + 1, тогда из (4) имеем:
Ui - Uj + N × Xi j £ R - (R - 1) + N = N - 1
Итак, существуют такие конечные значения для Ui и Uj, что для маршрута, содержащего N городов, условие (4) удовлетворяется как неравенство или строгое равенство. А следовательно, модель (1-4) описывает задачу о коммивояжере.
97. Динамическое программирование
Динамическое программирование, раздел математики, посвящённый теории и методам решения многошаговых задач оптимального управления.
В Д. п. для управляемых процессов среди всех возможных управлений ищется то, которое доставляет наименьшее или наибольшее значение целевой функции — некоторой числовой характеристике процесса. Под многошаговостью понимают либо многоступенчатую структуру процесса, либо разбиение управления на ряд последовательных этапов (шагов), соответствующих, как правило, различным моментам времени. Т. о., в названии "Д. п." под "программированием" понимают "принятие решений", "планирование", а слово "динамическое" указывает на существенную роль времени и порядка выполнения операции в рассматриваемых процессах и методах. Методы Д. п. являются составной частью методов, используемых в исследовании операций, и применяются как в задачах оптимального планирования, так и при решении различных технических проблем (например, в задачах определения оптимальных размеров ступеней многоступенчатых ракет, в задачах оптимального проектирования прокладки дорог).
Методы Д. п. находят применение не только в дискретных, но и в непрерывных управляемых процессах, например в таких процессах, когда решения надо принимать в каждый момент некоторого интервала времени. Д. п. дало новый подход к задачам вариационного исчисления.
Хотя метод Д. п. существенно упрощает исходные задачи, однако непосредственное его применение, как правило, сопряжено с громоздкими вычислениями. Для преодоления этих трудностей разрабатываются приближённые методы Д. п.
Динамическое программирование обычно придерживается двух подходов к решению задач:
98. Области применения моделей динамического программирования см. вопрос 9
99. Задача о дилижансах см. вопрос 10.
100. Задача управления запасами
Постановка задачи
Пусть месячная потребность предприятия в каком-либо материале (песок, щебень, цемент, ...) составляет Q единиц (м^ т, ...). Расход его во времени происходит равномерно. Необходимо определить, какова должна быть величина поставляемой партии материалов, чтобы суммарные затраты на создание и хранение запаса были минимальны.
Можно выделить четыре основные причины, приводящие к необходимости образования запасов:
• необходимость гарантирования бесперебойности питания производственного процесса с целью обеспечения его непрерывности;
• периодичность производства отдельных видов ресурсов у поставщиков:
• особенности доставки ресурсов от поставщика до потребителя (несо ответствие грузоподъемности транспортных средств и размеров по требления);
• несовпадение ритма производства и поставок производственных ре сурсов с ритмом их потребления.
Любая модель управления запасами, в конечном счете, должна дать ответ на
два вопроса:
1. Какое количество продукции заказывать?
2. Когда заказывать?
Ответ на первый вопрос выражается через размер заказа, определяющего
оптимальное количество ресурсов, которое необходимо поставлять каждый раз,
когда происходит размещение заказа. В зависимости от рассматриваемой
ситуации размер заказа может меняться во времени. Ответ на второй вопрос
зависит от типа системы управления запасами. Если система предусматривает
периодический контроль состояния запаса через равные промежутки времени
(например, еженедельно или ежемесячно), момент поступления нового заказа
обычно совпадает с началом каждого интервала времени. Если же в системе
предусмотрен непрерывный контроль состояние запаса, точка заказа обычно
определяется уровнем запаса, при котором необходимо размещать новый заказ.
Таким образом, решение обобщённой задачи управления запасами
определяется следующим образом;
1. В случае периодического контроля состояния запаса следует обеспечивать
поставку нового количества ресурсов в объеме размера заказа через равные
интервалы времени.
2. В случае непрерывного контроля состояния запаса необходимо размещать
новый заказ в размере объема запаса, когда его уровень достигает точки
заказа.
Размер и точка заказа обычно определяются из условий минимизации
суммарных затрат системы управления запасами, которые можно выразить в виде
функции этих двух переменных. Суммарные затраты системы управления запасами
выражаются в виде функции их основных компонент
Рассмотрим достаточно типичную задачу, возникающую в процессе планирования деятельности системы снабжения, — так называемую динамическую задачу управления запасами.
Пусть имеется некоторая система снабжения (склад, оптовая база и т. п.), планирующая свою работу на п периодов. Ее деятельность сводится к обеспечению спроса конечных потребителей на некоторый продукт, для чего она осуществляет заказы производителю данного продукта. Спрос клиентов (конечных потребителей) в данной модели рассматривается как некоторая интегрированная величина, принимающая заданные значения для каждого из периодов, и он должен всегда удовлетворяться (т. е. не допускаются задолженности и отказы). Также предполагается, что заказ, посылаемый производителю, удовлетворяется им полностью, и временем между заказом и его выполнением можно пренебречь (т. е. рассматривается система с мгновенным выполнением заказа). Введем обозначения:
yk — остаток запаса после (k-1)-го периода;
dk — заранее известный суммарный спрос в k-м периоде;
хk — заказ (поставка от производителя) в k-м периоде;
сk (хk) —затраты на выполнение заказа объема xk в k-м периоде;
sk (ξk) — затраты на хранение запаса объема ξk в k-м периоде.
После получения поставки и удовлетворения спроса объем товара, подлежащего хранению в период k, составит ξk = yk + хk - dk . Учитывая смысл параметра yk , можно записать соотношение:
Расходы на получение и хранение товара в период k описываются функцией
Планом задачи можно считать вектор х = (х1, х2, ..., хn), компонентами которого являются последовательные заказы в течение рассматриваемого промежутка времени. Соотношение между запасами (5.24) в сочетании с некоторым начальным условием связывает состояния системы с выбранным планом и позволяет выразить суммарные расходы за все п периодов функционирования управляемой системы снабжения в форме аддитивной целевой функции:
Естественной в рамках сформулированной модели представляется задача нахождения последовательности оптимальных управлений (заказов) x*k и связанных с ними оптимальных состояний (запасов) ξ*k , которые обращают в минимум (5.25). В качестве начального условияиспользуем требование о сохранении после завершения управления заданного количества товара yn+1 , а именно
При решении поставленной задачи методом динамического программирования в качестве функции состояния управляемой системы Λk(ξ) логично взять минимальный объем затрат, возникающих за первые k периодов при условии, что в k-й период имеется запас ξ . Тогда можно записать основное рекуррентное соотношение
поскольку
Система рекуррентных соотношений (5.27)-(5.28) позволяет найти последовательность функций состояния Λ1(ξ), Λ2(ξ), …, Λn(ξ) и условных оптимальных управлений 1(ξ), 2(ξ), …, n(ξ). На n-м шаге с помощью начального условия (5.26) можно определить х*n = n (yn+1). Остальные значения оптимальных управлений x*k определяются по формуле:
Особый интерес представляет частный случай задачи (5.24)-(5.25), при котором предполагается, что функции затрат на пополнение запаса сk(хk) являются вогнутыми по хk , а функции затрат на хранение sk(ξk) являются линейными относительно объема хранимого запаса, т. е. sk(ξk) = skξk . Параллельно заметим, что обе предпосылки являются достаточно реалистичными.
Обозначим функцию затрат в течение k-ro периода через
или, что то же самое,
В силу сделанных предположений все функции затрат fk (xk , yk+1) являются вогнутыми (как суммы вогнутой и линейной функций). Данное свойство значительно упрощает процесс решения, так как для поиска минимума вогнутых функций fk (xk , yk+1) достаточно рассмотреть только две крайние точки множества, на котором отыскивается минимум. С учетом введенного обозначения задачу (5.24)-(5.25) можно записать в виде:
при условиях
Рассмотрим процедуру решения (5.32)-(5.33). Так как ищется минимум суммы вогнутых функцийfk(xk , yk+1), то решение будет достигаться на одной из крайних точек множества, определяемого условиями (5.33). Общее число переменных xk и yk в системе (5.33) равно 2п. Однако, учитывая то, что в ней только п уравнений, в оптимальном плане будет не более п ненулевых компонент, причем для каждого периода k значения xk и yk не могут равняться нулю одновременно (в силу необходимости удовлетворения спроса либо за счет заказа, либо за счет запаса). Формально это утверждение можно представить в виде условия дополняющей нежесткости:
где
С точки зрения содержательной интерпретации условия (5.34)-(5.35) означают, что приоптимальном управлении заказ поставщику на новую партию не должен поступать, если в начале периода имеется ненулевой запас, или размер заказа должен равняться величине спроса за целое число периодов. Отсюда следует, что запас на конец последнего периода должен равняться нулю: у*n+1=0. Последнее позволяет решать задачу в прямом направлении, применяя рекуррентное соотношение
где ξ = уk+1= хk + уk - dk .
Учитывая (5.34)-(5.35) и вогнутость fk (xk, ξ), заключаем, что минимум (5.36) достигается в одной из крайних точек xk =0 или xk = ξ + dk поэтому
тогда для предыдущего периода функция состояния может быть выражена как
на oснове чего в общем виде получаем модифицированную форму для рекуррентного соотношения
При дальнейших конкретизирующих предположениях о виде функций fk (xk , уk+1) можно получить еще более компактные формы для рекуррентных соотношений. Однако эти вопросы носят достаточно частный характер, и мы их рассматривать не будем. Отметим лишь, что приведенные в данном пункте преобразования неплохо иллюстрируют общие подходы, применяемые в динамическом программировании, а также те свойства задач, которые открывают возможности, для эффективного и плодотворного использования соответствующих методов.
Особенности математической модели динамического программирования заключаются в следующем: задача оптимизации формулируется как конечный многошаговый процесс управления; целевая функция является аддитивной и равна сумме целевых функций каждого шага
;
выбор управления Xk на каждом шаге зависит только от состояния системы к этому шагу Sk-1 и не влияет на предшествующие шаги (нет обратной связи); состояние системы Sk после каждого шага управления зависит только от предшествующего состояния системы Sk-1 и этого управляющего воздействия Xk (отсутствие последействия) и может быть записано в виде уравнения состояния:
;
на каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние системы Sk зависит от конечного числа переменных; оптимальное управление X* представляет собой вектор, определяемый последовательностью оптимальных пошаговых управлений, число которых и определяет количество шагов задачи.
X*=(X*1, X*2, …, X*k, …, X*n),
Условная оптимизация. Как уже отмечалось выше, на данном этапе отыскиваются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем n-м шаге найти оптимальное управление X*n и значение функции Беллмана Fn(S) не сложно, так как
Fn(S)=max{Wn(S,Xn)},
где максимум ищется по всем возможным значениям Xn.
Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге:
Fk(S)=max{Wk(S,Xk)+Fk+1(S"(S,Xk))}. (1)
Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.
Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый (на первом шаге k=1 состояние системы равно ее начальному состоянию S0), осуществляется второй этап решения задачи. Находится оптимальное управление на первом шаге X1, применение которого приведет систему в состояние S1(S,x1*), зная которое можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге, и так далее до последнего n-го шага.
Очевидно, последний — после него других шагов нет. Этот шаг, единственный из всех, можно планировать так, чтобы он как таковой принес наибольшую выгоду. Спланировав оптимально этот последний шаг, можно к нему пристраивать предпоследний, к предпоследнему — предпредпоследний и т.д.
Поэтому процесс динамического программирования на 1-м этапе разворачивается от конца к началу, то есть раньше всех планируется последний,
N-й шаг. А как его спланировать, если мы не знаем, чем кончился предпоследний? Очевидно, нужно сделать все возможные предположения о том, чем кончился предпоследний, (N—1)-й шаг, и для каждого из них найти такое управление, при котором выигрыш (доход) на последнем шаге был бы максимален. Решив эту задачу, мы найдем условно оптимальное управление (УОУ) на N-м шаге, т.е. управление, которое надо применить, если (N—1)-й шаг закончился определенным образом.
Предположим, что эта процедура выполнена, то есть для каждого исхода (N—1)-го шага мы знаем УОУ на N-м шаге и соответствующий ему условно оптимальный выигрыш (УОВ). Теперь мы можем оптимизировать управление на предпоследнем, (N—1)-м шаге. Сделаем все возможные предположения о том, чем кончился предпредпоследпий, то есть (N—2)-й шаг, и для каждого из этих предположений найдем такое управление на (N—1)-м шаге, чтобы выигрыш за последние два шага (из которых последний уже оптимизирован) был максимален. Далее оптимизируется управление на (N—2)-м шаге, и т.д.
Одним словом, на каждом шаге ищется такое управление, которое обеспечивает оптимальное продолжение процесса относительно достигнутого в данный момент состояния. Этот принцип выбора управления, называется принципом оптимальности. Само управление, обеспечивающее оптимальное продолжение процесса относительно заданного состояния, называется УОУ на данном шаге. Теперь предположим, что УОУ на каждом шаге нам известно: мы знаем, что делать дальше, в каком бы состоянии ни был процесс к началу каждого шага. Тогда мы можем найти уже не "условное", а действительно оптимальное управление на каждом шаге.
Действительно, пусть нам известно начальное состояние процесса. Теперь мы уже знаем, что делать на первом шаге: надо применить УОУ, найденное для первого шага и начального состояния. В результате этого управления после первого шага система перейдет в другое состояние; но для этого состояния мы знаем УОУ и г д. Таким образом, мы найдем оптимальное управление процессом, приводящее к максимально возможному выигрышу.
Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс "проходится" дважды:
1. Первый раз — от конца к началу, в результате чего находятся УОУ| на каждом шаге и оптимальный выигрыш (тоже условный) на всех шагах, начиная с данного и до конца процесса;
2. Второй раз — от начала к концу, в результате чего находятся оптимальные управления на всех шагах процесса.
Можно сказать, что процедура построения оптимального управления методом динамического программирования распадается на две стадии: предварительную и окончательную. На предварительной стадии для каждого шага определяется УОУ, зависящее от состояния системы (достигнутого в результате предыдущих шагов), и условно оптимальный выигрыш на всех оставшихся шагах, начиная с данного, также зависящий от состояния. На окончательной стадии определяется (безусловное) оптимальное управление для каждого шага. Предварительная (условная) оптимизация производится по шагам в обратном порядке: от последнего шага к первому; окончательная (безусловная) оптимизация — также по шагам, но в естественном порядке: от первого шага к последнему. Из двух стадий оптимизации несравненно более важной и трудоемкой является первая. После окончания первой стадии выполнение второй трудности не представляет: остается только "прочесть" рекомендации, уже заготовленные на первой стадии.
Этапы построение алгоритма задач, решаемых методом динамического программирования
Основную часть работы составляют шаги 1-3. Если нас интересует только оптимальное значение параметра, шаг 4 не нужен. Если же шаг 4 необходим, для построения оптимального решения иногда приходится получать и хранить дополнительную информацию в процессе выполнения шага 3.
103. Задача распределения ресурсов
В общем случае задача оптимального распределения ресурсов формулируется следующим образом. Предприятие распоряжается ресурсами различных типов. Среди таких ресурсов могут быть материально-вещественные, энергетические, трудовые, технические, финансовые и другие, не участвовавшие в нашем примере. Ресурсы каждого типа могут быть разделены на классы. Сырье - по видам сырья, трудовые - по профессиям и квалификации работников, технические - по техническим характеристикам, финансовые - по источникам финансирования и т.п. Пусть в результате такой классификации, такого разделения получилось m видов ресурсов.
Пронумеруем все виды ресурсов числами от 1 до m, буквой i будем обозначать номер вида ресурса. Таким образом, i удовлетворяет неравенству 1 £ i £ m. Заметим, что ресурсы разных видов могут измеряться в различных единицах (тоннах, кубометрах, человеко-часах, рублях, штуках и др.). В течение планового периода предприятие обладает некоторыми доступными объемами ресурса каждого вида. Объем ресурса i-го вида, измеренный в единицах соответствующих данному виду ресурса, обозначим посредством bi. Индекс i около буквы b указывает, что доступные объемы ресурсов разных видов могут быть различными.
Из этих ресурсов предприятие способно изготавливать различную продукцию. Обозначим буквой n общее число видов продукции, которые может выпустить предприятие из имеющихся ресурсов. Занумеруем все виды продукции числами от 1 до n. Буквой j будем обозначать номер вида продукции, так что выполняется неравенство 1 £ j £ n. Продукция, как и ресурсы, может измеряться в различных единицах.
Пусть cj - цена, по которой предприятие реализует каждую единицу продукции j-го вида. Индекс j около буквы c указывает, что цена разных видов продукции может быть различной. Производство продукции требует затрат ресурсов. Объем затрат зависит от вида ресурса, вида продукции и количества единиц продукции. Обозначим посредством aij норму затрат ресурса i-го вида на производство продукции j-го вида. Другими словами, aij - это количество ресурса i-го вида, затрачиваемое при производстве единицы продукции j-го вида.
Задача оптимального использования ресурсов, задача производственного планирования, состоит в том, чтобы определить, какую продукцию и в каком объеме следует изготовить предприятию из имеющихся ресурсов с тем, чтобы доход от реализации продукции был наибольшим.
Построим математическую модель задачи. Сначала введем переменные. Посредством xj обозначим искомый объем выпуска продукции j-го вида. Математическую модель можно теперь записать в следующей форме:
Верхняя строка записи говорит о максимизации целевой функции. Сама целевая функция представляет собой обычно сумму произведений цен на объем выпуска для различных видов продукции, то есть доход предприятия от продажи изготовленной продукции. В качестве коэффициентов целевой функции часто используют величину маржи от продажи единицы продукции соответствующего вида. В этом случае целевая функция представляет собой маржинальную прибыль. Фигурная скобка объединяет систему ограничений задачи, неравенства, входящие в систему, соответствуют различным видам ресурсов. Каждое такое неравенство говорит о том, что суммарное количество ресурса, используемое в производстве различных видов продукции, не превосходит общего запаса этого ресурса. В последней строке системы ограничений указано, что количества производимой продукции не могут быть отрицательными. Заметим, что равенство нулю здесь не запрещено, то есть некоторые (или даже все) виды продукции предприятие может и не выпускать, хотя они и доступны для выпуска. Экономическая задача поиска плана производства продукции, дающего наибольший доход, превращается в математическую задачу поиска максимального значения целевой функции от n переменных при условии, что значения этих переменных подчинены системе ограничений, имеющих форму неравенств.
Всякий набор значений переменных (x1, x2, ... , xn ) называется планом задачи. Те планы, которые удовлетворяют системе ограничений, называются допустимыми планами. Оптимальным планом называется тот из допустимых планов, который дает наибольшее значение целевой функции среди всех ее значений на допустимых планах. Само это наибольшее значение целевой функции, то есть значение целевой функции на оптимальном плане, называется оптимумом задачи.
Нелинейное программирование — случай математического программирования, в котором целевой функцией или ограничением является нелинейная функция.
Задача нелинейного программирования ставится как задача нахождения оптимума определенной целевой функции при выполнении условий
где — параметры, — ограничения, — количество параметров, — количество ограничений.
В отличие от задачи линейного программирования, в задаче программирования нелинейного оптимум не обязательно лежит на границе области, определенной ограничениями.
Общая задача нелинейного программирования (ОЗНП) определяется как задача нахождения максимума (или минимума) целевой функции f(x1, х2,..., xn) на множестве D, определяемом системой ограничений
где хотя бы одна из функций f или gi является нелинейной.
По аналогии с линейным программированием ЗНП однозначно определяется парой (D, f) и кратко может быть записана в следующем виде
Также очевидно, что вопрос о типе оптимизации не является принципиальным. Поэтому мы, для определенности, в дальнейшем по умолчанию будем рассматривать задачи максимизации.
Как и в ЗЛП, вектор х* = (x1*,x2*,...,xn*) D называется допустимым планом, а если для любого x D выполняется неравенство f(x*) ≥ f(x), то х* называют оптимальным планом. В этом случае х*является точкой глобального максимума.
С точки зрения экономической интерпретации f(x) может рассматриваться как доход, который получает фирма (предприятие) при плане выпуска х, а gi(х) ≤ 0 как технологические ограничения на возможности выпуска продукции. В данном случае они являются обобщением ресурсных ограничений в ЗЛП (аiх – bi ≤ 0).
Задача (2.2) является весьма общей, т. к. допускает запись логических условий, например:
или запись условий дискретности множеств:
Набор ограничений, определяющих множество D, при необходимости всегда можно свести либо к системе, состоящей из одних неравенств:
либо, добавив фиктивные переменные у, к системе уравнений:
Перечислим свойства ЗНП, которые существенно усложняют процесс их решения по сравнению с задачами линейного программирования:
1. Множество допустимых планов D может иметь очень сложную структуру (например, быть невыпуклым или несвязным).
2. Глобальный максимум (минимум) может достигаться как внутри множества D, так и на его границах (где он, вообще говоря, будет не совпадать ни с одним из локальных экстремумов).
3. Целевая функция f может быть недифференцируемой, что затрудняет применение классических методов математического анализа.
105. Классификация нелинейных задач и методов их решения
В течение последних двух десятилетий из нелинейного программирования выделились самостоятельные разделы:
Задачи выпуклого программирования – это задачи, в которых определяется минимум выпуклой функции (или максимум вогнутой), заданной на выпуклом замкнутом множестве. Эти задачи среди задач нелинейного программирования наиболее изучены.
Среди задач выпуклого программирования более подробно изучены задачи квадратичного программирования. В этих задачах целевая функция – квадратична, а ограничения – линейны.
Для решения задачи нелинейного программирования было предложено много методов, которые можно классифицировать по различным признакам.
По количеству локальных критериев в целевой функции методы нелинейного программирования делятся на:
По длине вектора методы делятся на:
По наличию ограничений методы нелинейного программирования делятся на:
По типу информации, используемой в алгоритме поиска экстремума методы делятся на:
методы прямого поиска, т.е. методы, в которых при поиске экстремума целевой функции используются только ее значения;
Ни один метод нелинейного программирования не является универсальным.
Если целевая функция является линейной, а ограниченным пространством является политоп, то задача является задачей линейного программирования, которая может быть решена с помощью хорошо известных решений линейного программирования. Если целевая функция является вогнутой (задача максимизации) или выпуклой (задача минимизации) и множеством ограничений служит выпуклая, то задачу называют выпуклой, и в большинстве случаев могут быть использованы общие методы выпуклой оптимизации. Если целевая функция является отношением вогнутых и выпуклых функций (при максимизации) и ограничения выпуклые, то задача может быть преобразована в задачу выпуклой оптимизации использованием техник дробного программирования.
Существуют несколько методов для решения невыпуклых задач. Один подход заключается в использовании специальных формулировок задач линейного программирования. Другой метод предусматривает использование методов ветвей и границ, где задача делится на подклассы, чтобы быть решенной с выпуклыми (задача минимизации) или линейными аппроксимациями, которые образуют нижнюю границу общей стоимости в пределах раздела. При следующих разделах в определенный момент будет получено фактическое решение, стоимость которого равна лучшей нижней границе, полученной для любого из приближенных решений. Это решение является оптимальным, хотя, возможно, не единственным. Алгоритм можно прекратить на ранней стадии, с уверенностью, что оптимальное решение находится в рамках допустимого отклонения от найденной лучшей точки; такие точки называются ε-оптимальными.