Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения.

Задача линейной оптимизации характеризуется тем, что целевая функция L( Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru ) и ограничения в виде равенств и/или неравенств Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru ( Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru = (x1,…,xn) – вектор переменных) – линейные. При этом в своей исходной постановке задача линейной оптимизации может характеризоваться тем, что требуется отыскать либо минимум, либо максимум целевой функции, а в качестве ограничений могут выступать линейные равенства и неравенства одновременно.

Hайти такие неотрицательные значения переменных x1, x2, …,xn, которые удовлетворяют ограничениям

a11x1 + a12x2 + … + a1jxj +… + a1nxn = b1;

a21x1 + a22x2 + … + a2jxj + … + a2nxn = b2;

…………………………………………

aj1x1 + aj2x2 + … + aijxj + … + ainxn = bi;

…. ……………………………………. (1)

am1x1 + am2x2 + … + amjxj + … + amnxn = bm

и обращают в минимум целевую функцию

L( Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru ) = c1x1 + c2x2 + … + cjxj + … + cnxn. (2)

При этом коэффициенты aijв системе ограничений и коэффициенты cjцелевой функции могут принимать как положительные, так и отрицательные значения.

В такой постановке задача линейной оптимизации называется основной задачей линейного программирования (ОЗЛП).

Совокупность неотрицательных значений переменных x1, x2, …, xn, удовлетворяющих ограничениям (2), называется допустимым решением ОЗЛП, а совокупность всех допустимых решений представляет собой подмножество допустимых решений ОЗЛП. Допустимое решение ОЗЛП в виде совокупности значений Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru переменных, обеспечивающих минимальное значение целевой функции L( Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru ), называется оптимальным решением ОЗЛП.

Переход от задачи линейного программирования (ЗЛП) с ограничениями-неравенствами к канонической и стандартной формам представления ЗЛП.

– Если в исходной постановке задачи оптимизации присутствуют ограничения-неравенства, то переход от ограничений-неравенств к ограничениям-уравнениям можно осуществить по следующим правилам.

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

ai1x1 + ai2x2 + … + aijxj +… + ainxn ≤ bi,

то к его левой части необходимо прибавить неотрицательную величину xn+i. В таком случае данное неравенство преобразуется в уравнение

ai1x1 + ai2x2 + … + aijxj +… + ainxn + xn+i= bi.

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

ai1x1 + ai2x2 + … + aijxj +… + ainxn ≥ bi,

то из его левой части необходимо вычесть неотрицательную величину xn+i . В таком случае данное неравенство преобразуется в уравнение

ai1x1 + ai2x2 + … + aijxj +… + ainxn – xn+i=bi.

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

Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru ;

Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru ;

............................................................................

Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru ; Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru (3)

……………………………………………… Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru ,

где коэффициенты Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru являются комбинациями коэффициентов aijиbi.

Целевая функция вида (2) также выражается через свободные переменные и в результате принимает вид

Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru , (4)

где коэффициенты Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru являются комбинациями коэффициентов cj.

Затем система уравнений (3) и выражение для целевой функции (4) преобразуются к виду

Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru ;

…………………………………………………

Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru ; (5)

…………………………………………………

Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru ,

Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru , (6)

где Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru ; Постановка задачи линейного программирования. Основная задача линейного программирования (ЗЛП) и условия наличия у неё допустимого решения. - student2.ru .

Наши рекомендации