Задачи 4
Методом Лагранжа найдите условные локальные экстремумы следующих функций 4.1 – 4.6 и проверьте найденные экстремумы на глобальность:
4.1. при .
Ответ: – глобальный максимум.
4.2. при .
Ответ: – глобальный минимум.
4.3. при .
Ответ: (0;1) – локальный минимум; – локальный максимум;
глобальных экстремумов нет.
4.4. при .
Ответ: экстремумов нет.
4.5. при .
Ответ: (1; 1) – локальный минимум; (1; –1) – локальный максимум; глобальных
экстремумов нет.
4.6. при .
Ответ: (4; 2; – 4) – глобальный максимум; (– 4; –2; 4) – глобальный минимум.
Задача 5
Составьте математическую модель и найдите решение следующей задачи.
Фирма получила заказ на производство 9000 деталей. Для производства деталей фирме требуются ресурсы двух типов. Производственная функция имеет вид , где – количество единиц ресурсов соответствующего типа, – количество произведенных деталей. Одна единица ресурса первого типа стоит 2000 р., второго – 3000 р.
Методом Лагранжа с проверкой знакоопределенности окаймленного гессиана найдите оптимальный план приобретения ресурсов с минимальными расходами. Оцените по множителю Лагранжа, насколько увеличатся минимальные расходы фирмы на приобретение ресурсов, если заказ будет увеличен на одну деталь.
Убедитесь в глобальной оптимальности построенного плана, сведя задачу к одномерной.
Ответ: на р.
Задачи 6
Исследуйте на выпуклость – вогнутость функции 6.1 – 6.6:
6.1. ;
Ответ: выпукла и вогнута на (не строго).
6.2. ;
Ответ:выпукла и вогнута на (не строго).
6.3. ;
Ответ: строго выпукла на .
6.4. ;
Ответ: не выпукла и не вогнута ни на каком подмножестве с непустой
внутренностью.
6.5. ;
Ответ: выпукла на и вогнута на .
6.6. ;
Ответ: выпукла на (не строго).
Задачи 7
Убедитесь, что задачи 7.1 – 7.3 являются задачами выпуклого программирования, что для них выполняются условия Вейерштрасса и Слейтера, и найдите решения при помощи условий Куна-Таккера.
7.1. : ,
Ответ:
7.2. : , .
Ответ:
7.3.
Ответ:
Задача 8
Сформируйте задачу математического программирования, модифицировав экономическое содержание задачи 5 так, чтобы условие типа равенства заменилось бы на неравенство, а решение осталось бы прежним.
Проверьте выпуклость сформированной задачи. Выполняются ли для нее условия Вейерштрасса и Слейтера? Решение получите, воспользовавшись условими Куна-Таккера.
Ответ:
Задача 9
Распространите условия Куна-Таккера на случай двух прямых ограничений на сверху и снизу и одного непрямого ограничения:
если в функцию Лагранжа включены только непрямые ограничения:
и у нее существует седловая точка :
Условия Куна-Таккера получите как необходимые условия максимума функции по и минимума по в приведенном выше определении седловой точки.
Ответ:
Упражнения к теме 4
Задачи 1
Решите геометрически по схеме следующие задачи линейного программирования 1.1 – 1.7 или убедитесь в отсутствии решения, указав причину.
1.1. Ответ: нет решения.
1.2. Ответ: .
1.3. Ответ:
1.4. Ответ:
1.5. Ответ:
1.6. Ответ: нет решения.
1.7. Ответ:
Задачи 2
Приведите задачи линейного программирования 2.1 – 2.3 к стандартному и каноническому видам.
2.1. 2.2. 2.3.
Задачи 3
Для словесно сформулированных оптимизационных проблем 3.1 – 3.3 требуется:
а) формализовать проблему в виде задачи линейного программирования (ввести искомые переменные, записать таблицу исходных данных, написать в стандартном виде формулы для целевой функции и для ограничений – неравенств);
б) решить задачу геометрически, подтвердить геометрические решения аналитически вычислением координат найденной и соседних вершин, с последующей проверкой их допустимости и сравнением значений целевой функции;
в) градиентным анализом найти, при каком соотношении между коэффициентами целевой функции решение останется в той же вершине, что и для исходного варианта этих коэффициентов;
г) подтвердить полученное решение компьютерными расчетами симплекс-методом с помощью системы Microsoft Excel1) или ей подобной.
3.1. На заводе имеется запас олова и свинца в объеме 3 тонн и 5 тонн соответственно. Из этих металлов завод может изготовить два вида сплавов: с содержанием олова 30% и 50% (остальное свинец). Сплав первого вида завод может реализовать по цене 4200 р. за кг, второго – 6000 р. за кг. Требуется составить оптимальный план производства сплавов и вычислить максимальный доход.
(5т.;3т.), 39·106 р.
3.2. На рынке имеются два вида продуктов питания А и В, которые можно купить по ценам 240 р. и 300 р. за килограмм. В одном килограмме продукта А содержится 50 г питательного вещества М и 100 г питательного вещества N. Для продукта В соответствующие цифры составляют 100 и 100. Сколько требуется закупить продуктов А и В, чтобы общее количество питательных веществ М и N составляло не менее 4 кг. и 5 кг. соответственно, а расходы были минимальны? Вычислите также минимальные расходы.
(20 кг; 30 кг.), 13800 р.
3.3. Для производства сплава олова со свинцом заводу необходима ежедневная выработка не менее 3 т. олова и 5 т. свинца. Завод имеет возможность заключать договоры с двумя горнодобывающими фирмами. Первая фирма добывает руду, содержащую 5% олова и 10% свинца, и готова поставлять руду по цене 3600 р. за тонну. Вторая фирма добывает руду, содержащую 12% олова и 14% свинца, и готова поставлять руду по цене 5400 р. за тонну. Найдите оптимальный план закупок заводом руды в этих фирмах, минимизирующий стоимость закупки необходимого количества сырья и вычислите минимальную стоимость закупки.
Ответ: (36 т.; 10 т.), 18,36 тыс. р.
Задачи 4
Для словесно сформулированных ниже оптимизационных проблем 4.1, 4.2 необходимо:
а) выписать прямую и двойственную задачи линейного программирования и дать экономический комментарий двойственной задачи в духе п. 3.1;
б) геометрически решить задачу с двумя переменными, прямую или двойственную, а решение сопряженной задачи восстановить по соотношениям дополняющей нежесткости, проверив потом допустимость и оптимальность найденной пары решений;
в) определить пределы, в которых найденные значения двойственых переменных могут быть использованы для расчета влияния изменений объемов сырья на экстремальные значения целевой функции прямой задачи, и ответить на последний вопрос словесной формулировки.
4.1. У предприятия имеются запасы двух видов сырья: S1 и S2 в количествах 800 кг. и 1400 кг. Предприятие может изготавливать три вида продукции: Р1, Р2 и Р3. Затраты сырья S1 на один килограмм продукции разных видов составляют соответственно 4;2;1 кг., а сырья S2 – 2;6;4 кг. Продажная цена готовых изделий: 240; 420; 260 р./кг.. При планировании объемов производства максимизируется доход. Какое сырье выгодно докупить предприятию по цене 40 р./кг. для S1 и 50 р./кг. для S2 на сумму 100 р.
Ответ: (100 кг.; 200 кг.; 0), ; докупать S2.
4.2. Фирма по производству творожной пасты может выпускать два сорта пасты, используя три вида сырья – молоко, наполнители и специальные добавки. Затраты молока на один килограмм пасты первого вида составляют 0,15 кг., а второго вида – 0,75 кг. Затраты наполнителей на один килограмм пасты первого вида составляют 0,5 кг., а второго вида – 0,25 кг. Наконец, затраты добавок на один килограмм пасты первого вида составляют 0,35 кг., а при производстве второго вида пасты не используются. Запасы молока на фирме составляют 525 кг., наполнителей – 400 кг., добавок – 210 кг. Продажная цена 1 кг. первого вида пасты составляет 200 рублей, а второго вида – 300 рублей. Найти план производства, максимизирующий доход от продажи творожной пасты, и соответствующее значение дохода. Какое сырье выгодно докупить предприятию по цене 20 р./кг. для молока, 30 р./кг. для наполнителей и 50 р./кг. для добавок на сумму 1000 р.
Ответ: (500 кг.; 600 кг.),
;
докупать молоко.
Задачи 5
Решите следующие линейные целочисленные задачи 5.1, 5.2 графическим методом и методом ветвей и границ. Проверьте правильность решения с помощью компьютера.
5.1. Фирма, производящая дачные дома двух видов, решила прекратить свою деятельность. Однако у нее остался неизрасходованным строительный материал, в том числе, из наиболее ценного: 7,5 м3 бруса и 10 м3 вагонки. Фирма решила из оставшегося материала изготовить последнюю партию домов. Для постройки дома первого типа требуется 2 м3 бруса и 1 м3 вагонки. Для постройки дома второго типа требуется 1 м3 бруса и 2,5 м3 вагонки. Рыночная цена домов составляет 600 и 900 тысяч рублей соответственно. Определить оптимальный план использования остатков строительных материалов, обеспечивающий максимум дохода.
Ответ: план строительства (2;3), доход 3900 тыс. р.
5.2. Фирма по производству пластмассовых изделий арендовала помещение площадью 100 м2. Для производства продукции необходимо приобрести оборудование. Фирма выделила на эти цели 900 тыс. р. На рынке имеется два вида подходящего оборудования, которое может использоваться параллельно: стоимостью 90 тыс. р. и 150 тыс. р. за один экземпляр. Один экземпляр оборудования первого вида имеет производительность 2 т./сут. и занимает площадь 15 м2, а второго вида – имеет производительность 3 т./сут. и занимает площадь 18 м2. Определить оптимальный план закупки оборудования, максимизирующий его суммарную производительность.
Ответ: план закупки (3; 3), производительность 15 т./сут.
Упражнения к теме 5
Задача 1
Требуется оценить минимальное время, потребное для создания малого предприятия, по следующему исходному перечню работ.
Наименование работыВсе предшествующие работыПродолжительность работы : формирование устава
: анализ рынка
: регистрация предприятия
: получение кредита, аренда помещения и
приобретение оборудования
: реклама
: набор сотрудников
: заключение договоров–
_
,
, ,
, ,
, ,
Для этого нужно:
а) построить и проверить сетевой график (рекомендация – ввести условную связь – сигнал из состояния с выполненными работами , в состояние с выполненными работами , , );
б) задать числовые значения параметров . и найти минимальную продолжительность выполнения проекта методом критического пути и посредством формирования и решения задачи линейного программирования.
Ответ:
Задача 2
По схеме, указанной в задаче 1 найдите минимальную продолжительность строительства загородного дома со следующим исходным перечнем работ.
Наименование работыВсе предшествующие работыПродолжительность работы : выбор и корректировка проекта– : строительство фундамента : возведение стен и перекрытий , : строительство крыши с временной кровлей , , : монтаж электрооборудования , : организация водоснабжения и канализации , : теплофикация дома , , : укладка постоянной кровли на крыше , , : внутренняя отделка помещений ,
Помимо подробного сетевого графика, построенного для заданной таблицы, нарисуйте редуцированный граф. Убедитесь в совпадении результатов расчетов минимального времени выполнения проекта с использованием подробного и редуцированного графов.
Ответ:
Задача 3
На графе, построенном в задаче 2, замените продолжительности работ на пропускные способности дуг , характеризующие максимальное число работ, которые могут быть выполнены за единицу времени.
Для выбранных Вами чисел требуется определить максимальную интенсивность потока, который можно пропустить по построенной Вами сети из начальной вершины в конечную, если во всех вершинах соблюдается закон сохранения входящих и выходящих потоков.
Расчеты произведите тремя способами:
а) методом минимального разреза,
б) методом увеличивающей цепи,
в) сведением к задаче линейного программирования.
Упражнения к теме 6
Задачи 1
Решите с помощью процедуры Беллмана задачу динамического программирования при т.е.
с различными критериями качества управления 1.1 – 1.3.
1.1.
Ответ:
1.2.
Ответ:
1.3. фиксированный параметр, который для облегчения можно задать численно в трех характерных вариантах:
Ответ:
Дайте сравнительный экономический комментарий полученных решений.
Задача 2
Проблема «накопление – потребление» описывается динамической моделью в дискретном времени с безразмерными переменными:
Здесь x, y – фазовые координаты:
– капитал, накопленный к началу интервала
y(t) – нарастающий итог потребления к началу того же интервала,
u(t) – выбираемое управление: доля объема прибыли kx(t), направляемая на потребление за время
фиксированные параметры:
– процент на капитал,
– горизонт планирования.
Требуется: пользуясь уравнением Беллмана, построить программу распределения доходов, обеспечивающую максимум суммарного потребления при незаданной (оптимально выбираемой) конечной величине капитала для
Ответ:
Задача 3
а) Преобразуйте уравнения задачи 2 так, чтобы:
– на потребление можно было бы использовать не только прибыль и процент с капитала, но и сам капитал; при этом изъятие части капитала в объеме осуществляется в начале года t до начисления процентов;
– критерий оптимальности J сделать суммой пошаговых функций полезности, пропорциональных корню квадратному от годового потребления;
– в задаче оставить только одну фазовую координату и «объемное» управление вместо «долевого» , которое использовалось в задаче 2.
б) Решите полученную задачу методом динамического программирования с индивидуально назначенными числами , дайте экономический комментарий и сравните с «буквенным» ответом.
Ответ: а) формализация –
б) решение –
проверка:
Задача 4
Решите задачу 3 с измененным критерием:
Сравните решение с предыдущим, положив
Ответ:
Задача 5
а) Формализуйте в виде задачи динамического программирования следующую проблему оптимального вылова рыбы.
Рыбоводческое хозяйство изначально располагает в своих водоемах известным ему запасом рыбы x. Ежегодно на протяжении T лет оно решает вопрос о размерах u годового вылова рыбы и ее продажи, рассчитывая получать годовую прибыль К началу следующего года оставшееся количество рыбы прирастает до Хозяйство стремится максимизировать суммарную (за T лет) прибыль.
б) Выпишите и решите уравнение Беллмана для случая
Ответ: а) формализация –
б) решение –
Задача 6
Решите по общей схеме из п. 2.3 задачу о расплате предприятия за кредит в течение двух лет с годовым шагом по времени
(1)
Здесь
– основные производственные фонды развивающегося предприятия (безразмерная
фазовая координата);
– долг предприятия банку, начисляемый по правилу сложных процентов (безразмерная фазовая координата);
– объем выплат банку, произведенных предприятием с начала года 0 (нарастающий итог, безразмерная фазовая координата);
– годовые отчисления банку из прибыли предприятия (безразмерное управление; остаток прибыли идет на развитие предприятия);
– годовая рентабельность предприятия (постоянный заданный параметр);
k – годовой банковский процент (постоянный заданный параметр );
K – фиксированный размер кредита, взятого предприятием в банке в начале года 0 и мгновенно превращенный им в основные фонды (параметр );
l – доля минимальной промежуточной выплаты, устанавливаемая банком (фиксированный параметр ).
Для облегчения выкладок задайте численные значения параметров (индивидуальные) так, чтобы например,
Ответ:
Условия разрешимости:
Задача 7
Получите решение задачи 4, не прибегая к линейной свертке критериев, а ограничив снизу финишную величину капитала, т.е.
Ответ: при
Задача 8
Решите следующую задачу линейного программирования методом Беллмана:
предварительно сведя ее к динамической.
Ответ:
Упражнения к теме 7
Задача 1
Многим людям хочется заработать побольше денег и одновременно иметь как можно больше свободного времени .
Эти два противонаправленных критерия задаются в безразмерном виде как функции одного скалярного управления , выбираемого индивидуумом:
, ,
Здесь – доля рабочего времени от астрономического, – доля фактической сдельной заработной платы от максимально возможной на данной работе, – доля свободного времени от астрономического. Первый участок кусочно-непрерывной функции моделирует неоплачиваемые затраты времени на поездки к месту работы и обратно (все цифры здесь и далее – условные). Второй участок – основной: на нем заработная плата растет линейно по отработанному времени. Третий участок моделирует насыщение зарплаты на оговоренном уровне.
Остаток астрономического времени за вычетом рабочего считается свободным временем .
Требуется:
– изобразить множество достижимости на плоскости критериев , выразив
через ;
– выделить графически Парето-эффективное множество и найти его прообраз .
Ответ: ,
.
Задача 2
Выделите Парето-эффективное подмножество из конечного множества допустимых управлений , эффективность каждого из которых оценена экспертами по нескольким максимизируемым или минимизируемым показателям , с приведенными ниже вариантами значений 2.1–2.4.
2.1.
Ответ: .
2.2.
Ответ: .
2.3.
Ответ: .
Задача 3
Выделите недоминируемых кандидатов в президенты из пяти участников предвыборной кампании на основании следующих пятибалльных экспертных оценок по трем критериям:
Кандидат Привлекательность внутренней программы 53554Привлекательность внешней программы 52443Личная привлекательность кандидата 33445
Ответ: .
Задача 4
Сведите к задаче линейного программирования методом свертки критериев следующую проблему двухкритериального выбора.
Предприятие выпускает два вида продуктов в объемах . Первый продукт адсорбирующий, при его производстве поглощаются вредные отходы, образующиеся при выпуске второго, загрязняющего продукта. Уровень загрязнения окружающей среды определяется разностью в объемах их производства , а прибыль – суммой (все в безразмерных переменных). Руководство предприятия при планировании выпусков продуктов стремится уменьшить загрязнение и, вместе с тем, увеличить прибыль. Оба критерия приводятся к стандартной схеме максимизации посредством изменения знака у первого из них, так чтобы
Множество допустимых управлений задается ограничениями по производственным мощностям и условиями неотрицательности выпусков:
Первая мощность, составляющая 8 безразмерных единиц, используется для производства обоих продуктов. Две другие, в 7 и 6 единиц, специализированы по продуктам. Рынки сырья и готовой продукции считаются неограниченно емкими, ограничение по трудовым ресурсам даже при полной загрузке производственных мощностей считается выполненным.
Решите полученную задачу линейного программирования геометрически на критериальной плоскости , приняв во внимание, что при невырожденных линейных преобразованиях грани и вершины множества допустимости переходят в такое же число граней и вершин множества достижимости .
Ответ: .
Задача 5
Для заданных ниже вариантов 5.1, 5.2 континуальных множеств двухкомпонентных векторов допустимых управлений и вариантов критериев , требуется:
построить множество достижимости по аналитически заданному соответствию ;
геометрически выделить из множества подмножества эффективности, отметить его прообраз на плоскости управлений;
продублировать задание б) аналитически методом критериальных ограничений.
5.1.
Ответ:
5.2.
Ответ:
Задача 6
Потребитель решает, какую сумму денег из имеющихся ему потратить на сегодняшние покупки и как ее распределить между различными товарами, а какую сумму отложить на будущее. Предложение товаров считается неограниченным, а продажные цены – фиксированными.
Словесно представленная ситуация моделируется как двухкритериальная задача в безразмерных переменных:
где – максимизируемая полезность сегодняшнего потребления, – минимизируемая доля средств, истраченных на сегодняшние покупки ( – запас на будущее), – доля средств, потраченных на покупку товара вида
Требуется:
– построить множество достижимости , проверить его выпуклость и замкнутость;
– геометрически выделить его Парето-эффективную границу , не заменяя минимизируемый критерий на эквивалентный максимизируемый критерий;
– геометрическое решение подтвердить аналитически, максимизируя по методу Лагранжа линейную свертку критериев (п.2.2) ;
– определить, каким должен быть коэффициент для получения разных точек и участков паретовской границы ?
Ответ: .
Задача 7
Руководство региона готовит проект расходов регионального бюджета по двум укрупненным позициям:
– доля расходов на социальные нужды от общей суммы доходов,
– доля расходов на развитие инфраструктуры в пределах бюджетного ограничения:
.
По каждому из этих направлений экспертами определены минимально допустимые уровни расходов, а по инфраструктуре сформирован и максимальный уровень. Эти уровни приняты как обязательные для проекта бюджета:
.
Центральные органы оценивают региональный бюджет по критерию , а жители региона – по другому критерию того же вида, но с другими весовыми коэффициентами:
Руководство региона стремится максимизировать оба этих критерия и хочет формальными методами сузить множество рациональных решений .
Требуется:
записать множество допустимых решений аналитически в виде системы неравенств и представить его графически;
записать аналитически и изобразить множество достижимости на критериальной плоскости с учетом свойства, указанного в конце формулировки задачи 4;
графически выделить Парето-эффективную границу множества достижимости и показать ее прообраз на графике из задания а);
указать, при каких значениях весовых параметров , максимизация по линейной свертки критериев дает в качестве решения соответствующие угловые точки и отрезки паретовского множества (см. п.2.3);
графически найти идеальную точку , определенную в ( ), и графически на плоскости решить задачу о максимальной близости к идеалу по расстоянию
.
Рекомендация к этапу д): убедитесь, что на плоскости линии уровня минимизируемой функции представляют собой ромбы с центром в идеальной точке , вытянутые по оси или , и найдите точку соприкосновения самого маленького ромба с множеством достижимости .
Ответ:
•
•
•
в) вершины: x2 = (0,2; 0,1), x3 = (0,9; 0,1), x4 = (0,6; 0,4), x5 = (0,2; 0,4) и y2 = (0,16; 0,14), y3 = (0,58; 0,42), y4 = (0,52; 0,48), y5 = (0,28; 0,32); множество – ребро ; множество – ребро ;
г) ребро при = 0,5, = 0,5; вершина y3 при > 0,5, < 0,5; вершина y4 при < 0,5, > 0,5;
д) идеальная точка y1 = (0,58; 0,48), наименьшее расстояние = от вершины y4.
Задача 7
Докажите, что внутренние точки множества достижимости в критериальном пространстве не могут быть эффективными, т.е.
.
Постройте примеры, для которых прообразы эффективной точки принадлежат и не принадлежат границе множества допустимости в пространстве управлений .
Задача 8
Дайте определение и геометрическую интерпретацию Парето-эффективной границы для двух критериев, первый из которых максимизируется, а второй – минимизируется (без замены знака у второго критерия).
Задача 9
Все ли допустимые точки , в которых достигается абсолютный максимум по одного из максимизируемых критериев будут эффективными по нескольким критериям, т.е. обязательно ли
, если ?
Как соотносятся множества
и ?
Упражнения к теме 8
Задача 1
Торговая база составляет заявку производителю на поставку продукции, не зная точно будущего спроса своих потребителей. Предполагается, что фактическая поставка совпадает с планируемой по объему и производится однократно в оговоренный момент времени.
Заказанного объема продукции должно хватить, чтобы полностью удовлетворить спрос потребителей на всем периоде планирования, заканчивающегося в известный момент очередной поставки. Планируемый объем поставки должен быть кратен единичной грузоподъемности используемых однотипных транспортных средств и не может превышать емкости склада, составляющей 4 единицы.
К моменту составления заявки прогнозируется три ожидаемых варианта будущего спроса: низкий , средний и высокий , исчисляемые в тех же единицах, что и планируемая поставка и емкость склада.
Продажная и покупная цены продукции известны заранее. Издержками на хранение продукции и ее потерями при хранении пренебрегается.
База стремится к увеличению прибыли, придерживаясь принципа наилучшего гарантируемого результата.
Ожидаемая прибыль базы задается таблично:
0
1
2
3
4123–∞
2
1
0
–1–∞
–∞
4
3
2–∞
–∞
–∞
6
5
Символом –∞ помечены недопустимые для базы ситуации.
Требуется:
а) проверить условие разрешимости,
б) построить наилучшее гарантирующее решение с позиции базы.
Ответ: а)
б)
Задачи 2
На конечных множествах возможных стратегий управления и ожидаемых возмущений известны значения максимизируемого показателя качества (типа прибыли), заданные в виде матрицы . Строки матрицы отвечают номеру стратегии управления , а столбцы – номеру возмущения . Несобственное значение используется как признак недопустимости управления при каких-то возмущениях.
Для каждой из предложенных в 2.1 – 2.4 матриц требуется:
а) выбрать оптимальные гарантирующие стратегии и найти максимальный гарантированный результат ;
б) провести сопоставление с идеальным управлением , установить наличие или отсутствие седловой точки;
в) выбрать стратегии , предельно близкие к идеальным по наихудшим отклонениям в критерии, абсолютным и относительным ;
г) построить оптимистическое решение ;
д) выбрать оптимальную стратегию , руководствуясь принципом равновероятности возмущений.
Образец решения – задача уклонения от налогов.
1{2; 5}{2; 5} 0,70,80,9
б)
Ответ:а) = 4, = 0,6;
в) = 4 , = 4;
г) {2; 5}, = 3;
д) = 2.
2.1
664 0,30,60,9
б)
Ответ: а) {2; 5}, = 0,2;
в) {4, 5} , = 5;
г) 3, = 3;
д) = 4.
2.2
542 0,50,81
б)
Ответ: а) = 3, = 0,4;
в) = 5 , = 3;
г) 2, = 3;
д) = 5.
2.3
234 0,70,81
б)
Ответ: а) = 5, = 0,4;
в) = 5 , = 5;
г) 4, = 3;
д) = {3, 5}.
2.4
Задача 3
Фирма планирует объем своего производства в условиях неточного знания выпусков конкурирующего производства где . Объемы производств и измеряются в единицах переработки основного сырья, общие запасы которого ограничены: . Кроме того, выпуск ограничен сверху известной производственной мощностью фирмы .
Рентабельность фирмы линейно падает с ростом суммарного объема производства из-за падения цены на готовую продукцию с ростом предложения и увеличения цены на сырье с ростом спроса. Однако скорость падения будущей рентабельности неизвестна, она прогнозируется в диапазоне .
Фирма добивается увеличения своей прибыли
Требуется:
а) построить множество допустимых гарантирующих планов ;
б) конкретизировать условие разрешимости в классе гарантирующих планов;
в) найти максимальную гарантированную оценку прибыли и оптимальный гарантирующий план ;
г) сравнить аналитически и графически гарантирующий план с идеальным управлением по условиям разрешимости, а также по фактическим значениям прибыли и по ее гарантированным оценкам , , проверить наличие (или отсутствие) в задаче седловой точки.
Все этапы решения сопроводить экономическими комментариями.
Ответ:
а) , где – объем собственного производства, и – максимально возможные объемы собственного и конкурирующего производств;
б) ;
в) ,
где ,
– максимально возможная скорость падения рентабельности собственного производства;
г) , , ,
где ,
, и – фактические значения объема конкурирующего производства и скорость падения собственной рентабельности;
условия разрешимости совпадают с б);
есть седловая точка.
Задачи 4
Выбрать из шести возможных планов , соответствующих строкам матрицы , наилучшие вероятностно-гарантирующие планы для матричных задач 4.1–4.4 с указанными там вероятностями реализации возмущений (соответствуют столбцам матрицы ) и значениями надежности решения .
Сравнить максимальные вероятностно-гарантированные оценки критерия качества и максимальные гарантированные оценки , полученные в соответствующей задаче 2.1 －2.4. Может ли, и если может, то с какой вероятностью, реализоваться возмущение , при котором величина критерия окажется хуже, чем ?
4.1.
4.2.
4.3
4.4
Задача 5
Доказать, что для ограниченных снизу критериев их штрафное доопределение
(1)
ослабленное по сравнению с (3) из §2 ( вместо ), сводит задачу гарантирующего планирования (1),(2) из §1 с возмущаемым множеством планов к макс-мину на прямом произведении множеств , т.е. к задаче
. (2)
Рекомендация: по доопределению (1) построить функцию
и сравнить ее максимум с максимумом аналогичной функции для исходной задачи (1),(2) из §1.
Задача 6
Показать, что сужение множества ожидаемых возмущений или (и) расширение множества допустимости результирующего управления не сужают множества (1) из §1 гарантированно допустимых планов.
Упражнения к теме 9
Задачи 1
Для антагонистических игр, заданных в нормальной форме:
,
требуется:
а) найти седловые пары
или убедиться в их отсутствии посредством графического и аналитического отыскания точек пересечения
максимизирующей и минимизирующей стратегий:
;
б) при наличии седловой пары построить графики платежной функции в седловых сечениях
и ;
в) вычислить и сравнить между собой верхнюю и нижнюю цены игры, а также найти оптимальные гарантирующие стратегии
;
г) проверить наличие или отсутствие доминирующих стратегий
Проделайте указанные выше операции в следующих матричных играх 1.1 – 1.4, где
:
1.1.
Ответ:
1.2.
Ответ:
1.3.
Ответ:
1.4.
Ответ:
Проделайте то же для континуальных игр:
1.5. . Ответ:
1.6. . Ответ:
1.7. . Ответ:
1.8. . Ответ:
1.9. . Ответ:
Образцы решения
матричных задач типа 1.1. – 1.4.
При наличии седловой пары
В заданной платежной матрице
1 2 3
2
1
0
●
●
●
i
1 2 3
4
2
0
●
●
●
j
Рис. 10. Седловые сечения платежей
Проведенные мнемонические построения подкрепляются аналитически. Для этого выписываются теоретико - множественные
и
Это – множества пар одинаково упорядоченных координат всех точек максимумов платежей по и минимумов по , соответственно.
в случае его непустоты дает седловую пару, т.е. координаты элементов с двумя звездочками.
.
Результат сравнения: необходимое и достаточное условие существования седловой пары выполнено.
Доминирующих стратегий нет, так как
При отсутствии седловой пары
В заданной платежной матрице
после разметки ее максимальных элементов во всех столбцах звездочками вверху справа и минимальных во всех строках звездочками внизу справа элементов с двумя звездочками не оказывается.
Это означает, что
Результат сравнения: – седловой пары действительно нет.
Доминирующих стратегий тоже нет, поскольку максимизирующая и минимизирующая стратегии не постоянны.
Образец решения
континуальных задач типа 1.5 – 1.9.
Задана платежная функция и множества допустимых выборов сторон, одна из которых стремится максимизировать по , а другая – минимизировать по :
Строятся функции максимумов по при всевозможных фиксированных значениях переменной :
и соответствующая
Строятся также функции минимумов платежа по при всевозможных фиксированных значениях переменной :
и соответствующая минимизирующая стратегия
1
●
●
x
1
0.5
0
0
Рис.12. Пересечение графиков оптимальных стратегий
Ищется точка пересечения графиков оптимальных стратегий : так как (других точек пересечения нет – см. рис.12). Найденная пара по определению – седловая, так как
(см. рис.13).
Рис. 13. Седловые сечения платежной функции
Для проверки вычисляются и сравниваются между собой верхняя и нижняя цены игры:
Результат сравнения: подтверждает существование седловой пары.
Доминирующие стратегии отсутствуют, так как значения функций и не постоянны.
Задача 2
Докажите эквивалентность двух форм записи в определении седловой точки
1)
и
2) .
Задача 3
Пусть игра имеет цену
Всякая ли точка , в которой будет седловой в смысле определения 1) или 2) из задачи 2 ? Если нет, то приведите пример.
Задача 4
Пусть некоторая игра имеет две несовпадающие седловые пары и
, . Докажите, пользуясь определением 2) из задачи 2, что перемешанные пары и тоже будут седловыми для этой игры, и что значения платежной функции на всех четырех парах одинаковы.
Задача 5
Пусть платежная функция имеет седловую точку на множестве Докажите, что тогда стратегии будут оптимальными гарантирующими.
Верно ли обратное? Если нет, то приведите соответствующий пример антагонистической матричной игры, не имеющей седловой точки.
Задача 6 – А.В. Соколов
Постройте платежную биматрицу для следующей игры «пассажир – железная дорога» с непротивоположными интересами.
Пассажир выбирает один из двух вариантов своего поведения: – купить билет, – не покупать билета. У железной дороги также имеются две возможности действий: – выставлять контролера на линию, – не выставлять.
Стоимость билета 20 р. Величина штрафа за безбилетный проезд 100 р. Средняя стоимость проверки одного пассажира контролером (купившего билет или не купившего) 10 р. Выигрыш пассажира – минус истраченная сумма. Выигрыш железной дороги – доход от продажи билета или сумма штрафа за вычетом расходов на проверку.
Требуется найти в чистых стратегиях (или установить, что они не существуют):
а) оптимальные гарантирующие стратегии и максимальные гарантированные выигрыши;
б) доминирующие стратегии;
в) точки равновесия по Нэшу;
г) парето-оптимальные индивидуально приемлемые точки.
Ответ: а)
б) нет;
в) нет;
г)
Задача 7
В следующих играх двух лиц с непротивоположными интересами, заданных биматрицами 7.1 – 7.6, требуется найти в чистых стратегиях (или установить, что они не существуют):
а) оптимальные гарантирующие стратегии и максимальные гарантированные выигрыши;
б) доминирующие стратегии;
в) точки равновесия по Нэшу;
г) парето-оптимальные индивидуально приемлемые точки.
В биматрицах 7.1 – 7.6 первая цифра каждого элемента, заключенного в круглые скобки, означает выигрыш стороны, распоряжающейся строками , а вторая цифра – выигрыш стороны, распоряжающейся столбцами .
Задачи 8
В антагонистических играх с платежными матрицами А , заданными в 8.1 – 8.4:
требуется:
а) исключить, если это возможно, доминируемые стратегии-константы , определяемые как
(исключение нужно производить последовательно, проверяя условия доминирования на невычеркнутых строках и столбцах);
б) для редуцированной таким образом матрицы с недоминируемыми строками и столбцами найти седловые точки в чистых стратегиях:
или убедиться в их отсутствии;
в) найти верхнюю и нижнюю цены игры в чистых стратегиях:
и сравнить их между собой;
г) проверить, что седловые точки в случае их существования будут таковыми и для исходной матрицы и что цены игры также сохранятся;
д) для редуцированной матрицы найти седловые точки и цену игры в смешанных стратегиях:
,
где
,
путем решения пары задач линейного программирования,
прямой: и двойственной:
или в координатной записи через относительные переменные при :
так что
;
е) переписать найденные оптимальные смешанные стратегии в исходных вероятностях для полноразмерной матрицы .
.
Образец решения
задач типа 8.1 – 8.4
а) Доминирование в исходной матрице:
Стрелками, начинающимися у доминирующих столбцов и строк, нужно указать доминируемые ими столбцы и строки. Доминирование обнаруживается попарным сравнением соответствующих элементов всех столбцов и строк при последовательном удалении (вычеркивании) доминируемых столбцов и строк, найденных ранее.
Редуцированная матрица составляется из недоминируемых строк и столбцов исходной матрицы:
.
б) Производится разметка звездочками максимальных по : и минимальных по : элементов редуцированной матрицы . Элементов с двумя звездочками в матрице не оказалось, значит седловой точки в чистых стратегиях нет.
в) По этой причине верхняя и нижняя цены игры в чистых стратегиях для матрицы не должны совпадать:
– для .
– для .
г) Для исходной матрицы эти несовпадающие цены сохраняются:
поэтому для нее седловой точки в чистых стратегиях тоже нет.
д) По редуцированной матрице выписывается формула для математического ожидания платежа в смешанных стратегиях :
где – допустимые вероятности использования строк и столбцов матрицы .
Оптимальные вероятности в в долях от неизвестной пока цены игры в смешанных стратегиях:
,
отыскиваются в результате решения пары сопряженных задач линейного программирования.
Сравнение с другими вершинами:
.
1
0
1
Аналитическое решение:
сравнение с другими вершинами:
Двойственная задача Аналитическое решение
(рис.15):
1
0
1
|
