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

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

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

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

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

 

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

 

 

 

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

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

Вариант 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

 

 

РИС

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