Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 7
Текст из файла (страница 7)
ГЛ. Ь ОСНОВНЫЕ ПОНЯТИЯ является наличие в (6) такой подматрнцы А, что г[А)=-г[АЬ[=и, Ах=Ь, где Ь вЂ” соответствующий и-мерный вектор. Тновемь 1.11. Пусть Т вЂ” выпуклый многогранник в Е", определенный системой (6). Для того чтобьь точка х Р Т бььла крайней в Т, необходимо и достаточно, чтобы х была нуль-мерной гранью Т, т. е. чтобы х было единственным решением системь1 уравнений а;х =- Ьп 16Л', [Л' ~ —.— и (7) ранга и. ДокАЗАткльстВО. Достаточность. Пусть х 6 Т и х — решение системы (7) ранга и, которую нам удобно записать в виде Ах= Ъ.
Покаькем, что х— крайняя точка Т. Допустим, что х=-Хх,лс(1 — Х)хг, где 0(Х( (1, а х, и хг — различные точки из Т. Тогда в силу определения х и Т Ь=-Ах=-А [Хл,+(1 — Х)ха[ =-ААх,+(1 — Л) Ахг(Ь (0(А(1), и, следовательно, Ахе.= Ь, Ахг Ь, Таким образом, Ах = Ахг — — Ахг = Ь. Поскольку А — невырожденная матрица, то х —.-А 'Ь=х1=-хг что противоречит предположению о различии точек х, и х,. Итак х — крайняя 'точка в Т. Необходимость.
Пусть х — крайняя точка многогранника Т, и, следовательно, х удовлетворяет системе ~(6). Заметим, что некоторые из соотношений (6) выполняются для х обязательно как равенства. Действительно, если бы а;х(йн 1=1, ..., т, то можно было бы подобрать такой вектор Ах, что а~(х-+Ах)(Ьн 1=.1, ... т. !гь БАзиснык, допъстимын и оптимАльнык Ркшвния 39 Тогда 1 —, —, 1 х = — (х.-- !Ах) -; — (х — Ах), 2 что противоречило бы предположению о том, что точка х. — крайняя.
Итак, существует множество 1, такое, что а;х=-Ьп 1с1, а х(Ьь 1й1. (8) Число равенств в (8) не меньше и. Действительно, если ! 1 ( = = Й ( и, то в соответствующей однородной системе уравнений а!х=О, гс1, (9) число уравнений меньше числа неизвестных. Поэтому система (9) имеет ненулевое решение х ~ О. Рассмотрим произвольное число е и точки х1=х-',-ех и хг=х — ех. Очевидно, а;х! =-Ьп а;хг-— - Ь! Ири 1с1, а при достаточно малом е точки х, и хг удовлетворяют неравенствам а х, ( Ьп а!хг ( Ь! пРи 1 й 1. Таким образом, при малом е точки х, и х, различны и принадле- жат Т.
Из определения х, н х, следует 1 х= — х!гп —,хз, х„хгСТ, 2 а х = Ьг, 1 С 1, ! 1 ! = п. Иеобходииость доказана. ° Твогвма 1.12. Если множество допустимых решений задачи линейного программирования есть многогранник, то любое допу- что противоречит предположению о том, что х — крайняя точна в Т. Итак, число равопств в (8) не меныпо и. Если бы среди векторов а;, 1 С 1, были линейно зависимые, то некоторые из равенств в (8) были бы следствиями других. Тогда, искл1очая их из рассмотрения, мы пришли бы к случаю ) 1 ( = Ь ( п. Таким образом, точка х с Т удовлетворяет п линейно нозависимым уравнениям гл. ь основнын понятия стимое решение представимое виде выпуклой линейной комбиначии базисных допустимых решений.
Доказатнльство. Действительно, пусть допустимые решения образуют многогранник. Тогда в силу теоремы 1.11 базисные допустимые решения системы ограничений задачи соответствуют крайпим точкам выпуклого мнон'ества. Поскольку любая точка многогранника выражается в виде линейной выпуклой комбинации крайних точек '), любое допустимое решение есть выпуклая линейная комбинация базисных допустимых решений. ° Допустимое решение хв задачи линейного программирования, связанной с минимизацией функции сх, называется оптимальным, если сха ( сх для всех допустимых решений х. Тковкма 1.13. Если существует оптимальное решение, то существует базисное оптимальное решение. Доказатнльство.
Очевидно, оптимальное решение конечно. По теореме 1.7 линейная функция, являясь вогнутой, достигает глобального минимума в крайпей точке выпуклого множества. Теорема 1 11 устанавливает, что крайняя точка соответствует базисному решению. 1.6. Геометрическая интерпретация задачи линейного програм- мирования Пусть дана задача линейного программирования: найти минимум г = сх прн условиях Ах) Ъ, х~)0, где А есть (т х и)-матрица. Для задачи линейного программирования известны две геометрические интерпретации.
В первой из них задача линейного программпровапия рассматривается в пространстве векторов х, называемом пространством ресурсов; вторая интерпретация связана с рассмотрением задачи в пространстве точек Ъ, пазываемом пространством условий (см. пример 3 в 1.1). Пространство ресурсов имеет размерность и. л1пожество решений ') в пространстве ресурсов является пересечением т полупрострапств а,х ) 6; и и полупространств х, ) О.
Если г рассматривать как параметр в выражении г = сх, то возит|кает сово- 1) Эта теорема допускает обобщение к на случай, когда множество допустимых решений пввветсв пеограпвчевпын выпуклым ыпогограппык н вежеством. — Прим. р ев. а) Мпожоство решений иногда павываетсл также пространством решений. упРАжнвнпя купность гиперплоскостей с направляющим вектором с. Оптимальным решением является вер1пипа, припадлел1ащая опорной гиперплоскости с направляющим вектором с. Оптимальное решение не единственно, если гиперплоскость з =- сх параллельна одной из гиперплоскостей, пересекающихся в оптимальной вершине.
Ь Во второй интерпретации задачи линейного программирования рас- ее сматривается т-мерное пространство а1 условий, где Ь представлено вектором (или точкой). Каждый столбец матрицы А из системы Ах = Ь есть ь вектор с т компонентами. Допустимое решение системы Ах =- Ь су- а, ществует, если точка Ь лежит внутри конечно пороя1денпого конуса, патянутого на векторы ап Поскольку пространство условий имеет размер- Р и с. 1.7. ность т, то в общем случае конус натянут на т векторов. Если векторов меньше, чем т, то получаем вырол1деппый случай. Каждому вектору а; поставим в соответствие стоимость с;; оптимальное решение задачи совпадает с минимальной по стоимости линейной комбинацией векторов агч равной Ь.
Рассмотрим задачу лилейного программирования: минимизировать х, + йх, + бхе при условиях (,),1-(')*.~ (,)*.=( ), *,>о э=а,2,э. Геометрическая интерпретация этой задачи дана иа рис. 1.7. Заметим, что оптимальным решением будет х1 == 1,1,; хз = О, х, = 11'ю Если ограничения замеяить па неравенства, например а;х; ) Ь, то задача сводится к отысканию комбинации векторов, да1ощей точку, расположенную выше и правее точки Ь. Упражнения 1.
Дана т х и-матрица'А = [аы) (т п) и т-мерный вектор Ь = (61). 11усть аы ) О и Ь1 ) О (1 = 1,..., т; 1 = 1,..., п). Всегда ли можно найти вектор х, такой, что Ах ~ )Ь? Всегда ли можно найти х, такой, что Ах = Ь? Всегда ли можно найти неотрицательный вектор х ~ )О, такой, что Ах = Ь? Почему? гл, >, основнык понятия 42 2.
Дана матрица А= 1 2 4 3, Ь= Пока>ките, что не существует вектора х, такого, что Ах = Ь. 3. Образуют ли решения системы Ах ) 0 конус? Выпуклый конус? 4. В $1.3 приведены четыре теоремы. Нарисуйте четыре кружка, изображающие эти теоремы. Если для доказательства некоторой теоремы необходимо доказательство другой, то соедините соответствующие кружки стрелками.
Проделайте то >ке самое со всеми теоремами этой главы. 5. Докая'ите лемму Минковского — Фдркаша в следующей формулировке. Система Ах < Ь имеет неотрицательное решение тогда и только тогда, когда из условий я ) О, яА > 0 следует яЬ) О. 6. Дано конечное число точек в плоскости. Рассмотрите выпуклую оболочку этих точек. Будут ли все данные точки крайними точками выпуклой оболочки? Даны точки (5, О), (2, 1), (О, 6) и (О, 0); найдите их выпуклую оболочку. 7.
Будут ли следующие функции, определенные на действительной прямой, выпуклыми? с, х>0, ?(х)=/х/, У(х)=х', /(х)=- Какие из приведенных 'фупкций строго выпуклы? Приведите пример непрерывной функции, пе являющейся ни выпуклой, ни вогнутой. 8.
Приведите пример а) конуса, не явля>ощегося выпуклым множеством; б) выпуклого множества, не являющегося выпуклым конусом. 9. Функция ? (х) называется квазивыпуклой тогда и только тогда, когда множество (х !? (х) ( Ы) выпукло для любых. действительных значений д. Докажите, что строгий локальный минимум квазивыпуклой функции является глобальным минимумом.
10. Выпуклая функция определена на отрезке — 3 ~( х ( 4, так что > ( — 3) = 3 и'? (4) = 2. В какой точке фупкциядостигает максимума? Почему? упРАН<пения Нерешенная задача. Рассмотрим задачу линейного программирования. минимизировать — сх при условиях Ах= Ь, х) О, где А — матрица ранга л<.
В теории линейного программирования говорится о том, что всегда моя по отыскать оптимальное решение с не более чем <л ненулевыми компонентами. (Нредполагается, что задача имеет по крайней мере одно оптимальное решение.) Какой смысл имеет утверн<дение, что оптимальное решение содергяит не более д ненулевых козшонент (д ( и)? СИМПЛЕКС-МЕТОД 2Л. Введение В главе 1 были изучены фундаментальные теоремы линейного программирования. В этой главе, а также в гл. 4, 5, 6 и 7 будут рассмотрены вычислительные методы. Будем говорить, что задача линейного программирования записана в канонической форме, если все ее ограничения (кроне х, ) 0) представляют собой равенства.
Если все ограничения имеют внд неравенств, то задача записана в стандартной форме. Рассмотрим задачу линейного программирования в канонической форме: найти минимум функции прн условиях ~ ам=Ь| (1=1, ..., тп) (т(п), р=~ хз )~ 0 (1 = 1, ..., п). Теорема 1.9 устанавливает, что если существует допустимое решение, то существует базисное допустимое решение. Теорема 1.13 утверждает, что если существует оптимальное решение, то существует базисное оптимальное решение. Таким образом, для получения оптимального решения можно поочередно. выбирать т столбцов нз матрицы А и решать систему из т уравнений с т неизвестными.
Ио такой метод потребует решения примерно ( ) систем уравяеннй, что практически невозможно, даже для небольших значений и. Задачу линейного программирования можно решить за небольшое количество шагов, используя снособхназываемый симплекс-методом.(29). Высокая эффективность снмплексметода помогла распространению лилейного программирования и сделала практически разрешимыми прикладные задачи в промышленности и военном деле. Разберем симплекс-метод на небольшом числовом примере. Рассмотрим задачу линейного программирования: минимизировать з= + +х 45 2, 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
