Б.А. ЕСИПОВ

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

ИССЛЕДОВАНИЕ ОПЕРАЦИЙ.

КОНСПЕКТ ЛЕКЦИЙ

2007

САМАРА

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ УДК 681.3.07

ББК 32.973.26-018.2.75

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

?К218

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ ОНАЛЬ

ЦИ Инновационная образовательная программа НЫ УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА» А Н Е "Развитие центра компетенции и подготовка

ТЕТНЫЕ

ПР ОЕКТЫ специалистов мирового уровня в области аэрокосмических и геоинформационных РИ О И технологий” ПР Б. А. ЕСИПОВ Рецензенты: докт. техн. наук, профессор А.Н.Коварцев канд. физ-мат. наук, доцент Е.Я.Горелова МЕТОДЫ ОПТИМИЗАЦИИ И ?К218 Есипов Б.А.

Методы оптимизации и исследование операций.

ИССЛЕДОВАНИЕ ОПЕРАЦИЙ. Конспект лекций: учеб. пособие / Б.А.Есипов,. –Самара: Издво Самар. гос. аэрокосм. ун-та, Конспект лекций. 2007. – 90 с. : ил.

???ISBN 5-94774-0003- Утверждено Редакционно-издательским советом университета В учебном пособии дано краткое изложение основных методов в качестве учебного пособия оптимизации и исследования операций. Материал пособия основан на лекциях, читаемых автором для студентов факультета «Информатика» и соответствует программам курсов «Методы оптимизации», «Теория игр и исследование операций», «Теория принятия решений».

Настоящее пособие является вспомогательным материалом к прослушиваемому курсу лекций, поэтому применяется конспективный стиль изложения.

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

Подготовлено на кафедре «Информационные системы и технологии» Самарского государственного аэрокосмического университета.

УДК 681.3. ББК 32.973.26-018.2. САМАРА ?ISBN 5-94774-0003-6 © Есипов Б.А., Издательство СГАУ © Самарский государственный 2007 аэрокосмический университет, Учебное издание Есипов Борис Алексеевич

МЕТОДЫ ОПТИМИЗАЦИИ И ИССЛЕДОВАНИЕ

ОПЕРАЦИЙ.

КОНСПЕКТ ЛЕКЦИЙ

Редактор а Компьютерная верстка Доверстка Подписано в печать _г. Формат 60х84 1/16.

Бумага офсетная. Печать офсетная.

Усл. печ. л.. Усл. кр.-отт.. Уч.-изд.л..

Тираж экз. Заказ _. Арт. С- / Самарский государственный аэрокосмический университет.

443086 Самара, Московское шоссе, 34.

Изд-во Самарского государственного аэрокосмического университета.

443086 Самара, Московское шоссе, 34.

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ

УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА»

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

И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

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

САМАРА

УДК 681.3. ББК 32.973.26-018.2. К

ТЕТНЫЕ

Рецензенты: докт. техн. наук, профессор А.Н. Коварцев В учебном пособии дано краткое изложение основных методов оптимизации и исследования операций. Материал пособия основан на лекциях, читаемых автором для студентов факультета «Информатика» и соответствует программам курсов «Методы оптимизации», «Теория игр и исследование операций», «Теория принятия решений». Настоящее пособие является вспомогательным материалом к прослушиваемому курсу лекций, поэтому применяется конспективный стиль изложения. Приведены алгоритмы и примеры их работы, а также рисунки, поясняющие суть методов, что позволяет студентам разрабатывать компьютерные программы для выполнения индивидуальных заданий курсовой работы.

Предназначено для студентов специальностей «Прикладная математика и информатика», «Автоматизированные системы обработки информации и управления», а также аспирантов и специалистов, интересующихся методами оптимизации и исследования операций.

Подготовлено на кафедре «Информационные системы и технологии»

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

Введение

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

1.1. Системный анализ, система, оптимизация

1.2. Схема операционного проекта

1.3. Особенности математического моделирования операций............... 1.4. Постановка задачи исследования операций в детерминированном случае и в условиях неопределенности

1.5. Пример математического моделирования операции (задача о краске)

2. Линейное программирование (ЛП)

2.1. Общая и основная задачи ЛП

2.2. Геометрическая интерпретация задачи ЛП

2.3. Идея симплекс-метода решения задачи ЛП

2.4. Симплекс-таблица, стандартный алгоритм симплекспреобразования

2.5. Алгоритм отыскания опорного решения задачи ЛП

2.6. Алгоритм отыскания оптимального решения задачи ЛП................. 2.7. Алгоритм получения первого базисного решения с использованием симплекс – процедуры (метод искусственного базиса)

2.8. Вырожденная задача ЛП

2.9. Двойственная задача ЛП

3. Транспортные задачи (ТЗ)

3.1. Математическая модель ТЗ по критерию стоимости

3.2. Нахождение опорного плана транспортной задачи

3.3. Оптимизация плана ТЗ, распределительный метод

3.4. Метод потенциалов решения ТЗ

3.5. Решение ТЗ с неправильным балансом

3.6. ТЗ по критерию времени, типы критериев

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

Особенности задач дискретного программирования

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

4.2.2. Задача о коммивояжёре

4.2.3. Задача о раскрое материала

4.2.4. Задача о ранце

4.3. Алгоритм решения задачи о ранце

4.4. Решение задач ЛЦП методом отсечений Гомори

4.5. Метод ветвей и границ (МВГ)

4.6. Алгоритм МВГ для задачи ЛЦП

4.7. Алгоритмы решения задач булевского программирования............. 5. Динамическое программирование (ДП)

5.1 Принцип оптимальности Р.Беллмана

5.2. Решение графовых задач на основе принципа Беллмана................. 5.3. Функциональное уравнение Беллмана

5.4. Задачи распределения ресурсов

5.4.1. Классическая задача распределения ресурсов

5.4.2. Неоднородные этапы и распределение ресурсов по n отраслям

5.4.3. Распределение ресурсов с резервированием

5.4.4. Распределение ресурсов с «вложением доходов»

5.5. Расширение модели задач динамического программирования........ 5.6. Пример решения задачи распределения ресурсов

5.7. Эффективность динамического программирования

6. Нелинейное программирование

6.1. Особенности задач нелинейного программирования

6.2. Прямые методы одномерной оптимизации нелинейных функций без ограничений

6.3. Градиентные методы многомерной оптимизации

6.3.1. Классический градиентный метод

6.3.2. Покоординатный метод

6.3.3. Метод наискорейшего спуска и его модификации................ 6.4. Метод деформируемого многогранника Нелдера-Мида................ 6.5. Задача НЛП с ограничениями-равенствами

6.6. Выпуклое НЛП

6.7. Теорема Куна-Таккера для выпуклого НЛП

6.8. Квадратичное программирование

6.9. Методы возможных направлений

6.10. Метод проекции градиента

6.11. Методы штрафных и барьерных функций

6.12. Метод скользящего допуска

7. Особенности современной теории принятия оптимальных решений...... 7.1. Общая постановка задачи принятия решения

7.2.Классификация задач принятия решений

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

7.4. Определение множества Парето

7.5. Методы условной многокритериальной оптимизации

8. Игровые модели принятия решений

8.1. Основные понятия теории игр

8.2. Платежная матрица антагонистической игры, принцип минимакса

8.3. Решение игр в смешанных стратегиях

8.4. Упрощение игр и аналитическое решение игр 22

8.5. Геометрическое решение игр

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

8.7. Биматричные игры

8.8.Кооперативные игры

9. Элементы теории статистических оптимальных решений

9.1. Принятие решений при известных априорных вероятностях........ 9.2. Методы принятия решений в условиях априорной неопределенности

9.3. Планирование эксперимента при принятии решений

9.4. Многоэтапное принятие решений

10. Экспертные процедуры для принятия решений

10.1. Общая схема экспертизы

10.2. Задача оценивания

10.3. Подготовка экспертизы

10.4. Методы обработки экспертной информации

10.5. Метод Делфи для численной оценки

10.6. Строгое ранжирование

10.7. Нестрогое ранжирование

10.8. Метод попарных сравнений

Список литературы

ВВЕДЕНИЕ

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

Обычно та или иная цель может быть достигнута разными путями, но всегда важно знать наилучший из них, так как в реальных условиях приходится считаться с ограниченностью материальных ресурсов и времени, расходуемых на достижение цели. Понятие «лучший» начинает что-либо означать тогда, когда назван количественный показатель или критерий качества принимаемого решения. Например, изделие А лучше изделия В с точки зрения затрат материала; система С лучше системы D по показателю надежности и т.п.. Вот почему получение наилучших вариантов возможно только при количественном описании предметной области, т.е. на основе математической модели.

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

Большой вклад в развитие методологии исследования операций и методов оптимизации внесли российские и зарубежные ученые: Л.В.Канторович, Л.С.Понтрягин, Н.Н.Моисеев, Дж. Данциг, Г.Кун и А.Таккер, Р.Беллман, Р.Гомори и многие другие.

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

1. МЕТОДОЛОГИЯ СИСТЕМНОГО АНАЛИЗА

И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

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

Оказалось:

1) в сложных системах взаимосвязь между элементами играет большую роль, чем свойства самих элементов;

2) в таких системах элементы могут быть разнородны (оборудование, персонал, материалы, транспорт, условия поставок и сбыта и т.д.).

Термины системный анализ и исследование операций возникли, когда были образованы группы по исследованию военных операций в армии США и Англии во время второй мировой войны.

К этому времени, во-первых, был накоплен опыт применения математических методов для моделирования и решения некоторых задач экономики (В.Леонтьев, Л.В.Канторович), была теоретически обоснована возможность решения задач большой размерности на ЭВМ. Позже были созданы первые образцы таких машин. Совпали необходимость и возможность. Возникли новые идеи совершенствования организационных систем на основе математической теории игр (Нейман – Моргенштерн). Методология, сформулированная тогда и вобравшая в себя все научные достижения в области изучения сложных систем, оказалась применимой не только к боевым операциям, но и к другим сферам. Но термин «исследование операций» остался. Системный (операционный) подход – основа для изучения и совершенствования сложных систем. Применительно к специалистам - инженерам в области применения математики и информационных технологий в промышленности исследование операций формирует определенную технологию совершенствования существующих и создания новых систем как технических, так и организационных.

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

Процесс – все, что происходит в системе. Система работает, значит в ней происходит процесс.

Операция – часть процесса, которая наделена свойствами всей системы.

Операция – это управляемое мероприятие, выполняющее определенную цель, сопоставимую с целью всей системы. Например, операция составления расписания учебных занятий для учебного процесса в системе «университет».

При исследовании сложных организационных систем:

1) невозможен экспериментальный метод исследования;

2) невозможно описание поведения систем только на основе какой– либо естественнонаучной теории;

3) при описании таких систем количество факторов, которые необходимо учитывать, велико.

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

Весь комплекс работ по изучению и совершенствованию системы (операции) проводит операционная группа системных аналитиков. Этот проект проводится в интересах лица, принимающего решения (ЛПР). ЛПР может отвергнуть проект, а может принять. На рис.1 изображена примерная схема этапов операционного проекта.

4. Качественный системный анализ Методы оптимизации Дадим краткую характеристику этапов операционного исследования.

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

2.Установленные симптомы проблемы могут образовывать связанную цепочку фактов (тенденцию), которая помогает сформулировать проблему.

3.Важнейшим этапом исследования системы является четкая формулировка проблемы, которая присутствует на данном уровне жизнедеятельности системы.

4.Качественный системный анализ – это расщепление целостной системы (операции) на отдельные элементы (сущности). Для этого нужно:

- выделить изучаемую систему (операцию) из вышестоящей системы (операции);

- сформулировать цель, выполняемую системой (операцией);

- перечислить факторы, которые влияют на достижение цели;

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

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

- устанавливается критерий К – величина, количественно измеряющая степень достижения цели системы (операции);

- вводятся количественные внутренние параметры системы, которые измеряют факторы, участвующие в описании системы (операции);

- все множество этих параметров необходимо разбить на две части:

а) неуправляемые параметры (константы), которые мы в данной конкретной системе (операции) менять не можем (производительность, нормы расхода материалов и т.п.), их обозначают как коэффициенты А = (а1, а2, …, ак);

б) управляемые параметры (переменные) – величины, которые мы можем менять Х = (х1, х2, …, x n).

6. Суть математического моделирования – установление количественных связей между введенными величинами К, А, и X в виде так называемой операционной модели.

Первая часть операционной модели - это модель целевой функции, она устанавливает функциональную зависимость критерия К от неуправляемых параметров А и управляемых величин X в виде K = f(X, A). f – может быть функция, заданная аналитически, таблично или алгоритмом. В ряде практических задач в качестве элементов множества X выступают функции. В этом случае f - функционал. Задачи такого рода называются вариационными и в данном пособии не рассматриваются. Для целевой функции указывается направление улучшения критерия Этим выражением и определяется смысл оптимизации системы (операции).

Вторая часть операционной модели – математическое описание ограничений на выбор переменных Х. Все ограничения в общем виде можно записать в виде неравенств (равенств):

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

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

Модель в виде 1.1, 1.2, 1.3 – модель операционного вида или оптимизационная модель (неоптимизационная – без целевой функции).

Модель 1.1, 1.2, 1.3 позволяет поставить задачу оптимизации системы (операции) как математическую задачу: найти такие управляемые переменные Х, которые удовлетворяли бы системе ограничений 1.2, 1.3 и обеспечивали бы наилучшее значение критерия К.

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

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

9.Найденное оптимальное решение X* позволяет подготовить управляющее решение в форме документа для ЛПР.

Таким образом, операционное исследование – итерационный процесс, который сходится к определенному оптимальному решению. Рассмотренная схема является примерной. Она позволяет лучше понять смысл системного анализа и исследования операций как науки. Исследование операций (ИСО) это наука о количественном обосновании оптимальных решений на основе построения и использования математической модели. К сожалению, процесс перевода на количественное описание сложных систем и операций не является технологией. Математическая модель может получиться удачной или неудачной для получения практических решений. Вот почему знаменитый операционист Томас Саати иронично определил науку «Исследование операций» как « искусство давать плохие советы в тех практических случаях, в которых другие науки ничего не могут посоветовать».

1.3. Особенности математического моделирования операций Математическое моделирование – самый сложный этап ИСО. Математическая модель – это такое описание системы, которое позволяет специалисту выполнить цель исследования и оптимизации системы. Для одной и той же системы можно построить различные модели, чтобы выявить различные свойства: например аэродинамическая модель, прочностная модель и т.д.

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

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

1. Необходимо решить вопрос размерности модели. Если число параметров увеличить, то мы более точно отобразим реальное событие, но в модели будет трудно выявить основные свойства (наиболее значимые). Задача становится необозримой и может не иметь решения. Поэтому число переменных по возможности стараются уменьшать, оставляя главные, существенные.

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

2. Модель зависит от точности, с которой нужно получить решение.

3. Модель зависит от того, насколько мы знаем исходные данные.

4. Подход к построению модели может быть двояким:

4.1.Создание оригинальной модели (не учитывая предыдущей модели в этой области), т.е. разработка «с чистого листа». Это может дать, а может не дать хороший результат. Преимущество: «свежий взгляд на вещи», нет чужих ошибок. Но это может быть дороже и потребует большого времени.

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

- модель линейного программирования (ЛП);

- модель динамического программирования;

- игровые модели;

- модель массового обслуживания;

- модель систем управления запасами;

и многие другие.

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

1.4. Постановка задачи исследования операций в детерминированном случае и в условиях неопределенности Если в операционной модели все неуправляемые переменные А – заранее точно известные величины (const), а f – детерминированная функция, то такая модель называется детерминированной.

В некоторых задачах это не выполняется. Среди неуправляемых переменных есть такие Z=(z1, z2, …, zl), которые меняются случайно. В этом случае говорят, что операция проходит в условиях неопределенности.

K меняется не только с изменением Х и задача на максимум K становится некорректной.

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

В простейшем случае, когда f – линейная функция, можно искусственно свести задачу к детерминированной, заменив Z на M[Z], т.к. в этом случае M[K] = f(X, A, M[Z]).

Это же можно сделать, если f слабо меняется от Z. Но в общем случае это не так. В общем случае усреднение проводят по всем правилам:

где функция - плотность распределения вероятностей величин Z.

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

1.5. Пример математического моделирования операции Для демонстрации существа операционного подхода рассмотрим простой пример.

Для окраски помещения необходимо купить 15 кг краски. Эту краску можно купить в банках двух типов: по 1,5 кг, стоимостью 10 рублей каждая, или банках весом 0,9 кг, стоимостью 8,5 рублей. Для перевозки используется ящик, в который может уместиться 8 банок первого типа или 25 банок второго типа.

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

Необходимо дать графическую интерпретацию решения. Сравнить с решением, которое получится, если банка краски первого типа будет стоить рублей.

Обозначим x1 - количество банок первого типа, x2 - количество банок второго типа. Так как количество купленной краски не должно быть меньше 15 кг, то 1,5 x1 + 0,9 x2 15.

Каждая банка первого типа занимает 1/8 объема ящика, а второго 1/ часть, поэтому ограничение на объем ящика можно выразить следующим образом: x1 + x2 1.

Стоимость покупки обозначим L, она равна L = 10 x1 + 8,5 x2 min.

Получаем задачу, принадлежащую к классу задач линейного программирования (ЛП):

Если банки вскрывать нельзя, то необходимо добавить ограничения:

Задача 1.6, 1.7, 1.8, 1.9 – это задача линейного целочисленного программирования (ЛЦП).

Если количество переменных в задачах ЛП и ЛЦП большое, то их необходимо решать с использованием специальных алгоритмов (которые мы изучим) и компьютерных программ. В нашем случае – две переменные, следовательно, можно использовать простое геометрическое решение.

Рассмотрим равенства (1.7) и (1.8).

1,5 x1 + 0,9 x2 = 15 - уравнение прямой линии.

Это каноническое уравнение прямой. Построим его (рис.2). Отформ Уравнение (1.8) имеет вид Проверяя допустимость какой-нибудь точки для неравенств (1.7) и (1.8), например, точки (0; 0), определяем область допустимых решений, удовлетворяющих (1.7) и (1.8).

Изобразим линию постоянного уровня целевой функции L=const. возьмем, например, L=170, получим уравнение прямой 170 = 10 x1 + 8,5 x2.

Приведем его к канонической форме и построим 1 + 2 = 1.

Убеждаемся, что если L min, то эта прямая движется параллельно самой себе к началу координат. Оптимальной точкой будет точка выхода этой прямой из области допустимых решений.

Очевидно, что точка А является оптимальной для случая, когда банки можно вскрывать (x1 и x2 могут быть нецелыми), а точка В – оптимальная точка для целого решения.

Найдем координаты точки А, решив совместно уравнения (1.7) и (1.8):

Получим x1 = 5,8; x2 = 7,1; L* = 118,35.

Заметим, что «округленное» решение x1=6; x2=7 не является допустимым.

Оптимальное решение, которое является последним при выходе прямой L, находим из целых допустимых. Это точка В с координатами x1=4; x2=10;

L=125.

Если стоимость банки краски первого типа повысится до 17 рублей, то целевая функция будет L = 17 x1 + 8,5 x2 min.

Очевидно, что оптимальная точка будет в точке С: x1=0; x2=16,6.

Целое оптимальное решение будет x1=0; x2=17; L’=144,5.

Ответ:

1) Если банки можно вскрывать, то необходимо взять 5,8 банок первого типа;

7,1 банок второго типа, стоимость L*=118,35.

2) Если банки вскрывать нельзя, то необходимо взять 10 банок второго типа, стоимость L=125.

3) Если стоимость банки первого типа станет 17 рублей, то оптимальное решение изменится: x1=0; x2=17; L’=144,5.

2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (ЛП)

ЛП - наиболее распространенный и хорошо изученный раздел исследования операций. Изучение ЛП можно проводить в двух направлениях:

1) как развитие линейной алгебры (чисто математическое);

2) изучение конкретных моделей, приводящих к ЛП.

Впервые задача ЛП была сформулирована Л.В.Канторовичем, который применил математическую модель задачи ЛП для экономики (1939 г.). Впоследствии, в 1947 г. американец Джон Данциг разработал алгоритм решения этой задачи. С этого момента ЛП стало основным методом в системном анализе и в первую очередь в задачах экономики. В 1975г. Л.В. Канторович получил Нобелевскую премию как основоположник ЛП.

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

Пример: Задача о диете.

Имеются четыре вида продуктов П1, П2, П3, П4. Известна стоимость каждого продукта с1, с2, с3, с4. В рационе должно быть белков не менее b1; жиров не менее b2; углеводов не менее b3. Известно удельное содержание каждого вещества в единице продукта. Необходимо рассчитать рацион, содержащий необходимое количество полезных веществ и при этом, чтобы стоимость всего рациона была минимальной. Построим математическую модель:

j – номер продукта ; i – номер вещества;

aij – удельное количество в j – м продукте i – го вещества (например, а23 =30г/кг).

Введем величину хj – количество j-го продукта в рационе (управляемая переменная), величины сj, аij, bi неуправляемые параметры – константы. Выберем критерий L – общая стоимость рациона.

Тогда целевая функция и ограничения имеют вид а11 х1+а12 х2+а13 х3+а14 х4 b1, а31 х1+а32 х2+а33 х3+а34 х4 b3.

Математически эту задачу можно сформулировать так: найти такие значения х1, х2, х3, х4, чтобы они удовлетворяли системе линейных неравенств и при этом линейная функция L была бы минимальной. В компактном виде это можно записать:

Термин ЛП буквально означает линейное планирование.

Моделируя реальную задачу, мы можем получить задачу ЛП с некоторыми особенностями:

1) в одном случае L min, в другом- L max;

3) переменные могут быть любыми (как положительными, так и отрицательными).

Рассмотрим стандартную (основную) форму задачи ЛП, будем сокра- Удалено:

щенно называть ее ОЗЛП. В ней:

1) целевая функция минимизируется: L min;

2) ограничения только равенства;

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

1. Если L max, необходимо ввести L – = L, тогда если L max, то L min, и при этом arg min L = arg max L.

2. Чтобы привести неравенство к равенству, необходимо - перенести все части неравенства в одну сторону (ту, которая 0);

- полученную функцию обозначить новой дополнительной переменной, которая 0;

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

Введем дополнительные переменные у1 0, y 2 0 :

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

3. Пусть xk – переменная с любым знаком. Представим ее разностью двух положительных переменных. Тогда, если вместо xk подставить разность х k = х к х к, то остаются только неотрицательные переменные:

Таким образом, ОЗЛП в общем виде можно записать так:

В матричном виде: СX min, AX=B, X>=0.

Известно, что система линейных уравнений (СЛУ) (2.7) совместна, когда ранг матрицы А равен рангу АВ; A = {aij}, B = {bi}. Но допустимыми решениями задачи ЛП являются не все, а только 0 решения, т.к. должно выполняться (2.8). Если m = n, то может быть только одно решение; если m < n, то может быть бесчисленное множество решений, но таких, которые удовлетворяют системе (2.7). Эти точки образуют так называемую область допустимых решений (ОДР).

2.2. Геометрическая интерпретация задачи ЛП Рассмотрим частный случай n-m=2. Тогда m переменных выбираются базисными, а (n – m) – свободными. Рассмотрим такую систему, где х1, х2 свободные х3, х4,..., xn базисные Рассмотрим (2.9).

Пусть x3=0, 31х1 + 32 х2 + 3 = 0 – уравнение прямой. Значит для x3>0 точки лежат по одну сторону от этой прямой. Покажем это штриховкой.

Аналогично для других равенств (2.9). Очевидно, точки, где все штриховки пересекаются, и есть ОДР (рис. 3).

Область допустимых решений (ОДР) содержит все точки, удовлеРис 3.

творяющие задаче.

Рассмотрим теперь целевую функцию L:

Точки на прямой L = C2 лучше, чем L = C1 (в области), т.к. они дают меньшее значение целевой функции.

Оптимальное решение получается в точке выхода линии уровня целевой функции L (точка А) из ОДР. Отсюда ясно, что в задаче ЛП внутри ОДР не может быть оптимальной точки.

Выводы из геометрической интерпретации ОЗЛП.

Нет допустимого решения.

3) Если есть допустимое решение, то не обязательно есть оптимальное решение. ОДР может быть открытой, в этом случае оптимальной точки может не быть, если целевая функция изменяется, как показано в I (движемся в открытую область). Но если область открыта, то это не значит, что нет оптимального решения. Для целевой функции II оптимальное решение нахоРис. дится в точке А (рис. 6).

4) В задаче может быть бесчисленное множество оптимальных решений. Оптимальное решение будет в любой точке АВ (рис. 7).

5) Если оптимальное решение есть, то его необходимо искать в вершине многоугольника. Признаком вершины является пересечение двух прямых, т.е. равенство нулю двух переменных.

6) Если n-m=2, т.е. в ОЗЛП две свободные переменные. Тогда, чтобы попасть в вершину, можно приравнять к нулю две свободные переменные.

7) Если взять две переменные Получаем точку 2 ((х3=0) и х4 0 полупространство.

Тогда ОДР – выпуклый многогранник.

L = 0 + 1 х1 + 2 х2 + 3 x3 –> min - целевая функция (при L= const – плоскость).

Допустимые решения находятся во внутренних точках многогранника, а оптимальное, очевидно, может находиться только в вершине многогранника в точке «последнего» касания плоскости – целевой функции и многогранника, где пересекаются 3 плоскости, т.е. 3 переменных равны нулю.

Если в общем случае n – m = k, то у задачи k свободных переменных.

Следовательно, нужно искать оптимальное решение там, где k переменных равны нулю. Т.к. в вершине в особом случае может пересекаться и большее число плоскостей, то в оптимальной точке k переменных должны быть равны нулю. Заметим, что это является необходимым условием оптимального решения для задачи ЛП.

2.3. Идея симплекс-метода решения задачи ЛП Рассмотрим ОЗЛП, где базисные переменные xk+1,…,xn разрешены относительно свободных x1,x2,…,xk. Например:

(х1=х2=…хk=0) – вершина, при этом базисные переменные хk+1=4, хk+2= - 7, хn= 2.

В ОЗЛП все переменные должны быть 0, следовательно, эта вершина недопустима. Признаком недопустимости вершины является наличие отрицательных свободных членов в ограничениях равенствах. Если отрицательный свободный член есть, то надо перейти в другую вершину, для чего одну базисную переменную сделать свободной и приравнять к нулю, а какую-то свободную превратить в базисную. Следовательно, переход из одной вершины в другую осуществляется путем замены базисной переменной на свободную. Это называется симплекс-преобразованием. Если мы будем переходить из вершины в вершину «в сторону ОДР», то за конечное число таких переходов попадем в допустимую вершину. Назовем ее опорной вершиной, а соответствующее решение опорным решением.

Пусть получено опорное решение, например, для следующей задачи.

Проверим, оптимально оно или нет.

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

Видно, что увеличивать x2 можно только до х2=2, так как в противном случае х3 будет отрицательным, а это невозможно. Так мы нашли базисную переменную x3, которую надо поменять со свободной x2. Поиск этой пары для симплекс-преобразования и является основным элементом симплекс-метода.

Таким образом, симплекс-метод – это метод решения задач ЛП, который основывается на процедуре перехода от одной вершины к другой до тех пор, пока не придем в оптимальную вершину. Он состоит из трех алгоритмов:

1) Алгоритм перехода из одной вершины в другую, когда известна пара преобразования. Он пересчитывает коэффициенты системы уравнений для нового базиса. Назовем его алгоритмом симплекс-преобразования.

2) Алгоритм нахождения такой пары преобразования, чтобы при переходе в новую вершину мы приближались к ОДР. Это алгоритм отыскания опорного решения.

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

В симплекс-методе начинают со стандартной вершины (все свободные переменные равны нулю), т.е. с точки 1 (это недопустимая вершина, смотри рисунок 9). Дальше последовательно переходим из одной вершины в другую (2,3) и попадаем в опорную вершину 4.

Найдя опорное решение, мы движемся по вершинам ОДР так, чтобы целевая функция улучшалась, и при этом эти вершины были опорными (5 и 6 – оптимальная).

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

2.4. Симплекс-таблица, стандартный алгоритм Существует много форм симплекс–таблиц (СТ). Мы рассмотрим наиболее компактную форму, в которой строки – базисные переменные, а столбцы свободные переменные. Каждая СТ содержит коэффициенты модели задачи ЛП.. Для записи СТ необходимо представить ОЗЛП в стандартной форме:

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

Стандартная форма:

енты этой формы в левый ные = свободным членам.

Рассмотрим порядок вычислений для перехода в новую вершину.

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

Тогда нужно получить новую симплекс-таблицу. Для этого выполним алгоритм.

Алгоритм 1:

1. Отыскиваем в СТ элемент ij и объявляем его генеральным. Тогда i-я строка и j-й столбец – генеральные.

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

3. Все элементы генеральной строки умножаем на. Результат записываем в нижней части соответствующих клеток.

4. Все элементы генерального столбца умножаем на -. Результат записываем в нижней части клеток.

5. Отмечаем верхние элементы генеральной строки и нижние элементы генерального столбца.

6. В каждой клетке, не принадлежащей ни генеральному столбцу, ни генеральной строке, в нижнюю часть записываем произведение отмеченных элементов, стоящих в том же столбце и той же строке, что и данная 7. Переписываем СТ, заменяя в соответствии с табл. 2:

Этот алгоритм выполняется сразу после записи симплекс-таблицы.

1. Просматриваем столбец свободных членов (не смотря на свободный член строки L). Если все свободные члены 0, то данная таблица уже соответствует опорному решению, иначе переходим к п. 2.

2. В столбце свободных членов выбираем первый по порядку отрицательный элемент и в этой строке находим еще один отрицательный элемент.

Если такого элемента нет, то задача ЛП не имеет решения, если есть, то 3. Столбец с найденным отрицательным элементом объявляем генеральным.

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

5. По выбранному генеральному элементу выполняем стандартное симплекс- преобразование (алгоритм 1) и переходим к п. 1.

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

Примечание к пункту 2:

Задача ЛП не имеет решения, когда соответствующая строка СТ имеет, например, вид: y4 = 1 (2 x1 + x2 + 4 x3 ), которая не удовлетворяется ни при каких неотрицательных переменных.

2.6. Алгоритм отыскания оптимального решения задачи ЛП Этот алгоритм выполняется после того, как найдено опорное решение, то есть когда в симплекс-таблице все свободные члены 0.

Алгоритм 3:

1) Просматриваем элементы строки L (несмотря на свободный член). Если все элементы 0, то данная симплекс-таблица уже соответствует оптимальному решению, иначе переходим к п. 2.

2) В строке L выбираем наибольший положительный элемент и соответствующий столбец объявляем генеральным.

3) В генеральном столбце находим положительные элементы. Если таких нет, то задача не имеет оптимального решения, иначе переходим к п. 4.

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

5) По выбранному генеральному элементу осуществляем симплекспреобразование (алгоритм 1) и переходим к п. 1.

Примечание к пункту 2:

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

Схема алгоритмов решения задач ЛП показана на рис. 10:

Симплекстаблица отыскания опорного решения Пример:

Решить задачу ЛП L’= -х1-х2min; L’= 0 - (х1 + х2);

2/1=2; -1/-1=1(min) В таблице 4 получено опорное решение: х1=у2=0, y1=1, х2=1, y3=4, L’= -1.

В таблице 4 выполняем алгоритм отыскания оптимального решения:

В таблице 6 получено оптимальное решение:

у3 = у1= 0, у2= 5, х2= 6, х1= 4, L’= -10, Lmax= 10.

Так как в данной задаче всего две свободных переменных, то можно рассмотреть ее геометрически на плоскости (рис. 11).

Так как у1=0, у3=0, то решение находится в точке, в которой выполняются равенства: х1-х2+2=0 и 4 -х1 = 0.

На рисунке 11 показана последовательность перехода от вершины к вершине в соответствии с работой алгоритма симплекс-метода. Цифрами обозначены соответствующие симплекстаблицы. Рис. 2.7. Алгоритм получения первого базисного решения Выше было показано, что алгоритмы симплекс-метода требуют, чтобы исходная система ограничений-равенств была приведена к базису, т.е. какиенибудь базисные переменные должны быть выражены через свободные. Оказывается, что первый базис можно так же получить, используя алгоритм симплекс-метода. Для этого для каждого ограничения-равенства вводится искусственная переменная zi (i=1,m). Каждое ограничение-равенство формально записывается так:

zi =i - (gi1 x1 +... + gin xn), i=1,m, т.е. переменные zi тождественно равны нулю. Последнее равенство определяет так называемый искусственный базис.

Вводим в рассмотрение дополнительную целевую функцию для чего суммируем коэффициенты при переменных xj всех равенств zi и получаем ОЗЛП, готовую для решения симплекс-методом.

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

Пример. Пусть исходную задачу ЛП мы привели к форме ОЗЛП и получили систему ограничений-равенств Найдем первый базис, т.е. разрешим базисные переменные (их всего будет 2) относительно свободных (n-m=3-2=1). Для этого запишем Запишем симплекс-таблицу дим к таблице 8, в которой исключаем столбец z2.

В таблице 8 находим генеральный элемент и пару z1 x2, переходим к таблице 9.

Таблица 9 соответствует оптимальному решению вспомогательной задачи (2.10) и дает выражение базисных переменных x1, x2 относительно свободной переменной x3, а именно:

x2 = 2/3 + 2/3x3;

x1 = 8/3 - 4/3x3.

Теперь можно приступать к выполнению симплекс-алгоритма, записав вместо строки Lo целевую функцию задачи, выраженную через свободные переменные. Чтобы такая запись получалась автоматически можно в таблицу 7 кроме строки Lo записать строку целевой функции исходной ОЗЛП и выполнять описанный выше алгоритм, помня, что генеральный элемент не может быть ни в строке Lo, ни в строке ЦФ.

При использовании симплекс-метода некоторые свободные члены могут быть равны нулю. Это значит, что в вершине, которой соответствует CТ, равны нулю не k переменных, а больше (равна нулю и базисная). В этом случае при выборе генерального элемента отношение bi/aij будет минимальным именно для этой строки. Ясно, что соответствующую свободную переменную увеличить никак нельзя и целевая функция при переходе в новую вершину не меняется, т.к. мы остаемся фактически в этой же вершине, хотя формально перешли в новую.

Такая задача называется вырожденной задачей. Вырождение отрицательно сказывается на эффективности вычисления. Признаком вырожденности является равенство 0 некоторых свободных членов. В этом случае может произойти 2 отрицательных явления:

1. «Пробуксовка». Переходим в новую вершину, где равна нулю другая совокупность переменных, а на самом деле остаемся в той же точке. Значение ЦФ не меняется.

2. «Зацикливание» алгоритма. Через некоторое количество операций мы можем прийти к первоначальной таблице, следовательно, если алгоритм не менять, то зацикливаемся.

Существует несколько способов борьбы с зацикливанием:

• Использование степени свободы алгоритма. Например, если в алгоритме сказано: «берем первый по порядку…» - то, если обнаруживается зацикливание, можно взять «второй по порядку». Аналогично, если сказано «берем любой…».

• «Зашумление» коэффициентов задачи ЛП. Прибавляем матрицу малых случайных величин к матрице А. Получаем А +, где А – матрица коэффициентов; – матрица очень малых случайных величин. Тогда матрица коэффициентов СТ не будет содержать одинаковых чисел и после вычислений появление нулей будет маловероятным. Подробнее этот сложный вопрос освещен в специальной литературе.

Важным вопросом анализа полученного решения ЛП является анализ чувствительности решения к параметрам модели (коэффициентам целевой функции, свободным членам ограничений, коэффициентам аij). Теория этого вопроса тесно связана с так называемой двойственной задачей ЛП. Двойственная задача ЛП получается из прямой и она имеет физический смысл, когда прямая задача – задача об использовании ресурсов. Имеются ресурсы m типов в количестве b1, … bm. Для изготовления одного изделия j – го типа расходуется aij сырья i-го типа. Каждое j – е изделие продается по цене сj.

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

Можно рассмотреть эту проблему по-другому. Пусть некоторые величины i – стоимости единицы i – го ресурса. Нужно определить эти стоимости так, чтобы выполнялись неравенства, выражающие то, что стоимость затраченного ресурса на j – е изделие была бы не меньше стоимости изделия и при этом общие затраты на ресурсы были минимальны.

Задача (2.13), (2.14) называется двойственной по отношению к задаче (2.11), (2.12) Она получается из прямой (2.11), (2.12) так: коэффициенты целевой функции двойственной задачи – это правые части прямой задачи и наоборот; а коэффициенты aij – суммируются по другому индексу (матрица коэффициентов двойственной задачи это транспонированная матрица прямой задачи). Направление оптимизации целевой функции меняется на противоположное.

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

Оптимальное решение задачи ЛП находится в седловой точке:

Существует и двойственный симплекс–метод решения задачи ЛП, который в ряде случаев эффективнее прямого [1, 10].

Экономический смысл двойственной задачи: какова цена единицы каждого ресурса i, чтобы при заданных количествах ресурсов bi и стоимости единицы продукции сj обеспечить минимум общей стоимости затрат.

i называется двойственной оценкой или теневой ценой. Если решение прямой задачи найдено, то i – есть коэффициенты, стоящие в строке L в последней оптимальной CТ.

Если i > 0, то она показывает, насколько увеличивается значение целевой функции прямой задачи, если соответствующие запасы сырья i – го типа увеличиваются на единицу.

Соответствующая дополнительная переменная yi при этом равна нулю.

Это означает, что i – е ограничение выполняется точно (как равенство) и весь ресурс bi тратится полностью.

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

На рисунке 12 показано, что для ЦФ1 решением является точка А, для ЦФ3 *(при малом изменении коэффициентов cj) также точка А, а для ЦФ2 решением уже будет точка В.

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

Современные алгоритмы ЛП способны с использованием современных компьютеров решать задачи ЛП очень большой размерности. Многие из них учитывают архитектуру компьютера.

Наиболее широко известны блочные методы ЛП. При большой размерности матрица А будет содержать много нулей. В этом случае задачу можно решать по блокам. Вот почему параметрами сложности решаемой задачи ЛП являются: число переменных, число ограничений и число ненулевых коэффициентов ограничений. Число итераций симплекс- метода, за которое находится решение в большей степени зависит от числа ограничений. Современные программы ЛП имеют удобный интерфейс, позволяющий моделировать и решать небольшие задачи в удобной «математической» или табличной форме. Для решения задач ЛП большой размерности используются режимы работы с крупными базами исходных данных. Например, программа LINDO, а также приложение «Поиск решения» (SOLVER) программы Microsoft EXCEL.

3.1. Математическая модель ТЗ по критерию стоимости Симплекс–метод является общим для любой задачи ЛП. Но существуют специальные задачи ЛП, которые имеют более простой и наглядный способ решения.

Постановка транспортной задачи:

Имеется m пунктов А1…Аm отправления, в каждом из которых сосредоточено определенное количество груза (a1…am). Груз однородный, величина ai называется запасом. Имеются n пунктов назначения B1…Bn, где требуется количество груза (b1…bn); величина bi - заявка. Известна стоимость перевозки cij - из i – го пункта в j – й пункт.

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

Введем дополнительное требование – так называемое условие правильm n ного баланса:

xij - количество груза, перевозимого из i – го в j – й.

1. Наличие условия баланса (3.3) приводит к тому, что задача ТЗ всегда нумерации имеет решение.

2. Просуммировав левые части (3.2), получим (3.3), следовательно, одно уравТабуляци нение в (3.2) линейно зависимо, значит ранг системы (3.2) будет (n+m – 1). Отступ: 3. Коэффициенты при переменных в (3.2) все равны единице.

4. Подсчитаем число свободных и базисных переменных. Всего переменных mn. Базисных (m+n -1). Свободных переменных будет mn- m-n+1 =k, … k=(m-1)(n-1). Т.е. практически все переменные свободные. Т.к. ТЗ является задачей ЛП, то в оптимальном решении все свободные переменные должны быть равны нулю, т.е. большинство маршрутов не будут задействованы. Если m=100 и n=100, всего маршрутов (переменных) 10 000, но не более 199 будут задействованы.

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

В ней выполняются и все необходимые вычисления.

Пример:

Стоимость перевозки Назовем xij «перевозкой». Решение ТЗ, также как и ЛП состоит из 2 этапов:

1. Находится опорный план, т.е. допустимый план, соответствующий условию «вершины». В нем отличных от нуля перевозок не более (m+n-1).

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

Метод «северо-западного угла» (СЗУ) для нахождения опорного плана ТЗ Он заключается в заполнении плана перевозок, начиная с самих верхних (северных) пунктов отправления за счет самых левых (западных) пунктов назначения. Величина перевозки определяется выражением:

где ai' и b' - остатки запаса и заявки после предыдущей итерации. Этот способ обеспечивает линейную независимость столбцов. Свойство допустимого плана: сумма перевозок по строке равна запасу, а по столбцу – заявке.

План называется невырожденным, если отличных от нуля перевозок ровно m+n -1. В вышеприведенном примере m + n – 1 = 4 +4 – 1 = 7=7, т.е. план невырожденный.

Выполненные действия показаны в таблице Определим стоимость плана:

L=45+54+14+22+31+53+52=76.

Часто бывают такие транспортные задачи, где количество ненулевых перевозок (базисных клеток) меньше, чем m + n – 1.

Чтобы автоматически определять место для дополнения плана будем избавляться от вырожденности в процессе заполнения плана в соответствии с выражением (3.4). Вырожденность появляется тогда, когда в формуле (3.4) будет ai\=bj\. В этом случае будем считать, что в строке ai\=ai\ + (0).

В методе СЗУ мы не использовали стоимость перевозок. Существуют методы, которые позволяют получить первый план сразу близким к оптимальному (т.е. с достаточно малой общей стоимостью перевозок).

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

Метод не обязательно гарантирует лучшее решение, чем метод С ЗУ, но, как правило, дает лучшие результаты.

Способ борьбы с вырождением такой же, как и в предыдущем методе.

Пример: Начинаем с самого дешевого маршрута (А1В4), далее в столбце В4 ищем самый дешевый (А4В4), затем в строке А4 минимальная стоимость в маршруте (А4В2) и т.д.

L=91+12+24+38+51+42+12=58.

3.3. Оптимизация плана ТЗ, распределительный метод Если в плане есть свободные клетки, для которых стоимость меньше, чем в базисных клетках, то можно передвинуть какую – либо перевозку в эту свободную клетку, но чтобы баланс не нарушался, нужно из строки или столбца, где будет новая базисная клетка, убрать такое же количество груза. Будем ставить (+) там, где перевозка увеличивается и (-) там, где уменьшается.

Пример:

Т.е. необходим перенос по циклу. Назовем циклом замкнутый маршрут, который показывает перенос груза по некоторым клеткам таблицы. В цикле всегда четное число вершин.

Назовем ценой цикла алгебраическую сумму стоимостей перевозок cij, стоящих в вершинах цикла с соответствующими знаками. Цена показывает, насколько увеличится стоимость перевозок в плане, если по данному циклу переносится единица груза. Если bj.

1. ТЗ с избытком запаса:

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

Чтобы учесть фиктивность перевозки, достаточно считать, что стоимость перевозки в фиктивный пункт Вф равна нулю, сiф=0. Тогда, если какие-то перевозки хiф>0, то ci i = 0.

Таким образом, чтобы решать ТЗ с избытком запаса, нужно к таблице прибавить дополнительный столбец Вф, заявка которого b = ai b j, а сiф=0, i = 1, m. Тогда для новой таблицы будет выполняться условие правильного баланса. После этого задача решается любым способом.

2. ТЗ с избытком заявок:

Необходимо ввести фиктивный пункт отправления (Аф), в котором якобы есть недостающий запас a = b j ai, при этом сфj=0, j = 1, n. После этого задача решается обычным способом.

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

Иногда задача решается по-другому. Пусть вычислить коэффициент дефицита:

После этого каждую заявку можно скорректировать:

При этом можно решать задачу с учетом приоритетов на заявку. Величина приоритетов j-го пункта назначения (dj) может быть от 0 до 1 (0dj1).

Чем меньше dj, тем выше приоритет.

– величина дефицита.

Пример:

Если ограничение (4.37) не выполняется, то переходим к следующему вектору, в противном случае – к ограничению (4.35). Если новый вектор удовлетворяет всем ограничениям, то, подставляя его в (4.34), получим новый рекорд Z* и формируем новое фильтрующее ограничение, заменяя Z* на Z**. Если пройден весь список, то последний рекорд даёт решение. При Наконец находим новое рекордное значение (1111); z=5. Т.к. список исчерпан, то последний рекорд – это оптимальное решение. Отформ Эффективность процесса можно оценить количеством значков в таблице.

В современных алгоритмах (например, в алгоритме Лемке-Шпильберга) порядок перехода от одного вектора к другому меняется в соответствии с анализом коэффициентов модели задачи:

1. Критерий недопустимости – запрещает двигаться к некоторым векторам, которые заведомо недопустимы.

2. Проверяются целевые функции – множеству дается оценка (подробнее см.[7,10,23]).

0 1 0 0 - всех двоичных векторов. Подмножество множества N, состоящее из таких элементов j, что каждому j поставлено в соответствие x j {0,1}, называется частичным решением, а множество индексов обозначим V.

1 0 1 1 + - + Переменные xj, номера которых не принадлежат этому подмножеству, называются свободными, множество индексов свободных переменных обозначим S.

Пример: Вектор переменных (x1, x2, x3, x4, x5) N=(1, 2, 3, 4, 5), (x1, 0, 1, x4, x5) - частичное решение, V=(2, 3), S= (1, 4, 5) - номера свободных переменных.

Если частичное решение содержит k переменных, то существует 2n-k различных дополнений частичного решения.

Пусть каким – то образом выбрано частичное решение, содержащее k переменных, тогда проверка 2n-k его дополнений на допустимость по условию (4.35) называется зондированием.

Если до этого получен рекорд Z* и если удаётся установить, что для какого – то частичного решения не существует допустимого дополнения, приводящего к лучшему рекорду, то говорят, что частичное решение прозондировано, т.е. что это подмножество можно отсеять.

Балаш установил, что если V определяет переменные зондированного решения, а Z* - ранее достигнутый рекорд, то зондируемое решение x не Проверим наличие допустимых дополнений для выбранного частичного решения.

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

В общем случае это комбинация всех строк ограничений.

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

Пример:

Пусть задача состоит из такого решения x1, x2, …, x5, которое имеет ограничения:

Разобьём участок от h0 до h1 на n частей:

Известен расход горючего при переводе системы на h при v=const и на Удалено v при h=const. Таким образом, из каждого состояния есть лишь два управУдалено ления.

Начиная с конца помечаем все узлы (состояния) величинами условных (для данного узла) оптимальных расходов горючего от этого узла и до конца, Отформ a стрелками условные оптимальные управления. Указанные действия в упУдалено рощенном виде демонстрируют рассмотренную процедуру решения на осноОтформ ве уравнения Беллмана. Дойдя от конечного состояния до начального и получив 22, мы получим минимальную величину потерь горючего. Идя по Удалено стрелкам от начального состояния до конечного, мы получаем безусловные оптимальные управления (показаны двойной линией).

Видно, что любая задача, сводящаяся к поиску минимального пути в 5.3. Функциональное уравнение Беллмана Назовём состоянием системы вектор координат: S = (1, 2,..., L ). В не- Удалено которых задачах состояние - одна величина. Тогда работу системы можно Отформ представить как движение в фазовом пространстве - пространстве состояний. Удалено Назовём шаговым управлением - управление на i-м шаге. Рассмотрим процесс управления системой за m шагов. Функция i (S, U i ) называется выиг- Отформ рышем на i-м шаге. Здесь S-состояние перед i-м шагом, а Ui - управление на Величина i (S, U i ) должна быть известна до начала динамического про- Удалено граммирования. Если состояние перед i-м шагом было S и мы приняли какое- Отформ то управление Ui, то система перейдёт в новое состояние S = i ( S,U i ). Эта функция должна быть так же известна. Если эти функции не заданы, то их Отформ надо сформулировать. Введём функцию Wi(S) - условный оптимальный выУдалено игрыш. Это выигрыш на всех этапах от i до конца, если i-й шаг начинается с Рассмотрим m шагов. Пусть с (i+1)-го шага мы системой управляем оп- Удалено тимально, тогда величина выигрыша будет такая - Wi +1 ( S ). Применим на i-м Удалено шаге произвольное управление Ui, тогда Wi ( S ) - неоптимальный выигрыш, т. к. на i-м шаге мы применяем неоптимальное управление Ui. Чтобы от i-го шага и до конца получить оптимальный выигрыш, нужно изменять Ui так, Это функциональное уравнение Беллмана. Для использования уравнения получаем последовательно:

Придя в начальное состояние W1(S), мы можем подставить S=S0 и W1(S0)=Wmax ловные оптимальные уравнения, идя от начала к концу по цепочке:

U1*,U 2,...,U m ;Wmax.

5.4.1. Классическая задача распределения ресурсов Распределение ресурсов - это едва ли не самая распространённая операция. Под ресурсом в общем случае понимают физическую или абстрактную величину, которую система использует для производства полезного продукления та. Например: горючее, деньги, время, объём склада. Как правило - ресурс ограничен, поэтому встаёт задача так распределить ресурс между отдельныразрежен ми элементами системы, чтобы суммарный эффект был максимальным. Расуплотнен смотрим классическую задачу распределения ресурсов.

Имеется начальное количество ресурсов k0, которое необходимо распределить между двумя отраслями. Каждая отрасль работает в течении m лет. Если в Отформ первую отрасль в i-й год вкладываются средства Xi, то доход f(Xi), если же во вторую вкладываются Yi, тогда доход g(Yi). Средства тратятся, принося доход, а новых средств не поступает и полученный доход не вкладывается.

Суммарный выигрыш равен сумме выигрышей на каждом шаге. СостояШрифт:

нием системы является количество средств перед i-м шагом. Так как новых Управление Yi может быть записано как Yi=k-Xi. После i-го шага в первой Отформ отрасли остаются средства ( X i ), а во второй (Yi ) = ( k X i ). Эти функУдалено ции называются функциями траты. Мы можем составить уравнение Беллма- ются…о… на. В этой задаче на i-м шаге одно управление Xi и одно состояние k.

пускает геометрическую интерпретацию:

распределении ресурсов.

5.4.2. Неоднородные этапы и распределение ресурсов по n отраслям Выше мы считали, что все функции одинаковы на всех этапах. Во многих не меняется. Запишем уравнение Беллмана:

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

может быть выражено как: X = k X i. В этом случае в правой части уравнения Беллмана будет две или более переменных, по которым ищется Начальное количество средств разделяется на первом этапе на X1 и на Отформ k - X1 (резерв), на втором этапе подлежат распределению оставшиеся средства и из резерва. Такую задачу можно представить с одной реальной отраслью, а другой - фиктивной (не приносящей доход и не расходующей средства). На рисунке 27 показаны графики распределения ресурсов с ре- Удалено зервированием и в дополнение к этому с нулевыми функциями трат. Отформ Решение такой задачи сводится к классической, задав функции дохода и трат в виде:

Задача с резервированием в одной отрасли при нулевых функциях траты. подчерки В этом случае задача сводится к более простой:

Рассмотрим более частный случай - все функции одинаковые на всех шагах.

Пусть эти функции неубывающие, тогда недоиспользование средств невыгодно и в ограничении можно поставить равенство: Удалено 1 Если функция f (x) неубывающая и выпуклая вверх, то оптимальным распределением является равномерное распределение: xi=k0/m.

2 Если функция f (x) неубывающая и выпуклая вниз, то оптимальным распределением является такое - все распределение в один этап (элемент) и ничего в другие: xr=k0, xi=0 для всех i, кроме i=r.

Покажем это на графических примерах.

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

Так как оставшиеся средства и доход объединяются, то можно ввести единую интегральную функцию - функцию изменения средств F(Xi) - количестУдалено во оставшихся средств плюс доход после i-го шага, если вложили Xi.

Выигрыш на i-м шаге зависит от того, как мы подсчитываем доход (эф- Удалено фект) от управления всеми ресурсами. Поставим задачу: максимизировать доход в конце m-го шага. Тогда на всех шагах i = 1, m 1, доход = 0, Wi = 0.

На m-м шаге выигрыш Wm = Fm ( X m ) + Gm ( k X m ). Подставив эти выражения Отформ в уравнение Беллмана, мы программируем задачу от начала к концу, если Удалено имеется начальное количество средств k0. Здесь функция траты:

Рассмотрим частный случай: когда F и G неубывающие функции. В этом случае, чем больше значение доход + средства получается в конце i-го шага, Отформ тем лучшим условием это будет для проведения (i+1)-го шага. Поэтому мож- Удалено но не заботиться о следующих шагах, достаточно обеспечить максимум на Таким образом, процедура оптимизации возможна в одном направлении от начала к концу, т. е. задача динамического программирования вырождаетОтформ ся в задачу последовательной оптимизации.

дохода и функции траты:

и максимизируем суммарный отчисленный доход + оставшиеся средства после m-го шага. Введём функцию отчисления ri ( Di ) ; D-доход. Тогда выигУдалено:

рыш на каждом шаге:

для i=m надо учесть (5.3).

Если ri=1, то мы получаем классическую задачу.

5.5. Расширение модели задач динамического программирования Учёт предыстории процесса Мы считали, что все функции, как выигрыша, так и траты, зависят от состояния перед i-м шагом, т. е. не зависят от более ранних состояний. Такие Отформат процессы называются процессами без памяти. Но иногда при рассмотрении некоторых процессов требуется помнить всю историю происходящего (наУдалено:

пример, в задачах ремонта и замены оборудования). Такая задача более Si-L - состояние за L шагов до i-го. Тогда, считая аргументы векторами, функции не меняются i ( S, U i ), i ( S, U i ). Но задача становится сложней в Удалено вычислительном аспекте. Пусть S имеет k координат и предыстория распространяется на L шагов, тогда в результате число переменных будет kL. Вот Отформ почему подобные задачи практически можно решать если kL3.

ДП для задач со многими ограничениями Пусть в задаче распределения ресурсов есть два ограничения (два ресурса).

Введем два параметра состояния K1 и K2. Тогда функции условных оптимальных выигрышей и условных оптимальных управлений будут иметь по Удалено два аргумента W(K1, K2); xi(K1, K2). Уравнение Беллмана для решения такой задачи имеет вид При этом величина Xi на каждом этапе варьируется в пределах от нуля до величины di :

di= min(K1/a1i ;K2/a2i) Видно, что для двух ограничений, если каждая из величин K1, K2 может Отформ принимать 102 значений, то функцию Wi(K1,K2) приходится табулировать в 104 точках. Таким образом, наиболее серьезным препятствием для практичеУдалено ского применения ДП является число параметров задачи, что заставило Р.Беллмана заявить о так называемом «проклятии многомерности». Некото- Удалено Задача с мультипликативным критерием До сих пор мы считали, что суммарный выигрыш равен сумме выигрышей, полученных на i-х шагах. Но есть задачи, где общий критерий равен Отформ произведению критериальных величин на каждом шаге:

В этом случае так же можно применить уравнение Беллмана, но вместо этого можно взять функцию W = ln W. Оптимальные решения будут одина- Отформат ковы ввиду монотонности логарифмической функции. Но можно при выводе Удалено:

Т.о. метод ДП применим в случае, когда аргументы в критериальной функции разделяются (смотри вышеприведенное выражение) Пример: устройство состоит из n узлов. Имеется некоторый ресурс k0, который может использоваться для повышения надёжности каждого узла. Удалено:

Необходимо так распределить ресурс, чтобы суммарная надёжность была Отформат максимальной. Получаем задачу Во многих задачах распределение ресурсов не связано с временными ша- Отформат гами. Ресурс распределяется по объектам. Например, если рассмотреть рас- eq пределение ресурсов между n объектами, когда на каждый объект задана функция выигрыша, то такая задача эквивалентна рассмотренной нами зада- Отформат че о распределении ресурсов с резервированием в одной отрасли по n шагам. Удалено:

Это наиболее распространенная задача распределения ресурсов, поэтому 5.6. Пример решения задачи распределения ресурсов Рассмотрим пример. Завод получил 4 новых станка, которые необходимо распределить между тремя цехами. Известна дополнительная прибыль, которая получится в i-м цехе, если туда поставят хi станков – f(хi). Отформат Состоянием является оставшееся (текущее) количество станков (k).

Пусть мы распределяем оставшиеся k станков. Начинаем с третьего (последнего) цеха:

стояние известно, то для Сравним по числу необходимых операций динамическое программировыше на вание с простым перебором всех вариантов для задачи Переход от отрезка [an-1; bn-1] к отрезку [an; bn] методом деления отрезка пополам иллюстрируется на рис. 35а, если F(X1(n-1))< F(X2(n-1)),и на рис. 35б, если F(X1(n-1))>F(X2(n-1)).

Полагая x* = (an+ bn)/2, находим X* с абсолютной погрешностью, не превосходящей величины n =(bn- an)/2=(b-a-)/2n+1+/2.

Кроме этих методов известны и другие, более эффективные методы, такие как: метод Фибоначчи, метод золотого сечения, метод поиска по дискретным точкам [12, 25].

6.3. Градиентные методы многомерной оптимизации Если ограничения в задаче НЛП отсутствуют, то применяют все методы оптимизации нелинейных функций. Причём, если в задаче с ограничениями решение гарантированно находится внутри области, то его можно найти этими методами, так как эти ограничения не являются активными и их можно отбросить. Рассмотрим наиболее широко применяемые методы оптимизации нелинейных функций многих переменных – это так называемые поисковые методы. Здесь поиск оптимальной точки начинают из начальной точки (ее выбирают из некоторых знаний о примерном месте нахождения решения). Далее в соответствии с некоторым разумным правилом переходят в новую точку с лучшим значением ЦФ и т.д. до тех пор, пока не выполнится некоторое заранее заданное правило остановки, например выполнение условия по точности.

В этом методе поиска каждая последующая точка получается путем перехода по вектору градиента, т.е. по нормали к линии уровня. Длина шага выбирается из двух основных условий: если длина шага очень большая, то можно перейти точку экстремума, если очень маленькая, то количество шагов от начальной точки до оптимальной будет очень велико. Поиск начинается из начальной точки X0. Точка X(k+1) ищется по формуле X(k+1)=X(k)±(k)g(X(k)), (+) – если F(X) max и (-) – если F(X) min, где g(X(k)) – градиент в точке Xk, - множитель, определяющий длину шага. В координатах X(k+1) = X(k) + (k) ( F ) k. Величина (k ) может в простейj j шем случае не изменяться по мере движения (k)= = const.

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

Для простоты можно считать, что X является точкой экстремума, если max ( Ясно, что этот метод можно применять в том случае, когда можно хотя бы численно вычислить градиент функции в точке. Заметим, что для гладкого оптимума при приближении к оптимальной точке величина градиента автоматически уменьшается, поэтому даже при постоянной величине длина шага уменьшается, что является желательным для любого поискового метода.

В этом методе движение из начальной точки производится сначала вдоль первой координаты x1. Знак направления совпадает с направлением проекции градиента на эту координату (для F(X) max) или противоположен ему, если F(X) min. Конец шага определяется точкой, где F =0. Затем движеX ние производится по второй координате X2, затем по X3 и т.д., и, наконец, по Xn. Затем повторяют движение опять по X1, X2 и т.д. Можно использовать следующее правило остановки: max ( 6.3.3. Метод наискорейшего спуска и его модификации В этом методе из некоторой начальной точки движение осуществляется вдоль направления градиента до тех пор, пока производная по этому направлению не будет равна нулю. Далее из этой точки определяем новый градиент Эту вспомогательную задачу одномерной оптимизации можно решать на основе рассмотренных методов прямого поиска (дихотомии и т.д.) Наискорейший и покоординатный методы называют методами с длинным шагом. Кроме этого существуют методы, использующие вторую производную для определения длины шага, например, метод Ньютона:

где [F”(Xk)] -1 - обратная матрица вторых производных в точке Xk.

6.4. Метод деформируемого многогранника Нелдера-Мида Современные методы поиска минимума (максимума) нелинейной функции чрезвычайно разнообразны. Одним из наиболее эффективных является метод Нелдера-Мида. Идея метода состоит в том, что для определения направления движения вычисляются значения целевой функции в вершинах сначала правильного, а затем деформируемого многогранника. Многогранник - некоторое тело в n-мерном пространстве. Правильный многогранник называется симплексом, в задачах для двух переменных - это правильный треугольник.

Вычисленные значения целевой функции в вершинах симплекса сравниваются, а затем выполняются операции:

1) отражение - поворот симплекса через одну из сторон;

2) растяжение - если идём в правильном направлении;

3) редукция - возврат назад, если перескочили оптимум;

4) сжатие - уменьшение сторон, чтобы движение было с более мелким 1. Выбирается начальный симплекс (если в задаче 2 переменные n=2, то симплекс–правильный треугольник). Его вершины X i( 0), i = 1, n + 1. Обозначим X hk ) - самая худшая точка, т.е. для F ( X ) min, F X nk ) = max F ( X ik );

X l( k ) - лучшая точка, т.е. F X l( k ) = min F ( X ik );. X 0k ) - центр тяжести всех вершин, исключая X, его координаты 2. Осуществляют отражение (проектирование) X hk ) через центр тяжести, новая точка получается так:

где - коэффициент отражения. Обычно =1.

Если для полученной точки F X b k ) < F X l( k ), то X hk ) заменяется на X b ), и переходим к пункту 2. В противном случае заменяем X h и переходим к пункту 2.

Если F X k ) > F X hk ), для всех ih то вектор X hk ) X 0k ) сжимается, Точка X hk ) заменяется на X k ), и переходим к выполнению пункта 2.

(обычно =2) - редукция X i( ) = X lk + Возвращаемся к пункту 2. Правила остановки могут быть различными, например, для простоты можно использовать правило:

Например:

выберем параметры:

решение видно из рисунка 38.

Подробнее смотри в [16].

В НЛП особо рассматриваются задачи с ограничениями-равенствами.

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

где F(X) - целевая функция, i – множители Лагранжа, имеющие смысл коэффициентов чувствительности ограничений.

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

После выполнения операций дифференцирования получаем систему в общем случае нелинейных уравнений относительно неизвестных Xi и i множителей Лагранжа.

Решение системы (6.4) дает точки подозрительные на экстремум, и их ещё надо проверить с помощью достаточных признаков экстремума. Рассмотрим некоторые из этих признаков.

1) Пусть X - точка подозрительная на экстремум, полученная с помощью выражений (6.4). Рассмотрим матрицу Гессе – матрицу H вторых производных в точке X*:

Если эта матрица определена положительно, то точка X* -минимум, а если определена отрицательно, то максимум. Если же матрица Гессе знаконеопределена, то в этой точке экстремума нет, а если полуопределена, то этот признак не даёт ответа на вопрос.

2) Пусть Dk - главный определитель матрицы Гессе k-го порядка.

а) если D1 > 0, D2 > 0, D3 > 0,K - это достаточный признак минимума;

б) если D1 < 0, D2 > 0, D3 < 0,K - достаточный признак максимума (знаки строгих неравенств чередуются);

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

3) Наиболее «сильным» достаточным признаком является следующий.

Составим расширенную матрицу Гессе HB, для чего используем матрицу производных от функций ограничений:

Q - транспонированная матрица.

Матрица HB имеет размерность (m+n)(m+n).

Признак: точка X* соответствует максимуму, если начиная с главного определителя порядка m+1, последние n-m определителей матрицы HB образуют знакопеременный ряд, а знак определителя стоящего на (n-m)-м месте от конца совпадает с знаком: если (-1)m+1, то max; если (-1)m, то min.

Например: n=3, m=2, n-m=1, проверяем D5;

Пример:

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

Запишем матрицу H B :

Начиная со второго определителя (m+1=2) знаки чередуются:

Проверяем: D3 >0, значит в точке X1=X2=1/2 находится максимум.

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

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

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

Таким образом, СEn выпукло, если Важно: если Сi - выпуклое множество, то С= Сi также выпукло.

Т.е. если каждое ограничение в задаче НЛП образует выпуклое множество, то и все ограничения дают выпуклое множество.

Дважды дифференцируемая функция F(x) является выпуклой в том и только в том случае, когда Для любых xM, M - выпуклое множество и хi и хj не обращается в нуль одновременно. Для проверки выпуклости F(X) используется критерий Сильвестра:

Функция F(X)- выпукла, если неотрицательны (для строго выпуклой положительна) все главные миноры матрицы Гессе:

Если все k>0, то F(X) - строго выпукла.

Функция F(X) n переменных ||X1, X21,…, Xn|| = X G называется выпуклой функцией в выпуклой области G, если для любых двух точек выполняется соотношение F{ X (1) + (1 ) X (2) } F ( X (1) ) + (1 ) F ( X (2) ), где 00, значит в качестве генерального надо выбрать этот j-й столбец, строку надо выбрать ту, для которой вычисляется величина.

Запишем все матрицы, которые нам нужны:

Запишем условие Куна-Таккера, определяемое выражением (1): Код пол Чтобы записать симплекс-таблицу, надо выразить базисные переменные через свободные. Для получения первого базисного решения используется любой метод, например, метод Гаусса. Можно использовать метод искусственного базиса (см. главу 2), который использует симплекс-процедуру. Затем нужно получить опорное решение, и только после этого записать модифицированную симплекс-таблицу. Для простых задач можно подобрать первое базисное решение так, чтобы сразу получить опорное решение (свободные Запишем симплекс-таблицы по методу Баранкина-Дорфмана.

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

В первой таблице T= а0=24, а во второй 4. Чтобы не вычислять всю третью таблицу подсчитаем а0 для следующей таблицы по формуле T= 2*4+1/ (-8)=0, значит следующая таблица оптимальная. Вычислим только необходимые элементы (свободные члены), получим; X1=3/2; X2=1/2;

Y1=V1=V2=1=0; Оптимальное значение F = -11/2.

Недостаток метода: иногда встречаются задачи, когда все Kj>0. Значит, мы будем переходить в новую вершину, а значение T будет увеличиваться. В этом случае идём на временное ухудшение T (проходим через «мёртвую зону»). В методе Франца-Вульфа это учтено [1,7,12,16].

Наиболее распространенным классом методов решения выпуклых задач НЛП являются градиентные методы, которые отличаются как способом получения последующей точки, так и способом «обработки» ограничений.

В методах возможных направлений переход от точки Xk к точке Xk+1 осуществляется по направлению Sk, не обязательно вдоль градиента. При этом движение вдоль Sk должно быть таким, что бы новая точка принадлежала области допустимых решений D. Направление, удовлетворяющее этому условию, называется возможным или допустимым:

Таких направлений множество; среди возможных направлений выбирают такое, для которого скалярное произведение градиентов в точке k и этого наУдалено правления больше нуля (для задачи минимизации меньше нуля). Такое наОтформ правление называется подходящим. Таких направлений в общем случае так же множество. Г.Зойтендейк предложил выбирать то, которое максимально увеличивает значение целевой функции.

Обозначим область допустимых решений через D, пусть x0- начальная точка, а X* - единственное решение задачи, X0 D, x0x*.

Переход из точки X(k) в X(k+1) осуществляют по такому направлению S(k), Обозначим g0(X) и gi(X) градиенты функций F(X) и i(X) в точке X соответственно. Обозначим I(X) множество индексов I таких, что i(X)=0; I(X) указывает номера ограничений, выполняющихся в точке X точно (I(X) - активные ограничения).

Знак (•)’ обозначает транспортированный вектор (матрицу).

корень уравнения (,S)=0 (если нет решения, то Ci= ). Таким образом, ’ выбирается из условия невыхода из области D, а ’’ из условия Направление S, удовлетворяющее условию (6.15), и называют возможным (допустимым) в точке x0. То из возможных направлений, для которого, кроме этого, выполняется условие, называется подходящим, так как при движении в этом направлении значения целевой функции улучшаются, Далее находится направление S из подходящих направлений, которое обеспечивает максимально возможное увеличение целевой функции, т.е. на каждом шаге решается вспомогательная задача Для нормализации длины вектора S используют следующие условия:

Видно, что условие (6.17) уже содержится в N5. Точка X*, является решением, как только любых выпуклых функций F(x) и i(x), но он может не дать решения за конечное число шагов. Для задачи квадратичного программирования можно с использованием принципа сопряженности обеспечить сходимость за конечное Рассмотрим этот случай. Если x есть внутренняя точка, т.е.

, то новое искомое S должно удовлетворять, помимо условия нормировки, еще одному условию сопряженности, где C - положительно полуопределенная матрица квадратичной формы для задачи квадратичного программирования:

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

Рассмотрим пример с нормирующими условиями N5 для задачи квадратичного программирования (6.18), (6.19). Для нее:

Длина очередного шага определяется из соотношения:

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

Подставим выражение градиента, получим Отсюда получаем Величина для N5 всегда равна 1.

На рис.42 изображена иллюстрация поиска решения для примера Для решения неквадратичных задач НЛП принцип сопряженности уже неприменим и для построения алгоритма, сходящегося к решению, приходится применять процедуру изменения длины шага. Рассмотрим такой алгоритм по методу возможных направлений Зойтендейка. При выборе подходящего направления будем принимать во внимание не только те ограничения, которые в данной точке выполняются точно, но и те, которые выполняются «почти точно». В противном случае может измельчаться вдали от точки минимума. Для и определим теперь – активное индексное множество. Это те i, для которых методом Зойтендейка необходимо выполнить условия невыхода из D, нормировки длины вектора S и условия большего возрастания (убывания для задачи на минимум) целевой функции. В алгоритме, излагаемом ниже, последнее требование заменятся требованием выбора направления, имеющего наибольший угол к касательным с ограничениями вблизи точки x(k), что дает возможность двигаться с большим шагом, не выходя за пределы D, а длина этого шага выбирается из условия наибольшего увеличения (уменьшения) F(x). В качестве нормировки выберем N2. Тогда для задачи минимизации для заданного в точке x необходимо определить величину из условия Более подробно алгоритм решение и примеры можно найти в [7, 16].

На каждой итерации этого метода предусмотрена процедура возврата очередного приближения градиентного спуска на допустимое множество U, если. Такой возврат производится посредством проектирования на U, т.е. замены на ближайшую точку множества U.

если Таким образом, в методе проекции градиента последовательные приближения x(k) к точке минимума X* целевой функции f(x) на множестве U вычисляются по формулам В зависимости от способа вычисления ak из (6.20) различают несколько вариантов метода проекции градиента, самыми распространенными из которых являются следующие.

предположении, что градиент f (k) целевой функции удовлетворяет на множестве U условию Липшица, т.е.

число из интервала (0;2/L). Если известна минимальная константа Липшица L из (6.21), то выбирают, как правило, =1/L.

Вычисления по формуле (6.20) завершаются при выполнении одного из самостоятельной задачей нелинейного программирования:

решение которой может вызвать затруднения.

В частном случае, когда множество U определяется лишь линейными ограничениями, задача (6.22) представляет собой задачу квадратичного программирования. Ее решение может быть найдено за конечное число шагов, как описано выше.

Особый интерес при использовании метода проекции градиента представляют такие множества U, для которых задача проектирования (6.22) решается в явном виде.(U - шар, параллелепипед и т.д.) Иногда, как в примере с шаром, нахождение кратчайшего расстояния приводит к задаче на условный экстремум Если область допустимых решений U - параллелепипед, то проекция точки определяется очень просто. Пусть область U определяется условиями:

a1 min,