Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 149
Скачиваний: 0
36 |
ГЛ . 1. ОСН ОВНЫ Е п о н я т и я |
Теорема 1.9. Если система линейных уравнений обладает допустимым решением, то она имеет и базисное допустимое решение.
Д о к а з а т е л ь с т в о . Рассмотрим систему
П
j=i
(/' = 1 , • • •> п). |
(2 ) |
Доказательство проведем индукцией по к — числу столбцов aj. При к — 1 теорема очевидна. Допустим, что она справедлива для к <С п, и докажем теорему для к = п. По условию теоремы суще ствует допустимое решение х° = (х\, . . ., х°„) системы (2). Если хоть одно х] = 0 , то мы сразу приходим к случаю к < п — 1 .
Поэтому будем считать, что все х° > 0. Итак,
2 а > , = Ь, ^ > 0 , / = 1 , . . . , п . |
(2 а) |
5=1 |
|
Если система векторов аь . . ., ап линейно независима, то решение х° является базисным и теорема доказана.
Если же векторы at, . . ., а„ линейно зависимы, то существуют такие числа Xj, не все равные нулю, что
2 Xjaj = 0. |
|
(3) |
|
5=1 |
|
|
|
Можно считать, что среди чисел Xj |
есть |
положительные (в про |
|
тивном случае достаточно умножить |
(3) |
на — 1). Среди положи |
|
тельных X, выберем то, при котором |
отношение |
будет мак- |
|
|
|
Х} |
к |
симальным. Не теряя общности, можно считать, |
что это будет —- . |
||
Обозначим его через 0. Очевидно, |
0 > О , |
|
ХТ1 |
поскольку Хп и хп поло |
|||
жительны. Итак, |
|
|
|
0 = max |
> |
0. |
(4) |
5 хз |
хп |
|
|
Умножая (3) на -д- и вычитая полученное равенство из (2а), при ходим к равенству
- г 2 |
( е - д - И “;= -ь - |
<5> |
5=1 |
3 |
|
В силу (4 ) выражение (5) есть представление вектора Ь в виде
неотрицательной линейной комбинации векторов aj, причем
|
1.5. Б А ЗИ С Н Ы Е , ДО П УСТИ М Ы Е И |
О П ТИ М А Л ЬН Ы Е |
Р Е Ш Е Н И Я |
37 |
||||
коэффициент при |
а„ равен нулю. Отсюда |
|
|
|||||
|
|
|
|
4 2 |
(0— |
= |
|
|
|
|
|
|
3= 1 |
1 |
|
|
|
т. |
е. из |
(2 а) |
следует существование допустимого |
решения систе |
||||
мы |
(2) |
при |
к ^ |
п — 1. Остается |
воспользоваться .индуктивным |
|||
предположением. Индукция завершена и теорема доказана, щ
Т еорема 1.10. Совокупность всех допустимых решений |
систе |
|||||
мы (1) есть выпуклое множество х). |
|
|
||||
Д оказательство. |
Пусть |xt |
и ) х2 — произвольные допустимые |
||||
решения, т. е. |
|
|
|
|
|
|
|
|
A x j = |
b , |
X i ^ |
0 ; |
|
|
|
А х 2 = |
Ь , |
х 2 ^ |
0. |
|
Тогда для |
0 < К < |
1, bcj + |
(1 — А,) х2 > 0, поскольку |
каждое |
||
слагаемое |
неотрицательно. Более |
того, |
|
|
||
А [Ях! + (1 — Я) х2] = ЯАх4 + (1 — Я) Ах2= Ь,
т. е. Ях! + (1 — Я) х2 — также допустимое решение. Теорема
доказана. и
Покажем теперь, что базисное допустимое решение соответ ствует крайней точке выпуклого многогранника. В «-мерном
пространстве Е п |
рассмотрим |
выпуклый |
многогранник |
Т: |
|||||
|
Т = |
{х |
| агх ^ Ъи |
i — 1, . . ., |
m), m ^ |
п. |
(6) |
||
Множество Fp ^ |
Т называется р-мерной гранью многогранника Т, |
||||||||
если |
|
|
|
с множеством |
решений системы |
|
|
||
1 ) Fp совпадает |
|
|
|||||||
|
|
|
|
|
Ах = Ь |
|
|
|
|
ранга (п — р), |
получающейся из (6 ) превращением соответствую |
||||||||
щих неравенств |
в равенства; |
|
|
|
|
|
|||
2) любое другое условие из (6 ), выполняющееся на Fp как |
|||||||||
равенство, |
линейно |
зависит |
от системы Ах = Ь. |
называется |
|||||
Грань |
нулевой |
размерности |
многогранника Т |
||||||
вершиной; это соответствует размерности р = 0. Таким образом,
необходимым и достаточным условием существования вершины в Т
1) Поскольку условия задачи линейного программирования всегда можно записать в виде системы линейных уравнений, все переменные которой неотрицательны, то теорему 1.10 можно сформулировать и так: множестворешений задачи линейного •программирования выпукло.— П р и м . р е д .
38 |
ГЛ . 1. ОСН ОВНЫ Е понятия |
является наличие |
в (6) такой подматрицы А, что |
|
г [А] = г [АЬ] = п, Ах = Ь, |
где Ь — соответствующий и-мерный вектор.
л
Теорема 1.11. Пусть Т — выпуклый многогранник в Е п, опре деленный системой (6). Д ля того чтобы точка х £ Т была крайней в Т, необходимо и достаточно, чтобы х была нулъ-мерной гранью Т, т. е. чтобы х было единственным решением системы уравнений
ajX = Ьг, i £ N, | N | = n |
(7) |
ранга п.
Д оказательство.
Достаточность. Пусть х £ Г и х —решение системы (7) ранга п,
которую нам удобно записать в виде Ах = Ь. Покажем, |
что х — |
||||
крайняя точка Т. Допустим, |
что х = ^х1 + |
(1 —Я,)х2, где |
0 < А ,-< |
||
< 1 , a Xi и х2 — различные |
точки |
из Т. |
Тогда в силу определе |
||
ния х и Т |
|
|
|
|
|
b = Ах = А [Хх! -f- (1 —Х)х2] = AAxi + |
(l — X) Ax2^ b |
(0 < |
А,< 1), |
||
и, следовательно, |
|
|
|
|
|
что противоречит предположению о различии точек Xj и х2. Итак х — крайняя [точка в Т.
Необходимость. |
Пусть ;х — крайняя точка |
многогранника |
Т, |
и, следовательно, |
х удовлетворяет системе |
](6 ). Заметим, |
что |
некоторые из соотношений (6) выполняются для х [обязательно как
равенства. Действительно, если |
бы |
aiX<.bi, i |
= l, . . . , m, |
то можно было бы подобрать такой вектор Ах, что
а;(х±Ах)^Ьг, i= 1, ..., m .
1.5. БА ЗИ С Н Ы Е , ДО П УСТИ М Ы Е И О П ТИ М А Л ЬН Ы Е Р Е Ш Е Н И Я |
39 |
Тогда
х = у (х + Ах) + у (х — Ах)’
что противоречило бы предположению о том, что точка х — край няя. Итак, существует множество I, такое, что
aiX = bi, |
г 6 /, |
(о) |
— |
|
|
аг х ^ 6г, i $ I . |
|
|
Число равенств в (8 ) не меньше п. Действительно, если | I |
| = |
|
= к < п, то в соответствующей |
однородной системе уравнений |
|
агх = 0 , |
г 6 I, |
(9) |
число уравнений меньше числа неизвестных. Поэтому система (9)
имеет ненулевое решение х |
0. |
Рассмотрим произвольное число е |
|
и точки |
|
|
|
xt = x -fex |
и |
х2 = х — ех. |
|
Очевидно, |
|
|
|
aiXi = bi, |
aiX2 = |
bi при i £ l , |
|
а при достаточно малом е точки Xj и х2 удовлетворяют неравен
ствам
агХ! < bt, агх2 < Ъг приД $ I.
Таким образом, при малом е точки х4 и х2 различны и принадле жат Т. Из определения xt и х2 следует
-Х = у1 Х 1 + у1 Х 2, х4, х2 6 Т,
что противоречит предположению о том, что х — крайняя точка в Т.
Итак, число равенств в (8 ) не меньше п.
Если бы среди векторов аг, i £ I, были линейно зависимые, то некоторые из равенств в (8 ) были бы следствиями других.
Тогда, |
исключая их из рассмотрения, |
мы пришли бы к случаю |
| / | = |
к < п. Таким образом, точка |
х £ Т удовлетворяет п |
линейно независимым уравнениям |
|
|
|
а(X = bt, i £ I, | / |
| = n. |
Необходимость доказана. и
Теорема 1.12. Если множество допустимых решений задачи линейного программирования есть многогранник, то любое допу
40 |
Г Л . 1. О СН ОВНЫ Е п о н я т и я |
стимое решение представимо в виде выпуклой линейной комбинации базисных допустимых решений.
Д оказательство. Действительно, пусть допустимые решения образуют многогранник. Тогда в силу теоремы 1.11 базисные допустимые решения системы ограничений задачи соответствуют крайним точкам выпуклого множества. Поскольку любая точка многогранника выражается в виде линейной выпуклой комбина ции крайних точек *), любое допустимое решение есть выпуклая линейная комбинация базисных допустимых решений. а
Допустимое решение х* задачи линейного программирования, связанной с минимизацией функции сх, называется оптимальным, если сх* ^ сх для всех допустимых решений х.
Теорема 1.13. Если существует оптимальное решение, то существует базисное оптимальное решение.
Д оказательство. Очевидно, оптимальное решение конечно. По теореме 1.7 линейная функция, являясь вогнутой, достигает глобального минимума в крайней точке выпуклого множества. Теорема 1.11 устанавливает, что крайняя точка соответствует базисному решению.
1.6. Геометрическая интерпретация задачи линейного програм мирования
Пусть дана задача линейного программирования:
найти |
минимум |
|
|||
при |
условиях |
Z = |
сх |
||
Ах Дз Ь, |
|||||
|
|
|
|||
|
|
|
X > |
0 , |
|
где А есть (т X н)-матрица. Для задачи линейного программиро |
|||||
вания известны |
две геометрические интерпретации. В первой |
||||
из |
них |
задача |
линейного программирования рассматривается |
||
в пространстве векторов х, называемом пространством ресурсов;
вторая интерпретация связана с рассмотрением задачи в простран стве точек Ь, называемом пространством условий (см. пример 3 в 1.1). Пространство ресурсов имеет размерность п. Множество решений 2)* в пространстве ресурсов является пересечением т полу пространств агх Дг bt и п полупространств Xj Д: 0. Если z рас-, сматривать как параметр в выражении z = сх, то возникает сово
*) Эта теорема допускает обобщение и на случай, когда множество допустимых решений является неограниченным выпуклым многогранным множеством.— Прим. ред.
2) Множество решений иногда называется также пространством решений.