Задача линейного программирования. Проверка оптимальности текущего плана

Глава 1. Линейное программирование (ЛП)

1.1. Задача линейного программирования

1.1.1. Общая задача линейного программирования формулируется следующим образом: найти экстремум целевой функции

Z (Х) = c₁x₁ + c₂x₂ + … + c_nx_n ® max (min),                                   (1)

при ограничениях а_i1х₁ + а_i2х₂ + … + а_inх_n   = b_i ,   i = 1, …, m₁;                                   (2)

а_i1х₁ + а_i2х₂ + … + а_inх_n   ≤ b_i , i = m₁+1, …, m₂;                               (3)

а_i1х₁ + а_i2х₂ + … + а_inх_n   ≥ b_i , i = m₂ +1, …, m;                                (4)

х₁ ³ 0,   х₂ ³ 0,  . . . ,   х_t ³ 0,    t £ n .                                                (5)

1.1.2. Основная задача линейного программирования

Z (Х) = c₁x₁ + c₂x₂ + … + c_nx_n ®  max (min),                                  (6)

при ограничениях а_i1х₁ + а_i2х₂ + … + a_inx_n   = b_i ,   i = 1, …, m;                                    (7)

х₁ ³ 0,   х₂ ³ 0,  . . . ,   х_n ³ 0.                                                           (8)

1.1.3. Правило приведения общей задачи ЛП к основной.

1) Если х_k не подчинено условию неотрицательности, заменяем разностью х_k = х′_k - х′′_k , х′_k ³ 0 , х′′_k ³ 0 .

2) Введем положительную дополнительную переменную в левую часть каждого из неравенств (3) со знаком "+", чтобы превратилось в равенство.

3) Введем положительную дополнительную переменную в левую часть каждого из неравенств (4) со знаком "-" , чтобы превратилось в равенство.

4) В целевую функцию дополнительные положительные переменные вводятся с коэффициентом, равным нулю.

Пример 1. Привести к основному виду задачу ЛП Z(Х) = 3x₁ + x₂ + x₃ → max (min),

x₁ + 2x₂ + x₃ = 7,

x₁ -  x₂ + 2x₃ ≤ 1,

2x₁ + x₂ + 2x₃ ≥ 5,      

x₂ ≥ 0,   x₃ ≥ 0.

Решение. 1) х₁ не подчинено условию неотрицательности, заменяем разностью х₁ = х₁′ - х₁′′, х₁′  ≥ 0,   х₁′′  ≥ 0.

2) Введем х₄ ≥ 0 в левую часть неравенства х₁ – х₂ + 2х₃ ≤ 1 со знаком «+», чтобы превратилось в равенство х₁ – х₂ + 2х₃ + х₄ =1, где  х₄ = 1 – х₁ + х₂ – 2х₃.

3) Введем х₅ ≥ 0 в левую часть неравенства 2x₁ + x₂ + 2x₃ ≥ 5 со знаком «-», чтобы оно превратилось в равенство 2х₁ +x₂ +2x₃ –х₅ =5,  где х₅= -5+2х₁+х₂+2х₃.

4) В целевую функцию х₄, х₅ вводятся с коэффициентом, равным нулю.5)Запишем задачу в основном виде:

Z (Х) = 3х₁′ - 3х₁′′ + x₂ + x₃ + 0 х₄ + 0х₅ → mах (min),                    (9)

х₁′ - х₁′′ + 2х₂ + х₃                = 7, х₁′ - х₁′′ -   х₂ + 2х₃ + х₄       = 1,                                                     (10)

2х₁′- 2х₁′′ + х₂ + 2х₃        - х₅ =5, х₁′  ≥ 0,    х₁′′  ≥ 0,  х₂ ≥ 0,   х₃ ≥ 0,    х₄ ≥ 0,    х₅ ≥ 0.                      (11)

1.2. Симплекс-метод .Пусть поставлена задача ЛП. Найти минимум (максимум) функции

Z(Х) = c₁x₁ + c₂x₂ + … + c_nx_n,                                                  (1)

при ограничениях:

                                                              (2)

хi ³ 0,  i = 1, 2, …, n,                                                                          (3)

bj ³ 0,   j = 1, 2, …, m, m<n.                                                               (4)

Перепишем эту задачу в векторной форме:

Найти минимум (максимум) функции Z(Х) = c₁x₁ + c₂x₂ + … + c_nx_n, при ограничениях

                                                    (5)

где

m – Мерные вектор-столбцы.

1.2.1 Определения. 1º. Любые m переменных системы (2) называются базисными (или основными), если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные n-m переменных называются небазисными.

2º. Решение Х0 = (х1, х2, …, хn) системы (2) называется:

а – планом или допустимым, если xi ≥ 0 для любых i = 1, 2, …, n;

б – базисным, если n-m небазисных переменных равны нулю, т.е.   Х0 = (х1, х2, …, xm, 0, …, 0);

в – вырожденным, если Х0 - базисное решение и хотя бы одна из базисных переменных равна нулю.

г – опорным, если X0 – базисное решение и векторы А1, А2, …, Аm, входящие в разложение (5) с положительными коэффициентами хj, являются линейно-независимыми.

3º. Оптимальным решением (планом) задачи ЛП (1) – (4) называется решение, доставляющее наименьшее (наибольшее) значение линейной функции Z(X).

Пусть требуется найти минимальное (максимальное) значение функции

Z(Х) = c₁x₁ + с₂x₂ +…+ c_nx_n   при ограничениях:

1х₁ + 0х₂ + … + 0х_m + a_{1 m+1}x_m+1 + … + a_1nx_n = b₁ ,

0х₁ + 1х₂ + … + 0х_m + a_{2 m+1}x_m+1 + … + a_2nx_n = b₂ ,

.    .    .    .    .    .    .    .    .    .    .    . .    .    .    .    .    .                    (6)

0х₁ + 0х₂ + … + 1х_m + a_{m m+1}x_m+1 + … + a_mnx_n = b_m ,

x_i ³ 0 ,  i = 1, 2 ,…, n ,    b_j ≥ 0 ,   j = 1, 2, …, m.

Заметим теперь, что система (6) имеет матрицу

.

Векторная форма данной задачи имеет следующий вид: Найти минимум (максимум) функции

Z(Х) = c₁x₁ + с₂x₂ +…+ c_nx_n   , при ограничениях

где