Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 34
Текст из файла (страница 34)
(317), (318), (3.24)— (3.26)). После такого преобразования переменная и' перейдет преобразований — их нужно было вычеркивать по мере того, как соответствующая вспомогательная переменная переходила из базисной в небазисную. Заметим, что в симплекс-таблицах столбцы, соответствующие базисным переменным, также часто вычеркивают, так как в каждом таком столбце всегда находится одна и та же заранее известная информация: в строке, номер которой равен номеру базисной переменной, находится единица, а все остальные элементы такого столбца равны нулю. Таким образом, метод построения начальной угловой точки и ее симплекс-таблицы для канонической задачи описан.
Симплекс-метод для решения таких задач полностью обоснован. Существуют и другие методы поиска начальной угловой точки. 3. Для иллюстрации изложенного выше приведем один пример. П р и м е р 1. Минимизировать функцию У(и) = й+ Зй+ 2й+ й — Зй (15) 144 ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ /гл. з в базисные, а переменная и' станет небазисной, и, как было замечено выше, в следующей симплекс-таблице столбец для и' можно вычеркнуть. В результате получим табл. 9. Из атой таблицы видно, что в полученной угловой точке з, =(О, О, О, 3, О, О, О, 0) множества Таблица 8 Таблица 9 Свебенные члены Бавненые переменные и' не — 1/2 — 5/2 5/2 на иа иа 1 Π— 5 1/2 1/2 — 5/2 — 2 — 2 10 2 2 значение функции У,(з,)=0. Поскольку е,(з)>0 при всех з вил, а У,(г,)= О, то ясно, что 1Е1У,(з) = У,(з,) = О, т.
е. вспог могательная задача (18) — (20) решена. Тогда точка Р, =(О, О, О, 3, 0) является угловой для множества У. Для получения базиса точки и, вспомогательные переменные й, и' в табл. 9 нужно вывести из числа базисных. В строках переменных и', й на пересечении со столбцами не- базисных переменных имеются положительные величины, любую из которых можно взять в качестве разрешающего элемента для вывода одной из вспомогательных переменных из числа базисных. Возьмем, например, величину 1/2 из столбца й и строки и' раарешающим элементом и осуществим симплекс-преобразование табл. 9. Получим табл.
10. В этой таблице в строке для и' все величины равны нулю. Как было замечено выше, такую строку беэ ущерба можно вычеркнуть из симплекс-таблицы. В результате получим табл. 11. В ней строки переменных и', и' соответствуют системе уравнений и' = — 2и'+ 4й + и', й и'+ 2й + 3, 4 б1 ОБ условии РАЗРешимости кАноническои ЗАДАчи 14ч которая эквивалентна системе (17). В нижней строке табл.
11 представлены коэффициенты, полученные подстановкой выражений (21) для базисных переменных и', и' в (15): е'(и) = 2и' + 6и' + 3 = — ( — 2) и' — ( — 6) и' + 3. Таким образом, табл.11 является симплекс-таблицей угловой точки (О, О, О, 3, 0) для аадачи минимизации функции (15у Таблица 10 Бнвисные переиениые Свободные члены не не нв ие не — 4 ΠΠ— 1 — 2 О 2 — 1 О Таблица 11 Бввисные переиенные Свободные члены н' не пв ие — 4 Π— 1 — 2 2 — 1 Функции при ограничениях (16), (21) (ср. с задачей (12) — (14)). Остается решить эту задачу симплекс-методом. Впрочем, в данном случае из табл.
11 сразу видно, что в нижней строке нет положительных величин — реализовался случай 1 (см. (3.13')). Это значит, что и. =(0,0,0,3,0) — решение задачи (15) — (17). й 6. Об условии разрешимости канонической задачи Как показывает теорема 5 1, с помощью описанного выше симплекс-метода можно не только численно решать задачи линейного программирования, но и можно доказывать основные факты теории линейного программирования. Приводим еще две такие теоремы.
Т е о р е м а 1. Для того чтобы каноническая задача (1 14) была разрешима, т. е. существовала точка иевнП такая, что (с, ин) = ш1 (с, и) ) — оо, необходимо и достаточно, чтобы: и 1) множество У было непустым; 2) функция з(и)=<с, и> была ограничена снизу на К Доказательство. Необходимость очевидна. Докажем достаточность. Из того, что УФ й, по теореме 51 следует суще- $46 ЗЛЕЫЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ГГЛ. 3 ствование угловой точки множества У.
Принимая эту точку за начальную, будем решать задачу (1.14) с помощью симплекс- метода. Поскольку по условию 1Е(з" (и) ) — оо, то случай П О (условие (3.14)) здесь невозможен, и за конечное чпсло шагов симплекс-метода процесс завершится отысканием точкп и, являющейся решенпем задачи (1.14). Т е о р е м а 2. Если задача (1А4) разрешима, то среди ев рвшсний найдетгя хотя бы одна угловая точка множества У.
Доказательство. По условию теоремы УФ О и суще ствУет точка ив~У такаЯ, что (с,и ) =1п1(с,и)) — оо. и По теореме 5.1 тогда множество П имеет хотя бы одну угловую точку. Отправляясь ог одной из этих угловых точек, с помощью симплекс-метода за конечное число шагов придем к угловойточке ив, являющейся решением задачи (1.14). На этом заканчиваем изложение симплекс-метода для решения и исследования канонической задачи (1А4). Учитывая связь между общей задачей линейного программирования (1.5) и задачами (1А4) и (1.15), установленную в з 1, можно сказать, что симплекс-метод является универсальным методом решенпя задач линейного программирования.
Однако это не значит, что симплекс-метод выгодно применять во всех случаях. Существуют и другие общие методы, а также ряд частных методов, приспособленных для решения специальных классов задач линейного программирования, лучше учитывающих конкретные особенности задачи. Например, для транспортных задач, у которых матрица А в ограничении Аи=5 имеет ряд особенностей, разработаны специальные методы.
Отметим, что известен пример задачи линейного программирования с н переменными и 2п ограничениями, для решения которой требуется не менее 2" — 1 итераций симплекс-метода и, следовательно, количество необходимых вычислений оценивается экспоненцнальной функцией параметров задачи. Это значит, что существуют задачи линейного программирования не слишком большой размерности, решение которых симплекс-методом невозможно за обозримое время. Однако вопреки этому пессимистическому выводу в практических задачах симплекс- метод показывает поразительную эффективность, и число необходимых итераций отнюдь не растет экспоненциально с ростом размерности.
Причина этого удивительного явления пока еще не выяснена. Хотя и в последнее время появились методы 13131, в которых объем вычислений при решении задач линейного программирования выражается полиномом от параметров задачи, тем не менее симплекс-метод по-прежнему остается основным методом в линейном программировании. В заключение подчеркнем, что всюду выше предполагалось, что исходные данные задачи линейного программирования— $ З) ОБ УСЛОВИИ РАЗРЕШИМОСТИ КАНОННЧЕСКОИ ЗАДАЧИ 147 матрица А, векторы Ь, с — известны точно и, кроме того, все промежуточные вычисления В симплекс-методе проводятся без погрешностей.
Такая идеализация позволила нам дать строгое обоснование симплекс-метода, доказать ряд важных теорем линейного программирования. Однако на практике исходные данные задаются, как правило, неточно, промежуточные вычисления проводятся с округлениями и применение симплекс-метода нли других методов в конкретных задачах линейного программирования может привести к большим погрешностям, неверным выводам.
В частности, наличие погрешностей может сделать задачу линейного программирования некорректной, и для ее решения могут понадобиться специальные методы регуляризации (б, 22]. К задачам линейного программирования мы еще вернемся в 3 4.9. У и р а ж и е и и я. 1. Минимизировать функцию и' — пт — и' — и" + 2из при условиях и' ~ )0 (» = 1, ..., 5), и'+Зпз+ и'+ и' — 2пз = 10, 2и'+ + бпз+ и'+ За' — 4и'= 20, Зи'+ 10из+ па+ би» вЂ” 7из = 30. 2. Максимизировать фуикцию и' — 4и'+ Зи'+ 10и' при условиях и' > 0 (< = 1, ...
4) и'+ из — пз+ и» = О, и' + 14и<+ 10из — 10п» = М. 3. Мияимизировать фувкцию и'+ 2и' — 2из+ 5и' при условиях и' ) 0 (< = 1,, 4), и'+ 2и' — пз — и» = 1, — и'+ 2и'+ Зиз+ и' = 2, и'+ 5из+ пз и» 4. Мииимизировать функцию и'+ и'+ и' при условиях и') О, из) О, вз)0, и'+и'=1, и' — и'=1, Зи' — п»=3. 5. Мииимизировать Функцию и'+ 2п<+ Зпз+ 4и< при условиях и»,в 0 (< = 1, ..., 4), и' + и' + и< + и< > 1.
6. Минимизировать функцию и'+ а<+ из+ и» при условиях и') О (» = 1, ..., 5), и' — и' ) О, и' + и' — и'+ и' — и' ) 1. рассмотреть згу же задачу при дополиительиом огравичеиии 1 с и' » 2. 7. Мииимизирозать функцию из — и<+ и< — и' при условиях и' > О (< = 1, ..., 7), и'+ и' — 2и' — За<+ 4п» = О, из+ 4и' — Зп» вЂ” 2и'+ и< = О, и'+ и<+ и»+ из+ и'= 1.
Покааать, что в атой задаче можпо получить аацикливаипе, если с помощью симплекс-метода организовать перебор базисов в следующем порядке: (Аз, Аз, А») »- (Аз, А», А») -» (Аз, А< А») -»- -ь (А», А<, А») -» (А», Ав, А») -ь (Аь А<, А») — (Аз, Аз, А»). Применить для решения атои задачи симплекс-метод с аитициклином, изложенный в кокце 13.
8. Обобщить симплекс-метод па случай задачи <с, и>-~1п(; иш<»'=(и: пшЕ", Аи=Ь, а<(п'())<, <=1, ..., п), где а<, ()» — задапкые величины, а, с 3» (< =1, ..., и) (возможио, иекоторые пз а» = с и некоторые из Ц< = сс). 9. Пусть 1» = (и: и ш Е", <аь и>< Ь», » = 1, ..., т), и ) и, Показать, что точка и ш П является угловои для Ь» тогда и только тогда, если в точке г обращаются в точные равенства ке мепее чем и из неравенств <а», и> ( ( Ь', среди которых есть п ликейио независимых.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
