Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 154
Скачиваний: 0
У П Р А Ж Н Е Н И Я |
41 |
купность гиперплоскостей с направляющим вектором с. Опти мальным решением является вершина, принадлежащая опорной гиперплоскости с направляющим вектором с. Оптимальное реше ние не единственно, если гиперплоскость z = сх параллельна одной из гиперплоскостей, пересе кающихся в оптимальной вершине.
Во второй интерпретации задачи линейного программирования рас сматривается m-мерное пространство условий, где Ь представлено векто ром (или точкой). Каждый столбец
матрицы |
А из системы Ах = |
Ь есть |
|
вектор |
с |
т компонентами. |
Допу |
стимое |
решение системы Ах = |
b су |
|
ществует, если точка Ь лежит внутри конечно порожденного конуса, натя
нутого |
на |
векторы а П о с к о л ь к у |
|
пространство |
условий имеет размер |
||
ность |
т , |
то |
в общем случае конус |
натянут на т векторов. Если векторов меньше, чем т, то получаем вырожденный случай. Каждому вектору aj поставим в соответствие стоимость су, оптимальное рещение задачи совпа дает с минимальной по стоимости линейной комбинацией векто ров &j, равной Ь.
Рассмотрим задачу линейного программирования: минимизировать
X i + А х 2 + Ъ х ?
при условиях
Геометрическая интерпретация этой задачи дана на рис. 1.7. Заметим, что оптимальным решением будет xt = 2/3; х2 = 0Г х3 — V3. Если ограничения заменить на неравенства, например ajXj ^ Ь, то задача сводится к отысканию комбинации векторов,, дающей точку, расположенную выше и правее точки Ь.
Упражнения |
|
|
|
|
|
1. Дана т X /г-матрица А = |
[а;Д (т ^ п) |
и та-мерный вектор |
|||
Ь = [&;]. Пусть ац > 0 и bt > |
0 |
(t = 1, |
. . ., |
т; j |
= 1, . . ., п). |
Всегда ли можно найти вектор х, |
такой, |
что Ах |
Ь? Всегда ли |
||
можно найти х, такой, что Ах = |
Ь? Всегда ли можно найти неотри |
||||
цательный вектор х ^ 0, такой, |
что Ах = Ь? Почему? |
||||
42 ГЛ . 1. ОСН ОВНЫ Е п о н я т и я
2. Дана матрица
- 2 1 2 |
со |
- 3 ‘ |
II ◄
1 2 4
Со
, Ь = 1
.3 |
со |
6 6 . |
_ 2 _ |
Покажите, что не существует вектора х, такого, что Ах = Ь.
3.Образуют ли решения системы Ах ^ 0 конус? Выпуклый конус?
4.В § 1.3 приведены четыре теоремы. Нарисуйте четыре круж ка, изображающие эти теоремы. Если для доказательства некото рой теоремы необходимо доказательство другой, то соедините
соответствующие кружки |
стрелками. Проделайте то же самое |
со всеми теоремами этой |
главы. |
5. Докажите лемму Минковского — Фаркаша в следующей формулировке. ‘Система Ах ^ b имеет неотрицательное решение тогда и только тогда, когда из условий я ^ О, я А ^ 0 следует яЬ > 0 .
6 . Дано конечное число точек в плоскости. Рассмотрите выпук
лую оболочку этих точек. Будут ли все данные точки крайними точками выпуклой оболочки? Даны точки (5, 0), (2, 1), (0, 6 )
и(0 , 0 ); найдите их выпуклую оболочку.
7.Будут ли следующие функции, определенные на действитель ной прямой, выпуклыми?
Г с, х > 0 ,
/ (х) = IX |, /(х) = х2, /(*)■={ _ с> х < 0 >
Какие из приведенных функций строго выпуклы? Приведите пример непрерывной функции, не являющейся ни выпуклой, ни вогнутой.
8 . Приведите пример а) конуса, не являющегося выпуклым
множеством; б) выпуклого множества, не являющегося выпуклым конусом.
9.Функция •/ (х) называется квазивыпуклой тогда и только тогда, когда множество {х | / (х) ^ d ) .выпукло для любых дей ствительных значений d. Докажите, что строгий локальный мини мум квазивыпуклой функции является глобальным минимумом.
10.Выпуклая функция определена на отрезке —3 ^ х ^ 4, так что / (—3) = 3 и / (4) = 2. В какой точке функция достигает
максимума? Почему?
УПРАЖНЕНИЯ |
43 |
Нерешенная задача. Рассмотрим задачу линейного программи рования:
минимизировать
Z = сх
при условиях
Ах = Ь,
х > О,
где А — матрица ранга т. В теории линейного программирования говорится о том, что всегда можно отыскать оптимальное решение с не более чем т ненулевыми компонентами. (Предполагается, что задача имеет по крайней мере одно оптимальное решение.) Какой смысл имеет утверждение, что оптимальное решение содер жит не более q ненулевых компонент (q < ш)?
Г Л А В А 2
СИМПЛЕКС-МЕТОД
2Л. Введение
В главе 1 были изучены фундаментальные теоремы линейного программирования. В этой главе, а также в гл. 4, 5, 6 и 7 будут
рассмотрены вычислительные методы. Будем говорить, что задача линейного программирования записана в канонической форме, если все ее ограничения (кроме Xj ^ 0 ) представляют собой равен
ства. Если все ограничения имеют вид неравенств, то задача запи сана в стандартной форме. Рассмотрим задачу линейного програм мирования в канонической форме: найти минимум функции
|
|
П |
|
|
2= 2 Cj X j |
при условиях |
|
|
п |
|
|
^ Iaijfc bi |
( i = 1 ) • • •) т) {т п), |
|
j = i |
J |
|
|
X j > 0 |
(/ = 1, . . . , п ) . |
Теорема 1.9 устанавливает, что если существует допустимое решение, то существует базисное допустимое решение. Теоре ма 1.13 утверждает, что если существует оптимальное решение, то существует базисное оптимальное решение. Таким образом, для получения оптимального решения можно поочередно выбирать т столбцов из матрицы А и решать систему из т уравнений с т
неизвестными. Но такой метод потребует решения примерно ^
систем уравнений, что практически невозможно, даже для неболь ших значений га. Задачу линейного программирования можно решить за небольшое количество шагов, используя способ, назы ваемый симплекс-методом [29]. Высокая эффективность симплексметода помогла распространению линейного программирования и сделала практически разрешимыми прикладные задачи в про мышленности и военном деле.
Разберем симплекс-метод на небольшом числовом примере. Рассмотрим задачу линейного программирования:
минимизировать |
|
z = Xi + х2 + х3 |
(1) |
2.1. ВВЕДЕНИЕ |
45 |
|
при условиях |
|
(2) |
Zi — Х2 + 2 ж3 = 2 , |
||
— |
= 1 > |
(3 ) |
х} > 0 (/ = 1 , 2 , 3). |
|
|
Перепишем условия (1), (2) и (3) следующим образом: |
|
|
z —• Xi — х2 — |
х3 = О, |
(!') |
Xi — х2 + 2 ж3 = 2 , |
( 2' ) |
|
— X i + 2ж 2 — |
ж3 = 1. |
(3') |
Система (1'), (2') и (3') состоит из трех уравнений с четырьмя неизвестными. Применяя метод исключения Гаусса, получим сле дующую систему:
Z |
+ |
Зж3 |
— |
8 , |
(1") |
|
+ |
Зх3 |
= |
5 |
(2 ’') |
|
х2 + |
х3 |
= |
3. |
(3 ") |
Такая система называется диагональной формой относительно неизвестных z, xt и х2. Решение z = 8 , xv = 5, х2 = 3, х3 = О
непосредственно следует из записи в диагональной форме. Заметим, что Xi и х2 называются базисными переменными, а х3 — небазис ной переменной (см. § 1.5).
Так случилось, что в полученном решении xt и хг неотрицатель
ны, т. е. полученное решение является допустимым, a |
z = 8 . |
|
Из уравнения (1") видно, что, если |
увеличивать х3, z будет |
умень |
шаться; можно выразить z через х3 |
непосредственно: z = 8 |
— Зх3. |
Поскольку требуется минимизировать z, увеличим х3, насколько
это возможно. |
Из |
(2") |
и |
(3") видно, |
что |
х3 нельзя увеличивать |
|
неограниченно, |
так |
как |
тогда Xi |
и |
х3 |
станут отрицательными. |
|
В нашем случае Xi |
= |
5 — Зх3, |
х2 = |
3 — х3. Таким образом, |
|||
максимальное значение х3, оставляющее xt и х2неотрицательными, получается из условия
|
* |
/ 5 |
3 |
у |
|
ах:3 = min ( у |
, |
|
|||
5 |
|
5 |
|
Представим теперь систему |
|
Если х3 = -£, то Xi — 5 —3*-g- = 0. |
|||||
в диагональной форме относительно z, |
х2 и х3: |
||||
Z — |
X i |
|
|
= |
3 , |
1 |
|
|
|
|
|
1 |
, |
х2 |
|
|
4^ |
----3 |
Х1 + |
|
|
3 ' |
|
|
|
|
|
|
|