Примеры линейных оптимизационных моделей

ПРЕДПРИНИМАТЕЛЬСТВА и ИНСТИТУТ ПАРЛАМЕНТАРИЗМА

Г.М. БУЛДЫК

ЭКОНОМИКО – МАТЕМАТИЧЕСКИЕ СПОСОБЫ

И

МОДЕЛИ

Часть I

Минск, 2010

УДК 338.2(075.8)

ББК 65.050я73

Б90

Р е ц е н з е н т ы: врач физико-математических наук, доктор наук В.В. Амелькин;

кандидат физико-математических наук, доцент А.Е. Руденок

Рекомендовано к изданию Научно-методическим советом университета, протокол № 2 от “ “ ноября 2010 года.

Булдык Г.М.

Б90Экономико-модели и математические методы.Учебное пособие в 2 ч. Часть I. – Мн.: ИПП. – 108 с., [ил.].

Рассматриваются современные способы математического моделирования разных экономических процессов.

Для студентов экономических профессий институтов; полезно экономистам-практикам.

Булдык Георгий Митрофанович – врач педагогических наук, доктор наук по профессии «Математика». Создатель более134 научно-методических работ. Среди них учебник «прогнозирование и Статистическое моделирование», учебные пособия: «математическая статистика и Теория вероятностей», «Сборник упражнений и задач по высшей математике. математическая статистика и Теория вероятностей», «Управление к ответу упражнений и задач по математической статистике и теории вероятностей», «Сборник упражнений и задач по высшей математике».

Главные научные интересы связаны с разработкой современной концепции преподавания математики. Г.М. Булдык есть автором монографий: «Формирование математической культуры студентов экономических профессий», «Многофакторные динамические модели».

© Булдык Г.М., 2010

ПРЕДИСЛОВИЕ

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

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

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

Главными задачами курса являются: 1) углубление и расширение теоретических знаний о закономерностях и количественных взаимосвязях экономразвития, механизмах управления народным хозяйством; 2) овладение методикой и методологией построения, применения и анализа математических моделей экономических процессов; 3) изучение самые характерных моделей и получение навыков практической работы с моделями, применяемыми в практике.

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

Введение

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

Действенных ответов

Предметом изучения дисциплины экономико-модели и математические методы являются количественные характеристики экономических процессов, протекающих в промышленном производстве, и их связи. В курсе рассматриваются экономические задачи и их математические модели.

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

Так, каждая экономико-математическая модель высказывает в математических соотношениях экономическую сущность условий задачи и поставленной цели изучения, т. е. экономические связи между экономическими параметрами либо размерами описываются математическими соотношениями. Академик Немчинов писал: «Экономико-математическая модель представляет собой концентрированное выражение неспециализированных закономерностей и взаимосвязей экономического процесса в математической форме».

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

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

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

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

Оптимизационные и балансовые экономико-математические модели содержат целевую функцию и систему ограничений.

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

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

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

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

Напомним, что в случае если модель имеет множество оптимальных замыслов, то для каждого из них значение целевой функции одно и также.

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

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

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

Постоянные размеры обозначаются — Они также будут иметь индексы: один — , либо пара индексов: .

Потом составляются главные (все учесть нереально) ограничения, каковые отражают все условия, формирующие оптимальный замысел.

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

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

Оптимизационные модели

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

Оптимизационные модели смогут носить детерминированный либо стохастический темперамент. В детерминированных моделях итог ответа конкретно зависит от входных данных. Стохастические модели обрисовывают случайные процессы, в которых итог постоянно остаётся неопределенным.

Самый созданы и фактически более применимы детерминированные модели, применяющие аппарат математического программирования.

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

В общем виде оптимизационную математическую модель возможно представить в следующем виде:

Отыскать замысел , что max (min) целевую функцию

(1.1)

при исполнении ограничений

(1.2)

где и — узнаваемые функции, — заданные постоянные размеры.

Вид целевой функции , специальные ограничения и вид ограничений на переменные (к примеру, требования целочисленности переменных) определяют выбор способа математического программирования для ответа оптимизационной задачи:

  • линейного программирования;
  • нелинейного программирования;
  • динамического программирования;
  • целочисленного программирования и т. д.

Мы остановимся на оптимизационных моделях, каковые решаются способами линейного программирования, т. е. разглядим оптимизационные модели (1.1) — (1.2) у которых ограничения и целевая функция линейные функции. Тогда оптимизационная математическая модель примет вид:

Отыскать замысел , что max (min) целевую функцию

(1.3)

при исполнении совокупности ограничений

(1.4)

(1.5)

(1.6)

(1.7)

Множество замыслов , удовлетворяющих совокупности ограничений (1.4) – (1.7), именуется множеством допустимых ответов и обозначается . Допустимый замысел , доставляющий целевой функции (1.3) экстремальное значение, именуется оптимальным.

Напомним, что максимизация целевой функции в области допустимых ответов эквивалентна задаче минимизации функции « » в той же области: .

В случае если все ограничения задачи заданы в виде равенств и на все переменные , наложено условие неотрицательности , то оптимизационная модель имеет каноническую форму записи:

max

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

.

В случае если ограничения заданы в виде неравенств, то оптимизационная модель имеет симметрическую форму записи:

max

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

,

либо

min

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

.

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

Примеры линейных оптимизационных моделей

Пример 1. Линейная оптимизационная модель годовой производственной программы предприятия.

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

Для построения модели введем обозначения:

  • — количество производства продукции — го вида, ;
  • — цена единицы продукции — го вида, ;
  • — время обработки — ой продукции на — том оборудовании;
  • — фонд времени работы оборудования — го вида.

Математическая модель разглядываемой задачи будет иметь вид:

Отыскать замысел выпуска продукции, при котором предприятие возьмёт максимум выручки

при ограничениях на фонд времени работы оборудования

.

Частным случаем разглядываемой модели есть оптимизационная модель применения ресурсов.

Предположим, что предприятие может изготавливать четыре вида продукции . Предприятие располагает нормами и ресурсами их расхода, приведенными в таблице 1.1

Таблица 1.1

Ресурсы Продукция Количество ресурса
П-1 П-2 П-3 П-4
Трудовые ресурсы, человеко-смены 2,5 2,5 1,5
Полуфабрикаты, кг
Станочное оборудование, станко-смены
Прибыль от единицы продукции, ден. ед.

Требуется: 1) выяснить замысел выпуска продукции, максимизирующей прибыль предприятия;

2) учесть требование комплектации, дабы количество единиц третьей продукции было вдвое больше количества единиц первой;

3) выяснить оптимальный ассортимент при дополнительных условиях: первой продукции производить не меньше 27 единиц, третьей – не более 35, а второй и четвертой – в отношении 2:3.

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

  • на трудовые ресурсы:
  • на полуфабрикаты:
  • на станочное оборудование:
  • условию неотрицательности переменных:
  • дополнительное требование комплектации: ;
  • дополнительные условия:

Линейная оптимизационная модель выстроена. Методы ответа разглядим ниже.

Пример 2. Линейная оптимизационная модель о выборе разработок.

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

Выстроим математическую модель, решая которую определим оптимальную разработку для выпуска однородной продукции. Пускай: — время, за который предприятие производит продукцию по — тому технологическому методу;

, , — цена конечной продукции, создаваемой в единицу времени, по — тому технологическому методу;

— расход — го ресурса в единицу времени по — тому технологическому методу.

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

Выяснить оптимальное использование технологических способов , при которых максимизируется количество выпуска ( в ден. ед.) продукции:

и, каковые удовлетворяют совокупности ограничений:

Предположим, что предприятие может трудиться по трем технологическим методам. Расход ресурсов за единицу времени при соответствующей технологии и производительность по каждому технологическому методу (в ден. ед.) в единицу времени, представим в таблице 1.2.

Таблица 1.2

Ресурсы Технологические методы Количество ресурса
Т-1 Т-2 Т-3
Трудовые ресурсы, человеко — часов 1 300
Сырье, т
Электричество, кВт/ч 3 000
Производительность технологического метода

Выяснить замысел применения технологических способов, при котором максимизируется количество выпуска продукции.

Выстроим математическую модель задачи. Пускай — время применения — го технологического метода. Требуется отыскать замысел , при котором целевая функция

достигает большого значения, и, что удовлетворяет ограничениям:

Пример 3.Линейная оптимизационная модель раскроя материалов.

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

Составим математическую модель данной задачи.

Обозначим количество страниц фанеры, раскраиваемых по j — тому методу. Определим замысел раскроя страниц фанеры так, дабы суммарное количество отходов по всем вариантам раскроя было минимальным:

и дабы выполнялись ограничения на изготовление подробностей:

Количество страниц фанеры, раскраиваемых по j — тому методу, должно быть неотрицательным:

.

Пример 4. Линейная оптимизационная модель о рационе.

Сельскохозяйственное предприятие для откорма скота располагает n видами кормов (сочные, неотёсанные, концентрированные и др.). Любой вид корма характеризуется содержанием питательных веществ (кормовые единицы, белки, фосфор, кальций и др.). Известно содержание i-го питательного вещества в единице корма j-го вида и равняется оно единиц ( , ), и – цена единицы корма j-го вида ( ) и минимальная дневная потребность скота в i-м питательном веществе ( ). Требуется составить рацион минимальной цене.

Для построения математической модели данной задачи обозначим — количество корма — го вида. Определим рацион , при котором суммарная цена рациона:

будет минимальной, а дневная потребность животного в питательном веществе — го вида будет не меньше предельного числа :

Количество корма, потребляемого животным, не может быть отрицательной величиной:

.

Пример 5. Линейная оптимизационная модель о назначениях.

Имеется n механизмов, каковые смогут употребляться для исполнения n работ. Известна производительность каждого i-го механизма ( ). Требуется так закрепить механизмы за работами, дабы суммарная их производительность была большой.

Для составления математической модели задачи введем переменные:

Отыщем замысел применения механизмов так, дабы их суммарная производительность была большой:

,

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

  • — ый механизм должен быть назначен лишь на одну работу:

,

  • любая работа обязана выполняться лишь одним механизмом:

.

Пример 6. Линейная оптимизационная модель о размещениях.

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

Введем обозначения и выстроим математическую модель задачи:

i – вид создаваемой продукции ( );

j – номер предприятия, создающего продукцию ( );

k – номер потребителя продукции ( );

– мощности j-го предприятия по производству продукции i-го вида;

– цена производства единицы продукции i-го вида на j-м предприятии;

– затраты на перевозку единицы продукции i-го вида от j-го предприятия k-му потребителю;

– размер поставки продукции i-го вида k-му потребителю в соответствии с договорным обязательствам;

– искомый количество производства продукции i-го вида на k-м предприятии;

– размер поставки j-м предприятием продукции i-го вида k-му потребителю.

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

.

Ограничения задачи:

  • по мощностям каждого предприятия

  • по балансу потребления и производства продукции

  • по удовлетворению спроса потребителей

  • производства продукции и объёмы поставок должны быть неотрицательными:

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

(1.8)

(1.9)

(1.10)

(1.11)

, ; (1.12)

– произвольные, .

с геометрической точки зрения. Целевая функция (1.8) определяет семейство параллельных гиперплоскостей уровня цели, каждой из которых соответствует определенное значение функции , так как при трансформации коэффициенты не изменяются. Потому, что частные производные целевой функции по переменным : определяют координаты вектора , то вектор — это вектор градиентного направления и, следовательно, определяет направление наискорейшего возрастания целевой функции , а вектор определяет направление наискорейшего убывания. Неравенства (1.9), (1.11) определяют полупространства, а (1.10) – гиперплоскости. Полупространства и гиперплоскости являются выпуклыми множествами. Множество точек выпукло, в случае если отрезок, соединяющий две произвольные точки этого множества, в собственности множеству. Пересечение конечного числа выпуклых множеств – множество выпукло. Следовательно, пересечение полупространств и гиперплоскостей определяет выпуклое множество, именуемое многогранным множеством либо многогранником. Многогранник (ограниченный либо неограниченный) – это область допустимых ответов линейной оптимизационной модели. Особенное значение имеют угловые (либо крайние) точки области допустимых ответов. Угловой ( крайней) точкой выпуклого множества именуется точка, если она не есть внутренней ни для какого именно отрезка полностью принадлежащего множеству.

Так как замыслы линейнойоптимизационной модели – это упорядоченные совокупности n чисел ( ), то их возможно разглядывать как точки n?мерного пространства. Они образуют выпуклое множество, т. е. честна теорема:

Теорема.Множество замыслов линейнойоптимизационной модели есть выпуклым.

Подтверждение (для канонической линейнойоптимизационной модели). Линейнуюоптимизационную модель возможно записать и в матричном виде:

где .

Пускай и – замыслы канонической линейнойоптимизационной модели. Следовательно, они удовлетворяют совокупности ограничений: и . Продемонстрируем, что линейная выпуклая комбинация замыслов и

кроме этого есть замыслом данной задачи. Вправду, подставив в совокупность ограничений, последовательно преобразовывая, возьмём верное равенство:

что и требовалось доказать.

Введением дополнительного неравенства:

(большое)

задачу с неограниченной областью замыслов формально возможно преобразовать в задачу с ограниченной областью.

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

Так, линейнуюоптимизационную модель на геометрическом языке возможно сформулировать следующим образом: отыскать точку многогранника замыслов, определяемого совокупностью ограничений (2.2) – (2.5), через которую проходит гиперплоскость семейства (2.1), соответствующая громаднейшему (мельчайшему) значению функции .

Пускай , тогда линейнаяоптимизационная модель на геометрическом языке формулируется следующим образом: отыскать точку многоугольника (многоугольной области) замыслов, определяемого совокупностью ограничений:

(1.13)

,

через которую проходит прямая семейства

, (1.14)

соответствующая громаднейшему (мельчайшему) значению функции .

Прямые именуются линиями уровня. Применяя данную геометрическую интерпретацию, линейнуюоптимизационную модель (1.13)- (1.14) возможно решить графически. Для этого:

1) необходимо выстроить многоугольник (многоугольную область) замыслов, т. е. множество допустимых ответов ? с учетом совокупности ограничений (1.13);

2) выстроить вектор и одну из прямых семейства , к примеру ;

3) параллельным перемещением прямой в направлении вектора отыскать точку, в которой достигает максимума (минимума);

4) решая совместно уравнения прямых, пересекающихся в точке оптимума, отыскать ее координаты, а после этого .

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

1) функция может быть около минимума в одной точке, а максимума – в любой точке отрезка;

2) максимум может достигаться в одной точке, минимума не имеет ( ) либо минимум может достигаться в любой точке отрезка;

3) функция не имеет ни максимума ( + ), ни минимума ( ).

Так, оптимальный замысел возможно единственным; оптимальных замыслов возможно нескончаемое множество; целевая функция возможно не ограничена; задача не имеет решения (см. рис. 1.1).

Рис. 1.1.

Урок 1. Ответ задачи линейного программирования в Excel посредством надстройки \


Также читать:

Понравилась статья? Поделиться с друзьями: