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

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

max Хо = Z Cj-JCj-; (7.54)

2] uijXj = Cio, = 1, m\ (7.55)

Xj>0, /=:l,n. (7.56)

Ей соответствует двойственная задача:

т

min = ZI йУь (7.57)

2] Щ^уг > Cj, i=\,n; (7.58)

- Произвольные, i - i,m. (7.59)

Пусть Y={yi, у2,...,Ут) -допустимое базисное (опорное) решение задачи (7.57) - (7.59).

Введем ряд определений.

Базисом опорного плана (решения) У= {уиУ^, -,Ут), или сопряженным базисом, назь1вается произвольная система т линейно независимых векторов {Л^ 4й^} ограничений задачи (7.54) -

(7.56), для которых т ограничений (7.58) выполняются как строгие равенства.

Вектор X- {Xi, Х2,Хп), компоненты которого равны коэффициентам разложения Xjo вектора Ло по векторам сопряженного базиса {Лй Лй}, называется псевдопланом исходной задачи

(7.54) -(7.56).

Псевдоплан Х° = (х?, х ,Хп) будет оптимальным решением исходной задачи, если среди его базисных компонентов нет отрицательных, т. е. х% > Of = 1, т. План У° = (уь у1,Ут), определяющий псевдоплан Х°, является решением двойственной задачи (7.57) -(7.59).

Если среди базисных компонентов псевдоплана Х= (xi, Ха, Хп) имеются отрицательные компоненты, и среди них есть хотя бы одна отрицательная компонента Хго<0, для которой XijO, } = \,п, то целевая функция исходной задачи (7.54) и (7.56) неограничена снизу на множестве ее планов, т. е. задача (7.54) и (7.56) - неразрешима; если для каждой компоненты Хго<0 существует хотя бы один Xij < О, j=l,n, то данный псевдоплан X (хьХг, ...,х„) можно улучшить.

Для улучшения псевдоплана из базиса выводится вектор Ап, причем, если имеется несколько Xrj<0, то из базиса можно вывести любой из векторов Ai, например тот, для которого Xrj имеет минимальное значение. . - - .

Вводится в базис вектор Ai, номер которого одределяется из соотношения

-- min

xrj<:o . (7.60)

приведем алгоритм двойственного симплекс-метода.

1. Представить исходную задачу линейного программирования в канонической форме (7.54) - (7.56).

2. Записать двойственную задачу (7.57) - (7.59).

3. Выбрать сопряженный базис по ограничениям (7.58)--(7.59).

4. Определить коэффициенты разложения небазисных векторов по векторам сопряженного базиса.

5. Записать псевдоплан Х= {xi,Хп).

6. Проверить, имеются ли среди компонентов псевдоплана Х= = {Хи Хп) отрицательные {Xj<:0). Если не имеются, то план Х~

= {xi.....Хп) -оптимальный план исходной задачи (7.54) - (7.56),

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

7. Проверить в строках псевдоплана, соответствующих его отрицательным компонентам (д;го<0), все ли элементы XrjO, }- = !, . Если да, то задача (7.54) - (7.56) - неразрешима. Если нет, выполняют условие п. 8.

8. Выбрать направляющую строку, т. е. определить вектор, выводимый из базиса. Если Xrj<.0 при нескольких г, то из базиса можно вывести любой из векторов Ah.

9. Определить направляющий столбец, т. е. вектор, вводимый в базис Ai. Номер этого столбца / определяется из соотношения

. f Ai 1 Д

Bmiii = mm i--jCrj < О f = --.

I Xrj J Xrl

10. Выполнить симплексные преобразования и условие п. 6.

Пример. Рассмотрим решение задачи о составлении бетона двойственным симплекс-методом при следующей исходной информации: стоимости единицы каждого вида сырья:

ci = 2, С2 = 4, Сз = 3, С4 = 5;

необходимое количество компонентов бетона:

Ь, = 600, bi = 250, Ьз = 150;

содержание t-й компоненты в единице у-го вида сырья а -:

Си = 6; flij = 6; 13 = 0; ац -= 4; Сгг = 0; 022 = 2; огз = S;

24 == 6; Ggi - 4; аз2 = 2; Сзз = 5; аз4 = 0.

Математическая модель задачи (7.12)-(7.13): минимизировать

(2x1 -f 4X2 + Зхз + 5x4)

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

6Х1-Ь6Х2-Ь0хз-Н4х4>600; 4xi-f 2x2-f 5хз-f 0Х4> 150;

Gxi + 2X2 + 5хз-h 6x4> 250; xi >0.X2> 0; Хз > О, x*> 0.

Решение. Запишем модель задачи в канонической форме; максимизировать

(-2X1 - 4X2 ~- Зхз - 5X4)

пр:; зграничениях

6X1+6X2 + 0X3 + 4X4-1X6 = 600; Oxi + 2X2 + 5x3 + 6x4 - Ixs = 250; 4Xi + 2x2 + 5x3 + 0x4 - Ixr = 150;

Xi>0, X20, Хз>0, X4>0, X5>0, ХбО, Х7;з=0.

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

Для выбора сопряженного базиса построим двойственную задачу: минимизировать

Сопряженным является базйо (Л5, Ле, Л7), так как (/i = О, {/2 = 0, (/3 = 0, т. е. удовлетворяют всем ограничениям двойственной задачи. Псевдоплан будет иметь вид

Х= (0,0.0, 0 - 600, -250, -150). Заполним симплекс-таблицу 7.11.

/ итерация

Поскольку Х5 = -600 - наименьший отрицательный компонент псевдоплана, то Xs выводится из числа базисных переменных. Переменная Xi вводится в число базисных переменных, так как вш.п = @i = 2/6.

Выполнив симплекс-преобразования с направляющим элементом Хц, получим симплекс-таблицу 7.12.

II итерация

В псевдоплане только одна отрицательная компонента хе = -250. Поэтому переменную Xg необходимо вывести из псевдоплана, а ввести в псевдоплан переменную Хз, так как втш = 63 = 3/5.

Проделав симплексные преобразования с направляющим элементом Хгз, получим симплекс-таблицу 7.13.

Таблица 7.13

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

Х° = (100, О, 50, 0), Ооо = -350,

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

Таким образом, оптимальное решение задачи о составлении бетона следующее:

для составления бетона необходимо взять 100 ед. сырья первого вида (Xi ~ 100) и 50 ед. сырья третьего вида (хз~ 50), при этом стоимость бетона равна 350 ед.

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

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

В большинстве случаев представляют интерес ответы на такие вопросы: в каком интервале можно менять входные параметры без существенного отклонения от найденного оптимального решения и без значительного нарушения структуры базиса, формирующего оптимальное решение? Изменится ли полученное оптимальное решение, и если да, то каково новое оптимальное решение?

Исследование, позволяющее ответить на эти вопросы, называется анализ модели на чувствительность (или анализ модели при известном оптимальном решении).

Численные данные заключительной симплекс-таблицы позволяют ответить на такие вопросы: остается ли решение оптимальным, если уменьшить удельный вклад в прибыль одной из базисных переменных? К каким последствиям приведет сокращение объема песурсов? Что произойдет, если ввести в рассмотрение новую управляемую переменную?

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

1. Пусть изменяются компоненты вектора Ло= (ю, mo), т. е. изменяются ресурсы.

Как эти изменения повлияют на оптимальное значение целевой функции? В каких случаях найденное оптимальное решение не изменится?

Допустим величина Сго получила некоторое^ приращение ДСго. Соответственно изменится оптимальный план Х°=Х°(Сго-ЬД io) и значение функции цели /max (Х° (Cio-hАош))

Пусть Aflio таковы, что решение Х°=Х°(аго+Д ш) остается допустимым, т. е. Z°0.

Найдем отношение

Afmax (flic) fmax (йго + Айго) ) /шах {Х° (йк) )

---(7.61)

При Afljo-O, получим

Afmax(aio) 6fma!;(aio)

lim = я (7.62)

На основании теоремы двойственности имеем:

/шах (Х°) = Z = Z aioyl (7.63)

3=1 i=i

Подставляя (7.63) в (7.62), получим

..о

5fmax(aio)

а.. = (7.64)

Таким образом, управляемые переменные оптимального решения двойственной задачи У°= {уи -., Ут) определяют вклад каж-

дого i-го ресурса в доход /max при оптимальном решении Х°. Эта величина равна допустимому доходу при увеличении ресурса i-ro вида, т. е. правой части ограничения Gjo, на единицу и условии, что ресурсы используются оптимальным образом. Управляемые переменные оптимального решения У° являются показателями важности соответствующих ресурсов для исследуемой системы управления. Чем больше значение у°,-тем существеннее вклад t-ro ресурса

в максимальный доход /max и тем выгоднее его увеличение.

Если у° = О, то f-й ресурс не является существенным ограничением для системы, так как по условию дополняющей нежесткости

п

йгО - 2] aijX°. > 0. 3=1

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

2. Пусть изменяются коэффициенты целевой функции Cj, / =

= 1,п. Рассмотрим условия, при которых найденное оптимальное решение не изменится. Допустим новое значение коэффициента в целевой функции отличается от старого на 6г, т. е.

с] = Ci + бг.

Пусть / - множество индексов базисных переменных оптимального решения Найдем оценки (симплекс-разности) Д1 после изменения Ci на 6г для двух случаев: Ci - коэффициент при небазисной переменной хи Щ1, и а - коэффициент при базисной переменной Хи 11. Если 11, то

Д] == А.З для всех / Ф I; (7.65)

Д' = Z CiUii - {Ci + 6i) для / = /. (7.66)

Если fe/, TO

Ai = H clan - Cj = 2] CiOij + 6iaij - c, для / g /. (7.67)

Таким образом, для сохранения оптимальности прежнего решения при изменении ci необходимо и достаточно сохранение знаков оценок Д1. для всех небазисных переменных. Поэтому из условия А'О (задача максимизации) можно определить допустимые

изменения 6; коэффициента Си при котором сохраняется прежнее оптимальное решение.

Аналогично можно получить допустимые изменения для всех или нескольких коэффициентов целевой функции. В этом случае новые оценки Aj будут функциями нескольких параметров (6i, 62,Ьт). Решая совместно систему

. Aj (61,62,бг) > О, / е /, (7.68)

получим искомые допустимые изменения коэффициентов целевой функции.

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

Изменение целевой функции в окрестности оптимального реше-

ния имеет вид

i=i 3=1

n dfo dcj m df daio .+ 2- + 1:- (7.69)

3=1 i=l

Если принять, что t=aij, то

= -M,. (7.70)

где i/i и x°-управляемые переменные соответственно оптимал^-гюу решения У° двойственной задачи и оптимального решения Х° исходной задачи.

Условие (7.70) показывает, что скорость изменения оптимального значения /° прямо пропорциональна произведению оптимальных решений исходной и двойственной к ней задач. Если у° и х°

неотрицательны, то положительное приращение Cij вызовет уменьшение целевой функции.

Таким образом, имея оптимальное решение исходной задачи Z°= (х°,-...,х°) и оптимальное решение двойственной к ней задачи

У°= (у°У^). можно исследовать модель задачи на чувствительность. При этом надо помнить, что решение двойственной задачи получается из последней симплекс-таблицы с оптимальным решением исходной задачи по правилу

где Св - вектор коэффициентов при базисных переменных целевой функции исходной задачи; В - оптимальный базис исходной задачи.

Поскольку значение целевой функции /° зависит от управляемых переменных, которые определяются в зависимости от коэффициентов ограничений, то

duij dXj дац dots

В выражениях (7.70) и (7.71) левые части равны, поэтому при оптимальных значениях управляемых переменных х° и у° изменение Xj, tji в окрестности экстремальной точки определяется в зависимости от изменения коэффициентов ограничений c,-j следующим образом:

дац

0 0 ,

о о

7.2. ОПТИМИЗАЦИЯ НА СЕТЯХ

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

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

Сеть является частным случаем графа. Граф - это совокупность точек (узлов, вершин) и линий, соединяющих эти точки. Графом описывают отношения между множествами объектов, которые обладают многими характеристиками. При исследовании задач, описываемых графами, особое значение имеют связи между отдельными точками (объектами) и порядок их соединения.

Все задачи, решаемые с помощью теории графов, делятся на две группы: 1) требуется определить, существуют ли объекты с определенными свойствами и сколько этих объектов; 2) заданы некоторые свойства объектов и требуется построить граф.

Математический граф G -это упорядоченная пара G={V, L), где V - множество вершин (непустое множество), L - множество ребер.

Если ребро принадлежит множеству L, то оно инцидентно вер-, шинам (узлам), которые оно соединяет. Например, ребро tj{tjL) соединяет вершины Vi и Vi2{ViV, ViV). Значит ребро Ij инцидентно вершинам Vi и t),j. Ребра и вершины являются элементами графа.

Графы делятся на ориентированные и неориентированные.

Ориентированный граф - это упорядоченная пара (V, L), 1. е. L - упорядоченное отношение на V. Ребра упорядоченного графа называются дугами. Каждая дуга соединяет две вершины. Вершина, из которой выходит дуга, называется начальной; вершина, в которую входит дуга, называется конечной.

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

Если граф содержит конечное число ребер, он называется конечным.

Граф может иметь подграфы. Граф G=(V, U) называется подграфом G={V,L), если VciV, LciL. Если ребро входит в ту же вершину, из которой выходит, то это ребро образует петлю.

Одной и той же вершине может быть инцидентно несколько ребер. Валентностью (степенью) вершины называется количество инцидентных ей ребер. Две вершины могут соединяться нескольки-

ребрами (отражающими различные характеристики). Количество ребер, соединяющих две вершины, называется кратностью

этой пары вершин. / ч , ,

Последовательность п ребер (дуг) In называется маршру-

том длины п, если существует соответствующая последовательность из fi-4-l вершин Уо, Уь Vn таких, что Ij инцидентно

(Vj-i&Vj), j= I, п. В ориентированном графе - маршрут ориентированный, в неориентированном - неориентированный.

Если начальная вершина маршрута vq совпадает с его конечной вершиной Vn, т. е. Vo=Vn, то маршрут (ориентированный) называется замкнутым, если vo=9Vn - маршрут называется незамкнутым.

Если в маршруте иф1з для всех i и /, 1ф], то маршрут называется цепью. Для ориентированного графа цепь является путем. Таким образом, множество ребер (дуг) образует цепь (путь).

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

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

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

Деревом в неориентированном графе называется связный подграф, не имеющий циклов.

Если все вершины графа принадлежат дереву, то оно называется покрывающим. Если существует путь от вершины vi к каждой другой вершине графа, то ориентированное дерево имеет корень в этой вершине и,-.

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

Сетью называется линейный граф, элементам которого поставлены в соответствие некоторые параметры.

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

Общая линейная экстремальная задача на сети

Пусть имеется некоторый конечный граф G={V, L), каждой вершине которого поставлено в соответствие некоторое число gt, называемое интенсивностью вершины.

Вершины называются источниками, нейтральными вершинами и стоками, если g,>0, giQ и gii соответственно, т. е.

у = У+ и и У ,

где

V+= {i:g,>0}, V-= {i:gi<0}, V = {i: gi = 0). Потоком в сети называется совокупность величин, удовлетворяющих соотношениям:

2 Хц - Z Xji = gi, i e V; (7.73)

Xij-Q, {i,j)L. (7.74)

Соотношение (7.73) физически означает, что поток, выходящий из i-u вершины, равен сумме ее интенсивности и входящего в нее потока.

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

S CijXij, (7.75)

где Сф (i, j)L - функция стоимостей потока. Такой поток называется оптимальным.

Задача (7.73) - (7.75) является представлением задачи линейного программирования на сети и называется задачей об оптимальном потоке (максимальном потоке).

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

Задача формулируется следующим образом: имеется m различных поставщиков (предприятий или пунктов отправления), которые имеют некоторый однородный продукт (изделия). Этот продукт требуется п потребителям, т. е. его нужно отправить в п пунктов назначения, связанных с поставщиками дорогами. Предполагается, что поставщик i{i=l,m) может отгрузить не более ai продукта (груза), потребитель / требует не менее bj продукта (груза). Величины Oi, i=l,m, и bj, на плановом периоде принимаются постоянными. Заданы затраты су на перевозку единицы груза из пункта отправления i в пункт назначения /. Необходимо так составить план перевозок грузов в плановом периоде, чтобы их общая стоимость была минимальной.

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

т п

E-EcijXij , (7.76)

i=l 3=1

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

п

Hxijat, i=\,m; (7.77)

i:xij>bj, i=\,n; (7.78)

Xij0, i - l,m; j = l,n. (7.79)

Задача (7.76) - (7.79) будет иметь решение только в случае, когда ,212