Санкт-Петербургский Государственный университет
Аэрокосмического приборостроения
РУКОВОДСТВО
К лабораторной работе
Исследование моделей и методов
Решения задач выбора с линейной целевой
функцией и ограничениями»
Санкт-Петербург
Введение
В рамках изучения учебной дисциплины «Системы поддержки принятия решений» обучаемыми выполняется цикл из 7 лабораторных работ, в ходе проведения которых студенты приобретают необходимые умения в построении и исследовании математических моделей, описывающих различные классы задач выбора в сложных технико-экономических системах (ТЭС), а также получают навыки решения указанных задач с использованием современных технических и программных средств, разработанных на базе новых информационных технологий.
При этом в ходе последовательного выполнения лабораторных работ предполагается постоянное усложнение решаемых задач выбора, заключающееся в переходе от линейных математических моделей выбора с линейной целевой функцией и ограничениями к нелинейным моделям, от детерминированных моделей к стохастическим моделям, от статических моделей выбора к динамическим моделям выбора, от задач выбора с одним отношением предпочтения к задачам выбора с многими отношениями предпочтения. Главная особенность исследования всех перечисленных математических моделей, описывающих процессы подготовки и принятия решений, заключается в том, что их рассмотрение осуществляется с единых позиций, базирующихся на методологических и методических основах системного анализа и теории принятия решений. Вместе с тем, для облегчения понимания студентами в ходе проведения лабораторных работ особенностей применения изучаемых методов и алгоритмов, в качестве основной математической модели, описывающей процессы подготовки и принятия решений, была выбрана модель с линейной целевой функцией и ограничениями. Традиционно указанные математические модели применяются для описания и исследования задач линейного программирования. Однако существуют специально разработанные подходы (методики), позволяющие, используя методы декомпозиции, релаксации, детерминизации и скаляризации, сводить сложные задачи многокритериального выбора в условиях неопределённости воздействия внешней среды к задаче линейного программирования.
1. цель лабораторной работы
Целью лабораторной работы является:
- закрепление теоретических знаний, получаемых студентами на лекционных и самостоятельных занятиях по решению задач линейного программирования;
- развитие практических навыков в постановке задач линейного программирования, в проведении их технико-экономической интерпретации, умения составлять по содержательному описанию задачи её математическую модель;
- ознакомление с особенностями применения современных пакетов прикладных программ для решения задач линейного программирования, приобретение навыков в их постановке и решении на ПЭВМ;
- приобретение навыков в методике исследования и решения задач выбора в сложных технико-экономических системах с использованием современных инструментальных программных средств, базирующихся на новых информационных технологиях.
В связи с этим при подготовке к проведению лабораторной работы обучаемым следует уяснить такие вопросы:
- методологические и методические основы подготовки и принятия решений в сложных технико-экономических системах (ТЭС);
- классификация задач выбора с одним отношением предпочтения;
- содержательная постановка задачи о назначениях, транспортной задачи, задачи распределения ресурсов в ТЭС;
- формализация задач выбора с линейной целевой функцией и ограничениями;
- формализация двойственных задач выбора с линейной целевой функцией и ограничениями;
- графический метод решения задач линейного программирования;
- симплекс-метод отыскания оптимального решения основной задачи линейного программирования;
- основные этапы решения задачи линейного программирования;
- особенности подготовки исходных данных и решения задач линейного программирования с использованием пакета прикладных программ QSB и табличного процессора Excel 7.0.
Понимание этих вопросов позволит успешно справиться с индивидуальным заданием по рассматриваемой лабораторной работе и получить необходимые практические навыки в постановке и решении с помощью ПЭВМ задач линейного программирования.
2. теоретические основы работы
Общая характеристика задач подготовки и принятия решений в сложных технико-экономических системах
Среди системных направлений науки ведущее место занимают системный анализ и системотехника. Системный анализ может рассматриваться как развитие,… К настоящему времени в мировой и отечественной литературе опубликовано… Одной из актуальных проблем, связанных с активной человеческой деятельностью всегда была и будет оставаться проблема…
Постановка задачи линейного программирования
Значительная часть задач принятия решения – это задачи распределения ресурсовмежду объектами.
Пусть имеется т видов ресурсов, каждый i-й ресурс в количестве bi (i=1...m).… В реальных задачах суммарное количество основных xj (j = 1...n) и дополнительных yi (i = 1...m) переменных всегда…
ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Из таб.2.1 видно, что для выпуска единицы продукции, например вида П2, требуется две единицы трудовых ресурсов, П3 – четыре единицы материальных… Таблица 2.1
Ресурсы (i)
Вид продукции ( j)
Запас… На основании исходных данных требуется составить математическую модель для определения плана выпуска продукции.
ПРОВЕРКА СБАЛАНСИРОВАННОСТИ ПЛАНОВ
Требование выпуска продукции без обеспечения его ресурсами – это ЧП. Нет, не то ЧП, которое «чрезвычайное происшествие», а то ЧП, которое «часто… К сожалению, часто имеет место несбалансированность планов по номенклатуре,… Сбалансированность планов по номенклатуре и ресурсов можно проверить с помощью моделирования на ЭВМ, и ответ будет…
ТРЕБОВАНИЯ СОВМЕСТНОСТИ УСЛОВИЙ
Рассмотрим неравенство а´х £ b. Если от неравенства мы хотим перейти к уравнению, то введём дополнительную переменную у и запишем… В общую постановку задачи оптимизации входят неравенства вида (i =1...т), где… В этой системе общее число неизвестных N = n+m, где п – число основных неизвестных xj; т – число дополнительных…
ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Линейное уравнение с двумя переменными может быть записано a1x1+a2x2 =b. Чтобы построить это уравнение, найдём точки пересечения с осями координат.… Разделим теперь левую и правую части уравнения на b и перепишем уравнение ,… Теперь вспомним неравенства. Если линейное уравнение с двумя переменных 2х1+х2=2 может быть представлено прямой на…
ИДЕЯ СИМПЛЕКС-МЕТОДА
Пример 2.3. Рассмотрим задачу (табл.2.5) оптимизации плана производства с целью получения максимальной прибыли
.
Правила составления симплекс-таблиц
Таблица 2.7
Базис
Свободные члены
Свободные переменные
х1
х2
х3
х4
у1
… Таблица 2.8
Базис
Свободные члены
Свободные… Таблица 2.9
Базис
Свободные члены
Свободные переменные
х1
х2
х3
…
ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
ДЗ по отношению к прямой составляют согласно правилам:
1) ЦФ ПЗ задаётся на max, тогда ЦФ ДЗ – на min, и наоборот;
2) матрица , составленная из коэффициентов в
Приложение 1
Варианты индивидуальных заданий на выполнение лабораторной работы
1. Прядильная фабрика для производства двух видов пряжи использует три типа сырья – чистую шерсть, капрон и акрил. В табл.П.1.1 указаны нормы расхода сырья, его общее количество, которое может быть использовано фабрикой в течение года, и прибыль от реализации тонны пряжи каждого вида.
Таблица П.1.1
Тип сырья
Нормы расхода сырья на 1 т пряжи (т)
Количество сырья (т)
Вид 1
Вид 2
Шерсть
Капрон
Акрил
0,5
а
0,5–а
0,2
0,6
0,2
b
c
Прибыль от реализации 1 т пряжи (р.)
Требуется составить годовой план производства пряжи с целью максимизации суммарной прибыли:
a
b
c
a
b
c
a
b
c
a
b
c
0,1
0,1
0,2
0,3
0,1
0,1
0,2
0,3
0,1
0,2
0,2
0,3
0,1
0,2
0,2
0,3
0,1
0,2
0,3
0,3
2. Нефтеперерабатывающий завод может использовать две различные технологии перегонки нефти для производства бензина, керосина и солярового масла. В табл.П.1.2 приведены данные, показывающие выход продукции, отходы, издержки производства (стоимость нефти, заработная плата, амортизация и т.п.) и загрузку оборудования в расчёте на 1 т переработанной нефти. Кроме того, указаны стоимость 1 т готовой продукции и суточный объём государственного заказа, который необходимо удовлетворить.
Таблица П.1.2
Наименование продукции
Виды продукции (т)
Технология 1
Технология 2
Бензин
Керосин
Солярное масло
Отходы
0,6
0,1
–
0,3
0,3
0,3
0,3
0,1
Издержки производства (р.)
Загрузка оборудования (маш.-ч)
а
0,2
b
0,05
Ресурс оборудования составляет 75 маш.-ч. в сутки. Все отходы должны пройти через очистные сооружения, производительность которых составляет с т/сут. Поставки нефти и спрос на всю продукцию завода неограничены.
Требуется составить суточный план производства с целью максимизации прибыли:
a
b
c
a
b
c
a
b
c
a
b
c
3. Цех выпускает три вида деталей, которые изготовляются на двух станках. На рис.П.1.1 показана технологическая схема изготовления каждого вида с указанием времени её обработки на станках. Задан суточный ресурс рабочего времени каждого станка: b мин для станка 1, с мин для станка 2. Стоимость одной детали вида 1, 2 и 3 составляет 3, 1 и 2 р. соответственно. Требуется составить суточный план производства деталей с целью максимизации стоимости выпущенной продукции:
Рис.П.1.1
a
b
c
a
b
c
a
b
c
a
b
c
4. Для производства трёх видов изделий (А, В, С) используется сырьё типа I, II, III, причём закупки сырья типа I и II ограничены возможностями поставщиков. В табл.П.1.3 приведены нормы затрат сырья, цены на сырьё и на изделия, а также ограничения по закупке сырья.
Таблица П.1.3
Тип сырья
Цена 1 кг сырья (р.)
Нормы затрат сырья на одно изделие (кг)
Ограничения по закупке сырья (кг)
А
В
С
I
II
III
b
a
–
Цена одно изделия (р.)
6b+12
5b+22
c
Требуется определить план производства продукции с целью максимизации прибыли:
a
b
c
a
b
c
a
b
c
a
b
c
5. На фабрике производится ткань двух артикулов. Любая из этих тканей может изготавливаться на станках одного или двух типов. В табл.П.1.4 указаны: производительность станка каждого типа при изготовлении траки артикулов 1 и 2; суммарные мощности станочного парка фабрики в расчёте на одну рабочую неделю; трудовые затраты по обслуживанию станков в минутах рабочего времени на 1 ч работы станка; цена метра ткани каждого артикула.
Таблица П.1.4
Тип станков
Мощности (тыс.ч)
Трудозатраты (мин/ч)
Производительность (м/ч)
Артикул 1
Артикул 2
b
a
b
Цена 1 м ткани (р.)
c
Известно также, что недельный ресурс трудозатрат на обслуживание станков равен 6000 ч.
Требуется составить недельный план выпуска тканей с целью максимизации стоимости изготовленной продукции:
a
b
c
a
b
c
a
b
c
a
b
c
6. Строителям требуются комплекты досок, каждый из которых состоит из а досок длиной 1,5 м и b досок длиной 0,6 м. Как следует распилить с четырёхметровых досок, чтобы получить наибольшее количество указанных комплектов?
a
b
c
a
b
c
a
b
c
a
b
c
7. Чаеразвесочная фабрика выпускает чай сорта А и Б, смешивая три ингредиента: индийский, грузинский и краснодарский чай. В табл.П.1.5 приведены нормы расхода ингредиентов, объём запасов каждого ингредиента и прибыль от реализации 1 т чая сорта А и Б.
Таблица П.1.5
Ингредиенты
Нормы расхода (т/т)
Объём запасов (т)
А
Б
Индийский чай
Грузинский чай
Краснодарский чай
0,5
0,2
0,3
0,2
0,6
0,2
Прибыль от реализации 1 т продукции (р.)
Требуется составить план производства чая сорта А и Б с целью максимизации суммарной прибыли.
8. Нефтеперерабатывающий завод производит за месяц 1500 000 л алкилата, 1200 000 л крекинг-бензина и 1300 000 л изопентона. В результате смешивания этих компонентов в пропорциях 1:1:1 и 3:1:2 получается бензин сорта А и Б соответственно. Стоимость 1000 л бензина сорта А и Б соответственно равна 90 р. и 120 р.
Определить месячный план производства бензина сорта А и Б, максимизирующий стоимость выпущенной продукции.
9. Рацион кормления коров на молочной ферме может состоять из трёх продуктов – сена, силоса и концентратов. Эти продукты содержат питательные вещества – белок, кальций и витамины. Численные данные представлены в табл.П.1.6. В расчёте на одну корову суточные нормы потребления белка и кальция составляют не менее 2000 и 210 г соответственно. Потребление витаминов строго дозировано и должно быть равно 87 мг в сутки.
Таблица П.1.6
Продукты
Питательные вещества
Белок (г/кг)
Кальций (г/кг)
Витамины (мг/кг)
Сено
Силос
Концентраты
Составить самый дешёвый рацион, если стоимость 1 кг сена, силоса и концентрата равна соответственно 1,5; 2 и 6 к.
10. В области имеются два цементных завода и три потребителя их продукции – домостроительных комбината. В табл.П.1.7 указаны суточные объёмы производства цемента, суточные потребности в нём комбинатов и стоимость перевозки 1 т цемента от каждого завода к каждому комбинату.
Таблица П.1.7
Заводы
Производство цемента (т/сут)
Стоимость перевозки 1 т цемента (р.)
Комбинат 1
Комбинат 2
Комбинат 3
Потребности в цементе (т/сут)
Требуется составить план суточных перевозок цемента с целью минимизации транспортных расходов.
11. Перед проектировщиками автомобиля поставлена задача сконструировать самый дешёвый кузов, используя листовой металл, стекло и пластмассу. Основные характеристики материалов представлены в табл.П.1.8.
Общая поверхность кузова (вместе с дверьми и окнами) должна составить 14 м2; из них не менее 4 м2 и не более 5 м2 следует отвести под стекло. Масса кузова не должна превышать 150 кг. Сколько металла, стекла и пластмассы должен использовать наилучший проект?
Таблица П.1.8
Характеристики
Материалы
Металл
Стекло
Пластмасса
Стоимость (р./м2)
Масса (кг)
12. В металлургический цех в качестве сырья поступает латунь (сплав меди с цинком) четырёх типов с содержанием цинка 10, 20, 25 и 40% по цене 10, 30, 40 и 60 к. за 1 кг соответственно. В каких пропорциях следует переплавлять это сырьё в цехе, чтобы получить сплав (латунь), содержащей 30% цинка и при этом самый дешёвый?
13. Цех выпускает три вида деталей, которые изготовляются на трёх станках. На рис.П.1.2 показана технологическая схема изготовления детали каждого вида с указанием времени её обработки на станках. Суточный ресурс рабочего времени станков 1, 2 и 3 составляет соответственно 890, 920 и 840 мин. Стоимость одной детали вида 1, 2 и 3 равна соответственно 3, 1 и 2 р.
Рис.П.1.2
Требуется составить суточный план производства с целью максимизации стоимости выпущенной продукции.
14. Объединение «Комфорт» производит холодильники, газовые плиты, морозильные шкафы и электропечи по цене 200, 180, 250 и 100 р. соответственно. Постоянным фактором, ограничивающим объёмы производства, является фиксированная величина трудовых ресурсов – 12000 человеко-часов в месяц. Выяснилось, однако, что в ближайший месяц дефицитной будет и листовая сталь для корпусов указанных изделий, поскольку поставщики смогут обеспечить лишь 7000 м2 этого материала.
Требуется составить план производства на данный месяц, с тем чтобы максимизировать стоимость выпущенной продукции. Известно, что для изготовления холодильника требуется 2 м2 листовой стали и 3 чел.-ч рабочего времени, для газовой плиты – соответственно 1,5 м2 и 3 чел.-ч, для морозильного шкафа – 3 м2 и 4 чел.-ч, для электропечи – 1 м2 и 2 чел.-ч.
15. Участник экспедиции «Северный полюс» укладывает рюкзак, и ему требуется решить, какие положить продукты. В его распоряжении имеются мясо, мука, сухое молоко и сахар. В рюкзаке для продуктов осталось лишь 45дм3 объёма, и нужно, чтобы суммарная масса продуктов не превосходила 35 кг. Врач экспедиции рекомендовал, чтобы мяса (по массе) было больше муки по крайней мере в два раза, муки не меньше молока, а молока по крайней мере в восемь раз больше, чем сахара. Сколько и каких продуктов нужно положить в рюкзак, с тем, чтобы суммарная калорийность продуктов была наибольшей? Характеристики продуктов приведены в табл.П.1.9.
Таблица П.1.9
Характеристики
Продукты
Мясо
Мука
Молоко
Сахар
Объём (дм3/кг)
Калорийность (ккал/кг)
1,5
16. На мебельной фабрике требуется раскроить 5000 прямоугольных листов фанеры размером 4´5 м каждый, с тем чтобы получить два вида прямоугольных деталей: деталь А должна иметь размер 2´2 м, деталь Б – размер 1´3 м. Необходимо, чтобы деталей А оказалось не меньше, чем деталей Б. Каким образом следует производить раскрой, чтобы получить минимальное (по площади) количество отходов?
17. Для серийного производства некоторого изделия требуются комплекты заготовок профильного проката. Каждый комплект состоит из двух заготовок длиной 1800 мм и пяти заготовок длиной 700 мм. Как следует раскроить 770 полос проката стандартной длины 6000 мм, чтобы получить наибольшее количество указанных комплектов?
18. Колхоз может засеять свои поля пшеницей четырёх сортов, урожайность которых зависит от того, будет ли лето дождливым или сухим. Соответствующие данные приведены в табл.П.1.10. Какие сорта пшеницы и в какой пропорции следует сеять, чтобы максимизировать гарантированный (не зависящий от погоды) урожай?
Таблица П.1.10
Погода
Урожайность (ц/га)
Сорт 1
Сорт 2
Сорт 3
Сорт 4
Дождливая
Сухая
19. На звероферме могут выращиваться песцы, черно-бурые лисицы, нутрии и норки. Для их питания используются три вида кормов. В табл.П.1.11 приведены нормы расхода кормов, их ресурс в расчёте на день, а также прибыль от реализации одной шкурки каждого зверя.
Таблица П.1.11
Вид корма
Нормы расхода кормов (кг/день)
Ресурс кормов (кг)
Песец
Лиса
Нутрия
Норка
I
II
III
Прибыль р./шкурка
Определить, сколько и каких зверьков следует выращивать на ферме, чтобы прибыль от реализации шкурок была наибольшей.
20. Завод изготовляет корпуса для холодильников и комплектует их оборудованием, поставляемым без ограничений другими предприятиями. В табл.П.1.12 указаны нормы трудозатрат, затрат материалов для изготовления корпусов, ограничения по этим ресурсам и расчёте на месяц и прибыль от реализации холодильника каждой из пяти марок.
Таблица П.1.12
Наименование ресурса
Марка холодильника
Объём ресурса
Трудозатраты (чел.-ч)
Металл (м2)
Пластик (м2)
Краска (кг)
Прибыль (р.)
Найти месячный план выпуска холодильников, максимизирующий прибыль.
21. Для серийного изготовления детали механический цех может использовать пять различных технологий её обработки на токарном, фрезерном, строгальном и шлифовальном станках. В табл.П.1.13 указано время (в минутах) обработки детали на каждом станке в зависимости от технологического способа, а также общий ресурс рабочего времени станков каждого вида за одну смену.
Таблица П.1.12
Станки
Марка холодильника
Ресурс времени станков (мин)
Токарный
Фрезерный
Строгальный
Шлифовальный
Требуется указать, как следует использовать имеющиеся технологии, с тем чтобы добиться максимального выпуска продукции.
22. В трёх пунктах отправления сосредоточен однородный груз в количествах, соответственно равных 420, 380 и 400 т. Этот груз необходимо перевезти в три пункта назначения в количествах, соответственно равных 260, 520 и 420 т. Тарифы перевозок 1 т груза из каждого пункта отправления в каждый пункт назначения являются известными величинами и задаются матрицей
.
Найти план перевозок, обеспечивающий вывоз имеющегося в пунктах отправления и завоз необходимого в пунктах назначения груза при минимальной общей стоимости перевозок.
23. Кондитерская фабрика для производства трёх видов карамели А, В и С использует три вида основного сырья: сахарный песок, патоку и фруктовое пюре. Нормы расхода сырья каждого вида на производство 1 т карамели данного вида приведены в таблице.
В ней же указано общее количество сырья каждого вида, которой может быть использовано фабрикой, а также приведена прибыль от реализации 1 т карамели данного вида.
Вид сырья
Марка холодильника
Объём ресурса
А
В
С
Сахарный песок
Патока
Фруктовое пюре
0,8
0,4
–
0,5
0,4
0,1
0,6
0,3
0,1
Прибыль от реализации 1 т продукции (р.)
Найти план производства карамели, обеспечивающий максимальную прибыль от её реализации.
24. При откорме животных каждое животное ежедневно должно получить не менее 60 ед. питательного вещества А, не менее 50 ед. вещества В и не менее 12 ед. вещества С. Указанные питательные вещества содержат три вида корма. Содержание единиц питательных веществ в 1 кг каждого из видов корма приведено в следующей таблице:
Питательные вещества
Количество единиц питательных веществ на 1 кг корма вида
I
II
III
А
В
С
Составить дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах, если цена 1 кг корма I вида составляет 9 коп., корма II вида – 12 коп. и корма III вида – 10 коп.
25. В т пунктах могут быть размещены предприятия, производящие некоторую однородную продукцию Эта продукция поступает в п пунктов её потребления, причём в j-м пункте потребности в продукции равны aj единицам. Затраты, связанные с доставкой единицы продукции с i-го пункта отправления в j-й пункт потребления, составляют ci j руб. Известно, что в i-м пункте изготовления продукции максимальный объём её производства не может превышать bi единиц, а затраты, связанные с изготовлением единицы продукции, составляют di руб. Определить такое размещение предприятий, при котором обеспечиваются потребности в продукции в каждом из пунктов её потребления при наименьших общих затратах, связанных с производством и доставкой продукции.
26. Для производства п видов изделий предприятие использует т групп взаимозаменяемого оборудования. Изделий i-го вида необходимо изготовить Bi единиц (), причём j-я группа оборудования может быть занята изготовлением изделий не больше чем аj часов (). Время изготовления одного изделия i-го вида на j-й группе оборудования равно ai j часам, а цена производства равна ci j руб. Определить, сколько изделий данного вида с использованием каждой из групп оборудования следует изготовить, чтобы произвести нужное количество изделий каждого вида при наименьшей общей стоимости их изготовления.
27. При выращивании некоторой культуры (или группы родственных культур) может быть использован i-й вид удобрений в количестве, не большем, чем bi кг (). Вся посевная площадь содержит п почвенно-климатических зон, причём площадь j-й зоны равна dj га (). Внесение на каждый гектар площади j-й зоны 1 кг удобрений i-го вида увеличивает среднюю урожайность на ci j центнеров. Требуется распределить выделенный фонд удобрений между посевными зонами так, чтобы суммарный прирост урожайности культур за счёт внесения удобрений был максимален.
28. Для производства чугунного литья используется п различных исходных шихтовых материалов (чугун различных марок, стальной лом, феррофосфор и др.). Химический состав чугунного литья определяется содержанием в нём химических элементов (кремния, марганца, фосфора и др.). Готовый чугун должен иметь строго определённый химический состав, который задаётся величинами Hj, представляющими собой доли (в процентах) j-го химического элемента в готовом продукте. При этом известны величины: hi j – содержание (в процентах) j-го химического элемента в i-м исходном шихтовом материале; ci – цена единицы каждого i-го шихтового материала. Определить состав шихты, обеспечивающий получение литья заданного качества при минимальной общей стоимости используемых шихтовых материалов.
29. Для производства столов и шкафов мебельная фабрика использует необходимые ресурсы. Нормы затрат ресурсов на одно изделие данного вида, прибыль от реализации одного изделия и общее количество имеющихся ресурсов каждого вида приведены в следующей таблице:
Ресурсы
Нормы затрат ресурсов на одно изделие
Общее количество ресурсов
стол
шкаф
Древесина (м3):
I вида
II вида
Трудоёмкость (человеко-час)
0,2
0,1
1,2
0,1
0,3
1,5
371,4
Прибыль от реализации одного изделия (р.)
Определить, сколько столов и шкафов фабрике следует изготовлять, чтобы прибыль от их реализации была максимальной.
30. Для производства двух видов изделий А и В используется токарное, фрезерное и шлифовальное оборудование. Нормы затрат времени для каждого из типов оборудования на одно изделие данного вида приведены в таблице. В ней же указан общий фонд рабочего времени каждого из типов оборудования, а также прибыль от реализации одного изделия.
Тип оборудования
Затраты времени (станко-ч) на обработку одного изделия
Общий фонд полезного рабочего времени оборудования (ч)
А
В
Фрезерное
Токарное
Шлифовальное
Прибыль от реализации одного изделия (р.)
Найти план выпуска изделий А и В, обеспечивающий максимальную прибыль от их реализации.
31. На мебельной фабрике из стандартных листов фанеры необходимо вырезать заготовки трёх видов в количествах, соответственно равных 24, 31 и 18 шт. Каждый лист фанеры может быть разрезан на заготовки двумя способами. Количество получаемых заготовок при данном способе раскроя приведено в таблице. В ней же указана величина отходов, которые получаются при данном способе раскроя одного листа фанеры.
Вид заготовки
Количество заготовок (шт.) при раскрое по способу
I
II
III
Величина отходов (см2)
Определить, сколько листов фанеры и по какому способу следует раскроить так, чтобы было получено не меньше нужного количества заготовок при минимальных отходах.
32. На звероферме могут выращиваться чёрно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используется три вида кормов. Количество корма каждого вида, которое должны ежедневно получать лисицы и песцы, приведено в таблице. В ней же указаны общее количество корма каждого вида, которое может быть использовано зверофермой, и прибыль от реализации одной шкурки лисицы и песца.
Вид корма
Количество единиц корма, которое ежедневно должны получать
Общее количество корма
лисица
песец
I
II
III
Прибыль от реализации одной шкурки (р.)
Определить, сколько лисиц и песцов следует выращивать на звероферме, чтобы прибыль от реализации их шкурок была максимальной.
Приложение 2
Использование пакета прикладных программ qsb в процессе принятия решений
П.2.1. Общие сведения о QSB
При изложении данного материала воспользуемся материалом учебного пособия [10].
QSB – это набор программ (русифицированный авторами пособия), с помощью которого можно «проигрывать» различные варианты решения экономических и производственных задач, выявлять оптимальные из них и анализировать полученные результаты, используя различные методы.
Запуск QSBосуществляется вводом команды: progl и, после появления функционального меню, нажатием цифры 9 . Далее на экране появится главное менюсистемы:
QSB - Количественные Системы для бизнеса!
Код программа
Код программа
1 Линейное программирование
2 Целочисленное программирование
3 Транспортная задача
4 Задача о назначениях
5 Сетевое моделирование (NET)
6 Сетевое моделирование (СРМ)
7 Сетевое моделирование (PERT
8 Динамическое программирование)
9 Управление запасами
А Теория очередей (расписаний)
В Имитационное моделирование
С Вероятностные модели
D Марковские модели
Е Экстраполяция тенденций
F Определение типа принтера
G Выход из QSB
Линейное программирование решает задачи ЛП, включающие от 40 переменных (без учёта дополнительных и искусственных) и 40 ограничений (без учёта граничных условий), используя симплекс-метод.
Целочисленное программированиереализует алгоритм метода ветвей и границ для решения смешанных задач целочисленного программирования размерностью до 20 переменных и 20 ограничений.
Транспортная задача решает транспортные задачи, содержащие до 50 пунктов отправления и до 50 пунктов назначения, используя для получения начального допустимого решения метод северо-западного угла и метод аппроксимации Фогеля, а для оптимального плана – метод потенциалов.
Задача о назначениях предназначена для решения Венгерским методом задач о назначении, включающих до 60 работ и 60 кандидатов.
Сетевое моделирование (NET)содержит три алгоритма для анализа сетей размерностью до 150 ветвей и до 75 узлов: алгоритм кратчайшего пути (определяет кратчайший путь от начального узла сети до любого другого), алгоритм максимального потока (находит максимальный поток от начального узла до конечного) и алгоритм минимального размаха дерева (устанавливает минимальную длину полного пути.
Сетевое моделирование (СРМ) определяется раннее и позднее время начала и окончания работ методом критического пути для сетей, включающих до 200 работ.
Сетевое моделирование (PERT)анализирует сети объёмом до 200 работ методом PERT.
Динамическое программирование решает три задачи ДП размерностью до 20 этапов с 50 пунктами в каждом: задачу о дилижансе, задачу о рюкзаке, задачу управления запасами.
Теория очередей (расписаний) анализирует работу одноканальных и многоканальных систем массового обслуживания с ограниченной и неограниченной длиной очереди и различными законами распределения времени обслуживания.
Имитационное моделированиеиспользует метод Монте-Карло для анализа систем очередей с 20 каналами обслуживания, 20 очередями, 100 заявками в очереди максимум.
Вероятностные модели обеспечивает проведение дисперсионного и байесовского анализа, анализа платёжной матрицы и дерева решений. При дисперсионном анализе по заданным исходным и вероятностям вычисляется среднее и дисперсия. При байесовском анализе по априорным вероятностям состояний природы и условным вероятностям исходов определяются совместные, безусловные и апостериорные вероятности. При анализе платёжной матрицы размерностью до 40 состояний природы и до 40 альтернатив рассчитываются различные критерии. Программа анализирует деревья решений, включающие до 80 ветвей с заданной вероятностью.
Марковские модели позволяют найти вероятность нахождения системы в заданном состоянии в заданное время с помощью марковских моделей (общее число состояний – не более 50).
Экстраполяция тенденций вычисляет простое и скользящее среднее, производит простое и двойное экспоненциальное сглаживание, а также линейную регрессию.
Определение типа принтера. В начале каждого сеанса работы необходимо задать тип принтера (если планируется его использование), для чего и предусмотрена эта опция.
Выход из QSB служит для окончания работы пользователя с системой.
Для выбора пункта меню нужно выделить его курсором с помощью клавиш ¯ , , ¬ , ® , и нажать Enter ; или нажать «горячую клавишу», соответствующую коду программы.
При работе с пунктами 1-Е на экране появляется функциональное меню:
Добро пожаловать в линейное программирование!
Варианты работы с LP:
Если вы работаете с системой впервые, то выберите опцию 1.
Опция
Функция
Помощь по LP
Ввод новой задачи
Чтение задачи с диска
Просмотр/Печать исходных данных
Решение задачи
Запись задачи на диск
Изменение задачи
Просмотр/Печать итогового решения
Возврат в главное меню
Выход из QSB
Функция 1 – выводит краткое описание используемой программы (в данном случае ЛП); 2 – служит для ввода исходных данных новой задачи непосредственно с клавиатуры; 3 – предназначена для ввода исходных данных задачи из файла; 4 – осуществляет вывод исходных данных на экран и/или принтер; 5 – обеспечивает решение задачи и просмотр этого процесса по шагам; 6 – сохраняет исходные данные задачи в файле; 7 – производит корректировку исходных данных путём изменения количества переменных, ограничений или значений коэффициентов задачи; 8 – выводит на экран и/или принтер итоговое решение; 9 – обеспечивает выход в главное меню системы; 0 – позволяет окончить работу с системой.
Процедура принятия решения с использованием QSB сводится к четырём этапам: постановке задачи, подготовке исходных данных, решению задача и анализу полученных результатов. Рассмотрение этих этапов для различных видов задач будет изложено далее.
П.2.2. Решение задач линейного программирования
В нашей задаче: ЦФ на максимум, 4 переменных и 7 ограничений. Условия… Выберите опцию Линейное программирование в главном меню системы. На экране появится функциональное меню:
…
П.2.3. Решение задач целочисленного программирования
Подготовьте ЭММ задачи для решения на ЭВМ, исключив условия неотрицательности переменных:
В нашей задаче: ЦФ на максимум, 10 переменных и 9 ограничений.
П.2.4. Решение транспортной задачи
Пример. Требуется составить такой план прикрепления трёх потребителей к трём поставщикам, при котором общая стоимость перевозок будет минимальной.… Обозначим через xi j – количество единиц груза, запланированных к перевозке от… Тогда ЭММ:
П.2.5. Решение задачи о назначениях
Итак, в нашей задаче: ЦФ на минимум, 4 кандидата и 4 работы.
Выберите опцию 4 – Задача о назначениях в главном меню системы. На экране… В функциональном меню выберите опцию 2 – Ввод новой задачи, введите название задачи (например, prim4), ответьте на…
П.2.8. Решение задач динамического программирования
Подготовьте исходные данные задачи для решения на ЭВМ: определите количество этапов в задаче (4 задачи), тип задачи (задача о дилижансе).
Выберите опцию 8 – Динамическое программирование в главном меню системы.
В функциональном меню выберите опцию 2 – Ввод новой задачи, введите название задачи (например, prim7 ), ответьте на…
П.2.9. Решение вероятностных моделей
Выберите опцию С – Вероятностные модели в главном меню системы.
В функциональном меню выберите опцию 2 – Ввод новой задачи, введите название… Введите данные как показано ниже:
S1: 0.2_____ S2: 0.3_____ S3: 0.5____
Сост. Альт.
S1: А: 9____ А2: …
Приложение 3
Поиск оптимальных решений задач линейного программирования с использованием программных средств excel 7.0
Решение задач линейного программирования с использованием Excel 7.0 осуществляется с помощью инструментального средства Поиск решения. Для запуска… После загрузки инструмента Поиск решения в списке опций ниспадающего меню… В поле ввода Установить целевую ячейку указывается ссылка на ячейку с целевой функцией, значение которой будет…
Литература
1. Акулич И.Л. Математическое программирование в примерах и задачах: Уч. пособие для студентов экон. спец. вузов. – М.: Высшая школа, 1998.
2. Акулич И.Л., Ворончук И.С. Задачи нелинейного и динамического программирования. – Рига: Изд-во ЛГУ, 1989..
3. Иванилов Ю.П., Лотов А.В. Математические модели принятия решений в управлении и экономике. – М.: Наука, 1979.
4. Ларичев О.И. Наука и искусство принятия решений. – М.: Наука, 1979.
5. Саати Т. Принятие решений. Метод анализ иерархий: Пер. с англ. – М.: Ради и связь, 1989.
6. Князевский Н.В., Князевская В.С. Принятие раскованных решений в экономике и бизнесе: Уч. пособие. – М.: Контур, 1998.
7. Фатхутдинов Р.А. Разработка управленческого решения. – Учебник, М.: ЗАО «Бизнес-школа Интел-Синтез», 1998.
8. Андрейчиков А.В., Андрейчикова О.Н. Анализ, синтез, планирование решений в экономике. – Учебник. – М.: Финансы и статистика, 2000.
9. Красников В.С. Разработка управленческих решений. – СПб.: Изд-во СЗАГС, 1999.
10. Глухов В.В., Медников М.Д., Коробко С.Б. Экономико–математические методы и модели в менеджменте. – Уч. пособие. – СПб.: Изд-во СПб ГТУ, 1999.
11. Курицкий Б.Я. Поиск оптимальных решений средствами Excel 7.0. – СПб., ВНV Санкт-Петербург, 1997.
ОГЛАВЛЕНИЕ
введение.............................................................................................. 2
1. цель лабораторной работы.......................................................... 3
2. теоретические основы работы................................................ 4
2.1. Общая характеристика задач подготовки и принятия решений в сложных технико-экономических системах 4
2.2. Постановка задачи линейного программирования 8
2.2. ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.................................................................... 9
2.4. ПРОВЕРКА СБАЛАНСИРОВАННОСТИ ПЛАНОВ..................... 12
2.5. ТРЕБОВАНИЯ СОВМЕСТНОСТИ УСЛОВИЙ............................ 15
2.6. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.................................................................. 16
2.7.ИДЕЯ СИМПЛЕКС-МЕТОДА........................................................... 19
2.8. ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 21
3. Методические указания по выполнению лабораторной работы.............................................................................................. 24
4. форма отчётности по выполненной лабораторной работе 25
Приложение 1. варианты индивидуальных заданий на выполнение лабораторной работы............................................................. 26
Приложение 2. использование пакета прикладных программ qsb в процессе принятия решений............................................. 37
П.2.1. Общие сведения о QSB.............................................................. 37
П.2.2. Решение задач линейного программирования...................... 39
П.2.3. Решение задач целочисленного программирования............ 46
П.2.4. Решение транспортной задачи................................................. 50
П.2.5. Решение задачи о назначениях................................................ 53
П.2.6. Решение сетевых задач (NET)................................................... 55
П.2.7. Решение сетевых задач (СРМ).................................................. 57
П.2.8. Решение задач динамического программирования.............. 60
П.2.9. Решение вероятностных моделей............................................. 62
Приложение 3. поиск оптимальных решений задач линейного программирования с использованием программных средств excel 7.0......................................................................... 63
литература................................................................................................ 65