Экономико-математические методы и модели в управлении производством Лекции для студентов 6 курса ФЭиМ, з/о, спец. 080502 Экономика и управление на предпри- - презентация

1 Экономико-математические методы и модели в управлении производством Лекции для студентов 6 курса ФЭиМ, з/о, спец Экономика и управление на предпри- ятии полиграфической промышленности

2 1.Задачи и методы экономико- математического моделирования производственных систем

3 Экономико-математическая модель производственной системы Экономико-математические методы и модели (ЭММиМ) предназначены для поиска и обоснования путей повышения эффективности производства, рационального использования ресурсов, обеспечения конкурентноспособности предприятий в условиях рыночной экономики. На основе ЭММиМ с помо- щью современных компьютерных технологий получают дан- ные для анализа производственных систем, прогнозирования их поведения при возможных изменениях производственной ситуации и выработки управленческих решений для дости- жения поставленных целей. Экономико-математической модель – это формализо- ванное (математическое) описание условий и результатов функционирования производственной системы с позиций экономики. Модель строится с помощью переменных, множеств, функций, уравнений, неравенств, логических правил. 1

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

5 Задача математического программирования Найти max (min) при условиях где f, g i, - заданные, в общем случае нелинейные функции n переменных - b i – заданные параметры. Запись означает, что может иметь место неравенство вида, уравнение или неравенство вида. В экономических приложениях функцию f называют целевой функцией. Если f и g i, - линейные функции, то имеет место задача линейного программирования. 1

6 Оптимальное решение задачи математического программирования Каждый набор значений переменных, (n-мерный вектор), удовлетворяющий всем ограничениям задачи, называется ее решением или планом. Множество всех решений задачи образует область допустимых решений (ОДР). Каждому плану соответствует определенное значение целевой функции. План, которому соответствует максималь- ная - в задаче максимизации, минимальная - в задаче минимизации - величина f, носит название оптимального и обозначается Решить задачу математического программирования - это значит найти ее оптимальный план и соответствующее ему значение целевой функции. 1

7 Задачи линейного программирования Наиболее популярными задачами математического программирования для экономических приложений являются задачи линейного программирования, в которых целевая функция f и функции ограничений являются линейными функциями неизвестных x 1, x 2, …, x n : Найти мах (min) f = при условиях 2

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

9 Обобщенная модель академика Л.В. Канторовича Задача планирования производства наряду с задачами раскроя материалов, загрузки производственного оборудова- ния и рядом других задач линейного программирования относится к задачам технико-экономического планирования, для которых академик Канторович Л.В. предложил обобщен- ную модель, введя понятия ингредиентов и способов функци- онирования производственной системы. Под ингредиентами производственной системы понима- ются готовая продукция и услуги, производимые системой (накапливаемые ингредиенты), а также используемые в процессе производства материальные, трудовые, финансовые и др. ресурсы (потребляемые ингредиенты). Под способами функционирования производственной системы понимаются различные варианты использования имеющихся ресурсов для производства продукции и услуг. 2

10 Структура обобщенной модели В экономико-математической модели задачи технико- экономического планирования неизвестные соответствуют возможным способам функционирования производственной системы, значения неизвестных - интенсивности применения различных способов функционирования. Число основных ограничений в модели совпадает с числом ингредиентов, причем накапливаемым ингредиентам соответствуют уравнения и неравенства вида, потребляемым ингредиентам – неравенства вида. Введенные понятия способов функционирования и ингредиентов производственной системы позволяют наглядно интерпретировать экономическую суть рассматриваемой задачи и результаты ее решения. 2

11 Методы математического программирования Математическое программирование Выпуклое программирование Линейное программирование Параметрическое программирование Стохастическое программирование Целочисленное программирование Динамическое программирование Не существует единого, универсального метода решения задач математического программирования. В зависимости от свойств целевой функции f и функций ограничений g i рассматривают различные классы задач математического программирования и применяют различные методы их решения. 1

12 Программные средства решения оптимизационных задач Перечисленные методы решения оптимизационных задач в том или ином виде реализованы в современных пакетах компьютерной математики. Однако, наиболее полным и удобным инструментом решения оптимизационных задач экономико-математического моделирования следует признать пакет Поиск решения, который является одной из надстроек ЭТ Excel и предназначен для решения задач линейного, выпуклого и целочисленного программирования. Полезным дополнением к Поиску решения может служить пакет Линейное программирование, в котором удачно решена проблема анализа устойчивости оптимального решения задачи линейного программирования при измене- ниях параметров задачи. 1

13 2. Экономико-математические модели задачи планирования производства

14 Постановка задачи планирования производства (базовая модель) Предприятие может производить продукцию n видов, используя m видов ресурсов. Известны: a ij, i=1,...,m, j=1,...,n - нормы затрат ресурсов каждого вида на производство единицы продукции различного вида; b i, i=1...,m - запасы ресурсов; c j, j=1,...,n - прибыль от реализации единицы продукции каждого вида. Требуется найти объемы производства продукции каждого вида x j, j=1,...,n, при которых будет достигнута максимальная суммарная прибыль f при условии сбалансированности плана производства продукции по каждому виду ресурсов. 3

15 Базовая модель задачи планирования производства Найти max f = при условиях 3

16 Модифицированная модель задачи планирования производства Найти max f = Q – сумма на приобретение дополнительных ресурсов; s i, i=1,...,m – стоимость единицы i-го ресурса; z i, i=1,...,m – число приобретаемых единиц i-го ресурса; u j, j=1,...,n – объем спроса, v j, j=1,...,n – объем заказа на продукцию j-го вида. при условиях 4

17 Пример задачи планирования производства Исходные данные Обозначения неизвестных x1_1 - планируемый объем выпуска продукции 1-го вида по 1-му технологическому варианту; x1_2 - планируемый объем выпуска продукции 1-го вида по 2-му технологическому варианту; x4_3 - планируемый объем выпуска продукции 4-го вида по 3-му технологическому варианту; z2 - число приобретаемых единиц ресурса 2-го вида; z5 - число приобретаемых единиц ресурса 5-го вида. 5

18 Числовая модель задачи планирования производства 5

19 3. Компьютерные методы решения задачи планирования производства

20 Программные средства для решения задачи планирования производства Для решения задачи планирования производства приме- няются две компьютерные программы: Надстройка Поиск решения ЭТ Excel. Пакет Линейное программирование (файл lp83.exe). Достоинством Поиска решения является простота и удобство подготовки исходных данных, возможность получе- ния целочисленного решения, использование встроенных средств Excel для постоптимизационного анализа и нагляд- ного представления полученных результатов в виде таблиц, графиков и диаграмм. Пакет Линейное программирование позволяет проводить параметрирование задачи, выводит информацию о диапазонах устойчивости при стоимостном и граничном анализе оптимального решения.

21 Компоновка ЭТ и настройкаПоиска решения

22 4. Экономико-математическая модель оптимального раскроя материала

23 Постановка задачи оптимального раскроя материала Базовая модель задачи о раскрое соответствует одному виду исходного материала (листов или рулонов), который используется для получения m видов заготовок в заданных объемах b i, i=1,...,m. Разработано n возможных вариантов раскроя, каждый из которых характеризуется нормами выхода заготовок каждого вида из одного листа (рулона) a ij, i=1,..., m, j=1,..., n и площадью листа (рулона), идущей в отход c j, j=1,...,n. Требуется найти оптимальный план раскроя материала, при котором производственные задания по каждому виду заготовок будут выполнены с минимальными отходами материала при раскрое. 6

24 Базовая модель задачи оптимального раскроя материала Обозначив x j, j=1,...,n - число листов (рулонов), раскраиваемых по j-му варианту, f – суммарную площадь отходов материала, запишем базовую модель задачи оптимального раскроя материала в виде: Найти min f = при условиях 6

25 Комментарии к базовой модели раскроя материала В качестве целевой функции можно использовать суммарное число листов (рулонов), необходимых для раскроя заданного числа заготовок: Основные ограничения могут быть записаны в виде уравнений, однако, в этом случае при неблагоприятном соотношении размеров заготовок, размеров исходного материала и требуемого числа заготовок задача может не иметь решения. С другой стороны, заготовки, выкраиваемые сверх установленного производственного задания, могут рассматриваться как скрытые отходы. При экономическом анализе результатов решения задачи о раскрое на эти обстоятельства необходимо обратить особое внимание. 6

26 5. Оптимизация загрузки производственного оборудования

27 Структурная схема производственной системы (участка) Структурная схема производственной системы с взаимозаменяемым оборудованием 7

28 Постановка задачи оптимизации загрузки оборудования На участке, оснащенном m разнотипными взаимозаменяемыми машинами, планируется обработка n заказов. Известны фонды машинного времени (в часах) для каждой машины a i, i = 1, …, m; производственные задания (в учетных единицах) по каждому заказу b j, j = 1, …, n; время, затрачиваемое на обработку одной учетной единицы каждого заказа на каждой машине t ij, i = 1, …, m, j = 1, …, n. Кроме того, определены удельные затраты, связанные с обработкой заказов на различных машинах c ij, i = 1, …, m, j = 1, …, n (в д.ед/уч.ед.). Требуется так распределить заказы на машины, чтобы минимизировать суммарные затраты на выполнение производственных заданий по всем заказам, обеспечив при этом работу каждой машины в пределах располагаемого фонда машинного времени. 7

29 Базовая модель оптимизации загрузки производственного оборудования Найти min f = при условиях x ij – число учетных единиц j-го заказа, обрабатываемых на i-й машине; f – общие затраты на обработку всех заказов. 7

30 6. Транспортная задача линейного программирования

31 Постановка транспортной задачи В m пунктах отправления (у поставщиков) сосредоточено a i, i=1,...,m единиц однородного груза, который следует доставить в n пунктов назначения (потребителям) с потребностями в грузе b j, j=1,...,n. В базовой (закрытой) модели транспортной задачи предполагается, что суммарные запасы груза в пунктах отправления равны суммарным потребностям в грузе пунктов назначения: Известны затраты на перевозку единицы груза из каждого пункта отправления в каждый пункт назначения: c ij, i=1,...,m, j=1,...,n. Необходимо найти план перевозки груза, при котором весь груз будет вывезен из пунктов отправления, в каждый пункт назначения будет доставлено требуемое число единиц груза и при этом общие затраты на перевозку груза будут минимальными. 8

32 Математическая модель транспортной задачи (закрытого типа) Найти min f = при условиях x ij – число единиц груза, подлежащих перевозке из i -го пункта отправления в j -й пункт назначения; f – общие затраты на перевозку груза. 8

33 Постановка задачи о назначениях Частным случаем транспортной задачи является следующая задача о назначениях. Имеется n должностей и n претендентов на эти должности. Известна полезность каждого претендента при назначении на каждую из должностей, т.е. задана матрица c ij, i,j=1,...,n. Требуется произвести назначение каждого претендента на одну из должностей, обеспечив при этом максимальную суммарную полезность назначений. Обозначим через x ij, i,j=1,...,n неизвестные, которые будут принимать значение, равное единице, если i-й претендент получает назначение на j-ю должность, и нулю - в противном случае; через f обозначим суммарную полезность назначений. 8

34 Математическая модель задачи о назначениях Найти max f = при условиях Переменные, которые могут принимать одно из двух значе- ний: 0 или 1, называются булевыми переменными. Задача о назначениях является задачей с булевыми неизвестными - частным случаем задачи целочисленного линейного программирования. 8

35 Пример задачи о назначениях Группа из 5 студентов сдает экзамен 5 преподавателям. Прогнозные значения оценок приведены в табл. Необходимо найти оптимальный план назначений студентов к преподава- телям, обеспечивающий максимальную сумму оценок, полученных студентами. 8

36 7. Двойственность в линейном программировании

37 Правила построения двойственной задачи Число неизвестных двойственной задачи равно числу основных ограничений исходной задачи и, наоборот. Матрица основных ограничений двойственной задачи образуется путем транспонирования соответствующей матрицы исходной задачи. Параметрами ограничений (правыми частями) двойствен- ной задачи служат коэффициенты при неизвестных в целевой функции исходной задачи и, наоборот. Знаки неравенств основных ограничений двойственной задачи противоположны знакам неравенств основных ограничений исходной задачи; если исходная задача - на максимум, то двойственная к ней - на минимум и, наоборот. 9

38 Задача оптимизации условных (внутренних) цен ресурсов Найти min z = при условиях y i, i=1,...,m - неизвестные двойственной задачи (условные цены ресурсов). Условные цены ресурсов отражают значимость ресурсов в конкретных условиях данной производственной ситуации 9

39 Первая теорема двойственности Теоремы двойственности устанавливают взаимосвязь меж- ду оптимальными решениями прямой и двойственной задач. Согласно первой теореме двойственности суммарная стоимость ресурсов по оптимальным условным ценам равна общей прибыли от реализации всей продукции, изготовлен- ной предприятием при оптимальном плане выпуска продук- ции из имеющихся запасов ресурсов. Условные цены ресурсов характеризуют приращение суммарной прибыли на каждую дополнительную единицу запаса соответствующего ресурса. 10

40 Иллюстрация первой теоремы двойственности 10

41 Вторая теорема двойственности Вторая теорема двойственности устанавливает соотношения между компонентами оптимальных решений прямой и двойственной задач. Для того, чтобы допустимые решения x 1,x 2,...,x n ; y 1,y 2,...,y m прямой и двойственной задач были бы их оптимальными решениями, необходимо и достаточно выполнение условий: 11

42 Экономическая интерпретация второй теоремы двойственности Ресурс i-го вида имеет ненулевую цену, если полностью расходуется в процессе производства (такой ресурс будем называть дефицитным). Продукции j-го вида производится, если стоимость затраченных на ее производство ресурсов по условным ценам равна прибыли от реализации данной продукции (такой вид продукции будем называть базисным). Сравнительно небольшие изменения удельной прибыли или запасов ресурсов не приводят к нарушению условий второй теоремы двойственности: оптимальная номенкла- тура выпускаемой продукции и состав дефицитных ресурсов остаются неизменными. 11

43 8. Постоптимизационный анализ решения задачи планирования производства

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

45 Требования к рекомендуемому плану выпуска продукции Объемы выпуска продукции должны быть целочислен- ными значениями, кратными установленному размеру партии, например, 10, 20 или 50 единицам; План не должен включать малообъемные компоненты, т.е. должны быть установлены пороговые значения, ограничивающие снизу ненулевые объемы выпуска продукции, предлагаемой для производства; Потери прибыли по сравнению с теоретически оптималь- ным решением не должны превышать установленной величины, например, 5%. 13

46 Задача планирования производства с комплектным выпуском продукции Найти max f = при условиях k – размер партии ; p j, j=1,..., n – число производимых партий продукции j- го вида (неизвестные); d j, j=1,..., n – минимально допустимое число производимых партий продукции j- го вида. 13

47 Интерактивный метод ветвей и границ Задача формирования целочисленного плана выпуска продукции с пороговыми значениями объемов выпуска продукции является задачей нелинейного целочисленного программирования и не может быть решена в автоматиче- ском режиме с помощью пакета Поиск решения ЭТ Excel. Для ее решения применяется интерактивный метод ветвей и границ: решение исходной задачи нелинейного целочислен- ного программирования сводится к решению последователь- ности порожденных задач линейного целочисленного программирования, каждая из которых формируется в интерактивном режиме с учетом ограничений, связанных с пороговыми значениями объемов выпуска продукции. При описании интерактивного метода ветвей и границ используются понятия текущего, допустимого и приемлемого плана задачи с пороговыми значениями объемов выпуска продукции.

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

49 Тестовая целочисленная задача планирования производства Продемонстрируем методику формирования целочислен- ного плана выпуска продукции на примере тестовой задачи с дополнительными условиями: продукция производится партиями размером 10 ед.; пороговая величина объема выпуска продукции по каждому технологическому варианту для первого, второго и четвертого видов продукции равна 100 ед. (10 партий); для продукции третьего вида в соответствии с ограничением спроса пороговая величина объема выпуска равна 60 ед. (6 партий); при использовании целочисленного плана выпуска продукции потери прибыли не должны превышать 5% по сравнению с теоретически оптимальным решением.

50 Поиск оптимального целочисленного плана

51 Иерархическая структура множества порожденных задач

52 Разработка рекомендаций по допол- нительной подготовке производства Разработка предложений по дополнительной (по сравнению с рекомендуемым планом) организационно-технологической подготовке производства проводится на основе: Анализа возможных неблагоприятных структурных (качественных) изменений производственной ситуации и разработки альтернативных (аварийных) планов, минимизирующих потери суммарной прибыли в этих условиях. Анализа устойчивости оптимального плана при случайных количественных изменениях параметров производственной ситуации, не контролируемых со стороны предприятия (в пределах 30% от номинальных значений). 14

53 Альтернативные (аварийные) планы выпуска продукции Для минимизации потерь при неблагоприятных структурных изменениях производственной ситуации предприятие должно заблаговременно провести подготовку выпуска продукции: 1-го вида по 1-му технологическому варианту в объеме 120 ед. 2-го вида по 1-му технологическому варианту в объеме 120 ед. 4-го вида по 2-му технологическому варианту в объеме 120 ед. предусмотреть возможность увеличения выпуска продукции: 3-го вида по 1-му технологическому варианту до 60 ед. Для эффективного использования благоприятной ситуации при возраста- нии спроса на продукцию 1-го и 2-го вида необходимо предусмотреть возможность увеличения в 3 – 4 раза выпуска этих видов продукции. 14

54 Диапазон устойчивости оптимального плана Диапазоном устойчивости оптимального плана при изменении удельной прибыли c j называется множество значений c j, при которых остаются неизменными оптимальные объемы выпуска продукции, а оптимальные значения суммарной прибыли и цен дефицитных ресурсов линейно изменяются при переходе от нижней к верхней границе диапазона устойчивости (в частном случае, некоторые из них не изменяются). 15

55 График стоимостного анализа Сплошной линией показано изменение суммарной прибыли f при исполь- зовании оптимальных планов выпуска продукции для всех значений удельной прибыли c j. Пунктирная линия соответствует применению плана независимо от фактической величины удельной прибыли c j 15

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

57 Граничный анализ по параметру Сумма

58 Модель задачи планирования производства с расширением спроса Найти max f = Q – сумма на дополнительные ресурсы и расширение спроса; u j, j=1,...,n – имеющийся объем спроса на продукцию j-го вида, w j, j=1,...,n – расширение спроса на продукцию j-го вида, q j, j=1,...,n – затраты на единицу спроса. при условиях 16

59 Анализ перспектив развития производственной системы На основе комплексного подхода к наращиванию объемов ресурсов и расширению спроса предприятие может в несколько раз увеличить суммарную прибыль 16

60 Итоги постоптимизационного анализа задачи о планировании производства