Решение оптимизационных задач

Многочисленные проблемы, связанные с распределением и использованием финансовых, трудовых и других ресурсов, планированием, управлением и оценкой эффективности производства, управлением запасами, календарным планированием работ, могут быть формализованы и решены с использованием специальных математических методов, объединенных общим названием - математическое программирование.

Наиболее общая математическая постановка задачи математического программирования - определить значения переменных Х₁, Х₂ ... Х_n; , доставляющих максимум (минимум) заданной функции

(1)

при условиях

Функцию W принято называть целевой функцией или показателем эффективности исследуемой экономической операции.

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

Задача. Фабрика выпускает три вида изделий. Суточные ресурсы фабрики следующие: 700 единиц производственного оборудования; 800 единиц сырья; 600 единиц энергоресурсов. Расходы каждого вида ресурсов на единицу изделий каждого типа представлены в табл. 4

Таблица 4

Исходные данные задачи оптимизации

Ресурсы	Виды изделий
А	В	С
Оборудование
Сырьё
Э/ ресурсы

Цена единицы изделия первого вида равна 8 ден. ед., изделия второго вида - 7 ден. ед., изделия третьего вида - 6 ден. ед.

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

Допущение: вся произведенная ткань реализуется. В данной задаче показателем эффективности W является выручка; переменными Х₁, Х₂, Х₃ - физические объемы производимой ткани первого, второго и третьего вида соответственно; ограничения f_j (j = 1, 2, 3) связаны с располагаемыми ресурсами.

Общая характеристика задачи линейного программирования

Задача линейного программирования (ЛП) в общей постановке состоит в отыскании значений п переменных Х₁, Х₂, Х₃, ..., , доставляющих экстремум функции:

при условиях

(2)

Как следует из приведенных выражений, условия (2) представляют собой систему нестрогих линейных неравенств, а показатель эффективности W является аддитивной линейной функцией п переменных.

Вернувшись к задаче, нетрудно убедиться в том, что ее формально-математическая постановка соответствует общей постановке задачи линейного программирования.

Действительно, требуется определить значения переменных Х₁, Х₂, Х₃, доставляющие максимум целевой функции

при ограничениях

(3)

Ограничения-неравенства в задачах линейного программирования замещают равенствами, введя дополнительные переменные. Так, в случае (3) получим

(4)

где Х₄, Х₅, Х₆ - дополнительные переменные.

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

найти значения n переменных Х₁, Х₂, Х₃, ... , Х_п, доставляющие экстремум функции

при условиях

(5)

Кроме того, дополнительно вводится условие неотрицательности всех переменных

Последнее условие требует, чтобы решение задачи было допустимым, т.е. неотрицательным.

Заметим, что в ряде случаев система ограничений может отличаться от (2) и (5). Однако следует помнить о том, что приведенная постановка задачи линейного программирования является общей, а значит, остальные случаи могут быть сведены к ней.

Допустимое решение (Х₁, Х₂, ..., Х_п), при котором функция (показатель) W принимает оптимальное (наилучшее) значение, называют оптимальным.

Частное решение системы уравнений (5), получаемое приравниванием нулю п из (п + т) переменных, называют базисным. При этом переменные, приравненные нулю, принято называть неосновными, или свободными. Оставшиеся переменные называют основными.

Оптимальное решение задачи ЛП ищут среди допустимых базисных решений. Для этого используют специфические свойства задачи ЛП, которые вводят рядом теорем. Из этих теорем непосредственно следует справедливость следующего положения:

Экстремум целевой функции является абсолютным и достигается хотя бы в одной крайней точке многогранника, задающего область определения задачи линейного программирования; данная точка соответствует допустимому базисному решению системы - уравнений ограничений.

Для решения задач линейного программирования в зависимости от их специфики применяют различные методы:

геометрический метод; симплекс-метод; распределительный метод и др.

Геометрический подход к решению задач линейного программирования

Геометрический метод решения задач ЛП имеет весьма ограниченное применение и главным образом используется для наглядной иллюстрации существа подобных задач.

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

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

Пример выполнения задания

Содержательная постановка задачи

Фирма выпускает два вида тканей. Суточные ресурсы фирмы следующие: 700 единиц производственного оборудования; 800 единиц сырья; 600 единиц энергоресурсов. Расходы каждого вида ресурсов на единицу ткани каждого типа представлены в табл. 4.

Цена единицы ткани первого вида равна 8 ден. ед., а второго вида - 6 ден. ед.

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

Математическая постановка задачи

Найти Х₁, Х₂, доставляющие максимум целевой функции

при ограничениях

Геометрическое решение задачи

В системе координат (X₁, 0, Х₂) строим график линейной зависимости, полученной переходом от первого неравенства к равенству (рис. 1):

По аналогии получаем выражения для двух других линейных зависимостей

Изображаем графики данных зависимостей в той же системе координат и штриховкой выделяем область определения рассматриваемой задачи.

Затем на том же рисунке (рис. 5) изображаем прямую, полученную с использованием целевой функции для случая

Рис. 5. Графическая интерпретация решения

оптимизационной задачи

График данной линейной зависимости перемещаем параллельно самому себе до вершины с максимальным значением целевой функции (при поиске минимума - линию, соответствующую функции цели перемещаем в противоположном направлении).

Координаты данной вершины (точка А) и соответствуют оптимальному решению задачи.

В этой точке пересекаются линии (1) и (3). Решая совместно систему из двух уравнений, соответствующих этим линиям, получаем координаты точки А:

Вычтем из первого уравнения второе и получим:

0 = 125 – Х₁

отсюда

Х₁ = 125.

Подставляя найденное значение в одно из уравнений, получим

Х₂ = 175 – ½ 125

отсюда

Х₂ = 112,5.

Подставляя значения переменных в целевую функцию, получим

W = 8·125 + 6·112,5 = 1675.

Выводы: продукции первого вида должно быть произведено 125 единиц, второго вида – 112,5. Максимальная выручка от реализации продукции составит 1675 ден.ед.

Варианты заданий

Исходные данные для своего варианта задания каждый студент формирует самостоятельно по следующему алгоритму:

1) обращение к таблице, содержащей выборку из таблицы случайных чисел, и извлечение из нее трёх чисел подряд (а₁, а₂, а₃), начиная с числа, соответствующего в таблице номеру варианта.

Таблица 5

Таблица случайных чисел

2) замена в задаче переменных в₁, в₂, в₃ числами, полученными по зависимостям

Примечание. ] с [ - означает целую часть от с.

Задача. Фирма выпускает два вида продукции А и В. Суточные ресурсы фирмы следующие:

в₁ - единиц производственного оборудования;

в₂ - единиц сырья;

в₃ - единиц электроэнергии.

Расходы каждого вида ресурсов на единицу продукции каждого типа представлены в табл. 6:

Таблица 6

Ресурсы	Тип продукции
А	В
Оборудование
Сырьё
Э/ ресурсы

Цена единицы продукции первого вида равна 8 ден. ед., а второго вида - 6 ден. ед.

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

ОПРЕДЕЛЕНИЕ НАДЁЖНОСТИ

ПРОИЗВОДСТВЕННЫХ СИСТЕМ

Допустим, что производственная система S состоит из n элементов е₁, е₂, …, е_n. Надёжности элементов (вероятности безотказной работы) известны р₁, р₂, …, р_n. Для безотказной работы системы, состоящей из нескольких последовательно соединённых элементов (например станков, объединённых в технологическую линию), нужно, чтобы работал безотказно каждый из её элементов. Тогда по правилу умножения вероятностей независимых событий надёжность Р системы равна

Рис. 6. Система из последовательно соединённых

элементов

Задача. Определить надёжность системы, состоящей из десяти последовательно соединённых элементов, надёжность каждого из которых равна р = 0,95. Поскольку вероятности безотказной работы для всех элементов одинаковы, то вместо произведения используем возведение в степень

Р = рⁿ = 0,95¹⁰ ≈ 0,6.

Одним из путей повышения надёжности системы является резервирование её элементов. При этом дублирующие элементы включаются в систему параллельно тем, надёжность которых недостаточна. В этом случае надёжность Р системы определяется из выражения

.

Рис. 7. Система из параллельно соединённых элементов

Задача. Определить надёжность системы, состоящей из трёх дублирующих друг друга элементов, надёжность каждого из которых составляет р = 0,9. Поскольку вероятности безотказной работы для всех элементов одинаковы, то вместо произведения используем возведение в степень

Р = 1 – (1 – 0,9)³ = 0,999.

Задание. Определить надёжность системы, представленной на рис. 8.

Рис. 8. Производственная система из семи элементов

Варианты вероятностей безотказной работы элементов

Варианты	е1	е2	е3	е4	е5	е6	е7
	0,95	0,9	0,85	0,8	0,75	0,7	0,75
	0,9	0,85	0,8	0,75	0,7	0,75	0,8
	0,85	0,8	0,75	0,7	0,75	0,8	0,85
	0,8	0,75	0,7	0,75	0,8	0,85	0,9
	0,75	0,7	0,75	0,8	0,85	0,9	0,95
	0,7	0,75	0,8	0,85	0,9	0,95	0,9
	0,75	0,8	0,85	0,9	0,95	0,9	0,85
	0,8	0,85	0,9	0,95	0,9	0,85	0,8
	0,85	0,9	0,95	0,9	0,85	0,8	0,75
	0,9	0,95	0,9	0,85	0,8	0,75	0,7

ПРОГРАММА ДИСЦИПЛИНЫ

"Методы моделирования производственных систем"

Раздел 1. Основы моделирования производственных систем

Тема 1. Методы моделирования производственных систем

Задачи курса "Методы моделирования производственных систем". Методологические основы моделирования производственно-экономических систем. Процесс системного моделирования производственных систем.

Математическое моделирование в экономике. Этапы экономико-математического моделирования. Постановка экономической проблемы и ее качественный анализ. Построение математической модели. Математический анализ модели. Подготовка исходной информации. Численное решение. Анализ численных результатов и их применение. Взаимосвязь этапов экономико-математического моделирования.

Тема 2. Классификация моделей производственных систем

Материальные модели и абстрактные. Модели производственно-экономических систем, региональных комплексов, отраслевые модели, модели народного хозяйства. Модели перспективного, стратегического планирования, текущего и оперативно-календарного. Модели линейные и нелинейные. Модели детерминированные и стохастические. Модели статические и динамические. Имитационные модели. Эвристические методы в моделировании. Графические модели. Элементы теории графов.

Тема 3. Системный подход к производству, как объекту моделирования.

Понятие системы. Большие сложные системы. Производственно-экономические системы. Иерархические системы. Свойство эмерджентности. Целенаправленность систем. Процессы передачи информации и управления в сложно организованных системах. Понятие цели. Классификация целей. Дерево целей. Требования к компонентам сложных систем. Понятие обратной связи. Моделирование обратных связей. Надёжность производственных систем. Метод анализа иерархий.

Раздел 2. Дескриптивные модели

Тема 4. Моделирование структур производственных систем.

Функциональное, морфологическое и информационное описание систем. Понятие структуры. Организационная структура, функциональная, техническая. Моделирование структур. Типы организационных структур и их модели. Последовательная структура, кольцевая, звездочная, многосвязная, иерархическая, смешанная. Количественные параметры моделей организационных структур. Критерий оптимальности. Моделирование структур производственных систем на основе теории графов. Матричное моделирование структур производственных систем. Информационный подход в моделировании сложных производственно-экономических систем. Энтропийные методы моделирования производственных систем.

Тема 5. Методы отбора существенных факторов моделей производственных систем.

Использование методов экспертного опроса и статистического анализа. Этапы процедуры экспертного исследования. Формирование списка факторов моделей исследователем. Подготовка анкеты. Формирование группы экспертов. Постановка задачи экспертам. Проведение опроса экспертов. Составление сводной таблицы результатов опроса. Ранжирование оценок экспертов. Оценка согласованности мнений экспертов. Оценка статистической значимости коэффициента конкордации.

Отыскание параметров эмпирических математических моделей производственно-экономических систем. Моделирование с использованием метода "черного ящика". Понятие об интерполяции, аппроксимации и экстраполяции. Экономико-математические модели для аппроксимации опытных данных. Метод наименьших квадратов. Корреляционно-регрессионный анализ.

Тема 6. Hазначение моделей производственно-экономических систем.

Дискриптивные модели. Оптимизационные модели. Многокритериальные модели. Имитационные модели.

Раздел 3. Имитационные модели

Тема 7. Имитационное моделирование как метод исследования и анализа производственно-экономических систем.

Аналитическое и имитационное моделирование. Случаи использования имитационного моделирования. Классификация имитационных моделей. Порядок построения имитационной модели производственно-экономической системы и проведения машинных имитационных экспериментов. Формулировка проблемы, изложение целей эксперимента на модели. Формулировка комплекса задач модельного исследования объекта.

Построение концептуальной модели объекта, определение ограничений и измерителей эффективности изучаемой системы. Составление содержательного описания объекта, предварительная формализация объекта. Формирование комплекса требований к моделирующей программе. Построение логико-математической модели объекта, формирование структуры системы - формализованного представления объекта, составление логико-математических описаний элементов системы и внешних воздействий, т.е. переход от реальной системы к некоторой логической схеме (абстрагирование). Принципы выбора шага моделирования (детерминированный шаг, моделирование по событиям, позаявочный способ. Сбор и подготовка данных и отбор данных, необходимых для построения модели, представление исходных данных в соответствующей форме. Моделирование случайных событий. Разработка моделирующей программы (алгоритма), трансляция модели – описание модели на языке, используемом в применяемой для экспериментирования ЭВМ. Выбор языка моделирования. Проверка работы (верификация) имитационной модели. Оценка пригодности, адекватности имитационной модели объекту моделирования. Планирование эксперимента или стратегическое планирование. Планирование имитационных экспериментов при оптимизации по градиенту. Тактическое планирование, определение способов проведения каждой серии испытаний. Полный и неполный факторный эксперимент. Процесс проведения экспериментов на модели, анализ чувствительности модели к изменениям исходных данных. Обработка результатов эксперимента, интерпретация результатов моделирования. Практическая реализация результатов моделирования. Документальная регистрация хода построения модели и результатов проведения экспериментов.

Тема 8. Моделирование производственно-экономических систем с помощью сетей Петри.

Сети Петри и их расширения. Представление сети с помощью ориентированного графа. Типы вершин. Понятие позиции (состояния, места) и перехода (события). Входные и выходные позиции. Маркированные графы. Правила срабатывания переходов. Режим ожидания, активизации и запуска переходов. Описание структур моделируемых проблемных ситуаций в виде сетей Петри. Представление имитационных моделей систем в виде сетей событий, являющихся расширением сетей Петри.

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

а) Основная литература

1. Иозайтис В.С. Экономико-математическое моделирование производственных систем: Учеб. пособие для инженерно-экономич. спец. вузов / В.С. Иозайтис, Ю.А. Львов. - М.: Высш. шк., 1991. 192 с.

2. Имитационное моделирование в оперативном управлении производством / Н.А. Саломатин, Г.В. Беляев, В.Ф. Петроченко, Е.В. Прошлякова. - М.: Машиностроение, 1984. 208 с.

3. Данильченко И.А. Имитационное моделирование в организационно-технических системах / И.А. Данильченко. - Воронеж: ВПИ, 1983. 176 с

4. Имитационное моделирование и оптимизация сложных систем / В.Н. Фролов Воронеж: ВПИ, 1983. 173 с

5. Имитационное моделирование производственных систем / под ред. А.А. Вавилова М.: Машиностроение, Берлин: Техника, 1983. 416 с

6. Дудорин В.И. Моделирование в задачах управления производством / В.И. Дудорин. - М.: Финансы и статистика, 1986. 191 с.

7. Системный анализ в экономике и организации производства: учебник/ под ред С.А. Валуева М.: Политехника, 1991. 397 с.

8. Бережная Е.В. Математические методы моделирования экономических систем: учеб. пособие / Е.В. Бережная. - М.: Финансы и статистика, 2001. 368 с.

9. Бусленко В.Н. Автоматизация имитационного моделирования сложных систем / В.Н. Бусленко. - М.: Наука, 1977. 239 с.

10. Бусленко Н.П. Моделирование сложных систем / Н.П. Бусленко. - М.: Наука, 1968. 355 с

11. Клейнен Дж. Статистические методы в имитационном моделировании: пер. с англ./ Дж Клейнен. М.: Статистика, 1978. 222 с.

12. Советов Б.Я. Моделирование систем: учебник / Б.Я. Советов. - М.: Высш.шк. 1998. 319 с.

13. Бешелев С.Д., Гурвич Ф.Г. Математико-статистические методы экспертных оценок / С.Д. Бешелев, Ф.Г. Гурвич. - М.: Статистика, 1980. 263 с.

14. Моделирование и оптимизация сложных систем. Киев: Вища шк., 1987. 109 с.

б) Дополнительная литература

1. Дудорин В.И., Алексеев Ю.Н. Системный анализ экономики на ЭВМ / В.И. Дудорин, Ю.Н. Алексеев. - М.: Финансы и статистика, 1986. 191 с.

2. Колесников А.Н. Краткий курс математики для экономистов: учеб. пособие / А.Н. Колесников. - М.: ИНФРА-М, 1997. 208 с.

3. Красс М.С. Математика для экономических специальностей: учебник / М.С. Красс. - М.: ИНФРА-М, 1998. 464 с.

4. Высшая математика для экономистов: учеб. пособие для вузов / под ред. Н.Ш. Кремера. - М.: Банки и биржи, ЮНИТИ, 1997. 439 с.

5. Колемаев В.А. Теория вероятностей и математическая статистика: учебник / В.А. Колемаев, В.Н. Калинина. - М.: ИНФРА-М, 1997. 302 с.

6. Математическая экономика на персональном компьютере: пер.с яп. / под ред. М. Кубонива. - М.: Финансы и статистика, 1991. 304 с.

7. Горчаков А.А., Орлова И.В. Компьютерные экономико-математические модели: учеб. пособие для вузов / А.А. Горчаков, И.В. Орлова . - М.: Компьютер, ЮНИТИ, 1995. 136 с.

8. Лопатников Л.И. Экономико-математический словарь/Словарь современной экономической науки. Л.И. Лопатников. - М.: Издательство "АВF", 1996.

9. Питерсон Дж. Теория сетей Петри и моделирование систем / Дж.Питерсон. - М.: Мир, 1984. 264 с.

в) Методическая литература

1. Советов Б.Я. Моделирование систем. Курсовое проектирование: учеб. пособие / Б.Я. Советов. - М.: Высш. шк. 1988. 135 с.

2. Советов Б.Я. Моделирование систем. Лабораторный практикум / Б.Я. Советов. - М.: Высш. шк. 1989.- с. 79 с

3. Советов Б.Я. Моделирование систем: практикум. Б.Я. Советов М.: Высш. шк. 1999.- 224 с.

СОДЕРЖАНИЕ

ОБЩИЕ МЕТОДИЧЕСКИЕ УКАЗАНИЯ………...…………..1

ВОПРОСЫ ДЛЯ ПИСЬМЕННОГО ОТВЕТА……..…………2

1. МОДЕЛИРОВАНИЕ СТРУКТУР

ПРОИЗВОДСТВЕННЫХ СИСТЕМ…………...…………...6

2.МЕТОД КОРРЕЛЯЦИОННО-РЕГРЕССИОННОГО

АНАЛИЗА………….………………………………………...16

3. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ…………....23

4. ОПРЕДЕЛЕНИЕ НАДЁЖНОСТИ

ПРОИЗВОДСТВЕННЫХ СИСТЕМ……………………….31

ПРОГРАММА ДИСЦИПЛИНЫ……………………..……….33

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА………………..……….37

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

по изучению дисциплины «Методы моделирования

производственных систем» и контрольные задания

для студентов специальности 080502 «Экономика и

управление на предприятии» заочной формы

обучения и экстерната

Составитель

Амелин Станислав Витальевич

В авторской редакции

Подписано в печать 11.06.2008.

Формат 60 х 84 / 16. Бумага для множительных аппаратов.

Усл. печ. л. 2,6. Уч.-изд. л. 2,4. Тираж 200 экз. «С» .

Зак. №

ГОУВПО "Воронежский государственный технический

университет"

394026 Воронеж, Московский просп., 14