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