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

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

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

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).В  связи с этим симплекс-метод и  называют методом последовательного  улучшения плана. Поиск начального опорного плана составляет первый этап  симплекс-метода. На втором этапе среди  опорных планов отыскивается оптимальный.