Контрольная работа по дисциплине «Методы оптимальных решений»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФГБОУ ВПО

Финансовый университет при Правительстве РФ

 

Кафедра математика и информатика

 

 

Факультет: заочный факультет экономики

Специальность: бакалавр экономики

 

 

Контрольная работа

По дисциплине «Методы оптимальных решений»

Вариант 4

 

 

 

Выполнила Рябова Виктория Константиновна

Студент 2 курса

Группа вечерняя

Личное дело № 100.06/120024

Преподаватель: Горбатенко Е.Н.

 

 

 

 

 

 

 

 

 

 

 

 

Владимир 2014

Контрольная работа

Вариант 4

Задание 1. Методы нелинейной и дискретной оптимизации.

Задача (модель) нелинейного программирования (ЗНЛП) формулируется так же, как и общая задача оптимального программирования со следующими требованиями к целевой функции (ЦФ) и допустимой области: ЦФ f(х1, х2, ..., хn) и (или) одна из функций gi (x1, х2, ..., хn) являются нелинейными:

min(max) f(x1, x2, …, xn)

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

При решении управленческих задач модель НЛП дает существенно меньше информации, чем ЗЛП.

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

 

Пример 1

Предприятие располагает двумя способами производства данного вида продукции. В течении рассматриваемого периода времени необходимый объем продукции равен В=Х1+Х2, где Х1 и Х2 – объемы производства по соответствующему технологическому способу. Затраты производства S при каждом способе зависят от объемов нелинейно:

S(Х1) = с0 + с1Х1 + с2Х12, с0, с1, с2 >0,

S(Х2) = p0 + p1Х2 + p2Х22, p0, p1, p2 >0.

Необходимо так распределить объем производства между технологическими способами, чтобы минимизировать общие затраты производства. Данные для расчетов: p0 =5, p1 =1, p2 =2; B=100; с0=3, с1=2, с2=1

Экономико-математическая модель

min f(Х1, Х2 ) = 2 Х1 + Х1 2 + Х2 +2 Х2 2 +8

Х1+Х2 =100

Решение

        Данная задача  является типичным примером простой  ЗНЛП с линейными ограничениями  и нелинейной целевой функцией. Рабочий лист может быть подготовлен в виде, представленном на рис. 1.1 – 1.2, формулы этого листа приведены в ячейках.

Рис. 1.1. Ввод целевой функции в ячейку E4 рабочего файла.

Рис 1.2. Ввод ограничения в ячейку В6 рабочего файла.

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

Рис. 1.3

В Параметрах галочка у строки Линейная модель не ставится (Рис. 1.4)

Рис 1.4

Реализуя приведенную модель средствами MS Excel (рис. 1.5), будем иметь:

Х1 = 66,5, Х2 = 33,5

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

Рис 1.5

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

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

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

Решение задачи НЛП (реализация модели нелинейной оптимизации) средствами Excel отличается от решения ЗЛП следующим:

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

В Excel признаком достижения оптимума является величина относительного приращения ЦФ на каждой итерации  . Оптимум считается достигнутым, если выполняется условие Δfk ≤ Δfзад, где Δfзад - точность, назначаемая при решении задачи (Параметры).

Примером задачи НЛП является модель оптимального формирования портфеля ценных бумаг (модель Марковица минимального риска).

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

xj,   - доля капитала, потраченная на покупку ценных бумагу j-го вида (весь выделенный капитал принимается за 1);

mj — средняя ожидаемая доходность j-й ценной бумаги,   (mj называют эффективностью j-й ценной бумаги);

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

В предположении о некоррелированности ценных бумаг (их независимости) модель Марковица имеет вид:

Найти xj,   , минимизирующие риск портфеля ценных бумаг

 (1)

при условии, что обеспечивается заданное значение эффективности портфеля mp, т.е.

 (2)

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

 (3)

 (4)

В модели (1)-(4) нелинейной является ЦФ.

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

min(max) f(x1, x2, …, xn)

xj - целые неотрицательные 

Если множество индексов   = {1, 2, ..., n}, то задачу называют полностью целочисленной, если  , то - частично целочисленной.

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

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

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

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

Пример 2. Задача оптимального формирования портфеля ценных бумаг. Необходимо сформировать оптимальный портфель Марковица (минимального риска) трех ценных бумаг с эффективностями и рисками: (4, 10), (10, 40), (40, 80). Нижняя граница доходности портфеля задана равной 15.

Экономико-математическая модель

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

4x1 + 10x2 + 40х3 ≥ 15

x1 + x2 + x3 = 1

xj ≥ 0, j = 1, 2, 3.

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

Рис. 1.6. Рабочий лист

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

Рис. 1.7. Диалоговое окно

Реализуя приведенную модель средствами ППП Excel (рис. 1.8), будем иметь оптимальный портфель Марковица:

x1 = 0,5213, х2 = 0,2078, х3 = 0,2709,

т.е. доли ценных бумаг оказались равными 52,13 %; 20,78 % и 27,09 %. При этом минимальный риск - 23,79, доходность портфеля оказалась равной заданной - 15.

Рис. 1.8. Результаты решения

 

Задание 2. Решите графическим методом типовую задачу оптимизации.

Осуществите проверку правильности решения с помощью средств

MS Excel (надстройка Поиск решения).

Фермер планирует засеять кукурузой и соей 400 га земли. Затраты на сев и уборку кукурузы составят 200 ден. ед./га, сои –100 ден. ед./га. На покрытие расходов, связанных с севом и уборкой урожая, фермер получил кредит в размере 60 тыс. ден. ед. Фермер планирует получить: кукурузы – 30 ц/га, сои – 60 ц/га. Фермер заключил договор на продажу кукурузы по 3 ден. ед./ц и сои по 6 ден. ед./ц. Однако согласно данному договору он обязан хранить убранное зерно в течение нескольких месяцев на складе, максимальная вместимость которого – 21 тыс. ц.

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

 

 

Экономико-математическая модель

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

Целевая функция будет иметь вид:

max f(Х1, Х2 )= 90Х1 + 360Х2    

        При ограничениях:

Х1+Х2 <400

200Х1 + 100Х2 ≤ 60000

30Х1 + 60Х2 ≤ 21000

 

      Решение (графический метод)

Рассчитаем данные для ограничений

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Построим график

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

т. А (0;350) – ЦФ = 126000

т. B (100;300) – ЦФ = 117000

т. C (200;200) – ЦФ = 90000

т. E (300;0) – ЦФ = 27000

т. О (0;0) – ЦФ = 0

 

Так как по условию задачи целевая функция стремится к максимуму, то оптимальным решением задачи будет Х1  =0, Х2 =350, т.е. 0 га кукурузы и 350 га сои.

Проверка правильности решения с помощью средств MS Excel (надстройка Поиск решения)

Рабочий лист может быть подготовлен в виде, представленном на рис. 2.1 – 2.3, формулы этого листа приведены в ячейках.

Рис 2.1. Пример оформления задачи в среде MS Excel.

 

 

Рис. 2.2. Ввод формулы целевой функции.

 

 

Рис. 2.3. Копирование формулы целевой функции в ячейки F9:F11.

 

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

Рис 2.4

 

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

Реализуя приведенную модель средствами MS Excel (рис. 2.5), будем иметь:

Х1 = 0, Х2 = 350

Рис. 2.5. Результат решения задачи средствами MS Excel.

 

 

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

Торговая компания собирается приобрести новый товар – комплекты постельного белья. Ожидаемая потребность – 800 единиц в месяц. Товар можно приобрести у поставщика. Стоимость заказа – 150 руб., годовая стоимость хранения единицы товара – 6 руб. Доставка товара осуществляется в течение двух дней. Компания работает 300 дней в году.

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

а) годовые расходы на хранение запасов;

б) период поставок;

в) точку заказа.

 

Решение:

Дано:

Т = 300 р.д./год

М= 800 ед/мес (9600 ед/год)

h = 6 руб/год

k = 150 руб /заказ

t = 2 дня

 

 

 

Qопт = = ≈ 693 комплекта

а) Z1 (Q) = + = + = 4157руб./год

б) период поставок: = = 0,072 года

в) точка заказа: х= = = 64 комплекта

Ответ: объем заказа, минимизирующий общие годовые расходы компании составляет 693 комплекта, годовые расходы на хранение запасов составляют 4157 рублей в год, период поставок – 0,072 года (примерно каждые 25-26 дней), точка заказа – 64 комплекта.

 

 

 

 

 

Задание 4

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