3. Основные теоремы линейного программирования

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

Однако сначала напомним о некоторых понятиях, важных с точки зрения дальнейшего разговора.

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

Базисным решением системы m линейных уравнений c n переменными (m < n) называется всякое ее решение, в котором все неосновные переменные имеют нулевые значения.

Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

В частном случае, когда в систему ограничений входят только две переменные x₁ и x₂, это множество можно изобразить на плоскости. Так как речь идет о допустимых решениях (x₁, x₂ ≥ 0), то соответствующее множество будет располагаться в первой четверти декартовой системы координат. Это множество может быть замкнутым (многоугольник), незамкнутым (неограниченная многогранная область), состоять из единственной точки и, наконец, система ограничений-неравенств может быть противоречивой.

Теорема 2. Если задача линейного программирования имеет оптимальное решение, то оно совпадает с одной (двумя) из угловых точек множества допустимых решений.

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

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

Следствием из теорем 2 и 3 является утверждение о том, что оптимальное решение (оптимальные решения) задачи линейного программирования, заданной (или приведенной) ограничениями-уравнениями, совпадает с допустимым базисным решением (допустимыми базисными решениями) системы ограничений.

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

4. Симплекс-метод решения задачи линейного пронраммирования

Пусть требуется найти max целевой функции ,

Z = , (1)

при условиях:

(2)

, . (3)

где , , , , – постоянные числа ( > 0 , m < n ).

Введя векторы:

A₁ = ,A₂ = ,...,A_m = , A_m+1 = ,...,A_n = ,A₀ = ,

можно записать систему (2) в векторной форме :

x₁ A₁ + x₂ A₂ + ... x_m A_m + x_m+1 A_m+1 + ... + x_n A_n = A₀. (4)

Нетрудно заметить, что справедливо равенство:

b₁A₁ + b₂A₂ + ... +b_mA_m = A₀,

а это означает, что X₀ = (b₁,b₂,...,b_m,0,..,0) является решением системы (2) или начальным опорным планом задачи. Этот план определяется системой базисных векторов A₁,A₂,...,A_m m-мерного пространства. Каждый вектор A_j может быть представлен в виде линейной комбинации векторов этого базиса: A_j= (j=0..n).

Положим Z_j = C_б A_j = , где C_б = (c₁, c₂, ...,c_m) - ценовoй вектор базиса и

_j = Z_j - c_j (x_ij - компоненты вектора A_j в данном базисе).

Оптимальность опорного плана и последующие шаги решения задачи определяются следующими теоремами:

Теорема 1. Опорный план X=(x₁, x₂,..,x_m,0,...,0) задачи линейного программирования (1)-(3) является оптимальным тогда и только тогда, когда _j0 для всех j (j=1,...,n).

Теорема 2. Если для некоторого j=k _j<0 и среди чисел a_ik (i=1,..,m) нет положительных чисел, то целевая функция задачи не ограничена на множестве ее планов.

Теорема 3. Если опорный план X задачи не вырожден и _k < 0, но среди чисел a_ik есть положительные (не все a_ik  0 ), то существует опорный план X₁ такой, что Z(X₁)>Z(X).

Исходные данные и процесс вычисления (переход к новому опорному плану) удобно записывать в табл. 1

Таблица 1

i	базис	Сб	A0	c1	c2	...	ck	...	cn
				A1	A2	...	Ak	...	An
1	E1	C10	b10	a11	a12	...	a1k	...	a1n
2	E2	C20	b20	a21	a22	...	a2k	...	a2n
...	...	...	...	...	...	...	...	...	...
m	Em	Cm0	bm0	am1	am2	...	amk	...	amn
m+1			Z0	1	2	...	k	...	n

Базисный вектор E_i(i=1,...,m) совпадает с A_s, если a_is = 1, а все остальные компоненты равны нулю. Соответствующий коэффициент c_s при x_s целевой функции записан в C_б. Значения _j=Z_j-c_j=A_jC_б-c_j (j=0,...,n) записаны в (m+1)-й строке. В столбце A₀ записаны свободные члены b_i системы (2) в порядке, соответствующем каждому базисному вектору. Компоненты вектора A₀ и составляют опорный план (b_i>0); в (m+1)-й строке этого столбца получаем значение целевой функции Z₀=C_бA₀ при этом плане.

Приведем алгоритм решения задачи симплекс-методом.

1. Находят опорный план X₀ = (b₁, b₂,...,b_m, 0,..., 0).

2. Составляют симплекс-таблицу типа 1.

3. Выясняют, имеется ли хотя бы одно _j<0. Если нет таких чисел, то найденный опорный план будет оптимальным. В противном случае устанавливают либо неразрешимость задачи (все компоненты вектора A_j неположительны), либо переходят к новому опорному плану.

4. В новый план включают вектор A_s, для которого , _j < 0, a , a_is > 0. Элемент a_ks является разрешающим, который и определяет базисный вектор E_k, подлежащий замене вектором A_s.

5. В новом базисе таблица пересчитывается так:

а) все элементы k-ой строки, начиная со столбца А₀, делятся на a_ks;

б) все элементы столбца A_s заменяются нулями, кроме a_ks=1. Координаты остальных базисных векторов остаются неизменными;

в) любой элемент (j  s) определяется по формуле:

- правило прямоугольника; (5)

г) (m+1)-я строка вычисляется аналогично:

.

6. Если все , то полученный план оптимальный (составляется из компонент A_o) и . В противном случае возвращаемся к п.4 алгоритма. После конечного числа итераций получим оптимальный план или докажем отсутствие такого плана.

Пример 4. Для изготовления изделий типа А и В используется сырье трех видов, запасы каждого из которых Р1 , Р2 , Р3 . На производство одного изделия типа А требуется затратить а1 кг сырья первого вида, а2 кг сырья второго вида, а3 кг сырья третьего вида. На одно изделие типа В расходуется соответственно b1 , b 2 , b3 кг сырья каждого вида. Прибыль от реализации единицы изделия А составляет α /ден.ед./, а изделия В - β /ден.ед./. Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации. Решить задачу симплекс-методом.

Таблица 4.

Вид сырья	Нормы затрат сырья (кг) на одно изделие		Общее количество сырья (кг)
	А	В
1	2	3	428
2	3	6	672
3	2	8	672
Цена одного изделия (руб.)	3	8

Решение. Задача принимает вид:

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

, .

В векторной форме будем иметь

x₁A₁ + x₂A₂ + x₃A₃ + x₄A₄ = A₀ , где

A₁= ,A₂= , A₃ = , A₄= ,A₅= .

Среди векторов A₃, A₄ A₅ - единичные, их принимаем за базисные и, положив x₁=x₂=0, получаем начальный опорный план:

X₀=(0, 0, 428, 672, 672).

Составляем симплексную таблицу для 1-ой итерации и вычисляем

Z₀=C_бA₀=0, ₁=Z₁-c₁=0-3=-3, ₂=Z₂-8=-8, и для векторов базиса ₃=₄=₅=0. Как видно, основные переменные x₁, x₂ равны нулю, т.е. производство не начато, прибыль Z₀=0, и потому план X₀ не является оптимальным. Находим в каждом из столбцов A₁, A₂

(j=1, 2, 3)

и ,

и ,

Очевидно .

Поэтому вектор A₂ подлежит включению в базис вместо A₅ (разрешающий элемент a₃₂).

Составляем новую таблицу в базисе векторов A₃, A₄, A₁. Для удобства поместим все итерации последовательно в одну табл. 3.

Таблица 3

i	Базис	Cб	A0	3	8	0	0	0
				A1	A2	A3	A4	A5
1 2 3 m+1	A3 A4 A5	0 0 0	428 672 672 0	2 3 2 -3	3 6 8 -8	1 0 0 0	0 1 0 0	0 0 1 0
1 2 3 m+1	A3 A4 A1	0 0 8	176 168 84 672	5/4 3/2 1/4 -1	0 0 1 0	1 0 0 0	0 1 0 0	-3/8 -3/4 1/8 1
1 2 3 m+1	A3 A1 A2	0 3 8	36 112 56 784	0 1 0 0	0 0 1 0	1 0 0 0	-5/6 2/3 -1/6 2/3	1/4 -1/2 1/4 1/2

Приведем некоторые этапы заполнения таблицы 2-й итерации.

Все элементы строки A₅, начиная со столбца A₀ (вектор A₅ подлежит исключению из базиса), делим на a₃₂=8. Записываем в соответствующих столбцах базисные векторы A₃, A₄, A₁ (₁=₄=₃=0). Вычисляем элементы столбцов A_j по формулам (4). Например:

,

,

и т.д.

В (m+1)-й строке ₁=-1<0, следовательно план не является оптимальным. Вектор A₁ подлежит включению в базис вместо A₄, так как - разрешающий элемент.

После 3-й итерации получаем все _j  0 и опорный план X=(112, 56, 36, 0, 0) будет оптимальным, а Z_max=784.

Итак, оптимальный план включает изготовление 112 изделий типа A и 56 изделий типа B. При этом полностью используется сырье двух видов, а прибыль от производимой продукции составит 784 руб.

Пример 5. Решить симплекс-методом задачу: для изготовления различных изделий А, В, С предприятие использует три вида сырья. Нормы расхода сырья на производство одного изделия каждого вида, цена одного изделия А, В и С, а также общее количество сырья каждого вида, которое может быть использовано предприятием, приведены в табл.2. Изделия А, В и С могут производиться в любых соотношениях (сбыт обеспечен), но производство ограничено выделенным предприятию сырьем каждого вида. Составить план производства изделий, при котором общая стоимость всей произведенной предприятием продукции является максимальной.

Таблица 2.

Вид сырья	Нормы затрат сырья (кг) на одно изделие			Общее количество сырья (кг)
	А	В	С
1	18	15	12		360
2	6	4	8		192
3	5	3	3		180
Цена одного изделия (руб.)	9	10	16

Решение. В векторной форме будем иметь

x₁A₁ + x₂A₂ + x₃A₃ + x₄A₄ + x₅A₅ + x₆A₆ = A₀ , где

A₁= ,A₂= , A₃ = , A₄= ,A₅= ,A₆= , A₀= .

Среди векторов A₄, A₅, A₆ - единичные, их принимаем за базисные и, положив x₁=x₂=x₃=0, получаем начальный опорный план:

X₀=(0, 0, 0 ,360, 192, 180).

Составляем симплексную таблицу для 1-ой итерации и вычисляем

Z₀=C_бA₀=0, ₁=Z₁-c₁=0-9=-9, ₂=Z₂-c₂=-10, ₃=Z₃-c₃=-16 и для векторов базиса ₄=₅=₆=0. Как видно, основные переменные x₁, x₂, x₃ равны нулю, т.е. производство не начато, прибыль Z₀=0, и потому план X₀ не является оптимальным. Находим в каждом из столбцов A₁, A₂, A₃

(j=1, 2, 3)

и ,

и ,

и .

Очевидно .

Поэтому вектор A₃ подлежит включению в базис вместо A₅ ( ₃ = b₂/a₂₃, разрешающий элемент a₂₃).

Составляем новую таблицу в базисе векторов A₄, A₃, A₆. Для удобства поместим все итерации последовательно в одну табл. 5.

Таблица 5

i	Базис	Cб	A0	9	10	16	0	0	0
				A1	A2	A3	A4	A5	A6
1 2 3 m+1	A4 A5 A6	0 0 0	360 192 180 0	18 6 5 -9	15 4 3 -10	12 8 3 -16	1 0 0 0	0 1 0 0	0 0 1 0
1 2 3 m+1	A4 A3 A6	0 16 0	72 24 108 384	9 3/4 11/4 3	9 1/2 3/2 -2	0 1 0 0	1 0 0 0	-3/2 1/8 -3/8 2	0 0 1 0
1 2 3 m+1	A2 A3 A6	10 16 0	8 20 96 400	1 1/4 5/4 5	1 0 0 0	0 1 0 0	1/9 -1/18 -1/6 2/9	-1/6 5/24 -1/8 5/3	0 0 1 0

Приведем некоторые этапы заполнения таблицы 2-й итерации.

Все элементы строки A₅, начиная со столбца A₀ (вектор A₅ подлежит исключению из базиса), делим на a₂₃=8. Записываем в соответствующих столбцах базисные векторы A₄, A₃, A₆ (₅=₃=₆=0). Вычисляем элементы столбцов A_j по формулам (4). Например:

,

,

и т.д.

В (m+1)-й строке ₂=-2<0, следовательно план не является оптимальным. Вектор A₂ подлежит включению в базис вместо A₄, так как - разрешающий элемент.

После 3-й итерации получаем все _j  0 и опорный план X=(0, 8, 20, 0, 0, 96) будет оптимальным, а Z_max=400.

Итак, оптимальный план включает изготовление восьми изделий типа В и двадцати изделий С. При этом полностью используется сырье первых двух видов и остается не использованным 96 кг сырья третьего вида, а прибыль от производимой продукции составит 400 руб.

Задача 1. Графическим методом найти решение задачи линейного программирования :