книги / Математические методы принятия решений
..pdfНарушение условия оптимальности зависит от конкретных значений последнего слагаемого в выражении (2.17): если Дс,- — —(До,, a,j) ^ 0 для всех j = 1,2, ... , п, то оптимальное решение не изменяется; при наличии хотя бы одного неравенства A cj —
—(До,, dj) > 0 возможно изменение оптимального решения. Система неравенств
(cj (сь, ûj)) (Дс,- (До>> ûj)) ^ О,
(2.18)
3 = 1, 2 ,
определяет то множество значений элементов Acj, j = 1,2, .. . , n , в которое входят и элементы вектора Ась, не нарушающие условия оптимума в данной точке.
Пример 1. Рассмотрим задачу ЛП о выпуске продукции пред приятием (см. §2.4). Математическая модель этой задачи имеет
следующий вид: |
|
|
|
z = lOxi + 20x2 —*ш ах |
(2.19) |
||
при условиях |
|
|
|
X] + 3,5x2 |
^ |
350, |
|
2х] + 0,5x2 |
^ |
240, |
|
+а?2 ^ 150,
Х\ + Х 2 ^ ПО,
lO x i+ 20x2 ^ 1400, Xj, Х2 ^ 0.
Оптимальное решение задачи приведено в следующей симп лекс-таблице (табл. 2.29).
Элементы строки z для переменных Xj, j = 1,2, ... ,7 , взятых с противоположным знаком, и есть значения с,- —Zj = Cj —(сь, dj), по которым судят об оптимальности решения. Различие в знаках обусловлено правилами заполнения симплекс-таблиц.
По условию неопределенность Acj содержится только в ко эффициентах исходной целевой функции, поэтому Acj # 0 для j = 1,2, Acj = 0 для j = 3 , ... , 7, Д сь = {0; 0; 0; Д с1; Д с2}.
|
|
|
|
|
|
|
Таблица 2.29 |
|
|
|
|
Оптимальное решение |
|
|
|
||
Базис |
b |
- Х\ |
-Х 2 |
-хз |
—Х4 |
-Х 5 |
-Хб |
-XI |
х 7 |
90 |
0 |
0 |
1/5 |
0 |
3/5 |
0 |
1 |
Х4 |
120 |
0 |
0 |
3/5 |
1 |
- 2 6 /5 |
0 |
0 |
2/6 |
40 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
Х\ |
70 |
1 |
0 |
- 1 / 5 |
0 |
7/5 |
0 |
0 |
х 2 |
80 |
0 |
1 |
1/5 |
0 |
- 2 / 5 |
0 |
0 |
Z |
2300 |
0 |
0 |
2 |
0 |
6 |
0 |
0 |
Рассчитаем значения Д j = A Cj —(Дс&, а; ) для различных j :
A j = 0, |
3 = 1,2,4,6, 7, |
|
Дз = - Дс[ — - Дсг, |
j = 3, |
|
7 |
2 |
з = 5 . |
Д 5 = - j Д с1 + - Дс2, |
||
Таким образом, на выбор оптимальной точки в данном случае оказывают влияние только коэффициенты при j = 3 и j = 5. Точка оптимума не изменится для тех значений Д с1 и Дс2, при которых согласно (2.18) имеем
- 2 + j Д с1 - |
^ Дс2 < О, |
7 |
2 |
—6 —- Д с1+ - Дс2 ^ 0.
Множество D значений Д сь Дс2 представляет собой часть плоскости, заключенную между двумя лучами, выходящими из точ ки (—10, —20) в направлениях векторов vi = {1; 1} и v2 = (1; 3,5}.
Проблему устойчивости точки оптимума в задаче линейного программирования при неопределенности только в коэффициентах целевой функции можно рассмотреть геометрически, на плоскости. Плоскость, вектор нормали которой определен коэффициентами це левой функции, в точке оптимума можно повернуть таким образом, чтобы она коснулась граней выпуклого многогранника, содержащих эту точку. Диапазон изменения углов поворота плоскости и будет
определять допустимый разброс значений коэффициентов целевой функции.
Для простоты изложения материала все уравнения линейных поверхностей запишем в нормальном (нормированном) виде. Таким образом, мы будем использовать направляющие косинусы плоско стей; в трехмерном пространстве это cos a, cos (3, cos у. Чтобы опре делить грани многогранника, содержащие точку оптимума, подста вим координаты точки оптимума в ограничения (2.14) и (2.15). Те ограничения, которые являются равенствами, определяют искомые грани.
Пусть некоторая грань в трехмерном пространстве задана урав нением
ах + by + си + d = 0 ;
нормальное уравнение этой плоскости имеет вид
(cos <х)х + (cos Р)у + (cos y)u —р = О,
где х, у, и —текущие координаты; о, b, с, d —параметры уравнения плоскости; р —параметр, определяющий расстояние до плоскости от начала координат;
cos а = |
=, |
cos р — |
b |
COS Y — |
____________ |
||||
|
\/a 2 + b2 + C 2 ’ |
r |
л/а 2 -f- Ь 2 + C2 ’ |
л/ а 2 + b2 4 - с 2 |
Для плоскости, соответствующей целевой функции с парамет рами C l, С2, Сз, получим
Cl |
COS Р о - |
С2 |
COS Обо - |
r j — J — |
|
У ч + CJ + с | |
|
y Cf -h Cf -h Cf |
COSY0 = V ^ + 3^ + ^ '
Врассматриваемом случае важны не сами значения ci, С2, сз,
аих отношения:
ci |
_ cos ао |
ci _ |
cos oto |
сг _ |
cos Ро |
С2 |
COS Ро ’ |
Сз |
COS Уо ’ |
Сз |
(2.20) |
COS Уо |
Если некоторая г-я грань многогранника имеет направляющие косинусы cos ai, cosp*, cosyj, то всякая плоскость, направляющие косинусы которой будут иметь значения между cos ао и cos щ, cos Ро
и cos Pi, cos YO и cos Yi, не изменит положение оптимальной точ ки. Анализируя таким образом все грани, которым принадлежит оптимальная точка, найдем диапазоны отношений параметров (ко эффициентов) a, b и с, которым должны удовлетворять плоскости, проходящие через оптимальную точку и не изменяющие оптималь ное решение задачи. Отсюда легко получить возможный диапазон неопределенностей Д с, в значениях коэффициентов целевой функ ции, не влияющих на решение задачи.
Пример 2. Рассмотрим задачу, описанную в примере 1. Определим грани многоугольника, которым принадлежит точка
оптимума. Подставим оптимальное решение задачи х\ = 70, хг = = 80 в исходную модель (2.19) и получим, что оптимальной точкой является точка пересечения прямых х\ + 3 ,5x 2 = 350 и х\ + хг = = 150.
Вектор нормали целевой функции имеет координаты {10; 20}, вектор нормали первой прямой— {1;3,5}, вектор нормали второй прямой — {1; 1}. Вектор нормали целевой функции можно повер нуть так, чтобы он совпал либо с вектором нормали первой прямой, либо с вектором нормали второй прямой, т. е. согласно (2.20) имеем
COS pi |
С2 + |
Д с г > |
COS Рг |
COS Ot] |
CI + |
Дс1 |
COS 0(2 ’ |
cos ai = 0,275, cos Pi = 0,962, |
cos щ = cos рг = 0,707. |
||
Окончательно условие (2.20) принимает вид |
|||
3,5 ^ |
с 2 + |
Д с г |
1. |
|
CI + Act |
|
|
Таким образом, если отношение коэффициентов целевой функ ции лежит в пределах от 1 до 3,5, то координаты оптимальной точки не изменятся.
Полученный результат полезно сравнить с приведенным выше аналитическим расчетом.
2. |
Н е о п р е д е л е н н о с т ь т о л ь к о в к о о р д и н а т а х в е к |
|
т о р а |
п р а в о й ч ас т и . При изменении значений правой части ис |
|
ходной системы (2.14), |
(2.15) в процессе решения изменяется толь |
|
ко столбец свободных |
членов 6 и значение целевой функции z. |
|
В точке оптимума столбец свободных членов не содержит отри цательных элементов. Таким образом, неопределенность в коорди натах вектора правой части до тех пор не влияет на оптимальное решение, пока не появятся отрицательные элементы в столбце сво бодных членов.
Представим матрицу полного ранга А из условий (2.16) в ви де двух блоков N и В: А = (N; В), где N состоит из небазисных столбцов А, &В — из базисных. Аналогично, векторы с и а; состо ят из базисных и небазисных координат: с = (сдг; св), х = (хдг; хв). Следовательно, имеем
А х = Ь,
N X N + В х в = Ь,
B - 1N X N + В - гВ х в = В ~ 1Ь,
х в = В - \
так как х ^ = 0. Отсюда следует, что столбец свободных членов b + Ab на любой итерации может быть получен умножением мат рицы В ~ х на вектор b в исходной постановке задачи (2.16). Сам же блок В формируется из тех столбцов исходной матрицы А из усло вий (2.16), номера которых на данной итерации определяют ба зисные переменные. С другой стороны, j - й столбец в матрице А (матрица А после преобразований становится матрицей У) для дан ной итерации имеет вид
yj = B ~ laj ,
где a.j — j - й столбец исходной матрицы А из условий (2.16). Столбцы матрицы В ~ 1— это столбцы тех переменных текущей
матрицы Y , которые были базисными в исходной таблице (как пра вило, это последние т столбцов), так как Y = В ~ 1А, а столбцы А, относящиеся к базису исходной таблицы, образуют единичную мат рицу, т. е. матрица В ~ 1 всегда присутствует в процессе решения. Исходный вектор b и неопределенность его значения Д6 задают ся по условию задачи. Таким образом получают новый столбец свободных членов. Если исходный вектор равен b + Ab, то можно найти новый столбец свободных членов:
В ~ \Ь + АЪ) = В~'Ь + В ~ 1АЬ = х в + В ~ 1АЬ.
Поскольку в столбце свободных членов оптимального решения из симплекс-таблицы не должно быть отрицательных элементов, то условие стабильности примет вид
х в + В -1 ДЬ ^ 0.
Пример 3. Рассмотрим описанную в примере 1 задачу, предпо лагая, что исходный вектор правой части Ъ= {350; 240; 150; —ПО; -1400} имеет неопределенность АЬ = {Д61; Д 62; АЬз; Д 64; Д&5}> т. е. необходимо рассматривать вектор
{350 + Д 61; 240 + Д62; 150 + Д Ь з ; —110 + ДЬ4; -1400 + Д65}.
и определить диапазон значений АЬ\ , ..., Д 65, при которых опти мальное решение не изменится.
Матрица В -1 занимает пять последних столбцов симплекс-таб лицы оптимального решения (см. табл. 2.29):
|
/ |
1/5 |
0 |
3/5 |
0 |
1\ |
|
|
|
3/5 |
1 |
-26/5 |
0 |
0 |
|
|
В -1 |
0 |
0 |
1 1 |
0 |
|
|
|
|
-1 /5 |
0 |
7/5 |
0 |
0 |
|
|
|
1/5 |
0 |
-2 /5 |
0 |
0у |
|
Условия стабильности оптимального решения данной задачи |
|||||||
имеют вид |
|
, |
|
|
|
|
|
|
90 + Abi + —АЬз ^ 0, |
|
|
||||
|
120 + ДЬ2 - |
у |
АЬ3 ^ 0, |
|
|
||
|
|
40 + АЬз ^ 0, |
|
|
|
||
|
70 + ДЬ4 + —АЬз ^ 0, |
|
|
||||
|
80 + ДЬ5 - |
| |
ДЬз ^ 0. |
|
|
||
Отсюда находятся те комбинации значений величин Abu |
i = |
||||||
= 1,2, ... , 5, при которых оптимальное решение не изменится. |
|
||||||
3. |
Н е о п р е д е л е н н о с т ь в э л е м е н т а х м а т р и ц А\ и A 3. |
||||||
Если неопределенность имеет место в отдельных элементах мат |
|||||||
риц А\ |
и Аз, то можно воспользоваться тем, что элементы |
мат |
|||||
рицы У оптимального решения определяются через матрицу В -1
и исходную матрицу А из условия (2.16):
|
yj = |
j = 1,2, |
|
|
Пусть только один элемент |
имеет неопределенность Д о^ . |
|
В |
матрице Y оптимального |
решения получим элемент |
yij = |
= |
+ Aüj). По знаку рассматриваемого элемента уij |
при |
|
нимается соответствующее решение. Этот подход приемлем для небольшого числа элементов матриц, имеющих неопределенность.
Рассмотрим более общий метод учета неопределенностей в эле
ментах матриц А\, Aj. Пусть все элементы матриц А\ |
и A j имеют |
|||
неопределенности |
Д о ^, |
г = 1,2,..., ш, |
j = 1,2, ... , п. |
Перенесем |
неопределенности |
Д а^ |
в правую часть |
уравнений и |
объединим |
их с неопределенностями Д6*. В таком случае надо вычислить
неопределенность г-й линейной комбинации 2 a>ijXj и добавить
з
ее к неопределенности правой части Д6*. Теперь возникает вопрос, каким образом (согласно какой гипотезе) вычислить неопределен ность линейной комбинации и согласно какой гипотезе присоеди нить ее к неопределенности правой части. От выбора этих гипотез зависит конкретный алгоритм вычисления неопределенностей ли нейной комбинации.
Рассмотрим две гипотезы. В первом случае неопределенность Aciij является детерминированной величиной (например, показыва ет изменение цены некоторого ресурса); во втором (в задачах ЛП с другим физическим содержанием) неопределенность Д а^ будет случайной величиной, для шторой известны математическое ожи дание и дисперсия. Тогда в первом случае неопределенность г-й ли нейной комбинации 2 dijXj будет равна 2 AaijXj, а полная неопре-
3 |
3 |
|
деленность г-й координаты вектора правой части есть |
|
|
A-zbi = ^ |
AaijXj + Ab{. |
(2.21) |
з |
|
|
Во втором случае мы будем исходить из того, что все участвующие в расчете неопределенности носят случайный характер и мож
но |
вычислить |
дисперсию линейной комбинации, полагая Да*,-, |
г = |
1,..., гл, j = |
1,2,..., га, независимыми случайными величинами |
с известными дисперсиями D(aÿ), а затем суммировать дисперсию линейной комбинации и неопределенности правой части Д6*, пола гая величину (Abi)2 равной дисперсии bi, т. е. D(6*) = (Abi)2.
Таким образом, дисперсию линейной комбинации определяем по формуле
а полную неопределенность Д^Ь* (погрешность) г-й координаты вектора правой части системы (2.16) —по формуле
|
71 |
|
+ D(Ы) = |
x 2D(a,ij) + (Abi)2. |
(2.22) |
В формулах (2.21) и (2.22) значения X j , j = 1,2, ... ,п , |
берутся |
|
из симплекс-таблицы оптимального решения. Далее анализируем ситуацию так же, как в случае существования неопределенности только в правой части. Очевидно, что исследование можно прово дить подобным образом и для случая Abi = 0, i = 1,2,..., т.
Г л а в а 3
СЕТЕВЫЕ И ПОТОКОВЫЕ ЗАДАЧИ
§3.1. Основные определения и приложения сетевых и потоковых моделей
Многие задачи линейного программирования могут быть сфор мулированы как сетевые. Примером таких задач является транс портная задача (см. ранее рис. 1.2). Однако можно указать и такие сетевые задачи, которые нельзя сформулировать в виде задачи ЛП. Например, таковой является задача коммивояжера.
Вследствие специальной структуры сетевых задач для них получено много эффективных алгоритмов и изящных теорем, обес печивающих решение широкого круга практических задач. В боль шинстве сетевых задач оптимальные решения являются целочис ленными, в отличие от решения общей задачи линейного програм мирования.
Основные определения в сетевых и потоковых задачах
Введем основные определения и понятия. Сеть состоит из мно жества узлов Ni, i = 1, 2, . . . , к (называемых также вершинами, или
точками соединения), и множества дуг A y, i , j = \ , 2 , . . . , k (назы ваемых также звеньями или ребрами), которые связывают узлы Ni и Nj. Если дуга имеет определенную ориентацию (направление), то ее называют ориентированной, или направленной.
Сеть называют связной, если при любом разбиении множества узлов сети на подмножества X и X найдется дуга Ац или ду га Aji, связывающая г-й узел N , принадлежащий подмножеству X , Ni 6 X , и j -й узел Nj, принадлежащий подмножеству X , Nj е X .
Будем рассматривать только связные сети и будем считать, что между любыми двумя узлами N и N j имеется не больше одной ориентированной дуги Aij и одной ориентированной дуги Aji либо
имеется только одна неориентированная дуга А ^ . Одну неориенти рованную дугу можно заменить двумя ориентированными. Суще ствование петель (дуг, ведущих из некоторого узла в тот же узел) исключается.
Последовательность узлов и дуг N\, А \2, N2, А 23, • • Nk~\,
Ak- 1,ь Nk сети называют цепью (ориентированной цепью), веду щей из узла Ni в узел TV*.. Если N\ = Nk, то такую последова тельность называют ориентированным циклом. Цепь называют про стой, если она не содержит циклов.
Путем называют последовательность N \,A \2,N 2,A 23,...,N k -i, А к-\,ь N k, где N \, N2, ■■-, N k —узлы сети и либо A iti+l, либо A i+iti, г= 1,2, ...,к — 1, — дуга сети. Путь отличается от цепи тем, что при движении от узла N\ к узлу N k можно пройти дугу сети и в направ лении, противоположном ее ориентации. Для неориентированных сетей понятия цепи и пути совпадают. В частности, циклами явля ются контуры.
Контуром называют конечную цепь, начальный и конечный уз лы которой совпадают. Очевидно, что циклы являются замкнутыми путями, а контуры замкнутыми цепями. Вырожденный цикл назы вают петлей. Петля образуется одним узлом и одной дугой и по этому является как контуром, так и циклом.
В связной сети для любых двух различных узлов существует по крайней мере один соединяющий их путь (или цепь). Частным случаем связных ориентированных и неориентированных сетей яв ляются деревья. Если множество всех узлов и дуг задать в виде графа G = (TV, А), где N — множество узлов, А — множество дуг, то дерево определяют как связное подмножество {подграф) G\ мно жества (графа) G, не содержащее циклов, т. е. для любых двух узлов дерева существует единственный путь, соединяющий их. В сети, содержащей п узлов, подграф из к узлов (к ^ п) является деревом, если выполнены любые два из следующих условий:
1)подграф является связным;
2)подграф не имеет циклов;
3)число дуг в подграфе равно к — 1.
Остовным связующим деревом (остовом) называют дерево, содержащее все узлы сети. Если сеть содержит п узлов, дере во с п узлами и п — 1 дугами является остовом. Кратчайшим