Задачи для практических занятий

по курсу “Исследование операций”

для студентов 4 курса дневного отделения

математического факультета.

Иваново 2010

Задачи для практических занятий

по курсу “Исследование операций”

для студентов 4 курса дневного отделения

математического факультета.

Составители: Иванова Т.П., доцент кафедры

вычислительной и прикладной математики ИвГУ,

Копрова А.Е., Иванова О.А.,

студенты математического факультета ИвГУ

Список рекомендуемой литературы

Основная

1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986.

2. Киселев В.Ю. Экономико-математические методы и модели. – Иваново, ИГЭУ, 1998.

Дополнительная:

1. Ашманов С. А. Линейное программирование. – М.: Наука, 1981.

2. Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Наука, 1988.

3. Волков И.К., Загоруйко И.А. Исследование операций: Учеб. для вузов. – М.: Изд-во МГТУ им Н.Э.Баумана, 2002.

4. Кремер Н.Ш. и др. Исследование операций в экономике: Учеб. пособие для вузов. – М.: ЮНИТИ, 2005.

5. Шикин Е.В., Шикина Г.Е. Исследование операций: учеб. – М.: ТК Велби, Изд-во Проспект, 2006.

Методические указания:

1. Практикум по линейному программированию. Учебно-методическое пособие под редакцией Черемных Ю.Н., Павловой Л.С., Суторминой Е.И. М.: Изд. МГУ, 1984.

2. Кузнецова Г.А. Методические указания по графическому решению задач линейного программирования. Иваново, 1982.

3. Сазонова И.Г. Методические указания к проведению лабораторных работ по симплексному методу решения задач линейного программирования. Иваново, 1991.

4. Сазонова И.Г. Методические указания по курсу «Исследование операций» для студентов 6 курса математического факультета (заочное отделение). Иваново, 1988.

Тема 1. Математическое моделирование

Составьте математическую модель следующих ситуаций.

Задача №1. Задача определения ассортимента.

Механический завод производит три вида врезных замков, рынок сбыта которых практически не ограничен. При производстве каждого из видов замков Зi, i = 1, 2, 3, применяется три вида оборудования Мj, j = 1, 2, 3, время (в часах) обработки изделия Зi на оборудовании Мj задается следующей таблицей.

  М1 М2 М3
З1 0,05 0,04 0,03
З2 0,025 0,02 0,04
З3 0,03 0,03 0,03

Максимально возможное время работы машин М1, М2, М3 составляет соответственно 40, 36 и 40 часов в неделю. Прибыль, приносимая каждым произведенным замком типа З1, З2, З3, равна соответственно 5, 3, 4 руб. Требуется определить, сколько нужно заводу производить в неделю замков каждого из типов, чтобы максимизировать прибыль.

Задача №2. Издательство, параметры деятельности которого отражены в таблице, выпускает литературу четырех серий.

Серия Показатель
Прибыль от реализации ед. продукции, руб./экз.
Себестоимость ед. продукции, руб./экз. 0,5
Удельная пропускная способность типографии, оттиск/экз.        
Удельный расход бумаги, лист./экз.

Издательство располагает фондом финансовых средств, равным 10 т. руб., лимитами на бумагу в размере 90 т. листов и пропускной способностью типографий, равной 110 т. оттисков.

При каких тиражах выпускаемых серий издательство получит максимальную прибыль, если имеется предписание, что тиражи серий не должны быть менее 2000, 1300, 1500 и 1000 экземпляров соответственно?

Задача №3. Задача об удешевлении смеси.

Электростанции требуется топливо с содержанием фосфора (Р) не более 0,03%, серы (S) не более 0,1% и негорючих твердых примесей (Z) не более 3%. На рынке энергоресурсов предлагаются в неограниченном количестве три вида топлива N1, N2, N3, которые допускают смешивание в любых пропорциях. Содержание компонентов P, S и Z (в %) в топливе вида N1, N2, N3 задается следующей таблицей.

  P S Z
N1 0,04 0,05 3,5
N2 0,02 0,1 2,8
N3 0,03 0,08 2,5

Цена тонны топлива видов N1, N2, N3 равна соответственно 150, 160, 200 руб. Сколько топлива (в %) видов N1, N2, N3 должна закупать электростанция, чтобы получить топливо допустимой кондиции по минимально возможной цене за 1 т?

Задача №4.Как произвести распил десятиметровых древесных стволов на бревна размерами 5; 2,8 и 6,4 метра в отношении 3 : 5 : 4 так, чтобы минимизировать общую величину отходов?

Задача №5. Ткань трех артикулов производится на ткацких станках двух типов с различной производительностью. Для изготовления ткани используется пряжа и красители. В следующей таблице указаны мощности станков (в тыс. станко-ч), ресурсы пряжи и красителей (в тыс. кг), производительности станков по каждому виду пряжи (в м/ч), нормы расхода пряжи и краски (в кг на 1000м).

Виды ресурсов Объем ресурсов Производительность и нормы расхода
Станки I типа
Станки II типа
Пряжа
Красители

Приняв условие, что количество тканей трех артикулов должно находиться в отношении 2:1:3, определить, какое максимальное количество ткани может выпустить фабрика.

ПРИМЕР РЕШЕНИЯ ЗАДАЧИ С ПОМОЩЬЮ ПАКЕТА

ПРИКЛАДНЫХ ПРОГРАММ

Задача оптимизации плана производства

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

Ресурсы Нормы затрат на одно изделие вида Общее количество ресурсов
Производительность оборудования (нормо-ч) 1 типа 2 типа         –        
Сырье (кг) 1 вида 2 вида        
Цена одного изделия (руб.)
Выпуск (шт) минимальный максимальный         –  

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

РЕШЕНИЕ. Составим математическую модель. Предположим, что предприятие изготовит х1 изделий 1-го вида, х2 изделий 2-го вида и х3 изделий 3-го вида.

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

Задачи для практических занятий - student2.ru ,

при ограничениях на имеющийся фонд рабочего времени каждого типа оборудования:

Задачи для практических занятий - student2.ru ,

Задачи для практических занятий - student2.ru ,

на возможное использование сырья:

Задачи для практических занятий - student2.ru ,

Задачи для практических занятий - student2.ru ,

на возможный выпуск изделий каждого вида:

Задачи для практических занятий - student2.ru , Задачи для практических занятий - student2.ru , Задачи для практических занятий - student2.ru .

Результаты решения задачи с помощью пакета прикладных программ POM WIN содержатся в таблицах 1-3 (стр.19‑20).

Из таблиц 1 и 3 следует, что оптимальный план выпуска продукции включает в себя 10 изделий 1-го вида, 33 изделия 2-го вида и 45 изделий 3-го вида. Максимальная общая стоимость продукции составляет 1495 рублей. При этом рабочее время станков 1 типа использовано полностью (slack 1 = 0), 316 часов работы станков 2 типа остались неиспользованными (slack 2 = 316). Сырье 1-го вида использовано полностью (slack 3 = 0), остаток сырья 2-го вида составляет 2415 кг (slack 4 = 2415).

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

Так как базисными переменными (таблица 3) являются Задачи для практических занятий - student2.ru , Задачи для практических занятий - student2.ru , Задачи для практических занятий - student2.ru , slack 2 (остаток рабочего времени станков 2 типа), slack 4 (остаток сырья 2-го вида), slack 6, slack 8, slack 10 (разность между верхней границей выпуска продукции 1-го, 2-го и 3-го видов соответственно и оптимальным значением выпуска), и surplus7, surplus 9 (превышение плана выпуска продукции по сравнению с нижней границей), то оптимальное решение задачи определяется из следующей системы уравнений.

Задачи для практических занятий - student2.ru ,

Задачи для практических занятий - student2.ru ,

Задачи для практических занятий - student2.ru ,

Задачи для практических занятий - student2.ru ,

Задачи для практических занятий - student2.ru , (1)

Задачи для практических занятий - student2.ru ,

Задачи для практических занятий - student2.ru ,

Задачи для практических занятий - student2.ru ,

Задачи для практических занятий - student2.ru ,

Задачи для практических занятий - student2.ru .

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

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

Тема 2. Графическое решение

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

Пример. Имеется два продукта питания А и В, каждый из которых содержит белки, жиры и углеводы. Количественный состав этих продуктов (в некоторых единицах) и их цена задается таблицей:

Продукт Состав А   В
Белки
Жиры
Углеводы
Цена 4 руб. 6 руб.

Минимальная потребность в питательных веществах – белках, жирах и углеводах – соответственно 45, 10, 60 единиц, при этом можно потребовать продукта А не более 25 единиц, а продукта В – не более 30 единиц. Требуется рассчитать необходимое количество обоих продуктов так, чтобы удовлетворить потребности организма в указанных веществах при минимальных денежных затратах.

РЕШЕНИЕ. Составим математическую модель. Предположим, что Задачи для практических занятий - student2.ru – количество продукта А, Задачи для практических занятий - student2.ru – количество продукта В. Тогда целевая функция задачи имеет вид:

Задачи для практических занятий - student2.ru ,

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

Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru .

Полученную задачу линейного программирования решим графически. Построим сначала допустимое множество нашей задачи, то есть область решений системы неравенств. Шестиугольник CDEFGH – допустимое множество.

x2

Задачи для практических занятий - student2.ru Задачи для практических занятий - student2.ru D E

C

 
  Задачи для практических занятий - student2.ru

H

Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru 0 G x1 Задачи для практических занятий - student2.ru F

Определим направление возрастания значений целевой функции Задачи для практических занятий - student2.ru . Для этого строим вектор (4;6).

Затем проводим линию уровня целевой функции, пересекающую допустимое множество. Теперь переместим линию уровня параллельно самой себе в направлении вектора (4;6) до тех пор, пока она не станет опорной к допустимому множеству.

Пересечение допустимого множества с опорной прямой есть точка H. Точка H есть точка пересечения двух прямых

Задачи для практических занятий - student2.ru

Таким образом, для удовлетворения потребностей в питательных веществах необходимо 12 единиц продукта A и 3 единицы продукта B при минимальных денежных затратах 66 руб.

Задача №1. В одном опытном хозяйстве нашли, что откорм животных выгоден лишь тогда, когда каждое животное получит в дневном рационе не менее 6 единиц питательного вещества А, не менее 12 единиц питательного вещества В и не менее 4 единиц питательного вещества С, при этом используются два вида корма. Содержание питательных веществ в 1 кг каждого вида приведено в таблице:

Вид питательного вещества Вид корма
I II
А
В
С

Цена корма I равна 0,5 денежных единиц за 1 кг, цена корма II – 0,6 денежных единиц за 1 кг. Какое количество корма необходимо расходовать ежедневно, чтобы затраты на него были минимальными при соблюдении указанных выше условий.

Задача №2. Одной из ученических бригад выделили два участка земли в 8 га и 9 га под посевы пшеницы и кукурузы. Средняя урожайность по участкам и культурам отражена в таблице (в ц на га):

участки культура   I   II
Пшеница
Кукуруза

За 1 ц пшеницы получают 2,5 руб., за 1 ц кукурузы – 1,4 руб.

Сколько гектаров и на каких участках необходимо отвести под каждую культуру, чтобы получить от реализации наибольшую сумму, если по плану надо собрать не менее 150 ц пшеницы и не менее 220 ц кукурузы?

Задача №3. Трикотажная фабрика использует для производства свитеров и пуловеров следующие материалы: чистая шерсть, силон, нитрон. Запасы материалов ограничены и составляют соответственно: 900, 400 и 300 кг.Количество пряжи каждого вида (в кг), необходимой для изготовления 10 штук изделий, а также прибыль, получаемая от реа­лизации, приведены в таблице.

Виды сырья Запас сырья в кг Затраты на 10 шт. (в кг)
свитера Пуловеры
Шерсть
Силон
Нитрон
Прибыль

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

Тема 3.Решение задач линейного программирования

I. Для заданных систем ограничений задач линейного программирования указать все возможные базисы и все ДБР:

1. Задачи для практических занятий - student2.ru

2. Задачи для практических занятий - student2.ru

II. Решить задачу линейного программирования, начав с исследования на оптимальность заданного ДБР:

1. Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru

2. Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru

3. Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru

4. Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru

Пример. Решить задачу линейного программирования, начав с исследования на оптимальность заданного ДБР:

Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru

РЕШЕНИЕ. Построим каноническую форму с соответствующими базисными переменными:

Задачи для практических занятий - student2.ru Запишем систему:

Задачи для практических занятий - student2.ru

Преобразуем целевую функцию:

Задачи для практических занятий - student2.ru

Задача приведена к канонической форме:

Задачи для практических занятий - student2.ru

Попробуем уменьшить значение целевой функции.

Пусть Задачи для практических занятий - student2.ru , тогда Задачи для практических занятий - student2.ru .

Берем Задачи для практических занятий - student2.ru , придем к новому решению: Задачи для практических занятий - student2.ru .

Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru Следовательно, (1, 0, 0, 4) – оптимальное решение.

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

Решить задачу с помощью симплексных таблиц.

Задачи для практических занятий - student2.ru

Тема 5.Двойственность в линейном программировании

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

Задачи для практических занятий - student2.ru

РЕШЕНИЕ.

Задачи для практических занятий - student2.ru

I. Сформулировать двойственную задачу:

1. Задачи для практических занятий - student2.ru 2. Задачи для практических занятий - student2.ru

3. Задачи для практических занятий - student2.ru

II. Сформулировать двойственную задачу и найти решения обеих задач двойственной пары:

1. Задачи для практических занятий - student2.ru 2. Задачи для практических занятий - student2.ru

3. Задачи для практических занятий - student2.ru 4. Задачи для практических занятий - student2.ru

5. Задачи для практических занятий - student2.ru

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

Задание.В упражнении приведена таблица, в клетках которой проставлены стоимости перевозок Задачи для практических занятий - student2.ru ( Задачи для практических занятий - student2.ru = 1, 2, 3, 4; Задачи для практических занятий - student2.ru = 1, 2, 3, 4, 5). Справа от таблицы – значения запасов Задачи для практических занятий - student2.ru , внизу – значения потребностей Задачи для практических занятий - student2.ru . Необходимо решить соответствующую задачу методом потенциалов.

 

Тема 7.Целочисленное программирование

Задание. Решить задачи, используя алгоритм Гомори

Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru

Тема 8. Матричные игры

I. Составить платежную матрицу игры «трехпальцевая морра», определить нижнюю и верхнюю цену игры, максиминную и минимаксную стратегии.

II. Найти верхнюю и нижнюю цену матричной игры. Если игра имеет решение в чистых стратегиях, найти его.

Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru

Задачи для практических занятий - student2.ru

III. Построить смешанное расширение и решить игру Г(А), где:

Задачи для практических занятий - student2.ru

IV. Матрица A имеет седловую точку: Задачи для практических занятий - student2.ru , i=1,…,m , j=1,…,n. Доказать, что цена смешанного расширения игры Г(А) равна аkl .

V. Решить игры с заданными платежными матрицами, т.е. найти оптимальные стратегии и цену игры:

1. Задачи для практических занятий - student2.ru 2. Задачи для практических занятий - student2.ru

4. Задачи для практических занятий - student2.ru

3. Задачи для практических занятий - student2.ru

5. Задачи для практических занятий - student2.ru

6. Задачи для практических занятий - student2.ru

7. Задачи для практических занятий - student2.ru

9. Задачи для практических занятий - student2.ru

10. Задачи для практических занятий - student2.ru

8. Задачи для практических занятий - student2.ru

11. Задачи для практических занятий - student2.ru



Приложение.

Results

  X1 X2 X3   RHS Dual
Maximize      
Constraint1 <=
Constraint2 <=
Constraint3 <= 1 495
Constraint4 <= 4 500
Constraint5 >=
Constraint6 <=
Constraint7 >=
Constraint8 <=
Constraint9 >=
Constraint10 <=
Solution 1 495  

Ranging

  Variable   Value Reduced Cost Original Value Lower Bound Upper Bound
X1 -Infinity
X2 0, 0
X3 Infinity
  Constraint Dual Value Slack/ Surplus Original Value Lower Bound Upper Bound
Constraint1
Constraint2 Infinity
Constraint3 1 495 1 300 1 600
Constraint4 2 415 4 500 2 085 Infinity
Constraint5
Constraint6 Infinity
Constraint7 - Infinity
Constraint8 Infinity
Constraint9 - Infinity
Constraint10 Infinity

Solution list

Variable Status Value
X1 Basic
X2 Basic
X3 Basic
slack 1 NON Basic
slack 2 Basic
slack 3 NON Basic
slack 4 Basic 2 415
surplus 5 NON Basic
slack 6 Basic
surplus 7 Basic
slack 8 Basic
surplus 9 Basic
slack 10 Basic
Z Optimal 1 495

Наши рекомендации