Симплекс-метод, его сущность

Содержание.

Введение……………………………………………………………………………………….с.5.

1. Теоретическая часть.

Глава 1. Простой симплекс-метод.

1.1 Обоснование и описание вычислительной процедуры. Приведение задачи линейного программирования к стандартной форме……………………………с.7

1.2 Симплексный метод решения задач……………………………………..…...с.8.

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

1.4 Решение задачи оптимизации. Построение аналитической модели……...с.12.

1.5 Приведение задачи к стандартной форме. Определение начального допустимого решения…………………………….……………………………...с.14.

Глава 2. Двухэтапный метод.

2.1 Искусственное начальное решение…………………………………………с.16.

2.2 Алгоритм двухэтапного метода……………………………………………..с.19.

Глава 3. Особые случаи симплекс-метода……………………………………………...23.

3.1 Вырожденность……………………………………………………………....с.24.

3.2 Альтернативные оптимальные решения…………………………………....с.27.

3.3 Неограниченные решения…………………………………………………...с.30.

3.4 Отсутствие допустимых решений…………………………………………..с.32.

2. Практическая часть.

2.1 Постановка задачи…………..……………………………………………………..с.34.

2.2 Решение…..…………………………………………………………………………с.36.

Заключение…………………………………………………………………………………...с.39.

Литература…………………………………………………………………………………....с.40.

Введение.

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

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

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

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

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

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

· количество продукции - расход сырья

· количество продукции - качество продукции

Выбор компромиcного варианта для указанных свойств и представляет собой процедуру решения оптимизационной задачи.

При постановке задачи оптимизации необходимо:

1. Наличие объекта оптимизации и цели оптимизации. При этом формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины, т.е. одновременно системе не должно приписываться два и более критериев оптимизации, т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого. Приведем примеры.

Типичный пример неправильной постановки задачи оптимизации:

«Получить максимальную производительность при минимальной себестоимости».

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

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

а) получить максимальную производительность при заданной себестоимости;

б) получить минимальную себестоимость при заданной производительности;

В первом случае критерий оптимизации - производительность а во втором - себестоимость.

2. Наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта.

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

4. Учёт ограничений.

1. Теоретическая часть.

Глава 1. Простой симплекс-метод.

1.1 Обоснование и описание вычислительной процедуры.
Приведение задачи линейного программирования к стандартной форме.

Любая задача линейного программирования приводится к стандартной (канонической) форме основной задачи линейного программирования, которая формулируется следующим образом: найти неотрицательные значения переменных X1 , X2 , Xn , удовлетворяющих ограничениям в виде равенств:

A11X1 + A12X2 + … + A1nXn = B1;

A21X1 + A22X2 + … + A2nXn = B2;

……………………………………

Am1X1 + Am2X2 + … + AmnXn = Bm;

Xj ≥ 0, j=1,…,n

и обращающих в максимум линейную функцию этих переменных:

E = C1X1 + C2X2 + … + CnXn Þ max

При этом также требуется, чтобы правые части равенств были неотрицательны, т.е. должны соблюдаться условия:

Bj ≥ 0, j=1,…,n

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

- перейти от минимизации целевой функции к ее максимизации;

- изменить знаки правых частей ограничений;

- перейти от ограничений-неравенств к равенствам;

- избавиться от переменных, не имеющих ограничений на знак.

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

1.2 Симплексный метод решения задач.

Симплексный метод задач линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет оптимальный план, и каждый ее опорный план является невырожденным). Указанный переход возможен, если известен какой-нибудь исходный опорный план. Рассмотрим задачу, для которой этот план можно непосредственно записать.

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

ѓ = C0 + C1x1 + C2x2 +...+ Cnxn

и система m линейных уравнений с n неизвестными. Это называется системой ограничений:

a11x1 + a12x2 +...+ a1nxn = b1

a21x1 + a12x2 +...+ a2nxn = b2

...

am1x1 +am2x12 +...+ amnxn = bm

Целевую функцию представим в виде:

ѓ - C1x1-C2x2 -...-Cnxn = C0

Составим симплекс-таблицу. В дальнейшем будем считать, что ранг матрицы системы ограничений равен r.В системе ограничений выбран базис (основные неизвестные)x1,x2,...xn и коэффициенты в правой части не отрицательны.

В этом случае система ограничений будет иметь вид:

x1 +...+ a1,r+1xr+1 +...+ a1nxn = b1

x2 + a2,r+1xr+1 +...+ a2nxn = b2

...

xr+ ar,r+1xr+1 +...+ arnxn = br

Тогда целевая функция имеет вид:

ѓ + Cr+1xr+1 + Cr+2xr+2 -...- Cnxn = C0

Нахождение оптимального плана симплексным методом включает следующие этапы:

1. Находят опорный план.

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

Базисные неизвестные	Свободные члены	x1	x2	xr	xr+1	xj	xn
x1 x2 xi xr	b1 b2 bi br	1 0 0 0	0 1 0 0	0 0 0 1	a1,r+1 a2,r+1 ai,r+1 ar,r+1	a1j a2j aij arj	a1n a2n ain arn
ѓ	C0	0	0	0	Cr+2	Cj	Cn

3. В нижней строчке симплекс-таблицы необходимо отыскать отрицательные числа (не считая коэффициент Со). Если таких чисел нет, то данное базисное решение является оптимальным.

4. Пусть элемент Сj<0,тогда в j-ом столбце необходимо найти положительный элемент. Если все коэффициенты этого столбца отрицательные, то решения не существует.

5. Если положительный коэффициент в j-ом столбце один, то выбранную строку с номером i надо поделить все коэффициенты на число aij.Результат деления записываем в новую симплекс-таблицу. Если же положительных коэффициентов несколько, необходимо составить отношение bi/aij и из полученных значений выбрать наименьшее, соответствующее i-ой строке.

6. В новой симплекс-таблице в столбце базисных неизвестных вместо xi пишется xj. Продолжается заполняться таблица. В столбце с номером j необходимо получить нули(включая строку с целевой функцией). Для этого надо умножить i-ую записанную строку на нужное число и сложить с остальными строками.

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

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

Пусть система приведена к каноническому виду.

X1+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

X2+q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

X3+q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

………………………………………………………

Xm+ qm,m+1 Xm+1 + …. + qm,m+n Xm+n =hm

В ней m базисных переменных, k свободных переменных. m+k=n - всего переменных.

Fmin= C1X1+ C2X2+ C3X3+....+ CnXn

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

Таблица 1.Симплекс таблица

C	Б	H	C1	C2	…	Cm	Cm+1	…	Cm+k
X1	X2	…	Xm	Xm+1	…	Xm+k
C1 C2 C3 : : Cm	X1 X2 X3 : : Xm	h1 h2 h3 : : Hm	1 0 0 : : 0	0 1 0 : : 0	: : : : : :	0 0 0 : : 0	q1,m+1 q2,m+1 q3,m+1 : : qm,m+1	: : : : : :	q1,m+k q2,m+k q3,m+k : : qm,m+k
F0	F1	F2	…	Cm	Cm+1	…	Cm+k

Первый столбец - коэффициенты в целевой функции при базисных переменных.

Второй столбец - базисные переменные.

Третий столбец - свободные члены (hi00).

Самая верхняя строка - коэффициенты при целевой функции.

Вторая верхняя строка - сами переменные, входящие в целевую функцию и в систему ограничений.

Основное поле симплекс метода - система коэффициентов из уравнения.

Последняя строка - служит для того, чтобы ответить на вопрос: «оптимален план или нет».

Индексная строка позволяет нам судить об оптимальности плана:

При отыскании Fmin в индексной строке должны быть отрицательные и нулевые оценки.

При отыскании Fmax в индексной строке должны быть нулевые и положительные оценки.

Переход ко второй итерации:

Для этого отыскиваем ключевой (главный) столбец и ключевую (главную) строку.

Ключевым столбцом является тот в котором находится наибольший положительный элемент индексной строки при отыскании Fmin или наименьший отрицательный элемент при отыскании Fmax.

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

На пересечении строки и столбца находится разрешающий элемент.

На этом этапе осуществляется к переходу к последующим итерациям.

Переход к итерациям:

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

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

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

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

Остальные элементы переносятся по формуле:

1.4 Решение задачи оптимизации. Построение аналитической модели.

В цехе имеется токарный станок и станок-автомат. Цех выпускает детали 1,2 и 3 в комплекте: на каждую деталь 1 – по 2 детали 2 и 3. Часовая производительность станков по каждой из деталей приведена в таблице:

Таблица 1. Часовая производительность станков

Станки	Детали
	1	2	3
1.Токарный	5	5	10
2. Автомат	15	15	10

Составить программу работы станков, при которой в течение смены (8 часов) будет выпускаться максимальное количество комплектов деталей.

Составим аналитическую модель задачи. Для этого сначала введем переменные, которые требуется определить:

X1 – время, которое работал токарный станок над деталями типа 1 в течение рабочей смены;

X2 – время, которое работал токарный станок над деталями типа 2 в течение рабочей смены;

X3 – время, которое работал токарный станок над деталями типа 3 в течение рабочей смены;

X4 – время, которое работал станок-автомат над деталями типа 1 в течение рабочей смены;

X5 – время, которое работал станок-автомат над деталями типа 2 в течение рабочей смены;

X6 – время, которое работал станок-автомат над деталями типа 3 в течение рабочей смены.

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

Ограничение времени работы токарного станка:

X1 + X2 + X3 £ 8;

Ограничение времени работы станка-автомата:

X4 + X5 + X6 £ 8.

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

5X1 + 15X4 - будет произведено за смену деталей типа 1;

5X2 + 15X5 - будет произведено за смену деталей типа 2;

10X3 + 10X6 - будет произведено за смену деталей типа 3.

Теперь введем сами ограничения:

2(5X1 + 15X4) = 5X2 + 15X5;

2(5X1 + 15X4) = 10X3 + 10X6.

Очевидно, что все переменные в задаче неотрицательные (объем продукции не может быть отрицательным):

X1 , X2 , X3 , X4 , X5 , X6 ≥ 0.

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

E= (5X1 + 15X4 + 5X2 + 15X5 + 10X3 + 10X6)/5 Þ max

или, если упростить это выражение, то получим:

E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 Þmax

Целевую функцию надо максимизировать.

Таким образом, формальная постановка задачи оптимизации имеет следующий вид:

X1 + X2 + X3 £ 8;

X4 + X5 + X6 £ 8;

2(5X1 + 15X4) = 5X2 + 15X5;

2(5X1 + 15X4) = 10X1 + 10X6;

X1 , X2 , X3 , X4 , X5 , X6 ≥ 0.

E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 Þmax

1.5 Приведение задачи к стандартной форме. Определение начального допустимого решения.

Для приведения данной задачи к стандартной форме необходимо лишь перейти от ограничений – неравенств к равенствам. Для этого введем дополнительные балансовые неотрицательные переменные. Также для упрощения дальнейших вычислений разделим обе части ограничений на комплектацию деталей на 5:

X1 + X2 + X3 + X7 = 8;

X4 + X5 + X6 + X8 = 8;

2X1 – X2 + 6X4 – 3X5 = 0;

2X1 – 2X3 + 6X4 – 2X6 =0;

X1 , X2 , X3 , X4 , X5 , X6 , X7 , X8 ≥ 0.

E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 Þmax

где Х7 , Х8 – остаточные переменные.

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

Для задачи, представленной в стандартной форме, количество переменных обычно больше, чем количество ограничений. Поэтому для нахождения начального решения задачи требуется выразить m переменных (т.е. количество переменных, равное количеству уравнений) через остальные n-m переменных, принять эти n-m переменных равными нулю и, таким образом, найти значения m переменных (в заданной задаче m=4 и n=8). Переменные, значения которых принимаются равными нулю, называются небазисными, а остальные m переменных - базисными. Значения базисных переменных неотрицательны (некоторые из них могут оказаться равными нулю). Количество базисных переменных всегда равно количеству ограничений. Найденное таким образом решение называется начальным допустимым базисным решением. Оно соответствует всем ограничениям.

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

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

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

Для того, чтобы построить искусственный базис, необходимо в каждое уравнение стандартной формы, не содержащее базисных переменных (т.е. полученное из ограничения-равенства или "не меньше"), добавить по одной искусственной переменной. В нашем случае это:

2X1 – X2 + 6X4 – 3X5 + Х9 = 0;

2X1 – 2X3 + 6X4 – 2X6 + Х10 =0.

где Х9 и Х10 – искусственные переменные, не имеющие никакого физического смысла, причем Х9, Х10 ≥0.

После построения искусственного базиса, придав нулевые значения всем переменным, кроме базисных, получим начальный базис: Х7, Х8, Х9, Х10 . Всего в базисе имеется четыре переменные и их значения равны правым частям ограничений, т.е.:

Х7 = 8; Х8 = 8; Х9 = 0; Х10 = 0.

Теперь необходимо решить эту задачу, т.е. найти оптимальное допустимое решение. Для этого воспользуемся двухэтапным симплекс-методом.

Глава 2. Двухэтапный метод.

2.1 Искусственное начальное решение.

В простом симплексе при начальном допустимом базисном решении гарантировалось, что все последующие базисные решения, получаемые при выполнении симплекс-метода, также будут допустимыми. В задачах линейного программирования, где все ограничения являются неравенствами типа «<=» (с неотрицательной правой частью), дополнительные (остаточные) переменные позволяют сформировать начальное допустимое базисное решение в задачах ЛП, где есть ограничения в виде равенств или неравенств типа «>=» ?

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

Для объяснения двухэтапного метода объясним сначала концепцию М-метода.

Пусть задача ЛП записана в стандартной форме. Для любого равенства I, в котором не содержится дополнительная остаточная переменная, введём искусственную переменную Ri, которая далее войдёт в начальное базисное решение. Но поскольку эта переменная искусственна (другими словами, не имеет никакого «физического смысла» в данной задаче), необходимо сделать так, чтобы на последующих итерациях она обратилась в нуль. Для этого в выражение целевой функции вводят штраф.

Переменная Ri, с помощью достаточно большого положительного числа М, штрафуется путём ввода в целевую функцию выражения – MRi в случае максимизации целевой функции и выражения +MRi – в случае минимизации. Вследствие этого штрафа естественно предположить, что процесс оптимизации симплекс-метода приведёт к нулевому значению переменной Ri. Следующий пример проясняет детали этого метода.

Пример 3.4-1

Минимизировать z = 4x1 + x2

при выполнении условий

3x1 + x2 = 3,

4x1 + 3x2 >= 6,

x1 + 2x2 <= 4,

x1, x2 >= 0.

Стандартная форма этой задачи получается в результате добавления дополнительной (избыточной) переменной x3 во второе неравенство и дополнительной (остаточной) переменной x4 в третье неравенство. Эта задача в стандартной форме будет записана следующим образом.

Минимизировать z = 4x1 + x2

при выполнении условий

3x1 + x2 = 3,

4x1 + 3x2 – x3 = 6,

x1 + 2x2 + x4 = 4,

x1, x2, x3, x4 >= 0.

В полученной задаче первое и второе уравнения не имеют дополнительных (остаточных) переменных, которые можно ввести в базисное решение. Поэтому введём в эти уравнения искусственные переменные R1 и R2, а в целевую функцию добавим штраф MR1 + MR2. В результате получим следующую задачу ЛП.

Минимизировать z = 4x1 + x2 + MR1 + MR2

при выполнении условий

3x1 + x2 + R1 = 3,

4x1 + 3x2 – x3 + R2 = 6,

x1 + 2x2 + x4 = 4,

x1, x2, x3, x4, R1, R2 >= 0.

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

При использовании М-метода следует обратить внимание на следующие два обстоятельства.

1. Использование штрафа М может и не привести к исключению искусственной переменной в конечной симплекс-итерации. Если исходная задача линейного программирования не имеет допустимого решения (например, система ограничений несовместна), тогда в конечной симплекс-итерации, по крайней мере, одна искусственная переменная будет иметь положительное значение. Это «индикатор» того, что задача не имеет допустимого решения.

2. Теоретически применение М-метода требует, чтобы М → ∞. Однако с точки зрения компьютерных вычислений величина М должна быть конечной и, вместе с тем, достаточно большой
. Как понимать термин «достаточно большая» – это открытый вопрос. Величина М должна быть настолько большой, чтобы выполнить роль «штрафа», но не слишком большой, чтобы не уменьшить точность вычислений. На практике вы должны помнить о возможных ошибках машинного округления при выполнении выполнений, в которых совместно участвуют как большие, так и малые числа.

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

2.2 Алгоритм двухэтапного метода.

Пример 2.2-2 демонстрирует проблемы, которые могут возникнуть при М-методе вследствие ошибок округления. Двухэтапный метод полностью лишён тех недостатков, которые присущи М-методу. Как следует из названия этого метода, процесс решения задачи ЛП разбивается на два этапа. На первом этапе ведётся поиск начального допустимого базисного решения. Если такое решение найдено, то на втором этапе решается исходная задача.

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

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

Пример 2.2-3

К задаче из примера 2.2-3 применим двухэтапный метод.

Этап 1

Минимизировать r = R1 + R2

С ограничениями

3x1 + x2 + R1 = 3,

4x1 + 3x2 – x3 + R2 = 6,

x1 + 2x2 + x4 = 4,

x1, x2, x3, x4, R1, R2, >= 0.

Соответствующая таблица имеет следующий вид.

Базис	x1	x2	x3	R1	R2	x4	Решение
r	0	0	0	-1	-1	0	0
R1	3	1	0	1	0	0	3
R2	4	3	-1	0	1	0	6
x4	1	2	0	0	0	1	4

Как и в М-методе, сначала вычисляется новая r-строка.

Старая r-строка: (0 0 0 -1 -1 0 | 0)

+ 1 * R1-строка: (3 1 0 1 0 0 | 3)

+ 1 * R2-строка: (4 3 -1 0 1 0 | 6)

= Новая r-строка: (7 4 -1 0 0 0 | 9)

Новая строка

r + 7x1 + 4x2 – x3 + 0R1 + 0R2 + 0x4 = 9

используется для решения первого этапа, что приведёт к следующему оптимальному решению (проверьте!).

Базис	x1	x2	x3	R1	R2	x4	Решение
r	0	0	0	-1	-1	0	0
x1	1	0	1/5	3/5	-1/5	0	3/5
x2	0	1	-3/5	-4/5	3/5	0	6/5
x4	0	0	1	1	-1	1	1

Поскольку достигнут минимум r = 0, значит, на первом этапе получено допустимое базисное решение x1 = 3/5, x2 = 6/5 и x4 = 1. Искусственные переменные полностью выполнили свою «миссию», поэтому из последней таблицы можно удалить их столбцы. Переходим ко второму этапу.

Этап 2

<

br />

После удаления искусственных переменных исходная
задача будет записана следующим образом.

Минимизировать z = 4x1 + x2

с ограничениями

x1 + 1/5 x3 = 3/5,

x2 + 3/5 x3 = 6/5,

x3 + x4 = 1,

x1, x2, x3, x4 >= 0.

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

Базис	x1	x2	x3	x4	Решение
z	-4	-1	0	0	0
x1	1	0	1/5	0	3/5
x2	0	1	-3/5	0	6/5
x4	0	0	1	1	1

Поскольку базисные переменные x1 и x2 имеют ненулевые коэффициенты в z-строке, эту строку следует преобразовать.

Старая z-строка: (-4 -1 0 0 | 0)

+ 4 * x1-строка: (4 0 4/5 0 | 12/5)

+ 1 * x2-строка: (0 1 -3/5 0 | 6/5)

= Новая z-строка: (0 0 1/5 0 | 18/5)

Начальная таблица второго этапа примет следующий вид:

Базис	x1	x2	x3	x4	Решение
z	0	0	1/5	0	18/5
x1	1	0	1/5	0	3/5
x2	0	1	-3/5	0	6/5
x4	0	0	1	1	1

Так как решается задача минимизации, следует ввести переменную x3 в базис. Применение алгоритма симплекс-метода уже на следующей итерации приведёт к оптимальному решению (проверьте!).

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

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

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

Глава 3. Особые случаи симплекс-метода.

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

1. Вырожденность.

2. Альтернативные оптимальные решения.

3. Неограниченные решения.

4. Отсутствие допустимых решений.

При изучении этих случаев основное внимание мы уделим (1) теоретическому
обоснованию причин, приводящих к таким ситуациям, и (2) их практическим
интерпретациям применительно к реальным задачам.

3.1 Вырожденность.

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

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

Пример 3.1-1. (Вырожденное оптимальное решение)

Рассмотрим следующую задачу ЛП.

Максимизировать z = 3x1 + 9x2

При выполнении условий

X1 + 4x2 <= 8,

X1 + 2x2 <= 4,

X1, x2 >= 0.

Итерация	Базис	x1	x2	x3	x4	Решение
Начальная	z	-3	-9	0	0	0
Вводится x3	x3	1	4	1	0	8
Исключается x3	x4	1	2	0	1	4
Первая	z	-3/4	0	9/4	0	18
Вводится x1	x2	1/4	1	1/4	0	2
Исключается x4	x4	1/2	0	-1/2	1	0
Вторая	z	0	0	3/2	3/2	18
Оптимум	x2	0	1	1/2	-1/2	2
x1	1	0	-1	2	0

На начальной итерации в качестве исключаемой можно выбрать как переменную x3, так и x4. Если оставить в базисе переменную x4, на следующей итерации она примет значение 0 (как показано в таблице), т.е. получим вырожденное базисное решение. Оптимальное решение получается на следующей итерации.

Что же практически приводит к вырожденности решения? Рассмотрим рис. 3.4, графически представляющий решение этой задачи. Точка оптимума x1 = 0, x2 = 2 является пересечением трёх прямых. Поскольку данная задача двухмерна, эта точка переопределена (на плоскости для определения точки достаточно двух прямых), и, следовательно, одно из ограничений избыточно. На практике информация о том, что некоторые ресурсы недефицитны, может быть полезной при интерпретации результатов решения задачи. Эти сведения также могут помочь выявить неточности и ошибки в постановке исходной задачи. К сожалению, не существует способов определить избыточное ограничение непосредственно из данных симплекс-таблиц.

Рис. 3.1

С вычислительной и теоретической точек зрения вырожденность может привести к двум последствиям. Во-первых, в процессе вычислений может возникнуть зацикливание. Если в приведённой выше таблице сравнить первую и вторую итерации, то можно заметить, что значение целевой функции не изменилось (z = 18). Поэтому может возникнуть ситуация, когда при реализации симплекс-метода некоторая последовательность будет повторяться, не изменяя значения целевой функции и не приводя к завершению вычислительного процесса. Существуют методы, предотвращающие зацикливание, однако они значительно замедляют процесс вычислений. Поэтому в большинстве программ, реализующих симплекс-метод, отсутствуют специальные средства защиты от зацикливания, тем более, что вероятность зацикливания очень мала.

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

x1 = 0, x2 = 2, x3 = 0, x4 = 0, z = 18.

Можно ли, несмотря на то что оптимальное решение не достигнуто, остановить вычисления на первой итерации (когда впервые обнаруживается вырожденность)? Ответ отрицательный, так как решение может быть только временно
.

3.2. Альтернативные оптимальные решения.

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

Пример 3.2-1 (Бесконечное множество решений)

Рассмотрим следующую задачу ЛП.

Максимизировать z = 2x1 + 4x2

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

x1 + 2x2 <= 5,

x1 + x2 <= 4,

x1, x2 >= 0.

На рис. 3.2 показано множество альтернативных оптимальных решений, которые являются следствием того, что прямая, представляющая целевую функцию, параллельна прямой, соответствующей связывающему ограничению. Каждая точка отрезка
BC
соответствует оптимальному решению со значением целевой функции z = 10.

Рис. 3.2

Последовательные итерации выполнения симплекс-метода представлены в следующей таблице.

Итерация	Базис	x1	x2	x3	x4	Решение
Начальная	z	-2	-4	0	0	0
Вводится x2	x3	1	2	1	0	5
Исключается x3	x4	1	1	0	1	4
Первая	z	0	0	2	0	10
Вводится x1	x2	1/2	1	1/2	0	5/2
Исключается x4	x4	1/2	0	-1/2	1	3/2
Вторая	z	0	0	2	0	10
(Альтернативный	x2	0	1	1	-1	1
оптимум)	x1	1	0	-1	2	3

На первой итерации получаем оптимальное решение x1 = 5/2 и z = 10, которое соответствует точке B на рис. 3.2. Как узнать из симплекс-таблицы, что существует альтернативное оптимальное решение? Посмотрите на коэффициенты небазисных
переменных в z-строке первой итерации. Коэффициент небазисной переменной x1 равен нулю, это означает, что данную переменную можно ввести в базис без изменения значения целевой функции, но значение самой переменной x1 изменится. Введение переменной x1 в базисное решение выполнено на второй итерации, при этом из базиса исключена переменная x4. Получено новое решение x1 = 3, x2 = 1, z = 10, которое соответствует точке Cна рис. 3.2.

Симплекс-метод может определить только две угловые точки Bи C. Математически мы можем найти все точки (x1’,x2’) отрезка BCкак взвешенное среднее (с неотрицательными весами) точек B и C. Полагая 0 <= α <= 1 и

B: x1 = 0, x2 = 5/2,

C: x1 = 3, x2 = 1,

координаты любой точки отрезка BC можно записать следующим образом:

x1’ = α * 0 + (1 - α) * 3 = 3 – 3 α,

x2’ = α * 5/2 + (1 - α) * 1 = 1 – 3/2 α,

При α = 0 (x1’,x2’) = (3, 1), что соответствует точке C. При α = 1 получаем (x1’,x2’) = (0, 5/2) – это точка B. Если значение α лежит строго между 0 и 1, получаем внутренние точки отрезка BC.

На практике альтернативные оптимальные решения весьма полезны, поскольку позволяют сделать выбор среди множества решений без ухудшения значения целевой функции. Например, в рассмотренной выше задаче переменная x2, принимает нулевое значение в точке B, тогда как в других альтернативных оптимальных решениях её значение положительно. Если интерпретировать задачу как задачу организации производства двух видов товара (которые соответствуют переменным x1 и x2), то, с учётом конкуренции на рынке, более рационально производить оба вида товара, а не один. В этом случае решение, соответствующее точке C, предпочтительнее.

3.3 Неограниченные решения.

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

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

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

Пример 3.3–1. (Неограниченная целевая функция)

Рассмотрим задачу

Максимизировать z = 2x1 + x2

при выполнении условий

x1 – x2 <= 10,

2x1 <= 40,

x1, x2 >= 0.

Симплекс-таблица начальной итерации этой задачи имеет следующий вид.

Базис	x1	x2	x3	x4	Решение
z	-2	-1	0	0	0
x3	1	-1	1	0	10
x4	2	0	0	1	40

Из этой таблицы видно, что в качестве вводимой переменной можно взять как x1, так и x2. Поскольку переменная x1 имеет максимальный (по абсолютной величине) отрицательный коэффициент в z-строке, именно её следует ввести в базисное решение. Однако заметим, что во всех ограничениях
коэффициенты, стоящие перед переменной x2, отрицательны
или равны нулю
. Это означает, что значение переменной x2 может возрастать до бесконечности, и при этом не нарушается ни одно ограничение. Поскольку увеличение на 1 значения переменной x2 приводит к увеличению на 1 значения целевой функции, значит, неограниченное увеличение значения переменной x2 ведёт к неограниченному увеличению значения целевой функции. Эта ситуация проиллюстрирована на рис. 3.3. На этом рисунке видно, что пространство допустимых решений не ограничено в направлении оси x2 и значение целевой функции может быть каким угодно большим.

Рис. 3.3

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

3.4 Отсутствие допустимых решений.

Если ограничения задачи ЛП несовместны (т.е. они не могут выполняться одновременно), то задача не имеет допустимых решений. Такая ситуация не может возникнуть, если все
неравенства, составляющие систему ограничений, имеют тип «<=» с неотрицательными правыми частями, так как в этом случае дополнительные переменные могут составить допустимое решение. Для других типов ограничений мы используем искусственные переменные. И хотя в оптимальном решении все искусственные переменные в силу штрафов равны нулю, такой исход возможен только тогда, когда задача имеет непустое пространство допустимых решений. В противном случае, в оптимальном решении будет присутствовать хотя бы одна положительная
искусственная переменная.

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

Пример 3.4-1. (Отсутствие допустимых решений)

Рассмотрим следующую задачу.

Максимизировать z = 3x1 + 2x2

при выполнении условий

2x1 + x2 <= 2,

3x1 + 4x3 >= 12,

x1, x2 >= 0.

Результат применения симплекс-метода представлен в следующей таблице.

Итерация	Базис	x1	x2	x4	x3	R	Решение
Начальная	z	-3 -3M	-2 -4M	M	0	0	-12M
Вводится	x3	2	1	0	1	0	2
Исключается	R	3	4	-1	0	1	12
Первая	z	1 + 5M	0	M	2 + 4M	0	4 – 4M
(псевдооптимум)	x2	2	1	0	1	0	2
R	-5	0	1	-4	1	4

Данные из этой таблицы показывают, что в точке оптимума искусственная переменная Rимеет положительное значение (= 4), что свидетельствует об отсутствии допустимого решения. На рис. 3.4 графически представлена ситуация данной задачи. Алгоритмы симплекс-метода, допуская положительные значения искусственной переменной, по существу, превращает неравенство 3x1 + 4x3 >= 12 в 3x1 + 4x3 <= 12. (Объясните, почему так происходит.) В результате получаем то, что можно назвать псевдооптимальным решением
.

Рис. 3.4

2. Практическая часть.

Постановка задачи.

Решить задачи:

F = 14x1 + 10x2 + 14x3 + 14x4→ max

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

4x1 + 2x2 + 2x3 + x4 <= 35;

x1 + x2 + 2x3 + 3x4 <= 30;

3x1 + x2 + 2x3 + x4 <= 40;

xj >= 0, j = 1, 2, 3, 4.

F = x1 + x2→ max

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

x1 – 4x2 – 4 <= 0;

3x1 – x2 >= 0;

x1 + x2 – 4 >= 0;

x1 >= 0, x2 >= 0.

Решение.

1. F = 14x1 + 10x2 + 14x3 + 14x4→ max

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

4x1 + 2x2 + 2x3 + x4 <= 35;

x1 + x2 + 2x3 + 3x4 <= 30;

3x1 + x2 + 2x3 + x4 <= 40;

xj >= 0, j = 1, 2, 3, 4.

Переведём систему в канонический вид для решения симплексным методом.

4x1 + 2x2 + 2x3 + x4 + x5 = 35;

x1 + x2 + 2x3 + 3x4 + x6 = 30;

3x1 + x2 + 2x3 + x4 + x7= 40;

xj >= 0, j = 1, 2, 3, 4, 5, 6, 7.

14x1 + 10x2 + 14x3 + 14x4 + 0x5 + 0x6 + 0x7 → max

Ответ: maxz= 225 при x2 = 5, x3 = 12,5, x7 = 10, x1 = x4 = x5 = x6 = 0.

Двухэтапный метод.

2. F = x1 + x2→ max

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

x1 – 4x2 – 4 <= 0;

3x1 – x2 >= 0;

x1 + x2 – 4 >= 0;

x1, x2 >= 0.

Переведём в канонический вид и добавим искусственные переменные.

f = x1 + x2 + 0x3 + 0x4 + 0x5 – Mx0 – Mx7 → max.

x1 – 4x2 – 4 + x3 = 0;

3x1 – x2 – x4 + x6 = 0;

x1 + x2 – 4 – x5 + x7 = 0;

x1, x2, x3, x4, x5, x6, x7 >= 0;

Этап 1.

Z = x6 + x7 → min

Базис	x1	x2	x3	x4	x5	x6	x7	Решение
x3	1	-4	1	0	0	0	0	4
x6	3	-1	0	-1	0	1	0	0
x7	1	1	0	0	-1	0	1	4
z - c	0	0	0	0	0	-1	-1	0

Так как базисные переменные x6 и x7 имеют ненулевые коэффициенты в (z - c) – строке, эту строку следует преобразовать:

(z- c): 0 0 0 0 0 -1 -1 0

+

1 * x6: 3 -1 0 -1 0 1 0 0

+

1 * x7: 1 1 0 0 -1 0 1 4

= (z- c): 4 0 0 -1 -1 0 0 4

Базис	x1	x2	x3	x4	x5	x6	x7	Решение	Отношение
x3	1	-4	1	0	0	0	0	4	4
x6	3	-1	0	-1	0	1	0	0	0 ←
x7	1	1	0	0	-1	0	1	4	4
(z - c)’	4	0	0	-1	-1	0	0	4

↑

Базис	x1	x2	x3	x4	x5	x6	x7	Решение	Отношение
x3	0	-3 и 2/3	1	1/3	0	-1/3	0	4
x1	1	-1/3	0	-1/3	0	1/3	0	0
x2	0	1 и 1/3	0	1/3	1	-1/3	1	4	3 ←
(z - c)’	0	4/3	0	1/3	-1	-4/3	0	4

↑

Базис	x1	x2	x3	x4	x5	x6	x7	Решение	Отношение
x3	0	0	1	5/4	11/4	-5/4	11/4	4
x1	1	0	0	-1/4	1/4	1/4	1/4	0
x2	0	1	0	1/4	3/4	-1/4	3/4	4
(z - c)’	0	0	0	0	-2	-5/3	-1	4

Так как достигнуто min (z - c)’ = 0, то получено допустимое базисное решение для второго этапа: x1 = 1, x2 = 3, x3 = 15. Искусственные переменные могут быть исключены.

Этап 2.

Перепишем исходную задачу с учётом полученного базисного решения:

f = x1 + x2 + 0x3 + 0x4 + 0x9→ max

x3 + 5/4 x4 + 11/4 x5 = 15;

x1 – 1/4 x4 + 1/4 x5 = 1;

x2 + 1/4 x4 + 3/4 x5 = 3;

x1, x2, x3, x4, x5 >= 0.

Базис	x1	x2	x3	x4	x5	Решение
x1	1	0	0	1/4	1/4	1
x2	0	1	0	1/4	3/4	3
x3	0	0	1	5/4	11/4	15
(f - c)	1	-1	0	0	0	0

Согласуем значения в строке (f - c) с остальной частью таблицы:

(f - c): -1 -1 0 0 0 0

+

1 * x1: 1 0 0 -1/4 1/4 1

+

1 * x2: 0 1 0 1/4 3/4 3

= (f-c)’: 0 0 0 0 1 4

Исходное решение является оптимальным.

Ответ: max (f) = 4 при x1 = 1, x2 = 3, x3 = 15, x4 = 0, x5 = 0.

Так как небазисные переменные равны нулю, задача имет множество альтернативных оптимальных решений, находящихся н отрезке AB (x1+ x2 = 4).

Заключение.

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

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

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

Литература.

1. Ашманов С.А. Линейное программирование. – М.: Наука, 1981.

2. Гасс С. Линейное программирование. – М.: Физматгиз, 1961.

3. Гольштейн Е.Г., Юдин Д.Б. Линейное программирование: Теория, методы и приложения. – М.: Наука, 1969.

4. Таха, Хэмди, А. Введение в исследование операций. 6-е издание. : Пер. с англ. — М.: Издательский дом "Вильяме", 2001. — 912 с. : ил. — Парал. тит. англ.

5. Н.Ш. Кремер, Б А Путко, И.М. Тришин, М.Н. Фрид­ман; Под ред. проф. Н.Ш. Кремера. Исследование операций в экономике: Учеб. пособие для И87 вузов —М: ЮНИТИ, 2002.— 407 с.