Графический метод решения.

Построим многоугольник допустимых решений. Для этого в неравенствах (4.5), (4.6) знаки неравенств заменим на знаки точных равенств

Построив эти прямые, найдем соответствующие полуплоскости и их пересечение (рис. 4.1).

Как видно из рис. 4.1, допустимым множеством решений задачи является многоугольник ОАВСDЕ. Координаты точек этого многоугольника удовлетворяют условиям (4.5) и (4.6). Следовательно, задача будет решена, если среди точек многоугольника OABCDE найти такую, в которой функция ƒ=2x₁+3х₂ принимает максимальное значение. Для нахождения этой точки построим вектор–градиент и линию нулевого уровня, т.е. прямую ƒ=2x₁+3х₂=0. Ясно, что прямая ƒ=0 проходит через начало координат и перпендикулярная вектору-градиенту . Передвигая данную прямую ƒ=0 параллельно самой себе в направлении вектора ,видим, что последней общей точкой с многоугольником является точка С.. Следовательно, в этой точке функция ƒ принимает максимальное значение. Так как С-точка пересечения прямых I и II, то ее координаты определяются решением системы уравнений

откуда х₁= 6, х₂= 4, С(6,4),

а потому f _max = f (c) = 2·6+3·4= 24.

Итак, f _max = 24 при оптимальном решении х₁= 6, х₂= 4, т.е. максимальная прибыль в 24 руб. может быть достигнута при производстве 6 единиц продукции Р₁ и 4 единиц продукции Р₂.

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

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

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

Для этого на каждой итерации производится процедура однократного замещения: одна из свободных переменных переводится в базисные и при этом одна из базисных переменных становится свободной.

Пример. Найти максимальное значение функции

Z=2x₁ + 5x₂ – 3x₃, (5.1)

при условиях (5.2)

Преобразуем неравенства системы (5.2) в уравнения. Для этого введем неотрицательные балансовые переменные х₄ и х₅

(5.3)

1. Начальным этапом решения задачи является исследование системы линейных уравнений (5.3)

Данная система уравнений (5.3) совместна и все уравнения, входящие в нее, линейно-независимы, так как ранги матрицы коэффициентов при неизвестных

A= (5.4)

И расширенной матрицы

(А/b) = (5.5)

совпадают и равны числу уравнений, т.е. трем. Чтобы в этом убедиться, достаточно найти хотя бы один минор третьего порядка в матрице (5.4), отличный от нуля. Например: = 36 ≠ 0

2. Находим опорное допустимое решение. Для этого определим количество базисных и свободных переменных. Число базисных переменных равно рангу системы, т.е. трем. Тогда число свободных переменных 5-3 = 2. При выборе базисных неизвестных необходимо следить, чтобы определитель, составленный из коэффициентов при этих неизвестных, был отличен от нуля. Если этот определитель равен нулю, то выразить выбранные базисные переменные через свободные невозможно.

Примем за свободные переменные х₁ и х₅ и выразим остальные неизвестные через свободные

(5.6)

Теперь при равенстве нулю свободных переменных х₁ = 0, х₅ = 0 базисные окажутся равными: х₂ = 5, х₃ = –, х₄ = 25. Данное решение является недопустимым, так как не выполняется условие х_j ≥ 0 (ј = 1,2,3,4,5): х₃ <0.

Полученное решение (5.6), тем не менее, полезно использовать для нахождения допустимого решения. Для этого переведем одну из свободных переменных х₁ или х₅ в базис. Учитывая соотношение х_j ≥ 0, из уравнений (5.6) можно записать для переменной х₅ (оставляя х₁ = 0) следующие неравенства:

––

(5.7)

В стандартной процедуре однократного замещения принято выбранную свободную переменную увеличивать до максимально возможного значения. Тогда х₅ = – 9. При этом х₃ = 0 и переходит из базисных переменных в свободные. Но полученное новое базисное решение не является допустимым, т.к. х₅ < 0 и требует дальнейшего изменения набора свободных переменных.

Вместо этого, можно попытаться сразу перевести в базисные переменные х₁ , а не х₅ . Аналогичные рассмотренным рассуждения для свободной переменной х₁ (оставляя х₅ = 0), дают:

.

Эти неравенства одновременно выполняются в интервале

. Максимальное значение х₁ = 4. При этом х₄ =0 и переходит из базисных в свободные переменные. Теперь х₄ и х₅ являются свободными переменными, а остальные базисными.

Выразим базисные переменные через новый набор свободных. Из третьего уравнения системы (5.6) найдем выражение для х₁ через х₄ и х₅, и подставим найденное выражение в первое и второе уравнение системы (5.6).

(5.8) Целевую функцию (5.1) также выразим через свободные переменные

(5.9)

Итак, опорное допустимое решение имеет вид

, а целевая функция

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

Из выражения (5.9) видно, что целевая функция возрастает при увеличении любой из свободных переменных, так как коэффициенты перед этими переменными положительны. Допустим, что будем увеличивать х₄ (оставляя х₅ = 0), чтобы выполнялись условия х_i ≥ 0. Из первого уравнения системы (5.8) имеем

х₄ ≤ 25. Второе уравнение никаких ограничений на возрастание х₄ не накладывает. Из третьего уравнения системы (5.8) имеем х₄ ≤ 7. Следовательно, х₄ можно увеличивать только до 7. При этом х₅ становится равным нулю и переходит в число свободных переменных.

Итак, в качестве свободных переменных выбраны х₃ и х₅ .

Выразим через эти переменные х₁, х₂, х₄ и целевую функцию.

(5.10)

(5.11)

Так как в целевую функцию обе свободные переменные входят с отрицательными коэффициентами, то наибольшее значение Z достигается при х₃ = х₅ = 0. Это означает, что решение является оптимальным и Z _max = 16.

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

1. ЗЛП формулируется в виде задачи на максимум в канонической форме.

(5.12)

(5.13)

(.5.14)

В первой строке первой симплекс-таблицы записываются коэффициенты целевой функции (f- строка). В остальные строки –коэффициенты уравнений (5.13) так, чтобы их свободные члены были неотрицательны Смотрите табл. 5.1.

2. Производится разбиение переменных на свободные и базисные. Отыскивается неотрицательное базисное решение (Н.Б.Р.).

Количество базисных переменных равно r-рангу системы ограничений (5.13). Все эти переменные должны быть выражены через остальные, которые называются свободными. Решение системы (5.13), в котором свободные переменные равны нулю, называется базисным. Если при этом все базисные переменные неотрицательны, то такое решение является допустимым и совпадает с одной из вершин многогранника допустимых решений. Задача этого этапа – найти неотрицательное базисное решение (НБР). Для получения НБР следует придерживаться следующих правил (на этом этапе f – cтрока не принимается во внимание):

2.1) просматриваются все строки симплекс- таблицы, соответствующие уравнениям (5.13) (при условии : если в какой-то строке нет положительных элементов, а свободный член b_i > 0 , то система (5.13) не имеет НБР и процесс решения на этом заканчивается;

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

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

если в выбранном столбце несколько положительных элементов a_{i j} > 0, то для каждого из них находят симплекс-отношение , т.е. отношение свободного члена строки с элементом , к самому элементы . За разрешающий элемент выбирают тот элемент столбца, для которого симплекс -отношение будет наименьшим (если таковых несколько, берут любой из них);

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

Выполнив в эту процедуру достаточное число раз, получим НБР системы (5.13) и выражение целевой функции через свободные переменные.

3. Исследуется найденное НБР на оптимальность:

3.1) если в f-строке симплекс-таблицы нет отрицательных чисел (кроме, быть может, последнего столбца - ), то решение оптимально;

3.2) если в f-строке хотя бы один элемент (коэффициент при свободной переменной ) отрицателен, и в соответствующим ему столбце нет положительных чисел, то целевая функция f неограничена. Задача не имеет решения;

3.3) если же в каждом столбце с есть положительные числа, то переходят к новому опорному плану, более близкому к оптимальному. За разрешающий выбирают столбец с наибольшим по абсолютной величине отрицательным элементом в f-строке. Определяют по минимальному симплексному отношению (см. п. 2.2) разрешающую строку и на пересечении разрешающих строки и столбца отмечают разрешающий элемент. Далее зануляют все остальные элементы разрешающего столбца (см. п. 2.3).

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

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

Задача 5.1. Решить задачу 4.1 симплекс-методом.

Запишем задачу 4.1 в канонической форме, вводя 4 дополнительных неотрицательных переменных :

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

x₁+3x₂+х₃=18, х₂+х₅=5

2х₁+х₂+х₄=16, х₁+х₆=7, где , i = 1,2,…6.

↓

№	f	x1	x2		x3		x4	x5	x6		b	Комментарии к решению: Прежде всего, приведем Координаты вершин О,А,.В,С многоугольника решений, которые нам понадобятся ниже: О(0,0),А(0,5),В(3,5), С(6,4). Далее, представим целевую функцию ƒ= 2х1+3х2 в виде: ƒ- 2х1 --3х2 =0 и запишем первоначальную симплекс-таблицу. Из нее видим, что введенные дополнительные переменные:х3,х4,х5,х6 можно принять за базисные, тогда переменные х1,х2 будут свободными. Из нее также видим начальный опорный план (НБР)=(0,0,18,16,5,7), причем f()= 0 .
f-строка 0	1	-2	-3		0		0	0	0		0
	0	1	3		1		0	0	0		18
	0	2	1		0		1	0	0		16
	0	0	1		0		0	1	0		5
	0	1	0		0		0	0	1		7
↓
f-строка 1	1	-2	0		0		0	3	0		15
	0	1	0		1		0	-3	0		3
	0	2	0		0		1	-1	0		11
	0	0	1		0		0	1	0		5
	0	1	0		0		0	0	1		7
↓
f-строка 2	1	0	0		2		0	-3	0		21
	0	1	0		1		0	-3	0		3
	0	0	0		-2		1	5	0		5
	0	0	1		0		0	1	0		5
	0	0	0		-1		0	3	1		4
f-строка 3 (начало)	5	0	0		4		3	0	0	120
	0	5	0		-1		3	0	0	30
	0	0	0		-2		1	5	0	5
	0	0	5		2		-1	0	0	20
	0	0	0		1		-3	0	5	5
f-стро-ка 3 (окончание)	1	0	0					0	0		24=fmax
	0	1	0	-				0	0		6
	0	0	0	-				1	0		1
	0	0	1			-		0	0		4
	0	0	0					0	1		1

Первый этап симплекс метода (отыскание начального НРБ) уже реализован. 2-ой этап симплекс-метода заключается в проверке найденного плана на оптимальность, и в случае его не оптимальности надо перейти, по приведенным выше правилам, от плана к другому плану более близкому к оптимальному и т.д. Так как в f-строке есть отрицательные элементы, то -- не оптимален. Наибольший по абсолютной величине отрицательный элемент f-строки есть "-3". По нему вертикальной стрелкой помечаем разрешающий столбец; далее по наименьшему симплексному отношению находим разрешающую строку. На пересечении разрешающего столбца и строки выделен жирным шрифтом разрешающий элемент. Теперь проведем процедуру однократного замещения (введем в базис переменную х₂ и выведем из базиса переменную х₅) Для этого к 1-ой строке ( f-строке) прибавим утроенную 4-ую; затем и 2-ой строки вычтем утроенную 4-ую; затем из 3-ей строки вычтем 4-ую. В результате получим вторую симплекс – таблицу. В ней НБР: =(0,5; 3,11; 0,7), . План неоптимален, ибо в f-строки есть один отрицательный элемент «-2». По нему определяем разрешающий столбец (помечен вертикальной стрелкой.) Далее, по наименьшему симплексному отношению находим разрешающую строку. На пересечении разрешающего столбца и строки выделен жирным шрифтом разрешающий элемент. Теперь проведем процедуру однократного замещения (введем в базис переменную х₁ , и выведем из базиса переменную х₃). Для этого к первой строке (f-строке) прибавим удвоенную 2-ую; из 3-ей строки вычтем удвоенную 2-ю; из 5-ой строки вычтем 2-ю. В результате получим 3-ю симплекс – таблицу. В ней НБР: = (3,5; 0,5; 0,4), .

Планх₂ не оптимален, ибо в f-строке есть один отрицательный элемент «-3». По нему определяем разрешающий столбец (помечен вертикальной стрелкой). Далее, по наименьшему симплексному отношению находим разрешающую строку На пересечении разрешающего столбца и строки выделим жирным шрифтом разрешающий элемент и проведем процедуру однократного замещения (введем в базис переменную х₅ и выведем из базиса переменную х₄). Для этого к упятеренной 1-ой строке (f-строке) прибавим утроенную 3-ю; затем к упятеренной 2-ой строке прибавим утроенную 3-ю; затем из упятеренной 4-ой строке вычтем 3-ю; наконец, из упятеренной 5-ой строки вычтем утроенную 3-ю. В результате получим 4-ю симплекс таблицу. В ее f-строке нет отрицательных элементов. План оптимален.

Однако, чтобы по симплекс-таблице прочитать оптимальное НБР и значение f_max , надо 4-ю симплекс-таблицу привести к завершенному виду т.е., чтобы единственный не нулевой элемент в 1-м столбце и во всех базисных столбцах был равен единице. Для этого, как видим, все строки 4-ой симплекс-таблицы нужно разделить на 5. В результате получаем пятую симплекс-таблицу, из которой находим НБР_опт::

^опт = (6,4; 0,0; 1,1), и .

Тем самым, при отыскании f_max симплекс-методом мы прошли последовательно по цепочке вершин многоугольника решений: О→А→В→С, каждый раз увеличивая значение целевой функции:

Задача 5.2

Решить симплекс-методом задачу Л.П

f=40х₁+36х₂→min, при ограничениях: 5х₁+3х₂-х₃=45, х₁+х₄=6, х₂+х₅=10,

где х₁≥0, х₂≥0, х₃≥0, х₄≥0, х₅≥0.

↓

№	Z	х1	x2	x3	x4	x5	b	Комментарии к решению
	1	40	36	0	0	0	0	Заменим нашу задачу минимизации на задачу максимизации функции z=-f=–40x1-36x2. Представив функцию z в виде Z+40x1+36x2=0, запишем первоначальную симплекс – таблицу 1. Из нее видим, что переменные: х3, х4 и х5 будут базисными, а переменные х1, х2 –свободными. Здесь базисным решением системы ограничений, очевидно, будет =(0,0,-45,6,10); но оно не является допустимым (не является НБР). Поэтому на 1-м этапе симплекс-метода надо найти первоначальный опорный план (НБР). Следуя правилам пункта 2.2, выберем в системе ограничений за разрешающей столбец
1	0 0 0	5 1 0	3 0 1	-1 0 0	0 1 0	0 0 1	45 6 10
↓
	1	0	36	0	-40	0	-240
2	0 0 0	0 1 0	3 0 1	-1 0 0	-5 1 0	0 0 1	15 6 10
	1	0	0	12	20	0	-420
3	0 0 0	0 1 0	3 0 0	-1 0 1	-5 1 5	0 0 3	15 6 15
	1	0	0	12	20	0	-420
4	0 0 0	0 1 0	1 0 0	-1/3 0 1/3	-5/3 1 5/3	0 0 1	5 6 5

– столбец коэффициентов при х₁, ибо в нем есть положительные коэффициенты. Он помечен вертикальной стрелкой (можно было взять и столбец коэффициентов при другой свободной переменной – х₂). Затем по наименьшему симплексному отношению находим разрешающую строку и на пересечении разрешающих столбца и строки выделяем разрешающий элемент. Далее производим процедуру однократного замещения, включая f-строку (вводим в базис х₁ и выводим из базиса х₄). Для этого к 1-й строке (f-строке) прибавим 3-ю предварительно умноженную на "-40"; затем из 2-й строки вычтем упятеренную 3-ю. В результате получили симплекс-таблицу 2. В ней базисным решением системы ограничений будет =(6,0,-15,0,10), но оно опять не является НБР. Поэтому процедуру поиска НБР продолжаем. Выберем в качестве разрешающего столбца – столбец при х₂, ибо в нем есть положительные коэффициенты (он помечен вертикальной стрелкой); затем по наименьшему симплексному отношению находим разрешающую строку. На пересечении выбранного столбца и строки выделяем разрешающий элемент и опять производим процедуру однократного замещения, включая f-строку (т.е. вводим в базис х₂ и выводим из базиса х₃). Для этого умножим вторую строку на "-12" и прибавим к 1-й строке (f-строке); затем из утроенной 4-ой строки вычтем 2-ю.

В результате получим симплекс – таблицу 3, которая содержит НБР. Однако для его прочтения целесообразно перейти к симплекс- таблице 4 (она получается из таблицы 3 делением на 3 ее 2-ой и 4-ой строки). В результате получаем начальный опорный план (НБР) =(6,5,0,0,5). Но так как в f-строке все коэффициенты неотрицательные, то найденное НБР будет одновременно и оптимальным. Следовательно Z_max = Z(6;5)= –420, а потому f_min= –Z_max =420.