Файл: Арутюнян А.Г. Применение математических методов и ЭВМ в народном хозяйстве.pdf

тельно Я4 должен выйти из базиса, а в базис вводится — Р2. Текущая таблица преобразуется методом последователь­ ного уточнения оценок.

По направлению S решается однопараметрическая за­ дача, фиксируя отрезки и базисы, порождающие функцию

4 > W = f (A(0,+ l ‘ S) на этих отрезках.

В результате получается:

A -" = A « + ^ = ( i , i ) 4 - f ( - 1 . - Ч = ( т ' Y >

Из полученной симплексной таблицы определяется строка, базисные переменные которой в точке ji,nax меняют знак (строка Яа).

Из первых трех столбцов строки Я2 составляется урав­ нение

и находятся промежуточные значения К

Если л1==0, то />2 = - 3 -, а если Х2 = 0, то >., = 3.

В результате получается промежуточная точка Л(2\«= (3,0).

Теперь на этой прямой выбирается новое направление

Sv Так как Ли = (3,0), а Л(,,= ( - L - 1 ) , т0

^ - [ ( з - т Х о Ч ) ] - ^ - - ^

По выбранному направлению снова перейдем к'-одно- параметрической задаче и определим коэффициенты при

т - ^ + ( - т ) ( - - т ) - т .

( Х ) ^ + ( - ^ ) ( - т ) = о ,

4 l + 5( ~ t )= 4 -

Свободные члены будут:

_3_ _3_____L — J_

270

Имеющаяся таблица примет вид:

Преобразуем симплексную таблицу:

Для выбора нового направления, определяется проме­

272

Новые значения коэффициентов при [* будут соответст­ венно равны:

------!----- - + 2 •— = 0 ,

1

. „ - - Н - Ц - Т — А . А + 3 . Л „ ± ,

а свободных членов:

По выбранному направлению 5 (2), реализуя один шаг метода последовательного уточнения оценок (при р- > 0 базисная переменная х 2 меняет знак), получаем следую­ щую таблицу:

т

18—644

где область Ж\ определяется условиями:

на конечном интервале. Но так как по этому алгоритму мы двигаемся по оси X только в одном направлении, то сле­ дует либо запомнить матрицу, соответствующую начальной точке Х0 (чтобы в дальнейшем построить f(X ) на допол­ нении уже рассмотренной полуоси), либо после получения одной границы области N двигаться в обратном направ­ лении по рассмотренным подобластям Nт до получения другой границы. Следовательно, решение поставленной за­ дачи на ЭВМ в первом случае приводит к потерям объема памяти, а во втором случае — машинного времени. Из до­ казанных в предыдущих параграфах утверждений сле­ дует, что:

а) области М, являются конечными отрезками, кроме, может быть, двух крайних, которые могут быть лучами;

б) если в точке Хт получены все базисы, порождающие F(X,), и ни один из этих базисов не остается допустимым левее (правее) точки Хт, то X- является левой (правой) гра­ ницей области Nil

в) на каждом N. функция F(X) является линейной, а на общих границах двух соседних Мт—непрерывной функцией;

г) функция F(X) вогнута.

Для решения задачи (15.1) — (15.3) пользуемся соот­ ветствующей расширенной задачей, обеспечивая заранее неотрицательность правых частей условий (15.2) для доста-

275

состоящая из искусственных векторов, будет базисом рас­ ширенной задачи.

Для расширенной задачи заполняется исходная сим­ плексная таблица, отличающаяся от симплексной таблицы обычной числовой расширенной задачи тем, что здесь для значений базисных переменных отводятся два столбца (вместо одного): в первом столбце заполняются коэффи­ циенты Ь\ при X, а во втором -свободные члены Ь>.

К заполненной симплексной таблице применяется алго­ ритм метода последовательного улучшения плана и через конечное число шагов либо обнаруживается неограничен­ ность целевой функции, либо обеспечивается признак опти­ мальности (неотрицательность оценок внебазисных векто­ ров). В первом случае заключаем, что jV = 0 . Во втором случае имеется базис, являющийся оптимальным базисом расширенной задачи на некотором луче (X ',,+ ©о). Как видно, нахождение точки X't эквивалентно (по объему вы­ числений) решению одной числовой задачи линейного про­ граммирования. Если в полученном оптимальном базисе не

луче. Если же оптимальный базис содержит хотя бы один искусственный вектор с положительным значением базис­ ной переменной, то область N (если она не пуста) может находиться только левее от указанного луча. Для перехода по левой границе указанного луча пользуются методом последовательного уточнения оценок.

В [20] приведены формулы преобразования симплексной таблицы и определения отрезка, на котором функция /■’ (/.) порождается одним н тем же баз'исом. Очевидно, эта ме­ тодика приемлема и для построения соответствующей функции расширенной задачи. Через конечное число пере­ ходов строятся последовательность соседних отрезков и выражения целевой функции. Если при таких переходах попадаем на отрезок, где оптимизирующий базис уже не

•содержит ни одного искусственного вектора, то это озн&г

276