Учебник системный анализ - Антонов

1.'

1,'

;1

1.

1

I

1

I

i

10.5. Метод искусственных переменных

Рассмотрим задачу линейного программирования, в которой огра­

ничения имеют вид АХ::; РО' Если все Ьj";г, О, i= 1,2,... , т, то свободные

векторы, образующие единичную подматрицу, составляют начальный

базис, а соответствующие им переменные - начальное базисное реше­

ние.

В более общем случае, когда ряд неравенств имеет знак «больше

или равно», например, аilХ1+аizX2+... +аjnХn";г, b , i= 1,2, ... , т, для приве­

дения их к стандартной канонической формеi свободные переменные надо вычесть. Тогда расширенная форма задачи имеет вид

.................................................................................

ат\Х1 +ат2Х2 + ... +aтnXn +ОХn+1 + ... -1Хn+т =Ьт'

Свободные переменные {Хn+1' Хn+2" •• , Хn+m} уже нельзяиспользовать

которые не имеют ничего общего с реальной задачей, и должны быть

выведены из базиса как можно скорее. Чтобы гарантировать их быст­

рое выведение после начала итераций для задач максимизации, искус­ ственнымпеременнымвцелевойфункцииприписьmаюточень большиепо

величине отрицательные коэффициенты (-М), где M»c , и=1, 2, ... , n).

В случае решениязадач минимизацииискусственные переменныеi вво­

дят в целевую функцию с большими по величине ПОложительными ко­

эффициентами (+М).

Знаки Вводимых в ограничения искусственных переменных Хn+m+1'

Хn+m+2'"'' X n+m+k должны совпадать со знаками соответствующих сво­

бодных членов. Искусственные переменные образуют начальное ба­

зисное решение. Применив симплекс-метод, решают задачу по выве­

дению из базиса всех искусственных переменных. Если доказано, что

от искусственных переменных избавиться нельзя, то это означает, что

задача не имеет решения, Т.е. ограничения задачи противоречивы.

Рассмотрим пример решения задачи линейного программирования

с использованием метода искусственных переменных.

Требуется минимизировать линейную форму вида miпf (Х) = miп(15х\ +33х2) при ограничениях

322

{3Х\ +2Х2 ~ 6.

6Х1 +Х2 ~ 6.

Х2 ~ 1.

Х1'Х2 ~O.

Вводя свободные переменные Хз, Х4, Xs приходим К расширенной форме

задачи

{3Х\ +2Х2 -Хз : 6.

6х1 +х2 -х4 -6,

x2 -xs =l.

Переменные Хз, Х4, X s образуют недопустимое базисное решение Х36= -6 < О, Х4б= -6 < О, X S6=- 1 < О,

поэтому вводим В ограничения и в целевую функцию искусственные пе­ ременные Х6, Х7, Хв' Получим следующую запись задачи:

miп{15Х1 +33Х2 +МХ6 +МХ7 +Мх8}.

3х\ +2Х2 -Хз +Х6 = 6.

6Х1 + Х2 - Х4 +Х7 = 6,

Х2 - Xs +Х8 = 1.

Очевидно, начальное базисное решение Х6* =6, Х7* = 6'Х8* =1.

Поскольку А6• А7• А8 образуют единичный базис, а все а/О> О, тодля

решения применим метод симплекс-таблиц.

Исходная таблица имеет следующий вид (табл. 10.6).

Первая итерация. Элементы индексной строки вычисляем сле­

1

:1.

,'.

1,

l'

, "'!

(

1

'l'

11 '

' ,1 i

аО2 = L,Cj Xi2 -С2 =2М +lM +lM -33=4М -33;

'ej6

аоз = L,С;Х;З-С3 =-М; а04 =-М; аО$ =-М; а06 =а07=а08=0;

iej,

аоо = fc;x; =6М+6М +lM =13М.

iej,

Поскольку решается задача минимизации, то направлЯЮщий стол­

бецопределяютпонаибольшемуположительномуэлементуиндексной

ющая строка- вторая. Выполним один шаг преобразования1. Разделим

направляющую строку нанаправляющийэлемента11= 6. Умножив пре­

образованную направляющую строку на 3, вЫчтем ее из первой. Тре­

тья строка остается без изменений, поскольку элемент направляюще­

го столбца для нее равен нулю. Затем, умножив преобразованную на­

правляющую строку на (9М-15), вычтем ее из индексной. В результа­

те получим табл. 10.7.

Вторая итерация. Таккак аО2=~M-зо.!.> aOj(j ~2), т.е. являет-

Выполним шаг симплекс-преобразования. Умножив направляющую

, строку на l.!., вычтем ее из первой строки. Затем, умножив направля-

2

, ющуюc~oкyна ~,вычтемееизвторойи,наконец,умноживнаправ-

ляющую строкуна (%М _ зо~), вычтемееиз последней строки. Полу­

Третьяитерация. Поскольку aos =%М- зо~> a Oj (j ~5), тонаправ:

ляющий столбец - As. Направляющая строка - первая, направляющии

элемент а65 -l.!2.. Выполнивочереднойшагсимплекс-преобразования,

выведем из базиса последнюю искусственную переменную Х6 и введем

1

I

I

,1

li

'I!

Четвертая итерация. Обратим внимание, что в этой таблице все

искусственные переменные выведены из базиса. Направляющий стол-

бец- А4,направляющаястрока- первая,направляющийэлемент а14 = ~•

Выполнивещеодиншагсимплекс-преобразования,получимтабл. 10.IЪ.

Таблица 10.10

Поскольку в индексной строке все оценки aO}~ О, то найдено опти-

Искомое значение целевой функции аоо= min z = 53.

линеиного программирования в общем случае, коща имеются ограниче­

ния в виде неравенств сразличными знаками: как«больше илиравно», так

и «меньше или равно».

10.6. Дискретное программирование

Постановка задачи дискретного программирования. Многие

задачи системного анализа, такие как распределение ресурсов, задачи сетевого планирования и управления, календарного планирования, опи­ сываются математическими моделями дискретного программирования.

Рассмотрим общую задачу максимизации.

Найти maxf( Х1' х2,••• , Хn ) (10.10)

при условиях

(10.11)

326

где D - некоторое множество R(n).

Если множество D является конечным или счетным, то условие

(10.12) - это условие дискретности, и данная задача является задачей

дискретного программирования (ЗДП). Чаще всего условие дискретно­

сти разделено по отдельнЫм переменным следующим образом:

Х} Е Dj'j = 1,2, ... , n,

где D - конечное (или счетное) множество.

Е~ли вводится ограничение Х.- целые числа(j = 1,2, ... , n), то при­

ходят К задачам целочисленногоJпрограммирования (ЦП), которое яв-

ляется частным случаем дискретного программирования.

В задачах дискретного программирования область допустимых

решений является невыпуклой и несвязной. Поэтому отыскание реше­

ния таких задач сопряжено со значительнЫми трудностями. В частно­

сти, невозможно применение стандартных приемов, используемых при замене дискретной задачи ее непрерывным аналогом, состоящих в даль­

нейшем окрyrnениинайденногорешениядо ближайшегоцелочисленного.

Например, рассмотрим следующую ЗЛП:

найти mах (ХI-3Х2 +3хз)

Проверка показьmает, что никакое округ.ление компонентэтого плана

не дает допустимого решения, удовлетворяющего ограничениям этой

задачи. ИскомоецелочисленноерешениезадачиХ1опт= 2, Х2опт= 2, ХЗопт= 5.

Таким образом, для решения задачи дискретного программирова­

ния (ЗДП) необходимы специальные методы. Методырешения здп по

принципу подхода к проблеме делят на три группы: 1) методы отсече­

ния илИ отсекающих плоскостей; 2) метод ветвей и границ; 3) методы

случайного поиска и эвристические методы.

Математические модели задач дискретного программирования. По структуре математической модели задачи дискретного про­

граммирования разделяют на следующие классы:

327

1)задачи с неделимостями;

2)экстремальные комбинаторные задачи;

3)задачи на несвязных и на невыпуклых плоскостях;

4)задачи с разрывными целевыми функциями.

Задачи с неделимостями. Математические модели задач с неде­

лимостями основаны на требовании целочисленности переменных {х),

вытекающем из физических условий практических задач.

К таким задачам относится задача об определении оптимальной

Если J = N = (1, 2, ... , n), то задача называется полностью целочис­ ленной, в противном случае, если J *N - частично целочисленной.

Задача о ранце. Одной из наиболее распространенных задач цело­

численного проrpаммирования является так называемая задача о ранце.

Рассмотрим постановку данной задачи. Турист готовится к длитель­

ному переходу в горах. В рюкзаке он может нести rpуз, масса которого

не более w. Этот rpуз может включать в себя n видов предметов, каж­ дый предмет типаj, массой ОО) ,}= 1,2, ... , n. для каждого вида предме­ та турист определяет его ценность EjBO время перехода. Задача зак­

лючается в определении количества предметов каждого типа, которые

он должен положить в рюкзак, чтобы суммарная ценность снаряжения была максимальной.

Обозначим через х] количество предметов j-гo типа в рюкзаке.

Тогда математическая модель задачи такова:

Экстремальные комбинаторные задачи. В данных задачахvне­ обходимо найти экстремум некоторой целевой функции, заданнои на конечном множестве, элементами которого служат перестановки из n

Каждая такая перестанов~~ может быть представлена точкой в n2 -

мерномевклидОВомпространстве илив виде матрицы Хnхn = \\Xij\\.

;=0

329

11

ч

. '!I

I

где Иj ' Иj - ПРОИзвольные целые и неотрицательные числа.

Условие (10.20) означает, что коммивояжер выезжает из каждого

города один раз, а условие (10.21) - что он въезжает один раз в каждый

город.

Если оrpаничить задачу только условиями (10.20) и (10.21), она бу­

дет Эквивалентна задаче о назначениях, план которой не обязан быть

цикличным. Иначе ГОворя, путь коммивояжера при этом можно пред­

ставить как ряд несвязанных подциклов, в то время как его путь в дей­

ствительности состоит из одного цикла.

Покажем, чтодля любого цикла, начинающегося вА можно найти

при XiJ - 1 условие (10.22) выполняется как строгое равенство:

Uj -и j +nX;} =р-(р+l)+n =n-l.

Метод ветвей и границ для задачи целочисленного програм­

мирования. Рассмотрим частично целочисленную задачу ЛП:

минимизировать

Процесспоискаоптимальногорешенияначинаютсрешениянепре­

рывнойзадачиЛП. Еслиполученныйприэтом ОПтимальный план Х не

удовлетворяет условию (10.26), то значение целевой функции ~ =!СХ)

дает нижнюю оценку для искомого решения, Т.е. min z = ~. О О

Пусть некоторая переменная Х;о(1$ iO$ т) не получила в плане

ХОцелочисленного решения. В целочисленном плане значениеХ сле­

/о

330

,дует либо уменьшить, по крайней мере до [Х;о], либо увеличить, по край­

ней мере дО [Х;о]+ 1.

Если rpаницы изменения Х/О заранее не заданы, то их можно вы­ числить, решив для этого две вспомогательные задачи ЛП. Эти задачи состоят в максимизации и минимизацииХ/О при условиях (10.24) и (10.25).

Теперь для каждого фиксированного целочисленного значения ХiO в

найденном отрезке (X;omin' X,"Qma) находят minz, решая задачу ЛП с orpa- ничениями (10.24), (10.25) и с дополнительным оrpаничениеМХ;о$ k/O.

Таким образом, все указанные выше возможности можно пред­ ставить в виде некоторого дерева, в котором вершина О отвечает плану

Хо , а каждая из соединенных с ней вершин отвечает оптимальному

плану следующей задачи: минимизировать z при условиях (10.24), (10.25) и дополнительном условии, что переменной XiO дано значение Х/О:$ k;o,

г~e kl,9 - целое число. Каждой из таких вершин приписывают оценку

~(kj =С.д?; k), которая равнаminz при указанных выше оrpаничениях. Оче­

видно, <;0 $ ~иO, k), для всех k.

Если оптимальные планы полученных задач удовлетворяют усло­

виям целочисленности, то план с минимальной оценкой ~ = ~иo, k) и

будет оптимальным планом исходной задачи. В противном случае воз­ никает необходимость в продолжении ветвления. При этом каждый раз для очередного ветвления выбирают вершину с наименьшей оценкой.

Любой маршрут в" дереве от начальной вершины О до некоторой

вершины определяет допустимую последовательность выбора цело­

численных решений для переменных. Процесс продолжают до тех пор,

пока продолжение ветвления становится невозможным.

, Каждая конечная вершина отвечает некоторому допустимому це­

лочисленному плану. Вершина с минимальной оценкой дает опти­

мальный план.

Рассмотрим алгоритм решения задачи целочисленного проrpамми­

рования. На первом этапе необходимо задать множество 0<0>, опреде­

ляемое условиями (10.24), (10.25). Далее формируются множества

G~k}(v=l, 2, ..., Pk; k=l, 2,...), задаваемые условиями (10.24), (10.25) и

дополнительным условием

где [xjO] - целая часть XjO'

~алее осуществляется вычисление оценок. Для множества 0<0)

оценку ~(O<O») определяют как 1;(G(О) ) = f (Хо), где хО - оптимальный

план непрерывной задачи ЛП.

для множества G~k} оценку ~(G~k}) определяют аналогично:

~(G~k})=f(X~k}),

где Х~k} - оптимальный план задачи с условиями (10.24), (10.25) и с до­

полнительным условием (10.27).

Если множество G~k} оказывается пустым, ему приписывают оценку

~(G~k}) = 00.

На следующем этапе осуществляется нахождение планов. Если план

ХО удовлетворяетусловию целочисленности (10.26), ХО - оптимальный

план задачи. Если Х~k} удовлетворяет условию целочисленности (10.26),

он является оптимальным планом задачи с условиями (10.24), (10.25), (10.27) и некоторым планом исходной задачи (10.23) - (10.26).

Далее выполняют ветвление. Ветвление производят в том случае,

когда план Х~k} не удовлетворяет условию целочисленности (10.26).

Пусть x~~; -однаизнецелочисленныхкомпонентплана,где 1~p~nl'

тогда множество G~k} разбивают на два подмножества:

Укажем некоторые особенности метода ветвей и 'границ для задач

ЦП.

1.Если все коэффициенты С} целевой функции - целые при 1 ~} ~n 1

иравны нулю при} > n l , то оценку ~(G~k}) можно заменить на более

сильную оценку ~1(G~k})=Jf(X~k}f, где ]а[ обозначено наименьшее

целое, но не меньшее, чем а, т.е. округленное до ближайшего целого с избытком.

{.

2. Алгоритм метода в вычислительном отношении представляет собой последовательность задач ЛП, причем конечность алгоритма следует из предполагаемой ограниченности множества G.

3. Из описания алгоритма следует, что в применении метода вет­

вей и границ для полностью целочисленных и для частично цело­

численных задач нет никакой разницы.

Геометрически этот метод можно интерпретировать таким обра­

зом. Гипер-плоскость, определяемая целевой функцией задачи, вдавли-

332

вается внутрь многогранника планов соответствующей задачи ЛП дО

встречи с ближайшей целочисленной точкой этого многогранника.

• Пример применения метода ветвей и границ для решения

задач дискретного программирования. Постановка задачи следующая: минимизировать функцию

min(-x1 +Х2) при ограничениях

{2ХI +llХ2 ~ 38;

Х1 +Х2 ~7;

4xl -5x2 ~5;

- _(40 23\ тогда

Нулевой шаг. Оптимальный план задачи ЛП ХО - 9' 9 )'

имеем ~(Go)= Jf(X o{ = ]-7[ =-7.

Поскольку план Хо не удовлетворяет условию целочисленности,

возьмем его нецелочисленную компоненту Х1 и разобьем множество

G(O) на G~I) и Gil) :

G1(1) ={Х/ХЕ GO, Х1 ~4};

Gil) ={Х/ХЕ GO, Х1 ~5}'

Первый шаг. Решаем две задачи ЛП, заключающиеся в ми­

нимизации исходной задачи по множествам G?) и G~I).

В первом случае минимум достигается при

. 'Второй шаг. Решаем две задачи ЛП, заключающиеся в миними

зацииисходнойзадачипридополнительномограничении Х2 ~ 2 и Х2 ~3 ,

тогда

333

х?)={з~, 2} и ~I(G?»)=]-5~[=-5;

X~2)={2~, 3} и ~I(GY»)=]-5И=-5;

GY) =0,~I(G~2»)=oo.

Производим разветвление множества G?):

G ~З) =О ~(a~з»)=oo

Рис. 10.2. Дереворешенийзадачи целочислеииого программнрования

334

Х~З)=Х~2)={2~, 3} и ~1(G~З»=-5; G:=G~2)=0 и ~1(G~З»=оо.

Дерево решении приведено на рис. 10.2.

Итак получен целочисленный план ХI(З) = {3,2}, причем

~I =miп{~I(G?»);~I(G~З»);1;I(G~З»);1;I(G2»)}=miП{-5; 00; -5; 0о}=-5.

ПЛан Х1(З) = {3,2} - оптимальный, так как

10.7. Нелинейное "рограммирование

Постановки задач нелинейного программирования. Задачи

нелинейного программирования на практике возникают довольно час­

то, например, когда затраты растут непропорционально количеству за­

купленных или произведенных товаров. Хорошо известно, что чем боль­

ше партия закупаемого товара, тем меньше стоимость единицы про­

дукта. Любому покушrrелю знакомо понятие розничных и оптовых цен. Рассмотрим конкретный пример, иллюстрирующий данную ситуацию.

Планирование производства продукции. На действующем

предприятии планируется организовать выпуск новых видов продукции.

Для организации производства необходимо приобретать сырье, сто­ имость которого колеблется в зависимости от спроса. Цены на гото­ вую продукцию предприятия предполагаются стабильными.

Итак, необходимо провести исследования о производстве двух ви­ дов изделий, для которых планируется приобретение сырья, цена кото­ рого зависит от объема закупаемой партии и спроса на рынке на сырье

данного типа. Цены же на продукцию предприятия утверждены с уче­

том реальной обстановки и должны сохраняться неизменными. Объе­ мы производства предстоит определить исходя из анализа сырьевой про­ блемы и ограниченности производственныхресурсов.

Пусть, х.. Х2 -:- объемы производимой продукции l-го и 2-го видов, сl' С2- цена единицы продукции l-го и 2-го видов соответственно. Зат­

раты на приобретение и доставку сырья представляют собой нелиней­

ную функцию, зависящую от объема закупаемого TOBapa,.r.(xl)'~(X2)'

Таким образом, экономическая рентабельность планируемых меропри­ ятий оценивается формулой

335

Предприятие для производства новых видов продукции может вы­ делить лишь часть своих мощностей, что накладывает дополнитель­

HЫ~ ограничения на максимальный объем выпуска новых видов изде­

лии. Устанавливаются также лимиты на стоимость основных фондов (эксплуатация зданий, снабжение электроэнергией, амортизационные от­ числения) в объеме Ь\ и стоимость производственных процессов (вспо­

могательные материалы, заработная плата, накладные расходы и др.) в объеме Ь2• Известно, что изготовление единицы продукции первого вида требует а\\ затрат из основных фондов и а\2 трудовых затрат, а

единицы продукции второго вида затрат в размере а и а соответ-

У 2\ 22

ственно. чет этих факторов приводит к условиям

a l2 x 1 +а22Х2 ~ Ь2'Х1'Х2 ~ О.

Таким образом сформулирована задача, в которой целевая функция

является нелинейной.

Задача распределения удобрений. Будем рассматривать задачу

распределения ограниченного количества удобрений между посевами n различных сельскохозяйственных культур. Предположим, что урожай­

ностьJ;(хj) культуры номера i является нелинейной вогнутой функцией от Х; -~количества BHeceH~ЫX на единицу площади удобрений. Тогда

урожаи ~льтуры н.омера 1 будет равен sj;(x), где Sj - площадь, занятая

культурои номера 1. Будем считать, что суммарная площадь фиксиро­

вана, Т.е.

(10.30)

;=1

где S - общая площадь, отводимая под посевы, заранее заданное чис­

ло. Будем также считать, что продукция должна быть получена во впол­

не определенном ассортименте, т.е. должны иметь место равенства

sJ;(x) .

=л.;,z=2,З,...,n, (10.31)

SI f I (x1)

ЗЗ6

где л. - заданные числа. Введем ограничение

I

(10.32)

Изменяя величиНЫ x ' Sj так, чтобы не нарушить условии (l0.30) -

i

(10.32), мы будем получать различные варианты плана использован~

площадиS. Этипланынеобходимо научиться сравниватьмеждусобои.

Введем критерий следующим образом: обозначим чер~.зР; цену едини­

цы продукта номера i, через q цену единицы удобрении, тогда суммар­

ныйдоход отпродажи продуктазавычетомрасходов напокупку удоб-

рений равен

(10.33)

;=1

X=(XI, .•• ,XJ, S=(sl""'sn),

Требуется найтитакой способ распределения земель, который мак­

симизируетфункционал(l 0.33) приограничениях(l О!О)- (10.32). За­

метим, что величину Х также можем считать искоМОИ.

Формулировка задачи нелинейноГО программирования. Зада­

ча нелинейного программирования в общем виде формулируется сле-

дующим образом.

Найти

(10.34)

равенства и 2) знаки неравенства. Рассмотрим вначале задачу услов­

ной оптимизации с ограничениями в виде равенств.

Ограничения в виде равенств. Начнем изложение метода услов-

нойоптимизации срассмотренияпримерамаксимиЗации функциидвух

переменныхz =!(х,у), где нах иу наложено ограничение, задаваемое

уравнениемg(х,у) = О. Разрешим уравнение g(x,y) = о относительноу.

ЗЗ7

22-4355

:1

i 11

11

'1

: I i 11

I1

и решение представим в виде зависимостиу от х, т.е. у = h(x). Предпо­ ложим, что функции g(x, у) и h(x) дифференцируемы, тогда можно оп­

ределить производную функции h(x). Она будет иметь вид:

Далее представим целевую функцию z как функцию одной незави­

симой переменной z =f(x, у) =f(x, h(x)).

Необходимым условием максимума функции z будет соотношение

dz =df + д! dy =о. dx dx ду dx

Подставляя в данное выражение формулу (10.36) и производя пере­

группировкупараметров, получаем

ду

Выражение, стоящее в скобках, обозначим следующим образом:

Тогда можно отметить, что в точке максимума должны выполняться

соотношения

Первое выражение - это ограничение, которое указано в постанов­ ке задачи, второе следует непосредственно из (10.3 7) путем замены переменных (10.38), и наконец, третье выражение получается из (10.38)

после умножения правой и левой частей на знаменатель выражения и переноса сомножителей в левую часть.

Получить эти три необходимых условия можно также, используя

функцию Лагранжа F(x, у, л)=f(х, у)+лg(х, у), которая представляет собой сумму целевой функции и произведения сомножителя л на функ­ цию ограничения. Коэффициент л называется множителем Лагранжа. Тогда неебходимые условия максимума функцииf(х,у) при наличии ограни'Чений могут быть записаны в виде

338

дF(х,у,Л) =дЛх,у) +лдg(х,у) =0;

дх дх дх

дF(х,у,л) _ дЛх,у)+~ дg(х,у) =0.

ду -ду "'ду ,

дF(х,у,л) =g(x у) =о.

дл '

Совместное решение данной системЫ уравнений относительuнох,у и л позволяет найти все точки, в которых имеет место условныи экст-

+ л(4 - х- у)

Соответс~ующие условия минимума можно записать следующим

образом:

дF =2х-Л =о;

дх

дF = 2у-л =0;

ду

дF =4-х-у=0.

дл