Оптимизационные модели. Метод искусственного базиса (М-метод)

СОДЕРЖАНИЕ

I. Теоритическая часть

1.1. История развития экономико-математического планирования.

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

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

Далее методы планирования продолжали совершенствоваться, но только развитие вычислительной техники в конце 50-х гг. позволило сделать плановые многовариантные расчеты достаточно распространенными. Важную роль в организации и пропаганде экономико-математических исследований в этот период сыграл академик В. С. Немчинов. Именно в эти годы получают развитие некоторые разделы прикладной математики, связанные с решением оптимизационных задач: линейное и нелинейное программирование, теория оптимального управления и др.

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

1.2. Классификация математических моделей

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

• дескриптивные  (описательные)  модели;
• оптимизационные модели;
• многокритериальные модели;
• игровые модели.

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

1.3. Оптимизационные экономико-математические модели

1.3.1. Понятие оптимизационных задач и оптимизационных моделей.

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

Оптимизационные задачи (ОЗ) решаются с помощью оптимизационных  моделей (ОМ) методами математического  программирования.

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

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

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

а) линейные (I и II) и нелинейные (III и IV) (рис.1);

Рис. 1. Линейные и нелинейные ограничения б)  детерминированные (А,В) и  стохастические (группы кривых) (рис. 2).

Рис. 2. Детерминированные  и стохастические ограничения

Стохастические  ограничения являются возможными, вероятностными, случайными.

Оптимизационные задачи решаются методами математического  программирования, которые подразделяются на:

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

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

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

1.3.2. Экономические основы оптимизаци.

Оптимизационные (экстремальные) модели в экономике  возникают при практической реализации принципа оптимальности в управлении.

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

Суть  принципа оптимальности состоит  в стремлении выбрать такое управленческое решение Х = (х₁, х₂, …, х_n), где х_j, j = 1, ..., n, - его компоненты, которое наилучшим образом учитывало бы внутренние возможности и внешние условия производственной деятельности хозяйствующего субъекта.

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

«Учитывало  бы внутренние возможности и внешние  условия производственной деятельности»  означает, что на выбор управленческого  решения (поведения) накладывается  ряд условий, т.е. выбор X осуществляется из некоторой области возможных (допустимых) решений D.

Таким образом, реализовать на практике принцип  оптимальности в планировании и  управлении — это значит решить экстремальную задачу вида:

max (min) f(X) (1.1)

X ∈ D (1.2)

где f(X) - математическая запись критерия оптимальности - целевая функция.

Задачу  условной оптимизации (1.1), (1.2) обычно записывают в виде:

найти максимум или минимум функции

f(X) = f(х₁, х₂, … х_n) (1.3)

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

(1.4)

x_j ≥ 0, j = 1, 2, ..., n. (1.5)

Условие (1.5) необязательно, но его всегда можно  добиться. Обозначение {≤, =, ≥} говорит  о том, что в конкретном ограничении  возможен один из знаков <, = или >. Более компактная запись выглядит следующим образом:

max (min) f(х₁, х₂, … х_n) (1.6)

g_i(x₁, x₂, …, х_n) {≤, =, ≥} b_i, i = 1, 2, ..., m (1.7)

x_j ≥ 0, j = 1, 2, ..., n. (1.8)

Задача (1.6)—(1.8) — общая задача оптимального (математического) программирования, другими  словами, математическая модель задачи оптимального программирования в основе построения (разработки) которой лежат  принципы оптимальности, системности  и адекватности.

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

Вектор X (набор управляющих переменных х_j, j = 1, 2, ..., n) называется допустимым решением или планом задачи оптимального программирования, если он удовлетворяет системе ограничений (1.7)-(1.8). А тот план X (допустимое решение), который доставляет максимум или минимум целевой функции f(х₁, х₂, …, х_n) называется оптимальным планом (оптимальным поведением или просто решением) задачи оптимального программирования.

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

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

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

Второй  случай обычно означает, что ЭММ  разработана некорректно и некоторые  существенные ограничения в ней  отсутствуют.

1.3.3. Классификация задач оптимального  планирования.

1. По  характеру взаимосвязи между  переменными —

а) линейные,

б) нелинейные.

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

2. По  характеру изменения переменных  —

а) непрерывные,

б) дискретные.

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

3. По  учету фактора времени —

а) статические,

б) динамические.

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

4. По  наличию информации о переменных  —

а) задачи в условиях полной определенности (детерминированные),

б) задачи в условиях неполной информации (случай риска),

в) задачи в условиях неопределенности.

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

5. По  числу критериев оценки альтернатив  —

а) простые (однокритериальные),

б) сложные (многокритериальные) задачи.

Задачи  а) — задачи, где экономически приемлемо  использование одного критерия оптимальности  или удается специальными процедурами (например «взвешиванием приоритетов») свести многокритериальный поиск к  однокритериальному; б) многокритериальная оптимизация — выбор управленческого  решения по нескольким показателям.

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

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

(суммирование k = 1, 2, ..., s),

где f_k - k-я целевая функция;

f_{k норм} - нормирующее значение k-й целевой функции;

α_k — коэффициент веса k-й целевой функции;

s — число критериев (целевых функций).

При этом перед составляющими целевой  функции, которые максимизируются, ставится знак плюс, перед минимизируемыми - минус. Значения f_{k норм} принимаются при максимизации k-й составляющей целевой функции: f_{k норм} = f_k max при ее минимизации — f_{k норм} = f_kmin.

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

Σa_ij = 1, i = 1, 2, ..., n,

где n — число экспертов.

В качестве коэффициента веса k-й целевой функции a_k можно взять среднее значение a_ik по всем экспертам.

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

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

- 1а2а3а4а5а  — задачи и методы линейного  программирования;

- 1б2а3а4а5а  - задачи и методы нелинейного  программирования;

- 1а2б3а4а5а  - задачи и методы целочисленного  программирования и т.д.

Рассмотрим  пример постановки и разработки оптимизационной  ЭММ.

2. Симплекс – метод.

2.1. Идея симплекс метода.

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

Если  задача линейного программирования записана в каноническом виде:

f=∑ c_i  x_j  (max),                                         (2.1)

∑ a_ij x_j = a_i0  (i=1,…,m)                             (2.2)

x_j >0   (j= 1,…,n)                                       (2.3)

Тогда, если оптимальный план задачи   (2.1)-(2.3)  существует, то он совпадает по крайней  мере с одним из опорных решений  системы (2.2). Это опорное решение  отыскивается симплекс-методом в  процессе упорядоченного перебора только опорных решений системы (2.2).В  связи с этим симплекс-метод и  называют методом последовательного  улучшения плана. Поиск начального опорного плана составляет первый этап  симплекс-метода. На втором этапе среди  опорных планов отыскивается оптимальный.