Материал: Контрольная работа 6 вариант (Коренская)

Министерство образования Республики Беларусь

Учреждение образования

«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ»

Институт информационных технологий

Специальность Программное обеспечение информационных технологий

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

По курсу Методы оптимизации

Тема: «Линейная оптимизация. Модели распределения ресурсов. Элементы теории двойственности»

Вариант № 6

Студент-заочник 3 курса

Группы № 781074

ФИО Красносельская Полина Юрьевна

Преподаватель: Коренская И.Н.

Минск, 2019

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

Индивидуальное задание

1. Составить математическую модель задачи. Объяснить экономический смысл переменных.

2. Составить математическую модель двойственной задачи. Объяснить экономический смысл двойственных переменных.

3. Найти оптимальный план выпуска продукции, обеспечивающий максимальную прибыль.

4. Провести анализ оптимальных решений прямой и двойственной задач, используя отчеты трех типов (по результатам, по устойчивости, по пределам):

а) указать, какая продукция вошла в оптимальный план, и насколько невыгодно производство продукции, не вошедшей в оптимальный план,

б) указать дефицитные и избыточные ресурсы,

в) выписать оптимальное решение двойственной задачи,

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

д) указать интервал устойчивости двойственных оценок,

5. Решить двойственную задачу. Сравнить решение с полученным в пункте 4.

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

В 6. Механический завод при изготовлении деталей Д1 и Д2 использует токарное, фрезерное и сварочное оборудование. Обработку деталей можно вести по технологиям I и II. Полезный фонд времени работы каждой группы оборудования (в станко-часах), затраты времени на изготовление детали (в часах) и прибыль от выпуска каждой детали приведены в таблице:

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

Вопрос 6. Классификация детерминированных задач оптимизации.

Рассмотрим детерминированную задачу оптимизации.

,

где область допустимых значений ,

Классификация этой задачи возможна по многим признакам:

1. Классификация по виду критерия оптимальности и ограничивающих функций.

Если критерий оптимальности Ф(X) – линейная функция, а множество D – выпуклый многогранник, то задачи называется задачей линейного программирования.

Если критерий оптимальности Ф(X) – есть отношение двух линейных функций, а множество D – выпуклый многогранник, задача называется задачей дробно-линейного программирования.

Пусть область D определяется только ограничениями типа неравенств:

Тогда если функция Ф(X) и функции являются сепарабельными, то задача называется задачей сепарабельного программирования.

Тогда если функция Ф(X) и функции являются полиномами, то задача называется задачей геометрического программирования.

Если Ф(X) – квадратичная функция, т.е. , а множество D есть выпуклое множество, то задача называется задачей квадратичного программирования. Здесь G – (n*n) симметричная матрица, C – (n*1) вектор.

Если множество D является конечным множеством, то задача называется задачей дискретного программирования.

Если множество D является множеством целых чисел, то задача называется задачей целочисленного программирования.

Если функция Ф(X) является выпуклой, то задача называется задачей выпуклого программирования.

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

2. Классификация по наличию или отсутствию ограничений.

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

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

3. Классификация по характеру ограничений.

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

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

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

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

Ход работы

1. Математическая модель задачи

Переменные задачи:

– объем выпуска деталей Д1 по технологии I

– объем выпуска деталей Д1 по технологии II

– объем выпуска деталей Д2 по технологии I

– объем выпуска деталей Д2 по технологии II

Целевая функция:

– определяет суммарную прибыль от реализации произведенной продукции

Система ограничений:

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

2. Математическая модель двойственной задачи

Двойственные переменные задачи:

– оценка времени при изготовлении деталей на токарном оборудовании

– оценка времени при изготовлении деталей на фрезерном оборудовании

– оценка времени при изготовлении деталей на сварочном оборудовании

Целевая функция:

– определяет суммарную оценку времени при изготовлении деталей

Система ограничений:

– определяет, что оценка времени, затраченного на производство одной детали не меньше, чем прибыль от выпуска единицы этой детали

3. Нахождение оптимального плана выпуска продукции, обеспечивающего максимальную прибыль.

Преобразовываем математическую модель задачи к канонической форме.

4. Классификация по размерности вектора X.

Если размерность вектора X равна 1 (n=1), то задача называется однопараметрической (одномерной) задачей оптимизации.

Если размерность вектора X больше 1 (n>1), то задача называется многопараметрической (многомерной) задачей оптимизации.

5. Классификация по количеству точек минимума.

Если функция Ф(Х) имеет в области допустимых значений D один минимум, то задача называется одноэкстремальной задачей оптимизации.

Если функция Ф(X) имеет в области допустимых значений D более одного минимума, то задача называется многоэкстремальной задачей оптимизации.

6. Классификация по характеру искомого решения.

Если отыскивается любой локальный минимум функции Ф(Х), то задача называется задачей локальной оптимизации.

Если отыскивается любой локальный минимум функции Ф(Х) и задача является задачей безусловной оптимизации, то эта задача называется задачей безусловной локальной оптимизации.

Если отыскивается любой локальный минимум функции Ф(Х) и задача является задачей условной оптимизации, то эта задача называется задачей условной локальной оптимизации.

Если отыскивается глобальный минимум функции Ф(Х), то задача называется задачей глобальной оптимизации.

Если отыскивается глобальный минимум функции Ф(Х) и задача является задачей безусловной оптимизации, то эта задача называется задачей безусловной глобальной оптимизации.

Если отыскивается глобальный минимум функции Ф(Х) и задача является задачей условной оптимизации, то эта задача называется задачей условной глобальной оптимизации.