Ф.П. Васильев - Методы оптимизации (1125241), страница 30
Текст из файла (страница 30)
Из (20) тогда имеем дь(шь) = д(и(тъ)) = 1(х ) — — сс, откуда с Учетом включениЯ гвь Е Иг, й =1, 2,..., полУчим, что д„= — со. Аналогично рассуждая, заключаем, что если д„= — со, то 7; = — ос. Пусть далее 1. > — оо, д„> — со. Возьмем произвольное число г > О. По определению нижней грани найдется точка х, Е Х, такая, что 7; < 7(х,) < < Г +г.
Тогда гв, = ге(х ) Е Иг и из (20) следует, что д, < д(и,) = 1(х ) < 1,+г, т. е. д„< 1, + г. Аналогично, по определению д, существует точка й, для которой д, < д(ге,) < д, + в. Тогда х, = х(иег,) Е Х и 1„< 1(х,) = 7(х(й,)) = =д(ю,) < д, + г, т. е. 1„< д„+г. Следовательно, 1. — г < д, < 1,+г.
В силу произвольности г > 0 отсюда вытекает, что 1, = д, > -со. Наконец, если х, е Х., то ы„ = ш(х.) е И', и в силу вышедоказанного д(гв„) = д(ы(х.)) = 1(х,) = 1„= д,. Это значит, что гв(х,) е Иг. при любом х, е Х„. Аналогично доказывается, что если ю„е Иг„, то х, = х(ш.) е Х„. Отсюда следует, что либо оба множества Х„и Иг, пусты или оба непусты одновременно. Теорема 1 доказана.
П 4. В теории и методах линейного программирования наряду с канонической задачей принято выделять так называемую основную (или стандартную) задачу линейного программирования: Упражнения Рис.'3.2 (с,с ) ьх с я +с х =а з я Рис. ЗА Рис. 3.3 '„.>у 1ОО Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ тогда задачу (15) можно записать в следующем виде у'(х) = (с, х) «ш1, х е Х = (х > О: Ах < Ь, ( — А)х < — 6) = =(х>О Сх~Д, С= — А ' з" — Ь ' (24) Рассуждая также, как при доказательстве теоремы 1, нетрудно установить равносильность задач (15), (24), Как видим, все три формы задач линейного программирования — общая задача (5),(6), каноническая (15), основная (21) — тесно связаны между собой и простыми преобразованиями от одной формы легко перейти к другой.
Поэтому, если мы научимся решать одну нз этих задач, то тем самым будем уметь решать задачу линейного программирования, записанную в любой другой форме. Заметим однако, что изложенные приемы сведения задач (5), (6), (15), (21) к канонической или основной задаче могут привести к чрезмерному увеличению размерности переменных или числа ограничений.
Поэтому методы решения задач линейного программирования обычно разрабатывают для задач (15) или (21), как более простых для исследования, а затем, учитывая указанную связь между задачами (5),(6),(15),(21), модифицируют полученные методы применительно к другим классам задач линейного программирования, стараясь, по возможности, не увеличивать их размерность.
1. Требуется составить наиболее дешевую смесь, содержащую не менее Ь! единиц 4-го вещества, ! =1, 2,..., пт, при условии, что для изготовления смеси имеется и видов продукции, причем в одной единице >что продукта содержится ог единиц Ого вещества, а цена одной единицы >ого продукта равна с! рублей (задача о смесях). Сформулировать зту задачу а виде основной задачи (21). 2.
Задачу >(х)=х +х +х +х — х тзцр, х=(х, х,х, х,х ) еХ=(х >О, х >О, ! 3 3 «а ! 3 3 «з ! 3 х«>0; х'+ ха — хз (1, х +х«+ха =3, х — х +л ) 1, — 1 <х < 1, х ) 1) записать в виде задач (5), (6), (! 5), (2! ). 3. Записать общую задачу (5), (6) линейного программирования в форме основной задачи, доказать ик вквиналентность„ Э 2. аеометрическая интерпретация. Угловые точки 1.
Кратко остановимся на геометрическом смысле задачи линейного про граммирования. Рассмотрим задачу (1.21) при и = 2: х Е Х = (х = (х', х ): х' > О, хз > О, а,.!х'+ азах < 6', « = 1,..., т) Введем множества! Х =(х=(х', х'): х' >О, х'>О) =.В+Я вЂ” неотрицательный квадРант плоскости; (х', х ), Хг = (х = (х', хз); аг,х'+ а,,хз < Ьг)— полуплоскость, образуемая прямой аг,х + а,х = Ь', з = 1,...,та.
Ясно, з ! что множество Х является пересеченйем мчожеств Х„Х„..., Х . Может случиться, что это пересечение пусто (рис. 3.1) — тогда задача (Я() теряет смысл. Если множество Х непусто, то оно, образованное пересечением ко- г $2. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ. УГЛОВЫЕ ТОЧКИ 161 хз 2 Хо с=(с, с ) Х ! аз : О в о х! Х г!! сх +ох =сг, Рис. 3.1 ) нечного числа полуплоскостей, представляет собой выпуклое многоугольное множество, границей которого является ломаная, составленная из отрезков каких-либо координатных осей и прямых аг,х'+ а,,х'= 6', з' = = 1,..., т.
Это многоугольное множество может быть как ограниченным (рис. 3.2) — тогда Х представляет собой выпуклый многоугольник, так и неограниченным (рис. 3.3). Пусть а — какое-либо значение функции у(х) = (с, х) = с' х'+саха. Тогда уравнение с' х' -1- с'х' = сз (2) задает линию уровня функции У(х), соответствующую ее значению ст и на плоскости определяет прямую, перпендикулярную вектору с = (с', сз) ~ О.
При изменении а от — оо до оо прямая (2), смещаясь параллельно самой себе, «зачертит» («заметет») всю плоскость. При этом вектор с — градиент функции У(х) — указывает направление, в котором следует смещать прямую (2), чтобы увеличивать значение функции у(х) = (с, х). Может случиться, что при изменении а от -оо до оо прямая (2) при некотором значении а = у. впервые коснется Х и будет иметь с Х общую точку хч (на рис. 3.2 — 3.5 прямая (2) представлена при ст = а, < У, < аз < сгз). Ясно, что (с, х,) = У, = !п1(с, х), т.
е. х, — решение задачи (1). Возможен случай, когда прямая (2) при первом касании с многоугольником Х будет иметь не одну 4 2. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ. УГЛОВЫЕ ТОЧКИ 1О3 102 Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Рис. 3.3 Рис. 3.6 общую точку с Х, а целую сторону (рис. 3.4, 3.5) — это может случиться, если Х имеет сторону, перпендикулярную вектору с. Если многоугольное множество Х не ограничено, то наряду со случаями, когда при первом касании прямая (2) будет иметь с Х одну общую точку х„ (см.
рис. 3,3) или сторону (рис, 3.5), возможна ситуация, когда прямая (2) при всех а ( — оо < сс < ссс < со) имеет общую точку с Х (рис. 3.6) — тогда 1п1(с, х) = — оо (первого касания прямой (2) с Х нет), т. е. задача (1) не х имеет решения. Из рассмотренных случаев задачи (1) видно, что задача линейного программирования может не иметь ни одного решения (см.
рис. 3.1, 3.6), может иметь лишь одно решение (см. рис. 3.2, 3.3), может иметь бесконечно много решений (см. рис, 3.4, 3.5), множество решений может быть неограниченным (рис. 3.5). Аналогично можно показать, что множество Х в задаче (1.21) при и = 3 является многогранным множеством, и дать геометрическую интерпретацию этой задачи. Предлагаем читателю самостоятельно рассмотреть этот случай, а также исследовать задачу (1,15) при и = 2, 3.
2. На примере рассмотренной выше задачи (1) нетрудно усмотреть, что если задача (1) имеет решение, то среди решений найдется хотя бы одна угловая точка (вершина) многоугольного множества Х, Ниже мы увидим, что это не случайно: и в более общей задаче линейного программирования, оказывается, нижняя грань функции (с, х) на Х достигается в угловой точке множества. О п р е де л е н и е 1. Точка с множества Х называется угловой точкой (вершиной, крайней точкой, экстремальной точкой) множества Х, если представление с=ссс1+(1 — сс)о, при сп о, Е Х и 0<а<1 возможно лишь при с,=о .
Иначе говоря, с — угловая точка множества Х, если она не является внутренней точкой никакого отрезка, принадлежащего множеству Х. Например, угловыми точками многоугольника на плоскости или параллелепипеда в пространстве являются их вершины; все граничные точки шара будут его угловыми точками; при и > 2 замкнутое полупространство или пересечение двух замкнутых полупространств не имеют ни одной угловой точки. В задачах линейного программирования понятие угловой точки играет фундаментальную роль и лежит в основе многих методов решения таких задач. В дальнейшем мы будем подробно исследовать каноническую задачу (1.15).
Поэтому начнем с изучения свойств угловых точек множества Х = (х Е.Е": х > О, Ах = 6),, (3) где А — матрица размера тп х и, А ~0, 6 — вектор из Е". Ниже будет показано, что множество (3), если оно непусто, имеет хотя бы одну угловую точку (см. теорему 4.1). Возникает вопрос, как узнать, будет ли та или иная точка множества (3) угловой точкой? Приведем один достаточно простой алгебраический критерий угловой точки множества (3). Для этого вначале обозначим з'-й столбец матрицы А через А,. и запишем систему уравнении Ах = 6 в следующей эквивалентной форме: А,х'+...
+ А„х" = Ь. (4) Теорема 1. ПустьмножествоХ определено условиями(3), А фо, т = гапдА — ранг мат ридьс А. Для того чтобы точка с = (с',..., и") Е Х была угловой точкой множества Х, необходимо и достаточно, чтобы сУи(ествовали номеРа 2п..., 3'„, 1 < ь < и, 1 = 1,..., т, такие, что А, о" +... + А, ь 6 = 6; ог = О, у ~ у'„1 = 1,..., т, (5) причем столбиы А,..., А линейно независимы. Доказательство. г( е о б х о д и м о с т ь.
Пусть и — угловая точка множества Х. Если с = О, то из условия 0 е Х следует, что 6 = О. Поскольку А ф О, то т = гапдА > 1 и существуют линейно независимые столбцы А,,, А . Отсюда имеем А О+... +А,. 0=0. Для случая с=о соотношения (о) доказаны. Пусть теперь э ф 0 и пусть о",..., ня — все положительные координаты точки с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
