WWW.NEW.Z-PDF.RU
БИБЛИОТЕКА  БЕСПЛАТНЫХ  МАТЕРИАЛОВ - Онлайн ресурсы
 

«МЕТОДЫ ОПТИМИЗАЦИИ. НАЧАЛЬНЫЙ КУРС ЧАСТЬ 2 Симплекс-метод и смежные вопросы, элементы теории двойственности, многокритериальная оптимизация Рекомендовано редакционно-издательским ...»

Кафедра ’’Прикладная математика-1”

И.Х. Сигал, А.П. Иванова

МЕТОДЫ ОПТИМИЗАЦИИ .

НАЧАЛЬНЫЙ КУРС

ЧАСТЬ 2

Симплекс-метод и смежные вопросы,

элементы теории двойственности,

многокритериальная оптимизация

Рекомендовано редакционно-издательским

советом университета в качестве курса лекций

для студентов специальности

’’Прикладная математика и информатика”

Москва - 2006

УДК 519.85

С 34

Сигал И.Х., Иванова А.П. Методы оптимизации. Началь­ ный курс. -- Курс лекций по дисциплине ’’Методы оптимиза­ ции”. Часть 2. Симплекс-метод и смежные вопросы, элементы теории двойственности, многокритериальная оптимизация. М.: МИИТ, 2006. - 104 с .

Курс лекций составлен на основании лекционных курсов, лабораторных и практических занятий по методам оптими­ зации, проводимых авторами со студентами, обучающимися по специальностям ’’Прикладная математика и информатика”, ’’Программное обеспечение” и др. в Московском государствен­ ном университете путей сообщения (МИИТе). Настоящий курс лекций содержит теоретический материал и большое количе­ ство подробно разобранных примеров, также приведены реше­ ния некоторых основных примеров с использованием пакета Maple® .

Для удобства ссылок в частях 1 и 2 настоящего курса лекций нумерация параграфов, формул, таблиц и рисунков сквозная .

Р ецензенты : д о к т о р тех н и ч е ски х наук, проф ессор кафедры ’’ЭВМ” МИИТа Барский А.Б .

кандидат физико-математических наук, старший научный сотрудник ВЦ РАН Голиков А.И .

©Московский государственный университет путей сообщения (МИИТ), 2006 Содержание П редисловие 5 11 С имплекс-м етод дл я реш ения задачи линей­ ного программирования 7

11.1 Построение начального базисного решения и переход к следующему б а з и с у

11.2 Условие оптимальности в задаче линейного п рограм м и рован и я

11.3 Основные шаги симплекс-алгоритма (в зада­ че на минимум)

12 М етод искусственного базиса 24 13' Задача со смеш анны ми ограничениями 31 14 Основы теории двойственности в математи­ ческом программировании 43

14.1 Теорема К уна-Т аккера о седловой точке..

–  –  –

Настоящий курс лекций составлен на основании лекцион­ ных курсов, лабораторных и практических занятий по ме­ тодам оптимизации, проводимых авторами со студентами, обучающимися по специальностям ’’П рикладная матема­ тика и информатика”, ’’Программное обеспечение” и др. в Московском государственном университете путей сообще­ ния (МИИТе) .

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

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

Авторами задуман цикл лекций по методам оптимиза­ ции, настоящее издание является вторым из этого цикла .

Это издание является продолжением первой части кур­ са [56]. В нем сохранен способ изложения, принятый в пер­ вой части. При этом наибольшее внимание уделяется алго­ ритмическим аспектам. Рассмотрены три основные темы, указанные в названии: линейное программирование, осно­ вы теории двойственности и многокритериальная оптими­ зация. Д л я удобства ссылок в частях 1 и 2 настоящего курса лекций нумерация параграфов, формул, таблиц и рисунков сквозная .

Авторы полагают, что настоящее пособие совместно с первой частью и выпущенной ранее их книгой ’’Введение в прикладное дискретное программирование: модели и вы­ числительные алгоритмы”, могут составить основу мате­ матического образования по курсу ’’Методы оптимизации” .

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

Авторы вы раж аю т благодарность рецензентам доктору технических наук, профессору кафедры ’’ЭВМ ” М ИИТа А.Б. Барскому и старшему научному сотруднику ВЦ РАН, кандидату физико-математических наук А.И. Голикову за работу по рецензированию курса лекций .

Авторы будут признательны всем, кто пожелает выска­ зать свои пожелания и замечания, которые можно направ­ л ять по адресу: 127994, г. Москва, Образцова, 15, МИИТ, каф. ’’П рикладная математика-1” .

–  –  –

Иными словами, получен новый базис А 2,, А т+1, для этого выполнен один шаг по схеме Жордана-Гаусса .

В базис можно включить вектор А к — т + 1, т + 2,...

, п, у которого имеются положительные компоненты:

x ifk 0. Если окажется, что таких компонент нет, то век­ тор Ak включить в базис невозможно .

Таким образом, описан процесс, который позволяет по­ следовательно, имея начальное базисное решение, перейти к следующему, применяя схему Ж ордана-Гаусса. По этой схеме можно построить последовательность базисных ре­ шений. При этом необходимо ответить на два вопроса: ка­ кой вектор включается в базис и как узнать, что получен­ ное базисное решение является оптимальным .

П ример 1. Рассмотрим следующую задачу .

Построить опорный план для задачи

–  –  –

Теперь систему можно записать в векторной форме:

Очевидно, что первые три вектора А \, А 2, А з образу­ ют базис, следовательно, переменные x i, x 2, x 3 - базис­ ные, а переменные х 4,х$,хб - свободные. П олагая сво­ бодные переменные равными нулю, получим начальное базисное решение (опорный план): Х 0 = (6, 4, 3, 0, 0, 0), z(Xo) — 12 + 4 — 9 = 7. Этому опорному плану соответ­ ствует разложение

6Л Х+ 4 А 2 + ЗЛ3 — Ад. (43)

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

Выпишем разложение вектора А 4 по базисным векторам

A i, А 2, А 3:

Ai -j- 2 А 2 + ЗА3 = A 4. (44) У множая (44) на в 0 и вычитая из (43), получим

–  –  –

Д ля исключения какого-нибудь вектора из разложения (45) определяем в0 = m in(6/ l, 4 /2,3 /3 ) = 1.

Подставим значение в0 = 1 в (45) и исключим из разложения век­ тор А3, в результате получим разложение вектора Aq по векторам нового базиса А \, А 2, А 4:

–  –  –

которому соответствует опорный план X i = (5, 2, 0,1,0, 0), z (X {) = 10 + 2 - 1 = 11 .

Теперь вместо вектора Л 4 возьмем вектор А 5, имеющий разложение в первоначальном базисе

–  –  –

Из этого разложения ни при каком в 0 нельзя исклю­ чить ни один из векторов .

П лан Х 2 = ( 6 + 9,4 + 29, 3 + 4в, 0, в, 0), где 9 0, не явл я­ ется опорным, так как содержит четыре положительные компоненты и соответствует внутренней точке многогран­ ника решений. Подставим этот план в целевую функцию, получим z ( X 2) — 7 — 79. Выбирая значение в 0 сколь угодно большим, можно получить сколь угодно малое зна­ чение целевой функции. Последнее означает, что целевая функция не ограничена снизу на многограннике решений .

11.2 Условие оптимальности в задаче линейного программирования Пусть в задаче линейного программирования множество допустимых решений непусто и все опорные планы невы­ рождены. Д л я начального опорного плана Хо (х\ = Ь\,х 2 — Ъ..., х т = Ьт, 0,..., 0), \/Xi 0, имеем 2,

–  –  –

2. Нахождение начального опорного плана .

3. Исследование опорного плана на оптимальность:

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

3.2) если для всех векторов Aj верно Zj — Cj 0, то задача решена;

3.3) если Zj — Cj 0 хотя бы для одного вектора Aj, то из условия максимизации 9(zj — Cj) по всем таким Aj находится в и вектор A j0, который вводится в ба­ зис, т а x d ( z j — Cj) — 6 (zj0 — c,j0), формируется новый з опорный план и выполняется переход к п.З .

Все вычисления удобно вести в виде симплексной таб­ лицы (симплекс-таблицы), содержащей (га + 1) строку, структура которой видна из рассматриваемых далее при­ меров .

П рим ер 2. Требуется найти минимальное значение ли­ нейной функции

–  –  –

где Единичные векторы А 4, А 5 и Л6 выберем за базис началь­ ного опорного плана, свободные неизвестные х х, х 2, х 3 при­ равниваем нулю. В результате получим начальный опор­ ный план Х 0 = (0, 0, 0, 5, 3,1) .

Составим первую симплексную таблицу (см. табл. 8.1) и вычислим значение целевой функции z ( X о) и оценок Zj — Cj, которые запишем в таблицу в последней стро­ ке: z ( X о) = cgAo = О, Z\ — C(,Ai = 0, z2 = сбА 2 = О, 2з = СбАз = 0. Значение z(Xo) = 0 записываем в столбце Д о, а значения zj —Cj в столбцах Aj соответственно .

–  –  –

Д л я векторов базиса оценки Zj —Cj равны нулю. Н ачаль­ ный опорный план не является оптимальным, так как сре­ ди полученных оценок есть две положительные: z2 —с2 = 1, ~з — сз = 3. Включим в базис вектор, которому соответ­ ствует m a x 6 0 j(zj —Cj) 0. Среди коэффициентов разло­ ж ения векторов А 2 и А 3 по базису есть положительные, значит ( 02 0 и #оз 0, которые исключают из базиса хо­ тя бы один из векторов, существуют. Найдем их: в02 = §, #03 = m in (|, Максимум из #02(^2 - с2) = § • 1 и #оз(23 — с3) = | • 3 равен |, следовательно, разрешающим элементом является число 2, стоящее на пересечении пер­ вой строки и второго столбца. Исключаем из базиса вектор A 4 и вводим в базис вектор А 2, делая один ш аг по схеме Ж ордана-Гаусса .

Вычисления запишем во вторую симплекс-таблицу (см .

табл. 8.2) .

В табл. 8.2 получен второй опорный план Х \ = (О, §, 0, 0, у, 6), которому соответствует значение целевой функции z ( X 1) = —|. Это значение может быть получено и Ао, либо по тео­ как скалярное произведение столбцов реме z ( X i ) = z ( X 0) - d(zj - cj), z ( X i) = 0 - e02{zj - Cj) = 0 — I = —|. Среди оценок Zj — Cj есть положительное чис­ ло 2з —Сз = следовательно, полученный опорный план неоптимален и вектор Л3 нужно вклю чить в базис .

–  –  –

Эту задачу можно решить такж е с помощью математи­ ческого пакета Maple®, текст программы приведен ниже:

re sta rt;

w ith (sim p le x );

W arning, the protected names maximize and minimize have been redefined and unprotected [ basis, convexhull, cterm, define_zero, display, dual, feasible, maximize, minimize, pivot, pivoteqn, pivotvar, ratio, setup, standardize ] x := a rra y ( 1..3 ) ;

–  –  –

-1 4 Функция m in im iz e ( z ( x ), s y s, NONNEGATIVE) решает задачу отыскания минимума функции z (x ) при условии, что переменные х удовлетворяют системе ограничений sys и принимают неотрицательные значения (NONNEGATIVE) .

Обратим внимание на то, что прежде чем использовать эту функцию, вначале следует подключить модуль simplex .

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

Предположим, что задача записана в следующем виде:

П z(x) = Y2 cj x j m in, j =i ijXj = bi, i = 1, m, Vbi 0, j =i X j 0, j = l, n,

–  –  –

Здесь M - достаточно большое положительное число, ес­ ли задача решается на минимум, и отрицательное число, если на максимум. Часто метод искусственного базиса на­ зывают М-методом .

Единичные вектора A„ + i,.. •, А п+т образуют искус­ ственный базис .

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

Теорема. Если в оптимальном плане X = (х \,..., х п, 0,..., 0) расширенной задачи (52) искус­ ственные переменные жп+)- = 0, то план X = (х х,..., х п) является оптимальным планом исходной задачи (51) .

Д о к а з а т е л ь с т в о. Заметим, что если план X является оптимальным планом расширенной задачи (52), то план А' - план исходной задачи (51), при этом z ( X ) — z ( X ). Ра­ венство значений целевых функций следует из того, что план X отличается от плана X последними т компонен­ тами, которые равны нулю .

Д окажем, что план X есть оптимальный план исход­ ной задачи. Допустим, что X не является оптимальным планом. Тогда существует такой оптимальный план X* — (х{, х\,..., *), для которого z (X* ) z ( X ). Отсюда для вектора X = (х{, х^,, ж*, 0,..., 0), являющегося пла­ ном расширенной задачи, получаем

–  –  –

z ( X 0) = сбА 0 = - 4 M - 4 M + 0 = 0 - 8 М, 2i — Ci = Сб^х — Ci = —2 М — I M —3 = —3 — ЗМ, z2 — с2 = СбА2 — с2 — —1М —3 М + 2 = 2 — 3 М, и так далее .

Отметим, что оценки Zj —Cj являются линейными ф унк­ циями от величины М .

Д л я удобства в (га + 1)-ую строку запишем слагаемое, не зависящее от М, а в (га + 2)-ую - только коэффициент при М, которые позволяют сравнивать оценки между со­ бой. В (771 + 2)-ой строке табл. 12.1 только отрицательные оценки, поэтому в задаче на максимум опорный план А 0 расширенной задачи оптимальным не является .

Включим в базис вектор, которому соответствует m in #0j ( zj — Cj) 0. Вычислим #0?-: #oi = m in ( l i f ) — 2, #02 = m in (|, | ) = f, #оз = f, #04 = f- m in(2 • ( —3), 3 - (— | I -(—2)) = — Разрешающим элементом будет число 2), 6 .

2, вектор Ах вводим в базис, а вектор А 5 исключаем из базиса .

Составим симплекс-таблицу (табл. 12.2). Д л я этого раз­ делим элементы первой строки на 2 и проведем одно ис­ ключение по схеме Ж ордана-Гаусса .

–  –  –

В (га 4- 2)-ой строке табл. 12.2 есть две отрицательные оценки, следовательно, полученный опорный план A’i = (2, 0, 0, 0, 0, 2) (z(Ari) = —2М + 6) оптимальным не являетДальнейшие вычисления приведены в табл. 12.3 .

После второй итерации получен опорный план Х 2 — (3, 0, 0,1, 0, 0) (г ( Х 2) = у ), который не является оптималь­ и Ае исключены из ба­ ным. Искусственные вектора зиса. Так как величина М представляет собой большое положительное число, а искусственные переменные х 5 и М, то xq входят в целевую функцию с коэффициентами — вектора А5 и А6 уже не могут попасть в базис. Исклю­ чим их из дальнейшего рассмотрения и удалим из табли­ цы (m -f 2)-ую строку. Дальнейший итерационный процесс будем выполнять по (га + 1)-ой строке, при этом величину М включим в оценки для искусственных векторов .

–  –  –

+М +М После третьей итерации в табл. 12.4 получено опти­ мальное решение расширенной задачи, в котором искус­ ственные переменные равны нулю: Х 3 = (0, 0, 3, 1, 0, 0), Zmax ~ Z ( X 3) = 8. Оптимальное невырожденное решение исходной задачи имеет вид: Л'ор(0, 0, 3,1), zmax = 8 .

–  –  –

Приведем эту задачу к стандартному виду. Д л я этого введем три дополнительные переменные х4 0, Х5 0 и xg 0.

Получим задачу с отрицательным начальным базисом:

–  –  –

Д алее необходимо перейти к положительному базису .

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

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

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

Получим задачу в стандартном виде:

–  –  –

Приведем эту задачу к стандартному виду. Умножим ограничения на —1, введем три дополнительные перемен­ ные х 4 0, х 5 0 и х 6 0.

Получим систему уравнений с отрицательным начальным базисом:

–  –  –

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

–  –  –

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

–  –  –

Приведем эту задачу к стандартному виду.

Введем три дополнительные переменные гс4 0, х 5 0 и х 6 0, при этом целевая функция не изменится, а система ограниче­ ний примет вид:

–  –  –

^ ___________ (62) ^ ijXj — bi, г = га + 1, га + / .

з=i Э та система ограничений состоит из т неравенств и I урав­ нений и не содержит единичной матрицы. Базис задачи состоит из дополнительных и искусственных векторов .

Чтобы привести задачу к стандартному виду поступа­ ем следующим образом. Если в неравенстве bi 0, то прибавляем к левой части неравенства неотрицательную дополнительную переменную. Если в неравенстве bi О, возьмем уравнение с номером к, bь 0, разделим это неравенство на произвольное положительное число так, чтобы его свободный член был меньше bд., и сложим с уравнением с номером к, затем перейдем от неравенств к равенствам. Полученные уравнения содержат дополни­ тельную переменную со знаком ”+ ”. В ограничения т + 1,..., т + I (типа равенств) введем искусственные пере­ менные Xn-(-m^_i,..., Рассмотрим на п р и м е р е приведение задачи со смешан­ ными ограничениями к стандартному виду .

z = —Х\ + З х 2 + 2х 3 —min, 2xj +х2 — Зх3 6,

–  –  –

Xi 0, г = 1, 3 .

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

Умножим второе ограничение на (—1), получим ограни­ чение, в котором свободный член отрицательный:

хх + 2х2 - 4х3 - 4 .

Разделим полученное неравенство на 4

–  –  –

Начальный опорный план X q = (0. 0, 0,1, 2,1), z ( X q) = М, оптимальным не является .

Решим эту задачу с помощью метода искусственного ба­ зиса (М -метода), вычисления запишем в табл. 15 .

–  –  –

После трех итераций метода получен невырожденный опорный план Хз = (6, 2, 3, 0, 0,0), г(Х$) = —1, кото­ рый является оптимальным планом расширенной зада­ чи. Решение исходной задачи имеет вид: X opt = (6,2,3), z ( X opt) = - 1 .

В последней строке в столбце Л4 имеется нулевая оцен­ ка, что является признаком неединственности оптималь­ ного решения задачи, однако столбец А 4 содержит только отрицательные элементы и при попытке включить вектор А\ в базис мы получим отрицательный опорный план, что противоречит условию задачи. Заметим, что при этом зна­ чение целевой функции не изменится и будет по-прежнему равно —1 .

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

Вычислительный эксперимент показывает, что число симплексных итераций оказывается от т до 3т и изме­ няется почти линейно от т .

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

Такая задача построена К ли и Минти [65], она имеет вид:

m ax х п, О Xi 1, г= 1, п, e x i- 1 Ж 1 —, г = 2, П, Полиномиальные алгоритмы для задачи линейного про­ граммирования с целочисленными коэффициентами опи­ саны в [11, 64, 66, 47], первый из них предложил Л.Г. Хачиян в 1979 г. В [6, 7] предложена модификация классической схемы алгоритма симплекс-метода, позволяющая решить общую задачу линейного программирования за число ите­ раций, полиномиально зависящее от ее размерности. При­ веденные в этих работах оценки трудоемкости не требу­ ют целочисленности коэффициентов задачи. Существен­ ным элементом описанного подхода является возможность включения в базис сразу нескольких переменных, в то вре­ мя как традиционная схема позволяет вклю чить в базис лишь одну переменную. Включение в базис s переменных требует решения специально построенной задачи линейно­ го программирования с s переменными и числом ограни­ чений т исходной задачи .

14 Основы теории двойственности в мате­ матическом программировании

14.1 Т еорем а К уна-Таккера о седловой точке Рассмотрим функцию г = f ( x, у), х — (х х, х 2,..., х п) X, У ~ (У У2, Ут) У Будем считать, что множества X г, и У ограничены и замкнуты, а функция f ( x, у) непрерыв­ на по совокупности переменных. Это значит, что ф ункция достигает своих минимального и максимального значений на множествах .

О п р е д е л е н и е. Точка (х °, у°) называется седловой т о ч­ кой функции f ( x, y ), если выполняются неравенства

–  –  –

Если f ( x, y ) - непрерывная функция, множества X, Y ограничены, замкнуты и выпуклы, f ( x, y ) выпукла отно­ сительно у для каж дого х и вогнута относительно х для каждого у, то

–  –  –

т.е. /(х ° ) / ( х ) и достаточность доказана. -4 Д оказательство необходимости приводить не будем. От­ метим, что в этом доказательстве используется существен­ но выпуклость задачи и условие Слейтера, не используе­ мые при доказательстве достаточности .

Из приведенного доказательства получим оценки для значений А” параметров \ г. Из условия т

–  –  –

/2 : х 1 -f- х 2 г—5, /з ; Зхх + х 2 = 9, Рассмотрим линии уровня функции х\ + —К = const 0. Это эллипсы, большая полуось которых в два раза длиннее меньшей полуоси. При увеличении К эллипс касается прямой 1Х в точке Е. Точка Е является решени­ ем задачи. Покажем, что в точке Е выполняются условия теоремы Куна-Таккера .

Найдем координаты точки Е. Прямая 2х\ + Зх2 = 6 является опорной по отношению к эллипсу xf + 4х\ = К, т.е. является касательной к эллипсу в точке Е.

Это означа­ ет, что ее координаты (xi, х2) удовлетворяют системе уравнений:

В этой системе два уравнения и три неизвестных: xi, х2 и К.

Выразим из первого уравнения х2 и подставим во второе:

–  –  –

14.2 Свойства ф ункции Л агранж а Сформулируем некоторые простые свойства функции Ла­ гранжа, для этого выполним переход к двойственной за­ даче .

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

–  –  –

Т е о р ем а 2. Если в точке х° = (х°, х \, .

.., х°) выпол­ няются условия регулярности и эта точка является реше­ нием прямой задачи (68), то существует решение А0 = (А?, А°,.. •, A^j) двойственной задачи (69) и справедливо равенство L(x°, А0) = /(х °) .

14.3 Д войственность в линейном программирова­ нии Рассмотрим применение этого подхода к задаче линей­ ного программирования. Запишем задачу линейного про­ граммирования в следующем виде, учитывая, что х т = { x i, x 2, -, х п), ст = (сь с2,..., сп):

–  –  –

14.4 Способы ф орм ирования двойственны х задач Рассмотрим способы формирования двойственной задачи из исходной (прямой). Пусть дана прямая задача вида

–  –  –

На примере 10 мы рассмотрели только один тип двой­ ственной задачи. Рассмотрим все виды математических м оделей пары двойственны х задач .

Напомним следующие обозначения: c-n -мерная строка, ж-п-мерный столбец, Ь-т-мерный столбец, Л-га-мерная строка .

Все пары задач делятся на симметричные и несиммет­ ричные. В симметричных задачах и прямые и двойствен­ ные переменные неотрицательны: Xi,Xj 0, i = 1,т, j — 1, п, а в несимметричных - только прямые переменные неотрицательны: 0, г = 1, га, а двойственные перемен­ ные Aj, j = 1, п могут быть любыми .

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

–  –  –

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

Теорем а 1. Пусть хТ = ( x lt х 2,, х п) - любой план прямой задачи (71), Лт = (Ai, А2, .

..

, Ат ) - любое допусти­ мое решение двойственной задачи (72), тогда выполняется следующее неравенство:

71 ТП

–  –  –

Это симметричная задача вида (4) (см. стр. 62) .

Д ля нахождения решения этой задачи можно использо­ вать симплексный алгоритм. Более простой подход состо­ ит в том, чтобы перейти к двойственной задаче с двумя пе­ ременными, которая легко решается геометрически. После нахождения решения двойственной задачи решение исход­ ной задачи легко находится по теореме Куна-Таккера .

Сформируем двойственную задачу, введем двойствен­ ные переменные \ х 0, Л2 0 .

lOAj 4- 7A2 — min, 5Aj +3A2 1, '

–  –  –

Подставим в последнюю систему х” = 0, х \ = 0 и х \ — 0 и найдем Х3 и х°:

Г Зх3 + 2х4 = 10, I х§ + 5х4 = 7, получаем ж = Ц, ж = f f .

® ® Оптимальное (невырожденное) решение прямой задачи (73) имеет вид (0.0, | |, ff,0 ), при этом максимальное зна­ чение целевой функции прямой задачи совпадает с мини­ мальным значением целевой функции двойственной зада­ чи и равно ~. Седловая точка функции Лагранжа имеет вид: (ж0, А0) = (0, 0,f f,f f, 0, ff, ^ ) .

Д ля иллюстрации теоремы 1 рассмотрим допустимое ре­ шение А = (2,0) двойственной задачи (74) и допусти­ мое решение х = (1,1,0,0,0 ) прямой задачи (73), то­ гда верно следующее соотношение для целевых функций:

z(x) = 3 20 = /(А ) .

Сформулируем теорему, которую мы использовали при решении примера 11 .

Теорема. Если при подстановке компонент оптимально­ го плана в систему ограничений исходной задачи г-ое огра­ ничение обращается в строгое неравенство, то г-ая компо­ нента оптимального плана двойственной задачи равна ну­ лю. Если г-ая компонента оптимального плана двойствен­ ной задачи больше нуля, то г-ое ограничение исходной за­ дачи выполняется как строгое равенство .

Это утверждение есть простейшее следствие теоремы Куна-Таккера .

–  –  –

Пусть х* = ( х \, х 2,,х*') - оптимальное решение пря­ мой задачи (75). Покажем, как можно найти оптимальное решение двойственной задачи (76) .

Пусть D - матрица, составленная из компонент векторов окончательного базиса А г, А 2, •, А т, тогда в симплекстаблице содержится разложение векторов А \, А 2,, А п исходной системы по векторам окончательного базиса, т.е .

каждому вектору Aj исходной системы ставится в соответ­ ствие вектор Ху .

–  –  –

где вектор с* = (cj, с2,..., с* однозначно определяется т) через вектор х* - это коэффициенты при переменных х* в оптимальном плане .

Сначала покажем, что Л* является планом двойственной задачи. Для этого ограничения двойственной задачи (76) запишем в виде неравенства ЛА — с 0, в левую часть которого подставим Л*. Тогда на основании (83), (80) и (81) получим

–  –  –

откуда находим, что Л М с .

Так как Л* удовлетворяет ограничениям двойственной задачи, то это и есть план двойственной задачи. При этом значение целевой функции двойственной задачи рав­ но /(Л*) = ЛМо- Учитывая соотношения (83), (80) и (81), имеем

–  –  –

Таким образом, значение линейной функции двойственной задачи от А* численно равно минимальному значению ли­ нейной функции исходной задачи (75) .

Докажем теперь, что Л* является оптимальным планом .

Умножим ограничение А х = Л0 задачи (75) на любой план Л двойственной задачи, а ограничение КА с задачи (76) - на любой план х исходной задачи: Л Ах = ЛАо = /(Л ), Л А х с х = z(x), отсюда следует, что для любых планов Л и х выполняется неравенство /(А ) z(x). (85) Этим же соотношением связаны экстремальные значения m ax/(Л ) т т г ( х ). Из последнего неравенства заклю­ чаем, что максимальное значение линейной функции достигается только в случае, если m ax /(Л ) = m inz(x), но это значение (см. (84)) /(Л ) достигает при плане Л*, следовательно, план Л* - оптимальный план двойственной задачи .

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

Рассмотрим задачу вида:

–  –  –

Решение прямой задачи найдем с помощью симплексметода, см. табл. 16. Начальный базис образуют вектора Ai, A 3, А 6. Оптимальное невырожденное решение полу­ чается после одной итерации: х* = (0,1, 3, 0, 0, 2), zmin = z(x*) = 1. Используя эту итерацию, найдем оптимальный план двойственной задачи .

–  –  –

Как было показано ранее, оптимальный план двойствен­ ной задачи находится по формуле (83), где D - матрица, обратная матрице, составленной из компонент векторов, входящих в последний базис, при котором получен опти­ мальный план прямой задачи. В последний базис входят вектора А 2, А 3, А 6 значит,

–  –  –

Теоремы 1-3 были сформулированы и доказаны в п. 14.4 .

Основная теорем а двойственности.

Если одна из па­ ры двойственных задач имеет решение, то разрешима и другая задача из этой пары и для оптимальных решений х° и А° справедливо равенство:

п т

–  –  –

Следствие 1. Для разрешимости одной из задач двой­ ственной пары необходимо и достаточно, чтобы каждая из этих задач имела хотя бы один план .

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

Следствие 3. Для оптимальности планов х* и Л* пря­ мой и двойственной задач соответственно необходимо и до­ статочно выполнение равенства п ТП

–  –  –

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

При этом условия (86) соответствуют столбцу j матрицы А, а условия (87) - строке г матрицы А .

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

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

Теорема двойственности. Если взаимносопряженные задачи разрешимы, то в любой паре их двойственных усло­ вий одно свободное, другое - закрепленное .

Теорема о дополнительной неж есткости. Если х * = (х\,х*2,...,х*п) - решение прямой задачи, а А* = (AJ, XI,...

, Aj) - решение двойственной задачи, то эти ре­ шения оптимальны тогда и только тогда, когда выполняются условия:

–  –  –

Заметим, что при ??iг = га и гаг = п получается пара двойственных задач, которые мы уже рассматривали .

Условия неотрицательности накладываются лишь на часть переменных исходной и двойственной задач. Если переменная xj не имеет ограничения Xj 0, то она может быть представлена в виде xj = x'j — х”, ж' 0, х ” 0 .

Аналогично Aj = А' —А", А- 0, А" 0 .

Если переменная х.} в прямой задаче неотрицательна, то условие j в двойственной задаче является неравенством .

Если на переменную Xj в прямой задаче условие неотри­ цательности не накладывается, то соответствующее усло­ вие двойственной задачи является равенством. Аналогич­ но для переменных А; двойственной задачи: если условие г прямой задачи является неравенством, то двойственная переменная Aj неотрицательна; если условие г является ра­ венством, то двойственная переменная Aj может быть лю­ бой .

Соответствующие теоремы двойственности верны и в этом случае .

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

14.9 Влияние изм енения вектора b на оптималь­ ное реш ение задачи

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

Теорема. Пусть задача линейного программирования невырождена и М(ЬХ,Ь2,..., Ьт) - максимальное значение целевой функции. В этом случае

–  –  –

15 Задачи многокритериальной оптими­ зации: краткие сведения о постановках и алгоритмах решения

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

В этом параграфе излагаются начальные сведения о многокритериальных задачах и алгоритмах их решения;

более полные сведения содержатся в работах [2, 15, 25, 41, 42, 43, 49, 50, 55, 57, 62, 63] .

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

15.2 Постановка задачи Пусть X = ( x i, x 2,, х п) е X С R n и f ( x ) = (/i(s)./2 (a 0, • • •, / Р(я)) G Е р, р 2. Задачу f ( x ) — min, » х GX (91) назовем задачей многокритериальной оптимизации, Е р будем считать метрическим числовым пространством и называть критериальным пространством. Д ля того, что­ бы задача (91) стала содержательной, необходимо опреде­ лить, что означает в ней операция нахождения минимума .

Пусть Y С Е р - множество допустимых значений функ­ ции f ( x ), которое предполагается непустым, замкнутым и ограниченным. Если множество X конечно, то задача (91) является задачей многокритериального дискрет,ного программирования, а если это множество определяется си­ стемой линейных неравенств и все функции /Д х), г = 1,р линейны, то задача (91) - это задача многокритериаль­ ного линейного программирования. В общем случае зада­ ча (91) - задача многокритериального математического программирования [41] .

Решим р однокритериальных задач У = /(*?) = min Л (ж), i = l, р .

® (92) Точка у 0 = ( у® у%,..., Ур) называется ’’ деальной” тон­, и кой, если у 0 G Y, то у 0 - ”идеальное” решение задачи (91) .

Из у 0 G Y следует, что существует точка ж0 G X такая, что f ( x ° ) — у 0, в этом случае ’’идеальное” решение задачи (91) полностью определяет понятие m in /(ж), введенное в (91) .

В точке ж0 G X достигается минимум по всем критериям .

В дальнейшем предполагаем, что у 0 ф Y .

При исследовании реальных задач представляется це­ лесообразным привести все критерии к нормализованно­ му виду Ji (x) = у \ ф 0, i = 1,р. В этом случае _ Ui все критерии Д(ж) становятся безразмерными и сравни­ мыми по величине, а области изменения их значений име­ ют одинаковый масштаб. Отсутствие размерности у крите­ риев и одинаковый масштаб областей их изменения дела­ ют осмысленными математические и логические операции над разными по содержанию критериями. В дальнейшем для новых критериальных функций /,(ж) сохраним старые обозначения /г(ж), г = 1,р. Решения ж1 и ж2, для которых /(ж 1) = /(ж 2), называются эквивалентными .

Рассмотрим простые примеры для р — 2 .

П р и м е р 13. / i ( ж) = (ж — I)2 + 1, / 2(ж) = (ж - 2)2 + 2, А - = [0,3], f (x ) = ( f i ( x ), M x )) -4 min, х ex .

Представим задачу графически на рис. 27. Введем функ­ цию г?/ \. и Г (ж — I)2 + 1, 0 ж 2;

F (х) = mmlAW, /2W) = | _ 2' 2+ 2, 2 з? 3, которая выделена на рис. 27 жирной линией. Под решени­ ем задачи будем понимать точку жо, такую, что F ( xq) = m inF (x), 0 x 3, x0 — 1. В этом примере решение задачи сведено к поиску точки минимума специально по­ строенной функции F(x) .

–  –  –

параметры Ai упорядочены в порядке важности рассмат­ риваемых критериев:

Ai ^ А2 Ар. (95) При этом задача (94) может решаться как при фиксиро­ ванных значениях А так и при определяемых непосред­ *, ственно в процессе ее решения значениях Ai в соответствии с приведенным упорядочением (95) .

15.4 Э ф ф ективны е реш ения Вектор у — ( уу, у 2,..., Ур) Y называется эффективным, G если не существует вектор с = (zi, z2), zp) 6 Y такой, что zt уг.: г — 1, р, и хотя бы для одного г0 выпол­ нено строгое неравенство zio yio. Множество всех эф­ фективных векторов P ( Y ) называется множеством оп­ тимальных решений задачи (91) по Парето. Если нера­ венства Zi yi выполнены для всех г, то множество эф­ фективных в этом смысле векторов « '(У) называется слабо S эффективным и является множеством оптимальных ре­ шений задачи (91) по Слейтеру ( S ( Y) 5 P{ Y) ) - Эффек­ тивные (слабо эффективные) решения несравнимы между собой: увеличение какой-либо из его компонент приводит к уменьшению других. В примере 14 под решением задачи будем понимать множество X .

Рис. 28 .

Иллюстрация для двух критериев приведена на рис. 28, где жирной линией показано множество эффективных ре­ шений. Д ля каждой точки множества Y проведены две взаимно перпендикулярные прямые, параллельные осям координат. Эффективные точки характеризуются тем, что прямой угол с вершиной в каждой из этих точек в указан­ ных стрелками направлениях не содержит ни одной точки множества У .

Введем понятие доминирования точек. Точка у1 = (yi. y h • • 1Уп) е У доминирует точку у2 = у \,..., у") € У, если у\ у 2, i = 1, гг и хотя бы для одного значения г неравенство является строгим. Точка у 2 не может быть эф­ фективной. Недоминируемые точки образуют множество Парето. Рассмотрим понятие доминирования для случая р — 2. Пусть у 1 и у] - две эффективные точки. Тогда из определения следует: если у{ у{, то у\ у\\ если у\ yj, то у г у 2- На рис. 29 геометрически иллюстрируется по­ нятие доминирования для р — 2 .

Рис. 29 .

Точка у 1 доминирует точку у 2, так как находится внутри прямого угла с вершиной в точке у 2 и сторонами, перпен­ дикулярными осям координат, поэтому точка у 2 не явля­ ется точкой Парето. Точка у1 также не является точкой Парето, так как точка у3 доминирует точку у1. На этом рисунке точки Парето - у3, у4, у5, у6, для точки у3, напри­ мер, видно, что у3 у4, у 2 у2. В нашем примере точки Парето у4, у5, у6 -- вершины выпуклой оболочки. При этом точка у3 не лежит на выпуклой оболочке. Нижняя часть выпуклой оболочки - это отрезки (у4, у5) и (у5, у6). Точка у3 не принадлежит ни одному из них .

Д ля нахождения оптимальных но Парето (Слейтеру) ре­ шений задачи (91) применяются различные свертки кри­ териев, некоторые из них рассматриваются далее .

15.5 Свертки критериев и их применение дл я на­ хож ден и я эф ф екти вны х реш ений

Линейная свертка критериев имеет вид:

р р = А, 0, 5 ; = 1- (96) i= l i= 1 Из нелинейных сверток известна свертка Ю.Б. Гермейера [15]: р z ( X, f ) = m a x \ i f t(x), Л О ]Р а = 1 .

*, (97) г=1 Для нахождения множества эффективных решений рас­ сматривается следующая задача 2 (Л, / ) -» min, х G X, f ( x ) G Y. (98) Как показано в [15] (Теорема V, стр. 59), при­ менение свертки (97) позволяет найти все эф­ фективные точки для любого числа критериев f { x ) = { f i ( x ), f 2( x ),..., f p(x)) G Е р, р 2. При­ менение этой свертки при решении многокритери­ альных задач сопряжено с вычислительными труд­ ностями, связанными с минимизацией функции максимума .

р Рассмотрим свертку (96) при условиях А 0 .

* Аг = 1 .

г—1 Можно показать, что все решения задач вида (98) явля­ ются эффективными точками, но обратное утверждение неверно, т.е. существуют эффективные точки, которые не являются решениями задач вида (98). Существуют клас­ сы задач, для которых линейная свертка критериев на­ ходит все эффективные решения. Это задачи, у которых все критерии линейны, а область X является выпуклым многогранником (задачи многокритериального линейного программирования) .

Если множество X - множество ?г-мерных булевых век­ торов, то любое решение задачи вида (98) со сверткой (96) при А, 0 - это эффективное решение задачи (91). Ес­ ли Aj 0, то приведенное утверждение перестает быть верным. Все приведенные в этом пункте утверждения об­ основаны в [15, 41], в [41] описаны общие схемы сведения многокритериальных задач к однокритериальным .

Из общей теории многокритериальных задач дискрет­ ной оптимизации [41, 42, 43] следует, что оптимизация линейной свертки критериев находит лишь множество Y c С P ( Y ) точек Парето, лежащих на выпуклой оболоч­ ке [52, 55] множества P ( Y ), т .

е. линейная свертка нахо­ дит лишь часть множества P ( Y ). Например, точка у3 на рис. 29 не лежит на выпуклой оболочке и не может быть найдена с применением алгоритма линейной свертки. В работах [42, 43] показано, что для ряда классических за­ дач дискретного программирования с двумя критериями отношение а — j^y jj монотонно убывает с ростом харак­ терного параметра п, определяющего размерность задачи .

Линейная свертка критериев в задачах многокритери­ альной оптимизации часто рассматривается в качестве практического метода нахождения оптимальных в том или ином смысле решений. Эта свертка находит лишь часть эффективных решений. Если результат, полученный с применением линейной свертки, используется для приня­ тия практических решений, то при этом следует проявлять известную осторожность [25] .

Отметим, что с ростом числа критериев возрастает мощ­ ность множества эффективных решений, для отбора кото­ рых необходимо использовать дополнительные соображе­ ния (например, рекомендации ЛПР). Оценки для числа эф­ фективных точек в дискретных задачах приводятся в [49] .

15.6 П рим енение м нож еств.R-близких реш ений в многокритериальны х задачах При решении задачи (92) будем предполагать, что для каждого их критериев /, (х), i — 1, р может быть найдено не только оптимальное решение х®, но и множество всех решений S ( R i ), удовлетворяющих условию

–  –  –

Множеству S(jF?i, R 2) соответствует отрезок [Л, В] на оси 0ж, х° ^ S ( R i, R 2), Хо S ( R i, R 2). Алгоритмы построения множеств типа 5 (Д,) для задач дискретного программи­ рования рассмотрены в [55, 62] .

15.7 Ч астичное упорядочение критериев Рассмотрим случай, когда условие (101) f i ( x ) У f j { x) задано для некоторых пар критериев (критерий f i (x) пред­ почтительнее, важнее, чем f j ( x) ) и опишем один из воз­ можных способов определения их весовых коэффициентов р К 0, Y1 — 1- Предположим, что выполнено условие i=i транзитивности, т.е. если f j ( x) У fk{x), то при выполне­ нии (101) получим fi (x) У fk(x). Условие (101) не имеет числового характера .

Построим ориентированный граф с р вершинами, в ко­ тором установим взаимно однозначное соответствие меж­ ду вершинами и критериями. В графе существует дуга если выполнено условие (101). Предположим, что в графе нет контуров, т.е. условия вида f i (x) У f j { x) У f i (x ) невозможны. Построенный граф состоит из f k(x ) нескольких компонент связности, каж дая из которых яв­ ляется транзитивным, порожденным и односторонне связ­ ным подграфом [35]. В графе между некоторыми парами вершин существуют ориентированные пути; вершины, не входящие в такие пути, являются изолированными. Для каждой вершины г найдем множество М* всех достижи­ мых из нее по ориентированным путям вершин, применяя алгоритмы, описанные в [35], /лг = [Л/*); каждая изолиро­ ванная вершина г достижима из себя, Mi = {г}, Hi — 1 .

Описанная процедура позволяет нечисловое условие вида (101) заменить числовым, т.е. превращает нечисловую ин­ формацию в числовую .

Параметр jj,t определяет число критериев j, для кото­ рых выполнены условия типа (101) при фиксированном значении i. Тогда E / J;

Полученные значения Aj могут быть использованы при формировании сверток критериев. Под решением задачи (91) будем понимать множество точек х G X. полученных при минимизации сверток. Более подробное исследование условий типа (101) содержится в [2, 49] .

–  –  –

(103) fi(x) f i, г = г + 1,р, х в X .

В постановке (103) предполагается, что все главные крите­ рии имеют одинаковый вес. Если эти критерии упорядоче­ ны в порядке их важности f i ( x ) у / 2(х) у У / г(.х), то необходимо ввести дополнительное ограничение Л] Л2 •' K t такое упорядочение может быть задано для всех критериев г —р. Другие способы упорядочения критериев описаны в предыдущем пункте .

Под решением задачи (91) будем понимать все точки х Е X, полученные при решении задач вида (102) или (103) .

Предметный указатель Базис искусственный, 25 — начальный отрицательный, 33 Вектор эффективный, 85 Доминирование, 86 Задача двойственная, 57, 77 — линейного программирования в канонической форме, 7 — многокритериального дискретного программирования, 81

----- линейного программирования, 81, 88

----- математического программирования, 81 — многокритериальной оптимизации, 81 — несимметричная, 62 — несовместная, 26 —прямая, 57, 77 — симметричная, 62 — совместная, 26 — со смешанными ограничениями, 31 Зацикливание, 42 Интерпретация двойственной задачи, 59 Лицо, принимающее решение (ЛИР), 84 М- метод, 25 Метод ’’идеальной” точки, 83 — искусственного базиса, 24 Множество Парето, 86 Множители Лагранжа, 45 Оценки плана, 14 Пара двойственных условий, 75 — взаимнодвойственных задач, 63 Переменные базисные, 8 — дополнительные, 16 — искусственные, 24 — свободные, 8 Пространство критериальное, 81 Решение ’’идеальное”, 82 — оптимальное по Парето, 85 по Слейтеру, 85 — слабо эффективное, 85 — эффективное, 85 Решения эквивалентные, 82 — /2-близкие, 89 Свертка критериев линейная, 87

----- нелинейная, 87 Симплекс-алгоритм, 15 — метод, 15 — таблица, 15 Система ограничений несовместная, 31 Схема Жордана-Гаусса, 10 Теорема двойственности, 75 — — основная, 74 — Куна-Таккера, 4G — — в дифференциальной форме, 48 — о минимаксе, 44 — о дополнительной нежесткости, 75 Точка ’’идеальная”, 82 — седловая, 44 Трудоемкость симплекс-метода, 42 Условие закрепленное, 75 — оптимальности в задаче линейного программирования, 13 — регулярности Слейтера, 45 — свободное, 75 — существования внутренней точки, 45 Функция Лагранжа, 45

-- minimize, 23 Список литературы [1 Абрамов Л. М., Капустин В.Ф. Математическое про­ граммирование. - Л.: Издательство ЛГУ, 1976 .

Айзерман М. А., Алексеров Ф.Т. Выбор вариантов .

[2 Основы теории. - М.: Наука, ГРФМЛ, 1990. - 236 с .

[3 Акулич И.А. Математическое программирование в примерах и задачах. Учебное пособие для вузов. - М.:

Высш. шк., 1986 .

[4 Ашмаиов С. А. Линейное программирование. - М.: На­ ука. ГРФМЛ, 1981 .

Банди Б. Основы линейного программирования. - М.:

Радио и связь, 1989 .

[6 Березнев В.А. Об одной модификации симплексметода // Вопр. моделирования и анализа в задачах принятия решений. М.: ВЦ РАН, 2002. С. 93-120 .

[7 Березнев В.А. О полиномиальной сложности одной модификации симплекс-метода // ЖВМиМФ, 2004. Т .

44. № 7. С. 1244-1260 .

[8 Булавский В.А., Звягина P.A., Яковлева М.А. Чис­ ленные методы линейного программирования. - М.:

Наука, ГРФМЛ, 1977 .

[9 Вагнер Г. Основы исследования операций. - М.: Мир, Том 1, 1972. Том 2, 1973 .

Васильев Ф.П. Численные методы решения экстре­ мальных задач. - М.: Наука, ГРФМЛ, 1980 .

[11] Васильев Ф.П., Иваницкий А.Ю. Линейное програм­ мирование. - М.: Факториал, 1998 .

[12] Волков И.К., Загоруйко Е.А. Исследование операций .

- М.: Изд-во МГТУ им. Н.Э. Баумана, 2000 .

[13] Галеев Э.М., Тихомиров В.М. Оптимизация, теория, примеры, задачи. - М.: Эдиториал УРСС, 2000 .

[14] Гасс С. Линейное программирование. - М.: Физматгиз, 1961 .

[15] Гермейер Ю.Б. Введение в теорию исследования опе­ раций. - М.: Наука, ГРФМЛ, 1971. - 383 с .

[16] Гольштейн Е.Г. Выпуклое программирование, эле­ менты теории. - М.: Наука, ГРФМЛ, 1970 .

[17] Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа. - М.: Наука, ГРФМЛ, 1969 .

[18] Гольштейн Е. Г., Юдин Д. Б. Новые направления в линейном программировании. - М.: Советское радио, 1966 .

[19] Горбовцов Г. Я. Методы оптимизации. Учебно­ практическое пособие. - М.: Московский государ­ ственный университет экономики, статистики и информатики, 2000 .

[20] Гуревич Т.Ф., Л у щ у к В. О. Сборник задач по матема­ тическому программированию. - М.: Колос, 1977 .

[21] Данциг Д. Б. Линейное программирование, его приме­ нения и обобщения. - М.: Прогресс, 1966 .

[22] Да у га в ет В. А. Численные методы квадратичного программирования. - C-Пб.: Издательство СанктПетербургского университета, 2004 .

[23] Даффин Р., Питерсон Э., Зенер К. Геометрическое программирование. -- М.: Мир, 1972 .

[24] Дьяконов В. Maple 7: учебный курс. - СПб.: Питер, 2002 .

[25] Евдокимов М.В., Медницкий В.Г., Сигал И.Х. Бикритериальная задача переоборудования производства. // Известия РАН. Теория и системы управления. - № 5 .

- 2001. - С. 90-96 .

[26] Ермольев Ю.М. Методы стохастического программи­ рования. - М.: Наука, ГРФМЛ, 1976 .

[27] Заславский Ю.Л. Сборник задач по линейному про­ граммированию. - М.: Наука, ГРФМЛ, 1969 .

[28] Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. - М.: Наука, ГРФМЛ, 1967 .

[29] Измаилов А.Ф., Солодов М.В. Численные методы оп­ тимизации. - М.: ФИЗМАТЛИТ, 2003 .

[30] Исследования операций в экономике. Под ред. Н.Ш .

Кремера. - М.: "Банки и биржи". Издательское объ­ единение "Ю НИТИ", 1997 .

[31] Калихман И.Л. Сборник задач по математическому программированию. - М.: Высш. шк., 1975 .

[32] Капустин В.Ф. Практические занятия по курсу ма­ тематического программирования. - Л.: Изд-во ЛГУ, 1976 .

[33] Карлин С. Математические методы в теории игр. про­ граммировании и экономике. - М.: Мир, 1964 .

[34] Карманов В.Г. Математическое программирование. М.: ФИЗМАТЛИТ, 2000 .

[35] Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978. - 432 с .

[36] Кузнецов Ю. Н., Кузубов В.И., Волощенко А.Б. Мате­ матическое программирование. Учебное пособие для вузов. - М.: Высш. шк., 1976 .

[37] Кюнци Г.П., Крелле В. Нелинейное программирова­ ние. - М.: Советское радио, 1965 .

[38] Л у н г у К Н. Линейное программирование. Руковод­ ство к решению задач. - М.: ФИЗМАТЛИТ, 2005. с .

[39] Ляшенко И.H., Карагодова Е.А., Черникова Н.В., Шор Н.З. Линейное и нелинейное программирование .

- Киев: Высш. шк., 1975 .

[40] Мак-Кинси Д ж. Введение в теорию игр. - М.:

ГИФМЛ, 1960 .

[41] Меламед И. И. Методы оптимизации в транспортном процессе. - ИНТ. ВИНИТИ. Сер. Оптимизация управ­ ления транспортом. Т. 10. - М.: ВИНИТИ. 1991. - 162 с .

[42] Меламед И. И., Сигал И. X. Исследование линейной свертки критериев в многокритериальном дискретном программировании. // Ж урнал вычислительной мате­ матики и математической физики. 1995. - Т.35. - № 8 .

С. 1260-1270 .

[43] Меламед И. И., Сигал И. X. Теория и алгоритмы ре­ шения многокритериальных задач комбинаторной оп­ тимизации. М.: ВЦ РАН. 1996. - 52 с .

[44] Моисеев H. H., Иванилов Ю. П., Столярова E. М .

Методы оптимизации. - М.: Наука, ГРФМЛ, 1978 .

[45] Муртаф Б. Современное линейное программирова­ ние: Теория и практика. - М.: Мир, 1984 .

[46] Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. - Новосибирск.: Наука, Сибирское отделение, 1977 .

[47] Нестеров Ю.Е. Метод линейного программирования с кубической трудоемкостью // Экономика и матем .

методы. 1988. Т. 24. № 1. С. 174-176 .

[48] Первушин В.Е. Математическое программирование в примерах и задачах. Учебное пособие. - М.: МГУИЭ, 2004 .

[49] Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. - М.: Наука, ГРФМЛ, 1982. - 254 с .

[50] Полищук Анализ многокритериальных Л. И .

экономико-математических моделей. - Новосибирск:

Наука, СО. 1989. - 351 с .

[51] Поляк Б. Т. Введение в оптимизацию. - М.: Наука, 1983 .

[52] Препарата Ф., Шеймос М. Вычислительная геомет­ рия: Введение. -- М.: Мир. 1989. - 478 с .

[53] Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования (теория, методы, при­ ложения). - М.: Радио и связь, 1982 .

[54] Романовский И. В. Алгоритмы решения экстремаль­ ных задач. - М.: Наука, ГРФМЛ, 1977 .

[55] Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычисли­ тельные алгоритмы: Учеб. пособие. - М.: ФИЗМАТ­ ЛИТ, 2002 .

[56] Сигал И.Х., Иванова А.П. Методы оптимизации. На­ чальный курс. - Курс лекций по дисциплине ’’Мето­ ды оптимизации”. Часть 1. Основные определения и понятия, постановки задач и примеры. - М.: МИИТ, 2005. - 96 с .

[57] Соболь И.М., Стат.ников Р.Б. Выбор оптимальных параметров в задачах с многими критериями. - М.:

Наука, 1981. - 110 с .

[58] Сухарев А.Г., Тимохов A.B., Федоров В.В. Курс ме­ тодов оптимизации. Издание второе. - М.: ФИЗМАТ­ ЛИТ, 2005 .

[59] Схрейвер А. Теория линейного и целочисленного про­ граммирования. - М.: Мир, Том 1, Том 2, 1991 .

[60] Табак Д., Куо Б. Оптимальное управление и мате­ матическое программирование. - М.: Наука, ГРФМЛ, 1975 .

[61] Юдин Д. Б., Гольштейн Е.Г. Задачи и методы линей­ ного программирования. - М.: Советское радио, 1964 .

[62] Хачатуров В. Р. и др. Комбинаторные методы и алго­ ритмы решения задач дискретной оптимизации боль­ шой размерности. - М.: Наука. 2000. - 355 с .

[63] Штойер Р. Многокритериальная оптимизация. Тео­ рия, вычисления и приложения. - М.: Радио и связь .

1992. - 504. с .

[64] Хачиян Л.Г. Полиномиальный алгоритм линейного программирования // Докл. АН СССР. 1979. Т. 244 .

№ 5. С. 1093-1096 .

[65] Klee V., Minty G.L. How good is simplex algorithm? // Inequalities-III. New-York, London: Acad. Press, 1972 .

P. 159-175 .

[66] Karmarkar N. A new polynomial-time algorithm for linear programming // Combinatorica. 1984. V. 4. № 4 .

P. 373-395 .

Св. план 2006 г., поз. 179

–  –  –

МЕТОДЫ ОПТИМИЗАЦИИ .

НАЧАЛЬНЫЙ КУРС

ЧАСТЬ 2 Симплекс-метод и смежные вопросы, элементы теории двойственности, многокритериальная оптимизация

Похожие работы:

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Ярославский государственный университет им. П.Г. Демидова Факультет информатики и вычислительной техники УТВЕРЖДАЮ Проректор по развитию образования _Е.В. Сапир _2012  г. Рабочая пр...»

«1 Профессор Игорь Н. Бекман КОМПЬЮТЕРЫ В ИНФОРМАТИКЕ Курс лекций Лекция 10. ПРОГРАМНОЕ ОБЕСПЕЧЕНИЕ Прикладная программа в широком смысле программа или пакет прикладных программ, ре...»

«Фтизиатрия и пульмонология №2(10) www.ftisiopulmo.ru ИНФОРМАТИВНОСТЬ ХИРУРГИЧЕСКИХ МЕТОДОВ БИОПСИИ ЛЕГКОГО В ДИАГНОСТИКЕ ДИФФУЗНЫХ ЗАБОЛЕВАНИЙ ЛЕГКИХ Раевская Н.В., Мотус И.Я., Сабадаш Е.В., Дьячков И.А., Егоров Е.А. Кафедра фтизиатрии и пульмонологии...»

«РАЗДЕЛ 8. ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ В РЕГИОНАЛЬНЫХ ОБРАЗОВАТЕЛЬНЫХ СИСТЕМАХ 7. Кривчанский И.Ф., Симан А.С. Опыт применения автоматизированного контроля учебных достиже­ ний на этапе итоговой аттестации выпускников вуза/ Современные проблемы информатизации про­ фессионального образования: материалы Международной научно-практическ...»

«Московский государственный университет имени М.В. Ломоносова Факультет вычислительной математики и кибернетики Магистерская программа "Математическое и программное обеспечение защиты информации" Магистерская диссертация "СРАВНИТЕЛЬНЫЙ АНАЛИЗ СТ...»

«ФЭИ-2076 ОЯ0 ФИЗИКО-ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ П. А. АНДРОСЕНКО, В. Л. ЛОМТЕВ О вычислительной эффективности методов Монте-Карло при решении задачи Дирихле г. Ч ч I J/ Обнинск — 1990 ФЭИ-2076 "ИЗИКО-ЭНЕРГЕТИЧЕСКИЯ ИНСТИТУТ П.А.Андросенко.В.Л.Ломтез...»

«Программа вступительного испытания в аспирантуру ЮФУ по направлению 09.06.01 “Информатика и вычислительная техника Программа включает общий раздел и два подраздела на выбор поступающего (А математическое моделирование и численные методы, Б – математическое и программное обеспечение). В билет вклю...»

«Задания отборочного этапа олимпиады школьников "Ломоносов-2015" по информатике (10–11 классы) Первыи тур Задачи 1, 2, 3, 5, 6, 7 имеют вариативную постановку. Каждому участнику предлагался один из вариантов этих задач. Комментарии по этим вариантам приводятся ниже. Для приема решений использовал...»

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФИЗИЧЕСКИЙ ПРАКТИКУМ ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ ИССЛЕДОВАНИЯ МОЛЕКУЛЯРНОЙ ДИНАМИКИ АКСЕНОВА Е.В., КШЕВЕЦКИЙ М.С. Учебно-методическое пособие (для студентов физического факультета) Санкт-Петербург Вычислительные методы исследования молекулярной динамики....»

«В. Ф. Очков, Национальный исследовательский университет "МЭИ", Москва, В. Л. Чудов, А. В. Соколов, лицей № 1502, Москва ИСПОЛЬЗОВАНИЕ ФОРУМА РТС COMMUNITY/MATHCAD НА ШКОЛЬНЫХ ЗАНЯТИЯХ ПО ИНФОРМАТИКЕ Аннотация В статье рассмотрены вопросы поддержки учебного процесса в школе с испо...»

«XIII Всероссийская научно-практическая конференция "Технологии Microsoft в теории и практике программирования" Данный метод балансировки нагрузки в РАС значительно повышает производительность системы, так как количество ДЦУ ограничено только вычислительной мощностью разработанной инфраструктуры системы. Список литературы Радченко Г.И. Распредел...»

















 
2018 www.new.z-pdf.ru - «Библиотека бесплатных материалов - онлайн ресурсы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 2-3 рабочих дней удалим его.