2. Постановка та математична модель задачі лінійного програмування (злп). Стандартна форма злп. Форми запису злп.

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

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

Составление математической модели включает: выбор переменных задачи; составление системы; ограничений; выбор целевой функции.

Целевая функция: Z = С₁x₁ + С₂x₂ +… + С_nx_n → mаx (min).

Задана система m линейных ограничений с n переменными:

a₁₁x₁ + a₁₂x₂ +… + a_1nx_n ≤ (≥) b₁,

a₂₁x₁ + a₂₂x₂ +… + a_2nx_n ≤ (≥) b₂,

…………………... ... ... ... ... ... ...,

a_k1x₁ + a_k2x₂ +… + a_knx_n ≤ (≥) b_k,

Где дополнительные ограничения: x1 ≥ 0, x2 ≥ 0,…, xn ≥ 0. Необходимо найти переменные x1, x2,…, xn, которые удовлетворяют системе ограничений и приводят целевую функцию к максимальному или минимальному значению. В общей форме задачи линейного программирования система ограничений включает в себя как равенства, так и неравенства, а целевая функция может стремиться как к максимуму, так и к минимуму.

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

Формы записи ЗЛП:

I. Злп записанное с помощью знака суммирования:

Z = (min).

x_ij ≥0 (j = 1, n)

II. Матричная форма записи злп:

Z=CX (min)

AX = X

X ≥ 0, где С = (С1, С₂,…, С_n)

X = ( x1, x₂,…, x_n) A =

X0 = III. Векторная форма матрицы ЗЛП. Z= (min)

x_{1 1} + x_{2 2} + … + x_{n n} = ₀

≥ 0, где = ( С₁, С₂, …, С_n)

= (x₁, x₂, …, x_n)

₁ = ₂ = … _n = ₀ =

3. Основні означення злп. Властивості множини планів злп. Основна теорема лінійного програмування.

Математическая модель ЗЛП отличается друг от друга вида искомого экстремума и типом соотношений в системе основных ограничений.

Задачей линейного программирования – называется заданной в каноническом виде если ее система основных ограничений представлена в виде уравнений. Приведение ЗЛП к каноническому виду осуществляется с помощью введения неотрицательных дополнительных переменных.

Под «полной системой ограничений» понимается система основных ограничений и дополнительных ограничений.

План ЗЛП – набор значений переменных х1, х2, х3 удовлетворяющий полной системе ограничений.

Решением ЗЛП или оптимальным планом называется план, доставляющий целевой функции заданный вид экстремума.

План ЗЛП называется опорным, если его положительным компонентом соответствует система линейно – независимых векторов.

Теорема:

Для того, чтобы план ЗЛП был опорным, необходимо чтобы число его положительных компонентов не превышало размерность векторного пространства, которая определяется основных ограничений(m).

Доказательство:

В m – мерном пространстве максимальное число линейно независимых векторов равно m. Число положительных компонентов опорного плана не может быть больше m, что и требовалось доказать.

Опорный план ЗЛП называется невыражденым, если вектора соответствуют его положительным компонентам, образуют базис.

Свойства множества планов ЗЛП:

Обозначим К - множество планов ЗЛП. Используя матричную форму записи. Множество планов К можно записать в виде :

Теорема 1:

Множества планов К является выпуклым.

Доказательство:

Рассмотрим 2 лбых плана и составит их линейную комбинацию, где Х = ,

где .

Надо доказать, что 1) Х≥0 , 2) АХ= , отсюда следует что Х К.

Докажем, что Х . Так как , тогда Х = ≥0

Докажем, что АХ= ,

Действительно АХ = А( = = .

Теорема 2:

Множество планов К являются замкнутыми

Теорема 3:

Опорному плану ЗЛП соответствует угловая точка множества К

Теорема 4( обратная Т. 3)

Угловой точке К соответствует опорный план.

Теорема 5:

Число угловых точек множества планов К - конечно. Можно показать, что мах.возможное число опорных планов не превышает сумму: +…+ то есть является конечной, m- число положительных копмпонент, n – размерность пространства