- •Введение
- •Математический аппарат для решения задач оптимизации Понятие математического программирования
- •Понятие линейного программирования
- •Задача линейного программирования
- •Постановка задач линейного программирования и исследование их структуры
- •Определение оптимальных значений параметров целевой функции средствами ms Excel Цель работы
- •Краткие теоретические сведения
- •Методические указания
- •Варианты заданий
- •Требования к содержанию и оформлению отчёта
- •Контрольные вопросы
- •Определение оптимальных значений параметров двухмерной целевой функции геометрическим способом Цель работы
- •Краткие теоретические сведения
- •Методические указания
- •Варианты заданий
- •Требования к содержанию и оформлению отчёта
- •Контрольные вопросы
- •Решение задачи о кратчайшем пути Цель работы
- •Краткие теоретические сведения
- •Методические указания
- •Варианты заданий
- •Требования к содержанию и оформлению отчёта
- •Контрольные вопросы
- •Решение задачи коммивояжера методом перебора Цель работы
- •Краткие теоретические сведения
- •Методические указания
- •Варианты заданий
- •Требования к содержанию и оформлению отчёта
- •Контрольные вопросы
- •Экспертное оценивание эффективности управленческих решений
- •Лабораторная работа №5 Методы обработки экспертных оценок Цель работы
- •Краткие теоретические сведения
- •Методические указания
- •Варианты заданий
- •Требования к содержанию и оформлению отчёта
- •Контрольные вопросы
- •Содержание
Постановка задач линейного программирования и исследование их структуры
Большинство задач, решаемых методами исследования операций, может быть сформулировано так:
максимизировать
при ограничениях:
где – целевая функция, или критерий эффективности (например, прибыль от производства каких-либо видов продукции, стоимость перевозок и т.п.); – варьируемые параметры; – функции, которые задают ограничения на имеющиеся ресурсы.
Несмотря на требование линейности функций критериев и ограничений, в рамки линейного программирования попадают многочисленные задачи распределения ресурсов, управления запасами, сетевого и календарного планирования, транспортные задачи и прочие.
Рассмотрим некоторые из них.
Определение оптимального ассортимента.
Имеются видов ресурсов в количествах и видов изделий. Задана матрица где характеризует нормы расхода -го ресурса на единицу -го вида изделий. Эффективность производства -го вида изделий характеризуется показателем , удовлетворяющим условию линейности. Нужно определить такой план выпуска изделий (оптимальный ассортимент), при котором суммарный показатель эффективности будет наибольший.
Обозначим количество единиц -го вида изделий, выпускаемых предприятием, через , . Тогда математическая модель этой задачи будет иметь такой вид:
при ограничениях
(1)
Кроме ограничений на ресурсы (1), в эту модель можно ввести дополнительные ограничения на планируемый уровень выпуска продукции , для всех и т.д.
Оптимальное распределение взаимозаменяемых ресурсов.
Имеются видов взаимозаменяемых ресурсов , используемых при выполнении различных работ (задач). Объемы работ, которые должны быть выполнены, составляют единиц. Заданы числа , указывающие, сколько единиц -й работы можно получить из единицы -го ресурса, а также – затраты на производство -й работы из единицы -го ресурса. Требуется распределить ресурсы по работам таким образом, чтобы суммарная эффективность выполненных работ была максимальной (или суммарные затраты - минимальными).
Данная задача называется общей распределительной задачей. Количество единиц -го ресурса, которое выделено на выполнение работ -го вида, обозначим через .
Математическая модель рассматриваемой задачи такова:
при ограничениях
(2)
(3)
Ограничение (2) означает, что план всех работ должен быть выполнен полностью, а (3) означает, что ресурсы должны быть израсходованы целиком.
Примером этой задачи может быть задача о распределении самолетов по авиалиниям.
Задача о смесях.
1. Имеется компонентов, при сочетании которых в разных пропорциях получают разные смеси. Каждый компонент, а следовательно и смесь, содержит веществ. Количество -го вещества входящее в состав единицы -го компонента и в состав единицы смеси, обозначим через и соответственно.
Предположим, что зависит от линейно, то есть если смесь состоит из единиц первого компонента, - единиц второго компонента и т.д., то
2. Задано величин , характеризующих стоимость, массу или калорийность единицы -го компонента, и величин , указывающих минимально необходимое процентное содержание -го вещества в смеси. Обозначим через значение компонента -го вида, входящего в состав смеси.
Математическая модель этой задачи имеет такой вид:
при ограничении
(4)
Ограничение (4) означает, что процентное содержание -го вещества в единице смеси должно быть не меньше .
К этой же модели принадлежит также задача определения оптимального рациона кормления скота.
Задача о раскрое материалов.
Пусть поступает в раскрой различных материалов. Требуется изготовить из них разных комплектующих изделий (комплектов) в количествах, пропорциональных величинам (условия комплектности). Пусть каждую единицу -го материала можно раскроить различными способами, так что при использовании -го способа раскроя, получим единиц -го изделия. Нужно определить такой план раскроя материалов, обеспечивающий максимальное количество комплектов, если имеющийся запас -го материала составляет единиц.
Обозначим через количество единиц -го материала, раскраиваемых -м способом, а через – общее количество изготавливаемых комплектов.
Математическая модель этой задачи имеет такой вид:
при условиях:
(5)
. (6)
Условие (5) означает ограничение на запас -го материала, а (6) – условие комплектности.
Лабораторная работа №1