15. F = 5X₁ + 3X₂  max;

3X₁ + 5X₂ 15,

5X₁ + 2X₂ 10,

.

16. F = 2X₁ + 3X₂  max;

X₁ + X₂ 2,

X₁ + X₂ 1,

.

17. F = X₁ - 2X₂  min;

X₁ - X₂ 1,

X₁ + X₂ 2,

X₁ - 2X₂ 0,

.

18. F = X₁ + 3X₂  max;

X₁ - X₂ 1,

2X₁ + X₂ 2,

X₁ - X₂ 0,

.

19. F = X₁ + X₂  max;

X₁ + 2X₂ 10,

X₁ + 2X₂ 2,

2X₁ + X₂ 10,

.

20. F = 2X₁ + 3X₂  min;

X₁ + X₂ 4,

3X₁ + X₂ 4,

X₁ + 5X₂ 4,

X₁ 3,

X₂ 3,

.

27. F = X₁ - X₂  min;

X₁ + X₂ 1,

X₁ - 2X₂ 1,

2X₁ + 3X₂ 2,

3X₁ + 2X₂ 3,

X₁ + X₂ 0.5,

.

1.4 Симплекс - метод решения задач лп

Каноническая задача имеет смысл только тогда, когда n (число неизвестных переменных) больше m (число уравнений).

(1.17)

при условиях (ограничениях)

i= (1.18)

. (1.19)

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

Каноническая задача имеет смысл только тогда, когда n (число неизвестных переменных) больше m (числа уравнений).

(1.17)

при условиях (ограничениях)

(1.18)

x  0. (1.19)

Если число уравнений больше числа неизвестных, то либо эти уравнения линейно зависимы, и тогда часть из них можно отбросить, либо эти уравнения противоречивы, и не существует ни одного допустимого решения. Если же число линейно-независимых уравнений равно числу неизвестных, то существует единственное решение, и поэтому не возникают задачи отыскания экстремума. Условие n>m в канонической задаче обусловливает множество решений системы. Среди множества решений существуют так называемые базисные решения X_б. Они строятся следующим образом. Среди n неизвестных выбирают m (по числу уравнений). Эти m неизвестных образуют базис. Все остальные n-m неизвестные, не вошедшие в число отобранных, полагают равными нулю и называют небазисными (свободными) неизвестными. Существует множество вариантов выбора базиса. Число таких вариантов равно . Базисное решение системы уравнений будет допустимым (опорным), если все базисные переменные неотрицательны (X_j 0). Таким образом, допустимым решением (планом) называют любой набор переменных X_j, удовлетворяющих ограничениям (1.18) и (1.19).

Решение задачи ЛП заключается в том, чтобы среди всех опорных базисных решений выбрать такое, при котором целевая функция (1.17) достигает экстремума. Наиболее распространенным методом решения задач ЛП канонического вида является симплекс-метод. Симплекс-метод заключается в последовательном вычислении решений, находящихся в вершинах многогранника (симплекса), образующего область допустимых решений. Вычисления выполняются таким образом, что значения целевой функции при каждом следующем шаге строго возрастают. Это свойство симплекс-метода приводит к тому, что просматривается лишь небольшая часть допустимых решений из общего числа. Благодаря этому за приемлемое время можно решить задачи с большим числом переменных.

Целенаправленный переход от одного допустимого решения к другому (от одной вершины симплекса к другой) осуществляется при этом за счет изменения состава базисных и свободных переменных по специальным правилам замещения.

Основная система уравнений

Пусть X_б=  0 - базисный вектор, X=  0 - небазисный вектор,

_{B= 0} - вектор свободных членов, A= - матрица коэффициентов.

Основной или нормальной формой системы уравнений называется векторное уравнение вида

X_б = B – AX, (1.20)

которое в координатной форме имеет вид :

(1.21)

По определению выполняется соотношение m<n, т.е. число уравнений всегда меньше числа неизвестных.

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

1. Выбираем такой столбец матрицы А, который имеет хотя бы один положительный элемент a_ij . Такой столбец называют разрешающим. Пусть для простоты рассуждения он будет первым в системе (1.21).

2. В разрешающем столбце для всех положительных элементов находим множество частных от деления на них соответствующих членов, т.е. находим для

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

4. Элемент матрицы А, стоящий на пересечении разрешающей строки и разрешающего столбца, назовем разрешающим. В нашем случае это .

Решим уравнение системы относительно неизвестного, стоящего при разрешающем элементе.

5. Подставим найденное значение неизвестного во все другие уравнения, получим систему

(1.22)

В результате исходная система (1.21) преобразована в новую систему (1.22), в которой произошло замещение переменной в базисном векторе. Все вычисления значительно упрощаются, если использовать компактный способ записи в специального рода таблицах. В таблице записывается только числовая информация системы (1.21), а в заголовке указывается, к каким переменным эта информация относится (табл. 1.7).

Таблица 1.7

	B	Xc
		xm+1	...	xn
x1	b1	a1,m+1	...	a1,n
...	...	...	...	...
xm	bm	am,m+1	...	am,n

Правила образования новых коэффициентов при замещении базиса

приведены в табл. 1.8.

Таблица 1.8

Элементы	Элементы таблицы
	Старой	Новой
Разрешающий	ak,s
Разрешающей строки	ak,j
Разрешающего столбца	ai,s
Все остальные	ai,j

В этой таблице введем следующие индексы:

S - индекс элементов разрешающего столбца,

K - индекс элементов разрешающей строки.

П

a_k,s

a_i,s

оясним вычисления _ai,j с использованием “правила прямоугольника“. Необходимо взять разрешающий элемент a_k,s и мысленно соединить его с тем коэффициентом, новое значение которого требуется найти. Эту прямую следует считать главной диагональю, на ней строится прямоугольник, сторонами которого являются строки и столбцы. В прямоугольнике надо провести побочную диагональ, тогда значение нового коэффициента будет равно его исходному значению, из которого вычитается произведение элементов, стоящих на побочной диагонали, поделенному на разрешающий элемент. Поясним эти действия на схеме (рис. 1.9). Прежде чем заполнить симплекс-таблицу исходные уравнения следует представить в виде (1.21).

a_k,j

a_i,j

Рис. 1.9

Суть преобразований симплекс-метода рассмотрим на примере 1.4. Давайте вспомним ограничивающие неравенства и целевую функцию из этого примера и найдем max целевой функции, пользуясь вышеизложенным методом :

F = 908X₁ + 676X₂  max.

X₁ + X₂ 14,

X₂ 10,

10 X₁ + 8 X₂ 120,

7X₁ + 5 X₂ 70,

4X₁ + 2X₂ 28,

.

Преобразуем ее в каноническую форму, вводя дополнительные переменные X_j 0, и превратив неравенства в равенства. Следует обратить внимание, что если в неравенстве стоит знак " ", то при свободной переменной пишут "  ", в противном случае - " + ":

X₁ + X₂ = 14 - X₃ ,

X₂ = 10 - X₄ ,

10 X₁ + 8 X₂ = 120 - X₅ ,

7X₁ + 5 X₂ = 70 - X₆ ,

4X₁ + 2X₂ = 28 - X₇ .

Чтобы приступить к процедуре симплекс-метода, нужно из множества базисных решений полученной системы уравнений сначала найти опорное. С учетом этого в решении задач симплекс-методом различают три этапа:

- нахождение первоначального базисного решения и формирование исходной симплекс-таблицы;

- определение допустимого решения;

- определение оптимального решения.

1-й этап

Первоначальное базисное решение систем находим, полагая свободными переменные X₁ и X₂.

Т огда X₃ = 14 - X₁ - X₂ ,

X₄ = 10 - X₂ ,

X₅ =120 - 10X₁ - 8X₂ ,

X₆ = 70 - 10X₁ - 5X₂ ,

X₇ = 28 - 4X₁ - 2X₂ ,

F = 908X₁ + 676X₂ = 0 .

Преобразуем эти уравнения к нормальному виду:

X ₃ = 14 - ( X₁ + X₂ ),

X₄ = 10 - ( 0X₁ + X₂ ),

X₅ =120 - (10X₁ + 8X₂ ),

X₆ = 70 - ( 7X₁ + 5X₂ ),

X₇ = 10 - ( 4X₁ + 2X₂ ),

F = 0 + 908 X₁ + 676 X₂ .

Полученную систему уравнений запишем в виде исходной симплекс-таблицы (табл. 1.9). В табл. 1.9 нет отрицательных свободных членов. Следовательно, нами получено опорное (допустимое) решение, так как допустимым решением является любое неотрицательное решение (при котором > 0), но оно не является оптимальным.

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

Таблица 1.9

Базисные переменные Xб	Свободный член	Свободные переменные
		X1	X2
X3	14	1	1
X4	10	0	1
X5	120	10	8
X6	70	7	5
X7	28	4	2
F	0	- 908	- 676

2-й этап

Напомним, что основная операция симплекс-метода заключается в том, что некоторая базисная переменная замещается на свободную переменную . При этом операция замещения выполняется при соблюдении следующих условий:

- значение целевой функции F в новом опорном (допустимом) решении должно быть больше, чем в предыдущем;

- новое решение системы должно быть также опорным (допустимым).

В нашем примере первое условие выполняется, если разрешающий элемент положительный и выбран в столбце отрицательного коэффициента F-строки.

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

По выше изложенному правилу для нахождения допустимого решения меняют местами базисные и свободные переменные. Для этого находят разрешающий элемент (в табл. 1.9 он взят в рамку). В нашем случае разрешающим может быть как столбец X₁ , так и X₂. Деля свободные переменные на соответствующие значения X₁ и X₂ (кроме строки F), находим наименьшее положительное значение. Для столбца X₁:

_{; ;} ; ; _.

_{Для столбца X2 :}

_{; ;} ; ; _.

Наименьшее отношение 28/4 определяет разрешающую строку и разрешающий столбец, а пересечение разрешающего столбца и разрешающей строки - разрешающий элемент a_ks = 4. В табл. 1.9 разрешающий столбец и разрешающую строку отмечаем стрелками (  ). Определив a_ks , строят следующую таблицу, в которой меняют местами переменные, входящие в строку и столбец разрешающего элемента, т.е. переводят базисные переменные в свободные, а свободные - в базисные.

В нашем примере меняем местами переменные Х₇ и Х₁ , отмеченные в табл. 1.9 стрелками. Коэффициенты новой табл. 1.10 находят по коэффициентам старой табл. 1.9, используя выражения, приведенные в табл. 1.8 и “правило прямоугольника”. В табл. 1.10 снова не имеем оптимального решения.

Таблица 1.10

				Базисные переменные Хб			Свободный член В		Свободные переменные
									X7		X2
Х3		7			- 1/4			1/2
Х4		10			0			1
	Х5		50			-5/2				3
	Х6		21			-7/4				3/2
	Х1		7			1/4				1/2
	F		6356			227				-222

По вышеописанным правилам в табл. 1.10 находим разрешающий элемент 1 и строим новую табл. 1.11 сделав замещение базиса (Х₄ и Х₂). Особо подчеркнем, что для нахождения разрешающего элемента мы должны выбирать наименьшее положительное значение, т.е. отрицательные отношения свободных членов к коэффициентам разрешающего столбца мы не рассматриваем.

Таблица 1.11

			Базисные переменные Хб				Свободный член В	Свободные переменные
								X7			X4
Х3		2			- 1/4				- ½
Х2		10			0				1
	Х5			20		-5/2				- 3
	Х6			6		-7/4				- 3/2
	Х1			2		1/4				- ½
	F			8576		227				222

3-й этап

Проверим, является ли найденное решение оптимальным, а для нашего примера - максимальным. Для этого сделаем анализ целевой функции F: F = 8576 + 227 X₇ + 222 X₄ .

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

X₃ = 2; X₂ = 10; X₅ = 20; X₆ = 6; X₁ = 2; X₇ = X₄ = 0;

F_max = 8576.

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

В соответствии с рассмотренной последовательностью, алгоритм симплекс-метода должен иметь следующие блоки:

1. Нахождения первоначального базисного (опорного) решения и формирование исходной таблицы.

2. Отыскание разрешающего элемента a _ks (нахождение отрицательного свободного члена - b _i < 0 и минимального отношения b _i / a_ij ; если в строке отрицательного свободного члена нет отрицательных коэффициентов, то задача неразрешима).

3. Перерасчет новой таблицы по формулам табл. 1.8.

4. Проверка наличия отрицательного свободного члена. Если он есть, то переходим к п. 2. Отсутствие отрицательного свободного члена означает, что получено опорное (допустимое) решение.

5. Аналогично п. 2 - 4 выполняется перерасчет таблицы при поиске оптимального решения.

Решение задачи ЛП симплекс-методом в матричной форме

Требуется минимизировать ,

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

при x  0.

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

C = (C₁ , ... , C_n ) - вектор оценок,

X = (X₁ , ... , X_n ) - вектор переменных,

b = (B₁ , ... , B_m ) - вектор ограничений

и матрицу

A=

размером ( m n ) - матрицу коэффициентов ограничений.

Тогда задача ЛП будет иметь следующую трактовку:

минимизировать F=CX

при условиях AX = b, X 0.

Эту задачу можно записать в матричной форме:

Введем обозначение:

А^*= - здесь матрица A^* размером (m+1)(n+1).

Согласно выше приведенной методике находят разрешающий элемент a_ks.

Следующий шаг симплекс-метода - процедура исключения Гаусса, которая позволяет сделать все коэффициенты в s-м столбце, кроме a_ks , нулевыми, a_ks - равным единице.

Для симплекс-метода в матричной форме итерация симплекс-метода эквивалентна умножению матричного уравнения слева на следующую квадратную матрицу:

(1.23)

, где k 0; s 0.

Если все столбцы матрицы A разделить на базисные B и небазисные N, то задачу ЛП можно записать так:

,

где C_b и C_N - соответствующие компоненты вектора C, X_b , X_N - базисные и небазисные переменные.

Для выбора начальных базисных переменных x_b следует умножить уравнение слева на матрицу:

где R= C_b B^-1 .

В результате получим

,

где I - единичная матрица.

Отсюда следует, что относительные оценки при небазисных переменных

c_j = c_j - C_b B^-1 a_j = c_j - Ra_j .

Базис будет допустимым, если свободные члены при базисных переменных будут неотрицательными, т.е. B^-1b  0.

Если c_j  0 для , то базис является оптимальным решением задачи. Вектор называют вектором текущих цен. Каждая строка умножается на вектор R и вычитается из строки коэффициентов стоимости, для того чтобы исключить коэффициенты стоимости при базисных переменных.

Если задача ЛП задана не в канонической форме, т.е.

минимизировать F=CX

при условиях AX b , X 0,

то, вводя слабые переменные, их можно записать в виде

Метод исключения по строкам для матрицы эквивалентен умножению этой матрицы слева на B^-1, где B - базис подматрицы A, тогда

,

т.е. матрица, получаемая на месте единичной I, будет матрицей, обратной для текущего базиса. Относительные оценки, расположенные над единичной матрицей, будут

,

поскольку - единичные векторы.

Так как F= C_bB^-1b = Rb, текущее значение целевой функции равно произведению вектора текущих цен матрицы A на исходный вектор b.

Пример. F = 5X₁ + 6X₂ + 3X₃ + 4X₄ + 5X₅  min

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

2 X₁ + 3X₃ + 4X₄ + 2X₅ = 10,

3X₂ + 3X₄ + 6X₅ = 9,

.

Для данного примера матрица A^* будет иметь вид

.

Пусть X₁ и X₂ - базисные переменные.

Матрица B имеет вид

.

Тогда обратная матрица B^-1 имеет следующий вид

.

Напомним, что , где присоединенная матрица, составленная из алгебраических дополнений элементов b_ik определителя матрицы B.

Определитель равен:

= .

Следовательно, матрица B неособенная.

Алгебраические дополнения элементов определителя имеют следующие значения:

b₁₁ = 3, b₁₂ = 0, b₁₂ = 0, b₂₂ = 2; т.е. .

Умножив на , находим обратную матрицу:

.

Вектор текущих цен будет

R = C_bB^-1 = = .

Напомним, что C_b - базисные компоненты вектора C:

C_b = .

Тогда = .

Для выбора начального базиса нужно матрицу A^* умножить слева на матрицу

,

получим

=

.

Разрешающий элемент находится в квадрате.

Итерация симплекс-метода эквивалентна полученной таблице, умноженной слева на следующую матрицу:

.

Эта матрица получена из матрицы (1.23)

Здесь a_ks = 2 ;

a₁₁ = 1; a₁₂ = - a_0s / a_ks = - 12/2 = - 6;

a₁₃ = 0 ; a₂₁ = 0 ; a₂₂ = 1/ a_ks = 1/2 ; a₂₃ = 0;

a₃₁ = 0 ; a₃₂ = - a_ms / a_ks = -1/2 ; a₃₃ = 1.

Тогда имеем

=

(1.24)

Разрешающий элемент помещен в квадрат.

Следующая итерация симплекс-метода равносильна умножению слева на матрицу

.

Тогда

=

.

Следовательно, F min =11; X₄=7/3; X₅=1/3; X₁=X₂=X₃=0.