Формальная постановка задачи математического программирования (М П)

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

Задача оптимизации состоит в выборе наилучших планов.

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

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

min(max)←Z=f(x_1,…,x_n),

при условиях: g_i(x_1,…,x_n)≤≥bi, i=1,m

Замечание: в случае, когда Z есть множество действительных чисел (используемых на практике), функция Z=f(x_1,…,x_n), называется скалярной. Условия g_i(x_1,…,x_n)≤≥b_i, i=1,m предполагающие, что в каждой из n строк может присутствовать одно из рассмотренных ограничений g_i(x_1,…,x_n)≤≥bi, i=1,m, называются областью определения (U) задачи.

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

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

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

X є U → max(min){Z=f(x)}

Два основных класса задач МП - это задачи линейного и нелинейного программирования. К задачам линейного программирования (ЛП) относятся те, в которых и целевая функция Z, и все функции g_i линейны.

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

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

Линейное программирование. Постановка задачи.

Задача ЛП в общей постановке состоит в отыскании переменных x_1,…,x_{n ,}обращающих в

_n

экстремум функцию: max←Z=Σ С_jX_j при ограничениях:

^j=1

a₁₁ x₁ + a₁₂ x₂ +… + a_1n x_n ≤ b₁

…

a_m1 x₁ + a_m2 x₂ +… + a_mn x_n ≤ b_m

Обычно, кроме того, на практике добавляют требования не отрицательности(" x_j >0_ij =1,n)

Пример постановки задачи: Ферма производит откорм скота. Допустим, что имеется 4 вида продуктов (П1,П2,П3,П4). Стоимость единицы каждого продукта (С1,С2,С3,С4). Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков не менее b1 единиц, углеродов не менее b2 единиц, жиров не менее b3 единиц. Для продуктов (П1,П2,П3,П4) содержание белков, жиров и углеродов в единицах на единицу продукта приведено в таблице.

Где аij некоторые числа и i – продукт j – элемент.

Задача: составить такой пищевой рацион, то есть определить количество продуктов (П1,П2,П3,П4) входящих в рацион, что при минимальной стоимости рациона, при условии выполнения ограничения белков, жиров и углеродов.

Z = C₁x₁ + C₂x₂ + C₃x₃ + C₄x₄ → min здесь мы за x₁ … x₂ обозначили количество продуктов которые должны входить в рацион.

a₁₁ x₁ + a₁₂ x₂ +a₁₃ x₃ + a₁₄ x₄ ≥ b₁

a₁₂ x₁ + a₂₂ x₂ +a₃₂ x₃ + 2₄₂ x₄ ≥ b₂

a₁₃ x₁ + a₂₃ x₂ +a₃₃ x₃ + a₄₃ x₄ ≥ b₃

"x ≥ 0

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