Модели линейного программирования в управленческом учете реферат

Обновлено: 07.07.2024

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

Линейное программирование: постановка задач и графическое решение

Общая задача линейного программирования.

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

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

Примеры задач, решаемых графическим методом.

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

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

Действительно, путь необходимо исследовать на экстремум линейную функцию Z = С₁х₁+С₂х₂+. +С_Nx_N

при линейных ограничениях

Так как Z - линейная функция, то = С_j (j = 1, 2, . n), то все коэффициенты линейной функции не могут быть равны нулю, следовательно, внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть на границе области, но исследовать точки границы невозможно, поскольку частные производные являются константами.

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

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

Даны линейная функция

и система линейных ограничений

где а_ij, Ь_j и С_j - заданные постоянные величины.

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

Общая задача имеет несколько форм записи.

Векторная форма записи. Минимизировать линейную функцию Z = СХ при ограничениях

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

Матричная форма записи. Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А₀, Х 0, где С = (с₁, с₂, . с_N) - матрица-cтрока; А = (а_ij) - матрица системы;

Х - матрица-столбец, А₀ - матрица-столбец

Запись с помощью знаков суммирования. Минимизировать линейную функцию Z = С_jх_j при ограничениях

0пределение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х₁, х₂, . х_N), удовлетворяющий условиям (1.2) и (1.3).

0пределение 2. План Х = (х₁, х₂, . х_N) называется опорным, если векторы А (i = 1, 2, . N), входящие в разложение (1.4) с положительными коэффициентами х , являются линейно независимыми.

Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М.

0пределение 3. Опорный план называется невырожденным, если он содержит М положительных компонент, в противном случае опорный план называется вырожденным.

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

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

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

Рассмотрим задачу линейного программирования, система ограничений которой задана в виде неравенств.

Найти минимальное значение линейной функции

Совокупность чисел х₁, х₂, . х_N, удовлетворяющих ограничениям (1.6) и (1.7), называется решением. Если система неравенств (1.6) при условии (1.7) имеет хотя бы одно решение, она называется совместной, в противном случае - несовместной.

Рассмотрим на плоскости х₁Ох₂ совместную систему линейных неравенств

Это все равно, что в системе (1.6) - (1.7) положить N=2. Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой

a_i1x₁ + a_i2x₂ = b_i ,(i = 1, 2, . m). Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми х = 0, х = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы (рис. 1.1).

Совокупность этих точек (решений) назовем многоугольником решений. Он может быть точкой, отрезком, лучом, много-угольником, неограничен-ной многоугольной облас-тью.

Если в системе ограничений (1.6) - (1.7) n = 3, то каждое нера-венство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого a_i₁x₁ + a_i₂x₂ + a_i₃x₃ = b_i ,(i = 1, 2, . n), а условия неотрицательности – полупрост-ранства с граничными плоскостями соответственно х_j = 0 (j = 1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Многогранник решений может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью. Пусть в системе ограничений (1.6) - (1.7) n 3; тогда каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью a_i₁x₁ + a_i₂x₂ + a_iNx_N = b_i (i = 1, 2, . m), а условия неотрицательности – полупространства с граничными гиперплоскостями х_j 0 (j = 1, 2, . n).

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

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

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

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

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

Найти минимальное значение функции

Допустим, что система (2.2) при условии (2.3) совместна и ее многоугольник решений ограничен. Каждое из неравенств (2.2) и (2.3), как отмечалось выше, определяет полуплоскость с граничными прямыми: a_i₁x₁ + a_i₂x₂ + a_i₃x₃ = b_i,(i = 1, 2, . n), х₁=0, х₂=0. Линейная функция (2.1) при фиксированных значениях Z является уравнением прямой линии: С₁х₁ + С₂х₂ = const. Построим многоугольник решений системы ограничений (2.2) и график линейной функции (2.1) при Z = 0 (рис. 2.1). Тогда поставленной задаче линейного прграммирования можно дать следующую интерпретацию. Найти точку многоугольника решений, в которой прямая С₁х₁ + С₂х₂ = const опорная и функция Z при этом достигает минимума.

Значения Z = С₁х₁ + С₂х₂ возрастают в направлении вектора N =(С₁, С₂), поэтому прямую Z = 0 передвигаем параллельно самой себе в направлении вектора Х. Из рис. 2.1 следует, что прямая дважды становится опорной по отношению к многоугольнику решений (в точках А и С), причем минимальное значение принимает в точке А. Координаты точки А (х₁, х₂) находим, решая систему уравнений прямых АВ и АЕ.

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

Случай 1. Прямая С₁х₁ + С₂х₂ = const, передвигаясь в направлении вектора N или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу (рис. 2.2).

Случай 2. Прямая, пере-двигаясь, все же становится опорной относительно многоу-гольника решений (рис. 2.2, а – 2.2, в). Тогда в зави-симости от вида области ли-нейная функция может быть ограниченной сверху и неограниченной снизу (рис. 2.2, а), ограниченной снизу и неограниченной сверху (рис. 2.2, б), либо ограниченной как снизу, так и сверху (рис. 2.2, в).

2.1. Примеры задач, решаемых графическим методом.

Решим графическим методом задачи использования сырья и составления рациона.

Задача использования сырья. Для изготовления двух видов продукции Р₁ и Р₂ используют три вида сырья: S₁, S₂, S₃. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукци, а так же величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2.1.

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

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

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

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

Основные этапы процесса моделирования.

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

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

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

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

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

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

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

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

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

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

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

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

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

6. Анализ численных результатов и их применение. На этом заключительном этапе цикла встает вопрос о правильности и полноте результатов моделирования, о степени практической применимости последних.

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

Особенности исследования операций.

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

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

3. Одной из существенных особенностей исследования операций является стремление найти оптимальное решение поставленной задачи. Однако часто такое решение оказывается недостижимым из-за ограничений, накладываемых имеющимися в наличии ресурсами или уровнем современной науки. Например, для комбинаторных задач, в частности задач календарного планирования при числе станков белее 4 оптимальное решение при современном уровне развития математики оказывается возможным найти лишь простым перебором вариантов. Однако даже при небольших n число возможных вариантов оказывается настолько велико, что перебор всех вариантов при существующих ограничениях на быстродействие ЭВМ и допустимое машинное время практически немыслимы,
тогда приходится ограничиваться поиском достаточно хорошего или субоптимального решения.

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

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

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

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

1. Детерминированый модель(линейная модель, нелинейная модель, динамическая модель, графическая модель);

2. Стохастический модель;

3. Неопределенный модель (теория игр, имитационные модели).

В стохастических моделях неизвестные факторы - это случайные величины, для которых известны функции распределения и различные статистические характеристики (математическое ожидание, дисперсия, среднеквадратическое отклонение и т.п.). Среди стохастических характеристик можно выделить:

*модели стохастического программирования, в которых либо в целевую функцию, либо в ограничения входят случайные величины;

*модели теории случайных процессов, предназначенные для изучения процессов, состояние которых в каждый момент времени является случайной величиной;

*модели теории массового обслуживания, в которой изучаются многоканальные системы, занятые обслуживанием требований.

Также к стохастическим моделям можно отнести модели теории полезности, поиска и принятия решений.

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

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

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

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

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

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

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

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

1. Графический метод;

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

4. Метод больших штрафов;

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

Метод Гомори. Сущность метода состоит в том, что сначала задача решается без условия целочисленности. Если полученный план целочисленный, задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами:

- оно должно быть линейным;

- должно отсекать найденный оптимальный нецелочисленный план;

- не должно отсекать ни одного целочисленного плана.

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

Далее задача решается с учетом нового ограничения. После этого в случае необходимости добавляется еще одно ограничение и т. д.

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

1. ПОСТАНОВКА ЗАДАЧИ ОПЕРАЦИОННОГО ИССЛЕДОВАНИЯ

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

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

2. Управленческие задачи, решаемые с помощью модели линейного программирования

2.1. Задача о планировании производственной программы предприятия

Предприятие может выпускать n видов продукции Р₁, Р₂, . Р_n, располагая для этого т различными ресурсами R₁, R₂, . R_m в количествах b₁ b₂. b_m соответственно. Известно, что для выпуска единицы продукции P_j необходимо затратить a_ij единиц ресурса R₁, i = 1, 2, . m;j = 1, 2. n. Кроме того, известен доход с₁, с₂. с_n от продажи единицы каждого вида продукции, где с_j, j = 1, 2, . n, - стоимость единицы продукта P_j, например 1 шт., 1 т и т.д.

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

Для удобства дальнейших выводов и рассуждений сведем исходную информацию в единую табл. 1, где через x_j обозначены объемы продукции P_j, выпускаемой предприятием. Тогда набор переменных 1,x₂. х_n> представляет собой не что иное, как производственную программу предприятия.

Исходная информация задачи

Доход, полученный предприятием при производстве продукта P_j в количестве х_j, составит c_jx_j, а при реализации производственной программы 1, x₂. x_j> будет равен величине

Подсчитаем, какое количество ресурсов будет израсходовано, если выбрать некоторый план 1, x₂. x_j>.

Ресурса R₁ потребуется а₁₁х₁ + а₁₂х₂ +. + а_1nх_n, в то время как в наличии имеется запас b₁.

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

Кроме того, понятно, что переменные решения x₁,x₂, . х_n, должны удовлетворять условию неотрицательности:

Объединяя полученные результаты, получаем следующую модель линейного программирования.

Требуется найти совокупность значений 1,х₂. х_п>, обращающих в максимум целевую функцию:

при условии, что переменные 2,х₂. х_n> удовлетворяют системе ограничений:

Химическая фабрика выпускает три разновидности стирального порошка марок А, В, С. Доход от реализации 1 кг порошка каждого наименования известен, и составляет с_A = 10, с_в = 12, с_с= 8 руб. соответственно. Недельные запасы и удельные расходы ресурсов, необходимых для производства 1 кг порошка каждой марки, приведены в табл. 2.

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

Обозначим через х_А,х_в,х_с недельные объемы выпуска стиральных порошков марок А, В, С (кг). Тогда доход от реализации порошков при производственной программе д,х_в,х_с> составит:

Подсчитаем расходы ресурсов, необходимые для выполнения производственной программы A,х_в,х_с>.

Сырья будет израсходовано 1,4х_A + 1,2х_в + 1,5х_с кг при запасе, равном 15 000 кг. Следовательно, для того, чтобы программу можно было реализовать, необходимо, чтобы выполнялось ограничение:

Кроме того, переменные х_А,х_в,х_с не могут принимать отрицательных значений:

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

Необходимо сформировать такую производственную программу A,х_в,х_с> (определить объемы выпуска продукции каждой марки), при которой целевая функция (доход от реализации) будет максимальной:

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

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

2.2. Задача об оптимальной корзине продуктов (задача о диете)

Медициной установлена суточная потребность организма в питательных веществах T₁,T₂, . Т_m (белки, жиры, углеводы и т.д.): человеку они необходимы в количествах не менее чем b₁, b₂, . b_m некоторых условных единиц (например, миллиграмм). В продаже имеются продукты питания П₁, П₂, . П_n, стоимость которых известна и равна c₁,с₂. с_n (где c_j -стоимость единицы продукта П_j, например 1 кг, 1 л, 1 уп. и т.д.). Известно также, что питательное вещество T_i содержится в единице продукта П_j в количестве а_ij единиц, i = 1,2, . m; j = 1,2. n.

Требуется составить продуктовую корзину с минимальной стоимостью, т.е. определить количество продуктов каждого вида 1, х₂. х_n>, которые следует приобрести для того, чтобы, с одной стороны, удовлетворить суточную потребность организма в питательных веществах, а с другой - израсходовать при этом минимум средств. Исходная информация, необходимая для формулировки задачи приведена в табл. 3.

Исходная информация для задачи

Обозначим стоимость искомой корзины через Z. Тогда для некоторого продуктового набора 2. x>

Подсчитаем количество каждого питательного вещества Т_i, i = 1,2, . m, содержащегося в корзине 2. x>.

Содержание вещества T_l в корзине a₁₁x₁ + a_l2x₂ +. + a_lnx_n, в то время как его должно быть не менее b₁

Содержание вещества Т₂ в корзине а₂₁х₁ +a₂₂x₂+. + a_2nx_n, в то время как его должно быть не менее b₂.

Содержание вещества Т_m в корзине a_mlx₁ + a_m2x₂ + . + a_mnx_n, в то время как его должно быть не менее b_m.

Кроме того, переменные решения 1,х₂. х_n> не могут быть отрицательными числами:

В результате приходим к следующей оптимизационной задаче. Необходимо найти такой набор значений для переменных 2. х_n>, которые обращают в минимум целевую функцию

и одновременно удовлетворяют следующей системе ограничений:

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

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

Обозначим через х₁,х₂,х₃,х₄ количество приобретаемых продуктов каждого вида (в кг). Тогда стоимость продуктового набора будет равна:

Содержание А в продуктовом наборе составит х₁ + 0х₂ + 2х_э + + 5х₄. Причем, согласно требованиям, его количество должно быть не менее 50. Тогда получаем первое ограничивающее условие - набор продуктов х₁,х₂,х₃,х₄ должен быть таким, чтобы обеспечить количество А не менее чем 50 условных единиц:

Рассуждая аналогично, получим ограничивающие условия по другим компонентам:

3х₁ + 5х₂ + 0х₃ + 4х₄ > 60 - ограничение по удовлетворению потребности в B;

4х₂ + 7х₃ + 0х₄ > 40 - ограничение по удовлетворению потребности в С.

Кроме того, переменные х₁,х₂,х₃,х₄ не могут быть отрицательными числами. Следовательно,

Объединяя полученные результаты, получаем следующую оптимизационную задачу.

Необходимо найти такой набор значений переменных х₁, х₂, х₃, х₄ (количества продуктов каждого вида), который обращает целевую функцию (стоимость продуктового набора) в минимум:

и при этом удовлетворяет системе ограничений:

Так как и целевая функция, и ограничения линейны, то это задача линейного программирования.

2.3. Формы записи задач линейного программирования

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

Теоретическая часть, в которой кратко рассмотрены основные вопросы теории.
Практическая часть, в которой рассмотрен 1 пример линейного программирования графическим способом.
НГТУ, 4 курс
Основой для решения экономических задач являются математические модели.
Линейное программирование - один из важнейших разделов математики, изучающий теории и методы решения определенных задач. Эта математическая дисциплина стала в последние годы широко применяться в различных областях экономики, техники и военного дела, где в их развитии не последнюю роль играет математическое планирование и использование автоматических цифровых вычислительных машин. Данный раздел науки изучает линейные оптимизационные модели. Иначе говоря, линейное программирование посвящено численному анализу и решению задач, требующих нахождения оптимального значения, т. е. максимума или минимума, некоторой системы показателей в процессе, а состояние его описывает система линейных неравенств.
Начало широкого использования линейных зависимостей для описания экономических явлений, многие из которых вовсе не обладают свойством линейности, было в середине ХХ в. подлинной научной революцией. Ее даже так и называли — линейная революция в экономике. Она дала мощный толчок развитию экономико-математических методов, способствовала всестороннему формированию практически применимого математического аппарата для исследования разнообразных областей экономики. Надо, однако, учитывать, что многие экономические процессы в действительности носят нелинейный и стохастический характер и их аппроксимация линейными зависимостями (линеаризация), упрощая расчеты, существенно огрубляет и искажает их. Поэтому линейные модели страдают известной ограниченностью в том, что касается отображения с их помощью реальных экономических процессов. Но во многих случаях созданный на этой основе математический аппарат в сочетании с компьютерной техникой, производящей сложные и трудоемкие расчеты, позволяет с успехом использовать такие модели в хозяйственной практике и в экономической науке.
Цель данной работы – рассмотреть модели линейного программирования - математические модели решения экономических задач, представленные в форме задач линейного программирования

Алесинская Т.В., Сербин В.Д., Катаев А.В. Учебно-методическое пособие по курсу Экономико-математические методы и модели. Линейное программирование

формат doc
размер 1.94 МБ
добавлен 24 октября 2011 г.

Таганрогский государственный радиотехнический университет, 2001, 84с. В учебно-методическом пособии рассмотрены вопросы построения математических моделей основных типов задач линейного программирования и способы их решения средствами табличного редактора Microsoft Excel, приведены примеры решения или рекомендации к решению конкретных задач. Предлагаемое учебно-методическое пособие рекомендуется для использования в курсе "Экономико-математические.

Березкин О.И., Кулагина А.Г. Математическое программирование

формат djvu
размер 6.98 МБ
добавлен 02 июля 2011 г.

Текст лекций для студентов экономических специальностей. Чебоксары. Изд.-во Чуваш. ун.-та, 2000. 164 c. Предмет математического программирования. Целевая функция ограничения. Основная постановка задачи. Классические методы решения задачи математического программирования и их возможности. Численные методы. Сплошное зондирование поверхности отклика. Равномерно-упорядоченное зондирование. Стохастическое зондирование (методы случайного поиска) Аддити.

Буторин. Математическая экономика

формат doc
размер 1.2 МБ
добавлен 17 апреля 2007 г.

Моделирование экономических процессов, математические модели. Математическая теория динамики развивающихся систем. Основные понятия. Классические методы описания динамических систем. Динамические модели в экономике. О классификации моделей. Некоторые примеры модели. Математическое моделирование. Зачем нужны модели? Примеры математических моделей. Математические модели и экономика. Линейная алгебра в экономике. Какие бывают задачи линейного прогр.

Мамаева З.М. Экономико-математические методы и модели

формат pdf
размер 808.68 КБ
добавлен 02 сентября 2011 г.

Математические методы исследования операций в экономике. Тест с ответами. 2011 г

формат doc
размер 2.92 МБ
добавлен 28 июня 2011 г.

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

Методическое пособие - Экономико-математические методы и модели

формат doc
размер 315 КБ
добавлен 16 марта 2011 г.

В.: ВолГТУ, экономический факультет, 2012 г. Содержание: Транспортная задача, по существу, представляет собой задачу линейного программирования, которую можно решать симплекс – методом. Однако специфическая структура условий задачи позволяет разработать более эффективный вычислительный метод. Определение транспортной модели и ее математическая постановка Решение транспортной задачи

Орлова И.В. Краткий конспект лекций и лабораторная работа № 1 по курсу Экономико-математические методы и прикладные модели

формат doc
размер 640.57 КБ
добавлен 12 ноября 2010 г.

Решение систем линейных уравнений методом Жордана - Гаусса. Общая задача оптимизации. Графический метод решения задач линейного программирования. Симплексный метод решения задачи линейного программирования. Технология решения задач линейного программирования с помощью Поиска решений в среде EXCEL. Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений. Задания к контрольной работе.

Пазюк К.Т. Практикум по курсу Математические методы и модели в экономике

формат doc
размер 1.51 МБ
добавлен 25 декабря 2011 г.

Учебное пособие. - Хабаровск: Издательство ХГТУ, 2003. - 100с. Введение Линейное программирование Теоретические основы моделирования. Составление математической модели Графический метод задач линейного программирования (ЛП) Симплекс-метод решения задач линейного программирования (ЛП) Транспортная задача (ТЗ) Универсальная транспортная задача Теория игр, нелинейное и динамическое программирование Задачи теории игр Нелинейное программирование (НП).

Полежаев В.Д. и др. Методы и модели в экономике

формат doc
размер 538.21 КБ
добавлен 15 июля 2011 г.

Конспект лекций/ В.Д. Полежаев, Л.Н. Полежаева, Е.Н. Казанцева. – Омск: Изд-во ОмГТУ, 2008.– 64 с. Классификация экономико-математических методов и моделей. Линейное программирование. Теоретические основы методов линейного программирования. Геометрический (графический) метод решения задачи линейного программирования. Алгоритм геометрического метода решения задачи линейного программирования. Симплексный метод. Метод искусственного базиса. Двойств.

Поттосина С.А. Экономико-математические модели и методы

формат pdf
размер 819.97 КБ
добавлен 29 апреля 2009 г.

Минск: 2003 г. , - 94 стр. В учебном пособии представлены основные математические модели и методы для решения широкого класса прикладных задач экономического анализа. Теоретический материал сопровождается конкретными числовыми примерами. Для студентов и преподавателей экономических специальностей. Содержание Введение. Основные понятия математического моделирования социально-экономических систем. Линейные балансовые модели. Необходимые сведения.

Читайте также: