Файл: Арутюнян А.Г. Применение математических методов и ЭВМ в народном хозяйстве.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.07.2024
Просмотров: 188
Скачиваний: 0
I |
*„+*., |
еслн Л |
— о, |
a x m,2 ,.< 0 , |
|
|
|
(13.6) |
|
I |
- о о , |
еС‘1Н Л'т +3.), = |
-<т+2. j, = 0, Я * т + М ,< 0 . |
|
Отметим, |
что |
случай -Гт+з.}, <^0 |
исключается, так как в |
|
этом случае в выбранном столбце |
найдется хотя бы одни |
|||
положительный элемент. |
|
|
||
б) Если в выбранном столбце имеются положительные |
||||
элементы, то для них находим: |
|
|||
Строка i0 определяет вектор, |
подлежащий исключению из |
|||
базиса. Если имеются равные минимальные отношения, то применяем обычный способ преодоления зацикливаний (это обеспечивает и допустимость базиса для достаточно боль ших значений /-).
После выбора единственной строки преобразуем симп лексную таблицу по обычным фурмулам преобразования метода последовательного улучшения плана.
Таким образом, после конечного числа шагов либо по лучим оптимальную таблицу на четверти плоскости л^=).тах, (где ).wex и определены по формулам (13.4) — (13.5)), либо обнаружим, что на полуплоскости ti>]j.'mal
область N' не имеет ни одной точки (где |
определяется |
по формуле (13.6)). |
|
Ясно, что при |A'max s=s — во, < V '= 0 ; |
так что в этом слу |
чае вычисления прекращаются. Если же ^'тах^>— оо, то ни
же |
линии |
= |
оценка Д,- будет неотрицательной (на |
|||
данном шаге). Если при ;х = |
tx'max все оценки неотрицательны, |
|||||
то |
на |
некоторой |
полосе |
|x'^(j.^(i'ma),, |
функция |
|
/й(/.,1х) |
порождается соответствующим базисом. |
|||||
|
Если |
же при |
= |
не все оценки |
неотрицательны, |
|
то определим вектор, подлежащий вводу в базис. Для
этого |
определяется |
|
|
|
|
|
Дь = |
min {!l'm„Xm+2, j + |
i '• |
(13.7) |
|
|
|
*m+Z, j=° |
|
|
|
Очевидно, |
что Aj0< 0 . |
Значит вектор |
подлежит |
||
вводу |
в базис. Если все |
элементы |
соответствующего |
||
245
столбца (первых т строк) неположительны, то по формуле
(13.6) |
находим новое значение |
при котором |
функция |
F i(>., |
(i) не определена для |
При наличии |
хотя бы |
одного положительного элемента вышеуказанным способом находим вектор, исключаемый из базиса, и реализуем пре образование таблицы по методу последовательного улуч шения плана.
Этот процесс продолжается до тех пор, пока на неко
тором шагу либо |
ll!na>i — — °°> |
либо при ^ |
> |
— <х> и |
'•Ss'-max (где |
определяется |
по формуле |
(13.6), |
а /.тах — |
по формуле (13.4)) имеем базис, порождающий функцию Fi{i-, н-). Очевидно, что мы придем к одному из этих слу чаев за конечное число шагов.
При |
Ф — со |
определим: |
|
||||
|
тах |
{ _ |
i |
V |
если существуют лгт м, j= 0 |
||
|
3<J<n+3 \ |
Xm+i |
} |
) |
И Хт+2, J> О, |
|
|
|
— со, |
в противном случае. |
(13.8) |
||||
Таким образом, выделяется прямоугольник А";0, на ко |
|||||||
тором |
определена: |
|
|
|
|
||
Ft (>., |l) == Л т ^з, |
1 Ml.JJ. + ЛГш-З, 2 M\X - f |
X m +2, i + |
|||||
|
|
+ |
-Xm+2.2|i +Л :т +1.1А +Л Г Ш.;],2 . |
(1 3 .9 ) |
|||
Прямоугольник N't0 определяется следующими соот |
|||||||
ношениями: |
|
|
|
/•iО . < + вс, |
|
||
|
|
|
|
|
|
||
|
|
|
|
|Xjs? a sg |
|
||
где |
вычисляется по |
формуле (13.4), р, |
вычисляется либо |
||||
по |
формуле |
(13.5), либо |
по формуле (13.8): причем в пер |
||
вом случае ц^а>х= |
+ во, |
а во |
втором — ц***, определяется |
||
по |
формуле |
(13.6). |
Отметим, |
что, если Uj— — оо, то все |
|
последующие прямоугольники будут неограниченными, т. е.
являются |
полосами, лежащими ниже линии |x = ix^k*. |
5. |
Предположим теперь, что и.} =£ — со. Тогда при ti< |
признак оптимальности данного базиса нарушается. В базис вводится вектор, при помощи которого по формуле (13.8) или (13.5) было определено значение а,. Ясно, что при преобразовании для /. = /j нужно обеспечить допустимость
246
полученного базиса. Из полученной таблицы по формуле- (13.8) определяется |i2. Этим выделяется новый прямо
угольник (это будет N'l't+i |
или iV'/+j,o), |
на котором соот |
|
ветствующая |
функция |
i-l) или Fi+j ( |
}j.) определяется |
по формуле |
(13.9). |
|
|
Продолжая переходы |
по линии |
через конечное |
|
число шагов либо найдем такое значение [л(|1), при котором в соответствующей симплексной таблице лгщ+з, i — -*т+з, 2 = 0 , либо получим такое что для [isSft полученный базис бу дет порождать некоторую функцию Е,()., !*). После нахож дения ^ фиксируем точку {>., и), В этой точке уже опре деляется функция F (/., fi); т. е. (/.,, |t)£jV.
Указанным способом, последовательно реализуя симп лексную процедуру, на линии >■= /.., отмечаем последова тельность точек (>.,, !гк), являющихся левыми верхними вер шинами последовательных прямоугольников iVk. Через ко нечное число шагов получим значение ц, при котором для
либо F (}., [i) не определена, либо пораждается одним и тем же базисом. После получения наинизшей точки (/.,, ц) реализуем следующую последовательность операций отно сительно имеющейся симплексной таблицы.
6. |
Так как >-г была определена по формуле (13.4), то |
при /. = |
/•! какая-либо из базисных переменных обращается |
в нуль, а при /.<>., она становится отрицательным. Значит,, соответствующий вектор подлежит исключению из базиса.
Если в указанной |
строке все элементы неотрицательны, |
то левее.линии ) .= |
/., задача (13.1')—(13.3') неразрешима. |
Если же хотя бы один из элементов указанной строки по ложителен, то единственным образом определяется вектор' подлежащий вводу в базис. Ясно, что новый базис будет допустимым при /..sS/.sS/., (где ).2 определяется по формуле
(13.4), если существует |
л;Г1> 0 |
и |
/.2= |
— оо в противном |
слу чае). |
|
|
|
|
Если окажется, что |
/.2 = /.,, |
то |
снова |
реализуется один |
шаг метода последовательного уточнения оценок. Через
конечное число шагов либо получим точку |
ПРИ ко- |
|
торой для >.'2^ ).sS /., имеющийся базис порождает |
функ |
|
цию F (/; |t), либо обнаруживаем, что при |
F()., ц) не |
|
определяется. Таким образом, npnjt = u. |
выделим |
прямо |
угольник, левая граница которого лежит на |
линии >. = |
|
247
При /.==>^ увеличиваем значение <а и отмечаем на этой ли нии левые верхние вершины последовательности прямо угольников, на каждом из которых выдаем значения коэф фициентов функции F {К ц) в выражении (13.9), Реализуем последовательно обычную симплексную процедуру до тех
пор, пока |
получим |
верхнюю |
границу |
значений а, при ко |
|||
торых ()-2, |
|i) £iV. |
|
|
|
|
|
|
Итак, по линии /.theorist мы последовательно спуска |
|||||||
емся вниз до получения минимального |
значения ч. |
После |
|||||
этого по линии |
|х = |
const = |
!imin продвигаемся |
влево |
и по |
||
лучаем другое |
значение |
По новой линии |
const (по |
||||
рученное |
значение |
/>) поднимаемся вверх до |
достижения |
||||
значения |
|j-=* t^max- |
По линии |x«=|imax |
на один |
шаг |
пере |
||
ходим влево и по новополученной вертикали спускаемся вниз.
На рис. 13.1 схематически показан процесс описанных переходов.
Как видно из рисунка, более эффективно, если мы
•осуществляем переход по линии [a — const (н.П1ах или ;j.min) не на один шаг, а сразу на Д8а шага, каждый раз опреде - лив прямоугольники с правой стропы линии Однако
•описанный процесс проще и дает возможность оперативно провести контроль правильности вычислений (переходом в
248