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

решения i-й задачи. Таким образом, данная задача представляет собой задачу целочисленного линейного программирования, причем перемен­ ная Х/ может принимать только два значения: О и 1.

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

встает перед проектировщиками на следующем этапе проектирования

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

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

будет вы~лядеть следующим образом: необходимо оптимизировать некоторыи функционал при выполнении ограничений на потребление ре­

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

ма в заданном временном интервале.

Будем использовать условия и обозначения, введенные при форму­ лировании предыдущей задачи, Т.е. будем считать заданными требуе­

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

введем обозначения a.ij и ~ij - моменты начала и окончания использо­

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

ся в виде

11.

frij(t)dt = Wij'

•v Если моменты начала и окончания использованияj-го ресурса для

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

ное количество связаны соотношением

11.

fr/t)dt = Wij' i = 1, i, j = и,

о

где (3; = nmx(3ij - момент окончания разработки i-й задачи. Сформулируем ограничения, которые должны иметь место в данной

задаче:

ограничение на потребление ресурсов всем проектом

1

L,r/j(t) ~ R/T), j =и,

;=1

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

номусроку

302

тах.(3; ~T.

{i}

При вьmолнении оговоренныхусловий и обозначений задачараспре­

деления ресурсов между операциями проекта обычно формулируется

следующим образом: имеется комплекс операций, для которых опре­

делены отношения частичного порядка, задаваемые в виде графа G.

Необходимо распределить ресурсы, заданные в количестве R/f), меж­

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

функция достигла своего экстремального значения.

В качестве критерия оптимальности можно использовать

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

Более общий критерий для данной задачи может быть записан в виде

(10.2)

i=\

где <p/(~) - неубывающая функция ~/' пре~ставляющая собой HeKOТO~

рый функционал, имеющий экономическии смысл. Чаще всего данныи

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

ем. В этом случае функционал необходимо минимизировать.

Задача (10.1) характерна для проектирования технических систем

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

вания. При разработке автоматизированных систем существенными

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

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

задач целесообразно пользоваться критерием (10.2).

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

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

транспортную задачу. В некоторых пунктах а\, а2,.. ·, аn находятСЯ

склады, в которых хранятся товары в количествах Х\, Х2,···, ХN соот­

ветственно. В пунктах ы' Ь2,... , Ьm находятся потребители, которым

необходимо поставить эти товары в количествах, не меньших, чем УI'

У2,••• , Уmсоответственно. Обозначимчерез Cij стоимость перевозки еди­ ницы груза из пункта а/ в пунктЬ/ Xij - количество товара, перевозимо­ го из пункта а/в пункт bj' Для того, чтобы удовлетворить запросы по­

требителей, необходимо, чтобы выполнялась система неравенств

L,X/j ~Yj,j=l, т.

303

С другой стороны, необходимо учитывать, что с i-гo склада нельзя вывезти больше продукта, чем там имеется. Следовательно, должна

выполняться еще одна система

! I

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

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

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

;j

Таким образом, paccMorpeHbl задачи, математическая формули­

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

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

мы некоторых переменных. Рассмотрим подходы к решению такого типа

задач.

10.2. Задача линейного программирования

Постановка задачи линейного программирования. Задачи ли­ нейного программирования (ЗЛП) - простейший тип оптимизационных задач. Постановка данной задачи выглядит следующим образом.

Имеется множество переменных Х = (Х\, х2,... , Х). Целевая функ­ ция линейно зависит от управляемых параметров:

;=1

Имеются ограничения, которые представляют собой линейные фор-

мы:

Задача линейного программирования формулируется так: определить максимум линейной формы

(10.3)

304

ЗадачулинейноГО программированияудобно представлять в вектор­

ной форме, тогда она будет выглядеть следующим образом:

найти тах F(x) = тах (СТх)

при условии АХ$; ро; X~ О,

Р.~[ J-т-мерныйвеrropсвободныхчленовОI]>авичений;

матрица А размером (т х n) -vматрица, составленная из коэффициен­

тов всех линейных ограничении:

Простые ЗЛП допускают геометрическую интерпретацию, позво-

ляющую непосредственно из граФика получитьрешение и проИЛЛЮСТРИ-

poвarьидеюрешенияболеесложныхзадачлинейноГОпрограммирования.

305

20-4355

При записи задачи линейного программирования в стандартной или канонической форме число линейно независимых уравнений, как прави­ ло, меньше числа переменных (на практике всегда т < n, где т - число уравнений). Orметим некоторые свойства, касающиеся системы огра­ ничений:

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

никакие из них не являются следствием остальных;

2) если число независимых уравнений больше числа перемен~ных,

то такая система не имеет решения и называется несовместимои;

3)если число независимых уравнений равно числу переменных, то

такая система имеет единственное решение, которое либо оптималь­

но, если все компоненты положительны, либо недопустимо, если хотя бы одна из компонент Otpицательна;

4)если удается найти множество неOtpицательных~наченийХ= (ХL' Х2'••. ' Х.), которое является решением системы т линеиных уравнении

сn+m неизвестными, то такое решение называют базисным, а ненуле­

вые переменные - базисными переменными.

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

двухмерную задачу линейного программирования. Пусть tpебуется найти максимум линейной формы

max:F(x"x2) = тах:(х, +2х2)

при условии

Х, +Х2 ~120, O~ Х, ~ 100,

O~ Х2 ~ 75.

Изобразим область, описываемую совокупностью ограничений на плоскости х,ОХ2 (рис. 10.1). Переменныех, ИХ2 неоtpицательные, по­ этому множество точек (Х\' х2), являющихся возможными решениями задачи, находятся в 1 квадранте. Заменим знак в Х\ + Х2 :5: 120 на знак равенства, получим уравнение прямой: Х\ +Х2 = 120. Эта прямая делит плоскость на две полуплоскости. Все точки одной полуплоскости удов­ летворяют неравенству Х, +Х2 > 120, другой - неравенству Х\ + Х2 < 120.

ПоCtpоив аналогичные прямые х, =100 и Х2 = 75, получим много­ угольник, множество точек которого (Х\, Х2) удовлетворяет всем нера­

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

собой область допустимых решений D.

Из множества точек (Х" Х2) многоугольника необходимо выбрать

такую, в которой функция F(x" Х2) = (Х, + 2х2) принимает максимальное

307

i

I

11

I I

Рис. 10.1. Геометрическая иитерпретациязадачилииейногопрограммирования

значен~е. Для некоторого Фиксированного значенияF * линейная функ­

ция F (X 1, Х2) = (Х1 + 2х2) представляет собой прямую линию. Задава­

ясьразличными значениями F*, получимсемейство параллельныхпря­

мых. Увеличениезначенийлинейной функциисоответствуетперемеще­

нию прямой параллельно самой себе вверх. Следовательно, как видно

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

множестве точек соответствует прямой, проходящей через точку z пе­

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

симплекс-методом

Метод полного Исключения. Перейдем к Изложению методов

решения задачлинейного программирования. Рассмотримвначалеодин из вспомогательных методов, ИЛЛюстрирующий Возможность преобра­

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

СОCПffiЛенноиизпараметровуравненииограничений, кединичномувиду.

Переобозначим свободные коэффициенты ограничений а =Ь

]о f

308

Пусть имеется система ограничений в виде

L,ajjXj =аjO' j =1, т.

;=1

Перепишемданную систему уравнений в матричной форме: АХ=Ао,

и А = [А, Ао], где Ар - расширенная матрица.

Методполногоисключениясостоитизконечногочислаоднотипных

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

Метод основан на следующих двух операциях.

Одну из строк расширенной матрицы умножают на число, отлич­

ное ОТ нуля.

Из каждой строки расширенной матрицы (Ар) вычитают данную строку. Каждое такое преобразование называется преобразованием Гаусса. В результате получаем новую систему линейных уравнений, эквивалентную исходной.

Рассмотрим более подробно метод полного исключения.

1. Среди элементов матрицы А выбирают произвольный элемент, отличный от нуля. Этот элемент называют направляющим элементом шага. Строку и столбец, содержащие направляющий элемент, называ­ ют направляющей строкой и направляющим столбцом данного преоб­

разования.

2. Все элементы направляющей строки расширенной матрицы (Ар) делят на направляющий элемент. В результате получают направляю­ щую строку с направляющим элементом, равным единице. Далее из каждой строки матрицы А вычитают новую направляющую строку, умноженную на элемент, который расположен на пересечении сроки и направляющего столбца. Итак, пусть исходная система уравнении имеет

вид

{аllХ\ +а\2Х2 + ... +а\nхn =а\о;

~~:~:.+.~~~~.~:::~.~~:~:.;.a w;

аm\х\ +аm2Х2 + ... +аmnхn -аmо·

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

стве направляющего столбца второй столбец, тогда направляющий эле­ мент будет Х2 (коэффициент при нем равен а22). Разделим направляю­ щую строку на этот коэффициент и перепишем вновь полученную сис­

тему ограничений:

аl\Х\ +а\2Х2 + ... +а\.х. =а\О;

Далее умножаем направляющую строку поочередно на элементы,

стоящие в направляющем столбце преобразуемого уравнения, и резуль­ тат вычитаем из соответствующего уравнения. Иными словами, вна­ чале умножим направляющую строку на а\2 и вычтем полученный ре­

зультат из первого уравнения. Далее направляющую строку умножим

на аЗ2 и вычтем из третьего уравнения и т.д. до последнего т-го урав­

нения. Получим новую систему:

Матрицу, в которую преобразовалась расширенная матрица А пос-

р

ле первого шага, обозначим А~\). В полученной матрице все элементы

направляющего столбца, отличные от направляющего элемента, стали равными нулю. Совокупность элементов первых n столбцов матрицы Ар' лежащих вне направляющей строки и столбца предьщущего шага,

называют главной частью матрицы А(\) данного преобразования. На­

правляющийэлементвторогошагавыбираютсрединенулевыхэлемен-

тов главной части матрицы A~\>' полученной после проведенного пре­

образования.

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

шагу. Последовательность действий продолжается до тех пор, пока

имеется возможность выбора направляющего элемента. Если послеk-

го шага главная часть матрицы A~k) не содержит ни одного элемента

или содержит только нулевые элементыI' то процесс исключения пере­

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

можетоказаться[уравнений, [~т. Пустьэтопервыепопорядку[ урав­

нений тогда система уравнений может быть записана в виде

}=\

Примем, что i-й направляющей строке соответствует i-й направляю-

•

(1) ~ (1)

Следовательно, (10.6) можно записать в виде Х; =а/о - "-'а/} Х)' причем

)=1+\

переменные Х/ являются базисными, а переменные Ха (s = [+ 1, ... , n) -

небазисными.

Пример применения метода полного исключения. Рассмот-

рим пример применения метода полного исключения Гаусса для иссле-

дованиясистемыуравнений

{Х\ +2Х2 +хз +Х4 =3;

2х\ +Х2 +хз +3Х4 =3;

4х\ +5Х2 +3хз +5Х4 =9.

Расширенная матрица имеет вид

12113

2 1 1 3 3

Ар = 4 5 3 5 9

~А2 Аз А4 Ао

Первый шаг. В качестве первого направляющегоэлемента возьмем

а11=1. Умножив первую строку матрицы А на 2, вычтем результат из второго уравнения и, умножив на 4, вычтем результат из третьего урав-

нения;получим

311

·11

·1' ,

1,11 '1

1:

'.1

111

1:

!!1

!)

1 :

I

11

1

1

1, l'

!I,

I!, '

11

.11.

11"

11'

,··1

1. l'

Второй шаг. ПОскольку главная часть маtpицы А(\) содержит от­

ЛИчные от нуля элементы, ПРОДОЛЖИМ процесс исклю~ения. Выберем

элемент a~~= -3 в качестве направляющего элемента на втором шаге

преобразования. Разделим вторую С1року на-3, получим

Далее УМНОжим вторую ctpoкy на 2 и вычтем результат из первой

Сtpоки, УМножим вторую строку на -3, результат вычтем из tpетьей

заканчивается. Исследуем матрицу А(2). Поскольку tpетья ctpoKa со-

держит только нулевые элементы, это свидетельствует о том, что на­

чальныIe уравнения были зависимыми, и, следовательно, она может

быть отброшена. Тогда Эквивалентная маtpица системы уравнений

будет Выглядеть следующим образом:

Теперь можно записать базисное решение

Х\ =1; Х2 =1; Хз =О; Х4 =О, а также соответствующее общее решение

312

где аз, а4 - произвольные скаляры.

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

1 О О

О 1 О

где е\ = О ; е2 = О ; еm = - единичный базис, элементы alO~ О для

О

О О 1

всех i = 1,2, ... , m.

Будем применять метод полного исключения к расширенной мат­ рице ограничений. Выбираем направляющий элемент alJ на данной ите­ рации. В результате преобразования Гаусса, методика которого была

только что описана, получим новые значения коэффициентов:

если 1:1= i, 1= 1,2, ... , m.

Выясним условия, при которых новое базисное решение будет до-

пустимым, т.е. a~~+\) > О для всех 1. По предположению, аю~ О, тогда

а/}

Если a~k) < О, то очевидно, a,(~+\) > О , так как a;~) > О, a/~k) > о.

условии atk ) > о.

:,

,,', 1

,11'

,",1

,1'1 i 1

""

li

I

I

11,1

ii 1.

,1

·11'

1 !

меняется соответствующее значение коэффициента целевой функции.

ВместокоэффициентаСn+1 соответствующего старой базиснойперемен­

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

при переменной, вводимой в базис.

Если направляющий элемент a/j' то переход от данной таблицы к

следующей осуществляется с использованием следующих правил. 1. для всех элементов направляющей с1рОКИ

(k) a(k+\) = a jt

где k - номер шага (k = 1, 2, ... ); i - номер направляющей С1роки;j­

номер направляющего столбца; f = о, т+n , Т.е. все элементы направ­

ляющей CtpОКИ делим на направляющий элемент, в итоге направляю-

щий элемент стал равным единице; al~~+1) =1.

2. Внаправляющемстолбценеобходимополучить a~jk+\) = о,длявсех r =1, т, r"# i, при a(.k+\) =1, Т.е. в направляющем столбце должны быть

V

все нули кроме направляющего элемента, которыиv равен еДИнице.

для всех остальных элементов, включая индексную с1рoку, произ­

водим вычисления

a;j

Симплексные преобразования повторяют до тех пор, пока не реа­

лизуется один из двух Возможных исходов:

а) все a ot ~0- это условие оптимальности базиса последней таб­

mщы;

б) найдется такой элемент аО}< о, при котором все элементы стол­

бцаarj::; о,- этопризнакнеограниченностицелевой функциина множе­

стве допустимых решений.

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

СМО1рим задачу линейного программирования в следующем виде:

найти максимумлинейной формы 4х\+ 3Х2при ограничениях

2

Х\ ~ 4000, Х2 ~ 6000, Х\ +-3Х2 ~ 6000, Х\'Х2 ~ О.

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

иметь вид

4х\ +3Х2 +Охз +ОХ4 +OXs ~ тах.;

lх\ +ОХ2 +lхз +ОХ4 +OXs =4000;

Ох\ +IХ2 +Охз +IХ4 +OXs =6000;

Составим исходную симплекс-таблицу (табл. 10.2).

На данном этапе в качестве направляющего столбца выбираем

1

Так как аоз =-2 < о, то направляющий столбец Аз, направляющая

строка- вторая, направляющийэлемент а23 = ~. Выполнимочередной

шаг преобразования, получим еще однутаблиtу (табл. 10.5).

Хзо = 2000. Искомое значение целевой функцииpa~HO4 Х,+ 3;:=26000:

10.4. Двойственная задача линейного

программирования

Структура и свойства двойственной задачи. Почти всякую злп

можно рассматривать как экономическую задачу о распределении ре­

сурсов Ь" Ь2,••• , Ьm между различными потребителями, например, меж-

ду некоторыми технологическими процессами А"А2,••• ,А•. Любое до­

пустимое решение ЗЛП Хl' Х2,.•• , Х. дает конкретное распределение,

указывающее ту долю каждого из ресурсов, которая должна быть ис­

пользована при осуществлении соответствующего технологического

процесса.

Рассмотрим пример. Завод производит три вида продукции Х" Х2, ХЗ' каждый из которых требует затрат времени на обработку на токар­

ном, фрезерном и сверлильном станках. Количество машинного времени

для каждого из станков ограниченно. Пусть С" С2' СЗ- прибьmь от реа­ лизации единицы соответствующего вида продукции. Требуется опре­ делить, какое количество каждого вида продукции необходимо произ­ водить в течение заданного интервала времени, чтобы получить мак­ симальную прибыль.

Формально задача записывается так: найти

max (с,х, +С2Х2 +СЗХЗ)

х1 ,х2,хз

при ограничениях

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

ках (j = 1,2,3); ы' Ь2, Ьз - ресурс машинного времени соответственно

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

Рассмотрим далее задачу в несколько иной постановке. Обозначим

через И" И2' ИЗ цену единицы времени работы на токарном, фрезер­

ном и сверлильном станках соответственно, тогда а,\ И,+а2, И2+аз, ИЗ

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

первого вида, а'2И,+а22И2+аЗ2ИЗ - расходы на изготовление единицы продукции второго вида, а\зИ\+а2зИ2+аззИЗ - расходы на изготовление

единицы продукции третьего вида.

;1

"1

ДЛЯ величин расходов Выполняются следующие соотношения:

а\3И\ + а23И2 +аззхз ~ Сз'

Учитывая, что Ь\, Ь2, Ьз - использованный ресурс машинного вре­

мени для каждого из станков, тоща Ь\И\+Ь2И2+ЬзИз - суммарные рас­

ходы на производство.

Требуется найтитакие И\, И2, ИЗ' удовлетворяющиеусловиям(10.7),

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

Таким образом, целевую функцию можно записать в виде

причем И\, И2, Из~ О.

Задачу (10.8) с ограничениями (10.7) называют двойственной зада­

чей по отношению к прямой, сформулированной ранее.

~оотно~ение прямой и двойственной задач. Между прямой и

двоиственнои задачами имеет место взаимно однозначное отношение.

Имея прямую задачу, всеща можно перейти к двойственной и наобо­

рот. Данное отношение находит выражение в виде следующих правил:

1) если прямая за~ача является задачей максимизации, то двой­

ственная будет задачеи минимизации и наоборот;

2)коэффициенты целевой функции прямой задачи С\, С2,••• , с стано­

вятся свободными членами ограничений двойственной задачи;n

3)свободные члены ограничений прямой задачи Ь\, Ь2,••• , Ь стано­

вятся коэффициентами целевой функции двойственной задачи;т

4)матрицуограничений двойственной задачи получаюттранспони­

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

5)знаки неравенств в ограничениях изменяются на обратные'

6)чи:лоограничений прямой задачиравночислупеременных~ой­

ственнои задачи, а число ограничений двойственной задачи равно чис­

лу переменных прямой задачи.

Переменные Ир И2,·•• , Иm двойственной задачи называют «тене­

выми ценами». Двойс~венную задачу выгоднее решать, чем исходную

прямую, если в ПРЯМОИ задаче при маломколичестве переменных (т > n)

имеется большое количество ограничений.

Запишем обе задачи в матричном виде.

Прямая задача. Найти тахЛХ) = тахСТ Х при АХ ~ Ао; Х ~ О.

Двойственная задача. Найти miпg(й) = А;Й при АТО ~ С; й ~ О.

320

Связь между оптимальными решениями прямой и двойственной

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