Задачи для практических занятий
по курсу “Исследование операций”
для студентов 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-го вида.
Задача состоит в определении максимальной общей стоимости всей изготовляемой продукции.
,
при ограничениях на имеющийся фонд рабочего времени каждого типа оборудования:
,
,
на возможное использование сырья:
,
,
на возможный выпуск изделий каждого вида:
, 
, 
.
Результаты решения задачи с помощью пакета прикладных программ POM WIN содержатся в таблицах 1-3 (стр.1920).
Из таблиц 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) являются 
, 
, 
, slack 2 (остаток рабочего времени станков 2 типа), slack 4 (остаток сырья 2-го вида), slack 6, slack 8, slack 10 (разность между верхней границей выпуска продукции 1-го, 2-го и 3-го видов соответственно и оптимальным значением выпуска), и surplus7, surplus 9 (превышение плана выпуска продукции по сравнению с нижней границей), то оптимальное решение задачи определяется из следующей системы уравнений.
,
,
,
,
, (1)
,
,
,
,
.
При изменении общего количества ресурсов сырья и ресурсов станков, а также границ выпуска продукции в пределах, указанных в таблице 2, решение задачи будет изменяться, при этом оптимальное решение будет определяться системой (1) с измененными правыми частями.
Анализ двойственных оценок (таблица 1 или таблица 2) показывает, что если запасы ресурсов сырья 1-го вида увеличить на единицу (уменьшить на единицу), то оптимальное значение целевой функции увеличится на единицу (уменьшится на единицу). Изменения фонда рабочего времени станков, запасов сырья 2-го вида, границ выпуска изделий в указанных в таблице 2 пределах, не влияют на оптимум задачи, то есть на максимальное значение прибыли.
Тема 2. Графическое решение
задач линейного программирования
Пример. Имеется два продукта питания А и В, каждый из которых содержит белки, жиры и углеводы. Количественный состав этих продуктов (в некоторых единицах) и их цена задается таблицей:
| Продукт Состав | А | В |
| Белки | ||
| Жиры | ||
| Углеводы | ||
| Цена | 4 руб. | 6 руб. |
Минимальная потребность в питательных веществах – белках, жирах и углеводах – соответственно 45, 10, 60 единиц, при этом можно потребовать продукта А не более 25 единиц, а продукта В – не более 30 единиц. Требуется рассчитать необходимое количество обоих продуктов так, чтобы удовлетворить потребности организма в указанных веществах при минимальных денежных затратах.
РЕШЕНИЕ. Составим математическую модель. Предположим, что 
– количество продукта А, – количество продукта В. Тогда целевая функция задачи имеет вид:
,
ограничения:
.
Полученную задачу линейного программирования решим графически. Построим сначала допустимое множество нашей задачи, то есть область решений системы неравенств. Шестиугольник CDEFGH – допустимое множество.
x2
D E
C
 |
H
0 G x1 
F
Определим направление возрастания значений целевой функции 
. Для этого строим вектор (4;6).
Затем проводим линию уровня целевой функции, пересекающую допустимое множество. Теперь переместим линию уровня параллельно самой себе в направлении вектора (4;6) до тех пор, пока она не станет опорной к допустимому множеству.
Пересечение допустимого множества с опорной прямой есть точка H. Точка H есть точка пересечения двух прямых
Таким образом, для удовлетворения потребностей в питательных веществах необходимо 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. 
2. 
II. Решить задачу линейного программирования, начав с исследования на оптимальность заданного ДБР:
1. 
2. 
3. 
4. 
Пример. Решить задачу линейного программирования, начав с исследования на оптимальность заданного ДБР:
РЕШЕНИЕ. Построим каноническую форму с соответствующими базисными переменными:
Запишем систему:
Преобразуем целевую функцию:
Задача приведена к канонической форме:
Попробуем уменьшить значение целевой функции.
Пусть 
, тогда 
.
Берем 
, придем к новому решению: 
.
Следовательно, (1, 0, 0, 4) – оптимальное решение.
Тема 4. Симплексный метод решения задачи линейного программирования
Решить задачу с помощью симплексных таблиц.
Тема 5.Двойственность в линейном программировании
Пример. Поставить задачу, двойственную к данной
РЕШЕНИЕ.
I. Сформулировать двойственную задачу:
1. 
2. 
3. 
II. Сформулировать двойственную задачу и найти решения обеих задач двойственной пары:
1. 
2. 
3. 
4. 
5. 
Тема 6. Транспортная задача
Задание.В упражнении приведена таблица, в клетках которой проставлены стоимости перевозок 
( 
= 1, 2, 3, 4; 
= 1, 2, 3, 4, 5). Справа от таблицы – значения запасов 
, внизу – значения потребностей 
. Необходимо решить соответствующую задачу методом потенциалов.
Тема 7.Целочисленное программирование
Задание. Решить задачи, используя алгоритм Гомори
Тема 8. Матричные игры
I. Составить платежную матрицу игры «трехпальцевая морра», определить нижнюю и верхнюю цену игры, максиминную и минимаксную стратегии.
II. Найти верхнюю и нижнюю цену матричной игры. Если игра имеет решение в чистых стратегиях, найти его.
III. Построить смешанное расширение и решить игру Г(А), где:
IV. Матрица A имеет седловую точку: 
, i=1,…,m , j=1,…,n. Доказать, что цена смешанного расширения игры Г(А) равна аkl .
V. Решить игры с заданными платежными матрицами, т.е. найти оптимальные стратегии и цену игры:
1. 
2. 
4. 
3. 
5. 
6. 
7. 
9. 
10. 
8. 
11. 
Приложение.
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 |