«26 сентября 2008 г. Содержание Предисловие 1 1 Вводная лекция 6 Тест для самоконтроля к лекции 1................. 14 I Принятие решений в условиях определённости 16 2 Экстремум функций одной переменной ...»

Математические модели

принятия решений в экономике

Учебное пособие

В.В. Розен Л.В. Бессонов

26 сентября 2008 г.

Содержание

Предисловие 1

1 Вводная лекция 6

Тест для самоконтроля к лекции 1................. 14

I Принятие решений в условиях определённости 16 2 Экстремум функций одной переменной 17 Тест для самоконтроля к лекции 2................. 27 3 Оптимизация при наличии ограничений 31 Тест для самоконтроля к лекции 3................. 43 4 Задачи линейного программирования 47 Тест для самоконтроля к лекции 4................. 5 Принятие решений при многих критериях (многокритериальная оптимизация) Тест для самоконтроля к лекции 5................. 6 Проблема построения обобщенного критерия в многокритериальной ЗПР Тест для самоконтроля к лекции 6................. 7 Задачи, решаемые при наличиии карты безразличий Тест для самоконтроля к лекции 7.................

РЕЗЮМЕ И ЗАКЛЮЧИТЕЛЬНЫЕ ЗАМЕЧАНИЯ K РАЗДЕЛУ I

II Принятие решений в условиях неопределенности и риска 8 Принятие решений в условиях неопределенности Тест для самоконтроля к лекции 8................. 9 Принятие решений в условиях риска Тест для самоконтроля к лекции 9................. 10 Критерий ожидаемой полезности Тест для самоконтроля к лекции 10................ 11 Использование смешанных стратегий как способ уменьшения риска Тест для самоконтроля к лекции 11................ 12 Принятие решения в условиях риска с возможностью проведения эксперимента Тест для самоконтроля к лекции 12................

РЕЗЮМЕ И ЗАКЛЮЧИТЕЛЬНЫЕ ЗАМЕЧАНИЯ K РАЗДЕЛУ II

III ТЕОРЕТИКО–ИГРОВЫЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ

13 Антагонистические игры Тест для самоконтроля к лекции 13................ 14 Методы нахождения решения матричной игры в смешанных стратегиях Тест для самоконтроля к лекции 14................ 15 Игры лиц в нормальной форме Тест для самоконтроля к лекции 15................ 16 Нахождение оптимальных решений биматричных игр в смешанных стратегиях Тест для самоконтроля к лекции 16................ 17 Кооперативные игры Тест для самоконтроля к лекции 17................ 18 Оптимальные исходы в кооперативных играх Тест для самоконтроля к лекции 18................

РЕЗЮМЕ И ЗАКЛЮЧИТЕЛЬНЫЕ ЗАМЕЧАНИЯ K РАЗДЕЛУ III

Заключение Ответы на тестовые задания ЛИТЕРАТУРА ОСНОВНАЯ ДОПОЛНИТЕЛЬНАЯ Основной целью предлагаемого пособия является обсуждение принципиальных аспектов построения и анализа математических моделей принятия решений в экономике.

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

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

Рекомендуется для студентов экономических специальностей в качестве математической поддержки дисциплин "Экономико–математическое моделирование "Математическое моделирование социально–экономических процессов "Микроэкономика".

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

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

Математические модели принятия решений можно разбить на два больших класса — оптимизационные и теоретико-игровые. Оптимизационные модели уходят своими корнями в классический математический анализ и имеют весьма "почтенный"возраст. Теоретико-игровые модели начали исследоваться лишь в последние десятилетия — после выхода в 1944 году фундаментальной монографии "Теория игр и экономическое поведение". Этим названием авторы (один из которых — Джон фон Нейман — был выдающимся математиком, а другой — Оскар Моргенштерн — известным экономистом), хотели подчеркнуть взаимосвязь между экономикой и теорией игр. Однако только в наши дни глубина проникновения теории игр в экономику была оценена в полной мере. Наиболее концентрированным выражением этого явилось присуждение Нобелевской премии 1994 года по экономике трем профессиональным математикам за их исследования по теории игр. Механизмы функционирования рынка, конкуренции, возникновения или краха монополий, а также способы принятия ими решений в условиях конкурентной борьбы, то есть механизмы игры монополий, действующие в экономической реальности, — не могут быть исследованы и поняты без теории игр.

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

Задача N 1 — Задача об оптимальном размере закупаемой партии товара (экстремум функции одной переменной);

Задача N 2 — Задача максимизации производственной функции (оптимизация при наличии ограничений);

Задача N 3 — Распределение заказа между двумя фирмами (условный экстремум функции);

Задача N 4 — Задача производственного планирования (линейное программирование);

Задача N 5 — Задача о смеси (линейное программирование);

Задача N 6 — Задача о перевозках — транспортная задача (линейное программирование);

Задача N 7 — Выбор места работы (многокритериальная оптимизация — дискретный случай);

Задача N 8 — Оптимизация производственного процесса (многокритериальная оптимизация — непрерывный случай);

Задача N 9 — Сравнение объектов по предпочтительности (многокритериальная оптимизация со сравнимыми критериями);

Задача N 10 — Исследование потребительских предпочтений (многокритериальная оптимизация при заданном локальном коэффициенте замещения);

Задача N 11 — Выбор проекта электростанции (принятие решения в условиях неопределенности);

Задача N 12 — Выбор варианта производимого товара (принятие решений в условиях риска — дискретный случай);

Задача N 13 — Сравнение качества обслуживания станций скорой помощи (принятие решения в условиях риска по критерию ожидаемой полезности);

Задача N 14 — Задача об оптимальном портфеле (принятие решения в условиях риска — непрерывный случай);

Задача N 15 — Бурение нефтяной скважины (принятие решения в условиях риска с возможностью проведения эксперимента);

Задача N 16 — Профилактика нежелательного события (решение матричной игры в чистых стратегиях);

Задача N 17 — Выбор момента поступления товара на рынок в условиях антагонистической конкуренции (решение матричной игры в смешанных стратегиях);

Задача N 18 — Планирование посева в неопределенных погодных условиях (графоаналитический метод нахождения решения матричной Задача N 19 — Инспекция предприятий торговли (решение матричной игры в смешанных стратегиях);

Задача N 20 — Задача распределения ресурсов (ситуации равновесия в игре общего вида);

Задача N 21 — Борьба за рынки сбыта (ситуации равновесия в биматричной игре);

Задача N 22 — Оптимальное распределение прибыли (кооперативное решение игры без разделения полезности);

Задача N 23 — Рынок трех лиц (построение характеристической функции кооперативной игры);

Задача N 24 — Оптимальное распределение прибыли (кооперативное решение игры с разделением полезности);

Задача N 25 — Оценка "силы"держателей акций (вектор Шепли для кооперативной игры).

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

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

ряд примеров заимствован нами из этих источников.

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

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

Настоящее пособие сложилось на основе курса лекций, читаемого автором в Высшей школе Бизнеса при Саратовском Государственном Техническом Университете и в Саратовском филиале Московского Международного Университета Бизнеса и Информационных Технологий.

Лекция Принятие решений в экономике.

Математические модели принятия решений (общее описание) Основные вопросы: 1. Экономика как система. Централизованная и децентрализованная экономика. Некоторые черты принятия решений в микроэкономических системах. 2. Системное описание задачи принятия решения (ЗПР). 3. Математическая модель задачи принятия решения. Реализационная и оценочная структура задачи принятия решения.

Особенности математических моделей принятия решений в экономике.

4. Методика исследования задач принятия решения на основе математического моделирования.

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

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

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

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

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

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

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

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

2. Наиболее общий подход к описанию задач принятия решений формулируется "на языке систем". Приведем в этом пункте системное описание задач принятия решений (ЗПР).

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

Управляющая подсистема может воздействовать на объект управления с помощью альтернативных управляющих воздействий (рис.1.1.). Состояние объекта управления определяется двумя факторами: 1) выбранным управляющим воздействием со стороны управляющей подсистемы и 2) состоянием среды. Принципиальным является следующее обстоятельство: управляющая подсистема не может воздействовать на среду и, более того, она, как правило, не имеет полной информации о наличном состоянии среды.

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

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

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

3. Математическая модель принятия решения представляет собой формализацию той схемы, которая приведена в системном описании ЗПР.

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

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

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

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

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

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

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

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

1. Принятие решения в условиях определенности характеризуется тем, что состояние среды является фиксированным (неизменным), причем управляющая система "знает в каком состоянии находится среда.

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

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

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

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

В математической модели ЗПР оценочная структура может задаваться различными способами.

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

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

Замечание. Иногда используется отношение предпочтения исходов ; запись 1 2 читается: "исход 1 не менее предпочтителен, чем исход Еще один способ задания оценочной структуры — разбиение множества исходов на два класса: 0 — класс "плохих"исходов и 1 — класс "хороших"исходов. Существуют и другие способы задания оценочной структуры.

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

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

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

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

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

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

В заключение этого пункта укажем некоторые особенности математических моделей задач принятия решений в экономике. Как уже отмечалось, в микроэкономических ситуациях принятия решений в качестве субъекта, принимающего решение (то есть в качестве управляющей подсистемы) чаще всего выступает фирма. Что выступает здесь в качестве среды? Это может быть и природная среда (или ее аналог), и конкурирующая фирма, и покупатели, и законодательный орган и т.п. Хотя при построении модели принятия решения в общем случае невозможно однозначно указать — что является средой, полезно руководствоваться следующим принципом: среда — это то, что определяет при каждой фиксированной альтернативе появление того или иного исхода. Другими словами, в качестве среды выступает та система (структура, организация, физическое лицо), фиксирование состояния которой приводит при выборе управляющей подсистемой любой конкретной альтернативы к однозначно оцениваемому ею результату.

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

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

1-й этап - построение математической модели ЗПР;

2-й этап — формулировка принципа оптимальности и нахождение оптимального решения;

3-й этап - анализ полученных результатов.

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

Реализация 2-го этапа связана с введением принципа оптимальности.

Универсального понятия оптимального решения, которое годилось бы для любой ЗПР, не существует. Поэтому в теории принятия решений рассматривают отдельные классы задач принятия решений и для каждого класса формулируют свой принцип оптимальности. Задача нахождения оптимального решения (в смысле некоторого указанного принципа оптимальности) является уже формальной задачей и решается математическими средствами. Следует отметить, что для ЗПР данного класса может существовать не один, а несколько различных принципов оптимальности; кроме того, даже при фиксированном принципе оптимальности может быть не одно, а несколько оптимальных решений. Это объясняет необходимость следующего — 3-го этапа, который состоит в анализе полученных результатов. Этот анализ проводится на содержательном уровне и заключается, говоря схематически, в соотнесении формально полученных рекомендаций с требованиями задачи принятия решения. В случае, когда полученное формальным способом оптимальное решение по каким-либо причинам оказывается неприемлемым, то это приводит либо к выбору другого оптимального решения (если оно имеется), либо к смене принципа оптимальности, либо к изменению самой математической модели ЗПР.

Тест для самоконтроля к лекции 1. В математической модели принятия решения <,, > есть множество....1....;

есть множество....2....;

есть множество....3....;

Варианты ответов: а) исходов альтернатив состояний среды (выбрать порядок) б) альтернатив состояний среды исходов 2. Реализационная структура ЗПД устанавливает связь между.........

Варианты ответов: а) альтернативами и состояниями среды 3. Если управляющая система знает о состоянии среды, то принятие решения происходит в условиях...

Варианты ответов: а) неопределенности 4. Если управляющая система знает распределение вероятностей на множестве состояний среды, то принятие решения происходит в условиях...

Варианты ответов: а) определенности Принятие решений в условиях определённости Лекция Экстремум функций одной переменной Основные вопросы: 1. Этапы исследования ЗПР в условиях определенности. 2. Основные теоремы об экстремумах и методы нахождения экстремумов функции одной переменной. 3. Задача № 1: Задача об оптимальном размере закупаемой партии товара.

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

(a) альтернативы и исходы могут быть отождествлены ( = ) (b) целевая функция становится функцией только переменной.

Итак, 1-й этап исследования ЗПР в условиях определенности — построение математической модели — сводится здесь к указанию множества допустимых альтернатив и заданию целевой функции : R.

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

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

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

Замечание. Если целевая функция в некоторой ЗПР рассматривается как функция потерь, то при задании отношения предпочтения на множестве надо в формуле (2.1) знак неравенства в правой части повернуть в противоположную сторону; в этом случае оптимальной будет та допустимая альтернатива, которая доставляет минимум (наименьшее значение) функции потерь.

Таким образом, исследование математической модели ЗПР в условиях определенности сводится к трем шагам:

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

) заданию целевой функции : R;

) нахождению максимума или минимума функции.

2. При рассмотрении математических моделей ЗПР возникают два основных вопроса:

(1) Существует ли оптимальное решение и (2) Если оптимальное решение существует, то как его найти.

Для ЗПР в условиях определенности все сводится к нахождению максимума или минимума целевой функции. В случае, когда множество допустимых альтернатив конечно, обе проблемы легко разрешимы. Ответ на вопрос (1) всегда утвердительный (так как в конечном множестве = { () : } всегда есть наименьший и наибольший элементы).

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

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

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

Определение. Пусть задана функция : R. Точка * называется точкой глобального максимума (глобального минимума) функции, если для всех выполняется неравенство () (* ) (соответственно, () (* )).

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

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

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

Определение. Пусть задана функция : R. Говорят, что в точке 0 функция имеет локальный максимум, если существует открытый интервал, содержащий точку 0 и целиком содержащийся в, такой, что в пределах этого интервала функция имеет наибольшее значение в точке 0. Формально: существует такое положительное число > 0, что интервал (0, 0 + ) содержится в и для всех (0, 0 + ) выполняется неравенство () (0 ).

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

Различие между локальным и глобальным экстремумом видно из рис.2.1.:

здесь единственной точкой глобального максимума является точка 3, а точками локального максимума будут {1, 3, 5 }; единственной точкой глобального минимума является точка 4, а точками локального минимума являются {2, 4 }.

Рассмотрим теперь способы нахождения экстремумов дифференцируемой функции, заданной на замкнутом интервале [, ]. Основной принцип: если — точка локального экстремума дифференцируемой функции, то ее производная в этой точке равна нулю: () = (геометрически это означает, что касательная, проведенная к графику функции в соответствующей точке, параллельна оси, см. рис.2.1).

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

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

Далее, очевидно, что если 0 — точка глобального экстремума, являющаяся внутренней точкой интервала [, ], то 0 также будет точкой локального экстремума и в силу основного принципа будет стационарной точкой.

Однако глобальный экстремум — в отличие от локального — может достигаться не только во внутренней точке замкнутого интервала [, ], но и на его границе (то есть в точке или ) — см. рис.2.2. Учитывая это обстоятельство, получаем окончательно Правило 2.1. Для дифференцируемой функции (), заданной на замкнутом интервале [, ], точки глобального экстремума содержатся во множестве критических точек являющемся объединением множества стационарных точек функции и концов интервала [, ].

Основанный на правиле 2.1 метод нахождения точек глобального экстремума дифференцируемой функции, заданной на отрезке [, ], состоит в следующем: надо, во-первых, найти множество всех критических точек функции и, во-вторых, сравнить значения функции во всех ее критических точках; та критическая точка *, в которой значение функции оказалось наибольшим, будет точкой глобального максимума, а критическая точка 0, в которой значение функции оказалось наименьшим, — точкой глобального минимума.

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

Задача № 1: задача об оптимальном размере закупаемой партии товара.

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

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

— требуемое количество товара на плановый период;

0 — стоимость единицы товара;

1 — стоимость заказа одной партии товара (считается, что стоимость заказа не зависит от величины заказываемой партии);

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

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

Решение. В соответствии с методикой, изложенной в п.4 лекции 1, необходимо реализовать три этапа.

1-ый этап — построение математической модели ЗПР. Здесь он сводится к нахождению функции суммарных затрат в зависимости от величины заказываемой партии товара. Пусть — величина заказываемой партии товара (по смыслу должно выполняться 0 <, то есть = (0, ]). Затраты фирмы состоят из трех частей:

() Затраты на покупку товара. Они равны 0 и не зависят от величины заказываемой партии товара.

() Затраты на заказы в течение планового периода. Число заказов равно / (точнее: /, если это число оказывается целым, и [/]+1 в противном случае; в нашей модели этим обстоятельством мы пренебрегаем). Отсюда суммарная стоимость заказов в течение планового периода будет равна 1 /.

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

Итак, пусть количество товара, хранимого в течение некоторого временного периода [, ], задается неотрицательной функцией () 0, — стоимость хранения единицы товара в течение всего периода времени =. Какова должна быть стоимость хранения товара за период времени ?

Для решения этой задачи изобразим на координатной плоскости (по оси абсцисс откладывается время, по оси ординат — количество товара) график функции () (рис.2.3.). Разобьем, как это принято при построении определенного интеграла, интервал [, ] точками деления = 0 < точку и положим = 1. Считая, что за малый промежуток времени количество товара меняется незначительно, можем считать, что в течение временного периода [1, ] количество товара остается практически неизменным и равным ( ). Учитывая, что стоимость хранения пропорциональна количеству хранимого товара и времени хранения, получаем, что стоимость хранения товара в течение периода [1, ] приблизительно равна ( ), откуда общая стоимость хранения Точное значение получается при переходе к пределу при условии, что 0, где = max, учитывая, что сумма, стоящая в правой части(2.2), является интегральной суммой, при переходе к пределу получаем определенный интеграл:

Итак, Так как () есть среднее значение функции () на интервале [, ], приходим к следующему простому правилу:

Стоимость хранения переменного количества товара в течение некоторого временного периода равна стоимости хранения среднего количества товара за этот период. (Согласно (2.3) стоимость хранения получается умножением среднего количества хранимого товара на стоимость хранения единицы товара в течение всего временного периода.) Вернемся к подсчету стоимости хранения товара в задаче № 1. В нашем случае переменное количество товара изображается графически в виде системы параллельных отрезков, см. рис.2.4. (Пояснение: Считаем, что заказы товара происходят в моменты времени 0, 1,..., 1 ; так как товар расходуется равномерно, то его количество равномерно убывает на каждом интервале [1, ] ( = 1, ) и потому оно изображается графически на этом интервале прямой отрицательного наклона.) Среднее значение функции, график которой изображен на рис.2.4, может быть подсчитано элементарно как отношение суммарной площади построенных прямоугольных треугольников к суммарной длине их оснований и равно, очевидно, /2. По указанному правилу затраты на хранение товара в течение планового периода составляют 2 /2, а суммарные затраты выражаются в виде следующей функции:

заданной в области = (0, ].

Построением целевой функции (в данном случае — функции потерь) заканчивается 1-й этап.

2-й этап — исследование построенной функции на экстремум. Находим производную: () = 2 +. В случае, когда числовые значения величин, 0, 1, 2 заданы, нахождение экстремума сводится к нахождению стационарных точек, то есть к решению уравнения () = 0, и сравнению значений функции в стационарных точках и граничных точках интервала (см. п.2). В нашем случае попробуем проанализировать поведение функции () в зависимости от величин, 0, 1, 2, рассматриваемых как параметры. С этой целью найдем интервалы распределения знаков производной. Имеем:

Итак, для функции () имеется единственная стационарная точка * = 21 /2, причем левее точки * функция () убывает, а правее точки * — возрастает. Может быть два случая: (a) * (то есть * );

(b) * > (то есть * ). В случае (a) очевидно, что * — единственная точка глобального минимума функции () на интервале (0, ] (рис.2.5a). В случае (b) точкой глобального минимума функции () на интервале (0, ] будет точка (рис.2.5b). При этом случай (a) имеет место, когда 21 /2, то есть 21 /2 ; случай () имеет место, когда < 21 /2.

3-й этап — анализ результатов. Оптимальная величина * заказываемой партии товара зависит от соотношения между параметрами 1, 2,. Попробуем установить характер этой зависимости "на уровне здравого смысла".

1) * должна быть монотонно возрастающей функцией от. (Обоснование: если при неизменной плате за заказы и за хранение потребуется большее количество товара, то и величина заказываемой партии должна быть увеличена.) 2) * должна быть монотонно возрастающей функцией от 1. (Обоснование: при увеличении стоимости заказов 1 выгодно уменьшить их число, а для этого надо увеличить размер заказываемой партии.) 3) * должна быть монотонно убывающей функцией от 2. (Обоснование: при увеличении стоимости хранения выгодно уменьшить количество хранимого товара, а для этого надо уменьшить размер заказываемой партии.) Функция = 21 /2 удовлетворяет всем перечисленным условиям.

Далее, возьмем какой-нибудь частный случай, например, * = (то есть когда оптимальным является решение о заказе всего требуемого товара целиком). Согласно формальным выкладкам, проведенным выше, такая ситуация наступает при выполнении условия (b): < 21 /2. Интуитивно ясно, что решение * = будет оптимальным тогда, когда требуемое количество товара "не слишком велико а плата за хранение "достаточно мала"по сравнению с платой за заказы. Но тогда решение "заказать весь товар целиком"будет тем более верным при уменьшении, увеличении 1 и уменьшении 2, что как раз имеет место для критерия: < 21 /2.

Видим, что содержательный анализ здесь согласуется с формальными результатами.

Итак, оптимальное решение для задачи 1 состоит в следующем: если < 21 /2, то надо весь товар заказать целиком; если 21 /2, то надо заказывать товар партиями по 21 /2 за один заказ.

Тест для самоконтроля к лекции 1. Точка * называется точкой глобального максимума функции, 2. Точка * называется точкой локального максимума функции, если 3. Достигает ли непрерывная функция, заданная на открытом интервале (, ), глобальных экстремумов?

4. Достигает ли функция, заданная на замкнутом интервале [, ], глобальных экстремумов, если она не является непрерывной?

5. Если точка * - точка локального экстремума функции (), то ее производная в этой точке....

Варианты ответов: а) равна 6. Из квадратичного листа жести с длиной стороны изготавливается прямоугольная коробка. Какова ее наибольшая вместимость?

Варианты ответов: а) 7. Чтобы попасть из пункта А в пункт В, автомобиль должен проехать вначале по лугу, а затем по прямолинейному шоссе. Скорость движения автомобиля по шоссе вдвое больше, чем по лугу. Ближайшей к точке А, находящейся на шоссе, является точка О, удаленная на расстояние от нее. На каком расстоянии от точки О автомобиль должен выйти на шоссе, чтобы затратить на путь минимальное время?

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

Варианты ответов: а) 9. Определить размеры открытого бассейна объемом 323 с квадратным дном так, чтобы на облицовку его дна и стен ушло наименьшее количество материала.

Варианты ответов: а) 10. Одна река имеет форму прямой 2 = 0, а другая – форму параболы = 2. Найти наименьшую длину канала, соединяющего эти реки.

Варианты ответов: а) 11. Найти оптимальный размер закупаемой партии товара при следующих данных:

Варианты ответов: а) 12. Найти оптимальный размер закупаемой партии товара при следующих данных:

Варианты ответов: а) Лекция Оптимизация при наличии ограничений Основные вопросы: 1. Экстремум функции нескольких переменных. 2. Графический способ нахождения экстремума функции 2-х переменных. Задача № 2: Задача максимизации производственной функции. 3. Условный экстремум функции. Метод множителей Лагранжа.

Задача № 3: Распределение заказа между двумя фирмами.

1. В этой лекции рассматриваются задачи принятия решений в условиях определенности, задаваемые целевыми функциями вида : R, где R, > 1; множество называется в этом случае допустимой областью. Нахождение оптимального решения такой ЗПР сводится к нахождению экстремума целевой функции в допустимой области (см.

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

Пояснение. Условие замкнутости области эквивалентно тому, что содержит свою границу; условие ограниченности области означает, что содержится в некотором шаре достаточно большого радиуса.

Укажем простое доказательство теоремы Вейерштрасса, основанное на понятии компактности. Как известно, в пространстве R замкнутость и ограниченность множества эквивалентны его компактности, таким образом, множество является здесь компактным. Далее, образ компактного множества при непрерывном отображении также является компактным, поэтому множество = { () : } будет компактным, а так как оно содержится в R, оно будет иметь наименьший элемент (0 ) и наибольший элемент (* ), где 0, *. Получаем, что 0 — точка глобального минимума, а * — точка глобального максимума функции в допустимой области.

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

Как и в случае функции одной переменной, глобальный экстремум функции переменных, где > 1, может достигаться либо во внутренней точке допустимой области, либо в граничной точке области. Для дифференцируемой функции переменных основной принцип, позволяющий выделить множество внутренних точек области, среди которых находятся точки глобального экстремума, — это следующий Принцип стационарности. Пусть () — дифференцируемая функция, заданная в области R. Если функция имеет глобальный экстремум во внутренней точке 0 области, то 0 является стационарной точкой функции (то есть все частные производные функции в точке 0 должны быть равны нулю).

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

Вот простое обоснование этого утверждения. Предположим, что — внутренняя точка области, в которой функция достигает, например, глобального максимума, и вектор grad в точке 0 отличен от нуля.

Сдвинемся из точки 0 по направлению градиента в некоторую точку *, оставаясь при этом в области (это можно сделать потому, что точка — внутренняя). Так как в направлении градиента функция возрастает, получаем (* ) > (0 ) в противоречие с тем, что 0 — точка глобального максимума функции в области.

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

St — множество стационарных точек функции ;

Fr — множество граничных точек области ;

Kr — множество критических точек функции, являющееся объединением множества стационарных и граничных точек:

Правило 3.1. Пусть — дифференцируемая функция, заданная в области R. Точки глобального экстремума функции содержатся в множестве Kr ее критических точек.

Замечание. Хотя правило 3.1 внешне вполне аналогично правилу 2.1 (и является его непосредственным обобщением), однако практическое применение этого правила для нахождения глобального экстремума функции переменных возможно лишь в простейших случаях (в основном при = 1, 2, 3). Дело в том, что в случае = 1 множество лежит на прямой и его граница Fr имеет, как правило, очень простую структуру (например, для замкнутого интервала = [, ] его граница состоит из двух точек и — концов этого интервала). В случае = множество лежит на плоскости и его граница представляет собой некоторую кривую. Поэтому для нахождения точек глобального экстремума здесь можно использовать графические методы (в сочетании с аналитическими). В некоторых простых случаях аналогичный прием можно использовать для = 3. Однако при > 3 геометрическая интерпретация области теряется и правило 3.1 для нахождения точек глобального экстремума становится неприемлемым. В теории оптимизации разработаны многочисленные методы и алгоритмы нахождения точек глобального экстремума функции переменных для различных частных случаев, которые выделяются наложением условий на функцию и на допустимую область, однако эффективных способов нахождения экстремумов функции для общего случая не существует.

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

Уравнение линии уровня записывается в виде (, ) =, где — произвольная постоянная (константа). Каждому значению константы соответствует своя линия уровня; варьируя константу, получаем в результате семейство линий уровня, при этом различные (то есть соответствующие различным значениям ) линии уровня не пересекаются.

Таким образом, через каждую точку плоскости 0 (0, 0 ), принадлежащую области определения функции, проходит, причем только одна, линия уровня функции ; ее уравнение (, ) = (0, 0 ).

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

1-й шаг: Изобразим область на координатной плоскости.

2-й шаг: Рассмотрим семейство линий уровня функции — оно покрывает всю область.

Так как для линии уровня, проходящей через точку 0 (0, 0 ), значение соответствующей ей константы есть = (0, 0 ), справедливо Правило 3.2.

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

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

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

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

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

Замечание 1. Разумеется, графический метод дает лишь приближенное решение задачи нахождения экстремума. Однако при = 2 во многих практических случаях графический метод может быть дополнен аналитическим следующим образом. Если граница области состоит из нескольких отдельных линий, тогда, используя графический способ, определим ту линию 0, на которой лежит точка глобального экстремума. Составим систему { где 0 (, ) = 0 — уравнение линии 0, и найдем — при поиске глобального максимума — наибольшее значение параметра = *, при котором система (3.2) совместна (при поиске глобального минимума — наименьшее значение = 0, при котором система (3.2) совместна). Решение системы (3.2) при = * дает координаты точки глобального максимума, а при = 0 — координаты точки глобального минимума функции. Этот способ будет использован в Задаче № 2.

Замечание 2. Для каждой точки 0 (0, 0 ) можно построить вектор grad — градиент функции, координатами которого являются частные производные и, вычисленные в точке (0, 0 ). Напомним геометрический смысл направления градиента: оно совпадает с направлением наибольшей скорости роста функции. При этом для каждой точки 0 градиент перпендикулярен линии уровня, проходящей через эту точку. Таким образом, сдвигаясь из точки 0 в направлении градиента, мы получаем для линии уровня увеличение значения соответствующей ей константы, а, сдвигаясь из точки 0 в направлении, противоположном направлению градиента — уменьшение значения константы. При этом надо иметь в виду, что в общем случае градиент функции не является постоянным вектором, поэтому, смещаясь, скажем, из точки 0 по направлению градиента в точку 1, далее надо строить градиент уже в точке 1 и т.д.

Замечание 3. В примере на рис. 3.1 глобальный максимум и глобальный минимум функции достигаются на границе допустимой области. Но так бывает не всегда (см. правило 3.1). Пример на рис.3.2 наглядно показывает, какой вид должно иметь семейство линий уровня функции (, ), чтобы ее глобальный максимум достигался во внутренней точке * области. В этом случае (согласно принципу стационарности) точка * должна быть стационарной точкой области.

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

Задача № 2: Максимизация производственной функции.

Предположим, что для производства некоторой продукции используется типов ресурсов. Затраты ресурсов могут быть формально представлены вектором = (1,..., ), где — количество ресурса типа ( = 1,..., ), по смыслу 0. Так как объем произведенной продукции определяется количеством затраченных ресурсов всех типов, возникает функция (1,..., ) — количество продукции, получаемой при векторе затрат ресурсов (1,..., ). Функция называется в этом случае производственной функцией. Основное свойство производственной функции — монотонность: при увеличении затрачиваемых ресурсов количество произведенной продукции увеличивается.

Пусть целью фирмы является максимизация количества производимой продукции. Причиной, по которой нельзя произвести "как угодно большое количество продукции"является ограниченность ресурсов (или ограниченность средств на покупку ресурсов). Рассмотрим здесь случай, когда фирма покупает ресурсы по фиксированным ценам. Пусть = (1,..., ) — вектор цен, где 0 — цена единицы ресурса -го типа. Предположим, что суммарные затраты на все ресурсы не должны превышать некоторой пороговой величины. Тогда вектор ресурсов = (1,..., ) будет допустимым, если общая стоимость ресурсов не превосходит, то есть В компактной записи неравенство (3.3) представляется в виде: (, ), где (·, ·) — скалярное произведение векторов. Неравенство (3.3) называется бюджетным ограничением.

Задача максимизации производственной функции состоит в следующем. Найти максимум производственной функции (1,..., ) в допустимой области = { R : (, ) ; 1,..., 0}, где > 0, = (1,..., ) — заданные величины.

Рассмотрим конкретный пример такой задачи, когда имеется всего два типа ресурсов, а производственная функция имеет вид: (, ) =, где и количество ресурса 1-го и 2-го типа, соответственно. Пусть цена одной единицы 1-го ресурса равна 2-м, а цена одной единицы 2-го ресурса — 3-м денежным единицам, причем общая стоимость ресурсов не должна превосходить 6-ти денежных единиц.

Здесь допустимая область = {(, ) R2 : 2 + 3 6;, 0} — она представляет собой треугольник, ограниченный осями декартовой системы координат и прямой : 2 + 3 = 6 (рис.3.3). Линии уровня целевой функции определяются уравнением: =. При каждом фиксированном > 0 линия уровня представляет собой гиперболу, лежащую в 1-й координатной четверти. Точка максимума функции (, ) есть та точка * (*, * ), для которой проходящая через нее гипербола касается прямой (см. рис.3.3). Приближенно значения координат точки * находятся по графику. Для нахождения точных значений координат точки Гипербола, проходящая через точку *, характеризуется тем, что при соответствующем ей значении константы = * система (3.4) имеет единственное решение — это обстоятельство мы и используем для нахождения *, *. Выражая из 1-го уравнения = (6 2)/3, подставляя его во 2-е уравнение и возводя обе части в квадрат, получаем в итоге квадратное уравнение относительно : 22 6+32 = 0. Это уравнение также должно иметь единственное решение, поэтому его дискриминант должен быть * = 6/4 = 3/2, * = 1.

Итак, максимальное значение функции в области достигается в точке * (3/2, 1). Оптимальное решение состоит в том, что надо использовать 3/2 единицы ресурса 1-го типа и одну единицу ресурса 2-го типа (при этом бюджетное ограничение выполнено: 2* + 3 * = 6). Вектор ресурсов (3/2, 1) дает максимально возможное — с учетом бюджетного ограничения — количество произведенной продукции.

3. Рассмотрим здесь вкратце один важный метод нахождения экстремума функции в допустимой области — метод множителей Лагранжа.

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

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

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

Справедливо следующее правило.

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

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

Рассмотрим более подробно случай = 2 и = 1 (число степеней свободы равно 1). Тогда целевая функция имеет вид (, ), а система ограничений (3.5) сводится к одному уравнению (, ) = 0.

В этом случае ищется экстремум функции двух переменных (, ) на линии, определенной уравнением (, ) = 0. Функция Лагранжа здесь принимает вид (,, ) = (, ) + (, ), а необходимые условия экстремума — условия стационарности функции Лагранжа — сводятся к системе:

нормальный вектор к линии, то первые два условия в (3.6) эквивалентны векторному равенству grad =, а последнее условие в (3.6) означает, что точка (, ) находится на линии. Таким образом, с геометрической точки зрения система условий (3.6) означает следующее:

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

Рисунок 3.4 поясняет эту ситуацию наглядно (здесь тонкие линии являются линиями уровня целевой функции (, ), а жирная линия — линия ). Легко понять, почему в точках экстремума * (*, * ) и 0 (0, 0 ) линия не должна пересекать проходящие через эти точки линии уровня целевой функции: например, если бы в точке * линия пересекала проходящую через * линию уровня функци (, ), то можно было бы сместиться по линии в некоторую точку (, ) в направлении, составляющем острый угол с вектором grad ; в этом случае выполнялось бы ( ) > ( * ) в противоречие с тем, что * — точка условного максимума. Таким образом, в точке условного экстремума линия и линия уровня целевой функции должны иметь общую касательную, поэтому нормали к ним будут коллинеарны.

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

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

функции и при более общей системе ограничений, чем система (3.5). Например, когда система ограничений имеет вид системы неравенств и все 0, = 1,...,. Такая оптимизационная задача называется задачей нелинейного программирования. Функция Лагранжа в этом случае определяется как сумма целевой функции и скалярного произведения вектора множителей Лагранжа и вектора разностей правых и левых частей системы (3.7). Более подробно см., например, в [1].

Проиллюстрируем метод множителей Лагранжа на следующем примере.

Задача № 3: Распределение заказа между двумя фирмами.

Предпринимателю требуется приобрести единиц некоторого продукта, распределив заказ между двумя фирмами и. Стоимость производства единиц продукта фирмой составляет () = 0 + 1 + ден.ед., а фирмой — () = 0 +1 +2 2 ден.ед. (0, 1, 2, 0, 1, 2 > 0). При каком распределении заказа между этими двумя фирмами общая стоимость заказа будет наименьшей?

Решение. Пусть заказ распределен между фирмами так, что фирма производит 1 единиц продукта, а фирма — 2 единиц продукта (при этом должно выполняться 1 + 2 =, 1 > 0, 2 > 0). Тогда целевая функция — стоимость заказа — есть а система ограничений сводится к уравнению 1 + 2 =.

Составим функцию Лагранжа: (1, 2, ) = (1, 2 ) + ( 1 2 ).

Находя частные производные функции и приравнивая их к нулю, получаем систему уравнений Система (3.8) есть система трех линейных уравнений с 3-мя неизвестными 1, 2,, которую можно решить любым известным способом. Например, вычтем из 1-го уравнения 2-е: (1 1 ) + 22 1 22 2 = 0;

подставляя сюда из 3-го уравнения 2 = 1, находим Окончательно получаем решение в виде:

Заметим, что всегда 0 + 0 = ; для выполнения граничных условий 0, 0 > 0 необходимо и достаточно, чтобы 0 < 0 <, то есть Итак, задача имеет решение только в том случае, когда Анализ результатов. Приведем некоторые содержательные пояснения полученного решения. Формулы (3.9) наглядно показывают способ оптимального распределения заказа: вначале общая величина заказа делится на две части обратно пропорционально старшим коэффициентам многочленов () и (); затем к полученным величинам прибавляются "добавки"1 и 2, пропорциональные разностям коэффициентов при первых степенях многочленов, причем 2 = 1. Рассмотрим теперь частный случай, когда 1 = 1. Интуитивно ясно, что в этом случае надо делить заказ обратно пропорционально коэффициентам при старших членах, что и диктует формула (3.9) (в этом случае "добавки"равны нулю).

Тест для самоконтроля к лекции 1. Точка области называется ее внутренней точкой, если она....

Варианты ответов: а) ей принадлежит 2. Функция (, ) в направлении, состовляющем с градиентом острый угол,....

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

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

Варианты ответов: а) возрастает 5. Множество точек плоскости, удовлетворяющих уравнению (, ) =, где - константа, называется...

Варианты ответов: а) областью определения функции (, ) 6. Множество точек пространства, удовлетворяющих уравнению (,, ) =, где - константа, называется...

Варианты ответов: а) областью определения функции (,, ) 7. Пусть 0, где - область определения функции (, ). Тогда через точку 0....

Варианты ответов: а) не проходит ни одной линии уровня 8. Градиент указывает направление....

Варианты ответов: а) постоянства функции 9. Продукт производится из продуктов и, причем его количество находится по формуле: = 2 + 3, где - количество продукта, - количество продукта. Какое максимальное количество продукта может быть получено при условии 42 + 9 2 72 ?

Варианты ответов: а) 10. Производственная функция имеет вид: (, ) =, где - количество ресурса 1-ого типа - количество ресурса 2-ого типа. Найти максимальное значение производственной функции, если стоимость одной единицы ресурса 1-ого типа равна 3 ден. ед., стоимость одной единицы ресурса 2-ого типа равна 2 ден. ед., а всего на покупку ресурсов выделено 12 ден. ед.

Варианты ответов: а) 11. Производственная функция имеет вид: (, ) = 5 3 3, где - количество ресурса 1-ого типа - количество ресурса 2-ого типа. Найти максимальное значение производственной функции, если стоимость одной единицы ресурса 1-ого типа равна 5 ден. ед., стоимость одной единицы ресурса 2-ого типа равна 2 ден. ед., а всего на покупку ресурсов выделено 20 ден. ед.

Указание: воспользуйтесь методом множителей Лагранжа.

Варианты ответов: а) б) в) г) д) Лекция Задачи линейного программирования Основные вопросы: 1. Общая задача линейного программирования. Задача № 4: Задача производственного планирования. Задача № 5: Задача о смеси. Задача № 6: Задача о перевозках (транспортная задача). 2. Основной принцип линейного программирования. Понятие о симплекс–методе. Особенности существования решений в задачах линейного программирования. 3. Двойственность в линейном программировании. Экономический смысл двойственности.

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

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

Общая задача линейного программирования (ОЗЛП) может быть задана в следующем виде: Найти max (1,..., ) при ограничениях где, 1,..., — линейные функции переменных; при этом, как правило, накладываются граничные условия неотрицательности переменных: 0 для всех = 1,...,.

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

ОЗЛП на плоскости (то есть относительно двух переменных) имеет вид: Найти максимум функции (, ) = + + при системе Так как каждое неравенство + ( = 1, ) определяет полуплоскость, ограниченную прямой + =, то допустимая область, выделяемая системой ограничений (4.2), представляет собой в этом случае пересечение конечного числа полуплоскостей, называемое выпуклым многоугольным (или многогранным) множеством. Если выпуклое многоугольное множество ограничено, оно будет выпуклым многоугольником.

ОЗЛП в пространстве (то есть относительно трех переменных) принимает вид: Найти максимум линейной функции (,, ) = + + + при системе ограничений Здесь каждое неравенство + + ( = 1, ) определяет полупространство, ограниченное плоскостью + + = ; пересечение конечного числа полупространств называется выпуклым многогранным множеством (ВММ); если ВММ ограничено, оно представляет собой выпуклый многогранник.

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

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

Задача № 4: Задача производственного планирования.

Содержательная постановка задачи такова. Предприятие может производить продукцию различных типов 1,...,, имея запас ресурсов типов 1,...,. Пусть — количество ресурса типа, которое требуется для производства единицы продукции типа ; — наличный запас ресурса типа, а — прибыль от реализации единицы продукции типа ( = 1,, = 1, ). Все эти данные можно свести в таблицу (см. таблицу 4.1).

Производственный план (короче — план) формально можно задать вектором = (1,..., ), где неотрицательное число 0 указывает количество продукции –го типа, ( = 1,..., ), производимое при этом плане (некоторые могут быть равны нулю — это означает, что соответствующий тип продукции при этом плане не производится). Перейдем к определению оптимального плана.

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

b) План называется оптимальным, если, во–первых, он является допустимым, и, во–вторых, дает максимальную прибыль среди всех допустимых планов.

Выразим теперь условия допустимости и оптимальности плана. Так как при плане = (1,..., ) расход ресурса –го типа равен 1 1 +· · ·+, а запас ресурса –го типа равен, то для того, чтобы план был реализован "по ресурсу надо, чтобы выполнялось неравенство 1 1 + · · · + ; реализуемость плана "в целом"означает его реализуемость по каждому виду ресурсов и сводится, таким образом, к системе линейных неравенств:

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

Далее, прибыль от реализации плана = (1,..., ) равна 1 1 +· · ·+. Таким образом, задача нахождения оптимального плана сводится к следующей оптимизационной задаче:

в допустимой области, выделяемой системой линейных неравенств (4.4) при граничных условиях 0 ( = 1,..., ). Это — частный случай ОЗЛП.

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

ной таблицей 4.2. Здесь система ограничений сводится к системе линейных неравенств при граничных условиях неотрицательности 0, 0. Допустимая область представляет собой многоугольник (см. рис. 4.1), ограниченный прямыми: (1 ) : + 2 = 15; (2 ) : 16 + 6 = 96; (3 ) :

9 + 7 = 69; (4 ) : = 0; (5 ) : = 0. Целевая функция имеет вид: (, ) = 5 + 7, а семейство линий уровня — семейство прямых 5 + 7 =, где — константа. Градиентом целевой функции здесь является постоянный вектор = grad с координатами (5, 7), который перпендикулярен всем линиям уровня. Задача нахождения глобального максимума функции (, ) в допустимой области в данном случае может быть решена графическим способом (см. лекцию 3, п. 2). Точка глобального максимума функции (, ) в области есть та вершина *, через которую проходит линия уровня при наибольшем возможном значении константы (геометрически точка * получается перемещением прямой 5 + 7 = в направлении градиента до тех пор, пока она еще пересекает область ). Приближенно значения координат (*, * ) точки * могут быть найдены по графику. Для нахождения точных значений (*, * ) составим систему из уравнений прямых (1 ) и (3 ), пересечением которых является точка * :

Решая систему, находим * = 3, * = 6.

Задача № 5: Задача о смеси.

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

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

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

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

Условия допустимости смеси = (1,..., ) сводятся к системе линейных неравенств Так как стоимость смеси равна 1 1 + · · · +, то задача нахождения оптимальной смеси сводится к следующей оптимизационной задаче:

, заданной системой линейных неравенств (4.6) при условии неотрицательности переменных.

С учетом Замечания 4.1 cформулированная задача является частным видом ОЗЛП.

Задача № 6: Задача о перевозках (транспортная задача).

Имеется пунктов производства (или хранения) некоторого продукта и пунктов потребления этого продукта. Количество данного продукта в пункте равно, а потребность в нем в пункте равна ( = 1,, = 1, ). Стоимость перевозки единицы продукта из пункта в пункт равна. Как оптимальным образом спланировать перевозки?

Решение этой задачи состоит в следующем. Составить план перевозок — значит для каждого пункта производства и для каждого пункта потребления указать то количество продукта, которое должно перевозиться из в при этом плане. Таким образом, математически план перевозок может быть задан в виде неотрицательной матрицы = ( = 1, ; = 1, ). Каковы условия допустимости (то есть реализуемости) такого плана? Общее количество продукта, вывозимое из пункта, есть пункт, равно План будет допустимым, если, во–первых, для каждого пункта производства вывезенное количество продукта не превышает его наличного количества, и, во–вторых, должны быть удовлетворены потребности в данном продукте всех пунктов потребления. Итак, условия допустимости плана = принимают следующий вид:

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

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

Итак, задача нахождения оптимального плана перевозок сводится к нахождению минимума функции (4.9) при ограничениях (4.7), (4.8) и граничных условиях неотрицатетельности переменных. Данная задача — с учетом Замечания 4.1. — является частным случаем ОЗЛП.

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

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

Доказательство. Для простоты записи рассмотрим случай функции 3–х переменных (,, ) = + + +. Градиент функции является здесь постоянным вектором с координатами (,, ), причем ввиду того, что функция отлична от постоянной, ее градиент не равен нулю. На основании принципа стационарности и Замечания к нему (см.

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

Рассмотрим теперь линейную функцию, заданную на выпуклом многограннике R. Так как выпуклый многогранник представляет собой замкнутое и ограниченное множество, то согласно теореме Вейерштрасса (см. лекцию 3, п. 1) функция достигает на нем глобального максимума; учитывая Правило 4.1, приходим к следующему утверждению.

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

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

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

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

Граница выпуклого многогранника представляет собой объединение выпуклых многоугольников. Предположим, что функция достигает, например, глобального максимума в некоторой внутренней точке 0 многоугольника, представляющего собой часть границы выпуклого многогранника (рис. 4.2). Тогда градиент функции в точке 0 должен быть перпендикулярен плоскости многоугольника. В самом деле, если бы это было не так, то можно было бы сдвинуться из точки 0 в некоторую точку 1 по направлению вектора, составляющему острый угол с вектором = grad |0. Так как разность (1 ) (0 ) представима в виде скалярного произведения на вектор смещения 0 1, то учитывая, что · 0 1 > 0, получаем (1 ) > (0 ) в противоречие с тем, что 0 — точка глобального максимума функции в области. Из условия перпендикулярности градиента плоскости многоугольника сразу следует, что функция является постоянной на, значит она достигает глобального максимума в любой вершине многоугольника Правило 4.2 Основной принцип линейного программирования.

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

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

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

(1) Допустимая область есть пустое множество (см. рис. 4.3).

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

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

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

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

4.6), а также иметь экстремум одного вида и не иметь другого (рис. 4.7).

3. Остановимся вкратце на одном из важнейших понятий линейного программирования — понятии двойственности. Общая задача линейного программирования (ОЗЛП) полностью определяется матрицей ( ) формата, к которой добавлены вектор–строка = (1,..., ) и вектор–столбец = (1,..., ), см. таблицу 4.5.

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

при граничных условиях 0 ( = 1,..., ), а целевая функция есть (1,..., ) = 1 1 + · · · + = (, ). Напомним, что ОЗЛП состоит в максимизации целевой функции (, ) при системе ограничений (4.10).

Назовем эту задачу прямой задачей ЛП.

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

при граничных условиях 0 ( = 1,..., ), а целевая функция есть ( 1,..., ) = 1 1 +· · ·+ = (, ). Если прямая задача ЛП состоит в нахождении максимума целевой функции, то двойственная задача ЛП состоит в нахождении минимума целевой функции (, ) при системе ограничений (4.11).

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

В заключении этой темы укажем экономический смысл двойственности на примере задачи о смеси (см. п.1).

Рассмотрим задачу о смеси, заданную таблицей типа таблицы 4.6.

Здесь {1,..., } — первичные продукты, из которых составляется смесь, а в качестве питательных веществ берутся белки (), жиры () и углеводы (). Прямая задача ЛП в данном случае имеет вид:

Найти минимум функции (1,..., ) = 1 1 + · · · + при системе ограничений и граничных условиях 1 0,..., 0.

Построим двойственную задачу ЛП. Система ограничений двойственной задачи принимает вид:

с граничными условиями 1 0, 2 0, 3 0. Целевая функция двойственной задачи есть ( 1, 2, 3 ) = 1 1 + 2 2 + 3 3. Двойственная задача формулируется следующим образом: Найти максимум функции ( 1, 2, 3 ) при системе ограничений(4.13). В чем состоит в данном случае экономический смысл двойственной задачи?

Предположим, что некая фирма продает первичные продукты {1,..., } по цене за единицу продукта ( = 1, ). Возникает конкурирующая фирма B, которая предлагает покупателям не сами первичные продукты 1,...,, а белки, жиры и углеводы, так сказать, "в чистом виде"(например, в виде таблеток, или "на вес"). Пусть 1, 2, — цена "единицы белков "единицы жиров"и "единицы углеводов соответственно. Так как единица продукта может быть заменена набором, состоящим из 1 единиц белков, 2 единиц жиров и 3 единиц углеводов (будем записывать такой набор в виде 1 2 3 ), то покупатель сможет предпочесть такой набор единице продукта только в том случае, когда стоимость этого набора будет не больше стоимости единицы продукта, то есть когда 1 1 + 2 2 + 3 3, но это и есть как раз неравенство, входящее в систему ограничений двойственной задачи. Далее, если покупатель приобретает белки, жиры и углеводы "в чистом виде то для получения требуемой смеси он должен приобрести набор, состоящий из 1 единиц белков, 2 единиц жиров и 3 единиц углеводов, то есть набор 1 2 3. Стоимость такого набора равна 1 1 + 2 2 + 3 3, что совпадает с целевой функцией двойственной задачи.

Итак, в данном случае смысл двойственных переменных 1, 2, 3 — это цены, назначаемые за единицу белков, жиров и углеводов, соответственно.

Экономический смысл оптимального вектора цен = ( 1, 2, 3 ) состоит в следующем.

а) Допустимость вектора цен = ( 1, 2, 3 ) означает, что "цены должны быть не слишком высокими"; точнее, такими, чтобы покупателю было выгодно вместо покупки единицы каждого продукта купить по этим ценам эквивалентный ему набор 1 2 3 ( = 1,..., ).

в) Оптимальность вектора цен состоит в том, что "цены должны быть не слишком низкими"; точнее: среди всех допустимых векторов цен оптимальный вектор цен характеризуется тем, что при покупке набора 1 2 3 по оптимальным ценам он приносит фирме наибольший доход.

Тест для самоконтроля к лекции 1. Задача линейного программирования состоит в нахождении....

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

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

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

Варианты ответов: а) является реализуемым по всем ресурсам 5. В задаче о смеси смесь называется оптимальной, если она....

Варианты ответов: а) имеет количество всех питательных веществ не ниже норм 6. В транспортной задаче план называется оптимальным, если....

Варианты ответов: а) удовлетворены потребности всех магазинов 7. Для того, чтобы транспортная задача имела решение, необходимо и достаточно, чтобы....

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

Варианты ответов: а) в единственной граничной точке области 9. Может ли линейная функция, заданная на выпуклом множестве, достигать экстремума ровно в двух точках?

Варианты ответов: а) да, всегда 10. Используя графический метод, найдите оптимальный план для производственной задачи, заданной таблицей:

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

Продукты Варианты ответа: * * 12. Используя графический метод, составьте оптимальный план перевозок для транспортной задачи, заданной таблицей:

Склады Лекция Принятие решений при многих критериях (многокритериальная оптимизация) Основные вопросы: 1. Оценка исходов по нескольким критериям.

Математическая модель многокритериальной ЗПР в условиях определенности. 2. Отношение доминирования по Парето. Парето-оптимальность.

3. Простейшие способы сужения Парето-оптимального множества и нахождения оптимального решения: a) указание нижних границ критериев;

в) выделение одного критерия (субоптимизация); с) упорядочение критериев по важности (лексикографическая оптимизация). Задача № 7:

Выбор места работы. 4. Обощенный критерий в многокритериальных ЗПР. Построение обобщенного критерияв виде взвешенной суммы частных критериев. Задача № 8: Оптимизация производственного процесса.

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

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

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

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

2. Критерий называется позитивным, если принимающий решение стремится к его увеличению, и негативным — если к его уменьшению. В конкретных задачах принятия решений характер критерия устанавливается по содержательным соображениям. Технически "превращение"негативного критерия в позитивный (и наоборот) можно осуществить при помощи смены знака; при рассмотрении многокритериальных ЗПР в общем виде будем, если не оговорено противное, предполагать, что все имеющиеся критерии являются позитивными. В многокритериальной ЗПР с позитивными критериями целью принимающего является получение исхода, имеющего как можно более высокие оценки по каждому критерию.

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

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

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

Определение. Пусть — некотрое множество векторных оценок. Векторная оценка * называется Парето–оптимальной в, если она является максимальным элементом множества относительно Парето–доминирования (то есть если в множестве не существует такой векторной оценки, которая доминирует по Парето векторную оценку Перенесем теперь эти понятия на исходы.

Определение. Говорят, что исход 1 доминирует по Парето исход 2 (записывается в виде 1 > 2 ), если векторная оценка исхода 1 доминирует по Парето векторную оценку исхода 2.

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

Введем теперь основное понятие.

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

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

Векторные оценки исходов представим точками координатной плоскости (по оси абсцисс откладываем значения критерия 1, а по оси ординат — значения критерия 2 ). В случае, когда множество допустимых исходов является дискретным (конечным), получаем "картинку"типа той, которая представлена на рис. 5.1. Здесь Парето-оптимальными являются исходы {4, 5, 7, 8}. При этом каждый исход, не являющийся Парето–оптимальным, доминируется по Парето некоторым Парето-оптимальным исPar Par Par Par ходом (не обязательно одним). Например: 6 < 5, 6 < 7, 10 < 7, 10 < и т.д.

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