При выполнении домашнего задания, посвященного решению задачи линейного программирования, требуется использовать компьютерную программу, которая позволяет проводить анализ чувствительности. В частности, рекомендуется использовать оптимизатор MS Excel.
Оценочные средства для текущего контроля и аттестации студента
Тематика заданий текущего контроля
Домашняя работа на тему
«Линейные оптимизационные модели и линейное программирование»
Задача. На изготовление двух видов продукции Р 1 и Р 2 требуется три вида сырья S 1, S 2, S 3. Запасы каждого вида сырья ограничены и составляют соответственно b 1, b 2, и b 3 условных массовых единиц. При принятой технологии количество сырья Pj, необходимое для производства единицы продукции Si, известно (см. табл. 1).
Таблица 1
| Сырье | Продукция | Запасы сырья | |
| P 1 | P 2 | ||
| S 1 | a 11 | a 12 | b 1 |
| S 2 | a 21 | a 22 | b 2 |
| S 3 | a 31 | a 32 | b 3 |
| Прибыль | c 1 | c 2 |
В последней строке таблицы сj - значения прибыли (в условных денежных единицах), получаемой предприятием от реализации единицы каждого вида продукции. Требуется составить такой план выпуска продукции видов P 1 и P 2, при котором суммарная прибыль от реализации всей продукции была бы максимальной.
Значения параметров задачи вычислить по формулам:
,
где n – последняя цифра номера группы студента. Значения 
и 
приведены в табл.2, где m – номер студента в списке группы (узнать у преподавателя).
Содержание работы
1. Составить математическую модель планирования производства, записав соответствующую задачу линейного программирования в стандартном виде (1 балл). Указать смысл всех используемых обозначений и математических выражений (2 балла).
2. Записать задачу линейного программирования в каноническом виде (2 балла).
3. Изобразить графически множество допустимых планов для задачи, записанной в стандартном виде (3 балла).
4. Составить таблицу соответствия вершин многоугольника допустимых планов для задачи в стандартном виде и точек допустимого множества задачи, записанной в каноническом виде (5 баллов).
5. Найти графическим методом оптимальный план выпуска продукции (3 балла).
6. Провести анализ чувствительности в отдельности для каждого из параметров b 1, b 2, b 3: построить графики зависимостей f *(bi), i = 1,2,3, для всего диапазона возможных значений bi - интервала [0, +∞) (9 баллов); найти их угловые коэффициенты, дать им экономическую интерпретацию в терминах решаемой задачи (3 балла).
7. Провести анализ чувствительности в отдельности для каждого из параметров с 1, с 2: построить графики зависимостей f *(сj), j = 1,2, для всего диапазона возможных значений сj - интервала [0, +∞) (6 баллов).
8. Записать двойственную задачу и решить ее аналитически (3 балла). Пояснить полученные результаты с использованием графиков f *(bi) (2 балла).
9. Найти графическим методом оптимальный план при условии целочисленности количеств выпускаемой продукции (привести отдельный рисунок) (3 балла).
10. Решить задачу линейного программирования (в непрерывной и целочисленной постановках) на компьютере с использованием программы Microsoft Excel. Привести распечатку полученных решений, сравнить их с полученными вручную и сделать вывод (4 балла). Распечатать отчеты по результатам, устойчивости и пределам (для непрерывной постановки) и объяснить смысл всех содержащихся в них данных (4 балла)
Вопросы для оценки качества освоения дисциплины
Теоретические вопросы
Тема I
1. Что такое инструментальные переменные и параметры математической модели? В чем состоит их отличие?
2. Что такое допустимое множество?
3. Что такое критерий оптимизации и целевая функция?
4. Что такое линии уровня целевой функции?
5. Дайте формулировку детерминированной статической задачи оптимизации.
6. Назовите причины неопределенности в параметрах математической модели и объясните ее влияние на решение.
7. Приведите примеры использования математических моделей для описания поведения экономических агентов.
8. Что такое рациональное поведение с точки зрения теории оптимизации?
9. Как методы оптимизации используются при принятии экономических решений?
10. Расскажите об использовании оптимизации в задачах идентификации параметров математических моделей.
11. Что такое глобальный максимум критерия и оптимальное решение?
12. Достаточное условие существования глобального максимума (теорема Вейерштрасса).
13. Назовите причины отсутствия оптимального решения.
14. Что такое локальный максимум?
Тема II
15. Сформулируйте общую задачу нелинейного программирования.
16. Сформулируйте необходимое условие локального максимума в общей задаче нелинейного программирования.
17. Что такое функция Лагранжа?
18. Дайте определение седловой точки функции Лагранжа.
19. Сформулируйте и докажите достаточное условие оптимальности с помощью функции Лагранжа.
20. Сформулируйте условие дополняющей нежесткости и дайте его экономическую интерпретацию.
21. Дайте определение выпуклого множества.
22. Какие свойства имеют выпуклые множества?
23. Дайте определение опорной гиперплоскости.
24. Дайте определение разделяющей гиперплоскости.
25. Сформулируйте и проиллюстрируйте теорему об отделимости выпуклых множеств.
26. Сформулируйте понятие выпуклой и вогнутой функций.
27. Что такое строгая выпуклость функции?
28. Что такое надграфик функции? Какими свойствами обладает надграфик выпуклой функции?
29. Сформулируйте достаточное условие выпуклости функции.
30. Какие свойства имеют выпуклые функции?
31. Сформулируйте выпуклую задачу нелинейного программирования.
32. Сформулируйте теорему о глобальном максимуме в выпуклом случае.
33. Приведите содержательный пример выпуклой задачи нелинейного программирования.
34. Сформулируйте теорему Куна-Таккера.
35. Дайте экономическую интерпретацию множителей Лагранжа.
36. Как решения выпуклой задачи оптимизации зависят от параметров?
Тема III
37. Сформулируйте задачу линейного программирования.
38. Приведите содержательные примеры задачи линейного программирования.
39. Что такое нормальная (стандартная) и каноническая формы задачи линейного программирования?
40. Какие свойства имеет допустимое множество задачи линейного программирования?
41. Какие свойства имеет оптимальное решение в задаче линейного программирования?
42. Как выглядят функция Лагранжа и условия Куна-Таккера в задаче линейного программирования?
43. Сформулируйте двойственную задачу линейного программирования.
44. Сформулируйте теоремы двойственности в задаче линейного программирования.
45. Дайте интерпретацию двойственных переменных в задаче линейного программирования.
46. Расскажите об анализе чувствительности в задаче линейного программирования.
47. Примените графический метод для решения конкретной задачи линейного программирования.
48. В чем состоят методы решения задач линейного программирования, основанные на направленном переборе вершин (симплекс-метод и др.)?
49. Какие возможности предоставляет среда MS Excel для решения задач линейного программирования?
50. В чем состоят градиентные методы решения задачи безусловной оптимизации?
51. Как штрафные функции используются при поиске решения выпуклой задачи нелинейного программирования?
52. Расскажите о методах решения задач линейного программирования, основанных на применении штрафных функций.
Тема IV
53. Сформулируйте задачу выбора решений в условиях неопределенности.
54. Назовите и сформулируйте критерии выбора решений в условиях неопределенности (принцип гарантированного результата, критерий Гурвица, критерий Байеса-Лапласа, критерий Сэвиджа).
55. Как определяется множество допустимых гарантирующих программ?
56. Что такое наилучшая гарантирующая программа?
57. Как используется вероятностная информация о параметрах в задачах принятия решений при случайных параметрах.
58. В чем состоит принятие решений на основе математического ожидания?
59. Как учитывается склонность к риску?
Тема V
60. Сформулируйте постановку задачи многокритериальной оптимизации.
61. Что такое множество достижимых критериальных векторов?
62. Дайте определение доминирования и оптимальности по Парето.
63. Что такое эффективные решения и паретова граница.
64. Назовите основные подходы к построению методов поиска решений в задачах многокритериальной оптимизации.
Тема VI
65. Приведите примеры многошаговых систем в экономике.
66. В чем состоят особенности динамических задач оптимизации?
67. Приведите примеры динамической задачи оптимизации.
68. Что такое многошаговые динамические модели?
69. Что такое непрерывные динамические модели?
70. Что такое управление и переменная состояния в динамических моделях?
71. Приведите примеры задания критерия в динамических задачах оптимизации.
72. В чем состоит метод динамического программирования в многошаговых задачах оптимизации?
73. Сформулируйте принцип оптимальности и запишите уравнение Беллмана.
74. Как задача оптимизации многошаговой системы сводится к задаче математического программирования?
Упражнения по курсу
«Методы оптимальных решений»
Основные понятия
1. Изобразить линии уровня 
следующих функций для указанных констант С. Рассчитать величину градиента в общем виде и найти его значения в указанных точках 
. Изобразить найденные градиенты в виде векторов, исходящих из заданных точек.
а) 
при С = 0; 1; 4, M1 = (1;–2), M2 = (2; –2), M3 = (–1; –2);
б) 
при С = 0; 1; –1, M1 = (0;0), M2 = (0;1), M3 = (1;1), M4 = (–1; –1), M5 = (1; –1);
в) 
при С = 0; 5; –5, M1 = (0;0), M2 = (1;1), M3 = (–1; –1);
г) 
при С = 0; 1; –1, M1 = (0;0), M2 = (
;2), M3 = (π; –1).
2. Найти градиент и производную по направлению 
заданной функции в точке 
. Для задачи а) изобразить вектор и градиент заданной функции в указанной точке.
Указание: все векторы следует изображать исходящими из заданной точки .
а) 
; 
; 
;
б) 
; 
; ; 
;
в) 
, М (2;1;0), 
.
3. В следующих задачах изобразить множество допустимых решений и проверить выполнение условий теоремы Вейерштрасса о существовании глобального максимума. Если теорема Вейерштрасса не применима, указать, какие условия не выполняются. Определить, существует ли решение задачи.
а) 
; б) 
;
в) 
; г) 
;
д) 
; е) 
.
4. Прибыль некоторой фирмы, производящей единственный товар, задается функцией
f (p, x)= p x – g(x),
где p – цена товара, устанавливаемая фирмой, x –количество проданного товара, зависящее от цены, g(x) – затраты на производство и транспортировку товара, которые будем считать пропорциональными x с некоторым положительным коэффициентом c. Заранее известно, что p ≥ pmin > 0, где pmin -- заданное число.
Рассмотрите описанные ниже ситуации и составьте их математические модели. Изобразите графики функций x(p) и f(p, x(p)). Выполняются ли условия теоремы Вейерштрасса? Существует ли цена, являющаяся решением задачи максимизации прибыли фирмы? Если решение не существует, назовите причину этого.
а) Фирма является монополистом, причем объем продаж x определяется функцией x(p)= b/p, где b>0.
б) Фирма выходит с произведенным товаром на рынок, на котором есть такая установившаяся цена p0, что
p0 > c ≥ pmin. Пусть объем продаж фирмы определяется назначаемой ею ценой p следующим образом
x = 0 при p > p0;
x = 0.1 b/p0 при p = p0;
x = b/p при pmin ≤ p < p0.
в) В случае зависимости продаж от цены, описанной в ситуации б), фирма решила, что цена на ее продукцию должна быть строго меньше p0.
г) Пусть в случае зависимости продаж от цены, описанной в ситуации б), имеет место pmin≤p0 < c, а фирма не может существовать при неположительной прибыли.
д) Пусть в случае зависимости продаж от цены, описанной в ситуации б), имеет место pmin≤p0 < c, а фирма не может производить товар при отрицательной прибыли.
5. Найти все локальные экстремумы следующих функций. Существует ли глобальный экстремум данной функции на всем множестве ее определения? Если да, найти его. Ответ обосновать.
а) 
;
б) 
;
в) 
;
г);
д) 
;
е) 
;
ж).
6. Методом Лагранжа найти локальные условные экстремумы следующих функций. Определить, выполняются ли в данных задачах условия теоремы Вейерштрасса. Найти глобальные экстремумы, если они существуют, или обосновать их отсутствие. Оценить, насколько изменятся значения функций в точках экстремума, если константы в правых частях условий связи увеличатся на 0,01.
а) при условии;
б) 
при 
;
в) 
при 
.
7. Фирма получила заказ на производство 2700 деталей по цене 10 тыс. рублей за штуку. Для выполнения заказа требуются ресурсы двух видов А и В. При полном расходовании х единиц ресурса А и у единиц ресурса В можно изготовить 
деталей. Рыночная цена единицы ресурса А составляет 1 тыс. рублей, единицы ресурса В – 27 тыс. рублей. Определить оптимальный план приобретения ресурсов (т.е. величины х и у) и прибыль от выполнения заказа. Оценить, насколько изменится прибыль при оптимальном приобретении ресурсов, если размер заказа увеличится на одну деталь. Издержками считать затраты на приобретение ресурсов.
8. Предприятие производит продукцию двух видов: А и В. Производство х единиц продукции вида А обходится предприятию в 
тыс. рублей, а производство у единиц продукции вида В – в 
тыс. рублей. Цена единицы продукции вида А на рынке составляет 4 тыс. рублей, а продукции вида В - 2 тыс. рублей. Определить оптимальный план производства (т.е. найти оптимальные значения х и у) и прибыль при условии, что предприятие затратило на приобретение ресурсов для производства указанных видов продукции 2340 тыс. рублей. Оценить, насколько изменится прибыль при оптимальном планировании производства, если затраты увеличить на 1 тыс. рублей. Издержками считать затраты на производство.