WWW.DOC.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные документы
 

Pages:   || 2 | 3 |

«В. А. Горелик, Т. П. Фомина «Основы исследования операций: Учебное пособие» Москва, МПГУ, 2004 Рекомендовано УМО по специальностям ...»

-- [ Страница 1 ] --

В. А. Горелик, Т. П. Фомина

«Основы исследования операций: Учебное пособие»

Москва, МПГУ, 2004

Рекомендовано УМО по специальностям педагогического образования для

студентов вузов по специальности 030100 Информатика.

Электронная PDF-версия издания подготовлена в 2011 году для сайта кафедры ТИДМ математического факультета МПГУ — http://tidm.ru

ВВЕДЕНИЕ

Принятие решений всегда было и остается наиважнейшим аспектом

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

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



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

Перед исследованием операций стоят следующие проблемы:

• составление математических моделей задач принятия решений;

• вопросы существования оптимальных решений в различных классах задач;

• разработка необходимых и достаточных признаков оптимальности в различных классах задач;

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

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

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

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

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

Глава 1. ОСНОВНЫЕ ПОНЯТИЯ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ

–  –  –

Изложение любого предмета начинается с определения или описания используемых в нем основных понятий. В исследовании операций естественно надо начинать с самого понятия «операция».

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

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

Оперирующей стороной (ОС) называется совокупность лиц, которые стремятся в данной операции к поставленной цели.

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

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

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

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

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

а) фиксированные;

б) случайные;

в) неопределенные.

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

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

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





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

Ход операции можно описать некоторым набором фазовых переменных 1 t,, k t. Степень соответствия хода операции поставленной цели в математической модели характеризуется критерием эффективности W, который представляет собой некоторую функцию, зависящую от фазовых переменных, стратегий и неконтролируемых факторов. В математической модели эквивалентом цели операции является требование максимизации критерия эффективности.

Существует много различных классификаций математических моделей.

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

W=F(x,y). (1.1) Переход от динамической формы модели к статической называется нормализацией. Фактически в ходе исследования можно сразу строить статическую модель, минуя динамическую. Несмотря на внешнюю простоту выражения (1.1), связь между значениями критерия, стратегии и неконтролируемого фактора может быть весьма сложной. Иногда ее не удается представить в явном виде, тогда она задается с помощью промежуточных соотношений или в виде вычислительного алгоритма.

С учетом сказанного, получаем математический объект {W, x, y}, где xX – множество (пространство) допустимых стратегий, yY - множество значений неконтролируемых факторов. Он называется статической (нормальной) формой математической модели операции.

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

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

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

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

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

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

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

Здесь:

ОС – руководство фирмы;

цель – максимизация дохода от продажи выпущенных за сутки изделий двух видов;

принятие решения для ОС состоит в определении суточных объёмов выпуска каждого из двух видов изделий;

возможности ОС ограничены временными ресурсами эксплуатации станков трёх видов.

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

В нашем примере известными являются следующие параметры:

суточная норма bj эксплуатации станка j, j 1,2,3;

время aij обработки единицы изделия вида i (i=1,2) на станке типа j (j=1,2,3);

стоимость ci (продажи) единицы изделия вида i (i=1,2).

Все эти параметры являются неуправляемыми (неконтролируемыми) факторами, т.к. они заданы, то это фиксированные неконтролируемые факторы.

Неизвестными или искомыми являются следующие величины:

объём суточного выпуска изделия вида i (i=1,2).

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

Введем систему обозначений неизвестных параметров задачи:

xi – объём суточного выпуска изделия вида i (i=1,2).

Тогда доход от продажи x1 и x 2 c1 x1 c 2 x 2, а время, необходимое для обработки x1, x2 единиц изделий на станке j, есть a1 j x1 a2 j x2 ( j 1,2,3).

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

c1 x1 c 2 x 2 max

–  –  –

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

Возникает вопрос:

на основании чего сравнивать стратегии. На первый взгляд ответ прост — с помощью критерия эффективности, который собственно для этого и задается.

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

Для того чтобы иметь возможность сравнивать стратегии, удобнее всего иметь численную оценку каждой стратегии. Оценка, ставящая в соответствие каждой стратегии х действительное число, т.е. являющаяся функцией переменной х, называется оценкой эффективности стратегии. Если имеется только фиксированный неконтролируемый фактор, т.е. у принимает известное исследователю операции значение у0, то критерий эффективности W=F(x,y0) является функцией только х. Введем обозначение f0(х)=F(x,y0). Величина f0(х) может служить оценкой эффективности стратегии. При этом стратегия х1 лучше стратегии х2, если f0(х1) f0(х2). Естественным образом определяется в этом случае и наилучшая или оптимальная стратегия. Это такая стратегия х0, для которой выполняется соотношение f0(х0) f0(х) хХ (1.2) (при наличии только фиксированных неконтролируемых факторов стратегиифункции не имеют смысла, поэтому пространство стратегий может включать лишь стратегии-константы, такое пространство стратегий принято обозначать через Х).

Пусть теперь имеются случайные или неопределенные факторы. В этом случае для фиксированной стратегии х* критерий эффективности W=F(x*, y) является функцией от у, а не фиксированным числом, и значит не может служить оценкой эффективности. Каждой стратегии уже соответствует не одно, а несколько значений критерия эффективности и результат сравнения стратегий с помощью критерия оказывается неопределенным.

Рассмотрим вопросы построения оценок эффективности, которые, вообще говоря, могут вводиться различным образом. Определение вида оценки эффективности и связанного с ней понятия (принципа, критерия) оптимальности представляет собой элемент постановки задачи и является, в конечном счете, правом оперирующей стороны. Однако существуют наиболее распространенные и обоснованные оценки эффективности, зависящие от вида неконтролируемых факторов. Если имеется случайный неконтролируемый фактор, представляющий собой случайную величину с известным исследователю операции законом распределения, то в качестве оценки эффективности чаще всего используется математическое ожидание критерия эффективности. Пусть неконтролируемый фактор у принимает n значений у1, …, уn c вероятностями р1, …, рn, тогда математическое ожидание определяется по формуле n M y F ( x, y ) = pi F ( x, yi ). (1.3) i 1 <

–  –  –

max F ( x, y ) (для простоты будем считать, что максимумы и минимумы yY функций существуют, в противном случае надо использовать верхние и нижние точные грани, т.е. супремумы и инфимумы, и там, где необходимо, вводить понятия приближенных —оптимальных стратегий). Значит оценка эффективности стратегии х по смыслу должна принадлежать отрезку [А, В].

Но как разумно выбрать на нем единственное число? Можем ли мы быть уверенными, что при применении стратегии х в данной ситуации получится значение критерия эффективности больше А? Очевидно, нет. Только значение А мы можем твердо гарантировать. Значит разумным будет взять это значение в роли оценки эффективности стратегии х, т.е. положить f г ( x) min F ( x, y ). (1.8) yY

–  –  –

называется максимальным гарантированным результатом на множестве X ~ (аналогично на Х ). В математике такое выражение принято называть максиминами или при перестановке процедур максимизации и минимизации — минимаксами.

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

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

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

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

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

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

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

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

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

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

Линейное программирование (включая целочисленное программирование), нелинейное программирование (включая выпуклое программирование) и динамическое программирование составляют основные подразделы математического программирования. В настоящем пособии им посвящены, соответственно, главы 3, 4 и 5.

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

Игровые задачи также имеют свою классификацию, в соответствии с которой выделяется несколько подразделов теории игр. Изучению теории игр посвящены главы 7 и 8 настоящего пособия (в соответствии с внутренней классификацией теории игр).

Среди задач исследования операций со случайными неконтролируемыми факторами наиболее важными являются задачи массового обслуживания, задачи теории надежности и задачи управления запасами. Эти задачи характеризуются определенным видом критериев эффективности, пространств стратегий и фигурирующих в них случайных величин, которые отражают их содержательный смысл. Массовому обслуживанию (включенному в программу) посвящена глава 9 настоящего пособия. Два других раздела можно изучать факультативно [7,9,16,33].

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

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

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

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

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

Основными видами оценки принимаемых решений в условиях риска являются:

• ожидаемое значение результата (математическое ожидание);

• ожидаемое значение результата в сочетании с минимизацией его дисперсии;

• доверительный интервал для получаемого результата;

• наиболее вероятное событие (исход) в будущем.

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

Задачи и упражнения

1. Фирмой "Супертранзистор'' выпускаются радиоприемники трех различных моделей: А, В и С. Каждое изделие указанных моделей приносит доход в размере 8, 15 и 25 единиц соответственно. Необходимо, чтобы фирма выпускала за неделю не менее 100 приемников модели А, 150 приемников модели В и 75 приемников модели С.

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

Так, в частности, в расчете на 10 приемников модели А требуется 3 ч для изготовления соответствующих деталей, 4ч на сборку и 1ч на упаковку. Соответствующие показатели в расчете на 10 приемников модели В равняются 3, 5 и 1.5 ч, а на 10 приемников модели С - 5, 7 и 3. В течение ближайшей недели фирма может израсходовать на производство радиодеталей 150 ч, на сборку 200 ч и на упаковку 60 ч.

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

2. Авиакомпания "Небесный грузовик", обслуживающая периферийные районы страны, располагает 8 самолетами типа 1, 15 самолетами типа - 2, 12 самолетами типа 3, которые она может использовать для выполнения рейсов в течение ближайших суток. Грузоподъемность (в тысячах тонн) известна: 45 для самолетов типа 1, 7 для самолетов типа 2, 4 для самолетов типа 3.

Авиакомпания обслуживает города А и В. Городу А требуется тоннаж в 20000 т, а городу В - в 30000 т. Избыточный тоннаж не оплачивается. Каждый самолет в течение дня может выполнить только один рейс.

Расходы, связанные с перелетом самолетов по маршруту "Центральный аэродром - пункт назначения", указаны в приведенной ниже таблице:

–  –  –

Постройте оптимизационную модель, минимизирующую расходы.

3. Фирма «Микродеталь» является владельцем мелкосерийного металлообрабатывающего завода. Дневной портфель заказов включает n деталей, каждая из которых может обрабатываться на n различных станках. Пусть tij общая продолжительность обработки детали i на станке j (включая время наладки станка).

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

4. Задача о доставке грузов (задача о покрытии). Фирма "Автопегас" должна доставить грузы пяти своим клиентам в течение рассматриваемого дня. Клиенту А нужно доставить груз весом в 1 единицу, клиенту В - в 2 единицы, клиенту С - в 3 единицы, клиенту D - в 5 единиц и клиенту Е - в 8 единиц. Фирма располагает четырьмя автомашинами следующей грузоподъемности: машина 1 - 2 единицы, машина 2 - 6 единиц, машина 3 - 8 единиц, машина 4 - 8 единиц. Стоимость эксплуатации автомашины j составляет сj.

Предположим, что одна машина не может доставлять груз обоим клиентам А и С, аналогично одна машина не может использоваться для доставки груза обоим клиентам В и D.

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

5. Предприятие производит изделия трех видов, поставляет их заказчикам и реализует на рынке. Заказчикам требуется 100 изделий первого вида, 200 изделий второго вида и 250 изделий третьего вида. Условия спроса на рынке ограничивают число изделий первого вида 200 единицами, второго — 300 и третьего — 500 единицами. Для изготовления изделий используется 4 типа ресурсов. Количество ресурсов, потребляемых для производства одного изделия, общее количество ресурсов и прибыль от реализации одного изделия заданы в таблице.

–  –  –

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

6. Предприятие рекламирует свою продукцию с использованием телевидения, радио, газет. Анализ рекламной деятельности в прошлом показал, что эти средства приводят к увеличению прибыли соответственно на 10, 5 и 7 усл.ед. в расчете на 1 усл.ед., затраченную на рекламу. Администрация предприятия на рекламу выделила 50 тыс.усл.ед. и не намерена тратить на телевидение более 40%, на радио и газеты — более 60% от общей суммы выделенных средств.

Постройте оптимизационную модель, максимизирующую прибыль, объясните ее элементы и соотношения.

Глава 2. КЛАССИЧЕСКИЕ ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ § 2.

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

Исходными данными при постановке задачи поиска экстремума является множество X и определенная на нем функция f(x). Мы будем рассматривать конечномерные задачи, поэтому x является вектором произвольной размерности n, т.е. x = (x1,…, xn), а множество X подмножеством евклидова пространства Rn (возможно совпадающим со всем пространством). Помимо задания X (его называют допустимым множеством) и f (x) (ее называют целевой функцией) необходимо определить, что понимается под решением задачи. Во-первых, речь может идти о нахождении точек максимума (одной или всех), минимума (одной или всех) или тех и других. Во-вторых, необходимо уточнить само понятие максимума (минимума), так как оно может пониматься в глобальном и локальном смысле.

Определение. Точка x*X называется точкой глобального (абсолютного) максимума функции f (x) на множестве X, если f(x*) f(x) x X. (2.1) Определение. Точка x*X называется точкой локального максимума функции f(x) на множестве X, если 0 такое, что f(x*) f(x) xX U (x*), (2.2) где U (x*) - -окрестность точки x* (шар радиусом с центром в x*).

Определения глобального и локального минимумов получаются заменой в (2.1) и (2.2) знаков неравенств на противоположные.

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

Если x* есть точка глобального максимума f(x) на X, то будем использовать запись f(x*) = max f(x), (2.3) xX т.е. под max f(x) понимается максимальное (абсолютное) значение f(x) на xX X. Для точки глобального максимума принято обозначение (2.4) x* = arg max f(x).

xX Частным решением задачи поиска максимума называется нахождение одной точки x* и значения f(x*), определяемых (2.3), (2.4). Полным решением называется нахождение величины max f(x) и всех реализующих xX ее значений аргумента, множество которых принято обозначать Arg max f(x) = {x* X | f(x*) = max f(x)}. (2.5) xX xX Обычно, если это не оговаривается особо, под решением задачи максимизации будем понимать нахождение ее частного решения (глобального).

Аналогичные понятия и обозначения используются для задачи поиска глобального минимума (соответственно min f(x), arg min f(x), xX xX Arg min f(x)).

xX Множество всех точек локальных максимумов включает в себя множество (2.5), но, вообще говоря, с ним не совпадает. Задачу нахождения всех локальных максимумов мы будем записывать в виде (2.6) f(x) max, xX.

Аналогично для локальных минимумов (2.7) f(x) min, xX, а для задачи нахождения всех локальных экстремумов (максимумов и минимумов) (2.8) f(x) extr, xX.

Так как, очевидно, точки максимума функции f(x) совпадают с точками минимума функции –f(x), то все свойства и методы решения задачи (2.6) легко переносятся на (2.7), (2.8) (мы будем их рассматривать на примере задачи максимизации).

Экстремальные задачи принято делить на задачи поиска безусловного и условного экстремума. Если X = Rn, т.е. рассматриваются точки экстремума f(x) на всем n-мерном пространстве, то имеем задачу на безусловный экстремум (или без ограничений). Если X Rn (собственное подмножество n-мерного пространства), то имеем задачу на условный экстремум (или с ограничениями). Терминология эта возникла в связи с тем, что множество X в последнем случае обычно задается какими-то условиями (обычно ограничениями вида равенств и неравенств). В классическом анализе рассматриваются задачи без ограничений и с ограничениями типа равенств.

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

Теорема Вейерштрасса. Если X компакт в Rn (замкнутое ограниченное множество), f(x) непрерывная на X функция, то точки глобального максимума и минимума f(x) на X существуют.

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

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

Следствие. Если X замкнутое непустое множество в Rn, f(x) непрерывная на X функция и ограничено множество P = {x X | f(x) c}, (2.9) где c некоторая константа, меньшая верхней грани f(x) на X, то точка глобального максимума f(x) на Х существует.

Доказательство. Множество P является по определению непустым подмножеством множества X, оно ограничено, а в силу непрерывности f(x), и замкнуто. Поэтому по теореме Вейерштрасса существует точка глобального максимума f(x) на P со значением не меньше c. Но на множестве X\P выполняется f(x) c, следовательно, данная точка является и глобальным максимумом f(x) на X, что и требовалось доказать.

Для существования глобального минимума в определении (2.9) множества P знак неравенства следует заменить на противоположный, а константа c должна быть больше нижней грани f(x) на X.

Для рассматриваемых в дальнейшем экстремальных задач будет предполагаться, как правило, выполнение условий теоремы Вейерштрасса или ее следствия. Условие ограниченности множества P может заменяться на условие f(xk) – при | xk | (для минимума f(xk) ).

§ 2.2. Условия экстремума в задачах без ограничений

–  –  –

Но (2.29) при i = *i и (2.30) с учетом определения функции Лагранжа эквивалентны (2.24), т.е. теорема доказана.

Принцип Лагранжа дает нам n+m уравнений (n уравнений (2.24) и m уравнений в определении (2.17) множества Х) для нахождения n+m неизвестных x1,…, xn, 1,…, m, что позволяет в простых случаях найти решение задачи.

–  –  –

Пример 2.3.

f(x) = x1 extr, X = {x R2 | x13 – x22 = 0}.

Здесь из ограничения x1 x 2 3, поэтому, очевидно, f(x) имеет единственный локальный (и глобальный) минимум в (0, 0), а локальных (и глобальных) максимумов нет. Функция Лагранжа L = x1 + (x13–x22), поэтому дL 2 1 3 x1 0 при х1 = 0, т.е. принцип Лагранжа не выполняется (градидx1 ент ограничения в решении равен нулю).

–  –  –

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

Задача о строительстве моста

Выбрать место для постройки моста через реку, чтобы длина дороги между двумя пунктами А и В, расположенными по разные стороны от реки, была наименьшей. Пусть a и b — расстояния от пунктов А и В до реки соответственно, с — расстояние между пунктами, а h — ширина реки.

Изобразим графически данную ситуацию.

–  –  –

Найти размеры цилиндрической закрытой цистерны с заданным объемом V и с наименьшей полной поверхностью.

Обозначив радиус и высоту цилиндра через r и h, а его полную поверхность через S, получим S = 2rh+ 2r 2.

Здесь переменные r и h не являются независимыми, а связаны между собой равенством V = r 2 h, так как согласно условию цилиндр должен иметь заданный объем V. Определяя из этого равенства h и подставляя в выражение полной поверхности, получим S = 2(r 2 + V/r), где r изменяется в интервале (0,+).

Выразив таким образом исследуемую полную поверхность цилиндра S через одну переменную r, найдем теперь ее наименьшее значение при изменении r в интервале (0; +).

Находим S' = 2(2r - V/r 2 ) = 2(2r 3 - V)/r, причем S'=0 в единственной точке r= 3 V / 2, которая лежит в рассматриваемом интервале. Эта точка является критической, так как в ней выполняются все необходимые для этого условия.

Исследуем найденную критическую точку по знаку второй производной в этой точке:

S''=4(+V/r 3 );

S''( 3 V / 2 )=120, Откуда следует, что критическая точка r= 3 V / 2 есть точка минимума.

Функция S(r) непрерывна в интервале (0; +). Поэтому согласно свойству непрерывных функций единственный минимум функции S в интервале (0; +) совпадает с ее наименьшим значением в этом интервале.

При r= 3 V / 2 получим h= V/r 2 = 2 3 V / 2 =2r.

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

–  –  –

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

На этой задаче мы продемонстрировали общий прием для доказательства неравенств: одна часть неравенства приравнивается к произвольной величине В и это берется в качестве ограничения, а другая часть неравенства выступает в роли целевой функции, для которой в зависимости от знака неравенства ищется максимум или минимум, найденное экстремальное значение соответственно не больше или не меньше В. Таким стандартным приемом можно доказать все известные неравенства (например, Коши-Буняковского, Гельдера, со всевозможными средними), а также выводить новые неравенства.

Метод наименьших квадратов

Имеются результаты измерений значений параметров на входе х и на выходе y некоторого устройства:

(x1, y1), (x2, y2), …, (xn, yn).

По этим данным нужно восстановить функциональную зависимость y=f(x), описывающую работу устройства. Уточним постановку задачи. Пусть априори известен класс возможных функциональных зависимостей f(x,d1,…,dk) с точностью до параметров d1,…,dk. По методу наименьших квадратов конкретное значение вектора параметров d =(d1,…,dk) выбирается так, чтобы минимизировать сумму квадратов невязок в измерениях, т.е.

величину n

–  –  –

порядка равен 4D, т.е. они положительны (если не все xi равны между собой). Значит, по критерию Сильвестра матрица положительно определена и в силу теоремы о достаточных условиях экстремума точка (а*, b*) доставляет минимум величине (по крайней мере, локальный).

Но так как выполнены условия следствия из теоремы Вейерштрасса, существует глобальный минимум, а в силу единственности экстремума пара (а*, b*) является точкой глобального минимума.

–  –  –

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

–  –  –

1. Найти оптимальное распределение ограниченного ресурса в а единиц между n потребителями, если прибыль, получаемая при выделении j-му потребителю x j единиц ресурса, вычисляется по формуле c j x j.

2. Завод А расположен на расстоянии а км от железной дороги, идущей в город В, и на расстоянии b км от города В. Под каким углом к железной дороге следует провести шоссе с завода А, чтобы доставка грузов была наиболее дешевой, если стоимость перевозок по шоссе в k раз дороже, чем по железной дороге?

3. Найти прямоугольник наименьшего периметра, ограничивающий заданную площадь, используя теорему о среднем.

4. Составляется электрическая цепь из двух параллельно соединенных сопротивлений. При каком соотношении между этими сопротивлениями сопротивление всей цепи r максимально, если при последовательном соединении этих сопротивлений оно равно R?

5. Поперечное сечение открытого канала имеет форму равнобедренной трапеции. При каком наклоне боков «мокрый периметр» сечения будет наименьшим, если площадь «живого сечения» воды в канале равна S, а уровень воды равен h?

6. По плану производства продукции предприятию необходимо изготовить 180 изделий, которые могут быть изготовлены двумя технологическими способами. При производстве х1 изделий первым способом затраты составляют 4х1 x12 руб., а при изготовлении х2 изделий вторым способом они равны 8х2+ x 22 руб. Определить, сколько изделий каждым из способов следует изготовить, так чтобы общие затраты на производство продукции были минимальны.

7. Фирма реализует автомобили двумя способами: через торговых агентов и магазин. При реализации х1 автомобилей через торговых агентов расходы на реализацию составляют 4 х1 х12 ден.ед., а при продаже х 2 автомобилей через магазин расходы составляют х 22 ден.ед. Найти оптимальный способ реализации автомобилей, минимизирующий суммарные расходы, если общее число предназначенных для продажи автомобилей составляет 200 штук.

8. Производственная функция фирмы имеет вид y x10.25 x 2.5, лимит на ресурсы равен 18 ед., цены на ресурсы соответственно равны 3 и 4 ден.ед. Решите задачу максимизации выпуска фирмы, используя условия первого и второго порядков для функции Лагранжа.

Глава 3. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ § 3.

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

Транспортная задача. Пусть имеется m складов S1,…, Sm, предназначенных для хранения некоторого товара, и n пунктов потребления этого товара P1,…, Pn. Надо составить наиболее экономичный план перевозок товара со складов в пункты потребления. Исходными данными являются запасы товаров на складах a1,…, am, потребности пунктов потребления b1,…,bn и стоимости перевозок единицы товара cij с каждого склада Si в каждый пункт потребления Pj, i= 1, m, j= 1, n.

Будем предполагать выполненным условие удовлетворения всех потребностей:

n m

–  –  –

Заметим, что если стоимости перевозок единицы товара с любого склада на любой пункт потребления отличны от нуля, т.е. cij 0, то для оптимального плана перевозок, минимизирующего функцию (3.5), неравенства (3.4), очевидно, будут выполняться как равенства, поэтому ограничения (3.4) можно заменить на ограничения m

–  –  –

Это следует из того, что если в (3.3) или (3.4) хотя бы одно из ограничений представляет собой строгое неравенство, то, просуммировав m+n неравенств, придем к противоречию с равенством (3.7).

Задача минимизации (3.5) при ограничениях (3.2) - (3.4) (или (3.2), (3.6), (3.8)) представляет собой важный случай задачи линейного программирования, называемый транспортной задачей. Для этой задачи существуют специфические методы решения, поэтому, а также в силу ее широкой распространенности, мы в дальнейшем остановимся на ней более подробно.

Задача о рационе кормления. Пусть имеется возможность производить n видов кормов К1,…, Кn для животноводческой фермы. Каждый из этих видов кормов характеризуется определенным набором полезных свойств (калорийность, содержание перевариваемого протеина, витаминных добавок и т.д.). Обозначим эти свойства буквами Н1, …, Нm. Будем предполагать, что для каждого вида кормов Кj известно содержание в единице веса всех указанных компонент Нi, т.е. калорий, протеина, витаминов и т.д. Обозначим эти характеристики кормов буквами aij, i= 1, m, j= 1, n. Матрица A=||aij|| размера m x n полностью характеризует все виды кормов. Предположим, что известна годовая потребность фермы по всем компонентам Н1, …, Нm, задаваемая вектором b= (b1,…, bm), а также вектор стоимости кормов с=(с1,…, сn), где cj стоимость единицы корма вида Кj.

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

Рацион кормления можно описывать вектором x = (x1,…, xn), где xj количество корма вида Кj, поставляемое на ферму в течение года. Он должен, во-первых, удовлетворять условию неотрицательности xj 0, j= 1, n. (3.9) Во-вторых, должна быть обеспечена потребность во всех полезных компонентах. Для фиксированного х содержание компоненты Нi в рационе равно n

–  –  –

Задача планирования производства. Пусть имеется m видов ресурсов R1,…, Rm, которые могут быть использованы для производства n видов товаров T1,…, Tn. Для производства единицы товара Tj необходимо затратить aij количества ресурса Ri, i= 1, m, j= 1, n. Матрица A = || aij || называется технологической матрицей. Известна цена cj на товар Tj и общее количество ресурсов b1,…, bm. Векторы b = (b1,…, bm), c = (c1,…, cn) называются, соответственно, векторами ресурсов и цен.

Требуется выбрать такой план производства x = (x1,…, xn), который в условиях заданных ограничений на ресурсы максимизирует валовое производство (стоимость выпущенной продукции). Здесь xj производимое количество товара вида Tj.

Ограничения в этой задаче записываются следующим образом:

xj 0, j= 1, n, n

–  –  –

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

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

–  –  –

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

Ограничение типа равенства можно заменить на два противоположных ограничения типа неравенства. Так, ограничение n

–  –  –

xj 0, j= 1, r (k m, r n). (3.24) Все сказанное выше, естественно, относится и к этим трем формам, т.е. они легко переводятся одна в другую. Стандартная форма является частным случаем общей при k = m, r = n, каноническая при k = 0, r = n.

Общая переводится в стандартную путем замены m – k равенств на 2(m – k) неравенств, а в каноническую путем замены k неравенств на k равенств с помощью k свободных переменных. Аналогично стандартная форма переводится в каноническую, и наоборот.

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

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

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

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

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

Для этого достаточно привести соответствующие примеры:

а) max (x1 + x2), x1 0, x2 0, x1 + x2 - 1;

б) max (x1 + x2 ), x1 0, x2 0, x1 – x2 1;

в) max (x1 + x2 ), x1 0, x2 0, x1 + 2x2 1, 2x1 + x2 1.

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

В примере а) неотрицательность переменных означает, что множество допустимых планов должно лежать в неотрицательном ортанте. Линейное неравенство x1 + x2 -1 определяет полуплоскость, лежащую ниже прямой, задаваемой аналитически уравнением x1 + x2 = -1. Эта полуплоскость не имеет общих точек с неотрицательным ортантом, значит, множество допустимых планов пусто и задача не имеет решения.

В примере б) множество допустимых планов Х представляет собой пересечение неотрицательного ортанта и полуплоскости, лежащей выше прямой, определяемой уравнением x1 – x2 = 1. В отличие от предыдущего примера это множество непусто, но не ограничено.

Линии уровня целевой функции x1 + x2, на которых она принимает постоянные значения, изображены на рисунке пунктирными прямыми, стрелка указывает направление роста. Очевидно, на множестве Х эта функция сверху не ограничена, значит задача не имеет решения. Впрочем, не следует думать, что неограниченность множества допустимых планов обязательно влечет за собой отсутствие решения. Если в примере б) изменить только целевую функцию на –(x1 + x2), то задача будет иметь решение x10 x2 0 (направление роста функции изменится на противоположное, и линия наивысшего уровня на множестве Х будет проходить через начало координат).

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

–  –  –

Так как множество Х замкнуто и ограничено, а целевая функция непрерывна, то по теореме Вейерштрасса задача имеет решение. Линия наивысшего уровня функции x1 + x2 на многоугольнике Х проходит через вершину с координатами x10 x2 13. Это и есть решение задачи.

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

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

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

–  –  –

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

Определение. Множество Х n-мерного евклидова пространства называется выпуклым, если вместе с любыми двумя точками x1, x2 X ему принадлежит весь отрезок, соединяющий эти точки, т.е. любая точка x = dx1 + (1 – d)x2, где 0 d 1, принадлежит Х.

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

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

Доказательство. Рассмотрим задачу линейного программирования в стандартной форме (3.17) (3.19). Если x1, x2 X, то x1 0, x2 0, Ax1 b, Ax2 b. Рассмотрим точку x = dx1 + (1 - d)x2, 0 d 1. Очевидно, x 0 и Ax= dAx1 + (1–d)Ax2 db + (1–d)b = b, т.е. x X. Для любой другой формы задачи линейного программирования доказательство легко получить либо непосредственно, как для стандартной формы, либо путем перехода к стандартной форме. Лемма доказана.

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

Определение. Множество Х n-мерного евклидова пространства называется замкнутым, если оно содержит все свои предельные точки, т.е.

такие точки, в каждой окрестности которых имеются точки из Х.

Предел и окрестность понимаются в обычном смысле (в евклидовой метрике).

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

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

Определение. Точка х выпуклого множества Х называется угловой (или крайней), если не существует таких точек x1, x2 X, x1 x2, что x=dx1+ +(1-d)x2 при некотором d(0,1).

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

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

Рассмотрим некоторые важные свойства выпуклых множеств.

Теорема отделимости. Для любого выпуклого замкнутого множества Х и любой точки y, не принадлежащей Х, существует разделяющая их гиперплоскость, т.е. существует такой вектор a 0, что a, y inf a, x.

x X.

Доказательство. Рассмотрим функцию расстояния от фиксированной точки y до произвольной точки xX: (x, y)= |x - y|. Эта функция непрерывна по х, ограничена снизу (нулем), значит на замкнутом множестве Х существует х 0, реализующая нижнюю грань этой функции | х 0 - y | =inf | x - y | 0 (3.25) x X (точка х называется проекцией точки y на Х).

–  –  –

Значит, x/, но x/ X, следовательно, x/ Xo=X. Аналогично доказывается, что x// Xo. Мы пришли к противоречию, так как xi угловая точка Xo.

Пусть теперь х 0 внутренняя точка X. Проведем через х 0 прямую l. Пересечение l X является отрезком, концы этого отрезка x/ и x// принадлежат границе множества X. Для них, как доказано, теорема верна, т.е.

существуют угловые точки y1,…, yk, z1,…, zr множества X такие, что k k

–  –  –

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

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

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

Доказательство. Пусть сначала множество допустимых планов ограничено, тогда по теореме о представлении, условия которой в этом случае выполнены, для любого оптимального плана х 0 найдутся такие угловые точки x1,…, xk множества X, что k k

–  –  –

1/ (x + x//), что противоречит предположению о том, что x угловая иx= точка X. Значит, r-мерные вектора а 1, а 2,…, а k независимы, а поэтому их число не может превышать r (факт известный из линейной алгебры), т.е.

r k. В матрице A можно выбрать независимые k строк (это также известный в линейной алгебре факт), тогда получим, очевидно, такую матрицу A, которая удовлетворяет всем условиям теоремы. Теорема доказана полностью.

Замечание. Приведенное доказательство теоремы с незначительными изменениями годится и для задачи линейного программирования в канонической форме (провести его в качестве упражнения).

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

Это утверждение легко вытекает из предыдущей теоремы, так как число квадратных подматриц матрицы коэффициентов А конечно.

Вектор х, являющийся угловой точкой множества допустимых планов Х, принято называть опорным планом. Опорный план называют невырожденным, если ему соответствует система уравнений вида (3.32) порядка m, где m число строк матрицы коэффициентов A. Задача линейного программирования называется невырожденной, если все ее опорные планы невырождены. Условие невырожденности облегчает решение задачи линейного программирования (в частности, гарантирует сходимость симплекс-метода), хотя и вырожденные задачи вполне доступны для практического решения (при соответствующей модификации вычислительных методов).

Система независимых вектор-столбцов матрицы A в разложении (3.32) называется базисом опорного плана x. Если задача невырождена, то базис состоит из m векторов и ранг матрицы A равен m.

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

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

max c, x при ограничениях Ах b, х 0.

Задача предполагается невырожденной, поэтому ранг матрицы А равен m (число строк) и число столбцов не меньше числа строк n m (как известно из линейной алгебры, ранг матрицы не превышает минимума из числа строк и столбцов).

Пусть известна некоторая угловая точка x множества допустимых планов X x / x 0, Ax b.

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

Ах b, (3.35) где a11...a1m x1 A.............., x....

a...a x m m1 mm Обозначим вектор-столбцы матрицы А через а i, i 1, m, тогда базис состоит из векторов а 1,..., а m.

–  –  –

Так как b 0, план = (0, b) является допустимым (x = 0, и = b). Этому плану соответствует базис из m последних вектор-столбцов матрицы A/ (искусственный базис), образующих единичную подматрицу. Значит, является опорным планом, т.е. исходный опорный план для вспомогательной задачи (3.44), (3.45) строится легко и можно сразу применять для ее решения описанный выше итеративный процесс симплекс-метода. Пусть получено это решение * = (x*, и*).

Покажем, что если и* = 0, то x* опорный план исходной задачи линейного программирования в канонической форме, а если и* 0, то исходная задача не имеет решения (вспомогательная задача всегда имеет решение, так как множество допустимых планов у нее непусто по крайней мере содержит, а целевая функция (3.44) ограничена снизу нулем). Действительно, если и*=0, то х* допустимый план исходной задачи, так как Ax* = b, а поскольку симплекс-метод состоит в переборе угловых точек множества допустимых планов, т.е. * угловая точка множества X / = { = (x, и) | Ax + и = b, x 0, и 0}, то, очевидно, х* угловая точка множества X = {x | Ax = b, x 0}, и мы получили опорный план исходной задачи х*. Если и* 0, то значение m

–  –  –

Ее матрица коэффициентов имеет вид 1 3 0 1 0 2 0 1 0 1, а исходный опорный план (0, 0, 0, 4, 6).

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

–  –  –

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

Рассмотрим задачу линейного программирования в стандартной форме (3.17) - (3.19).

Двойственной к ней называется задача min b, у (3.46) при ограничениях Aту с, (3.47) у 0. (3.48) т Здесь A матрица, получающаяся транспонированием матрицы A, если матрица A имеет размер m x n, то x n-мерный вектор, а у m-мерный вектор.

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

Если задачу (3.46) - (3.48) преобразовать к стандартной форме и применить к ней правило построения двойственной задачи, то нетрудно убедиться, что после соответствующих преобразований получится задача (3.17) - (3.19).

Таким образом, можно сказать, что задачи (3.17) - (3.19) и (3.46) взаимодвойственные или просто двойственные задачи линейного

–  –  –

Аналогично, если рассмотреть x0, Ат y0-c, то, с одной стороны, в силу x0 0, Ат y0 c выполняется неравенство x0, Атy0 – c 0, а с другой стороны, x0, Атy0 – c = Ax, y0 - c, x0 b, y0 - c, x0 = 0, значит x0, Атy0 –c=0 и справедливо второе утверждение теоремы.

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

Мы рассмотрим это на примере транспортной задачи.

§ 3.4. Транспортная задача Наряду с общими методами (например, симплекс-методом) в линейном программировании имеются специальные методы и модификации, которые позволяют ускорить процесс решения, учитывая специфику задачи (главным образом, структуру ограничений). К числу специальных задач, для которых созданы собственные методы решения, относится, в первую очередь, транспортная задача. Внимание к этой задаче обусловлено тем, что она, во-первых, имеет важное прикладное значение, во-вторых, к ней сводятся многие другие задачи линейного программирования (сетевые задачи, задача о назначениях, задачи календарного планирования), втретьих, структура ограничений этой задачи обладает ярко выраженной спецификой, которую удается эффективно использовать при разработке вычислительных методов. Рассмотрим некоторые из них. Будем предполагать, что имеет место баланс наличия товара и потребности в нем (3.7) (задачи с нарушенным балансом как в одну, так и в другую сторону легко сводятся к этому случаю путем введения дополнительного “фиктивного” склада или пункта потребления).

Тогда задача сводится к минимизации (3.5) при ограничениях (3.6), (3.8), (3.2).

План этой задачи представляет собой вектор размерности mn; если его компоненты записать в следующем порядке:

х = (x11,…, x1n, x21,…, x2n,…, xm1,…, xmn), то матрица коэффициентов имеет вид n n n

–  –  –

Эти таблицы отличаются от начальной тем, что у них заполнены либо первая строка, либо первый столбец. Снова рассматриваем клетку в “северо-западном углу ”. Для таблицы 2 это клетка на пересечении второй строки и первого столбца; соответствующая переменная полагается равной x21 min (a2, b1 a1 ). Для таблицы 3 это клетка на пересечении первой строки * и второго столбца; соответствующая переменная полагается равной x12 min (a1 b1, b2 ). В любом случае, заполняя нулями соответствующую *

–  –  –

т.е. либо x ij 0, либо u i0 v 0j cij (возможно одновременно). В данном случае оказывается, что это свойство можно использовать как признак оптимальности. Точнее, если x0 и y0 допустимые планы этих задач и если для

–  –  –

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

Алгоритм метода потенциалов состоит в следующем. Выбирается начальный опорный план x* транспортной задачи (например, методом “северо-западного угла”). Он имеет не более n+m-1 ненулевых компонент.

Обозначим множество пар индексов (i, j), для которых xij 0 через П*. Для *

–  –  –

Если *ij 0 (i, j ) П *, то данный опорный план x* является оптимальным. Если существует пара (i0, j0), для которой *i0 j0 0, то x* не является оптимальным и осуществляется переход к новому опорному плану, в котором переменная xi0 j0 уже будет базисной, т.е. будет осуществляться перевозка из S i0 в Pj0. Для простого определения такого опорного плана используется циклическая переброска. В таблице 1, заполненной компонентами предыдущего опорного плана x*, выбирается замкнутая ломаная линия, которая начинается и заканчивается в клетке (i0, j0), кроме этой клетки линия имеет вершины (точки излома) только в клетках, соответствующих

–  –  –

(здесь для единообразия считается ik+1=i0).

Возьмем новый план, у которого компоненты, соответствующие нечетным членам построенной последовательности, больше соответствующих компонент плана x* на, компоненты, соответствующие четным членам последовательности, меньше на, а остальные равны компонентам плана x*. Новый план х является, очевидно, допустимым и опорным, он имеет одну новую базисную переменную x* j, а одна бывшая базисная i 00

–  –  –

т.е. новый план лучше старого.

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

Для иллюстрации описанного процесса решения транспортной задачи рассмотрим численный пример и для него построим начальный опорный план по методу “северо-западного угла” и сделаем одну итерацию по методу потенциалов.

Пусть в транспортной задаче m=3, n=4, a1=20, a2=12, a3=8, b1=10, b2=15, b3=8, b4=7, а коэффициенты линейной формы проставлены в правых верхних углах клеток таблице 4, в которой методом “северо-западного угла” построен начальный опорный план.

Таблица 4

–  –  –

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

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

1. Задача о назначениях. Имеются п сотрудников, которые могут выполнять п работ, причем использование i-го сотрудника на j-й работе приносит доход сij (i,j= 1, n ). Требуется поручить каждому сотруднику выполнение определенной работы так, чтобы максимизировать суммарный доход.

Введем переменные:

x ij 1, если i-й сотрудник выполняет j–ю работу и x ij 0 в противном случае.

С учетом того, что каждый сотрудник выполняет одну работу и каждую работу кто-то делает, получаем такую задачу. Найти n n max cij xij i 1 j 1

–  –  –

которые отражают требования однократного въезда и выезда из каждого города.

Однако эти ограничения еще полностью не описывают допустимые маршруты. Дело в том, что они не исключают возможности разрыва пути, т.е. появления нескольких не связанных между собой подмаршрутов для части городов. Чтобы исключить такую возможность, обычно вводят дополнительные переменные ui, i 1, n, которые можно считать неотрицательными и целыми числами, и записывают еще (n - 1)2 - (п - 1) ограничений ui - u j + n xij n-1, i, j 2, n, i j. (3.58) Покажем, что ограничения (3.58) исключают возможность существования подмаршрутов. Действительно, если имеется подмаршрут, включающий k городов и начинающийся и заканчивающийся в одном из них, то для соответствующих переменных, очевидно, выполняются соотношения n

–  –  –

где М — множество номеров городов, образующих подмаршрут. Тогда, суммируя неравенства (3.58) для индексов i, j М и учитывая, что все величины ui сокращаются вследствие связности и замкнутости подмаршрута, придем к противоречию:

kn k(n - 1).

Необходимо еще показать, что ограничения (3.58) не исключают допустимый маршрут. Для этого положим число ui равным порядковому номеру города i по маршруту следования коммивояжера. Тогда для тех пар (i, j), для которых xij = 0, неравенства (3.58) вытекают просто из условий 1 ui n, откуда следует, что ui - u j n - 1, а для тех пар (i, j), для которых xij = 1, справедливы, очевидно, равенства ui - u j = -1 (город с номером j следует за городом с номером i), и неравенства (3.58) выполняются как равенства.

Итак, задача коммивояжера состоит в минимизации целевой функции n n <

–  –  –

Из свойств задачи линейного программирования следует, что максимумы линейной формы c, x на множествах X и X совпадают, причем среди решений задачи максимизации c, x на X есть целочисленные векторы. Значит мы, в принципе, построили обычную задачу линейного программирования, которая нам дает решение исходной целочисленной задачи. Однако эта замена задач является формальной, так как явное описание множества X представляет собой также сложную проблему, а без него нельзя применять обычные методы решения задач линейного программирования. Возникает мысль последовательно аппроксимировать множество X, отсекая части множества Х. Рассмотрим в общих чертах один из конструктивных способов проведения таких отсечений (так называемый первый алгоритм Гомори).

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

~

а) для любого вектора множества X выполняет

–  –  –

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

В качестве исходной задачи берем задачу (3.60) - (3.62) и находим ее решение, но не любое, а обладающее следующим свойством: среди всех решений задачи оно имеет наибольшую первую компоненту, если таких решений несколько, то среди них выделенное решение имеет наибольшую вторую компоненту и т.д. Такое решение называется лексикографическим;

оно может быть найдено несложной модификацией симплекс-метода.

Пусть для исходной задачи лексикографическое решение есть х (0). Если х (0) — целочисленный вектор, то он является решением задачи (3.60) Если нет, то находим его нецелочисленную компоненту с наименьшим номером; пусть это s. В симплексной таблице, соответствующей опорному плану х(0), берем s-ю строку, соответствующую s-му вектору базиса. Ее элементы при описании симплекс-метода обозначались через хsj, j 0, n. Пусть множество индексов j, соответствующих внебазисным переменным, обозначено J.

Введем величины s 0 xs 0 ; sj xsj, j J, где z z z — дробная часть числа z (разность между числом и его целой частью).

В качестве новой задачи берем следующую задачу:

найти max c, x при ограничениях Ах=b, x j xn 1 s 0, х 0, xn+1 0. (3.65) sj j J Она отличается от исходной наличием дополнительной переменной xn+1 и дополнительного ограничения (3.65). Для нее находим лексикографическое решение и итеративный процесс повторяется. За конечное число шагов либо находим решение целочисленной задачи (3.60) - (3.63), либо выясняем, что оно не существует.

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

Комбинаторные методы. Представление о комбинаторных методах дает наиболее известный и широко используемый на практике метод ветвей и границ.

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

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

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

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

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

Основную сложность в задачу коммивояжера вносит ограничение (3.58). Если его отбросить, т.е. рассмотреть задачу минимизации (3.59) при ограничениях (3.57), где переменные xij неотрицательны (не обязательно целочисленные), то получается транспортная задача, решение которой будет представлять собой вектор с компонентами 0 и 1 (как для задачи о назначениях). Однако это решение не всегда можно использовать непосредственно для задачи коммивояжера, так как оно не обязательно будет замкнутым маршрутом, т. е. в нем могут содержаться не связанные между собой замкнутые подмаршруты, которые как раз и исключаются ограничением (3.58). В связи с этим обстоятельством используется более сложная итеративная вычислительная процедура.

На первом шаге решается вспомогательная задача (3.59), (3.57). В качестве оценки Q1 используется априорная верхняя граница минимального значения целевой функции, например, Q1= с12 с23... сn1, что соответствует маршруту через все города в порядке их нумерации.

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

Таким образом, к началу второй итерации имеем несколько задач типа транспортной. Решаем их по порядку. Если при решении очередной задачи ее значение оказывается не меньше текущего значения оценки (для первой задачи это Q1), то переходим к следующей задаче. Если же значение очередной задачи меньше текущего значения оценки, то в случае, когда ее решение представляет собой маршрут, полагаем оценку равной этому значению и переходим к следующей задаче, а в случае, когда ее решение образует подмаршруты, выбираем подмаршрут с наименьшим числом городов и каждому хij= 1 в этом подмаршруте ставим в соответствие новую транспортную задачу с соответствующим сij =, после чего переходим к следующей задаче. Перебрав все задачи, которые имелись к началу второй итерации, получим новую совокупность задач и некоторое значение оценки. С ними проводим третью итерацию и т.д. Процесс заканчивается, когда на очередной итерации не появляется ни одной новой задачи.

Данная глава дает общее представление о линейном программировании как разделе исследования операций. Более подробное изложение задач и методов линейного программирования содержится, например, в работах [3, 7].

Задачи и упражнения

–  –  –

Среди коэффициентов последней строки симплекс-таблицы есть отрицательные это элементы -7 и -14. Следовательно, угловая точка x ( 0) не является решением задачи.

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

Так как min (40/1,30/1)=30/1, то разрешающей является строка, соответствующая базисной переменной x 6. Итак, опорный элемент выделен в симплекс-таблице.

Заполнив новую симплекс-таблицу, получим:

–  –  –

Отметим, что значение f ( x ) в новой угловой точке уменьшилось по сравнению со значением в исходной 460 вместо 880. В нижней строке последней таблицы есть отрицательный элемент -7, стоящий в столбце при свободной переменной x1. Кроме того, в этом столбце имеются положительные элементы, поэтому возможно дальнейшее уменьшение f ( x ) с помощью очередного шага симплекс-метода.

На данном шаге выбор опорного столбца однозначен и определяется отрицательным элементом -7 последней строки. Так как min (10/1,20/1)=10/1, то строка при базисной переменной x2 является разрешающей. Опорный элемент в последней таблице выделен.

Как и на предыдущем шаге находим очередную симплекс-таблицу:

–  –  –

В этой симплекс-таблице в последней строке оба коэффициента положительны. Поэтому угловая точка x ( 2 ), соответствующая внебазисным переменным x 2, x 6 является точкой минимума целевой функции.

f (x) : x x ( 2) (10;0;30;10;50;0). Минимальное значение f ( x ) записано в правом нижнем углу симплекс-таблицы, f 390.

Задачи 1 - 4 решите симплекс-методом.

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

2. Имеется три вида сырья: А, В, С, которые используются для производства двух видов продукции 1 и 2. В распоряжении находятся 500 единиц сырья А, 750 единиц сырья В и 200 единиц сырья С. Продукт 1 состоит из одной единицы сырья А и двух единиц сырья В. Продукт 2 состоит из двух единиц сырья А, одной единицы сырья В и одной единицы сырья С. Доход от производства одной единицы продукта 1 составляет 4 ден.ед., а от единицы продукта 2 5 ден.ед. Сколько единиц каждого продукта нужно производить, чтобы максимизировать прибыль?

3. Необходимо составить наиболее дешевую смесь из трех веществ.

В состав смеси должно входить не менее 6 единиц химического вещества А, не менее 8 единиц вещества В и не менее 12 единиц вещества С.

Имеется три вида продукции (1, 2, 3), содержащих эти химические вещества в следующих пропорциях:

А В С 3 3 1,5 2 Стоимость одной весовой единицы продукта 1 2 ден.ед., продукта 2 3 ден.ед., продукта 3 2,5 ден.ед.

4. Металлургический завод из металлов А, В, С может выпускать сплавы трех видов. В течение планируемого периода завод должен освоить не менее 640 т металла А и 800 т металла В, при этом металла С может быть израсходовано не более 860 т.

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

–  –  –

5. Груз, находящийся в пунктах А и В, необходимо перебазировать в пункты С и D. В этих пунктах имеется соответственно груза на 6 и 4 машины. В пункты С и D надо отправить соответственно 3 и 7 машин груза.

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

С D А 80 30 В 60 90

6. На трех складах А, В, С находится сортовое зерно соответственно 10, 15, 25 т, которое надо доставить в четыре пункта: пункту 1 5 т, 2 10 т, 3 20 т, и 4 15 т. Стоимость доставки одной тонны со склада А в указанные пункты соответственно равны 80, 30, 50, 20 ден.ед.; со склада В 40, 10, 60, 70 ден.ед. и со склада С 10, 90, 40, 30 ден.ед. Составить оптимальный план перевозки зерна в четыре пункта, минимизирующий стоимость перевозок.

–  –  –

Р е ш е н и е.

Изобразим на плоскости ( x1, x2 ) допустимое множество D (многоугольник АВСDЕ) и одну из линий уровня 3x1 2 x2 с целевой функции.

Направление убывания f ( x ) указывает вектор е ( 3,2 ). Совершая параллельный перенос линии уровня вдоль направления е, находим ее крайнее положение. В этом положении прямая 3x1 2 x2 с проходит через вершину D(3,2) многоугольника АВСDЕ. Поэтому целевая функция f ( x ) при

–  –  –

x 0, i 1,5.

i

9. При продаже двух видов товаров используется 3 типа ресурсов.

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

–  –  –

Требуется 1) составить линейную оптимизационную модель, объяснить ее элементы и соотношения; 2) графическим методом найти оптимальный план и оптимальное значение целевой функции; 3) записать двойственную задачу; 4) найти решение двойственной задачи; дать интерпретацию полученным значениям y1, y 2, y 3 ; 5) провести анализ чувствительности к изменению c1, c2 ; 6) провести анализ чувствительности к изменению b1, b2, b3 ; 7) предприятие может приобрести дополнительно сырье одного из видов на сумму 1 ден.ед.; какое сырье следует приобрести, если стоимость единицы сырья 1, 2 и 3 видов равна 0,4; 0,8; 0,2 соответственно?

12. Сформулировать математически и решить задачу коммивояжера со следующими данными n=4, c12=c21=25, c13=c31=40, c14=c41=30, c23=c32=50, c24=c42=20, c34=c43=60.

Глава 4. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ § 4.

1. Задача математического программирования

–  –  –

Вообще говоря, в задаче могут быть одновременно ограничения типа равенств и неравенств. Однако такую задачу можно преобразовать к указанному виду. Действительно, ограничение вида равенства g ( x) 0 можно заменить двумя ограничениями вида неравенств g ( x) 0, g ( x) 0, а ограничение вида g ( x) 0 можно заменить на - g ( x) 0, т.е. система ограничений (4.1) имеет общий вид. Разделение ограничений на (4.1) и (4.2) не носит принципиального характера, так как каждое из них может быть записано в одном из этих двух видов, но иногда оказывается полезным. Так в задаче линейного программирования записывается отдельно условие неотрицательности x 0, хотя это просто частный вид линейного ограничения.

Кстати, нетрудно видеть, что задача линейного программирования есть частный случай задачи (4.4). Действительно, если f(x) и g i (x) линейные функции, R неотрицательный ортант, а (4.1) переписать в виде обратных

–  –  –

где y ( y i,..., y m ) вектор множителей Лагранжа. Однако применительно к задаче с ограничениями вида (4.1), (4.2) метод множителей Лагранжа нуждается в некоторой модификации, для описания которой нам понадобятся новые важные понятия. Кроме того, метод множителей Лагранжа может быть усилен для некоторых частных случаев общей задачи математического программирования. Важнейшими такими случаями являются линейное программирование, для которого, как будет показано, метод Лагранжа уже фактически был обоснован и использован, и выпуклое программирование, которое будет далее рассматриваться. Кроме того, мы познакомимся с основными численными методами решения задач математического программирования.

–  –  –

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

Рассмотрим теперь минимаксную задачу для функции Лагранжа:

–  –  –

Определение. Задача (4.5), (4.16) называется двойственной к задаче (4.3), (4.4); соотношение ~ v, если оно выполняется, называется соотноv шением двойственности, а теоремы, устанавливающие (при некоторых предположениях) справедливость этого соотношения, называются теоремами двойственности.

Так как выше было показано, что v v и v ~ (последнее для любых v ~, но соотношение двойственнофункций F(x, y)), всегда справедливо v v сти не обязательно должно выполняться, и действительно иногда оно справедливо, а иногда и нет. Выполнение соотношения двойственности связано с существованием седловой точки у функции Лагранжа.

Теорема. Если функция Лагранжа (4.5) имеет седловую точку на R Y, то выполняется соотношение двойственности, причем если (x0, y0) седловая точка функции Лагранжа, то x0 решение задачи (4.3), (4.4), а y0 решение двойственной задачи (4.5), (4.16). Обратно, если задачи (4.3), (4.4) и (4.5), (4.16) имеют решения х0 и у0 и выполнено соотношение двойственности, то (x0, y0) седловая точка функции Лагранжа (4.5).

Доказательство данной теоремы непосредственно вытекает из теоремы об эквивалентности задач (4.3), (4.4) и (4.5), (4.15) и теоремы о необходимых и достаточных условиях существования седловой точки.

Факт существования седловой точки у функции Лагранжа представляет не просто теоретический интерес. На нем основываются методы решения задач математического программирования, в первую очередь, метод множителей Лагранжа. Действительно, если (x0, y0) - седловая точка функции Лагранжа (4.5), то по определению F ( x 0, y 0 ) max F ( x, y 0 ), xR

–  –  –

Уравнения (4.17) представляют собой обычный метод множителей Лагранжа для нахождения экстремума функции с ограничениями на переменные. Однако тут заложены два предположения. Одно, менее существенное, что х0 внутренняя точка множества R. Если это не так, то условия оптимальности претерпевают некоторые изменения, мы это продемонстрируем в дальнейшем на примере задачи выпуклого программирования. Другое предположение, принципиальное, о существовании седловой точки у функции Лагранжа. Если она не существует (а такое действительно может быть), то метод Лагранжа уже не обоснован. Достаточно представительными случаями существования седловой точки у функции Лагранжа, да и то при дополнительных предположениях, являются задача линейного программирования и задача выпуклого программирования.

Рассмотрим задачу линейного программирования в стандартной форме n max c j x j j 1

–  –  –

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

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

Теорема. Для того чтобы x0 было решением задачи линейного программирования, необходимо и достаточно существования y0 такого, что пара (x0, y0) является седловой точкой функции Лагранжа на прямом произведении неотрицательных ортантов.

Достаточность доказана для общей задачи математического программирования, значит, в частности, и для линейного программирования.

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

–  –  –

По определению множества В, очевидно, а 0, так как если ai0, то, выбирая последовательность векторов zkB с zki и остальными компонентами равными нулю, получим a, z k -, что противоречит неравенству (4.18). Далее, так как точка (0,…,0, f(x0)) является предельной для множества В, то имеем из (4.18) с учетом определения множества А m

–  –  –

y Учитывая, что y 0, имеем F(x, y ) F(x, y) у 0. Знаgi ( x0 ) 0 i i 1 чит (х, у ) седловая точка функции F(x, y) на RY. Теорема доказана.

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

Пример 4.3.

f(x)= x, m=1, g(x)= - x2, R=R1.

Очевидно, х=0 есть решение задачи, но у функции F(x, y)= x – yx2 седловой точки нет.

Теорема Куна-Таккера обосновывает сведение задачи выпуклого программирования к задаче поиска седловой точки функции Лагранжа. Задача поиска седловой точки аналогична по сложности задаче поиска экстремума функции, поэтому для того, чтобы такое сведение имело практический смысл, необходимо, чтобы получающаяся экстремальная задача была в чем-то проще исходной. Такое упрощение связано со следующим обстоятельством. Исходная задача представляет собой поиск максимума на множестве Х, которое имеет вид (4.3). Разбиение ограничений, описывающих допустимое множество Х, на xR и gi(x) 0, как уже говорилось, является условным, так как любое ограничение можно записать и в том, и в другом виде. Поэтому обычно под R понимается множество простого вида, это либо все пространство Rп, либо неотрицательный ортант, либо параллелепипед, т.е. границы множества R задаются простыми ограничениями типа а х b.

Сложность же задачи выпуклого программирования определяется системой ограничений gi(х) 0, i 1, m. Так как седловая точка функции Лагранжа ищется на произведении множеств RY, где Y также является множеством простого вида (неотрицательным ортантом), то смысл теоремы Куна-Таккера состоит в сведении задачи поиска экстремума функции со сложными ограничениями на переменные к задаче поиска экстремума новой функции с простыми ограничениями на переменные. Если множество R совпадает со всем пространством Rn, то условия экстремума имеют вид (4.17), причем очень существенным моментом является то, что эти условия являются не только необходимыми для того, чтобы функция F(x, y0) достигала в точке х0 максимума по х, но и достаточными. Это является важным свойством вогнутых функций (а F(x,y) для задачи выпуклого программирования вогнута по х).

Теорема. Для того чтобы непрерывно дифференцируемая вогнутая функция (х) имела в точке х0 максимум на Rn, необходимо и достаточно, чтобы ( х 0 ) =0 (докажите в качестве упражнения).

Таким образом, для нахождения седловой точки функции Лагранжа F(x, y) на произведении RnY, а следовательно, и для нахождения решения х0 задачи выпуклого программирования при R=Rn надо решить систему уравнений (4.17). Но в этой системе п уравнений, а неизвестных, вообще говоря, п+т, так как помимо п-мерного вектора х0 нам неизвестен и т– мерный вектор соответствующих ему множителей Лагранжа у0. Однако, если внимательно просмотреть доказательство теоремы Куна-Таккера, то мы увидим очень важное свойство, которое выполняется для седловой точки функции Лагранжа, а именно, условие (4.21). Так как yi0 0 и gi(x0)0, i 1, m, то из него вытекает, что либо yi =0, либо gi(x )=0, либо то и другое одновременно. Это свойство аналогично второй теореме двойственности линейного программирования. Ограничения, которые выполняются в некоторой точке как равенства, называются активными. Таким образом, только те множители Лагранжа yi0 могут быть отличны от нуля, которые соответствуют активным в точке х0 ограничениям. С учетом этого свойства для нахождения решения задачи выпуклого программирования получаем следующий способ.

Введем множество I ( x) i 1 i m, g i ( x) 0.

Множество I(x) представляет собой совокупность индексов активных в точке х ограничений. Тогда можно утверждать в силу сказанного выше, что yi0=0 i I ( x 0 ).

Поэтому для определения х0 и ненулевых уi0 имеем систему уравнений 0 g i ( x ) f ( x 0 ) 0 <

–  –  –

Теперь перейдем к более общим случаям.

Хотя в качестве множества R, как говорилось, обычно выбирается достаточно простое множество, чтобы не рассматривать каждый случай отдельно, рассмотрим общую ситуацию, когда R произвольное выпуклое множество. Рассмотрение такой ситуации полезно еще и потому, что оно позволяет несколько по-другому подойти к задаче выпуклого программирования. Действительно, если в R включить все ограничения gi(x) 0, то оно будет просто совпадать с множеством Х и задача выпуклого программирования состоит в максимизации вогнутой функции f(x) на выпуклом множестве R (или Х). Поэтому, не конкретизируя вида ограничений и не вводя функцию Лагранжа, можно напрямую рассмотреть функцию f(x) на Х. При этом очень полезным является следующее понятие.

Определение. Направление g является допустимым в точке х, принадлежащей выпуклому множеству Х, если 0 0 такое, что 0 выполняется х+g Х.

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

|g|=1.

Допустимое направление это такое направление, небольшое перемещение вдоль которого не выводит из допустимого множества, т.е. не нарушает ограничений задачи математического программирования. Но если точка х0 является решением задачи математического программирования, т.е. доставляет максимум функции f(x) на Х, то при перемещении вдоль допустимого направления, по определению максимума, функция f(x) не может возрастать. Изменение функции вдоль некоторого направления определяется ее производной по направлению.

Определение. Производной функции f(x) по направлению, задаваемому единичным вектором g, называется величина f ( x g ) f ( x ) f ( x) (4.24) lim, g 0

–  –  –

§ 4.4. Графический метод в нелинейном программировании и геометрический смысл условий Куна-Таккера Задачи нелинейного программирования обладают свойствами, которые усложняют процесс их решения по сравнению с задачами линейного программирования:

1. Множество допустимых планов (мы будем обозначать его буквой

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

2. Глобальный максимум (минимум) может достигаться как внутри множества Х, так и на его границах.

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

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

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

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

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

2) является ли целевая функция выпуклой или вогнутой, или она не относится ни к тому ни к другому классу.

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

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

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

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

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

Заметим, что решение задачи поиска минимума f(x) осуществляется аналогично, лишь движение по линиям уровня должно производиться в направлении обратному градиенту целевой функции, т.е. по вектору (- c ).

Возможна ситуация неограниченности целевой функции f(x) на множестве Х, т.е. сколько бы мы ни перемещались по линиям уровня в направлении вектора c ее значение будет возрастать.

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

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

Задача. На предприятии имеется два вида ресурсов. Определите оптимальное распределение величин затрачиваемых ресурсов на производство некоторого продукта, если цена ресурса первого вида 3 единицы, второго – 4 единицы, а всего на производство выделено 24 единицы. Известно, что из количества х первого ресурса и у второго ресурса можно получить f ( x1, x2 ) x12 x 22 единиц продукта ( f называется производственной функцией).

Р е ш е н и е Математическая модель задачи: на множестве ограничений 3 x1 4 x2 24, Х: x1 0, x 0.

найти максимальное значение функции z= x12 x 22.

–  –  –

§ 4.5. Численные методы нелинейного программирования Хотя теорема Куна-Таккера и вытекающие из нее условия на производные дают характеристику решений задачи математического программирования (по крайней мере выпуклого), они еще не дают конструктивных методов нахождения этих решений для сколь-либо сложных случаев. Рассмотрим некоторые из наиболее распространенных конструктивных (численных) методов, которые так или иначе используют полученные выше условия оптимальности.

1. Градиентные методы Рассмотрим сначала задачу максимизации функции f(x) без ограничений, т.е. в случае, когда Х совпадает со всем пространством Rn. Градиент функции f(x) будем обозначать f(x). Условие оптимальности в этом случае имеет вид f(x)=0, (4.26) однако непосредственное решение системы уравнений (4.26) может оказаться чересчур сложным, поэтому на практике поступают следующим образом. Выбирая произвольную начальную точку х(0), строят итеративный процесс х(k+1) = х(k) + k f(x(k)), k=0,1,2,…. (4.27) Число k называют длиной шага или просто шагом. Если все k равны между собой, то имеем процесс с постоянным шагом.

Процесс (4.27), лежащий в основе градиентных методов, представляет собой движение в сторону возрастания функции f(x), так как если f(x(k)) 0, то всегда можно выбрать k, так, что f(x(k+1))f(x(k)). Существуют разные способы выбора k. Вообще говоря, наилучшим является выбор такого k, при котором обеспечивается максимальный рост функции f(x). Такое k находится из условия f ( x ( k ) k f ( x ( k ) )) max f ( x ( k ) k f ( x ( k ) )). (4.28) Градиентный метод поиска экстремума (4.27) с выбором шага по способу (4.28) называется методом скорейшего подъема (или спуска для задачи на минимум). Такой метод требует наименьшего числа итераций, но зато на каждом шаге приходится решать дополнительную задачу поиска экстремума (4.28) (правда, в одномерном случае). На практике часто довольствуются нахождением любого k, обеспечивающего рост функции.

Для этого берут произвольное k и проверяют условие роста, если оно не выполняется, то дробят k до тех пор, пока это условие не будет выполнено (такое достаточно малое k при f(x(k)) 0 существует всегда).

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

Если рассматривается задача максимизации f(x) при ограничениях, т.е. когда Х не совпадает с Rn, то непосредственное применение процесса (4.27) может привести к нарушению ограничений, даже если начальная точка х(0)Х. Однако эту трудность можно преодолеть, например, если получаемую по формуле (4.27) очередную точку проектировать на множество Х. Если обозначить операцию проектирования точки х на множестве Х через РХ(х), то соответствующий итеративный процесс имеет вид x ( k 1) PХ ( x ( k ) k f ( x ( k ) )). (4.29) Полученный метод носит название метода проекции градиента. Шаг k в методе (4.29) может выбираться различными способами (например, как в методе скорейшего подъема). Стационарная точка этого процесса является решением задачи max f ( x ) в случае вогнутой функции f(x), а в обx X <

–  –  –

Ш а г 1. Так как f(x(0))=(-1;1), по формуле (4.29) находим x(1)=Px[x (0)-f(x(0))]=Px[(0;0,5)-0,75(-1;1)]=Px[(0,75;-0,25)].

Точка (0,75;-0,25) принадлежит допустимому множеству, так как 0,75 +0,252=0,625 1, поэтому х(1)=(0,75; -0,25).

–  –  –

2 (0,9965; 0,0830) 0,289 (-1; 0,1661) (1,7465; -0,0415) 3 (0,9997; -0,0238) 0,107 (-1; -0,0476) (1,7497; 0,0119) 4 (0,99998; 0,00769) 0,031 (-1; 0,0136) (1,74998; -0,00339)

–  –  –

Из таблицы следует, что х0 x(5)=(0,099998; -0,00194), f 0 f(x(5)) -1.

Отметим, что точное решение рассматриваемой задачи fmin=f(1; 0)= -1.

Существуют и другие варианты градиентных методов.

–  –  –

Идея методов возможных направлений, близкая к идее градиентных методов для задач с ограничениями, состоит в следующем: на каждой итерации определяется допустимое направление на множестве Х, вдоль которого функция f(x) возрастает (такое направление называется возможным направлением возрастания функции f(x)), и по нему совершается шаг. Фактически в методе проекции градиента и в методе условного градиента мы находим такие направления. Однако там исходным было определение градиента, а допустимое направление определялось по нему однозначно. В методах же возможных направлений исходным пунктом является описание всех допустимых направлений и выбор из них такого, вдоль которого функция f(x) возрастает и желательно скорейшим образом.

Рассмотрим вариант метода возможных направлений применительно к задаче максимизации f(x) на множестве (4.3), где R=Rn. Пусть мы имеем k-е приближение х(k) к решению этой задачи и для построения следующего приближения поставим следующую вспомогательную задачу: максимизировать и при ограничениях f ( x ( k ) ), a u, g ( x ( k ) ), a u, i Ik, a j 1, j 1, n, где I k i | 1 i m, gi ( x ( k ) ) 0, a (a1,, a n ).

Эта задача представляет собой задачу линейного программирования в (п+1)–мерном пространстве векторов (а, и). Множество допустимых планов замкнуто, ограничено и непусто, так как а=0, и=0 является допустимым планом. Значит вспомогательная задача имеет решение (аk, иk), причем иk 0. Если иk 0, то нетрудно показать, что направление аk является возможным направлением возрастания функции f(x), т.е. точка х(k+1)=х(k)+ kа при достаточно малом k принадлежит множеству Х и обеспечивает k большее значение функции f(x), чем х(k). Выбор пары (аk, иk) с возможно большим значением иk при этом означает выбор допустимого направления, наиболее близкого к градиенту функции f(x), т.е. возможного направления с наибольшим ростом функции. Если иk = 0, то получается стационарная точка процесса, которая для задачи выпуклого программирования дает решение, а в общем случае требует дополнительного исследования. Для линейных функций gi (x) можно заменять в правых частях ограничений вспомогательных задач и на нуль.

–  –  –

Решением этой задачи является а0 = (0,5;-1), а максимальное значение вспомогательной целевой функции равно 7. Значит исходная целевая функция по направлению аk убывает, причем если сделать шаг с =2,8, то сразу получаем х(1) точку минимума целевой функции с координатами (5,4;4,2) (иначе ее надо взять в качестве начальной точки для конструирования следующей итерации).

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

–  –  –

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

Составим функцию Лагранжа F ( x, y ) 2 x1 4 x 2 x12 2 x 2 + y1 (8 x1 2 x 2 ) + y 2 (12 2 x1 x 2 ).

–  –  –

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

Рассмотрим общую задачу математического программирования (4.3), (4.4):

.

X x x R, g i ( x) 0, i 1, m max f ( x), x X

–  –  –

4. На двух предприятиях отрасли необходимо изготовить 200 изделий некоторой продукции. Затраты, связанные с производством x1 изделий на первом предприятии, равны 4x12 ден.ед., а затраты, обусловленные изготовлением x2 изделий на втором предприятии, составляют 20 x2 6 x22 ден.ед. Определить, сколько изделий на каждом из предприятий следует произвести, чтобы общие затраты, обусловленные изготовлением необходимой продукции, были минимальными.

5. f=x12+x22 при условии x1+x2=5.

–  –  –

Найдите минимальное значение функции в задачах 10-14.

Указание. 10-12 целесообразнее решать методом штрафных функций, 13-14 — методом возможных направлений

–  –  –

Найдите максимальное значение функции в задачах 15-17.

Указание. Решите несколькими способами и сделайте вывод о том, какой метод наиболее рационален.

–  –  –

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

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

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

–  –  –

f ( k ) ( x, u ) — заданная n-мерная вектор-функция аргументов x R n, u R m.

Таким образом, предполагается, что в результате k-го шага процесс переходит в состояние x (k ), которое определяется только начальным состоянием x ( k 1) этого шага и выбранным на нём вектором управления u (k ) и не

–  –  –

где X k и U k ( x ( k 1) ) заданные множества в пространствах R n и R m соответственно, причём множество U k зависит от начального состояния x ( k 1) kго шага.

Ограничения на начальное и конечное состояния процесса x X 0, x ( N ) X N называются начальными и конечными условиями.

(0)

–  –  –

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



Pages:   || 2 | 3 |
Похожие работы:

«Обобщение педагогического опыта на тему: Нетрадиционные техники рисования как средство развития творческих способностей детей дошкольного возраста. Самойлова Любовь Николаевна Содержание Тема опыта. Усл...»

«Муниципальное бюджетное общеобразовательное учреждение "Средняя общеобразовательная школа № 64" городского округа "Город Лесной" Свердловской области ПРИНЯТО УТВЕРЖДАЮ на педагогическом совете Директор МБОУ СОШ № 64 протокол № 1 от 29.08.2014 г Т.А. Потапова ""_20г. Рабочая программа по учебно...»

«М.А. Кантурова Новосибирский государственный педагогический университет Образование вторичного речевого жанра как деривационный процесс (на примере речевого жанра кулинарного рецепта...»

«Муниципальное бюджетное образовательное учреждение дополнительного образования Центр Детского Творчества "Олчей удазыны" Тоджинского района Республики Тыва БАЗИСНЫЙ УЧЕБНЫЙ ПЛАН НА 2016-2017 УЧЕБНЫЙ Г...»

«20 Проблемы преподавания физики Аскадинова Заира Магомедсаидовна, магистрант 1 года обучения Махачкала, Дагестанский государственный университет, физический Математический язык при изучении физики в общеобразовательн...»

«Волчанская Н. Ф. Здоровый образ жизни как фактор развития волевых качеств подрастающего поколения // Концепт. – 2013. – № 10 (октябрь). – ART 13204. – 0,4 п. л. – URL: http://e-koncept.ru/2013/ 13204.htm....»

«А.Я. Белов, г. Рамат-Ган, Израиль Р. Явич, г. Нетания, Израиль Проблемы одарённости и стадийность математического обучения (к работе И.С. Рубанова "Как обучать методу математической индукции"). Проблем...»

«Погодина Светлана Викторовна РАЗВИТИЕ ДЕТСКОГО ИЗОБРАЗИТЕЛЬНОГО ТВОРЧЕСТВА ПОД ВЛИЯНИЕМ ХУДОЖЕСТВЕННЫХ ЭТАЛОНОВ В РАМКАХ КОНЦЕПЦИИ ТРАНСФОРМИРУЕМЫХ ЭСТЕТИЧЕСКИХ АРХЕТИПОВ Специальность 13.00.02 – теория и мето...»

«Рабочая программа по внеурочной деятельности "Юным умникам и умницам" 2 класс Класс: 2 "А" Учитель: Белова Т. Ю. Количество часов в год: 34 В неделю: 1 Планирование составлено на основе программы: "РПС" Учебник: "...»

«ФРАНЦУЗСКИЙ НОВЫЙ РОМАН В 50 Е ГГ. ХХ В. А.Г. Вишняков Кафедра французского языка Московский государственный областной педагогический институт ул. Зеленая, 3, Орехово-Зуево, Москов...»

«Уколова Любовь Ивановна Педагогически организованная музыкальная среда как средство становления духовной культуры растущего человека 13.00.08 теория и методика профессионального образова...»

«Источник http://psy.1september.ru/view_article.php?id=200900409 Людмила ЛЕБЕДЕВА, доктор педагогических наук, Российский государственный социальный университет, Москва Экстренная арт-терапевтическая помощь в ситуациях острого стресса Арт-терапевтические игры, упражнения и техники — эффективная...»

«Серія "Родовід Сердюків" ЗАПИСКИ СЕРДЮКА Николая Павловича 317724, Кировоградская обл., Долинский район, с. Кирово, ул. Ленина, 6. УДК 929.52 Сер (477) ББК 63.2 Укр С 32 В оригинальной манере повествования рукою простого сельского учителя описаны жизни и судьбы многих людей, в т.ч. представит...»

«РОССИЙСКАЯ ФЕДЕРАЦИЯ (19) (11) (13) RU 2 521 208 C1 (51) МПК G01K 17/08 (2006.01) ФЕДЕРАЛЬНАЯ СЛУЖБА ПО ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ (12) ОПИСАНИЕ ИЗОБРЕТЕНИЯ К ПАТЕНТУ 2013106349/28, 13.02.2013 (21)(22) Заявка: (72) Автор(ы): Чесноков Владимир Владимирович (RU), (24) Дата начала отсчета срока действия патента: Чесно...»

«Муниципальноеказенное общеобразовательное учреждение "Викторовская средняя общеобразовательная школа" Кореневского района Курской области (полное наименование образ...»

«Муниципальное автономное дошкольное образовательное учреждение города Нижневартовска детский сад № 80 "Светлячок" Консультация для родителей по художественноэстетическому развитию г. Нижневартовск Не сомневаюсь в том, что каждый из вас, дорогие мамы и папы, хочет вос...»

«Муниципальное бюджетное общеобразовательное учреждение "Средняя общеобразовательная школа № 14 г. Назарово Красноярского края" УТВЕРЖДАЮ Принята на методическом Директор МБОУ "СОШ 14" объединении учителей математики _В.Ф.Цветцых Протокол №10 от 25.06.2016 Приказ №01-04-64/3 от 26.08.2016 Рабочая программа по...»

«План проведения праздников и развлечений Месяц Форма работы Тема мероприятия Группа Праздник, посвященный Дню Здравствуй, детский сад! все группы Сентябрь знаний Игровой досуг "Озорные ладошки" 1 младшая "Беззаботный зайка" (кукольный театр) "В гостях у Петрушки" 2 младшая "Беззаботный зайка" (кукольный театр) "Ба...»

«УДК 378 Е.А.Шамонин, А.М. Плещёв, г. Шадринск Понятие и сущность познавательной самостоятельности будущих учителей физической культуры В статье анализируется понятие и сущность когнитивной составляющей будущего учителя. Так же содержание понятий "познание" и "самостоятельность" Познание, самостоятельность, познавательная...»

«Министерство образования и науки Российской Федерации Муниципальное бюджетное дошкольное образовательное учреждение детский сад общеразвивающего вида с приоритетным осуществлением художественно-эстетического направления развития воспитанников № 255 г.Челябинск, ул. Пети К...»

«Алексеева О. В. Особенности создания информационного буклета педагогом // Концепт. – 2016. – Спецвыпуск № 02. – ART 76021. – 0,3 п. л. – URL: http://e-koncept.ru/2016/76021.htm. – ISSN...»

«руются все основные черты характера и качества личности. Затем в воспитании включаются различные социальные институты: детский сад. школа, секции, кружки и т.д. Чем старше становится ребенок, тем ши­ ре, разнообразнее и сложнее то взаимодействие, в которое он вовлека­ ется. Он входит в состав разли...»

«Принято педагогическим Советом Д.Д.Шкаредный протокол №1 от 30.08.16г. УЧЕБНЫЙ план Муниципального казенного общеобразовательного учреждения Лицея №9 города Слободского Кировской области на 2016 2017 учебный г...»








 
2017 www.doc.knigi-x.ru - «Бесплатная электронная библиотека - различные документы»

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