«ПРАКТИКУМ ПО ИССЛЕДОВАНИЮ ОПЕРАЦИЙ В ЭКОНОМИКЕ Учебное пособие Под редакцией доктора экономических наук, профессора В. А. Колемаева и кандидата экономических наук, доцента В. И. Соловьева Рекомендовано кафедрой ...»

БИБЛИОТЕКА СТУДЕНТА — ЭКОНОМИСТА

Главный редактор серии

доктор экономических наук, профессор В. А. Колемаев

ПРАКТИКУМ

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

В ЭКОНОМИКЕ

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

Под редакцией

доктора экономических наук, профессора В. А. Колемаева

и кандидата экономических наук, доцента В. И. Соловьева Рекомендовано кафедрой прикладной математики ГОУ ВПО «Государственный университет управления»

в качестве учебного пособия для студентов вузов, обучающихся по специальностям 080000 «Специальности экономики и управления»

Рекомендовано кафедрой математики и естествознания НОУ «Институт гуманитарного образования» (ИГУМО) в качестве учебного пособия для студентов вузов, обучающихся по специальностям 080000 «Специальности экономики и управления»

Москва УДК 519 (075.8) ББК 22.1я К А в т о р ы:

доктор экономических наук, профессор В. А. Колемаев, кандидат экономических наук, доцент В. И. Соловьев, доцент И. С. Карандаев, доктор физико математических наук, профессор В. И. Малыхин, доктор экономических наук, профессор Т. М. Гатауллин Р е ц е н з е н т ы:

заведующий кафедрой математики и информационных технологий Московской академии предпринимательства при Правительстве г. Москвы, доктор физико математических наук, профессор В. И. Быков, заведующий кафедрой высшей математики Московского энергетического института (технического университета), доктор физико математических наук, профессор И. М. Петрушко, профессор кафедры прикладной математики Государственного университета управления, доктор физико математических наук В. В. Шмелев Колемаев В. А.

К60 Практикум по исследованию операций в экономике: Учебное по собие для вузов / В. А. Колемаев, В. И. Соловьев, И. С. Карандаев и др.; Под ред. В. А. Колемаева и В. И. Соловьева. – М., 2007. – 192 с.

– (Библиотека студента — экономиста).

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

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

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

© Коллектив авторов, ISBN

ПРЕДИСЛОВИЕ

Учебное пособие «Практикум по исследованию операций в экономике» пред назначено для студентов экономических специальностей вузов, изучающих раздел «Математические методы принятия решений в экономике» дисциплины «Математика», а также дисциплины «Математические методы и модели иссле дования операций», «Методы оптимизации», «Системный анализ и принятие решений», «Экономико математические методы», «Финансовая математика»

и т. п.

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

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

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

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

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

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

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

В зависимости от специфики вуза и специальности преподаватель может ис пользовать практикум полностью или частично. Так, студентам специальности 080801 «Математические методы в экономике» целесообразно выполнить прак тикум полностью в рамках курсового проекта по дисциплине «Математические методы и модели исследования операций», а студентам специальности «Статистика» — в рамках курсового проекта по дисциплине «Методы оптими зации». Самостоятельная работа студентов специальностей 080102 «Мировая экономика», 080103 «Национальная экономика», 080111 «Маркетинг», «Менеджмент организации» и других прикладных экономических и управлен ческих специальностей может быть организована в форме выполнения части заданий практикума, составляющих курсовой проект, семестровое домашнее задание, типовой расчет, лабораторную или расчетно графическую работу по разделу «Математические методы принятия решений в экономике» дисципли ны «Математика». На ряде специальностей, таких как 080105 «Финансы и кре дит», 080109 «Бухгалтерский учет, анализ и аудит», 080503 «Антикризисное управление», 080506 «Логистика и управление цепями поставок», «Управление инновациями» и др., Государственным образовательным стандар том высшего профессионального образования в дополнение к учебной дисцип лине «Математика» предусмотрены также такие дисциплины, как «Экономико математические методы», «Системный анализ и принятие решений», «Финан совая математика» и т. п. — часть заданий практикума может быть использова на и в преподавании экономико математических и финансово математических дисциплин.

Работа авторов над пособием разделилась следующим образом: предисловие написано В. А. Колемаевым и В. И. Соловьевым, ими же осуществлена общая редакция пособия; разделы 1, 2, 4, 8 и 10 написаны совместно И. С. Карандаевым и В. И. Соловьевым; раздел 3 написан совместно Т. М. Гатауллиным и В. И. Соловьевым; разделы 5, 19 и 20 написаны В. И. Соловьевым; разделы 6 и написаны И. С. Карандаевым; разделы 9, 11—13 и 16 написаны совместно В. И. Малыхиным и В. И. Соловьевым; разделы 14, 15, 17 и 18 написаны совмест но В. А. Колемаевым, В. И. Малыхиным и В. И. Соловьевым.

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

Авторы также благодарны преподавателям кафедры прикладной математи ки ГУУ, которые участвовали в подготовке исходных числовых данных для за даний практикума: кандидату физико математических наук, доценту Ю. Г. Прохорову и старшему преподавателю Х. Х. Юнисову.

1. ЛИНЕЙНАЯ ПРОИЗВОДСТВЕННАЯ ЗАДАЧА

и указания к выполнению заданий Задача планирования производства состоит в отыскании такого плана производства который позволяет получить максимальную прибыль при ограничениях по заданным ресурсам где по смыслу задачи Исходные данные задачи представляются в виде матрицы A удельных за трат ресурсов, вектора b объемов ресурсов и вектора c удельной прибыли:

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

В рамках модели линейного программирования предприятия должна пользуемых им в процессе производства. Эти оценки связаны с техноло гическими особенностями данного производственного процесса, характе ризуемыми технологической матрицей A, со структурой и количеством ресурсов, отпущенных для производственного потребления, описывае мых вектором b, а также со структурой внешних цен, на основе которых получается вектор прибылей c. Условимся называть эти оценки расчет ными оценками ресурсов. Подчеркнем, что расчетную оценку единицы ресурса не следует отождествлять с той ценой, по которой предприятие приобретало этот ресурс. Последняя отражает общественно необходимые затраты на производство единицы ресурса и определяется рынком, а расчетная оценка показывает только с р а в н и т е л ь н у ю ц е н н о с т ь этого ресурса на данном предприятии в данных Как определить расчетные оценки ресурсов? Обозначим через yi оцен ку единицы i го вида ресурса, т. е.

вектор оценок ресурсов.

Суммарная оценка всех ресурсов представляется в виде b1y1 + + bm ym.

Эта сумма должна быть минимальной при условии, что на производство единицы продукции j го вида мы должны затратить различные виды ре сурсов в количествах a1j, a2 j,..., amj, и их суммарная оценка, равная a1j y1 + a2 j y2 + + amj ym, должна быть не меньше той прибыли, которую мы получим от реализации единицы готовой продукции.

Таким образом, мы пришли к новой задаче линейного программирова ния: найти вектор оценок ресурсов минимизирующий суммарную оценку всех ресурсов при условиях где по смыслу задачи Полученная задача линейного программирования (1.1.4)—(1.1.6) назы вается двойственной задачей к задаче (1.1.1)—(1.1.3). Расчетные оценки ресурсов, соответствующие оптимальному плану производства, служат компонентами оптимального решения двойственной задачи. Поэтому ка ждую из компонент yi оптимального решения двойственной задачи назы вают двойственной оценкой i го ресурса.

Приведем краткую сводку основных результатов теории двойственности.

ПЕРВАЯ ОСНОВНАЯ ТЕОРЕМА ДВОЙСТВЕННОСТИ. Если одна из задач двойствен ной пары имеет оптимальное решение, то и другая имеет оптималь ное решение, причем экстремальные значения линейных форм равны;

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

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

ВТОРАЯ ОСНОВНАЯ ТЕОРЕМА ДВОЙСТВЕННОСТИ (ТЕОРЕМА О ДОПОЛНЯЮЩЕЙ НЕЖЕ

СТКОСТИ). Для того, чтобы допустимые решения пары двойственных задач являлись оптимальными решениями этих задач, необходимо и достаточно выполнение условий т. е. если какое либо неравенство системы ограничений одной из задач не обращается в точное равенство оптимальным решением этой задачи, то соответствующая компонента оптимального решения двойственной зада чи должна равняться нулю; если же какая либо компонента оптимально го решения одной из задач положительна, то соответствующее ограниче ние в двойственной задаче ее оптимальным решением должно обращать ся в точное равенство. Другими словами, если yi > 0 для некоторого i, то если x > 0 для некоторого j, то Рассмотрим экономическое содержание второй теоремы двойственно сти. Для этого обратимся последовательно к утверждениям (1.1.7')— (1.1.7'') и (1.1.8')—(1.1.8''). Утверждения (1.1.7') и (1.1.7'') можно истолковать следующим образом.

Если по оптимальному плану производства ( x ) расход i го ресурса то оценка yi единицы этого ресурса равна нулю:

если же оценка i го ресурса строго больше нуля:

то расход этого ресурса равен его запасу:

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

Условия (1.1.8') и (1.1.8'') можно истолковать так. Если оценка ij сурсов, расходуемых по j й технологии в единицу времени, строго больше цены продукта, производимого по той же технологии за то же время то j я технология не применяется:

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

то оценка ресурсов, расходуемых по этой технологии в единицу времени, равна цене произведенного за единицу времени по той же технологии продукта:

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

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

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

где переменные y1, y2, …, ym могут принимать значения любого знака.

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

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

ТРЕТЬЯ ОСНОВНАЯ ТЕОРЕМА ДВОЙСТВЕННОСТИ (ТЕОРЕМА ОБ ОЦЕНКАХ ВЛИЯНИЯ РЕ

СУРСОВ НА ВЫПУСК ПРОДУКЦИИ). Значения переменных yi в оптимальном решении двойственной задачи представляют собой оценки влияния правых частей bi системы ограничений исходной задачи на величину максимума ее целевой функции т. е. увеличение правой части i го ограничения приводит к увеличению или уменьшению zmax в зависимости от того, будет ли yi положительным или отрицательным, и при этом скорость изменения zmax определяется величиной |yi|.

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

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

ПРИМЕР 1.1.1. Предприятие может выпускать четыре вида продукции, ис пользуя для этого три вида ресурсов. Известна технологическая матрица A затрат каждого из ресурсов на единицу каждой продукции, вектор b объе мов ресурсов и вектор c удельной прибыли на единицу каждой продукции:

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

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

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

Подчеркнем, что за каждой симплексной таблицей надо видеть вспомо гательную систему четырех линейных уравнений, из которых первые три представляют некоторый предпочитаемый эквивалент системы условий задачи и определяют соответствующее базисное допустимое решение, а из последнего уравнения получается выражение функции цели через свободные неизвестные. Как видно из последней симплексной таблицы, оптимальной является производственная программа x1 = 27; x2 = 0; x3 = 0;

x4 = 20, обеспечивающая предприятию наибольшую прибыль zmax = 1972;

при этом остаток ресурса первого вида x5 = 0, второго вида x6 = 13, третьего вида x7 = 0.

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

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

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

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

Для производства единицы продукции первого вида мы должны затра тить, как видно из матрицы A, 4 единицы ресурса первого вида, 2 едини цы ресурса второго вида и 3 единицы третьего (элементы первого столбца матрицы). В ценах y1, y2, y3 наши затраты составят 4y1 + 2y2 + 3y3. При реализации единицы первой продукции на рынке мы получили бы при быль 36 руб. Следовательно, внутренняя оценка стоимости ресурсов, из которых можно изготовить единицу первого продукта ( 4y1 + 2y2 + 3y3 ), должна составлять не менее 36 руб. Аналогичные условия должны выпол няться и для всех остальных видов продукции.

208y1 + 107y2 + 181y3 должна быть минимальной.

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

причем оценки ресурсов не могут быть отрицательными:

для этой задачи:

и подставим в эти уравнения уже известную оптимальную производст венную программу x1 = 27; x2 = 0; x3 = 0; x4 = 20:

или Второе из этих уравнений [y2(94 – 107) = 0] означает, что поскольку второй ресурс используется не полностью (при выполнении оптимальной производственной программы расходуется 94 единицы из 107), его двой ственная оценка y2 = 0. Четвертое уравнение [27(4y1 + 2y2 + 3y3 – 36) = 0] означает, что поскольку первый продукт входит в оптимальную произ водственную программу (x1 = 27), то суммарная двойственная оценка ре сурсов, из которых можно изготовить единицу продукта первого вида (4y1 + 2y2 + 3y3) должна быть равна цене этого продукта (36 руб.). Из по следнего уравнения следует, что поскольку четвертый продукт входит в оптимальную производственную программу (x4 = 20), то суммарная двой ственная оценка ресурсов, из которых можно изготовить единицу про дукта четвертого вида (5y1 + 2y2 + 5y3) должна быть равна цене этого про дукта (50 руб.). Итак, Решив эту систему уравнений, получим окончательно, что y2 = 6, y2 = 0, y2 = 4.

Теперь получим решение этой же задачи в пакете Microsoft Excel. Вве дем исходные данные в рабочий лист Microsoft Excel, как показано на рис. 1.1.1, а: в ячейки A5:D7 введем элементы технологической матрицы A, в ячейки A2:D2 — элементы вектора удельной прибыли c, в в ячейки H5:H7 — запасы ресурсов (элементы вектора b). Ячейки A10:D10 отведем под компоненты плана производства x, а в ячейках F2 и F5:F7 рассчитаем значения целевой функции z = cj xj и расходов ресурсов aij xj соот ветственно (формулы Microsoft Excel приведены на рис. 1.1.1, а, а резуль тат их ввода в рабочий лист — на рис. 1.1.1, б).

A B C D E F G H

A B C D E F G H

Рис. 1.1.1. Исходные данные для решения задачи линейного программирования Запустим надстройку «Поиск решения» пакета Microsoft Excel (меню «Сервис | Поиск решения»; если такой пункт в меню Microsoft Excel отсут ствует, то это означает, что надстройка «Поиск решения» не установлена.

Чтобы ее установить, необходимо отметить флажок «Поиск решения» в списке надстроек пакета Microsoft Excel, который вызывается с помощью выбора пункта меню «Сервис | Надстройки».).

В появившемся диалоговом окне (рис. 1.1.2, а) укажем, что целевая функция рассчитывается в ячейке $F$2, переменные задачи находятся в ячейках $A$10:$D$10. С помощью кнопки «Добавить» добавим ограниче ния, состоящие в том, что расходы ресурсов не могут быть больше их за пасов ($F$5 0) = 5 = 31.

Для найденной свободной клетки (3, 1) построим цикл пересчета:

Производим перераспределение поставок вдоль цикла пересчета Получаем второе базисное допустимое решение (табл. 4.1.3).

Производство Находим новые потенциалы, новые оценки. Наибольшую положитель ную оценку будет иметь свободная клетка (1, 4). Для нее строим цикл пе ресчета производим перераспределение ( max = 20 ):

и получаем третье базисное допустимое решение. Продолжаем процесс дальше (табл. 4.1.4—4.1.6).

Производство Производство Производство 35 = 2. Поскольку все оценки неположительны, базисное допустимое решение является оптимальным.

Однородный продукт, сосредоточенный на трех складах фирмы в ко личествах a1, a2, a3 единиц, необходимо распределить между четырьмя магазинами, которым необходимо соответственно b1, b2, b3, b4 единиц про дукта. Стоимость перевозки единицы продукта из i го пункта отправле ния (i = 1, 2, 3) в j й пункт назначения (j = 1, 2, 3, 4) равна cij и известна для всех маршрутов.

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

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

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

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

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

5. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

и указания к выполнению заданий Функция f (x) называется выпуклой в в е р х на множестве X, если для любых x1, x2 X и любых [0;1] выполняется неравенство Функция f(x) называется выпуклой в н и з на множестве X, если для любых x1, x 2 X и любых [0;1] выполняется неравенство Задача выпуклого программирования формулируется так. Требуется найти вектор x R n, доставляющий в ы п у к л о й в в е р х дифферен цируемой функции максимум на множестве допустимых решений, заданных ограничениями к которых все i (x) — в ы п у к л ы е в н и з дифференцируемые функ ции (i = 1, 2, …, m).

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

Функцией Лагранжа задачи выпуклого программирования (5.1.1)— (5.1.2) называется функция при этом координаты y1, y1, …, ym вектора называется множителями Лагранжа для задачи выпуклого программи рования (5.1.1)—(5.1.2).

Если в задаче (5.1.1)—(5.1.2) f (x) выпукла вверх, а все i (x) выпуклы вниз (i = 1, 2, …, m), то, очевидно, функция Лагранжа (5.1.3) выпукла вверх по x, а по y она является и выпуклой вверх, и выпуклой вниз. Действи тельно, пусть x1, x2 R n, [0;1]. Тогда Говорят, что задача выпуклого программирования (5.1.1)—(5.1.2) удов летворяет условию регулярности, если существует хотя бы одна внут ренняя точка множества допустимых решений, определяемого неравен ствами (5.1.2) [т. е. такая точка x R n, что i (x) < bi (i = 1, 2, …, m)].

функции L(x, y), если для всех x R n, y R + ТЕОРЕМА КУНА — ТАККЕРА. Если задача выпуклого программирования (5.1.1)—(5.1.2) удовлетворяет условию регулярности, то точка x R n является оптимальным решением этой задачи тогда и только тогда, когда существует такой вектор с неотрицательными координатами, что точка (x, y ) R n + m являет ся седловой точкой функции Лагранжа данной задачи.

УСЛОВИЯ КУНА — ТАККЕРА В ДИФФЕРЕНЦИАЛЬНОЙ ФОРМЕ. Если функция Ла гранжа L(x, y) является выпуклой вверх по x, выпуклой вниз по y и не прерывно дифференцируемой по всем xj (j = 1, 2, …, n) и yi (i = 1, 2, …, m), то для того чтобы пара x R n, y R + была седловой точкой функции Лагранжа L(x, y), необходимо и достаточно, чтобы выполнялись сле дующие условия:

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

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

Составим функцию Лагранжа (5.1.3):

Здесь мы учли, в том числе, и ограничения (5.1.11), которые преобразо вали к такому виду: x1 0, x2 0.

Производные функции Лагранжа равны Условия Куна — Таккера в дифференциальной форме (5.1.5)—(5.1.8) запишутся в виде (5.1.5')—(5.1.8'):

Если ввести обозначения раскрыть скобки и перенести все переменные в левые части ограничений (5.1.5')—(5.1.8'), а все константы — в правые части, то условия Куна — Таккера примут следующий вид:

Решение этой системы, если оно существует, можно найти с помощью метода искусственного базиса.

Введем неотрицательные переменные s1 0, s2 0 и поставим такую задачу линейного программирования:

Если в оптимальном решении этой задачи s1 = s2 = 0, то набор чисел x1, x2, p1, p2, q1, q2, r1, r2 будет удовлетворять условиям Куна — Такке ра (5.1.12), значит, вектор будет являться оптимальным решением задачи (5.1.9)—(5.1.11).

Чтобы решить данную задачу, можно воспользоваться симплексным методом, при этом для учета условий p1r1 = 0, p2r2 = 0, q1x1 = 0, q2x2 = 0 при вычислительной реализации симплексного метода необходимо следить за тем, чтобы не вводить в базис одновременно переменные pi и ri с одним и тем же индексом i и переменные qj и xj с одним и тем же индексом j.

Соответствующая симплексная таблица представлена в табл. 5.1.1.

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

Поэтому на первом шаге в базис вводится переменная x1 (соответст вующий оценочный коэффициент x1 = 2 ). Итак, x1 = 29/10, x2 = 63/10, y1 = 17/5, y2 = y3 = y4 = 0.

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

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

Основная идея метода возможных направлений такова. В качестве на чального приближения к оптимальному решению задачи выпуклого про граммирования (5.1.1)—(5.1.2) выбирается некоторая внутренняя точка x (0) множества допустимых решений [т. е. все ограничения (5.1.2) в этой точке должны выполняться как строгие неравенства].

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

Вектор e(k), определяющий направление перемещения из точки x (k ) в точку x(k+1) (на k м шаге метода) должен удовлетворять двум т р е б о 1. При достаточно малых h(k ) точка x (k+1), определяемая формулой (5.1.13), должна принадлежать множеству допустимых решений (т. е. век тор e(k) должен задавать в о з м о ж н о е н а п р а в л е н и е). В частности, если точка x (k ) является граничной точкой множества допустимых реше ний, то вектор e(k) должен быть направлен внутрь этого множества.

2. При достаточно малых h(k ) точка x(k+1), определяемая формулой (5.1.13), должна принадлежать множеству допустимых решений [т. е. век функции f(x) ].

Величина h(k ) шага смещения в (5.1.13) выбирается из условия наиболь шего роста целевой функции f(x) при перемещении из точки x (k ) в точку x (k+1) с учетом того, что новое приближение x (k+1), определяемое формулой (5.1.13), должно оставаться во множестве допустимых решений.

Если очередное приближение x (k ) является в н у т р е н н е й точкой множества допустимых решений [т. е. в этой точке все ограничения (5.1.2) выполняются как строгие неравенства], то вектор e(k ) можно выбрать совпадающим с градиентом целевой функции f(x) [тогда e(k ) = grad f ( x (k) ) будет указывать направле ние наискорейшего возрастания функции f (x) в точке x (k ) ].

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

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

1. Угол между вектором e(k) и вектором grad f ( x (k ) ) должен быть как можно меньшим.

2. Для каждого из ограничений i = i1, i2, …, iq, активных в точке x (k ) (т. е.

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

3. Вектор e(1) должен быть ограниченным — поскольку направление определяется с точностью до положительного множителя, данное условие обеспечивает однозначность выбора e(1).

Эти условия приводят к постановке следующей задачи:

Данную задачу можно свести к задаче линейного программирования, для этого нужно представить переменные e(jk ) (которые по смыслу задачи (5.1.14)—(5.1.15) могут принимать значения произвольного знака) как раз ности e(jk) = e(jk) e(jk ) новых н е о т р и ц а т е л ь н ы х переменных e(jk) 0, e(jk) 0 и добавить условия e(jk )e(jk ) = 0 (j = 1, 2, …, n).

и задача (5.1.14)—(5.1.15) примет вид Эту задачу после введения фиктивных переменных (для преобразова ния к предпочитаемому виду) можно решить симплексным методом. При этом для учета условий e(jk )e(jk ) = 0 при вычислительной реализации сим плексного метода необходимо следить за тем, чтобы не вводить в базис од новременно переменные e(1) и e(1) с одинаковым индексом j (j = 1, 2,.., n).

ПРИМЕР 5.1.2. Требуется найти приближение к оптимальному решению задачи выпуклого программирования (5.1.9)—(5.1.11) из примера 5.1.1, для чего провести три первые итерации метода возможных направлений, вы брав в качестве начального приближения вектор Решение. Как было показано в примере 5.1.1, начальное приближение является в н у т р е н н е й точкой множества допустимых решений.

Очередное приближение x(1) к оптимальному решению задачи выберем в направлении наискорейшего возрастания целевой функции:

Найдем границы шага смещения h в направлении e(0), при котором точка будет оставаться во множестве допустимых решений. Запишем условия допустимости:

Решениями этой системы неравенств являются все h [1/14;1/14]. Вы берем h из этого отрезка таким образом, чтобы значение целевой функ ции f(x) в точке x (1) = x (0) + he(0) было максимальным.

Для этого найдем точку максимума функции одной переменной h на отрезке h [1/14;1/14].

Производная (h) = 49 2(2h 1) = 98(2h 1) обращается в нуль в точке h = 1/2, положительна при h < 1/2 и отрицательна при h > 1/2, поэтому точка h = 1/2 является точкой глобального максимума функции 0 (h), а максимум функции 0 (h) на отрезке h [1/14;1/14] достигается в точке h(0) = 1/14.

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

Итак, получили новое приближение к оптимальному решению задачи (5.1.9)—(5.1.11).

Переходим ко в т о р о м у ш а г у метода возможных направлений.

Точка x (1) является г р а н и ч н о й точкой множества допустимых ре шений; второе из ограничений (5.1.10) выполняется в этой точке как ра венство, а первое ограничение (5.1.10) и оба ограничения (5.1.11) — как строгие неравенства:

Поэтому если двигаться в направлении наискорейшего возрастания целевой функции, то новое приближение мо жет выйти за границы области допустимых решений, т. е. направление не является возможным в точке Возможное направление возрастания целевой функции f ( x ) в точке x (1) выберем так, чтобы оно являлось оптимальным решением задачи (5.1.14)—(5.1.15), которая в дан ном случае имеет вид Чтобы свести эту задачу к задаче линейного программирования, пред ставим переменные e1 и e2 как разности новых неотрицательных пере причем При этом и задача (5.1.20)—(5.1.21) примет вид Будем решать эту задачу симплексным методом, введя предварительно дополнительные переменные s1 и s2, чтобы преобразовать неравенства в равенства:

Для учета условий e1+ e1 = 0, e2+ e2 = 0 при вычислительной реализации симплексного метода будем следить за тем, чтобы не вводить в базис одно временно переменные e(1) и e(1) (j = 1, 2).

Симплексная таблица представлена в табл. 5.1.2.

В результате мы получили оптимальное решение задачи (5.1.22)—(5.1.25).

Теперь легко найти оптимальное решение задачи (5.1.20)—(5.1.21):

Тем самым, мы получили направление очередного шага:

Найдем границы шага смещения h в направлении e(1), при котором точка будет оставаться во множестве допустимых решений. Имеем:

Точка x (2) остается во множестве допустимых решений при всех h [4;1]. Выберем h из этого отрезка таким образом, чтобы значение це левой функции f (x) в точке x (2) было максимальным.

Для этого найдем точку максимума функции одной переменной h на отрезке h [4;1].

Производная 1 (h) = h + 6 обращается в нуль в точке h = 6, положи тельна при h < 6 и отрицательна при h > 6, поэтому точка h = 6 является точкой глобального максимума функции 1 (h), а максимум функции 1 (h) на отрезке h [4;1] достигается в точке h(1) = 1.

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

Итак, получили очередное приближение к оптимальному решению задачи (5.1.9)—(5.1.11).

Начинаем т р е т и й ш а г метода возможных направлений.

Точка x(2) является граничной точкой множества допустимых реше ний; оба ограничения (5.1.10) выполняются в этой точке как равенства, а оба ограничения (5.1.11) — как строгие неравенства:

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

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

Этой системе неравенств удовлетворяют все h [0; 5]. Выберем h из это го отрезка таким образом, чтобы значение целевой функции (5.1.2) в точке x (3) = x (2) + he(2) было максимальным.

Для этого найдем точку максимума функции одной переменной h на отрезке h [0; 5].

Производная (h) = (8 5h)/4 обращается в нуль в точке h = 8/5, по ложительна при h < 8/5 и отрицательна при h > 8/5, поэтому точка h = 8/5 является точкой глобального максимума функции 2 (h) и точкой локального максимума этой функции на отрезке h [0;5].

Получаем очередное приближение:

Итерационный процесс метода возможных направлений иллюстриру ется рис. 5.1.1.

Заметим, что x (3) — это точное решение задачи (5.1.9)—( 5.1.11); оно бы ло получено в примере 5.1.1.

Опишем теперь метод условного градиента. Пусть x (k ) — очередное при ближение к оптимальному решению задачи выпуклого программирования (5.1.1)—(5.1.2) — такая точка x (k ) множества допустимых решений, что Тогда в окрестности точки x (k ) целевая функция f (x) может быть представлена в виде Будем максимизировать на допустимом множестве линейную функцию которая является приближением разности f(x) f ( x (k ) ) с точностью до величины o ( x x (k ) ).

Рис. 5.1.1. Итерационный процесс метода возможных направлений Пусть x (k ) — решение вспомогательной задачи максимизации функции (5.1.22) при ограничениях (5.1.2).

Следующее приближение x(k +1) к оптимальному решению исходной за дачи (5.1.1)— (5.1.2) построим по формуле в которой величину шага смещения h(k ) выберем как где h(k ) выбирается из условия наибольшего роста целевой функции f(x) при перемещении из точки x (k ) в точку Тогда, поскольку множество допустимых решений выпукло, а h(k ) [0;1], точка x(k +1) (5.1.23) останется допустимым решением.

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

ПРИМЕР 5.1.3. Требуется найти приближение к оптимальному решению задачи выпуклого программирования (5.1.9)—(5.1.11) из примера 5.1.1, для чего провести три первые итерации метода условного градиента, выбрав в качестве начального приближения вектор Решение. Как было показано в примере 5.1.1, начальное приближение является допустимым решением. При этом Поставим вспомогательную задачу максимизации функции (5.1.22) при ограничениях (5.1.2):

Оптимальное решение этой задачи равно (симплексная таблица представлена в табл. 5.1.4).

Выберем h(0) из условия наибольшего роста целевой функции f(x) при перемещении из точки Рассмотрим функцию Производная обращается в нуль в точке h = 56/160 = 7/20, положительна при h < 7/ и отрицательна при h > 7/20, поэтому точка h(0) = 7/20 является точкой глобального максимума функции 0 (h).

Величину шага смещения h(0) выберем как и построим следующее приближение x (1) к оптимальному решению ис ходной задачи:

Поставим вспомогательную задачу максимизации функции (3.5.22) при ограничениях (5.1.2):

f1(x) = ( grad f ( x(1) ), x x(1) ) = Оптимальное решение этой задачи равно (симплексная таблица представлена в табл. 5.1.5).

Выберем h(1) из условия наибольшего роста целевой функции f (x) при перемещении из точки в точку Рассмотрим функцию Производная обращается в нуль в точке h = 70/53, положительна при h < 70/53 и от рицательна при h > 70/53, поэтому точка h(1) = 70/53 является точкой глобального максимума функции 1 (h).

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

При этом Поставим вспомогательную задачу максимизации функции (3.5.22) при ограничениях (5.1.2):

Оптимальное решение этой задачи равно (симплексная таблица представлена в табл. 5.1.6).

Выберем h(2) из условия наибольшего роста целевой функции f(x) при перемещении из точки Рассмотрим функцию Производная обращается в нуль в точке h = 4/25, положительна при h < 4/25 и отрица тельна при h > 4/25, поэтому точка h(2) = 4/25 является точкой глобаль ного максимума функции 2 (h).

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

Перейдем к рассмотрению метода штрафных функций, идея которого состоит в переходе от задачи условной максимизации функции (5.1.1) при ограничениях (5.1.2) к последовательности задач безусловной максимиза ции где функции k (x) с ростом k все в большей степени учитывают ограниче ния (5.1.2). Для этого функции k (x) подбираются так, чтобы fk (x) при больших k мало отличались от f(x) при x, удовлетворяющих ограничениям (5.1.2), и быстро убывали при удалении x от множества допустимых реше ний. Более строго, последовательность функций {k (x)}k =1 называется по следовательностью штрафных функций для задачи (5.1.1)—( 5.1.2), если lim k (x) = Такую последовательность штрафных функций можно определить, например, так:

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

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

ПРИМЕР 3.5.4. Требуется найти оптимальное решение задачи выпуклого программирования (5.1.9)—(5.1.11) из примера 5.1.1 с помощью метода штрафных функций.

Решение. Предположим, что в точке x (k ) максимума вспомогательной функции все ограничения исходной задачи (5.1.10)—(5.1.11), которые мы предста вим в форме нарушаются, т. е.

В точке максимума функции fk (x) частные производные по x1 и x должны быть равны нулю, откуда или Выразим из первого уравнения и подставим во второе уравнение:

Отсюда При этом Поскольку при любом k x1k ) > 0, x2k ) > 0, наше предположение о том, что все ограничения исходной задачи нарушаются, неверно.

Выдвинем другую гипотезу. Предположим, что в точке максимума функции fk (x) выполняются третье и четвертое ограничения исходной за дачи (5.1.10)—(5.1.11), а первое и второе ограничения не выполняются, т. е.

Тогда В точке максимума функции fk (x) частные производные по x1 и x должны быть равны нулю, откуда или Выразим из первого уравнения и подставим во второе уравнение:

Поскольку при любом k x1k) + x2k ) < 10, наше предположение о том, что второе ограничение исходной задачи нарушаются, неверно.

Рассмотрим третью гипотезу относительно местоположения точки мак симума. Предположим, что в точке максимума функции fk (x) выполняют ся все ограничения исходной задачи (5.1.10)—(5.1.11), кроме первого, т. е.

В точке максимума функции fk (x) частные производные по x1 и x должны быть равны нулю, откуда или Выразим из первого уравнения и подставим во второе уравнение:

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

ПРИМЕР 9.1.1. Инвестор рассматривает четыре инвестиционные опера ции со случайными эффективностями, описываемыми случайными вели чинами E1, E2, E3, E4 с рядами распределения Требуется определить, какие из этих операций оптимальны по Парето.

Решение. Ожидаемые эффективности и риски равны соответственно ME1 = 4,81, 1 = 1,77, ME2 = 4,16, 2 = 3,57, ME3 = 7,00, 3 = 2,30, ME4 = 2,81, 4 = 2,54. Нанесем точки (MEi; i) на единый график (рис. 9.1.1). i я опера ция доминирует j ю, если точка, соответствующая i й операции, нахо дится на графике правее и ниже точки, соответствующей j й операции.

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

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

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

• потерять 1 руб.;

• с вероятностью 0,5 получить 1 000 000 руб. и с вероятностью 0,5 поте рять 100 000 руб., то обе эти операции окажутся оптимальными по Парето (ME1 = –1, 1 = 0, ME2 = 550 000, 2 = 450 000), но, скорее всего, мы склонимся к выбору первой операции, несмотря на то, что ожидаемый доход по ней составляет отрицательное число (–1 руб.), тогда как ожидаемый доход от исполнения второй операции составляет 550 000 руб. — слишком велик риск у второй операции, слишком велика вероятность потерь.

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

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

Например, в ситуации с частичной неопределенностью можно рассмотреть в качестве критериев ожидаемый доход MQ (операция i не хуже операции j по этому критерию, если MQi MQj, и лучше операции j по этому критерию, если MQi > MQj) и ожидаемые сожаления MR (операция i не хуже операции j по этому критерию, если MRi MRj, и лучше операции j по этому критерию, если MRi < MRj).

Инвестор рассматривает четыре инвестиционные операции со случай ными эффективностями, описываемыми случайными величинами En, En + 1, E n + 2 и E n + 3 (где n —номер варианта) с рядами распределения, приведен ными в табл. 9.2.1. Требуется определить, какие из этих операций опти мальны по Парето.

10. МНОГОКРИТЕРИАЛЬНАЯ ОПТИМИЗАЦИЯ

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

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

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

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

Находим максимальное значение z1, первого по важности критерия в об ласти допустимых решений, решив задачу Затем назначается, исходя из практических соображений и принятой точ ности, величина допустимого отклонения 1 > 0 (экономически оправданной уступки) критерия z1 и отыскивается максимальное значение второго крите рия z2 при условии, что значение первого должно отклоняться от максималь ного не более чем на величину допустимой уступки, т. е. решается задача Снова назначается величина уступки 2 > 0 по второму критерию, ко торая вместе с первой используется при нахождении условного экстре мума третьего частного критерия, и т. д. Наконец, выявляется экстре мальное значение последнего по важности критерия z2 при условии, что значение каждого из первых m – 1 частных критериев отличается от экс тремального не более чем на величину допустимой уступки. Получаемое на последнем этапе решение считается о п т и м а л ь н ы м. Остается за метить, что этот метод не всегда приводит к эффективному решению.

ПРИМЕР 3.10.1. Дана задача векторной оптимизации:

Требуется определить переговорное множество, а затем решить дан ную задачу методом последовательных уступок (допустимые уступки по первым двум критериям принять равными 1 = 3 и 2 = 5/3 ).

Решение. Очевидно, в данной задаче переговорное множество совпадает с областью допустимых решений (т. е. точек, удовлетворяющих условиям (10.1.5), они соответствуют пятиугольнику ABCDE на рис. 10.1.1, а). Дейст вительно, возьмем любую точку множества допустимых решений. Если мы от нее сдвинемся вправо, то значения критериев z2 и z3 увеличатся, но значение критерия z1 уменьшится. Если мы сдвинемся левее, то значения критериев z2 и z3 уменьшатся, но значение критерия z1 увеличится. Если мы сдвинемся ниже, то значения критериев z1 и z2 увеличатся, но значе ние критерия z3 уменьшится. Если мы сдвинемся выше, то значения кри териев z1 и z2 уменьшатся, но значение критерия z3 увеличится. Таким об разом, ни одна из точек множества допустимs[ решений не доминируется другими, т. е. все допустимые точки оптимальны по Парето.

Максимизируем функцию z1 при условиях (10.1.5). Это легко сделать графически (рис. 10.1.1, а). Получаем:

Переходим к максимизации функции z2 при условиях (10.1.5) и допол нительном ограничении, позволяющем учесть, что по критерию z1 нельзя уступать более чем на 1. Так как z1 1 = 4, то дополнительное ограниче ние будет иметь вид Рис. 10.1.1. Графическое решение задачи векторной оптимизации Задачу (10.1.3), (10.1.5), (10.1.6) решим графически (рис. 10.1.1, б):

Теперь уступаем по критерию z2 на 2 и получаем второе дополнитель ное ограничение:

Максимизируем z3 при условиях (10.1.5), (10.1.6), (10.1.7) графически (рис. 3.10.1, в). Получаем оптимальное решение трехкритериальной задачи:

При этом Дана задача векторной оптимизации:

где n — номер варианта. Требуется определить переговорное множество, а затем решить данную задачу методом последовательных уступок (до пустимые уступки по первым двум критериям принять равными 1 = 3 и 2 = 2 ).

11. ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

и указания к выполнению заданий выбрать одну из возможных альтернатив, обозначенных номерами i = 1, 2, …, m. Ситуация является полностью неопределенной, т. е. известен лишь набор возможных вариантов состояний внешней (по отношению к лицу, принимающему решение) среды, обозначенных номерами j = 1, 2, …, n.

Если будет принято i e решение, а состояние внешней среды соответствует j й ситуации, то лицо, принимающее решение, получит доход qij. Матрица называется матрицей последствий (от реализации возможных решений).

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

Допустим, мы хотим оценить риск, который несет i e решение. Нам не известна реальная ситуация. Но если бы мы знали, что осуществляется j е состояние внешней среды, то выбрали бы наилучшее решение, т. е. при носящее наибольший доход Значит, принимая i e решение, мы рискуем получить не qj, а только qij, т. е. если мы примем i е решение, а во внешней среде реализуется j е состояние, то мы будем с о ж а л е т ь о недополученном доходе в размере (по сравнению с тем, как если бы мы знали точно, что реализуется j е состояние внешней среды, и выбрали бы решение, приносящее наиболь ший доход q j = max qij ). Матрица где сожаления rij рассчитаны по формуле (11.1.1), называется матрицей сожалений (или матрицей рисков).

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

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

ПРАВИЛО ВАЛЬДА (ПРАВИЛО КРАЙНЕГО ПЕССИМИЗМА). Рассматривая i e реше ние, будем полагать, что на самом деле складывается ситуация, наихуд шая с нашей точки зрения (т. е. приносящая наименьший доход ai = min qij ) и выберем решение i0 с наибольшим ai. Итак, правило Вальда j =1,2,…,n рекомендует принять такое решение i0, что ПРАВИЛО СЭВИДЖА (ПРАВИЛО МИНИМАЛЬНЫХ СОЖАЛЕНИЙ). При применении этого правила анализируется матрица сожалений R. Рассматривая i e ре шение, будем полагать, что на самом деле складывается ситуация макси мальных сожалений bi = max rij, и выберем решение i0 с наименьшим bi.

Итак, правило Сэвиджа рекомендует принять такое решение i0, что ПРАВИЛО ГУРВИЦА взвешивает пессимистический и оптимистический подходы к анализу неопределенной ситуации. По правилу Гурвица, при нимается решение i0, на котором достигается максимум выражения где [0; 1]. Значение выбирается из субъективных соображений. Если приближается к единице, то правило Гурвица приближается к правилу Вальда, при приближении к нулю правило Гурвица приближается к пра ПРИМЕР 11.1.1. Сидя в отправляющемся на курорт поезде, перед самым отправлением Петя вдруг вспомнил, что, к а ж е т с я, забыл выключить дома утюг. Можно еще успеть сойти с поезда и исправить ошибку, но то гда пропадет путевка (100 000 руб.). Если же уехать, утюг, если он дейст вительно включен, может стать причиной пожара, и тогда придется ре монтировать квартиру (1 500 000 руб.). Петя не уверен, включен утюг или выключен. Составить матрицу последствий и матрицу сожалений. Опре делить решения, рекомендуемые критериями Вальда, Сэвиджа, Гурвица.

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

Матрица последствий имеет вид Составим матрицу сожалений. Максимум по первому столбцу равен по второму — поэтому матрица сожалений Минимальные элементы строк матрицы последствий a1 = –1 500 000, a2 = =–100 000. Теперь из двух чисел (–1 500 000), (–100 000) находим наибольшее.

Это (–100 000). Значит, правило Вальда рекомендует принять второе решение, т. е. вернуться домой.

Максимальные элементы строк матрицы сожалений b1 = 1 400 000, b2 = 100 000. Из чисел 1 400 000, 100 000 находим наименьшее. Это 100 000.

Значит, правило Сэвиджа также, как и правило Вальда, рекомендует принять второе решение, т. е. вернуться домой.

Читатель может убедиться, что правило Гурвица при = 0,5 также, как правила Вальда и Сэвиджа, рекомендует принять второе решение, т. е. вернуться домой.

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

ПРАВИЛО МАКСИМИЗАЦИИ ОЖИДАЕМОГО ДОХОДА. Доход, получаемый при принятии i го решения, является случайной величиной Qi с рядом рас пределения Ожидаемый доход при принятии i го решения оценивается математическим ожиданием MQi соответствующей случайной величины Qi. Правило максимизации ожидаемого дохода рекомендует принять решение, приносящее максимальный ожидаемый доход.

ПРАВИЛО МИНИМИЗАЦИИ ОЖИДАЕМЫХ СОЖАЛЕНИЙ. Сожаления при реализа ции i го решения представляются случайной величиной Ri с рядом рас пределения Ожидаемые сожаления оценивается математическим ожиданием MRi со ответствующей случайной величины Ri. Правило минимизации ожидаемых сожалений рекомендует принять решение, влекущее минимальные ожи даемые сожаления.

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

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

Предположим, что банк рассматривает возможность инвестиций в m проектов: i =1, 2, …, m.

П р и а н а л и з е э ф ф е к т и в н о с т и инвестиционного проекта все издержки ct и денежные поступления bt приводятся к одному и тому же моменту времени (как правило, начальному) и суммируются, в результате получается характеристика инвестиционного проекта, называемая его чистым дисконтированным доходом NPV (Net Present Value):

где i — процентная ставка.

П р и а н а л и з е р и с к о в проекта можно классифицировать состояния внешней среды в зависимости от рисков: макроэкономических, экологических, социально опасных, связанных с непредвиденными срывами и др. В результате будет получен набор из таких состояний j = 1, 2, …, n.

Теперь можно составить матрицу последствий Q (каждый элемент которой qij будет представлять собой эффективность NPV i го проекта при j м состоянии внешних условий) и выбрать проекты, используя описанные критерии.

ПРИМЕР 11.1.2. Владелец груза должен выбрать одну из двух альтерна тив: страховать груз или не страховать. Риск заключается в том, что с ве роятностью 0,1 возможна катастрофа, в результате которой груз будет утрачен. Если груз застрахован, то в случае его утраты владелец теряет стоимость груза (95 000 руб.), но получает компенсацию 100 000 руб., если же катастрофы не произошло, он теряет 5000 руб, потраченные на стра ховой полис. Если груз не застрахован, в случае катастрофы теряется его стоимость, при благополучном же исходе владелец не несет никаких рас ходов. Какое решение принять?

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

Матрица последствий имеет вид Вероятности состояний внешней среды известны (p1 = 0,1, p2 = 0,9), по этому ряды распределения дохода при выборе первой и второй стратегии таковы:

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

Составим матрицу сожалений. Максимум по первому столбцу равен q1 = max q i1 = 0, по второму — q2 = max q i 2 = 0, поэтому матрица сожалений Вычислим ожидаемые сожаления при указанных выше вероятностях.

Получаем MR1 = 4500, MR2 = 9500. Минимальные ожидаемые сожаления равны 4500, они соответствуют первому решению — застраховать груз.

ПРИМЕР 11.1.3. Исследуем ситуацию принятия решений в условиях не определенности в случае, когда матрица последствий Решение. Составим матрицу сожалений. Имеем:

поэтому матрица сожалений По правилу Вальда (правилу крайнего пессимизма) будем полагать, что при принятии i го решения на самом деле складывается самая пло хая ситуация, т. е. приносящая наименьший доход ai = min q ij, и выберем решение i0 с наибольшим ai0. Имеем:

Из этих чисел 2, 2, 3, 1 находим максимальное: это 3. Значит, пра вило Вальда рекомендует принять третье решение.

Правило Сэвиджа аналогично правилу Вальда, только анализируется матрица сожалений: рассматривая i e решение, будем полагать, что на самом деле складывается ситуация максимальных сожалений bi = max rij., и выберем решение i0 с наименьшим bi0. Имеем:

Из этих чисел 8, 6, 5, 7 находим минимальное. Это 5. Значит, пра вило Сэвиджа рекомендует принять третье решение.

Если известны вероятности состояний внешней среды:

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

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

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

т. е. опять третье решение.

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

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

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

Рассмотрим конфликт двух участников с п р о т и в о п о л о ж н ы м и и н т е р е с а м и. Математической моделью такого конфликта является игра с нулевой суммой. Участники игры называются игроками. Страте гией игрока называется осознанный выбор одного из множества возмож ных вариантов его действий. Будем рассматривать конечные игры, в кото рых множества стратегий игроков конечны; стратегии первого игрока про нумеруем от 1 до m, а стратегии второго игрока — от 1 до n.

Если первый игрок выбрал свою i ю стратегию, а второй игрок — свою j ю стратегию, то результатом такого совместного выбора будет платеж aij второго игрока первому (это не обязательно денежная сумма, а любая оценка последствий выбора игроками своих стратегий). Таким образом, игра с нулевой суммой однозначно определяется матрицей которая называется платежной. Строки этой матрицы соответствуют стратегиям первого игрока, а столбцы — стратегиям второго игрока. Ко нечные игры с нулевой суммой называются матричными, так как цели ком определяются своими платежными матрицами.

Игра происходит партиями. Партия игры состоит в том, что игроки одновременно называют свой выбор: первый игрок называет некоторый номер строки матрицы (по своему выбору), а второй — некоторый но мер столбца этой матрицы (также по своему выбору). После этого проис ходит «расплата». Пусть, например, первый игрок назвал номер i, а вто рой — j. Тогда второй игрок платит первому сумму aij (не обязательно вы раженную в денежных единицах). На этом партия игры заканчивается.

Если aij > 0, то это означает, что при выборе первым игроком i й страте гии, а вторым — j й стратегии выигрывает первый игрок, если же aij < 0, то это значит, что при данном выборе стратегий выигрывает второй игрок.

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

Стратегия называется чистой, если выбор игрока неизменен от партии к партии. У первого игрока, очевидно, есть m чистых стратегий, а у второ го — n.

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

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

он выберет такой столбец матрицы, в котором платеж aij (второго игрока первому) минимален.

Переберем все наши стратегии i = 1, 2, …, m и выберем такую из них, при которой второй игрок, действуя максимально разумно, заплатит нам наибольшую сумму. Величина называется нижней ценой игры, а соответствующая ей стратегия первого игрока — максиминной. Аналогично (но уже с точки зрения второго иг рока) определяется верхняя цена игры и соответствующая ей минимаксная стратегия второго игрока. Подчерк нем, что по своему определению нижняя цена игры представляет собой минимальный гарантированный выигрыш первого игрока (т. е. применяя свою максиминную стратегию, первый игрок обеспечивает себе выигрыш, не меньший ), а верхняя цена — величину, противоположную макси мальному гарантированному проигрышу второго игрока [т. е. применяя свою минимаксную стратегию, второй игрок гарантирует, что он не проиг рает больше, чем, или, по другому, выиграет не меньше чем (– )].

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

ПРИМЕР 12.1.1. В платежной матрице указано, какую долю рынка получит наше предприятие, если оно будет действовать согласно каждой из возможных трех стратегий, а основной конкурент — согласно каждой из своих возможных трех стратегий.

Решение. Данная игра имеет седловую точку. Действительно, нижняя цена игры (соответствует второй стратегии первого игрока), а верхняя цена игры (соответствует второй стратегии второго), поэтому игроки, действуя каж дый по своей второй стратегии, могут гарантировать себе: первый — вы игрыш не менее = = = 0,3 = 30% рынка, а второй — что первый игрок выиграет не более = 30% рынка. Таким образом, оптимальная чистая стратегия первого игрока — вторая, второго игрока — вторая, а цена игры равна = 0,3.

Смешанной стратегией первого игрока называется вектор где все pi рой первый игрок выбирает свою i ю стратегию. Аналогично определяет ся смешанная стратегия второго игрока. Чистая стратегия также подпадает под определение сме шанной — если все вероятности равны нулю, кроме одной, равной единице.

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

Стратегии называются оптимальными смешанными стратегиями соответственно первого и второго игрока, если Если у обоих игроков есть оптимальные смешанные стратегии, то пара (p, q ) называется решением игры (или седловой точкой в смешанных стратегиях), а число = M(p, q ) — ценой игры.

ОСНОВНАЯ ТЕОРЕМА ТЕОРИИ ИГР. В любой матричной игре у игроков есть оптимальные смешанные стратегии.

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

ПРИМЕР 12.1.2. Правила игры таковы. Первый игрок прячет в кулаке од ну из двух монет: 1 руб. или 5 руб., по своему выбору, а второй игрок пы тается угадать, какая монета спрятана, и если угадывает, то получает эту монету, в противном случае платит первому игроку 3 руб.

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

а) гарантированный выигрыш первого игрока б) верхняя граница проигрыша второго игрока в зависимости от его Рис. 12.1.1. Гарантированный выигрыш первого игрока и верхняя граница проигрыша второго игрока в зависимости от смешанных стратегий Второй игрок так выбирает свои стратегии, чтобы обеспечить первому минимальный выигрыш: (p) = min{1 (p), 2 (p)} (эта функция отмечена на рис. 12.1.1, а жирной линией). Иными словами, второй игрок в любом слу чае заставит первого выиграть как можно меньше, т. е. в рассматривае мой игре при p [0; p ) второй игрок будет выбирать свою вторую страте гию и первый игрок будет выигрывать 2 (p), при p ( p ;1] второй игрок будет выбирать первую стратегию и первый игрок будет выигрывать 1(p). Наилучший для первого игрока выбор при этом соответствует = max v(p), т. е. p = p. Число называется при этом ценой игры. В нашем случае p = 2/3, т. е. оптимальной смешанной стратегией первого игрока является стратегия которая определяется из условия при этом цена игры равна = 1 (2/3) = 2 (2/3) = 1/3.

Отметим, что второй игрок, действуя разумно, никогда не будет выби рать третью и четвертую стратегии, поэтому вектор оптимальной сме шанной стратегии второго игрока имеет вид Тогда выигрыш второго игрока равен 1 (q) = q + 3(1 q), если первый игрок выбирает свою первую стратегию, и 2 (q) = 3q 5(1 q), если первый игрок выбирает свою вторую стратегию (рис. 3.12.1, б). Значение q опреде ляется из условия 1 (q) = 2 (q), оно равно q = 2/3.

Поэтому оптимальная смешанная стратегия второго игрока равна ПРИМЕР 3.12.3. Решить игру с платежной матрицей Решение. Платежная матрица данной игры имеет вид Проверим, имеет ли данная игра седловую точку. Нижняя цена игры а верхняя цена игры т. е., значит, седловой точки (в чистых стратегиях) в игре нет. Пусть первый игрок выбирает свою первую стратегию с вероятностью p, а вто рую стратегию — соответственно с вероятностью (1 – p), т. е. первый иг рок играет со смешанной стратегией Обозначим j (p) ожидаемый выигрыш первого игрока, если второй иг рок при этом выберет свою j ю стратегию. В нашем случае Графики этих функций построены на рис. 3.12.2.

Рис. 12.1.2. Гарантированный выигрыш первого игрока при различном выборе смешанной стратегии Второй игрок так выбирает свои стратегии, чтобы обеспечить первому минимальный выигрыш: (p) = min{1 (p), 2 (p), 3 (p), 4 (p)} (эта функция отмечена на рис. 3.12.2 жирной линией). Иными словами, при p [0; p ) второй игрок будет выбирать свою вторую стратегию и первый игрок бу дет выигрывать 2 (p), при p ( p ;1] второй игрок будет выбирать первую стратегию и первый игрок будет выигрывать 1(p). Наилучший для пер вого игрока выбор при этом соответствует = max v(p). В нашем случае оптимальной смешанной стратегией первого игрока является стратегия [она определяется из условия 1 (p) = 2 (p) ], при этом цена игры равна = 1 (6/11) = 2 (6/11) = 2/11.

Отметим, что второй игрок, действуя разумно, никогда не будет выби рать третью и четвертую стратегии, поэтому вектор оптимальной сме шанной стратегии второго игрока имеет вид Тогда выигрыш второго игрока равен 1 (q) = 2q + 3(1 q), если первый игрок выбирает свою первую стратегию, и 2 (q) = 2q 4(1 q), если первый игрок выбирает свою вторую стратегию. Значение q определяется из ус ловия 1 (q) = 2 (q), оно равно q = 7/11.

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

Пусть рассматривается игра с платежной матрицей (3.12.1), в с е смешанные стратегии первого и второго игрока.

Цена данной игры положительна, так как все элементы платежной матрицы положительны.

Если стратегия p является оптимальной, то выигрыш первого игрока независимо от того, какую стратегию выберет второй игрок, будет не меньше цены игры :

При этом Введем новые обозначения и разделить все неравенства системы (12.1.2) на положительную цену иг ры, то получим следующую систему:

При этом Цель первого игрока — максимизировать цену игры, т. е. минимизиро вать величину 1/ = xi.

Таким образом, приходим к задаче линейного программирования для первого игрока:

Аналогичные рассуждения с позиции второго игрока приводят к задаче линейного программирования, двойственной к задаче для первого игрока:

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

ПРИМЕР 12.1.4. Решить матричную игру из примера 12.1.2 с помощью ее сведения к паре взаимно двойственных задач линейного программирования.

Решение. От платежной матрицы путем добавления положительного числа b = 5 перейдем к матрице все элементы которой положительны.

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

Оптимальные решения этих задач равны оптимальные смешанные стратегии игроков 6/53 + 5/53 5/53 5/ а цена игры Предприятие имеет две стратегии рыночного поведения, тогда как его конкурент имеет четыре таких стратегии. Прибыль (в млн. руб.), которую получит предприятие при условии, что оно изберет стратегию i (i = 1, 2), а его конкурент — стратегию j (j = 1, 2, 3, 4), равна aij. Платежная матрица для каждого варианта приведена в табл. 12.2.1.

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

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

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

Первый игрок может выбрать одну из m своих стратегий, обозначен ных номерами i = 1, 2, …, m, а второй игрок — одну из n своих стратегий, обозначенных номерами j = 1, 2, …, n, Если первый игрок выбрал свою i ю стратегию, а второй игрок — свою j ю стратегию, то в результате такого совместного выбора первый игрок получает выигрыш aij, а второй игрок — выигрыш bij. При этом совершенно не обязательно, чтобы bij = aij, как в матричной игре.

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

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

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

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

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

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

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

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

Так как pi можные варианты пар выигрышей представляют собой выпуклую обо лочку точек плоскости с координатами ( aij, bij ), i = 1, 2, …, m, j = 1, 2, …, n ;

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

Множество точек, оптимальных по Парето (т. е. не доминируемых дру гими), описывается так:

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

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

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

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

Реализация алгоритма Нэша предполагает решение задачи математи ческого программирования ПРИМЕР 13.1.1. Проанализировать биматричную игру, заданную матри цами Решение. Смешанные стратегии игроков можно представить в виде (здесь p [0;1], q [0;1] ). При этом соответственно, то математические ожидания выигрышей игроков равны соответственно Максиминные стратегии игроков определяются из условий Таким образом, максиминные стратегии первого и второго игрока рав ны соответственно Множество всех возможных пар выигрышей игроков представлено че тырехугольником ABCD на рис. 13.1.1. Очевидно, множество Парето соот ветствует отрезку BC, а переговорное множество — отрезку EF.

Рис. 13.1.1. Множество ожидаемых выигрышей, множество Парето Прямая, проходящая через точки B(6; 9) и C(9; 7), задается уравнением M2 = 13 2M1 /3, поэтому функция Нэша на отрезке M1 [20/3; 63/8] (т. е. на отрезке BC) достигает максимума в точке M1 = 349/48. При этом M2 = 13 2M1 /3 = 587/72. Эта точка на рис. 13.1.1 обозначена G.

Точка G(349/48; 587/72) является выпуклой комбинацией точек B(6; 9) и C(9; 7), т. е.

откуда = 83/144.

Точка B соответствует выбору обоими игроками своих первых чистых стратегий, точка C соответствует выбору первым игроком своей первой чистой стратегии, а вторым игроком — своей второй чистой стратегии, поэтому точка G означает, что первый игрок выбирает свою первую чис тую стратегию, а второй игрок с вероятностью q = = 83/144 выбирает первую чистую стратегию, и с вероятностью 1 q = 61/144 — вторую чистую стратегию.

Таким образом, максиминные стратегии первого и второго игрока, рав новесные по Нэшу, равны соответственно При этом средний выигрыш первого игрока равен M1 = 349/48, а второ го игрока — M2 = 587/72.

Каждое из двух конкурирующих предприятий имеет по две стратегии рыночного поведения. Прибыли предприятий (в млн. руб.) при условии, что первое предприятие изберет стратегию i (i = 1, 2), а второе предпри ятие — стратегию j (j = 1, 2), равны соответственно aij и bij. Платежные матрицы (1) = (aij ) и (2) = (bij ) для каждого варианта приведены в табл. 13.2.1.

14. МОДЕЛЬ ПОВЕДЕНИЯ ПОТРЕБИТЕЛЯ

и указания к выполнению заданий Рассмотрим рынок, на котором продаются товары n видов. Пусть p1, p2, …, pn — цены этих товаров, вектор естественно назвать вектором цен.

Пусть некоторый потребитель обладает богатством M ден. ед., и xi — это количество единиц i го товара, которые данный потребитель приоб ретает на рынке (i = 1, 2, …, n). Вектор координаты которого неотрицательны и соответствуют приобретаемым количествам товаров каждого вида, называется набором товаров, а мно жество всех наборов товаров называется пространством товаров (поскольку на наборы товаров не налагается ограничений целочисленности, здесь предполагается, что можно приобрести произвольное — целое или дробное — количество лю бого товара, т. е. что все товары являются б е з г р а н и ч н о д е л и м ы м и).

Стоимость набора товаров x равна, очевидно, Бюджетное множество B — это множество наборов товаров x C, ко торые может себе позволить приобрести при данных ценах p1, p2, …, pn по требитель, обладающий богатством I (при этом предполагается, что тра тить в с е деньги необязательно).

С алгебраической точки зрения бюджетное множество описывается системой линейных неравенств ТЕОРЕМА О БЮДЖЕТНОМ МНОЖЕСТВЕ. Бюджетное множество является выпуклым, ограниченным и замкнутым.

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

В качестве первой аксиомы потребителя примем, что относительно любых двух наборов товаров x, y C потребитель может однозначно ска зать, верно ли, что x y. Тем самым, на пространстве товаров задано ние определяет еще два отношения на пространстве товаров:

когда одновременно верно, что x y и y x ; запись « x y » означает р а в н о ц е н н о с т ь наборов товаров x и y с точки зрения данного потре бителя: x не хуже y, а y не хуже x;

только тогда, когда верно, что x y, и неверно, что x y ; запись « x y »

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

Вторая аксиома потребителя описывает свойства отношений « », « »

и « »:

• отношения слабого предпочтения и равноценности являются рефлек сивными (т. е. для любого набора товаров x C верно, что x x и x x );

• отношения слабого предпочтения, равноценности и сильного предпоч тения являются транзитивными (т. е. для любых наборов товаров x, y, z C из того, что x y, а y z, следует, что x z ; из того, что x y, а y z, следует, что x z ; из того, что x y, а y z, следует, что x z );

• отношение равноценности является симметричным (т. е. из того, что x y, следует, что y x ).

Третья аксиома потребителя говорит о том, что каждый товар являет ся для потребителя желательным, т. е. если x y, то x y, а если x > y, то x y.

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

• u(x) u(y) x y ;

(Из этих условий следует, очевидно, что u(x) > u(y) x y.) Если выбран некоторый набор товаров x C, то множество Px = {y C | y x} называется множеством предпочтительности для x, а множество N x = {z C | x z} называется множеством непредпочти тельности для данного набора товаров. Система предпочтений называет ся непрерывной, если для любого набора товаров x C множества пред почтительности и непредпочтительности являются з а м к н у т ы м и.

ТЕОРЕМА ДЕБРЕ. Если система предпочтений потребителя непрерывна, то для такого потребителя существует непрерывная функция полез ности.

Будем считать функцию полезности д и ф ф е р е н ц и р у е м о й, при этом частная производная u / xi имеет смысл предельной полезности i го товара: она показывает, насколько увеличится полезность, если до бавить к данному набору товаров x е щ е одну единицу i го товара.

Перечислим основные свойства функции полезности:

u(x) — некоторая функция полезности, то, например, u1 (x) = u(x) + a, u2 (x) = bu(x) [при b > 0], u3 (x) = log c u(x) [при c > 1] и любая другая строго возрастающая функция от u(x) также будут функциями полезности);

• функция полезности является с т р о г о в о з р а с т а ю щ е й [аксиома желательности утверждает, что из того, что x > y, следует, что x y ; по определению функции полезности x y u(x) > u(y), значит, если x > y, то u(x) > u(y) ];

• предельные полезности товаров положительны (поскольку функция полезности является строго возрастающей и дифференцируемой, то u / xi > 0 );

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

• по мере увеличения потребления товара его предельная полезность уменьшается (первый закон Госсена):

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

На практике используются следующие конкретные функции полезно сти:

• мультипликативная:

• квадратичная:

где матрица B = (bij ) должна быть отрицательно определенной;

• пропорциональная:

где k1, k2, …, kn > 0 и др.

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

С геометрической точки зрения поверхность безразличия в простран стве n товаров представляет собой гиперповерхность (n – 1) го порядка.

В дифференциальной форме условие u(x) = u0 = const записывается так:

Г р а д и е н т функции полезности равен вектору предельных полезно стей:

Условие (14.1.2) означает, что градиент функции полезности перпенди кулярен касательной к поверхности безразличия (рис. 14.1.1).

Из рис. 14.1.1 видно, что снижение полезности, вызванное уменьшением количества одного товара, можно, вообще говоря, к о м п е н с и р о в а т ь увеличением количества другого товара. Рассмотрим некоторый набор товаров и предположим, что количество i го товара изменилось на величину dxi, количество j го товара изменилось на dxj, а все остальные товары оста лись в тех же количествах, что и раньше; новый набор товаров Рис. 14.1.1. Поверхность безразличия и градиент функции полезности Чтобы старый и новый наборы товаров оказались на одной поверхности безразличия, необходимо выполнение условия (14.1.2). Учтем, что dxk = при k i, k j, тогда получим, что откуда Величина называется предельной нормой замены i го товара j м; она показывает, на сколько е д и н и ц должно увеличиться количество j го товара, чтобы к о м п е н с и р о в а т ь потерю единицы i го товара (т. е. чтобы полез ность набора товаров не изменилась).

Часто бывает удобно иметь дело не с абсолютными величинами, а с о т н о с и т е л ь н ы м и. Эластичность замены i го товара j м ( eij ) пока зывает, на сколько п р о ц е н т о в должно увеличиться количество j го товара, чтобы компенсировать уменьшение количества i го товара на 1%:

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

Запишем эту задачу подробнее [с учетом (14.1.1)]:

ТЕОРЕМА СУЩЕСТВОВАНИЯ РЕШЕНИЯ ЗАДАЧИ ПОТРЕБИТЕЛЯ. Решение

задачи потребителя (14.1.3) существует и лежит на границе бюджет ного множества:

ТЕОРЕМА ЕДИНСТВЕННОСТИ РЕШЕНИЯ ЗАДАЧИ ПОТРЕБИТЕЛЯ. Если функция по лезности является строго выпуклой вверх, то решение задачи потре бителя (14.1.3) является единственным.

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