Оптимизация

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

Задача 1.6. О лесоматериалах

В районе лесного  массива имеются лесопильный  завод и фанерная фабрика. Чтобы  получить 2 м³ коммерчески реализуемых комплектов пиломатериалов, необходимо израсходовать 2 м³ еловых и 7 м³ пихтовых лесоматериалов. Для приготовления листов фанеры по 100 м² требуется 5 м³ еловых и 10 м³ пихтовых лесоматериалов. Лесной массив содержит 80 м³ еловых и 180 м³ пихтовых лесоматериалов.

Согласно условиям поставок, в течение планируемого периода необходимо произвести по крайней  мере 10 м³ пиломатериалов и 1200 м ² фанеры. Доход с 1 м³ пиломатериалов составляет 160 руб., а со 100 м² фанеры - 600 руб.

Задание. Постройте математическую модель для нахождения плана производства, максимизирующего доход. Определите, является ли данная задача задачей ЛП. Оцените ее размерность.

Примечание. При построении модели следует учесть тот факт, что пиломатериалы могут быть реализованы только в виде неделимого комплекта размером 2 м³ , а фанера - в виде неделимых листов по 100 м².   

Задача 1.7. О самолетах

Для обслуживания 2-х авиалиний (Новосибирск-Москва и  Новосибирск – Владивосток) авиакомпания использует 3 типа самолетов. Число самолетов каждого типа, которое авиакомпания имеет в наличии, - a_i , . Компания считает, что количество пассажиров, которые отправятся по каждой авиалинии, составит b_k, . Известны количество помещающихся в i-м типе самолета пассажиров p_i и эксплуатационные расходы на содержание одного самолета каждого типа на каждой авиалинии c_ik.

Задание. Постройте оптимизационную модель, позволяющую определить план использования самолетов на авиалиниях при минимальных издержках.   

Задача 1.8. О фермерском хозяйстве

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

Таблица 1.4 – Исходные данные задачи о фермерском хозяйстве

Участки	Посевная  площадь, га	Кукуруза		Горох		Картофель		Рожь
		урож-ть, ц/га	себест-ть, руб/ц	урож-ть, ц/га	себест-ть, руб/ц	урож-ть, ц/га	себест-ть, руб/ц	урож-ть, ц/га	себест-ть, руб/ц
А	300	100	10	60	20	80	25	35	40
В	500	80	15	48	25	64	15	28	40
С	400	120	18	72	20	96	10	42	20
План  урожая, т		3000		1800		2400		700

 

 

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

1) с использованием  приведенных в таблице 1.4 численных  значений показателей;

2) с использованием  самостоятельно введенных условных  обозначений в общем виде.  

Задача 1.9. О комплектах

Мебельная фабрика  выпускает 4 типа изделий. При изготовлении используется 2 типа досок. Фабрика  имеет 1000 м досок первого типа и 1500 м  досок второго типа. Общие трудозатраты ограничены 800 чел/час. Известны нормативы затрат каждого вида ресурсов на 1 ед. изделий ( - индекс вида изделия,  - индекс вида досок):

·     t_i - затраты трудовых ресурсов на производство одного изделия i-го вида;

·     m_ij - затраты досок j-го вида на производство одного изделия i-го вида;

·     p_i - прибыль от производства одного изделия i-го вида;

·     Р - план по прибыли.

Продукция реализуются  комплектами, при этом  ki – коэффициент ассортиментности, который указывает, сколько изделий i-го вида входит в комплект (шкаф - 1 ед., кровать - 1 ед., комод - 1 ед., тумбочка - 2 ед.).

Задание. Построить математическую модель, позволяющую определить оптимальный ассортимент выпуска изделий, максимизирующий количество комплектов.

Теория оптимизации (лекции)

Кравцова  Л.В.

Надіслав: Кравцова Людмила (27 січня 2004р.)

Факультет фізики, математики та інформатики :: Кафедра  інформатики :: Теория оптимизации

Анотація

Материал содержит лекции по курсу теории оптимизации

Четвертый курс, второй семестр

Теория  оптимизации (лекции)

ТЕМАТИЧЕСКИЙ  ПЛАН ЛЕКЦИЙ 
   
1. Предмет, особенности и сферы применения методов оптимизации в экономике, классификация задач. 
Предмет, объект и методологические основания курса.  
Задачи экономического выбора. Сущность обычной (однокритериальной) оптимизации. Экономическая и математическая постановка оптимизационных задач. 
Выбор критерия оптимизации, функциональных и нефункциональных ограничений оптимизационных задач. 
Классификация моделей и методов решения задач математического программирования. 
Примеры экономических проблем, которые целесообразно решать, используя методы и модели математического программирования. 
     Lecture1.pdf

2-3. Общая задача  линейного программирования и  некоторые из методов ее решения. 
Экономическая и математическая постановка задач линейного программирования (ЛП). Система используемых гипотез. 
Определение множества допустимых планов задачи ЛП. Геометрическая интерпретация множества допустимых решений задачи ЛП. 
Целевая функция задачи ЛП. Каноническая форма линейной оптимизационной модели. Оптимальный план задачи ЛП. 
Симплексный метод. Другие методы решения задач ЛП. 
     Lecture2.pdf 
     Lecture3.pdf

4. Теория двойственности  и двойственные оценки в анализе  решений линейных оптимизационных  моделей 
Основная и двойственная задачи как пара взаимносопряженных задач ЛП. 
Двойственные оценки и дефицитность ресурсов в окрестности оптимального плана задачи ЛП. 
Устойчивость оптимальных планов прямой и двойственной задач. 
Основные теоремы двойственности задачи и их экономический смысл. 
Послеоптимизационный анализ задач ЛП. 
     Lecture4.pdf

5. Анализ линейных  моделей экономических задач. 
Анализ решений линейных экономико-математических моделей. 
Оценка рентабельности производимой продукции и новой продукции. 
Анализ ограничений дефицитных и недефицитных ресурсов. Анализ коэффициентов целевой функции. Анализ коэффициентов технологической матрицы для базисных и свободных переменных. 
Примеры практического использования двойственных оценок в анализе экономических задач. 
     Lecture5.pdf

6-7. Транспортная  задача (ТЗ). Постановка, методы решения  и анализа. 
Экономическая и математическая постановка транспортной задачи. Условия существования решения ТЗ. Методы построения опорного плана. Случай вырождения. Двойственная задача. Условие оптимальности. Методы решения ТЗ. Транспортная задача по критерию времени. Нетрадиционные транспортные задачи. 
     Lecture6-7.pdf

8-9. Целочисленные  задачи линейного программирования. Некоторые из основных методов  их решения и анализа.   
Область применения целочисленных задач ЛП в планировании и управлении производством.  
Математическая постановка целочисленных задач ЛП. Геометрическая интерпретация решений на плоскости. Методы решения целочисленных задач ЛП. Метод Гомори. Метод ветвей и границ. 
     Lecture8-9.pdf

10. Сетевые модели.  Обзор применения сетевых моделей.  
Задача нахождения кратчайшего пути. Задача о максимальном  потоке.  
Нахождение потока наименьшей стоимости. Методы сетевого планирования. 
     Lecture10.pdf

11-13. Задачи нелинейного  программирования. Некоторые основные методы их решения и анализа. 
Экономическая сущность и постановка отдельных типов задач нелинейного программирования (НЛП). 
Классический метод оптимизации задач НЛП на базе использования множителей Лагранжа и их экономическая интерпретация.  
Выпуклое программирование. Необходимые и достаточные условия существования седловой точки. Теорема Куна-Таккера. 
Некоторые из основных методов решения задач НЛП.  
Методы анализа оптимального плана задачи НЛП.  
     Lecture11-13.pdf

14-15. Задачи динамического  программирования. 
Экономическая сущность, некоторые основные типы задач и модели динамического программирования (ДП). 
Задачи о замене основного капитала оборудования предприятия. 
Многошаговый процесс принятия решений и ДП. 
Метод рекуррентных соотношений. Принцип оптимальности Беллмана. 
Алгоритм Джонсона.  
     Lecture14-15.pdf

16-18. Модели и  методы стохастического программирования. 
Слабоструктурированные прикладные экономические проблемы и принятие решений в условиях неопределенности и риска. 
Общая математическая постановка задачи стохастического программирования (СП). Классификация задач СП. Творческая составляющая и система гипотез в формализации задачи СП.  
Некоторые (прямые и непрямые) методы решения задач СП. 
Методы имитационного моделирования в решении решения задач СП. 
Экономическая сущность и основные типы одноэтапных задач СП. 
Стохастические аналоги детерминированных моделей управления производством. Планирование объема реализации при неопределенном спросе. Индикативное планирование при неопределенности в ресурсах. 
Анализ решения одноэтапных статических задач СП. 
     Lecture16-18.pdf

19-20. Элементы  теории игр. 
Основные понятия теории игр. Матричные игры двух особ. Платежная матрица. Игра в чистых стратегиях. Минимаксные стратегии. Седловая точка. Смешанные стратегии.  
Основная теорема теории игр. Сведение задачи игры двух особ к задаче линейного программирования.  
     Lecture19-20.pdf