XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 14
Текст из файла (страница 14)
Воспользовавшись этим представлением целевой функции, с учетом неотрицательностн переменных модели можно показать, 'что: а) небазнсный столбец а, матрицы А имеет смысл вводить Н новый базис, если симплекс-разность Н положительна; б) в новый базис целесообразно включать тот небазисный столбец матрицы А, у которого симплекс-разность имеет наибольшее положительное значение (условие оитпимальиостпи ььыбора); в) если все симплекс-разности неположительны, то значение целевой функции улучшить нельзя, т.е. допустимое базисное решение является оптимальным решением. Пример 3.2. Рассмотрим следуюшую задачу линейного программирования: х1+ хг — ь шах; х1 — хг>1, хг <2, х1>0, хг>0, Или в стандартной форме У1 + уг -ь шах; У1 Уг УЗ=1 Уг + У4 = 21 уь >О, 1=1,4, Где уь = хь уг = хг, уз и У4 — новые переменные модели, У(У) = Уо+,~, ь11уз, А — 0 1 0 /1 Аь=(ад аг) = ~ ~0 где коэффициенты Н., у = 1+1, 1У, относятся к свободным переменным модели и определяются равенствами (3.16).
Каждый 0 /1'ь  —, à — (1 1 О 0), (3.17) десАь=1, Аь ' = 1. (3.18) 3 СИМЛЛЕКС-МЕТОД т В этом случае, согласно (3.5), (3.17), вектор У = (3 2 0 0) является базисным решением, притом допустимым, и его можно использовать в качестве начального. Из соотношений (3.2), (3.12) и (3.17) находим (3.19) А, =, Гь = (1 1), Г, = (О 0). Значение целевой функции Д, соответствующее начальному допустимому базисному решению, определяется формулой (3.14) с учетом равенств (3.17) — (3.19): 2.2, Симплекс-метод при известном допустимом базисном решении 97 Если (А ~В), и (А ~по)ь — г-е координаты векторов А ~В и А ~а, соответственно и у =(Аь В)' (Аь и.) у., г'=~,~, (3.20) то при (А ~а„), > 0 и достаточно большом значении у„ новое значение у;, определяемое согласно (3.20), может стать отрицательным. Пусть 1 С (1, ..., Ц вЂ” множество индексов г, для которых (Аь ~а„), > О.
Максимальное значение нового базисного переменного у„определим следующим образом: 7е = ГьАь В = Ь, а матрица-строка симплекс-разностей определяется из соотно- шений (3.15), (3.16), (3.18), (3.19): (Из Нд) = Гх — ГьАь Ах —— (1 — 2). Таким образом, Из —— 1 > О, И4 = — 2 < 0 и в новый базис нужно т включить столбец аз — — (-1 О) матрицы А, а новым базисным переменным будет уз. 4~ Предположим, что в соответствии с условием оптимальности выбора определен небзэисный столбец а„матрицы А., который будет введен в новый базис.
Новый базис, полученный из старого путем замены в нем некоторого базисного столбца а~ матрицы А небазисным столбцом а„, должен обеспечивать получение нового допустимого базисного решения. Согласно (3.11) и (3.2), Ж -1 -1 1сь =Аь 'В Аь А у, =Аь В Аь ~ пйуйхе ь В - А, а,у„, з=Е,+1 так как новое базисное переменное у, > О, а все остальные небазисные переменные у = 0 для всех 2 Е (А+ 1, ..., А') ~ (г). шах ° '4ь В) $' Если у„= у„", то по крайней мере одно переменное уб где 1 Е 1, обратится в нуль и соответствующий ему столбец а~ матрицы А можно вывести из старого базиса. Заметим, что (3.21) фактически определяет условие дотьусьтьммоспьм выборе столбца аб выводимого из старого базиса.
Понятно, что это условие может быть представлено в следующем виде: (3.22) (Аь а„)~ ьеЙ (Аь ~а ), ' а новый базис, построенный с использованием условия оптимальности выбора и условия допустимости выбора, обеспечивает получение нового допустимого базисного решения. Если (А 'а„); < 0 для всех ь' = 1, Ь, то, согласно (3.20), при увеличении значения нового базисного переменного модели у, все новые значения у;, ь = 1, Ь, будут строго положительными. В этом случае задача не имеет решения: существуют допустимые решения со сколь угодно большим значением целевой функции (говорят, что оььтпммаиьмое ремьемме меограмичеммое).
3.2. Симплекс-метод при известном допустимом базисном решении 99 98 3. СИМЛЛЕКС-МЕТОД Пример 3.3. Вернемся к задаче линейного программирования, рассмотрение которой начато в примере 3.2. В соответствии с условием оптимальности выбора в новый базис должен т быть включен небазисный столбец а„= аз = ( — 1 0) матрицы А. Согласно (3.18), Все координаты вектора А 'а„неположительны, и задача не имеет решения, что подтверждается при графическом решении задачи (рис. 3.2).
Ог Ог "г=г (3) хи=о О4 хг=п Рис. 3.2 Из определения допустимого базисного решения, уравнения (3.11) и условия допустимого выбора (3.21) следует, что если бы начальное допустимое базисное решение было выроггсдемным, т.е. среди координат Уь есть нулевые, то значение у„'" вводимого базисного переменного у„могло бы оказаться равным нулю. Кроме того, если считать, что у„= у, " в (3.20), то среди переменных у;, г = 1, Ь, могут оказаться два или более нулевых.
Тем не менее из начального базисного решения должно быть выведено лишь одно переменное у~ и соответствующий ему столбец а~ матрицы А должен быть выведен из базиса и заменен столбцом а„. Отметим, что вырожденность допустимого базисного решения (как начального, так и полученного нового) может осложнить поиск оптимального решения задачи. Далее (см. пример 3.7) проблема вырожденности обсуждена подробнее.
Пример 3.4. Рассмотрим задачу линейного программирования 2хг + Ьхг — + шах; хг < 4оо, хг < 300, хг + хг < 500, хг>0, хг>0, нли в стандартной форме 2уг + 5уг -+ шах; у +у зе400, Уг+ У4 = 300, Уг + Уг+ Уь = 500, Уь>0, Й=1,5, где уг — хг уг — хг, уз, у4, уь — новые переменные, 1 0 1 0 0 А = (аг ...
аь) = 0 1 0 1 0 1 1 0 0 1 (3.23)  — 300 , Г (2 5 0 0 0). 500 Выберем, согласно (3.10), вектор У = (О 0 400 300 500) в качестве начального допустимого базисного решения. Тогда Уо=гьА,'В=Он ув = У4 10 Аь = (вз п4 аь) = 13, А, = (аг аг) ео 01 11 г = (о о 0), г, = (2 5). 3.2. Симплекс-метод при иоиестном допустимом оеэисном решении 101 3. СИМПЛЕКС-МЕТОД 100 Соглаано (3.15), (3.16), вычисляем матрицу-строку симплекс- разностей: (414 "з) = Ге — ГьАь ~Ае = (2 5) А так как Нз > 4 > О, то в новый базис вводим столбец а, = аз матрицы А и новое базисное переменное уз. т В рассматриваемом случае А,, ~а„= 1заз — — (О 1 1) .
Поэтому (А 'а,), > О при г 6 1 си (4, 5). А так как А,, 'В = В = = (400 300 500), то по условию допустимости выбора (3.22) (А 4В)~ (Аь~В); . (300 500\ =ппп ' ' =ппп —, — =300 (Аь а„)у 'е~ (Аь а,)ь и 1 = 4, т.е. в базисе заменим столбец а4 матрицы А ее столбцом аз.
Кроме того, согласно (3.21), (3.22), у "= 300, и для определения нового допустимого базисного решения в (3.20) заменим у, на у. и при 4= 3,4,5 вычислим уз = 400 — 0 ' 300 = 400, У4 — 300 1 ' 300 0 уь = 500 — 1 300 = 200. Таким образом, получаем новое допустимое базисное решение У = (О 300 400 0 200), Уз 0 1 0 Уь= уз Уе=( 1, Аь=(аг аз аь)= 1 0 0 ь, У4/ 1 0 1 0 1 0 1 0 А ~= 1 0 О, А,=(аь а4)се 0 1 0 — 1 1 1 0 Гь=(5 0 0), Г,=(2 0), 1о=ГьАь В=1500. Согласно (3.15) и (3.16), вычисляем матрицу-строку симплекс- разностей: (ь(ь ь14) = Ге — ГьАь Ае = (2 — 5).
А так как 414 > 0 и 414 < О, то в новый базис вводим столбец а„ = аь матрицы А и новое базисное переменное уь. т В рассматриваемом случае А ~а„= Аь ~аь = (О 1 1) . Поэтому (Аь ~а„)ь > 0 при г 6 1 = (3, 5). А так как А, ~В = т = (300 400 200), то по условию допустимого выбора (3.22) (Аь В)г . (400 200) =ппп~ —, — =200 (А 'а,)~ '1 1 ' 1 и 1= 5, т.е. в базисе заменим столбец аь матрицы А ее столбцом аь.
Кроме того, согласно (3.21), (3.22), у, = 200, и для определения нового допустимого базисного решения в (3.20) заменим у„на у " и при 1= 2,3, 5 вычислим Уз = 300 — 0. 200 = 300, уз =400 — 1 200= 200, уь = 200 — 1 ° 200= О. Таким образом, новое допустимое базисное решение имеет вид У = (200 300 200 0 0), Уь о Уь и уз, У,= ~ "~, Аь=(аь аз аз)= 0 1 О Уз 1 1 0 0 -1 1 0 0 Аь — 0 1 О, А,=(а4 аь)се 1 0 1 1 — 1 0 1 Гь=(2 5 О), Г,=(О 0) Уо=ГьАь~В=1900.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
