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

Найти вектор x=(x₁...,x_n), что минимизирует целевую функцию

L(x)= c₁x₁ + ... + c_nx_n (2.1)

и удовлетворяет систему ограничений

a₁₁x₁ + . . . + a_1n x_n = a₁₀

. . . . . . . . . . . . . . . . . . . . . . . (2.2)

a_m1x₁ + . . . + a_mnx_n = a_m0

x_j0, j=1...,n. (2.3)

В задаче (2.1)–(2.3) будем называть матрицу A=||a_ij||, i=1...,m, j=1...,n, матрицей условий; вектор-столбец A_j=(a_1j...,a_mj) ^т, j=1...,n — j-м вектором условий; вектор A₀=(a₁₀...,a_m0) ^т — вектором ограничений.

Основные определения.

Вектор x=(x₁...,x_n) называется допустимым решением ЗЛП, если его компоненты удовлетворяют ограничение (2.2)–(2.3).

Ненулевое допустимое решение x — базисный (ДБР), если его положительным компонентам x_jотвечают линейно независимые векторы условий A_j. (Нулевое допустимое решение будем всегда считать базисным).

Система m линейно независимых векторов условий, что включает указанные векторы Aj, называется базисом.

Векторы базиса образуют базисную матрицу.

Изложение симплекс-метода.

Симплекс-метод (СМ) непосредственно применяется к развязыванию каноничной задачи линейного программирования (КЗЛП) и осуществляет целеустремленное перебирание допустимых базисных решений (ДБР) (вершин допустимого многогранника решений ЗЛП, что определяется ограничениями (2.2)–(2.3)), к множеству которых принадлежит оптимальное решение, если он существует; или определяет, что ЗЛП не имеет оптимального решения.

ЗЛП — каноничная, если ее ограничения (2.2) имеют каноничную форму:

x_i + a_i,m+1x_m+1 + ... + a_inx_n = a_i0, a_i00, i=1...,m

то есть, матрица условий A=||a_ij||, i=1...,m, j=1...,n, заключает в себе единичную подматрицу размера mm и вектор ограничений A₀=(a₁₀...,a_m0) ^т — неотъемлемый.

КЗЛП элементарно определяет такие основные в линейном программировании конструкции:

• некоторый ДБР — x(0)=(a₁₀...,a_m0,0,...,0);

• его базис — m-мерные единичные векторы (1,0...,0) ^т, (0,1...,0) ^т..., (0...,0,1) ^т;

• его базисную матрицу B — единичную матрицу размера mm;

• базисные переменные — x₁...,x_m.

Стандартная ЗЛП (2.1)–(2.3) сводится в общем случае к каноничной ЗЛП добавлением искусственных неотъемлемых переменных к левым частям ограничений (2.2) и введением этих же переменных с достаточно большим коэффициентом М>0к целевой функции (2.1) (М-метод).

М-задачаимеет вид:

L(x)= c₁x₁ + ... + c_nx_n + M(y₁ + ... + y_m)  min

a₁₁x₁ + . . . + a_1n x_n + y₁ = a₁₀

. . . . . . . . . . . . . . . . . . . . . . . . . . . . ,

a_m1x₁ + . . . + a_mnx_n + y_m = a_m0

xj0, j=1...,n, yi0, i=1...,m

a_i00, i=1...,m.

Признак оптимума: Если на некотором шаге СМ симплекс - разницы (см. алгоритм) ДБР x*незначительные, то x* — оптимальное решение КЗЛП.

Условия отсутствия решения:

1. ЗЛП не имеет оптимального решения, если на каком-либо шаге хотя бы один вектор условий _Aj с отрицательной оценкой _j не имеет положительных компонент;

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

Алгоритм симплекс-метода.

На каждом шагу СМ выполняются такие действия (расчетные формулы наводятся лишь для первого шага).

1. Рассматривается ДБР x=(a10...,a_m0,0,...,0).

Вычисляются относительные оценки (симплекс - разницы) _j небазисных переменных x_j, j=m+1...,n, за формулой:

_j=cj – (c_б, Aj)

где c_б=(c₁...,c_m), Aj — вектор условий, что отвечает переменной xj (относительные оценки базисных переменных приравняются нулю).

Если для всех j=1...,n, выполняется условие _j0, то ДБР x является оптимальным решением КЗЛП. Если к тому же все искусственные переменные равняются нулю, то, отбрасывая их, получим оптимальное решение исходной ЗЛП; иначе исходная ЗЛП не имеет решений (ее допустимая область пустая).

Если существует такое j, что _j<0, а вектор условий Aj не имеет положительных компонент, то ЗЛП не имеет оптимального решения (ее целевая функция L(x) не ограничена снизу на допустимом многограннике решений). Конец вычислений.

2. Если существуют индексы j, для которых _j<0, а соответствующие векторы условий Ajимеют положительные компоненты, то находят k за формулой

k=argmin_j

j: _j<0

и, вычисляя для a_ik>0отношения _i=ai0a_ik, определяют l, что удовлетворяет соотношение

l=argmin_и.

и: a_ik>0

3. Переходят к новому ДБР, путем введения к базису вектора A_kи выведения из базиса вектора A_l. Такой переход осуществляется с помощью симплекс - превращений (элементарных превращений Жордана - Гаусса) с ведущим элементом a_lkнад элементами расширенной матрицы условий (2.2). Переход к пункту 1.

Программное обеспечение.

Обучающий модуль, с помощью которого ЗЛП решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО. Геометрическая интерпретация задачи линейного программирования осуществляется модулем, который вызывается из того же самого раздела.

Задание.

Решить симплекс-методом задачи линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1№9), а также следующие задачи.

Во всех задачах, которые предлагаются ниже, все переменные неотъемлемые.

1)	x1 + x2 + x3  min	2)	2 x1 + x2 – x3 – x4  min
	x1 – x4 – 2 x6 = 5		x1 + x2 + 2 x3 – x4 = 2
	x2 + 2 x4 – 3 x5 + x6 = 3		2 x1 + x2 – 3 x3 + x4 = 6
	x3 + 2 x4 – 5 x5 + 6 x6 = 5;		x1 + x2 + x3 + x4 = 7;

3)	x1 – 2x2 + 3x3  min	4)	2x1 – 3x2  max	5))	6 x1 + 4 x2  min
	2x1 + 3x2 + 4x3 = 1		5x1 + 2x2  10		2 x1 + x2  3
	–2x1 + x2 + 3x3 = 2;		x1 + 3x2  12;		x1 – x2  1;

6)	2 x1 – 4 x2  min	7)	7 x1 + 5 x2  max	8)	3 x1 + 2 x2  max
	8 x1 – 5 x2  16		7 x1 + 5 x2  7		4 x1 + 2 x2  12
	x1 + 3 x2  2		7 x1 – 5 x2  35		x1 + 2 x2  10
	2 x1 + 7 x2  9;		x1 – x2  0;		2 x1 + 2 x2 = 6;

9)	4 x1 + 5 x2 + 9 x3 + 11 x4  max	10)	2 x1 + x2 – x3 – x4  min
	x1 + x2 + x3 + x4  15		x1 + x2 + 2 x3 – x4 = 2
	7 x1 + 5 x2 + 3 x3 + 2 x4  80		2 x1 + x2 – 3 x3 + x4 = 6
	3 x1 + 5 x2 + 10 x3 + 15 x4  60;		x1 + x2 + x3 + x4 = 7;

11)	4x1 + x2 – 2x3 – x4 – x5  min	12)	x1 + 2 x2 + 3 x3 – x4  max
	x3 – x4 + x5 = 1		x1 + 2 x2 + 3 x3 = 15
	x2 + 2x4 – x5 = 1		2 x1 + x2 – 3 x3 = 20
	x1 + 2x2 + 2x5 = 4;		x1 + 2 x2 + x4 = 10.

Ответы:

1) x* = (7.1; 0; 0; 1.3; 0; 0.4), L(x*)= 7.1.

2) x* = (0; 4.13; 0.25; 2.63), L(x*)= 1.25.

3) Решения нет ( D =  ).

4) x* = (12; 0), L(x*)= 24.

5) x* = (1.33; 0.33), L(x*)= 9.33.

6) x* = (0; 1.29), L(x*)= 5.14.

7) Решения нет (целевая функция неограниченна сверху на допустимом множестве).

8) x* = (3; 0), L(x*)= 9.

9) x* = (10.16; 0; 2.95; 0), L(x*)= 67.21.

10) x* = (0; 4.13; 0.25; 2.63), L(x*)= 1.25.

11) x* = (0; 0; 0.5; 1.5; 2), L(x*)= 4.5.

12) Решения нет ( D =  ).

Лабораторная работа 3.