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

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

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

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

Простейшая задача МЛП – нахождение максимума (или минимума ) линейной функции доходности (затрат)

Z(X) = с₁ Х₁ + с₂ Х₂ + с₃ Х₃ + … +с_n Х_n

 

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

a₁₁ X₁ + a₁₂ X₂ +…a_1n X _n ≤ b_1, ( или = b_1, ≥ b₁)

a₂₁ X₁ + a₂₂ X₂ +…a_2n X _n ≤ b_2, (или = b_2, ≥ b₂) …………………………………………………..

a_m1 X₁ + a_m2 X₂ +…a _mn X _n ≤ b _m, (или = b _m, ≥ b _m)

 

X₁≥ 0 X₂≥ 0 X₃≥ 0 …X _n ≥ 0

 

Совокупность чисел (вектор) Х= (Х₁, Х₂, Х_3… Х_n), удовлетворяющих задаче с ограничениями (2) называется допустимым решением или планом.

План Х= (Х₁^*, Х₂^*, Х₃^*_… Х_n^*), при котором целевая функция Z(X) принимает максимальное или минимальное значение, называется оптимальным.

В случае, когда требуется найти минимум Z(X) = с₁Х₁ + с₂Х₂ + с₃Х₃ + … +с_nХ_n можно перейти к нахождению максимума Z₁(X) = - с₁Х₁ - с₂Х₂ - …- с_nХ_n, так как

min Z(X) = - max Z₁(X).

 

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

Наилучшие в определенном смысле решения задач принято называть оптимальными. Без использования принципов оптимизации в настоящее время не решается ни одна более или менее сложная проблема.

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

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

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

необходимо определить значения вектора переменных x = (x₁, x₂, …, x_n), которые удовлетворяют ограничениям вида

g_i (x₁, x₂, …, x_n)b_i, для всех i = 1, …, m

 

и доставляют максимум или минимум целевой функции

f (x₁, x₂, …, x_n) → max (min).

Решением ( планом, вектором управления ) задачи МП называется всякий вектор х из пространства E_n (E_n - n-мерное векторное пространство), в геометрической интерпретации – это точка векторного n-мерного пространства.

Допустимым решением ( планом ) задачи МП называется такое решение задачи, которое удовлетворяет ее ограничениям g_i (x₁, x₂, …, x_n)b_i, для всех i = 1, …, m.

Совокупность допустимых решений задачи называют областью допустимых решений (ОДР) задачи МП, которую, как правило, обозначают как D.

Оптимальным решением х* называется такое допустимое решение, при котором целевая функция достигает своего оптимального (в нашем случае — максимального) значения, т. е. решение, удовлетворяющее условию maxf(x) = f(x*). Величина f* = f(x*) называется оптимальным значением целевой функции.

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

Если хотя бы одна из функций g_i (x₁, x₂, …, x_n) или f (x₁, x₂, …, x_n) нелинейная, то такая задача МП называется задачей нелинейного программирования.

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

1. глобальный или локальный;

2. натуральный или стоимостной;

3. максимизирующий или минимизирующий.

В общем виде задача линейного программирования (ЗЛП) может быть сформулирована как задача нахождения вектора x = (x₁, x₂, …, x_n) ϵ E_n такого, что функция линейного вида z(x) = c₁x₁ + c₂x₂ + c₃x₃ + … + c_nx_n → max(или min), т. е. достигает своего максимального или минимального значения, при этом вектор x = (x₁, x₂, …, x_n) должен удовлетворять системе линейных неравенств:

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

Функцию z в задаче является целевой функцией (ЦФ) задачи.

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

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

Линейные неравенства в модели ЛП вида:

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

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

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

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

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

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

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

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

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

 

 

Лекция № 8

Тема: Графический способ определения оптимального плана

План:

1. Графическое решение задач с двумя неизвестными, заданных линейными неравенствами ограничений.

2. Построение выпуклого многоугольника возможных решений и определение оптимального плана с помощью градиента функции цели.

 

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: