- •Экономико-математические методы и модели
- •Содержание
- •Лекция 1. Теоретические основы экономико-математического моделирования
- •1 Объекты изучения и методы исследования курса «Экономико-математические методы и модели»
- •2 Понятие экономико-математической модели и моделирования
- •3 Классификация экономико-математических моделей
- •4 Основные этапы экономико-математического моделирования
- •5 Программное обеспечение экономико-математического моделирования
- •Лекция 2. Система экономико-математических моделей оптимального планирования и управления
- •1 Понятие оптимизационных задач и оптимизационных моделей
- •2 Методика построения оптимизационной модели
- •3 Основные типы линейных экономико-математических моделей
- •1.3 Модели рационального распределения материальных ресурсов. В общем виде данная задача может быть сформулирована следующим образом:
- •Лекция 3. Экономико-статистическое моделирование и прогнозирование
- •1 Понятие экономико-статистической модели
- •2 Основные инструменты анализа экономических данных1
- •3 Применение корреляционного анализа для решения экономических задач1
- •4 Применение регрессионного анализа для решения экономических задач1
- •5 Трендовые модели прогнозирования экономических процессов
- •Лекция 4. Модели оптимального управления товарными запасами
- •1 Основные понятия экономико-математических моделей управления запасами
- •2 Модели управления однономенклатурными запасами1
- •3 Модели управления многономенклатурными запасами2
- •Лекция 5. Модели систем массового обслуживания
- •1 Понятие о системах массового обслуживания (смо)
- •2 Основные характеристики смо1
- •3 Классификация смо
- •4 Экономико-математическая постановка задач массового обслуживания
- •Лекция 6. Методы и модели сетевого планирования и управления
- •1 Особенности и назначение систем сетевого планирования и управления
- •2 Основные понятия, определения и графические обозначения спу
- •3 Правила построения сетевых графиков
- •4 Основные параметры сетевых моделей и методы их расчета
- •5 Постановка задач для решения методами спу
- •6 Виды и сущность оптимизации сетевых моделей
- •Лекция 7. Экономико-математические методы и модели теории игр
- •1 Предмет и задачи теории игр
- •2 Матричные игры с нулевой суммой
- •3 Решение матричных игр в чистых стратегиях
- •4 Решение матричных игр в смешанных стратегиях
- •5 Решение статистических игр по различным критериям
- •Лекция 8. Модели межотраслевого баланса
- •1 Общие понятия балансового метода
- •2 Принципиальная схема межотраслевого баланса
- •3 Экономико-математическая модель межотраслевого баланса
- •Литература
1.3 Модели рационального распределения материальных ресурсов. В общем виде данная задача может быть сформулирована следующим образом:
а) имеется т видов исходных материальных ресурсов, объемы которых ограничены определенной величиной аi; i = l, 2, ..., m;
б) из этих ресурсов необходимо изготовить п видов продукции, при этом минимальный объем выпуска продукции каждого вида bj задан в производственном плане; j = 1, 2,…, n;
в) заданы нормы расхода ресурса i-го вида на выпуск единицы j-ой продукции aij, которые принимаются постоянными, не зависящими от объема выпуска продукции;
г) известна прибыль, получаемая при реализации единицы j-го вида продукции, cj (или себестоимость изготовления этой единицы sj), эти величины также принимаются не зависящими от объемов выпуска.
Требуется составить такой план распределения исходных материальных ресурсов, чтобы сумма прибыли от реализации всей продукции была максимальной (или общая себестоимость изготовленной продукции была минимальной).
Экономико-математическая постановка задачи. Обозначим через хj количество продукции j-го вида, которое следует изготовить в целях удовлетворения выбранного критерия оптимальности. Требуется определить множество неотрицательных переменных хij > 0, где j = 1,2,…,n, удовлетворяющих ограничениям по ресурсам
(2.12)
и ограничениям по плану производства
. (2.13)
При этом целевая функция имеет вид
- для прибыли , (2.14)
- для себестоимости . (2.15)
1.4 Модели оптимального составления смесей. В ряде производств готовая продукция получается путем смешивания различных исходных компонентов, при этом качество готовой продукции должно соответствовать определенным требованиям при достижении максимального экономического эффекта. Оптимизация состава исходных компонентов представляет собой экономико-математическую задачу, которая называется задачей о смесях.
В общем виде задача о смесях может быть сформулирована следующим образом. Состав готовой продукции определяется содержанием в нем т видов элементов, содержание которых лимитируется величиной li (i = 1, 2, ..., m). Для k элементов, ухудшающих качество продукции, задана верхняя граница содержания того или иного элемента (), а для(m - k) элементов, улучшающих качество продукции, задана нижняя граница содержания элемента в готовой продукции (). Для производства готовой продукции может быть использовано n видов компонентов, объемы которых ограничены величиной bj (j = 1,2,..., n). Известно содержание i-го элемента в j-ом компоненте, которое обозначим как аij. Известна стоимость отдельных компонентов, включая расходы на их переработку, которую обозначим как сj. Наконец, задано общее количество М готовой продукции, которое следует изготовить по плану. Требуется составить такую смесь из имеющихся компонентов, чтобы затраты на это составление были минимальными.
Экономико-математическая постановка задачи. Обозначим количество используемого для составления смеси j-го компонента через xj, вектор, координатами которого являются величины xj, обозначим через . Целевая функция задачи имеет вид
, (2.16)
а ограничения формируются следующим образом:
(2.17)
(2.18)
(2.19)
(2.20)
Ограничения (2.17) относятся к элементам, ухудшающим качество; (2.18) - к элементам, улучшающим качество; (2.19) - по плану производства; (2.20) - по ограничению ресурсов.
1.5 Задача о ранце (или о рюкзаке). Так называется задача о наилучшем выборе предметов из общего их количества таким образом, чтобы суммарный вес (или габариты) отобранных предметов не превышал заданной величины, а их суммарная полезность или иная общая оценка (количество калорий, общая стоимость и т. д.) была максимальной. Задача о ранце решается как задача целочисленного линейного программирования, методами динамического программирования и другими методами. В частности, эта задача применяется при планировании оптимальной загрузки складов и др.
2 Модель транспортной задачи линейного программирования. Сущность транспортной задачи линейного программирования состоит в наивыгоднейшем прикреплении поставщиков однородного продукта ко многим потребителям этого продукта. На практике постоянно возникает необходимость решения таких задач, особенно когда количество пунктов отправления и получения грузов увеличивается.
Модель транспортной задачи линейного программирования может использоваться для планирования ряда операций, не связанных с перевозкой грузов. Так, с ее помощью решаются задачи по оптимизации размещения производства, топливно-энергетического баланса, планов загрузки оборудования, распределения сельскохозяйственных культур по участкам различного плодородия и т.п.
В торговле модель транспортной задачи линейного программирования применяется для решения следующих задач: планирование товароснабжения города, района; прикрепление торговых предприятий к поставщикам; организация рациональных перевозок товаров из пунктов отправления (баз, станций, фабрик, совхозов, заводов) в пункты назначения (магазины, склады); распределение работников торговли по должностям (задача о назначении); планирование капиталовложений; оптимизация межотраслевых связей торговли; размещение розничной торговой сети города и т.д.
Условие транспортной задачи обычно записывается в виде матрицы, в которой потребители однородного груза размещаются по столбцам, а поставщики – по строкам. В последнем столбце матрицы проставляют запас груза, имеющийся у каждого поставщика, а в последней строке – потребность в нем потребителей. На пересечении строк со столбцами (в клетках матрицы) записывают размер поставки, а также расстояние пробега по всем возможным маршрутам, время доставки груза или затраты на перевозку единицы груза по этим маршрутам.
Математически транспортная задача по критерию стоимости формируется следующим образом.
2.1 Статическая модель оптимизации прикрепления потребителей к поставщикам. В т пунктах отправления A1, A2, ..., Аm, которые в дальнейшем будем называть поставщиками, сосредоточено определенное количество единиц некоторого однородного продукта, которое обозначим ai (i = 1, 2,..., т).
Данный продукт потребляется в n пунктах B1, B2, ..., Bn, которые будем называть потребителями; объем потребления обозначим bj (j = 1, 2, …, n).
Известны расходы на перевозку единицы продукта из пункта Аi в пункт Вj, которые равны cij и приведены в матрице транспортных расходов С = (cij).
Требуется составить такой план прикрепления потребителей к поставщикам, другими словами, план перевозок, при котором весь продукт вывозится из пунктов Ai в пункты Bj в соответствии с потребностью и общая величина транспортных издержек минимальна.
Экономико-математическая постановка задачи. Обозначим количество продукта, перевозимого из пункта Аi в пункт Вj через xij. Совокупность всех переменных xij для краткости обозначим символом , тогда целевая функция задачи приобретет вид
, (2.21)
а ограничения выглядят следующим образом:
(2.22)
; (2.23)
. (2.24)
Условия (2.22) означают полное удовлетворение спроса во всех пунктах потребления; условия (2.23) определяют полный вывоз продукции от всех поставщиков.
Необходимым и достаточным условием разрешимости задачи (2.21-2.24) является условие баланса
. (2.25)
Транспортная задача, в которой имеет место равенство (2.25), называется закрытой и может быть решена как задача линейного программирования.
2.2 Модель оптимизации загрузки производственных мощностей. В общем виде эту задачу можно сформулировать следующим образом.
Имеется т предприятий (например, филиалов фирмы), которые могут производить n видов продукции. Известны:
а) аi - фонд рабочего времени (например, в сменах) каждого i-го предприятия; i = 1, 2,..., т;
б) bj - величина потребности в продукции j-го вида; j = 1, 2, ..., п;
в) aij - мощность, или количество продукции j-го вида, вырабатываемой (в смену) на i-ом предприятии;
г) cij - себестоимость производства единицы j-ой продукции на i-ом предприятии.
Требуется составить такой план распределения заказов на продукцию по всем предприятиям, при котором суммарные затраты по изготовлению продукции в заданной номенклатуре будут минимальными при полной загрузке производственных мощностей предприятий.
Экономико-математическая постановка задачи. Пусть xij - планируемый объем выпуска j-ой продукции на i-ом предприятии; совокупность таких величин обозначим . Тогда целевая функция рассматриваемой задачи имеет вид
(2.26)
при ограничениях
; (2.27)
(2.28)
. (2.29)
Если снять условие полной загрузки производственных мощностей предприятий, то ограничения (2.27) примут вид неравенств
; (2.30)
если условие точного выполнения плана в заданной номенклатуре заменить требованием «не меньше», то условия (2.28) превратятся в неравенства
. (2.31)
Очевидно, задачу (2.26) - (2.29) можно решить как задачу линейного программирования. Однако если привести определенными приемами коэффициент аij к единице, то данная модель не будет отличаться от модели транспортной задачи.
2.3 Модель рационального распределения работников по должностям (задача о назначении). В сфере торговли и общественного питания часто возникают задачи, связанные с рациональным распределением работников или механизмов по отдельным видам работ. Известно, что один и тот же работник может выполнить различные функции с разной производительностью в зависимости от опыта работы, квалификации, индивидуальных особенностей. Поэтому возникает задача о назначениях, предполагающая такое распределение работников, при котором производительность труда в коллективе была бы максимальной.
Приведем следующий пример. В универмаге имеется n работников: A1, А2, ..., Аi, …, An, каждый из которых может выполнять одну Вj из имеющихся n видов работ: B1, B2, ..., Bj, …, Bn.
Для каждого работника Аi на любом рабочем месте Вj известна производительность труда аij. Полагаем, что если работник назначен на работу Вj, то переменная назначения хij = 1, или xij = 0, если он на эту работу не назначен, что можно записать так
(2.32)
Условия задачи удобно записать в виде двойной матрицы и.
Если работник А1 назначен на работу B1, то x11 = 1, а остальные элементы назначения первой строки и первого столбца равны нулю. Из этого следует, что сумма переменных любой строки или столбца равна 1. Перечисленные ограничения задачи можно записать таким образом:
(2.33)
В качестве критерия оптимальности выбираем суммарную производительность работников. Тогда целевую функцию можно записать таким образом:
. (2.34)
Задача заключается в отыскании таких неотрицательных значений xij > 0 системы линейных равенств (ограничений), чтобы общая производительность труда всех работников была бы максимально возможной.
2.4 Задача о коммивояжере. В задаче о коммивояжере требуется отыскать наилучший маршрут, с тем чтобы объехать все порученные коммивояжеру пункты и вернуться назад либо в кратчайший срок, либо с наименьшими затратами на проезд.
В общем виде эту задачу можно сформулировать следующим образом. Имеется n городов, занумерованных числами от 1 до n. Коммивояжер, выезжая из города 1, должен побывать в каждом городе ровно один раз и вернуться в исходный пункт. Известны расстояния cij () между городами. Требуется найти самый короткий маршрут.
Введем переменные:
(2.35)
Требования однократного въезда и выезда из каждого города запишутся в виде
(2.36)
Однако эти ограничения полностью не описывают допустимые маршруты, так как не исключают возможности разрыва пути, т. е. появления нескольких не связанных между собой подмаршрутов для части городов. Поэтому вводят дополнительно n переменных Ui, принимающих только целые неотрицательные значения, и записывают еще [(n - 1)2 - (n - 1)] ограничений
. (2.37)
Нетрудно показать, что ограничения (2.37) не исключают допустимый маршрут, но исключают возможность существования подмаршрутов.
Таким образом, задача коммивояжера состоит в минимизации:
(2.38)
при условиях (2.36) и (2.37), где переменные хij, Ui принимают только неотрицательные целые значения.
К задаче о коммивояжере сводятся задачи выбора маршрута при развозке грузов, например при выборе оптимальных маршрутов автотранспорта при кольцевой доставке товаров в торговую сеть, а также ряд других задач маркетинга. В общем случае задача о коммивояжере решается методами динамического программирования; применяются также методы целочисленного программирования: метод отсекающих плоскостей, метод ветвей и границ и другие.
2.5 Задача о размещении складов является одной из оптимизационных задач исследования операций и решается обычно методами нелинейного программирования. Задача заключается в минимизации общей суммы транспортных и складских расходов при следующих ограничениях:
а) с каждого предприятия должна быть отгружена вся продукция;
б) не может быть превышена емкость ни единого склада;
в) должны быть удовлетворены заявки всех потребителей.
В процессе решения задачи находится оптимальная по минимуму затрат трехчленная комбинация: предприятие - склад - потребитель. При некоторых условиях задача о размещении складов может сводиться к обычной транспортной задаче линейного программирования.
3 Модель распределительной задачи линейного программирования часто называют обобщенной транспортной задачей. Наиболее типичными для ее интерпретации являются задачи использования взаимозаменяемых ресурсов.
Приведем следующий пример. В цеху изготовляются n видов изделий, причем каждое изделие может производиться на любом из имеющихся m групп оборудования. Время изготовления и затраты по обработке отдельных изделий j-ого вида на станках i-ой группы равны λij ч и cij ден. ед. Имеется заказ на изготовление bj изделий j-го вида. Наличное время работы станков ограничено, оно составляет аi станко-часов для i-ой группы оборудования.
Нужно так распределить производство n видов изделий на m группах взаимозаменяемого оборудования, чтобы план по номенклатуре был выполнен и затраты на обработку сводились к минимуму.
Экономико-математическая модель задачи. Обозначив через xij количество изделий j-го вида, обрабатываемых на i-ой группе оборудования, приходим к следующей математической модели распределительной задачи:
1) количество изделий данного вида, обрабатываемых на взаимозаменяемых группах оборудования, должно равняться потребности в них:
(2.39)
2) время работы отдельных групп оборудования ограничено:
(2.40)
3) количество обрабатываемых изделий на различных группах оборудования должно выражаться неотрицательными числами:
(2.41)
4) общая сумма затрат на обработку изделий должна быть минимальной:
. (2.42)
Общего математического метода решения таких задач не существует. В подобных случаях используют метод направленного перебора. Кроме того, распределительную задачу можно привести к виду общей задачи линейного программирования.
4 Модель ассортиментной задачи линейного программирования сформулирована Л. В. Конторовичем. Им же разработан метод решения задач данного класса. Ее можно решать на основе системы ограничений общей или распределительной задачи линейного программирования.
Особенность целевой функции состоит в том, что ставится задача максимизации количества комплектов изделий, то есть
, (2.43)
где с - количество комплектов;
kj - количество j-х изделий, входящих в комплект ();
хj - количество производимых изделий j-го вида.
Модель ассортиментной задачи в системе ограничений общей задачи линейного программирования:
1) учитываются лимитирующие условия в задаче:
; (2.44)
2) соблюдается неотрицательность переменных величин:
; (2.45)
3) максимизируется производство комплектной продукции:
, (2.46)
где aij - расход лимитирующего ресурса i-го вида на j-ое изделие;
аi - располагаемый фонд ресурса i-ro вида.
Когда необходимо распределить обработку комплектных изделий на взаимозаменяемых группах оборудования, используют ограничения распределительной задачи. Отсюда модель ассортиментной задачи в системе ограничений распределительной задачи линейного программирования:
1) учитывается время работы i-ой группы оборудования:
(2.47)
2) количество обрабатываемых изделий на различных группах оборудования должно выражаться неотрицательным числом:
(2.48)
3) максимизируется производство комплектной продукции:
, (2.49)
где λij - время обработки j-го изделия на i-й группе оборудования;
Аi - располагаемый фонд времени работы i-й группы оборудования;
с - количество комплектов;
kj - количество j-х изделий, входящих в комплект;
хij - количество изделий j-го вида, обрабатываемых на i-й группе оборудования.