Линейное программирование. 4

Федеральное государственное образовательное бюджетное учреждение

высшего профессионального образования

«ФИНАНСОВЫЙ УНИВЕРСИТЕТ ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ»

Уфимский филиал

 

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

 

 

 

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

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

Вариант 3

                                       

 

 

                                      

 

 Студента Никулиной А.И.

Курс 2 Группа 12БЭ

Зачетная книжка №100.28/120023

Преподаватель Хусаинова З.Ф.

 

 

Содержание:

Задание 1 Методы линейного программирования (ЛП), двойственность в ЛП ………………………………………………………………..	2
Задание 2……………………………………………………………	10
Задание 3……………………………………………………………	12
Задание 4…………………………………………………………….	15
Задание 5…………………………………………………………….	18
Список литературы…………………………………………………	22

 

 

 

Задание 1

Методы линейного программирования (ЛП), двойственность в ЛП

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

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

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

Для откорма крупно рогатого скота используют два вида кормов: b1, b2, в которых питательные вещества а1,а2,а3,а4. Содержание количества единиц питательных веществ в 1 кг каждого корма, стоимость  1 кг корма и содержание питательных веществ в рационе животного представлены в таблице 1. Составьте рацион  при условии минимальной стоимости.

 

 

 

 

Таблица 1

Питательные вещества	Виды кормов		Норма содержание питательных веществ
	b1	b2
а1	3	4	24
а2	1	2	18
а3	4	0	20
а4	0	1	6
Стоимость 1кг корма, руб	1	2

 

Решение какой-либо задачи управления можно разбить на несколько этапов:

1. формулировка задачи;

2. разработка математической модели изучаемой системы;

3. выбор метода и отыскание решения с помощью этой модели;

4. проверка решения.

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

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

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

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

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

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

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

Пусть с -матрица размера n х m и b . Задачу , называют общей задачей линейного программирования.

В терминах общей постановки здесь f(x)= и f(x)= в противном случае.

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

, y*,

где y (т.е. , y*, ).

Итак, применим преобразование Лежандра

F*(x*, y*)= =

  =

= =

Далее преобразуем неравенство в уравнение, подставив новую переменную z. Получим , где z . Теперь произведем замену переменных, вместо y подставим формулу .

 

Раскрыв скобки, совершив преобразования, получим

 

Если 0 и хотя бы один |y*| x, z будет равен . Если y*=0, то максимум по будет равен . Если 0 и хотя бы один |y*| .

Поэтому

Теперь выделим конечные значения :

Упростим

И тогда получим

Таким образом, получаем двойственную задачу:

 

arg max , ,

 

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

F=c1x1+c2x2+…cnxn

при условиях

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

1. Целевая функция исходной задачи задается на минимум, а целевая функция двойственной на максимум.

2. Матрица

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

 

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

3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной задаче.

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

5. Если переменная xj исходной задачи может принимать только лишь положительные значения, то j-е условие в системе двойственной задачи является неравенством вида «>». Если же переменная xj может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i – соотношение в системе исходной задачи является неравенством, то i-я переменная двойственной задачи . В противном случае переменная уj может принимать как положительные, так и отрицательные значения.

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

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

Рис. 6

 

Отобразим ограничения в математической модели на графике (Рис. 6):

             1 -              4 - 

                2 -                5 - 

                3 -                        6 -          F - F=2X1+X2®min                                         

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

Параллельно двигаем прямую F, соответствующую целевой функции. Первой вершиной, через которую пройдет прямая, при выходе за границу многоугольника, будет вершина A(6;6)(Рис.6):. Именно в ней достигнет своего минимального значения.

=6;

=6;

Подставляем значения в формулу:

     2*6+6=18.

Для эффективного откорма крупно рогатого скота необходимо 6 корма b1 и 6 корма b2  . При этом затраты минимальны и составят 18 руб.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание 2

Фирма выпускает два вида комплексных удобрений для газонов в упаковке – обычное и улучшенное. Обычное удобрение стоит 3 ден. ед./уп. и включает 3 кг азотных, 4 кг фосфорных и 1 кг калийных удобрений. Улучшенное удобрение стоит 4 ден. ед./уп. И включает 2 кг азотных, 6 кг фосфорных и 3 кг калийных удобрений.

Для подкормки некоторого газона требуется по меньшей мере 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений.

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

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

Решение:

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

Переменные: -обычное удобрение; - улучшенное удобрение.

Целевая функция: f () = 3+4 min

Ограничения:  

                              

                                       ,0

1. Строим ОДР ЗЛП:

:		0	3,3
		5	0
:+ 20		0	5
		3,3	0
+37		0	7
		2,3	0

 

 

РИС

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

2. Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными произведениями целевой функции:

=

Чтобы построить такой вектор, нужно соединить точку (3;4) с началом координат.

3. Строим линию уровня, которая является перпендикуляром вектора градиента.
4. Далее будем передвигать линию уровня до ее выхода из ОДР. При минимизации целевой функции движение линии уровня будем осуществлять в противоположном направлении градиента. В точке С достигается min целев. функции. Для нахождения координат этой точки решим систему из уравнений двух прямых, дающих в пересечении точку максимума:

 

Получаем и . При этих значениях min f () = 3+4

максимальное значение - отсутствует (функция неограниченна сверху на ОДР). С помощью надстройки ЕХСЕL «Поиск решения" минимум целевой функции, также как и при использовании графического метода. Максимум найти не удается (сообщается, что результат не сходится); в таблице помещено только одно из возможных значений.

Ответ: min f () = 3+4

 

 

Задание 3

Хозяйственный отдел крупного больничного комплекса использует за год 900 упаковок моющего средства «Comet» весом 400 г.

Стоимость заказа – 200 руб., стоимость хранения одной упаковки в год – 2 руб. 60 коп. Доставка заказа осуществляется в течение трех дней. Хозяйственный отдел работает 300 дней в году.

? Определите:

а) оптимальный объем заказа;

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

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

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

Решение:

Дано:

T = 300 дней;

М = 900шт/год;

h = 2,6 руб./шт;

K = 200 руб.;

t = 3 дня.

Определить: Qопт, издержки, уровень повторного заказа, число циклов за год, расстояние между циклами.

Решение.

1. Количество единиц в одной поставке:

 

2. Общие издержки за год:

 

 

3. Строим график общих годовых затрат с помощью таблицы:

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

4. Частота поставок (количество поставок за год):

 

5. Периодичность поставок (интервал между поставками):

 

то есть одна поставка происходит каждые 61 дней.

6. Точка заказа:

 

Каждый раз, когда остается 3 ед, делается новый заказ на 372 ед.

График циклов изменения запасов построим исходя из данных таблицы:

 

T, дни	Запас	Пояснения
0 1 2 2 3 4 4	372 3 0 372 3 0 372	Уровень запасов Точка заказа Запас исчерпан Уровень запасов Точка заказа Запас исчерпан Уровень заказов

 

 

График циклов изменения запаса

 

 

 

Ответ: оптимальный объем заказа = 372 ед; годовые расходы на хранение запасов = 967,47 руб; период поставок = 124 дней; точку заказа = 3 ед.

 

 

 

Задание 4

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

Вариант	Параметр λ	Параметр Тср=1/μ
4.3	16	10

 

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

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

С необходимым теоретическим материалом и примером решения подобной задачи можно ознакомиться в [1, с. 108–109].

Решение:

Рассчитаем по приведенным ниже формулам основные показатели системы для условий задачи. Это удобно сделать в MS Excel (рис. 4.1.).

Видно, что СМО в значительной мере перегружена: из двух мастеров занято в среднем около 1,5, а из обращающихся в мастерскую рабочих около 53% остаются необслуженными.

Из графика на рис. 4.2. (Мастер диаграмм Excel /Точечная) видно, что минимальное число каналов обслуживания (мастеров), при котором вероятность обслуживания работника будет выше 85%, равно n = 3.

1. Вероятность отказа в обслуживании

 

 

2. Относительная пропускная способность В, т.е. вероятность того, что заявка будет обслужена,

 

3. Абсолютную пропускную способность А получим, умножая интенсивность потока заявок λ на В:

 

4. Среднее число занятых каналов

 

 

Рис.4.1.Расчет характеристик СМО

Рис.4.2.График вероятности отказа в обслуживании

Вывод:

1. Основные характеристики работы бухгалтерии как СМО с отказами:

Вероятность отказа в обслуживании рабочего в бухгалтерии: ротк ≈ 52,2%

Относительная пропускная способность бухгалтерии: В ≈ 47,8%

Абсолютная пропускная способность: А ≈ 8,6 рабочих в час

Среднее число занятых бухгалтеров: М ≈ 1,4

2. Если в бухгалтерии начнет работать 9 бухгалтеров, то вероятность в обслуживании будет выше 85%.

 

 

Задание 5

Статистический анализ показал, что случайная величина Х (длительность обслуживания клиента в парикмахерской) следует показательному закону распределения с параметром μ , а число клиентов, поступающих в единицу времени (случайная величина Y), – закону Пуассона с параметром λ .

Значения параметров λ и μ по вариантам приведены в таблице.

Вариант	Параметр λ	Параметр μ
5.3	1,8	0,5

 

Организуйте датчики псевдослучайных чисел для целей статистического моделирования (использования метода Монте-Карло).

Получите средствами MS Excel 15 реализаций случайной величины Х и 15 реализаций случайной величины Y.

Решение:

Имитационный эксперимент проведем с использованием MS EXCEL

Рис.5.1 15 реализаций случайных величин Х и У

Вводим значения параметров данных законов распределения и λ=1,8 в ячейки В1 и В5

Получим 15 реализаций случайной величины Х (длительность обслуживания клиента в парикмахерской):

В ячейку В3 вводим формулу: =60*(-1/$B1)*LN(СЛЧИС())

Копируем эту формулу в ячейки С3:Р3

 

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

В ячейку В7 вводим формулу: =60*(-1/$B5)*LN(СЛЧИС())

Копируем эту формулу в ячейки С7:Р7

 

Введем учет времени прихода в парикмахерскую клиентов (мин):

В ячейку В9 вводим формулу: =В7 (время прихода 1-го клиента)

В ячейку С9 вводим формулу: =В9+С7 (время прихода 2-го клиента)

Копируем эту формулу в ячейки D9:Р9 (время прихода следующего клиента)

 

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

В ячейку 1 вводим формулу: =60/В1

В ячейку 3 вводим формулу: =СРЗНАЧ (В3:Р3)

В ячейку 5 вводим формулу: =60/В5

В ячейку 3 вводим формулу: =СРЗНАЧ (В7:Р7)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список литературы

1. Гармаш А.Н., Орлова И.В. Математические методы в управлении: учебное пособие/ под ред А.Н.Гармаш.-М.: Вузовский учебник: ИНФРА-М, 2012.

2. Орлова И.В., половников В.А. Экономико-математическое методы: Компьютерное моделирование: учебное пособие/ под ред. И.В.Орловой-3-е изд., перераб. и доп..-М.: Вузовский учебник: ИНФРА-М, 2012.

3. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач: учебное пособие/ под ред И.В.Орловой-2-е изд., исп. и доп..-М.: Вузовский учебник: ИНФРА-М, 2012.

4. Федосеев В.В. Гармаш А.Н., Орлова И.В. Экономико-математические методы и прикладные модели: учебник для бакалавров/под ред. В.В.Федосеева.-3-е изд., перераб. и доп.-М.: Юрайт,2012

5. Федосеев, В. В. Экономико-математические методы и прикладные модели [Электронный ресурс] : Учеб. пособие для вузов / В. В. Федосеев, А. Н. Гармаш, И .В. Орлова и др.; Под ред. В. В. Федосеева. - 2-е изд., перераб. и доп. - М. : ЮНИТИ-ДАНА, 2012. - 304 с.

6. Федосеев, В. В. Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / В. В. Федосеев, А. Н. Гармаш, Д.М.Дайитбегов и др.; Под ред. В. В. Федосеева. - М.: ЮНИТИ-ДАНА, 2001. - 391 с

7. Хуснутдинов Р.Ш.  Экономико-математические методы и модели: Учебное пособие / Р.Ш. Хуснутдинов. - М.: НИЦ Инфра-М, 2013. - 224 с.

8. http://emm.ostu.ru/lect/lect2_3.html#vopros5

9. http://nashaucheba.ru/v55495