Файл: Пивоваров, С. Э. Моделирование процессов прогнозирования в приборостроении.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.10.2024
Просмотров: 75
Скачиваний: 0
етва оси t, должны быть линейно независимы при t — ?. Используя эти фиксированные параметры, легко получить выражения для xi0(t) и Лу(0> необходимые для исследования имеющейся основы. Действи
тельно, допустим для определенности, |
что задача решается с по |
|||||
мощью |
второго |
алгоритма |
(метод |
обратной матрицы). Пусть |
||
еЧ ~ ец(П< 0 = |
И М; / = |
1, |
N) — элементы основной таблицы, |
|||
отвечающей системе векторов |
A^t'), |
Л8 , |
..., ASM. Если х'ц, (i = |
|||
= 1, М) |
— коэффициенты разложения вектора А по данной основе, |
|||||
а |
|
м |
|
|
|
|
|
|
|
|
|
^ I £\afla,ji |
|
|
|
^М+1, еаа\, |
%1/ |
|||
ТО
Приведенные формулы — следствие основных рекуррентных соотношений линейного программирования, примененных к случаю, когда вектор ЛХ(Г) основы заменяется на вектор A x{t) = A^(t') +
+ (/ — 4 ) л ;'.
По аналогичным формулам можно вычислять %(/) в тех случаях, когда в этом возникает необходимость.
Множество значений параметра t, при которых условия (5.2.40), (5.2.41) совместны, связно. Множество значений параметра t, при которых условия задачи, двойственной по отношению к (5.2.39) — (5.2.41) , несовместны, также связно.
Исследуя параметрическую задачу справа от t, как было пока зано, либо строим новое множество оптимальности, либо оказы ваемся в условиях случая б (несовместность условий исходной за дачи) или случая в (несовместность условий сопряженной задачи). В случае б утверждение, сформулированное выше, позволяет сделать вывод о несовместности условий (5.2.39) — (5.2.41) во всех точках
правее t.
Описанная процедура (случаи б и в анализируются аналогично случаю а) позволяет полностью исследовать задачу и приводит за
конечное |
число итераций к формированию функции f (t) = |
|
= max( |
V |
CjXA , где максимум берется по точкам X, удовлетво- |
* \/=! |
/ |
|
ряющим условиям (5.2.39) — (5.2.41). Используя вышесказанное, можно доказать следующее положение.
Если задача (5.2.39) — (5.2.41) разрешима более чем при одном значении t, то:
не
а) область определения Е функции f(f) представляет собой связное множество или состоит из двух связных компонент;
б) множество Е конечным числом точек /; (критические точки) разбивается на связные множества £*, на каждом из которых / (/) — непрерывная дробно-линейная функция.
В отличие от случаев, рассмотренных ранее, f (t) необязательно должна быть непрерывной функцией в области своего определения. В граничных точках множеств £,• она может терпеть разрыв, причем односторонние пределы в точках разрыва могут быть как бесконеч ными, так и конечными. Описанный метод позволяет исследовать задачу (5.2.39) — (5.2.41) при всех значениях параметра t, за исклю чением точек разрыва функции f (t).
Учитывая сложность методов параметрического линейного про граммирования и возможность практической реализации только частных случаев задачи (5.2.26) — (5.2.28), а также необходимость использования методов линейного программирования, перейдем к исследованию методов последовательного улучшения плана [21, 79, 80]. Причем, ввиду большого числа ограничений рассмотрим метод блочного программирования, называемый методом разложе ния [22].
Общая теория метода разложения. 1. Рассмотрим задачу линей ного программирования общего вида. Требуется обратить в макси мум линейную форму
при условиях: |
|
|
L = (C, X) |
|
(5.2.47) |
|
|
|
АХ = В, |
|
(5.2.48) |
||
|
|
|
|
|
||
|
|
|
|
Х ^ О . |
|
(5.2.49) |
Здесь С = |
(clt |
сз> |
• ••> |
Cjv) — JV-мерный |
вектор-строка; |
|
В = |
(bi, |
Ь2, |
..., |
Ьм)Т — JW-мерный |
вектор-столбец; |
|
А = |
|| a,j |
|| — матрица условий размером |
М X N; |
|||
X = |
(*!, |
х2, |
.... |
xN) — JV-мерный |
вектор-столбец. |
|
Разделим ограничения задачи на два блока. |
К первому блоку |
|||||
отнесем первые М ограничений, ко второму — остальные. Обозначим матрицы условий, отвечающие обоим блокам, через А1 и А2 соответ ственно, а векторы ограничений блоков через В\ и В2:
ЧЭД »-(£)•
Задача (5.2.47) (5.2.49) принимает вид
L = (С, X) max |
(5.2.50) |
при условиях: |
|
А1 ■Х — В\, |
(5.2.51) |
А2-Х=*В2, |
(5.2.52) |
А =г0. |
(5.2.53) |
|
117 |
Предположим, что множество, определяемое условиями (5.2.52), (5.2.53) , ограничено (в дальнейшем откажемся от этого предположе ния). Обозначим вершины выпуклого многогранника, отвечающего условиям (5.2.52), (5.2.53) через хх, х2, .... хыг. Точки хх, ..., хм,
являются геометрическими образами опорных планов задачи
(5.2.50), (5.2.52), (5.2.53). Будем называть задачу (5.2.50), (5.2.52), (5.2.53) Х2-задачей, а исходную задачу (5.2.50) — (5.2.53) — Х-за-
дачей.
Любая точка х многогранника, отвечающего условиям (5.2.52), (5.2.53) , представляет собой выпуклую комбинацию его вершин, т. е.
|
N 2 |
|
(5.2.54) |
|
х = |
2 |
z \ x y , |
||
|
V = 1 |
|
|
|
^ |
2 |
V= |
l; |
(5.2.55) |
V = 1 |
|
|
|
|
SsO, |
(v = |
1, N2). |
(5.2.56) |
|
Формулы (5.2.54) — (5.2.56) позволяют перейти в исходной задаче |
||||
от переменных х} к переменным zv. Полагая |
известными опорные |
|||
планыл;у = (x<v), x<v), ..., *$>), перепишем задачу (5.2.47) —(5.2.49) —
или, что то же самое, задачу |
(5.2.50) — (5.2.53) — в виде |
|||
n2 |
|
|
|
|
2 |
(С, xv) zv -v max |
|||
V = 1 |
|
|
|
|
при условиях: |
|
|
|
|
yv 2 |
|
|
|
|
2 |
(Al, xy) Z y = B\\ |
|||
|
v = |
l |
|
|
ZySzO, |
(v = |
1, |
N2). |
|
Введем обозначения |
|
|
|
|
|
(Ci> |
Xy) = |
Oyt |
(5.2.57) |
|
Al Xy = py. |
(5.2.58) |
||
Здесь ctv — скаляры; |
|
|
|
|
pv — Mi-мерные векторы. |
|
|
||
В новых обозначениях задача сводится к вычислению перемен ных Zy, на которых достигается максимум линейной формы
N , |
|
(5.2.59) |
2 |
av*v |
|
V = |
1 |
|
118
при условиях:
|
|
N.. |
|
|
(5.2.60) |
|
|
|
P vz v — Д1» |
||
|
|
n 2 |
|
|
|
|
|
У i Z \ == l: |
|
(5.2.61) |
|
|
Zv3i0, |
(v = l, |
N 2) . |
(5.2.62) |
|
Будем называть |
задачу |
(5.2.59) — (5.2.62) Z-задачей. |
|
||
Условия (5.2.60) и (5.2.61) Z-задачи удобно записывать в виде |
|||||
одного векторного равенства |
|
|
|
||
|
|
ЛГ„ |
__ |
|
(5.2.63) |
|
2 |
pvzv = B 1, |
|||
где |
V |
= 1 |
|
|
|
|
|
|
|
|
|
Pv = |
(p;v): |
M |
= (* '), |
(v = T7~/V^) |
(5.2.64) |
— соответственно векторы условий и ограничений Z-задачи.
Для решения Z-задачи вовсе необязательно знать все векторы pv.
На каждом шаге необходимо иметь только A4X+ |
1 векторов условий |
Z-задачи, составляющих ее текущий базис. Что |
касается вектора, |
подлежащего включению в базис, то он выбирается путем решения некоторой вспомогательной задачи линейного программирования с условиями (5.2.52), (5.2.53). В этом сущность метода разложения.
Решение Z-задачи однозначно |
определяет |
оптимальный |
план |
X-задачи. Вектор X* — решение |
Х-задачи — вычисляется |
через |
|
компоненты г* оптимального плана Z-задачи по формуле |
|
||
N , |
|
|
|
X* = 2 |
z**v. |
(5.2.65) |
|
V = |
1 |
|
|
Действительно, вектор X* является планом Х-задачи, так как: а) X* удовлетворяет условиям (5.2.52), (5.2.53), как выпуклая
комбинация опорных планов xv\
б) X* удовлетворяет условиям (5.2.51), поскольку в силу ра венств (5.2.65), (5.2.58) и (5.2.60)
N , |
Ni |
А 1Х *= 2 |
Alxvz3= 2 pvz* = B 1. |
V = 1 |
V = 1 |
Кроме того, из условия оптимальности вектора
N t |
N2 |
У, OvZ* S& °VZV
Y=0 Y=1
m