|     Карта сайта     |  
   Бизнес право
   Ведение бизнеса
   Маркетинг
   Менеджмент
   Операции
   Статистика
   Стратегия
   Учет и аудит
   Финансы
   Экономика
   
   Карьера
   Мои МВА проекты
   Тестирование
   Форум
   Контакт
   
 
Поиск на сайте
Поиск на Куличках

 
 
 

online dating
HotLog

Rambler's Top100

Операции
Управление Поставками      Управление Запасами       Качество и Продуктивность    Линейное Программирование      Электронная Коммерция        6 Сигм       Бизнес Процессы

Линейное программирование - количественный анализ для оптимизации целевой функции, при данном ряде ограничений. Название подразумевает, что функции должны быть линейными.
Проблемы, которые необходимо решить формулирутся в задании. Ниже приведен контрольный список вопросов для минимизации риска ошибок в формулировке задания.
1. Любое число в задании должно быть или использовано, или игнорировано, например неокупаемые капиталовложения.
2. Не забывайте начальных условий, например количество штата в начальном периоде.
3. Каждая переменная в целевой функции должна быть перечислена где-нибудь в ограничениях.
4. Необходимо перечислить любые ограничения.
5. Неоходимо ограничить число знаков в переменных до 0,1.

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

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

С точки зрения математики производственную программу предприятия в первом приближении можно записать как набор чисел $ x_1, x_2, \dots , x_n $ в котором $ x_i $ обозначает запланированый выпуск изделий $ i$-го типа, $ n$ -- количество типов изделий.

Если $ c_i $ -- доход от произведенного изделия $ i$-го типа и каждое произведенное изделие покупается по одной и той же цене, то суммарный доход предприятия является простой суммой

$\displaystyle P = c_1 x_1 + c_2 x_2 + \dots + c_n x_n = \sum_{j=1}^n c_j x_j ,$ (1)

что отражает присутствие слова ''линейное'' в названии ''линейное программирование''.

Сумма (1) является линейной функцией величин $ x_1, x_2, \dots , x_n $ и, конечно, лишь приближенно отражает экономические реалии. В этом случае при увеличении выпуска всех изделий в тысячу раз, доход предприятия возрос бы также в тысячу раз. В реальной экономике при значительном росте производства начинают сказыватся такие факторы как насыщение рынка, увеличение конкуренции, рост производственных издержек и пр., что, конечно, понижает доходность и не отражается в такой простой формуле, как (1). Рост масштабов производства может не только понижать доходность, но и повышать ее -- при переходе от кустарного или мелкосерийного производства к крупносерийному издержки, в расчете на одно изделие, могут уменьшаться и соответственно доходность -- повышаться.

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

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

$\displaystyle \max P = \max_x \sum_{j=1}^n c_j x_j.$ (2)

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

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

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

Чаще всего это так называемые ресурсные ограничения, описывающие тот факт что

  • для производства товаров приходиться тратить ресурсы;
  • количество ресурсов, которое можно затратить на производство товаров, ограничено.
Если считать, что в нашем производстве используются $ i = 1,2,\dots, m $ ресурсы (труд, различные виды сырья, энергия и т.д. ), то в модели линейного программирования эти два факта описываются с помощью коэффициетнов $ a_{ij} $ , которые задают затраты $ i$-го ресурса на производство единицы $ j $-го продукта.

Если затраты ресурсов линейно возрастают в зависимости от роста обьемов производства, то для выпуска продукта $ j $ в количестве $ x_j $ единиц требуется $ a_{ij} x_j $ единиц $ i$-го ресурса. Выпуск всего плана $ x = ( x_1, x_2, \dots, x_n ) $ потребует при этом

$\displaystyle z_i = a_{i1} x_1 + a_{i2} x_2 + \dots + a_{in} x_n =
\sum_{j=1}^n a_{ij} x_j $

единиц $ i$-го ресурса.

Когда в наличии имеется не более $ b_i $ единиц этого ресурса, то ясно, что любой реализуемый план производства $ x$ должен удовлетворять ограничению

$\displaystyle z_i = \sum_{j=1}^n a_{ij} x_j \leq b_i. $

Учитывая то, то у нас несколько ( $ m$ ) видов рекcурсов и допустимый план должен удовлетворять каждому из таких ограничений, получаем систему линейных неравенств

\begin{displaymath}\begin{array}{cccccccc} a_{11} x_1 &+ &a_{12} x_2 &+ \dots &+...
... &+ &a_{m2} x_2 &+ \dots &+ &a_{mn} x_n &\leq &b_m, \end{array}\end{displaymath} (3)

где $ b_1, b_2, \dots, b_m$ -- запасы соответствующих ресурсов. Эту систему можно записать компакнее, как

$\displaystyle \sum_{j=1}^n a_{ij} x_j \leq b_i, i = 1, 2, \dots, m,
$

чем мы и будем в дальнейшем пользоваться.

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

$\displaystyle \sum_{j=1}^n a_{ij} x_j = b_i, $

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

$\displaystyle \sum_{j=1}^n a_{ij} x_j \geq b_i.$ (4)

Последний тип ограничений может отражать, например, требования заказчика на удовлетворение определенных стандартов. Например, если $ x_j, j = 1, 2, \dots, n $ -- составляющие кормовой смеси для рациона животных на сельскохозяйственной ферме, а $ a_{ij} $ -- пищевая ценность $ j $-го продукта относительно $ i$-го критерия ( например, калорийность ), то условие (4) может означать требование, что суммарная пищевая ценность компонент смеси была не меньше, чем определенный стандарт $ b_i $.

С точки зрения практического экономиста, применение линейного программирования означает, таким образом:

  1. определение структуры задачи -- что в ней является критерием, какие в ней присутствуют ограничения, какими переменными величинами ( $ x_1, x_2, \dots , x_n $) мы можем управлять, в чем заключается желаемый экономический эффект;
  2. сбор необходимой информации -- определение, часто путем статистических исследований, анализа рынка, прогнозов и пр., значений коэффициентов задачи: стоимостных коеффициентов $ c_j, j=1,2,\dots,n $, расходных $ a_{ij}, i=1,2,\dots,m; j=1,2,\dots,n $, обьемов доступных ресурсов $ b_i, i=1,2,\dots,m $;
  3. подготовкой задачи к решению. Поскольку сейчас это делается, как правило, с помощью вычислительных машин, этот шаг в решении задачи представляет собой перенос данных и описания задачи в специальную машинно-читаемую форму. Для этого применяются специальные ( и достаточно сложные ) форматы данных и программные системы;
  4. собственно решение задачи.Для этого существует множество высокоэффективнх программ для самых разнообразных вычислительных платформ, от суперкомпьютеров до персональных ЭВМ и даже калькуляторов. Трудами многих талантливых математиков и программистов алгоритмы и программы доведены до столь высокой степени совершенства, что на этой стадии редко возникают вычислительные проблемы. Значительно чаще на этой стадии выявляются дефекты постановки задачи, ошибки в подготовке данных или описании структуры задачи. Эффект таких ошибок является часто весьма неожиданным и их исправление требует как высокой математической квалификации так и знания конкретной области приложения;
  5. анализ результатов. Это заключительная и, по сути дела, наиболее важная часть процесса. При это надо иметь в виду, что в ходе решения задачи линейного программирования, как правило, определяются не только собственно оптимальный план, но и большой обьем сопутствующей информации, которая весьма ценна для экономического анализа и планирования.

Источник: http://www.dvo.ru/studio/linpro/lp1st/node4.html

 

Образование на Куличках ©2004. Все права сохранены.