Исследование операций и методы оптимизации (стр. 2 )

№	тема	форма	часы
лекц	прак	лаб
1	Тема 2. Общая и основная задачи линейного программирования	лекция-визуализация	2
2	Тема 4. Нахождение решения задачи линейного программирования	взаимопроверка самостоятельных работ		2	2
3	Тема 6. Транспортная задача	разбор конкретных ситуаций		2	2
4	Тема 8. Задачи параметрического программирования	лекция-визуализация, взаимопроверка самостоятельных работ	2	2	2
5	Тема 10. Задачи теории игр и линейное программирование	деловая игра	2	2	2
6	Тема 13. Задачи выпуклого программирования	поиск ошибок в решениях		2	2
Итого часов аудиторных	6	10	10
Всего аудиторных часов по дисциплине	36	36	36
Процент использования активных и интерактивных форм	17%	28%	28%
Всего от общего количества аудиторных часов	24%

6. Учебно-методическое обеспечение самостоятельной работы студентов

Самостоятельная работа студентов реализуется в разных видах. Она включает подготовку студентов к семинарским (практическим) занятиям. Для этого студент изучает лекции преподавателя, основную, дополнительную литературу, Интернет-ресурсы, рекомендованные в разделе 8 «Учебно-методическое и информационное обеспечение дисциплины». Самостоятельная работа предусматривает также решение во внеучебное время практических заданий, приведённых в разделе 7 «Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины». К самостоятельной работе студента относится подготовка к экзамену. Экзаменационные вопросы приведены также в разделе 7.

7. Оценочные средства для текущего контроля успеваемости,

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

ЗАДАНИЯ ДЛЯ Практических занятий

РАЗДЕЛ 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Тема 1. Примеры задач линейного программирования

Контрольные вопросы

1.  В чем проявляется связь курса «Исследование операций и методы оптимизации» с другими науками?

2.  Основные понятия исследования операций.

3.  Что такое оптимальное программирование?

4.  Опишите общий вид задачи оптимизации, охарактеризуйте ее элементы.

5.  Что такое оптимальное решение с точки зрения оптимизационной задачи, и как та

-кое оптимальное решение может соотноситься с желаемым?

6.  Опишите классификацию методов оптимального программирования.

7.  Что каждый из них собой представляет, для решения каких задач может быть применим на практике?

8.  Кто является автором метода линейного программирования?

9.  Общий вид задачи линейного программирования.

10.  Опишите общий вид задачи ЛП, охарактеризуйте ее основные элементы.

11.  Какие разновидности задач линейного программирования вы можете назвать, чем они отличаются друг от друга, как соотносятся друг с другом?

12.  Что понимается под задачей линейного программирования?

13.  Где применяются задачи линейного программирования?

14.  Каковы задачи математических методов исследования экономики?

15.  В чем различие задач линейного и нелинейного программирования?

16.  Что понимается под математической моделью экономической задачи?

17.  Сформулируйте задачу о рационе.

18.  Сформулируйте задачу об использовании ресурсов.

19.  Приведите примеры задач линейного программирования.

Практические задания

Задание 1. Для изготовления двух видов продукции P1 и P2 используют четыре вида ресурсов S1, S2, S3, S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице 1.

Таблица 1

Вид ресурса	Запас ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции
P1	P2
S1	18	1	3
S2	16	2	1
S3	5	0	1
S4	21	3	0

Прибыль, получаемая от единицы продукции P1 и P2, соответственно равна 2 и 3 ден. ед. необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

Задание 2. В суточный рацион включают два продукта питания П1 и П2, причем продукта П1 должно войти в дневной рацион не более 200 ед. Стоимость 1 ед. продукта П1 составляет 2 ден. ед., продукта П2 – 4 ден. ед. Содержание питательных веществ в 1 ед. продукта, минимальные нормы потребления указаны в таблице 2.

Таблица 2

Питательные вещества	Минимальная норма потребления	Содержание питательных веществ в 1 ед. продукта
П1	П2
А	120	0,2	0,2
В	160	0,4	0,2

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

Задание 3. Фирма выпускает изделия двух типов: А и В. При этом используется сырье четырех видов. Расход сырья каждого вида на изготовление единицы продукции и запасы сырья заданы в таблице 3.

Таблица 3

Изделия	Сырье	Доход
1	2	3	4
А	2	1	0	3	200
В	3	0	2	2	100
Запасы	21	5	6	10

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

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

Таблица 4

Оборудование	Детали	Полезный фонд времени, станко-ч
1	2
Технологические способы
1	2	1	2
Фрезерное	2	2	3	0	20
Токарное	3	1	1	2	37
Сварочное	0	1	1	4	30
Прибыль, усл. ед.	11	6	9	6

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

Задание 5. Необходимо распилить 20 бревен длиной по 5 м каждое на бруски по 2 м и 3 м; при этом должно получиться равное количество брусков каждого размера.

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

Задание 6. Цеху, располагающему тремя видами металлорежущего оборудования, планируется изготовить в течение определенного периода времени два изделия, причем первое изделие комплектуется на двух деталях А1 и А2, которые должны изгото-вляться в соответствии 2:1.

Второе изделие также комплектуется на двух деталях А3 и А4, которые изготовляются соответственно в соотношении 4:1.

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

Таблица 5

Группы оборудования	Детали	Эффективный фонд времени
А1	А2	А3	А4
Нормы трудоемкости
I	1,2	1,8	2,4	0	768
II	2,4	0	1,2	2,4	600
III	0	1,2	1,2	1,2	480

Определить производственную программу выпуска деталей А1, А2, А3, А4 при обеспечении заданной комплектности, а также максимально возможную загрузку наличных производственных мощностей.

Литература основная: [1-4, 7, 8]; дополнительная: [1-7].

Тема 2. Общая и основная задачи линейного программирования

Контрольные вопросы

1.  Сформулируйте определение общей задачи линейного программирования.

2.  Какие существуют виды математических моделей?

3.  Сформулируйте определение канонической задачи линейного программирования.

4.  Сформулируйте определение допустимого решения (плана), оптимального плана?

5.  Как привести задачу линейного программирования к каноническому виду?

6.  Как преобразовать задачу линейного программирования из канонической формы в стандартную?

Практические задания

Задание 7. Преобразовать задачу линейного программирования, представленную в стандартной форме к каноническому виду:

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

.

Задание 8. Преобразовать задачу линейного программирования, представленную в канонической форме к стандартному виду:

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

Литература основная: [1-4, 7, 8]; дополнительная: [1-7].

Тема 3. Свойства основной задачи линейного программирования.

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

Контрольные вопросы

1.  Дайте определение выпуклого множества точек.

2.  Дайте определения внутренней, граничной, угловой точек.

3.  Дайте определения замкнутой, ограниченной, неограниченной области.

4.  Дайте определения n-мерного многогранника, n-мерной многогранной области.

5.  Что такое пересечение выпуклых областей?

6.  Сформулируйте свойства задачи линейного программирования.

7.  Какие переменные называются основными (базисными)?

8.  Какие переменные называются неосновными (свободными)?

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

10.  Какое решение задачи линейного программирования называется базисным?

11.  Что такое опорный план задачи?

12.  Дайте определение области решения системы (ОР)?

13.  Дайте определение области допустимых решений (ОДР).

14.  От чего зависит количество измерений пространства, в котором можно реализовать графическую иллюстрацию решения задачи?

15.  Какие задачи можно решать с помощью графического метода?

16.  Что является решением каждого неравенства системы?

17.  Что такое линия уровня?

18.  Как построить вектор нормали? Какую роль играет вектор нормали?

19.  В каком случае задача имеет альтернативный оптимум?

20.  Назовите возможные случаи решения задачи линейного программирования графическим методом.

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

22.  Сформулируйте алгоритм графического метода.

Практические задания

Задание 9. Решить графическим методом задачу линейного программирования с двумя переменными

Задание 10. Фирма выпускает два вида мороженого: сливочное и шоколадное. Для изготовления мороженого используются два исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы даны в таблице 6.

Таблица 6

Исходный продукт	Расход исходных продуктов на 1 кг мороженого	Запас, кг
Сливочное	Шоколадное
Молоко	0,8	0,5	400
Наполнители	0,4	0,8	365

Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Розничная цена 1 кг сливочного мороженого 16 р., шоколадного – 14 р.

Какое количество мороженого каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным?

Необходимо:

1.  Составить математическую модель задачи.

2.  Решить задачу графическим методом.

3.  Провести экономический анализ задачи.

Задание 11. Решить задачи с использованием графического метода.

11.1.

11.2.

11.3.

11.4.

Литература основная: [1-4, 7, 8]; дополнительная: [1-7].

Тема 4. Нахождение решения задачи линейного программирования

Контрольные вопросы

1.  Сформулируйте идею симплексного метода.

2.  Какие задачи можно решить с помощью симплексного метода?

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

4.  Как связаны симплекс-метод и геометрическая интерпретация решения задачи ЛП?

5.  Что такое базисные (основные) и независимые (неосновные) переменные задачи?

6.  Зачем необходимо деление переменных задачи на эти две группы?

7.  Что такое дополнительные переменные, для чего они нужны?

8.  Каковы характеристики начального опорного решения задачи?

9.  Опишите свойства задачи ЛП (предпосылки применения симплекс-метода)

10.  Охарактеризуйте последовательность действий при решении задачи ЛП симплекс-методом

11.  Как построить первоначальный допустимый план задачи?

12.  В чем заключается правило перехода к лучшему решению?

13.  Сформулируйте критерий оптимальности найденного решения для задачи нахождения минимума линейной функции.

14.  Сформулируйте критерий оптимальности найденного решения для задачи нахождения максимума линейной функции.

15.  Сформулируйте алгоритм составления симплексных таблиц.

16.  В чем заключается правило «прямоугольника»?

17.  Какой элемент называется ключевым? Как его найти?

18.  Какое решение называется вырожденным?

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

20.  Сформулируйте критерий альтернативного оптимума.

21.  В чем заключается метод искусственного базиса?

22.  Когда его требуется применять?

23.  Чем отличается симплексный метод от метода искусственного базиса?

24.  В чем заключается отличие дополнительных переменных от искусственных?

Практические задания

Задание 12. Решить задачу линейного программирования

Задание 13. Решить следующие задачи:

13.1.

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

13.2.

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

13.3.

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

Задание 14. Торговая фирма для продажи товаров трех видов использует ресурсы: время и площадь торговых залов. Затраты ресурсов на продажу одной партии товаров каждого вида даны в таблице 7.

Таблица 7

Ресурсы	Вид товара	Объем ресурсов
1	2	3
Время, чел.-ч	0,5	0,7	0,6	370
Площадь, м2	0,1	0,3	0,2	90

Прибыль, получаемая от реализации одной партии товаров 1-го вида – 5 усл. ед., 2-го вида – 8 усл. ед., 3-го вида – 6 усл. ед.

Определить оптимальную структуру товарооборота, обеспечивающую фирме максимальную прибыль.

Литература основная: [1-4, 7, 8]; дополнительная: [1-7].

Тема 5. Двойственные задачи линейного программирования

Контрольные вопросы

1.  Какая задача называется двойственной?

2.  Сформулируйте правила построения двойственных задач.

3.  В чем заключаются особенности построения несимметричных двойственных задач?

4.  Сформулируйте свойства двойственных задач.

5.  Какова взаимосвязь параметров и переменных взаимно двойственных задач?

6.  Какие виды двойственных задач существуют? В чем их отличие?

7.  Как соотносятся основные и дополнительные переменные взаимно двойственных

задач.

8.  Что такое невязки?

9.  Опишите метод одновременного решения взаимно двойственных задач.

10.  Сформулируйте экономическую интерпретацию задачи, двойственной задаче об использовании ресурсов.

11.  В чем заключается первая теорема двойственности? Ее экономический смысл.

12.  В чем заключается вторая теорема двойственности?

Практические задания

Задание 15. Фирма выпускает три вида изделий, располагая при этом сырьем четырех типов: А, Б, В, Г соответственно в количествах 18, 16, 8 и 6 т. Нормы затрат каждого типа сырья на единицу изделия первого вида составляют соответственно 1, 2, 1, 0, второго вида – 2, 1, 1, 1 и третьего вида – 1, 1, 0, 1. Прибыль от реализации единицы изделия первого вида равна 3 усл. ед., второго – 4 усл. ед., третьего – 2 усл. ед.

Требуется:

1.  Составить план производства трех видов, максимизирующих прибыль;

2.  Определить дефицитность сырья;

3.  Установить размеры максимальной прибыли при изменении сырья А на 6 т, Б – на 3 т, В – на 2 т, Г – на 2 т. Оценить раздельное влияние этих изменений и суммарное их влияние на прибыль;

4.  Оценить целесообразность введения в план производства фирмы нового вида изделий (четвертого), нормы затрат на единицу которого соответственно равны 1, 2, 2, 0, а прибыль составляет 15 усл. ед.

Задание 16. Составить математические модели двойственных задач и по решению исходной задачи найти оптимальное решение двойственной.

16.1.

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

16.2.

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

16.3.

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

16.4.

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

Задание 17. Пусть имеется каноническая задача линейного программирования

Необходимо последовательно выполнить следующие задания.

1.  Задачу решить графическим методом.

2.  Применяя симплекс-метод, решить задачу или установить, что задача не имеет решения. Начальный план рекомендуется искать методом искусственного базиса.

3.  Построить двойственную задачу. Если вектор найден, вычислить оптимальный план двойственной задачи, используя первую теорему двойственности . Вычислить значение функции .

4.  Провести анализ полученного решения, применяя условия дополняющей нежесткости.

Литература основная: [1-4, 7, 8]; дополнительная: [1-7].

РАЗДЕЛ 2. СПЕЦИАЛЬНЫЕ ЗАДАЧИ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Тема 6. Транспортная задача

Контрольные вопросы

1.  Сформулируйте общую постановку транспортной задачи и ее цель.

2.  Какие транспортные задачи называются закрытыми?

3.  Какие транспортные задачи называются открытыми?

4.  Каковы правила приведения открытой модели ТЗ к закрытой?

5.  Можно ли транспортную задачу решить симплексным методом?

6.  Назовите известные методы построения опорного плана транспортной задачи.

7.  Какой из методов построения опорного плана транспортной задачи является близким к оптимальному?

8.  Как определить количество занятых клеток в распределительной таблице транспортной задачи?

9.  Назовите метод построения оптимального плана транспортной задачи.

10.  Сформулируйте теорему о потенциалах. Каков её экономический смысл?

11.  Алгоритм метода потенциалов.

12.  Как вычисляют оценки при проверке на оптимальность в распределительной таблице?

13.  Сформулируйте критерий оптимальности базисного распределения поставок.

14.  При каких условиях ТЗ имеет бесконечное множество оптимальных планов перевозок?

15.  Что называется циклом?

16.  Что называется ценой цикла?

17.  Каковы правила построения цикла в распределительной таблице?

18.  В каком случае транспортная задача имеет вырожденное решение?

19.  Как исключить вырожденность в транспортных задачах?

20.  Какие экономические задачи можно отнести к транспортным моделям?

21.  Постановка транспортной задачи с ограниченной пропускной способностью.

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

23.  Какова цель транспортной задачи с ограниченными пропускными способностями?

24.  Какие условия должны соблюдаться, чтобы задача имела план?