Сведение многокритериальной задачи к однокритериальной.
Министерство образования и науки
Российской Федерации
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ
(ТУСУР)
Кафедра автоматизации обработки информации
(АОИ)
УТВЕРЖДАЮ
Зав. кафедрой АОИ,
профессор
___________Ю.П. Ехлаков
«___»___________2013 г.
Методические указания по выполнению лабораторных работ по дисциплине «Методы принятия управленческих решений»
для студентов направления подготовки
081100.62 – «Государственное и муниципальное управление»
Разработчик
доцент кафедры АОИ
___________Турунтаев Л.П.
20013 г.
СОДЕРЖАНИЕ
| 1.Введение……………………………………………………..…….. | 4 |
| 2. Моделирование деятельности объектов управления.………….. | 5 |
| 2.1. Постановка однокритериальной задачи использования ресурсов в условиях определенности……………………………… | 8 |
| 2.2. Задача транспортного типа…………………………………….. | 8 |
| 2.3.Задача о назначениях……………………………………………. | 8 |
| 2.4. Задача о коммивояжере………………………………………… | 9 |
| 2.5. Задача векторной оптимизации………………………………... | 10 |
| 3. Моделирование деятельности субъектов управления.……….... | 11 |
| 4. Требования к содержанию и оформлению лабораторных работ…………………………………………………………………. | 16 |
| Лабораторная работа 1. Решение и анализ моделей задач линейного программирования……………………………………… | 17 |
| Лабораторная работа 2. Задачи линейного программирования транспортного типа…………………………………………………. | 18 |
| Лабораторная работа 3. Моделирование, решение и анализ однокритериальных задач управления…………………………….. | 20 |
| Лабораторная работа 4. Моделирование и решение задач целочисленного программирования………………………………. | 29 |
| Лабораторная работа 5. Моделирование и решение задач управления векторной оптимизации……………………………….. | 38 |
| Лабораторная работа 6. Однокритериальные задачи принятия решений в условиях риска и неопределенности………………….. | 42 |
| Лабораторная работа 7. Многокритериальные задачи принятия решений в условиях риска и неопределенности………………….. | 47 |
| Лабораторная работа 8. Групповые методы принятия маркетинговых решений. Знакомство с компьютерной игрой «Дельта»……………………………………………………………… | 49 |
| Лабораторная работа 9. Групповые методы принятия производственных решений. ………………………………………. | 50 |
| 4.Список используемой литературы…..…………………….......... | 51 |
|
|
|
|
|
|
ВВЕДЕНИЕ
Данное руководство предназначено для выполнения лабораторных работ по курсу «Методы принятия управленческих решений» с целью закрепления знаний по моделям и алгоритмам выбора решений в условиях определенности, риска и неопределенности, приобретения навыков моделирования и решения задач принятия решений с помощью пакетов прикладных программ (ППП).
Руководство включает краткое описание задач принятия решений, методы их решения, задания на выполнение лабораторных работ.
2. МОДЕЛИРОВАНИЕ ДЕЯТЕЛЬНОСТИ ОБЪЕКТОВ УПРАВЛЕНИЯ.
Постановка однокритериальной задачи использования ресурсов в условиях определенности
Рассмотрим задачу линейного программирования об оптимальном использовании ресурсов.
|
|
|
Пусть предприятие изготавливает n видов продуктов (рис. 2.1), располагая m видами ресурсов в количестве 
Известна матрица 
расходов i-го ресурса на изготовление одной единицы j-го продукта 
Эффективность (прибыль) выпуска единицы j-го продукта равна 
. Требуется определить план выпуска продукции 
максимизирующий прибыль предприятия.
  |
Для задачи, сформулированной выше, математическая модель имеет следующий вид: максимизировать
(2.1)
при ограничениях:
, (2.2)
. (2.3)
Ограничения (2.2) представляют собой многогранное множество допустимых решений ЗЛП. Если многогранное множество ограничено, то оно называется многогранником. Многогранное множество в ЗЛП выпукло, содержит крайние (угловые) точки 
удовлетворяющие следующим условиям
1) любая точка Х может быть представлена как выпуклая линейная комбинация угловых точек;
2) каждой угловой точке соответствует базисный допустимый план ЗЛП.
|
|
|
Базисный план задачи (2.1)–(2.2) всегда имеет не более m (если ограничения являются линейно независимыми (m < n)) отличных от нуля координат. Они называются базисными. Если таких координат, отличных от нуля, меньше m, то базисный план называется вырожденным. Допустимый план X ЗЛП называется оптимальным, если целевая функция (2.1) достигает своего экстремального значения в точке(ах) 
Оптимальный план 
всегда является базисным планом.
На рис. 2.2 представлена геометрическая интерпретация ЗЛП для случая двух переменных 
и 
. Геометрически целевая функция — семейство параллельных прямых линий уровня цели Z, множество допустимых решений — выпуклый многоугольник.
Для решения ЗЛП Г. Данцигом был предложен симплекс-метод. В основу симплекс-метода положено поэтапное движение к оптимуму от исходной угловой точки области допустимых решений к рядом лежащей угловой точке, позволяющее последовательно улучшать значение целевой функции. Так как угловая точка характеризуется m базисными переменными, то на каждом этапе встают вопросы: какие переменные выбирать за базисные, а какие — за небазисные. Ответы на вопросы дает симплекс-алгоритм, который характеризуется сходимостью (последовательностью улучшения решений) и конечностью в силу конечности множества угловых точек.
 |
Для любой задачи ЛП всегда существует обратная (двойственная) ей задача.
| Если прямая задача: | то двойственной будет задача: | |
 (2.4)
|  (2.7)
| |
 (2.5)
|
|  (2.8)
|
 (2.6)
|  2.9)
|
Пара задач (2.4)–(2.6) и (2.7)–(2.9) называется симметричной парой двойственных задач, где — двойственная оценка. В содержательной постановке, если 
— продукт, 
— ресурс, 
— прибыль, то в двойственной задаче — оценка ресурса (его дефицитность).
В линейном программировании существуют следующие теоремы двойственности [2, 3].
1. Если одна из двойственных задач ЛП имеет оптимальное решение, то и другая его имеет, причем 
в других случаях 
Если целевая функция одной из ЗЛП не ограничена, то система условий другой противоречива.
2. Чтобы допустимые решения X и Y пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:
Получить решение двойственной задачи можно из оптимальной симплекс-таблицы прямой задачи. Допустим из оптимальной симплекс-таблицы получили оптимальные значения основных и дополнительных переменных прямой и двойственной задач:
Строка 
| 
| 
| 
| 
| 
|
| Основные | Дополнительные | ||||
| Решение
| 
| 
| 
| 
| 
|
| Дополнительные | Основные | ||||
Решение 
| 
| 
|
| 
| 
|
Тогда:
(основные), 
— план выпуска продукции;
(дополнительные), 
— остаток ресурса ;
(основные) — оценка дефицитности ресурса i, отражающая изменение целевой функции при изменении ресурса на одну единицу;
(основные) = 
;
(дополнительные), 
свидетельствуют об убытке производства продуктов 
2.2. Задача транспортного типа
Имеется m поставщиков и n потребителей однородной продукции, возможности и потребности которых соответственно равны 
и 
, 
Стоимость перевозки одной единицы продукции из пункта i в пункт j равна 
Определить план перевозки продукции от поставщиков к потребителям 
, минимизирующий общую стоимость всех перевозок.
Математическая постановка задачи:
(2.10)
при ограничениях:
(2.11)
(2.12)
Ограничение (2.11) накладывается на спрос j-го потребителя, ограничение (2.12) — на возможности i-го поставщика. Если 
, то задача называется закрытой, в противном случае — открытой.
Задача о назначениях
Имеется m потенциальных исполнителей 
) соответственно одной из имеющихся m работ 
). Известны затраты 
на выполнение j-м исполнителем i-й работы. Требуется назначить каждого исполнителя на одну работу так, чтобы минимизировать суммарные затраты. Математическая постановка задачи:
(2.13)
при ограничениях:
(2.14)
(2.15)
|
(2.16)
Ограничение (2.14) указывает, что на каждую i-ую работу должен быть назначен только один исполнитель. Ограничение (2.15) указывает, что каждый j-й исполнитель должен быть назначен для выполнения только одной работы. Если число работ не равно числу потребителей, то задача о назначениях называется задачей открытого типа, в противном случае — закрытого.
Задача о коммивояжере
Коммивояжер (посыльный, развозчик заказанной продукции) должен посетить каждый из n пунктов, связанных между собой дорогами, только один раз и вернуться в исходный пункт. Его маршрут должен минимизировать суммарную длину пройденного пути.
Формализуем задачу.
Пусть известна матрица 
расстояний между пунктами i и j 
. В качестве неизвестной величины введем переменную
 |
Модель задачи о коммивояжере будет иметь вид
, (2.17)
при ограничениях:
; (2.18)
; (2.19)
. (2.20)
Еще одно ограничение сформулируем следующим образом: искомые переменные 
должны образовывать полный контур, включающий все пункты.
Ограничение (2.18) говорит о том, что коммивояжер должен в каждый пункт 
заехать только один раз, а ограничение (2.19) – из каждого пункта 
выехать только один раз. Ограничения (2.18)–( 2.20) и дополнительное ограничение на маршруте коммивояжера создают так называемый гамильтоновый контур (по имени ирландского математика У. Гамильтона).
2.5. Задача векторной оптимизации
В жизни целенаправленная деятельность человека устроена так, что приходится учитывать не одну, а сразу несколько целей. Оптимизация решения задачи отдельно по каждому из критериев приводит к различным вариантам. Решение задачи с учетом всех предлагаемых критериев находится в компромиссной области решений (множестве Парето). Множество компромиссных решений обладает свойством противоречивости: улучшение качества решений по одним критериям вызывает ухудшение качества других. Это обстоятельство и является причиной того, что методы решения многокритериальных задач предусматривают в том или ином виде учет мнения лица, принимающего решение. Чтобы выбрать из области Парето лучшие решения, ЛПР обязан ввести соответствующие принципы выбора компромиссного решения, приводящие к тому или иному методу решения задачи. Рассмотрим наиболее часто употребляемые методы решения многокритериальных задач.
Сведение многокритериальной задачи к однокритериальной.
Наибольшее распространение получил подход определения глобального критерия (суперкритерия) в виде взвешенной суммы критериев 
,
где 
— отнормированное значение i-го критерия ;
— коэффициент относительной важности i-го критерия (весовой коэффициент);
.
Выделение главного критерия
Критерии располагаются в порядке убывания важности. Решается задача по первому (важному) критерию, а в ограничениях прописываются дополнительно ещё условия на предельные изменения остальных критериев.
3. Метод последовательных уступок
Критерии располагаются в порядке убывания важности.
Решается задача по первому (важному) критерию. Определяется оптимальное решение и значение целевой функции по первому критерию. Далее решается задача по второму критерию, при этом в ограничении дополнительно прописывается ещё условие на изменение первого критерия (делается уступка ухудшения решения по первому критерию). И так далее для других критериев. На последнем шаге решается задача поиска решения по n-му критерию с учетом уступок по 
наиболее важным критериям, и решение этой задачи принимается в качестве решения исходной многокритериальной задачи.
3. МОДЕЛИРОВАНИЕ ДЕЯТЕЛЬНОСТИ СУБЪЕКТОВ УПРАВЛЕНИЯ.
В реальной практике выбор альтернативы под влиянием внешней среды, неподдающемуся точному прогнозу и имеющему случайный характер, приводит к одному из нескольких возможных исходов. Для осуществления выбора наилучшего решения необходимо оценивать возможные исходы альтернатив в зависимости от возможных ситуаций (состояний) внешней среды и целевых установок. Такая комплексная оценка решения не может быть произведена без участиясубъекта управления, без учета системы его взглядов (системы предпочтений) на ценность альтернатив.
Сделаем формальное описание задачи.
Пусть 
— множество возможных состояний;
— множество целей системы управления;
— множество альтернатив;
— множество исходов альтернатив.
Исход 
может быть представлен в виде функции трех аргументов, ставящей в соответствие каждой тройке 
величину 
. Матрицу 
называют матрицей исходов, оценочным функционалом, функцией предпочтения (в литературе даются и другие названия [1-3]).
Необходимо построить модель оценки альтернативных решений в соответствии с предпочтением ЛПР.
Для обеспечения комплексной оценки решений необходимо сформулировать для полного множества целей систему показателей (критериев), характеризующих степень их достижения. Множеству целей Z сопоставим множество критериев K. В частном случае каждой цели 
может быть сопоставлен один свой критерий 
.
Полученная в процессе подготовки решения информация о множестве целей, критериев их достижения, приоритетов целей и критериев, значений (качественных или количественных оценок) критериев по оцениваемым альтернативам в предполагаемых возможных ситуациях их реализации уменьшает неопределенность задачи и обеспечивает условия для выбора наилучшего решения.
Оценка альтернатив 
производится на базе возможной информации о критериях 
и предполагаемых состояниях внешней среды 
при реализации этих альтернатив (табл. 3.1).
Таблица 3.1 - Информация для оценки альтернатив
| Критерии | Состояния | ||
Мощность 
| Шкала измерения | Мощность 
| Описание
|
| Один критерий | Качественная и (или) количественная | Одно состояние | Определенность |
| Много критериев | Много состояний | Риск Неопределенность | |
Наличие и отсутствие той или иной информации позволяет выделить характерные типы индивидуальных задач принятия решений.
1. Один критерий k, качественные и (или) количественные оценки измерения альтернатив, одно состояние внешней среды e.
Для таких задач принятия решений в условиях определенности каждой альтернативе 
соответствует однозначно исход 
измеренный по критерию k, (табл. 3.2).
Наилучшей альтернативой будет считаться альтернатива 
у которой исход 
будет принимать экстремальное значение
2. Много критериев 
качественная и (или) количественная шкала измерения критериев, одно состояние внешней среды e.
Для таких многокритериальных ЗПР в условиях определенности исход альтернативы 
оценивается через критериальные оценки 
(табл. 3.3).
Таблица 3.3 - Задача векторной оптимизации
| Альтернатива | Исход | ||||
| … | 
| … | 
| |
|
| 
| … | 
| … | 
|
| . . . | . . . | … | . . . | … | . . . |
|
| 
| … | 
| … | 
|
| . . . | . . . | … | . . . | … | . . . |
| 
| … | 
| … | 
|
Для определения наилучшей альтернативы следует перейти к одной (ранговой либо абсолютной) шкале измерения критериев. Далее следует свернуть критерии в один и перейти к тривиальной задаче, рассмотренной выше. Либо применить известные схемы поиска компромиссных решений задач векторной оптимизации, либо применить известные методы решения многокритериальных ЗПР на основе четкого и нечеткого отношения предпочтения альтернатив (например, методы порогов несравнимости «Электра»), нечетких бинарных отношений [2].
3. Один критерий k, качественная или количественная шкала измерения, много состояний внешней среды 
Реализация альтернативы 
оцениваемой по критерию k в зависимости от ситуации 
может привести к исходу 
(табл. 3.4).
Таблица 3.4 - Задача ПР в условиях риска и неопределенности
| Альтернатива | Исход | ||||
| … |
| … | 
| |
|
| 
| … | 
| … | 
|
| . . . | . . . | … | . . . | … | . . . |
|
| 
| … |
| … | 
|
| . . . | . . . | … | . . . | … | . . . |
| 
| … | 
| … | 
|
Оценку исходов приводят к одной шкале измерения. Если известны вероятности 
наступления ситуаций 
то определение наилучшей альтернативы может быть произведено через критерии выбора решений в условиях риска (например, по критерию Байеса). При отсутствии информации о вероятностях в зависимости от наличия или отсутствия дополнительной информации о предпочтениях наступления ситуаций, от активности поведения (противодействия) элементов внешней среды применяют соответствующие способы выбора альтернатив.
4. Много критериев 
качественная и (или) количественная шкала измерения критериев, много состояний внешней среды 
Реализация альтернативы оцениваемой по критериям 
в ситуации 
может привести к исходу 
Для определения наилучшей альтернативы в зависимости от конкретной постановки ЗПР реализуют один из подходов:
1) по каждой альтернативе 
и по каждой ситуации получают методом свертки критериев критериальную оценку и переходят к рассмотренной выше типовой задаче 3;
2) по каждой альтернативе и по каждому критерию получают среднестатистическую оценку исхода 
затем переходят к рассмотренной выше типовой задаче 2.
В целом, для построения модели интегральной оценки решений следует придерживаться следующей схемы (рис. 3.2):
1) получить оценки предпочтительности каждого из решений по каждому критерию для каждой ситуации 
(данные критериальной оценки могут быть измерены в качественной и(или) количественной шкале);
2) в зависимости от конкретной постановки ЗПР следует получить комплексную оценку решений по совокупности критериев для каждой ситуации 
либо комплексную оценку решений по совокупности ситуаций для каждого критерия 
3) получить интегральную оценку решений на множестве критериев с учетом возможных ситуаций 
Модель оценки решений в частных постановках может быть записана в виде функциональной зависимости от параметров, характеризующих внешнюю среду, и локальных критериев. Как правило, модель оценки решений носит более сложный характер причинно-следственных связей и не описывается простыми формальными соотношениями.
4. ТРЕБОВАНИЯ К СОДЕРЖАНИЮ И ОФОРМЛЕНИЮ ЛАБОРАТОРНЫХ РАБОТ
Лабораторная работа представляется к защите в виде отчета, содержащего постановку и решение задач линейного программирования, указанных в задании на работу. В отчет включаются следующие пункты:
1) номер варианта и текст задачи;
2) таблица исходных данных;
3) математическая модель задачи в общем виде с указанием физического смысла переменных, целевой функции и ограничений;
4) математическая задача в числовой форме;
5) методы решения задачи;
6) результаты решения и их содержательная интерпретация, включая физический смысл всех вспомогательных переменных, введенных при решении задачи.
Лабораторная работа № 1
Тема: Решение и анализ моделей задач линейного программирования
Цель работы: освоить пакет прикладных программ (ППП) по линейному программированию (ЛП) и закрепить навыки поиска и анализа решения задач на ПЭВМ.
Задание на лабораторную работу:
1) ознакомиться с ППП ЛП;
2) получить задачу у преподавателя;
3) решить полученную задачу графически, решить ее с помощью ППП ЛП;
4) перейти от исходной задачи ЛП к двойственной, решить ее с помощью ППП ЛП;
5) показать справедливость утверждений теорем линейного программирования:
· о расположении точки оптимума в ограниченном и неограниченном множестве допустимых решений;
· о составляющих вектора оптимальных решений для вырожденного и невырожденного базисного плана, для множества оптимальных решений;
· о необходимом и достаточном условии существования точки оптимума прямой и двойственной задач;
6) найти связь между прямой и обратной задачами ЛП для случая вырожденности и множеством оптимальных решений;
7) дать анализ оптимального решения задачи ЛП.
8) подготовиться к защите по нижеприведенным контрольным вопросам.
Контрольные вопросы.
1. Дайте экономическую и геометрическую интерпретацию задач линейного программирования.
2. В чем заключается сущность методов математического программирования?
3. Какова идея симплекс-метода решения задач линейного программирования?
4. В чем отличие прямого, двойственного и двухэтапного симплекс-алгоритмов?
5. Сформулируйте теоремы двойственности.
6. Дайте экономическую интерпретацию теорем двойственности.
7. Как делается анализ дефицитности ресурсов? Как определить интервалы изменения запасов ресурсов при их дефицитности?
8. Как делается анализ цен на продукты?
Лабораторная работа № 2
Тема: Задачи линейного программирования транспортного типа
Цель работы: закрепить навыки решения задач транспортного типа: классические транспортные задачи, с промежуточными пунктами, о назначениях, о коммивояжере. Для каждой из задач дать математическую постановку, найти решение.
Задание на лабораторную работу:
1. Решить транспортную задачу.
Заводы автомобильной промышленности расположены в Москве, Нижнем Новгороде, Тольятти, Минске. Основные центры распределения продукции сосредоточены в пяти городах. Данные ежеквартальных объемов производства автомобилей указанных заводов, величины квартального спроса в центрах распределения автомобилей, стоимость перевозки одного автомобиля по железной дороге между заводами и центрами распределения получить у преподавателя.
Найдите план перевозок с помощью ППП :
а) исходной задачи двумя способами: симплекс-методом SIMPL и методом потенциалов TRANS;
б) задачи с измененными условиями исходной в сторону увеличения объемов производства программой TRANS;
в) задачи с измененными условиями исходной в сторону увеличения центров спроса;
г) задачи с условиями (в) и с учетом штрафа за недопоставленный автомобиль в первый центр — 3 тыс. руб., в третий — 3,5 тыс. руб.;
д) задачи с условиями (б) и обязательными отправками автомобилей с завода г. Нижнего Новгорода.
2. Придумать задачу о назначениях размерностью 
Решить ее программой SIMPL, TRANS и NAZN;
3. Задача о коммивояжере.
Рассыльному почтового отделения связи необходимо развести корреспонденцию подписчикам таким образом, чтобы минимизировать время на объезд подписчиков:
а) начиная и заканчивая почтовым отделением (считать, что оно располагается в одном здании с подписчиком № 1);
б) начиная с подписчика № 1 без возврата в почтовое отделение;
в) начиная с подписчика № 3 без возврата в почтовое отделение.
Решить задачу алгоритмами Литтла (программа KOMM) и исключения подциклов (программой NAZN).
Варианты задач получить у преподавателя.
4. подготовиться к защите по нижеприведенным контрольным вопросам.
Контрольные вопросы.
- Дайте содержательную и математическую постановку транспортной задачи линейного программирования.
2. Можно ли решить транспортную задачу линейного программирования симплекс-методом?
3. Сколько базисных переменных должно быть в допустимом плане решения транспортной задачи?
4. Сформулируйте математическую постановку двойственной ТЗЛП.
5. В чем идея распределительного метода решения транспортной задачи?
6. В чем отличие метода потенциалов от распределительного метода?
7. Укажите способы решения ТЗЛП с промежуточными пунктами.
8. Можно ли решить задачу о назначениях методом, используемым для решения ТЗЛП?
Лабораторная работа № 3
Тема: Моделирование, решение и анализ однокритериальных задач управления.
Цель работы:
1. Построение математической модели реальных ситуаций в виде задачи ЛП.
2. Изучение возможностей пакетов прикладных программ для решения ЗЛП
3. Решение индивидуальной задачи путем построения математической модели и использования пакета
4. Анализ решений задачи ЛП.
Порядок выполнения работы:
1. Знакомство с пакетом ПП
2. Изучение, математическое моделирование тестовой задачи.
3. Выполнение индивидуального задания.
a) составление математической модели ,
b) ввод и решение задачи,
c) анализ оптимального решения на чувствительность к изменениям исходных данных.
Составление подробного отчёта по лабораторной работе, в котором представляется:
- формулировка индивидуального задания,
- математическая модель и пояснение к её построению,
- входная таблица с экрана монитора и выходные таблицы для всех опций программы и содержательные пояснения к ним,
- выводы по лабораторной работе.
Варианты заданий
Задача 1.
На швейной фабрике для изготовления четырёх видов изделий может быть использована ткань трёх артикулов. Нормы расхода тканей всех артикулов на пошив одного изделия приведены в таблице. В ней так же указаны имеющиеся в распоряжении фабрики общее количество тканей каждого артикула и цена изделия данного вида. Определить, сколько изделий каждого вида должна произвести фабрика, чтобы стоимость изготовленной продукции была максимальной.
Таблица 1
| Артикул ткани | Норма расхода ткани (м) на одно изделие вида | Общее количество ткани | |||
| 1 | 2 | 3 | 4 | ||
| I II III | 1 - 4 | - 1 2 | 2 3 - | 1 2 4 | 180 210 800 |
| Цена изделия (руб.) | 9 | 6 | 4 | 7 | |
Задача 2.
Предприятие выпускает четыре вида продукции и использует три типа основного оборудования: токарное, фрезерное и шлифовальное. Затраты времени на изготовление единицы продукции для каждого из типов оборудования приведены в таблице. В ней же указаны общий фонд рабочего времени каждого из типов оборудования, а также прибыль от реализации одного изделия данного вида. Определить такой объем выпуска каждого из изделий, при котором общая прибыль от их реализации является максимальной.
Таблица 2
| Тип оборудования | Затраты времени (станко-ч) на единицу продукции вида | Общий фонд рабочего времени (станко-ч) | |||
| 1 | 2 | 3 | 4 | ||
| Токарное Фрезерное Шлифовальное | 2 1 1 | 1 - 2 | 1 2 1 | 3 1 - | 300 70 340 |
| Прибыль от реализации единицы продукции (руб.) | 8 | 3 | 2 | 1 | |
Задача 3.
Для перевозок груза на трёх линиях могут быть использованы суда трёх типов. Производительность судов при использовании их на различных линиях характеризуются данными, приведёнными в таблице. В ней же указаны общее время, в течение которого суда каждого типа находятся в эксплуатации, и минимально необходимые объёмы перевозок на каждой линии. Определить, какие суда, на какой линии и в течение какого времени следует использовать, чтобы обеспечить максимальную загрузку судов с учётом возможного времени их эксплуатации.
Таблица 3
| Тип судна | Производительность судов (млн.тонномиль в сутки) на линии | Общее время эксплуатации судов | ||
| 1 | 2 | 3 | ||
| I II III | 8 6 12 | 14 15 12 | 11 13 4 | 300 300 300 |
| Заданный объём перевозок (млн. Тонно-миль) | 3000 | 5400 | 3300 | |
Задача 4.
Найти решение, состоящее в определении плана изготовления изделий A, B и C, обеспечивающего максимальный их выпуск, в стоимости выраженной с учётом ограничений на возможное использование сырья трёх видов. Нормы расхода сырья каждого вида на одно изделие, цена одного изделия соответствующего вида, а также имеющегося сырья, приведены в таблице.
Таблица 4
| Вид сырья | Нормы затрат (кг) на одно изделие | Общее количество сырья (кг) | ||
| A | B | C | ||
| I II III | 18 6 5 | 15 4 3 | 12 8 3 | 360 192 180 |
| Цена одного изделия (руб.) | 9 | 10 | 16 | - |
Задача 5.
На ткацкой фабрике для изготовления трёх артикулов ткани используются станки двух типов, пряжа и красители. В таблице указаны производительность станка каждого типа, нормы расхода пряжи и красителей, цена 1 метра ткани данного артикула, а также общий фонд рабочего времени станков каждого типа, имеющихся в распоряжении фабрики фонды пряжи и красителей и ограничения на возможный выпуск тканей данного артикула.
Таблица 5
| Ресурсы | Нормы затрат на 1 м ткани артикула | Общее количество ресурсов | ||
| 1 | 2 | 3 | ||
| Производительность станков (станко-ч): I типа II типа Пряжа (кг) Красители (кг) Цена 1м ткани (руб.) Выпуск ткани (м): Минимальный Максимальный | 0,02 0,04 1,0 0,03 5 1000 2000 | - 0,03 1,5 0,02 8 2000 9000 | 0,04 0,01 2,0 0,025 8 2500 4000 | 200 500 15000 450 - - - |
Задача 6.
Машиностроительное предприятие для изготовления четырёх видов продукции использует токарное, фрезерное, сверлильное, расточное и шлифовальное оборудование, а также комплектующие изделия.
Кроме того, сборка изделий требует выполнения определённых сборочно-наладочных работ. Нормы затрат всех видов на изготовление каждого из изделий приведены в таблице. В этой же таблице указаны наличный фонд каждого из ресурсов, прибыль от реализации единицы продукции данного вида, а также ограничения на возможный выпуск продукции 2-го и 3-го вида.
Найти план выпуска продукции, при котором прибыль от её реализации является максимальной.
Таблица 6
| Ресурсы | Нормы затрат на изготовление одного изделия | Общий объём ресурсов | |||
| 1 | 2 | 3 | 4 | ||
| Производительность оборудования (человек-ч): Токарного Фрезерного Сверлильного Расточного Шлифовального Комплектующие изделия (шт) Сборочно-наладочные работы (человек-ч) | 550 40 86 160 - 3 4,5 | - 30 110 92 158 4 4,5 | 620 20 150 158 30 3 4,5 | - 20 52 128 50 3 4,5 | 64270 4800 22360 26240 7900 520 720 |
| Прибыль от реализации одного изделия (руб.) Выпуск (шт.): Минимальный Максимальный | 315 - - | 278 40 - | 573 - 120 | 370 - - | - - - |
Задача 7.
Для обогрева помещений используются четыре агрегата, каждый из которых может работать на любом из пяти сортов топлива, имеющемся в количествах 90, 110, 70, 80 и 150 т. Потребность в топливе каждого из агрегатов соответственно равна 80, 120, 140 и 160 т. Теплотворная способность i-ого сорта топлива при использовании его на j-ом агрегате задаётся матрицей
Найти такое распределение топлива между агрегатами, при котором получается максимальное количество теплоты от использования всего топлива.
Задача 8.
Изготовляемый на пяти кирпичных заводах кирпич поступает на шесть строящихся объектов. Ежедневное производство кирпича и потребность в нём указаны в таблице. В ней же указана цена перевозок 1000 шт. кирпича с каждого из заводов к каждому из объектов.
Составить план перевозок, согласно которому обеспечиваются потребности в кирпиче на каждом из строящихся объектов при минимальной общей стоимости перевозок.
Таблица 8
| Кирпичный завод | Цена перевозки 1 тыс. шт. Кирпича к строящемуся объекту | Производство кирпича (тыс. шт.) | |||||
| 1 | 2 | 3 | 4 | 5 | 6 | ||
| I II III IV V | 8 13 12 14 9 | 7 8 4 6 12 | 5 10 11 12 14 | 10 7 9 13 15 | 12 6 10 7 8 | 8 13 11 14 13 | 240 360 180 120 150 |
| Потребность в кирпиче (тыс. шт.) | 230 | 220 | 130 | 170 | 190 | 110 | - |
Задача 9.
Для поддержания нормальной жизнедеятельности человеку необходимо потреблять не менее 118 г белков, 56 г жиров, 500 г углеводов, 8 г минеральных солей. Количество питательных веществ, содержащихся в 1 кг каждого вида потребляемых продуктов, а также цена 1 кг каждого из этих продуктов приведены в следующей таблице:
Таблица 9
| Питательные вещества | Содержание (г) питательных веществ в 1 кг продуктов | ||||||
| Мясо | рыба | молоко | Масло | сыр | крупа | карто-фель | |
| Белки Жиры Углеводы Минеральные соли | 180 20 - 9 | 190 3 - 10 | 30 40 50 7 | 10 865 6 12 | 260 310 20 60 | 130 30 650 20 | 21 2 200 10 |
| Цена 1 кг продуктов (руб.) | 1,8 | 1,0 | 0,28 | 3,4 | 2,9 | 0,5 | 0,1 |
Составить дневной рацион, содержащий не менее минимальной суточной нормы потребности человека в необходимых питательных веществах при минимальной общей стоимости потребляемых продуктов.
Задача 10.
Для перевозок трёх видов продукции предприятие использует два типа технологического оборудования и два вида сырья. Нормы затрат сырья и времени на изготовление одного изделия каждого вида приведены в таблице. Таблица 10
| Ресурсы | Нормы затрат на одно изделие вида | Общее количество ресурсов | ||
| 1 | 2 | 3 | ||
| Производительность оборудования (норм-ч): I типа II типа Сырьё (кг): 1-го вида 2-го вида Цена одного изделия (руб.) Выпуск (шт.): Минимальный Максимальный | 2 4 10 30 10 10 20 | - 3 15 20 15 20 40 | 4 1 20 25 20 25 100 | 200 500 1495 4500 - - - |
В ней же указаны общий фонд рабочего времени каждой из групп технологического оборудования, объёмы имеющегося сырья каждого вида, а также цена одного изделия данного вида и ограничения на возможный выпуск каждого из изделий.
Составить такой план производства продукции, согласно которому будет изготовлено необходимое количество изделий каждого вида, а общая стоимость всей изготовляемой продукции максимальна.
Задача 11.
При производстве четырёх видов кабеля выполняется пять групп технологических операций. Нормы затрат на 1 км кабеля данного вида на каждой из групп операции, прибыль от реализации 1 км каждого вида кабеля, а также общий фонд рабочего времени, в течение которого могут выполняться эти операции, указаны в таблице.
Таблица 11
| Технологическая операция | Нормы затрат времени (ч) на обработку 1 км кабеля вида | Общий фонд рабочего времени (ч) | |||
| 1 | 2 | 3 | 4 | ||
| Волочение | 1,2 | 1,8 | 1,6 | 2,4 | 7200 |
| Наложение изоляции | 1,0 | 0,4 | 0,8 | 0,7 | 5600 |
| Скручивание элементов в кабель | 6,4 | 5,6 | 6,0 | 8,0 | 11176 |
| Освинцевание | 3,0 | - | 1,8 | 2,4 | 3600 |
| Испытание и контроль | 2,1 | 1,5 | 0,8 | 3,0 | 4200 |
| Прибыль от реализации 1 км кабеля | 1,2 | 0,8 | 1,0 | 1,3 | - |
Определить такой план выпуска кабеля, при котором общая прибыль от реализации изготовляемой продукции является максимальной.
Задача 12.
На мебельной фабрике изготовляется пять видов продукции: столы, шкафы, диваны-кровати, кресла-кровати и тахты. Нормы затрат труда, а также древесины и ткани на производство единицы продукции данного вида приведены в таблице.
Таблица 12
|
Ресурсы
| Норма расхода ресурса на единицу продукции | Общее количество ресурсов | ||||
| стол | шкаф | диван-кровать | кресло-кровать | тахта | ||
| Трудозатраты (человека-ч) | 4 | 8 | 12 | 9 | 10 | 3456 |
| Древесина (м3) | 0,4 | 0,6 | 0,3 | 0,2 | 0,3 | 432 |
| Ткань (м) | - | - | 6 | 4 | 5 | 2400 |
| Прибыль от реализации одного изделия (руб.) | 8 | 10 | 16 | 14 | 12 | - |
| Выпуск (шт.): Минимальный Максимальный | 120 480 | 90 560 | 20 180 | 40 160 | 30 120 | - - |
В этой же таблице указана прибыль от реализации одного изделия каждого вида, приведено общее количество ресурсов данного вида, имеющееся в распоряжении фабрики, а также указано (на основе изучения спроса), в пределах каких объёмов может изготовляться каждый вид продукции.
Определить план производства продукции мебельной фабрикой, согласно которому прибыль от её реализации является максимальной. Используя пакет PER, найти решение задачи, а также провести после оптимизационный анализ полученного решения.
Задача 13.
Из трёх видов сырья необходимо составить смесь, в состав которой должно входить не менее 26 ед. химического вещества A, 30 ед. – вещества B и 24 ед. – вещества C. Количество единиц химического вещества, содержащегося в 1 кг сырья каждого вида, указано в таблице. В ней же приведена цена 1 кг сырья каждого вида.
Составить смесь, содержащую не менее необходимого количества данного вида и имеющую минимальную стоимость.
Таблица 13
| Вещество | Количество единиц вещества, содержащегося в 1 кг сырья вида | |||
| 1 | 2 | 3 | 4 | |
| A B C | 1 2 1 | 1 - 2 | - 3 4 | 4 5 6 |
| Цена 1 кг сырья (руб.) | 5 | 6 | 7 | 8 |
Лабораторная работа № 4
Тема: Моделирование и решение задач целочисленного программирования.
Цель работы: закрепить навыки построения математических моделей задач принятия решений и освоитьметоды решения задач целочисленного программирования на контрольных примерах.
Порядок выполнения работы:
1.Сформулировать математическую модель
2.Решить задачу с использованием пакета прикладных программ
3.Дать анализ результатов
4.Подготовиться к защите по нижеприведенным контрольным вопросам.
Контрольные вопросы.
1. Дайте классификацию задач целочисленного программирования. Приведите примеры.
2. Назовите методы решения задач целочисленного программирования.
3. Какое ограничение называется отсечением Гомори?
4. В чем сущность метода ветвей и границ?
Варианты заданий
Задача 1.
Стальные прутья длиной 110 см необходимо разрезать на заготовки длиной 45, 35 и 50 см. Требуемое количество заготовок данного вида составляет соответственно 40, 30 и 20 шт. Возможные варианты разреза и величина отходов при каждом из них приведены в следующей таблице:
| Длина заготовки (см) | Вариант разреза | |||||
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 45 35 50 | 2 - - | 1 1 - | 1 - 1 | - 3 - | - 1 1 | - - 2 |
| Величина отходов (см) | 20 | 30 | 15 | 5 | 25 | 10 |
Определить, сколько прутьев по каждому из возможных вариантов следует разрезать, чтобы обеспечить нужное количество заготовок каждого вида при минимальных отходах.
Как изменится модель и решение задачи, если из заготовок выпускаются комплекты: 2 заготовки по 45 см., 3 заготовки по 35 см., 1 заготовка по 50 см.
Максимизируется число комплектов. Число прутьев, которое имеется, взять из решения первоначальной задачи. Как при этом изменятся отходы?
Задача 2.
Для выполнения работ могут быть использованы n механизмов. Производительность i-го механизма (i=1,n) при выполнении j-ой работы (j=1,n) равна cij. Предполагая, что каждый механизм может быть использован только на одной работе и каждая работа может выполняться только одним механизмом, определить закрепление механизмов за работами, обеспечивающее максимальную производительность.
Построить математическую модель задачи.
Как изменится модель и решение, если имеется 2 механизма 1-го типа, 3 механизма 2-го типа, 1 механизм 3-го типа и 2 механизма 4-го типа и при этом на объекте не может находиться более 7 механизмов.
Задача 3.
Министерству необходимо составить план развития каждого из m предприятий, выпускающих однородную продукцию. Число возможных вариантов развития i-го предприятия различно и равно ni. Реализация j-го варианта развития i-го предприятия (j=1,n) требует капитальных затрат, равных Kij, и обеспечивает выпуск продукции в объеме bij единиц. При этом экономический эффект от капитальных вложений на развитие i-го предприятия по j-му варианту равен cij. Учитывая, что необходимо выпустить продукции в количестве B единиц и что общая величина капиталовложений ограничена и равна K, составить такой план развития предприятий, при котором экономический эффект от реализации выбранных вариантов развития предприятий является максимальным.
K=10 B=40
млн. руб. 
Как изменится решение, если К и В уменьшатся на 20 %.
Задача 4.
В аэропорту для перевозки пассажиров по n маршрутам может быть использовано m типов самолётов. Вместимость самолёта i-го типа равна ai человек, а количество пассажиров, перевозимых по j-му маршруту за сезон, составляет bi человек. Затраты, связанные с использованием самолёта i-го типа на j-ом маршруте, составляет cij руб.
Определить, сколько самолётов данного типа и на каком из маршрутов следует использовать, чтобы удовлетворить потребности в перевозках при наименьших общих затратах.
a1=100 a2=150 a3=200
b1=10т b2=20т b3=8т b4=30т
Подсчитать количество самолетов каждого типа в оптимальном решении. Как изменится решение, если самолетов 2-го типа есть только 100, а 3-го типа меньше 100.
Задача 5.
В обувном производственном объединении производится раскрой m различных партий материалов, причём каждая из партий состоит из bi единиц материала, имеющего одинаковую форму (например, пластины) и размер. Из материалов всех партий требуется выкроить максимальное количество комплектов деталей обуви, в каждый из которых входит dj (j=1,n) деталей j-того вида, если при раскрое единицы материала i-ой партии по k-му варианту (k=1,K) получается aikj деталей j-го вида.
b1=100 b2=200
d1=2 d2=1
a111=2 a112=4 a121=3 a122=1
a211=4 a212=7 a221=5 a222=6
Задача 6.
Для выполнения четырёх видов землеройных работ могут быть использованы экскаваторы четырёх типов. Производительность экскаватора i-го типа при выполнении j-ой работы задаётся матрицей
Учитывая, что на каждой из работ может быть занят только лишь один экскаватор и что все экскаваторы должны быть задействованы, найти такое распределение экскаваторов между работами, которое обеспечивает максимальную производительность. Как изменится модель и решение, если имеется 2 экскаватора 1-го типа, 3 экскаватора 2-го типа, 1 экскаватор 3-го типа, 2 экскаватора 4-го типа, а общее число экскаваторов не может превышать 6?
Задача 7.
Пароход может быть использован для перевозки 11 наименований груза, масса, объём и цена единицы каждого из которых приведены в следующей таблице:
| Параметры единицы груза | Номер груза | ||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
| Масса (т) Объём (м3) Цена (тыс. Руб.) | 80 100 4,4 | 62 90 2,7 | 92 96 3,2 | 82 110 2,8 | 90 120 2,7 | 60 80 2,8 | 81 114 3,3 | 83 60 3,5 | 86 106 4,7 | 65 114 3,9 | 83 86 4,0 |
На пароход может быть погружено не более 800 т груза общим объёмом, не превышающим 600 м3. Определить, сколько единиц каждого груза следует поместить на пароход так, чтобы общая стоимость размещённого груза была максимальной. Как изменится решение, если количество единиц каждого груза ограничено величинами соответственно: 2;1;4;2;2;3;4;4;4;3;3?
Задача 8.
Из листового проката нужно выкроить заготовки четырёх видов. Один лист длиной 184 см можно разрезать на заготовки длиной 45, 50, 65 и 85 см. Всего заготовок каждого вида необходимо соответственно 90, 96, 88 и 56 шт. Способы разреза одного листа на заготовки и величина отходов при каждом способе приведены в следующей таблице:
| Длина заготовки (см)
| Количество заготовок, выкраиваемых из одного листа при разрезе определенным способом | ||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | |
| 45 50 65 85 | 4 - - - | 2 1 - - | 2 - 1 - | 2 - - 1 | 1 2 - - | 1 - 2 - | 1 1 1 - | 1 1 - 1 | - 3 - - | - 2 1 - | - 1 2 - | - - 1 1 | - 2 - - |
| Величина отходов (см) | 4 | 44 | 29 | 9 | 39 | 9 | 24 | 4 | 34 | 19 | 4 | 34 | 14 |
Определить, какое количество листов по каждому из способов следует разрезать, чтобы получить нужное количество заготовок данного вида при минимальных общих отходах.
Как изменится модель и решение, если в окончательное изделие (комплект) входит 2 заготовки 1-го и 2-го вида и 3 заготовки 3-го и 4-го вида. Максимизируется число комплектов. Изменятся ли отходы для такого оптимального решения? (Общее число листов взять из результатов 1-й постановки задачи)
Задача 9.
Имеются одинаковые заготовки, которые могут быть раскроены тремя способами. Из имеющихся заготовок нужно получить не менее 10 деталей 1-го типоразмера, не менее 8-ми деталей 2-го типоразмера и не менее 10-ти деталей 3-го типоразмера. Способы раскроя определяются матрицей вида:
Здесь aij – количество деталей типоразмера i, получаемое из одной заготовки путём её раскроя способом j.
Количество заготовок, раскраиваемых каждым способом, должно быть целым и не превышать 4-х. Отходы от раскроя одной заготовки для каждого из способов составляют 4, 5 и 5 (усл. единиц). Предложить вариант раскроя с минимальными суммарными отходами. Определить величину этих отходов.
Фирма предполагает продавать выкроенные детали по ценам $4, $6 и $2,5 соответственно для 1-го, 2-го и 3-го типоразмера. При этом потери от процедуры раскроя оцениваются величиной $0,3 на условную единицу отходов. Оптимизируйте процесс раскроя, исходя из соображений получения максимальной прибыли.
Задача 10.
Рассматриваются пять проектов, которые могут быть осуществлены в течение последующих трёх лет. Ожидаемые величины прибыли от реализации каждого из проектов и распределение необходимых капиталовложений по годам (в тыс. долларов) приведены в таблице.
| Проект | Распределение капиталовложений | Прибыль | ||
| Год 1 | Год 2 | Год 3 | ||
| 1 | 5 | 1 | 8 | 20 |
| 2 | 4 | 7 | 10 | 40 |
| 3 | 3 | 9 | 2 | 20 |
| 4 | 7 | 4 | 10 | 15 |
| 5 | 8 | 6 | 1 | 30 |
| Максимальный объем капиталовложений | 25 | 25 | 25 | |
Предполагается, что каждый утверждённый проект будет реализован за трёхлетний период.
Требуется выбрать совокупность проектов, которой соответствует максимум суммарной прибыли.Как изменится максимум суммарной прибыли, если максимальный объем капиталовложений уменьшать от 25 до 0, или увеличивать от 25 до бесконечности? Построить график.
Задача 11.
Руководство завода предполагает провести комплекс организационно-технических мероприятий по модернизации производства. Перечень возможных мероприятий приведён в таблице. На реализацию всех мероприятий завод может выделить:
· трудовых ресурсов – 1300 чел-дней,
· финансовых ресурсов – 800 млн. руб.
· производственных площадей –700 кв. м
| Мероприятие | Трудовые ресурсы (чел. дни) | Финансовые ресурсы (млн. руб.) | Производственные площади (кв. м) | Экономический эффект (млн. руб.) |
| Закупка станков с ЧПУ | 350 | 400 | 130 | 13000 |
| Текущий ремонт | 250 | 90 | - | 3000 |
| Монтаж транспортного конвейера | 100 | 60 | 300 | 8000 |
| Установка рельсового крана | 200 | 300 | 150 | 12000 |
| Ввод системы контроля качества | 130 | - | 150 | 2500 |
| Разработка АСУ | 800 | 500 | 100 | 15000 |
Какие мероприятия следует провести, располагая этими ресурсами, чтобы общий экономический эффект был максимальным? Какова величина этого эффекта? Какой объём выделяемых ресурсов останется неиспользованным при реализации найденного варианта? Изменится ли решение задачи, если завод выделит на модернизацию 1 млрд. руб.?
Изменится ли решение задачи, если завод полностью удовлетворит потребности модернизации в производственных площадях и трудовых ресурсах при прежнем финансировании?
Задача 12.
В регионе работают 4 химических завода. Им предложено принять участие в конкурсе по размещению госзаказа на производство изделий 5-ти наименований в объёмах, приведённых в таблице.
| Наименование изделия | |||||
|
Объём заказа (шт.) | A1 | A2 | A3 | A4 | A5 |
| 350 | 250 | 400 | 150 | 150 | |
Каждый из заводов представил несколько вариантов годовой производственной программы по выполнению госзаказа и соответствующие финансовые условия. Программа включает выпуск всех изделий.
| Варианты завода 1 | Варианты завода 2 | Варианты завода 3 | Варианты завода 4 | |||||||
| Наименование изделия | 1 | 2 | 3 | 1 | 2 | 1 | 2 | 3 | 1 | 2 |
| A1 | 100 | 200 | 200 | 50 | 80 | - | - | 100 | 100 | 50 |
| A2 | 200 | 100 | 150 | - | - | 200 | 250 | 100 | 40 | 60 |
| A3 | 300 | 250 | 200 | 120 | 100 | 100 | 50 | 500 | 60 | 100 |
| A4 | 100 | 50 | 100 | 100 | 50 | - | - | - | 50 | - |
| A5 | 50 | 100 | 80 | - | - | 100 | 100 | 80 | 150 | 100 |
| Объём финансирования (млрд. руб.) | 12 | 16 | 14 | 7 | 9 | 16 | 15 | 17 | 5 | 8 |
Каковы минимальные затраты на выполнение госзаказа?
Какой вариант размещения заказа обеспечивает его выполнение при минимальных объёмах финансирования?
Как изменится решение, если учесть, что заводы 1 и 4 не могут одновременно выполнять однотипные варианты размещения заказов?
Задача 13.
Нефтеперерабатывающее предприятие использует в производстве нефть трёх сортов (1, 2 и 3). Резервные запасы нефти каждого сорта должны быть не меньше соответственно 20, 40 и 60 тыс. тонн. Для хранения нефти могут быть использованы 4 резервуара ёмкостью 25, 30, 35 и 40 тыс. тонн. Затраты на хранение 1-ой тонны нефти сорта 2 на 10% выше, чем сорта 1, а сорта 3 – на 20% выше, чем сорта 1. Смешение нефти разных сортов при хранении не допускается.Резервуары заполняются полностью.
Сколько резервуаров следует использовать?
Как распределяются сорта нефти по резервуарам?
Каковы минимальные затраты на хранение нефти?
Целесообразно ли устанавливать дополнительный резервуар объёмом 20 тыс. тонн?
Задача 14.
Для реконструкции машиностроительного предприятия было представлено на выбор 10 проектов, каждый из которых характеризуется четырьмя агрегированными показателями и ежегодной ожидаемой прибылью, представленными в таблице.
| Агрегированный показатель проекта | Варианты проектов | |||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| Затраты труда (нормо-час) | 50 | 60 | 30 | 40 | 80 | 70 | 50 | 20 | 40 | 50 |
| Затраты энергии (тыс. квт) | 4 | 4 | 2 | 5 | 5 | 2 | 3 | 6 | 6 | 3 |
| Расходы на материалы (млн. руб.) | 3 | 2 | 4 | 5 | 3 | 2 | 4 | 2 | 2 | 3 |
| Финансовые средства (млн. руб.) | 7 | 5 | 9 | 6 | 4 | 3 | 7 | 2 | 4 | 5 |
| Ожидаемая прибыль (млн. руб.) | 9 | 8 | 8.5 | 8.8 | 9 | 8 | 9 | 8.7 | 8.9 | 8 |
При выборе проектов необходимо учесть ряд ограничений технологического характера:
- одновременно может быть реализовано не более семи проектов
- 5-ый и 8-ой проекты взаимно исключают друг друга
- 1-ый проект может быть реализован лишь при условии реализации второго
- 4-ый проект может быть реализован лишь при условии реализации хотя бы одного из двух проектов: либо 3-его, либо 10-ого.
Выбрать проекты для реконструкции предприятия, обеспечивающие максимальную ожидаемую прибыль. Каков размер этой прибыли?
Задача 15.
Объединение кабельной промышленности состоит из 3-х заводов. Номенклатура выпускаемых изделий включает три позиции: “кабель силовой”, “провод для осветительных установок”, “провод обмоточный”. При планировании развития объединения на три года разработаны три варианта (1-3) для завода 1, 2 варианта (4-5) для завода 2 и один (6) – для завода 3.
(В таблице все данные в условных единицах)
Требуется выбрать варианты для включения в план развития объединения, обеспечивающие удовлетворение заданной потребности в кабельных изделиях и реализуемые с минимальными затратами. Каковы эти затраты?
| Вариант | Производство кабельных изделий по годам | ЗЗатраты за 3 года | ||||||||
| Кабель | Провод силовой | Провод обмоточный | ||||||||
| 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 | ||
| 1 2 3 4 5 6 | 6.9 7 7 19 16 - | 8 7 7.8 23 18 - | 10 8.6 8.7 28 22 - | 37 25 30 - - - | 44 - - - - 864 | 53 - - - - 950 | 2.8 3 6 13 16 - | 3 18 18 15 18 - | 4 20 20 18 21 - | 1557 1399 1034 2822 3044 364 |
| Потребность | 15 | 17 | 25 | 20 | 300 | 450 | 10 | 15 | 10 | |
Лабораторная работа №5
Тема: Моделирование и решение задач управления векторной оптимизации
Цель работы: закрепить навыки построения оптимизационных математических моделей задач принятия решений и освоитьметоды решения многокритериальных задач управления.
Порядок выполнения работы:
1.Сформулировать математическую модель
2.Решить задачу с использованием пакета прикладных программ
3.Дать анализ результатов
4.Подготовиться к защите по нижеприведенным контрольным вопросам.
Контрольные вопросы.
1. Назовите основные проблемы выбора компромиссных решений.
2. Охарактеризуйте основные принципы выбора компромиссных решений?
3. В чем основное отличие выбора компромиссного решения по принципу выделения главного критерия от принципа последовательных уступок?
4. Опишите основные этапы процедуры «СТЕМ».
Задания (вариант) 1 и 2
На заводе ежемесячно скапливается А тонн отходов металла, из которого можно штамповать мелкие детали 6 типов. Месячная потребность завода в деталях i-го типа равна bi тыс.шт. Недостающее количество деталей i-го типа или закупается на других предприятиях по цене ci рублей за тысячу штук или производится из дополнительного металлолома, который закупается на стороне по цене М рублей за тонну. Расход металла на тыс. деталей i-го типа составляет аi кг.
Для изготовления деталей используются 3 пресса, на каждом из которых за смену можно изготовить di тыс. деталей i-го типа. В месяц каждый пресс работает не более 52 смен. Найти стратегию (закупать недостающие детали или закупать недостающий метал) и план производства деталей на заводе, обеспечивающий минимум суммарных расходов (исходные данные приведены в табл.1).
Исходные данные к заданию 1 и 2
Таблица 1
| Вари-анты | А | а1 | а2 | а3 | а4 | а5 | а6 | b1 | b2 | b3 | b4 | b5 | b6 |
| 1 | 12 | 30 | 45 | 22 | 11 | 74 | 51 | 62 | 99 | 17 | 29 | 34 | 99 |
| 2 | 12 | 17 | 15 | 99 | 19 | 27 | 81 | 99 | 15 | 37 | 23 | 70 | 23 |
продолжение табл.1
| Вариант | c1 | c2 | c3 | c4 | c5 | c6 | М | d1 | d2 | d3 | d4 | d5 | d6 |
| 1 | 13 | 15 | 9 | 7 | 18 | 22 | 5 | 1,4 | 1,3 | 2,9 | 2,1 | 0,8 | 1,5 |
| 2 | 17 | 12 | 36 | 11 | 32 | 24 | 7 | 2,3 | 3,2 | 1,0 | 2,1 | 1,5 | 1,2 |
Задания (вариант) 3 и 4
Для поражения целей некоторого класса разработано 5 типов оружия. Один комплекс оружия j-го типа может действовать по группам целей (низколетящим и высоколетящим) с различной эффективностью. Среднее количество поражаемых целей при этом равны Р 1j и Р 2j. Количество вылетов низколетящих целей превосходит их количество высоколетящих в два раза. Необходимо разработать систему вооружения (определить количество комплексов каждого типа), обеспечивающую максимум математического ожидания числа уничтоженных целей, если стоимость одного комплекса j-го типа составляет rj % суммы, выделенной на всю сиcтему; трудоемкость изготовления одного комплекса j-го типа составляет аj % от общего фонда рабочего времени. Для производства одного комплекса j-го типа необходимо bj кг дефицитного материала, а в распоряжении производства имеется В т этого материала. В силу ограничений технологического характера может быть изготовлено не более Сj комплексов j-го типа (см.табл. 2).
Исходные данные к заданию 3 и 4
Таблица 2.
| Вар ант | Р11 | Р12 | Р13 | Р14 | Р15 | Р21 | Р22 | Р23 | Р24 | Р25 |
| 3 | 0,7 | 0,5 | 0,3 | 0,9 | 0,8 | 0,6 | 0,5 | 0,6 | 0,8 | 0,7 |
| 4 | 0,6 | 0,4 | 0,9 | 0,8 | 0,7 | 0,6 | 0,4 | 0,9 | 0,8 | 0,8 |
продолжение табл.2
| Вари ант | a1 | a2 | a3 | a4 | a5 | b1 | b2 | b3 | b4 | b5 |
| 3 | 0,03 | 0,02 | 0,01 | 0,04 | 0,02 | 13 | 17 | 25 | 10 | 19 |
| 4 | 0,02 | 0,01 | 0,05 | 0,02 | 0,03 | 35 | 34 | 60 | 25 | 25 |
продолжение табл.2
| Вари ант | r1 | r2 | r3 | r4 | r5 | B | c1 | c2 | c3 | c4 | c5 |
| 3 | 0,02 | 0,01 | 0,01 | 0,03 | 0,03 | 120 | 2000 | 6000 | 12000 | 2000 | 4500 |
| 4 | 0,01 | 0,01 | 0,04 | 0,02 | 0,01 | 220 | 6000 | 8000 | 3000 | 6000 | 2000 |
Задания (вариант) 5 и 6
Для приготовления комбикорма совхоз может закупить зерно 4-х сортов Ki , отличающихся друг от друга содержанием питательных компонентов Cj (j=1,..,5).Для обеспечения нормального питания скота в течение планируемого периода комбикорм должен содержать не менее Bj питательного компонента j-го типа. Одна тонна зерна i-го типа стоит ri рублей и содержит aij единиц питательного компонента j-го типа (табл.3). Складские помещения позволяют хранить не более А тонн зерна (для варианта 5: А=2800, для варианта 6: А=4400). Определить план закупки зерна каждого сорта, обеспечивающий компромиссное решение по минимизации затрат на покупку зерна и максимизации питательности комбикорма с учетом требований на его питательность и емкости складских помещений. Критерии считать равнозначными.
Исходные данные к заданию 5 и 6
Таблица 3.
Дата добавления: 2018-05-02; просмотров: 1925; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!