Курская академия государственной и муниципальной службы

Кафедра «информационной и техносферной безопасности»

Реферат

по дисциплине «Методы оптимальных решений»

на тему «Идея симплекс-метода»

Выполнила: студентка 2 курса

Специальности «экономика»

Москалева О. С.

Проверил: к.ф.м.н., доцент Погосян С. Л.

Курск – 2012

Введение……………………………………………………………………..3

1. Идея симплекс-метода…………………………………………….…4

2. Реализация симплекс-метода на примере……………………..……6

3. Табличная реализация простого симплекс-метода ……………….10

Заключение………………………………………………………………….15

Список использованной литературы………………………………..…….16

Введение.

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

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

Идея симплекс-метода

Рассмотрим универсальный метод решения канонической задачи линейного программирования, с n переменными и m ограничениями-равенствами, известный как симплекс-метод.

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

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

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

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

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

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

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

шаг 1 . Проверка текущего базисного плана на оптимальность. Если критерий оптимальности выполнен, то план оптимален и решение закончено. Иначе переход на шаг 2.

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

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

шаг 4 . Нахождение координат нового базисного плана (смежной угловой точки). Переход на шаг 1.

Повторяющиеся шаги 1-4 образуют одну итерацию симплекс-метода.

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

Определение . Будем говорить, что каноническая задача ЛП имеет "предпочтительный вид", если: правые части уравнений; матрица условий содержит единичную подматрицу размера.

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

Реализация симплекс-метода на примере

Продемонстрируем применение симплекс-метода на примере. Рассмотрим каноническую задачу ЛП

f(x) = x 1 + 2x 2 + 0 x 3 + 0 x 4 > max
-x 1 + 2x 2 + x 3 = 4,
3 x 1 + 2x 2 + x 4 = 12,
x j ? 0, j = 1,2,3,4.

Матрица условий A = (A 1 , A 2 , A 3 , A 4), где

Целевой вектор c =(c 1 , c 2 , c 3 , c 4 ) = (1, 2, 0, 0); вектор правых частей b =(b 1 , b 2) = (4, 12).

Шаг 0. Нахождение начальной угловой точки (базисного плана).

Задача имеет предпочтительный вид, так как правые части уравнений положительны, а столбцы матрицы условий A 3, A 4 образуют единичную подматрицу. Значит начальная базисная матрица = (A 3 , A 4); x 3 и x 4 - базисные переменные, x 1 и x 2 - небазисные переменные, c Б = (c 3, c 4) = = (0, 0).

Начальный базисный план имеет вид x 0 = (0, 0, x 3 , x 4) = (0, 0, 4, 12); f(x o ) = 0.

Шаг 1. Проверка базисного плана на оптимальность.

Подсчитаем симплексные оценки для небазисных переменных по формуле (5.1)

? 1 = 1 > - c 1 = 0 ·(-1) + 0 ·3 - 1 = -1.

? 2 = 2 > - c 2 = 0 ·2 + 0 · 2 - 2 = -2.

Так как оценки отрицательны, то план x - не оптимален. Будем искать новый базисный план (смежную угловую точку) с большим значением целевой функции.

Шаг 2 . Нахождение переменной вводимой в базис.

Целевую функцию можно увеличить, если ввести в состав базисных переменных (сделать положительной) одну из небазисных переменных x 1 или x 2 , поскольку обе оценки ? j x 2.

Шаг 3. Определение переменной выводимой из базиса.

После ввода в базис переменной x 2 новый план будет иметь вид

x" = (0, x 2, x 3 , x 4).

Этот план не является базисным, так как он содержит только одну нулевую координату, значит надо сделать нулевой (исключить из базиса) одну из переменных x 3 или x 4 . Подставим координаты плана x" = (0, x 2, x 3 , x 4) в ограничения задачи. Получим

2x 2 + x 3 = 4,

2x 2 + x 4 = 12.

Выразим отсюда базисные переменные x 3 и x 4 через переменную x 2 , вводимую в базис.

x 3 = 4 - 2x 2,
x 4 = 12 - 2x 2 .

Так переменные x 3 и x 4 должны быть неотрицательны, получим систему неравенств

4 - 2x 2 ? 0,
12 - 2x 2 ? 0.

Чем больше значение x 2 , тем больше возрастает целевая функция. Найдем максимальное значение новой базисной переменной, не нарушающее ограничения задачи, то есть удовлетворяющее условиям (2.8), (2.9).

Перепишем последние неравенства в виде

2x 2 ? 4,

2x 2 ? 12,

откуда максимальное значение x 2 = min { 4/2, 12/2 } = 2. Подставляя это значение в выражения (2.6), (2.7) для x 3 и x 4 , получаем x 3 = 0. Следовательно x 3 выводится из базиса.

Шаг 4. Определение координат нового базисного плана.

Новый базисный план (смежная угловая точка) имеет вид

x" = (0, x 2, 0, x 4)

Базис этой точки состоит из столбцов A 2 и A 4 , так что = (A 2, A 4). Этот базис не является единичным, так как вектор A 2 = (2,2), и следовательно задача (2.2)-(2.5) не имеет предпочтительного вида относительно нового базиса. Преобразуем условия задачи (2.3), (2.4) таким образом, чтобы она приняла предпочтительный вид относительно новых базисных переменных x 2, x 4, то есть чтобы переменная x 2 входила в первое уравнение с коэффициентом, равным единице, и не присутствовала во втором уравнении. Перепишем уравнения задачи

- x 1 + 2 x 2 + x 3 = 4, (p 1)

3x 1 +2 x 2 + x 4 = 12. (p 2)

Поделим первое уравнение на коэффициент при x 2 . Получим новое уравнение = p 1 / 2, эквивалентное исходному

1/2 x 1 + x 2 + 1/2 x 3 = 2. ()

Используем это уравнение, которое назовем разрешающим, для исключения переменной x 2 из второго уравнения. Для этого надо уравнение умножить на 2 и вычесть из p 2 . Получим = p 2 - 2 = p 2 - p 1:

4 x 1 - x 3 + x 4 = 8. ()

В итоге получили новое "предпочтительное" представление исходной задачи относительно новых базисных переменных x 2 , x 4:

f (x ) = x 1 + 2 x 2 + 0 x 3 + 0 x 4 ? max

1/2 x 1 + x 2 + 1/2 x 3 = 2 ()

4 x 1 - x 3 + x 4 = 8 ()

x j ? 0, j = 1,2,3,4

Подставляя сюда представление нового базисного плана x 1 = (0, x 2, 0, x 4), сразу найдем его координаты, так как значения базисных переменных равны правым частям уравнений

x" = (0, 2, 0, 8); f (x 1)=4.

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

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

Табличная реализация простого симплекс-метода

Табличную реализацию продемонстрируем на том же примере (2.2)-(2.5).

Шаг 0 . Решение начинается с построения начальной симплекс-таблицы. Сначала заполняется правая часть таблицы с третьей колонки. В двух верхних строках записываются имена переменных задачи (x 1, ...,x 4) и коэффициенты целевой функции при этих переменных. Ниже записываются коэффициенты уравнений - элементы матрицы условий А , так что под переменной x 1 располагается столбец A 1 , под переменной x 2 - столбец A 2 и т.д. В правый столбец заносятся правые части ограничений (числа b i > 0).

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

Таблица 1 - Начальная симплекс-таблица

	Базисные переменные					Значения базисных перем. (x Б =b )
		x 1	x 2	x 3	x 4
	x 3	a 11 =-1
	x 4
Строка оценок ? j	? 1 = -1	? 2 = -2

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

x o = (0, 0, x 3 , x 4) = (0, 0, 4, 12).

Шаг 1. Для проверки плана x o на оптимальность подсчитаем симплексные оценки для небазисных переменных x 1 и x 2 по формуле

? j = Б , A j > - c j .

? 1 = Б , A 1 > - c 1 = 0 ·(-1) + 0 ·3 - 1 = -1.

При табличной реализации для подсчета оценки ? 1 надо найти сумму произведений элементов первого столбца (c Б ) на соответствующие элементы столбца A 1 при небазисной переменной x 1 . Аналогично подсчитывается оценка ? 2 , как скалярное произведение первого столбца (c Б ) на столбец при переменной x 2 .

? 2 = 2 > - c 2 = 0 ·2 + 0 · 2 - 2 = -2.

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

f (x )= c Б, x Б >,

перемножая скалярно первый и последний столбцы таблицы.

Так как среди оценок ? j есть отрицательные, то план x o - не оптимальный, и надо найти новый базисный план, заменив одну из базисных переменных на новую из числа небазисных.

Шаг 2. Поскольку обе оценки ? 1 и ? 2 то в базис можно включить любую из переменных x 1, x 2 . Введем в базис переменную с наибольшей по модулю отрицательной оценкой, то есть x 2 .

Столбец симплекс-таблицы, в котором находится вводимая в базис переменная называется ведущим столбцом .

В примере ведущим будет столбец при x 2 .

Шаг 3. Если в ведущем столбце все элементы отрицательны, то решения задачи не существует и max f (x ) ???. В примере все элементы ведущего столбца положительны, следовательно, можно найти максимальное значение x 2 , при котором одна из старых базисных переменных обратится в ноль. Напомним, что максимальное значение x 2 = min{4/2, 12/2}=2.

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

Наименьшее отношение находится в строке с базисной переменной x 3. Значит переменная x 3 исключается из состава базисных переменных (x 3 = 0).

Строка, содержащая переменную, исключаемую из базиса, называется ведущей строкой.

В примере ведущей строкой будет первая строка.

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

В нашем случае ведущий элемент a 12 = 2.

Табл. 2 - Начальная симплекс-таблица с ведущими строкой и столбцом

	Базисные перемен.					Значения базисных перем.	Уравнения
			x 2
c 3 =0	x 3	-1	2	1	0	4
			2
Строка оценок ? j	? 1 = -1	? 2 = -2

Шаг 4 . Для получения нового базисного плана приведем задачу к новому предпочтительному виду относительно новых базисных переменных.

Для этого построим новую симплекс-таблицу, во втором столбце которой вместо исключаемой переменной x 3 запишем новую базисную переменную x 2 , а в первом столбце (с Б ) вместо с 3 запишем коэффициент целевой функции при x 2 : c 2 =2 . В новой симплекс таблице столбец при x 2 должен стать единичным (ведущий элемент должен равняться единице, а все остальные элементы должны обратиться в ноль). Это достигается следующими преобразованиями строк таблицы.

a. Все элементы ведущей строки делим на ведущий элемент и записываем в той же строке новой симплекс- таблицы.

Полученную строку p 1 " назовем разрешающей.

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

p 2 " = p 2 + (- 2) p 1 " = p 2 - p 1.

c. Заполним последнюю строку, вычислив оценки ? j " = - - c j , где c Б ", A j " - соответствующие столбцы новой симплекс-таблицы, и значение целевой функции f(x)= .

Получим вторую симплекс-таблицу с новым базисом.

Таблица 3 - Результат первой итерации

	Базисные перемен.					Значения базисных перем.	Уравнения
		-1/2
	x 4	4	0	-1	1	8	p 2 " =p 2 - p 1
оценки ? j "	-2

Новый базисный план x " = (0, x 2 , 0, x 4) = (0, 2, 0, 8 ). Поскольку оценка ? 1 = -2 то план x " не оптимален. Для перехода к новому базисному плану (соседней угловой точки) проведем еще одну итерацию симплекс - метода.

Так как ? 1 то в базис вводится переменная x 1 . Первый столбец, содержащий x 1 - ведущий.

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

Выделяем ведущий столбец и ведущую строку и на их пересечении находим ведущий элемент (= 4) .

Строим новую (третью) симплекс-таблицу, заменяя в ней базисную переменную x 4 на x 1 , и снова преобразуя строки таблицы таким образом, чтобы ведущий элемент стал равным единице, а остальные элементы ведущего столбца обратились в ноль. Для этого ведущую (вторую) строку делим на 4, а к первой строке прибавляем полученную вторую строку, деленную на 2. Последнюю строку вычисляем по формулам для симплексных оценок ? j "" = "", A j "" > - c j , где c Б "", A j "" - соответствующие столбцы новой симплекс-таблицы. Значение целевой функции на новом базисном плане находим по формуле f(x "")= "", x Б "" >.

Таблица 4 - Результат второй итерации

	Базисн. перемен.					Значения базисных перем.	уравнения
							p 1 ""= p 1 "+p 2 ""/2
							p 2 "" = p 2 "/4
оценки ? j ""					f(x "")= 8

Новый базисный план x "" = (x 1 , x 2 , 0, 0) = (2, 3, 0, 0 ). Поскольку все оценки неотрицательны, то план x "" - оптимальный план.

Таким образом, x* = (2, 3, 0, 0 ), f(x*) = 8.

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

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

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

• Было показано, как с помощью конечного перебора базисных решений системы ограничений задачи, найти это оптимальное решение. Однако с ростом размерности n системы ограничений задачи объем вычислений решения задачи методом полного перебора базисных решений растет экспоненциально и становится непригодным на практике.

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

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

• Нужно найти точку этого многоугольника, в которой целевая функция принимает наименьшее значение.

• Пусть определено начальное допустимое базисное решение задачи, соответствующее угловой точке B.

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

• Однако из рисунка видно, что, учитывая направление градиента N, выгоднее перейти к соседней вершине C, затем к соседней вершине D, которой соответствует оптимальное базисное решение задачи.

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

• Идея последовательного улучшения решения и положена в основу универсального метода решения задач линейного программирования –симплекс–метода.

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

• Впервые симплекс–метод и его название были предложены американским математиком Джоном Данцигом в 1947 году, хотя идеи метода были опубликованы российским математиком Л.В. Канторовичем еще в 1939 году в статье «Математические методы организации и планирования производства».

Симплекс–метод состоит из трех основных элементов:

• определения некоторого первоначального допустимого базисного решения задачи;

• правила перехода к следующему не худшему допустимому базисному решению;

• проверки оптимальности найденного решения.

• Симплекс–метод применяется к задаче линейного программирования, записанной в канонической форме.

Симплексные преобразования системы линейных уравнений

• Рассмотрим ЗЛП в канонической форме. Пусть задана система линейных уравнений:

• Нужно найти неотрицательное решение этой системы, которое минимизирует линейную функцию

• Обозначим – матрицу системы уравнений (1),

• – расширенную матрицу этой системы.

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

• Для определенности предположим, что линейно независимыми являются первые r столбцов матрицы A, тогда систему (1) можно, применяя метод исключения Гаусса, преобразовать к виду:

• Эта система равносильна системе уравнений (1). Столбцы коэффициентов

• образуют базис системы столбцов матрицы системы (2) и поэтому переменные являются базисными, а набор – базисным набором.

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

Выразим в системе (3) базисные переменные через свободные, получим систему (4):

• (4)

• Принято говорить, что (4) – общее решение системы уравнений (1). Придавая свободным переменным нулевые значения, определим значения базисных переменных и построим базисное решение, соответствующее построенному базисному набору переменных.

• Итак, базисное решение системы (1).

• В дальнейшем будет показано, что, если система (1) имеет допустимые решения, то ее можно так преобразовать к виду (3), что будет выполняться условие (5)

• Поэтому мы будем считать, что условие (5) выполняется. Тогда базисное решение является допустимым базисным решением.

Используя равенства (4), можно функцию f выразить через свободные переменные: (6) Теперь можно вычислить значение функции f, соответствующее базисному решению

• Осуществляя идею симплекс–метода, научимся переходить от одного допустимого базисного решения к другому. Для этого одна из базисных переменных xi удаляется из базиса и заменяется некоторой свободной переменной xj .

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

• Получится уравнение:

• Подставив вместо xj его выражение из (7) в остальные уравнения системы (4) и в функцию (6), мы получим новую систему, равносильную системе (1), которая будет разрешена относительно нового базиса

Коэффициент aij, указывающий, что в базисе происходит замена xi на свободную переменную xj, называют разрешающим элементом симплекс-таблицы. Из равенства (7) следует, что

• Так как новое базисное решение должно быть допустимым (неотрицательным),

• то должно выполняться условие, а значит, . Иначе говоря, разрешающий элемент aij (xi – свободная переменная) в j–том столбце надо выбирать положительным. Описанное преобразование назовем симплексным, если разрешающий элемент aij выбирается по следующему правилу:

• 1. Элемент aij выберем из такого j – ого столбца, в котором есть положительные элементы.

• 2. Если в этом столбце есть несколько положительных элементов, то составим отношения свободных членов bk к коэффициентам akj>0.

• Из всех отношений выберем наименьшее. Пусть это будет :

• (8)

• Знаменатель этой дроби и выберем разрешающим элементом. Если несколько из этих отношений будут минимальными (равными), то выберем любой из этих знаменателей.

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

• Доказательство. Обозначим новые свободные члены после симплексного преобразования в (4) через

• Тогда при

• Если akj>0, то из (8) следует, что

• Если akj

• Если akj =0, то

• Следствие. С помощью симплексного преобразования можно перейти от одного допустимого базисного решения ЗЛП к другому допустимому базисному решению этой задачи.

Симплекс-метод

1. Идея симплекс-метода

Рассмотрим универсальный метод решения канонической задачи ЛП.

известный как симплекс-метод.

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

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

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

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

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

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

Общая схема симплекс-метода состоит из следующих основных шагов.

·0 шаг . Определение начального базиса и соответствующей ему начальной угловой точки (базисного плана) .

·1 шаг . Проверка текущего базисного плана на оптимальность. Если критерий оптимальности выполнен, то план оптимален и решение закончено. Иначе переход на шаг 2.

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

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

·4 шаг . Нахождение координат нового базисного плана (смежной угловой точки). Переход на шаг 1.

Повторяющиеся шаги 1-4 образуют одну итерацию симплекс-метода.

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

Определение . Будем говорить, что каноническая задача ЛП имеет «предпочтительный вид», если

1.правые части уравнений, .

Матрица условий содержит единичную подматрицу размера

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

Пример.

Матрица условий и вектор правых частей ограничений имеют вид

Сразу очевидна одна базисная матрица: с единичными векторами

Следовательно, - базисные переменные, а x2, x4 - небазисные. Полагая в системе уравнений x2=x4 =0, немедленно находим x1 =10, x3 =20, x5 =8. Видим, что значения базисных переменных равны правым частям ограничений. Из этого понятно требование положительности правых частей bi.

В дальнейшем, базисные переменные будем объединять в вектор x Б.

Таким образом, в канонической задаче предпочтительного вида в качестве начальной базисной матрицы берется единичная подматрица AБ =E, а соответствующие ей базисные переменные равны правым частям ограничений: xБ =b.

. Простейшая реализация симплекс-метода

Простейшая реализация симплекс-метода («простой С-метод») применяется к канонической задаче ЛП, имеющей «предпочтительный вид». Не умаляя общности, будем считать, что единичная подматрица содержится в первых m столбцах. Тогда каноническая задача запишется следующим образом

f(x) = c1x1 + c2x2 +… + cmxm + cm+1xm+1 +… + cnxn ??max(3.1)x1 + a1m+1 xm+1 + … + a1n xn = b1(3.2)x2 + a2m+1 xm+1 + … + a2n xn = b2………………………………………………………….xm + amm+1 xm+1 + … + amn xn = bmxj³ 0, j=1,2,…, n.(3.3)

Матрица условий

содержит единичную подматрицу размера m x m в первых m столбцах, следовательно AБ ={A1, A2,…, Am}=E.

Основные шаги симплекс-метода (теория)

Поскольку единичная базисная матрица находится в первых m столбцах матрицы условий, то первые m координат начального базисного плана являются базисными, а последние n - m координат являются небазисными, то есть равны нулю:

o = (x1, x2,…, xm, 0,…, 0).

Подставляя координаты точки xo в ограничения (3.2) и учитывая, чтоm+1 =… = xn = 0, получаем: x1 = b1, x2 = b2,…, xm = bm, то есть xoБ = b.

Значит начальный базисный план имеет вид:

xo = (b1,…, bm, 0,…, 0),

где сБ = (с1,…, сm) - вектор, составленный из коэффициентов целевой функции при базисных переменных.

1 шаг.

Из системы ограничений (3.2) выразим базисные переменные через небазисные:

x1= b1 - a1m+1xm+1 - … - a1nxn, x2 = b2 - a2m+1xm+1 - … - a2nxn, ………………………………………… xm = bm - amm+1xm+1 - … - amnxn,(3.4)

Подставим эти выражения в целевую функцию (3.1).

f (x) = c1 (b1 - a1m+1xm+1 - … - a1nxn) + c2 (b2 - a2m+1xm+1 - … - a2nxn) +

………………………………………………..

Cm (bm - amm+1xm+1 - … - amnxn) + cm+1xm+1 +… + cnxn.

Сгруппируем слагаемые при одинаковых небазисных переменных:

f (x) = - (c1 a1m+1 + c2 a2m+1 + … + cm amm+1 - cm+1).xm+1 - …-

- (c1 a1n + c2 a2n + … + cm amn - cn). xn.(3.5)

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

c1 a1m+1 + c2 a2m+1 + … + cm amm+1 - cm+1 = < cБ, Am+1 > - cm+1 = Dm+1,

…………………………………………………………………………………………………………………………1 a1n + c2 a2n + … + cm amn - cn = < cБ, An > - cn = Dn,

где сБ = (с1,…, сm) - вектор, составленный из коэффициентов целевой функции при базисных переменных, Am+1,…, An - столбцы матрицы условий А при небазисных переменных xm+1,…, xn.

Выражения

D j = < сБ, Aj > - cj, j = m+1,…, n,(3.6)

называются симплексными разностями или симплексными оценками базисного плана.

С учетом (3.6), формулу (3.5) для целевой функции можно переписать в виде

Эта формула позволяет получить признак оптимальности базисного плана. Если все симплексные оценки с небазисными номерами D j ³ 0, то текущий базисный план - оптимален.

Действительно, если хотя бы одна оценка, например, ?k строго отрицательна, то придавая соответствующей небазисной переменной xk положительное значение, а остальные небазисные переменные плана x полагая равными нулю, получим

f (x) = f (xo) - Dk xk = f (xo) + | D k | xk > f (xo),(3.7)

то есть в этом случае план xo может быть улучшен.

Легко проверить, что симплексные оценки, соответствующие единичным базисным столбцам всегда равны 0.

2 шаг . Нахождение переменной вводимой в состав базисных переменных.

Как следует из формулы (3.7), целевую функцию можно увеличить, если ввести в состав базисных переменных (сделать положительной) небазисную переменную xj, которой соответствует отрицательная оценка?j < 0. Если таких оценок несколько, то обычно в состав базисных вводят небазисную переменную хк с наибольшей по модулю отрицательной оценкой, то есть такую, для которой

где D j = < CБ, Aj > - cj, j = m+1,…, n (номера небазисных переменных).

Таким образом мы получим новый план

x1 = (x1,…, xm,0,…, xk,…, 0,…, 0).

Но х1 - небазисный план, так как число положительных координат равно m+1, число нулевых координат равно n - m -1.

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

3 шаг.

Подставим координаты точки х1 в условия (3.4) и учтем, что переменные xj должны быть неотрицательны

x1 = b1 - a1kxk³ 0 x2 = b2 - a2kxk³ 0 …………………………. xm = bm - amkxk³ 0(3.8)

Из формулы (3.7) видно, что чем больше величина хк > 0, тем больше возрастает целевая функция. Постараемся найти максимальное значение хк, не нарушая ограничений задачи и выполняя условия неотрицательности (3.8).

Неравенства (3.8) можно переписать в виде

A1kxk£ b1 a2kxk£ b2 ……………… amkxk £ bm(3.9)

При решении системы неравенств (3.9) возможны два случая:) среди коэффициентов при хк нет положительных: aik£ 0, i=1,2,…, m. Так как bi> 0, то неравенства (3.9) выполняются при любом сколь угодно большом значении хк. Это говорит о том, что целевая функция не ограничена на множестве планов (max f(x) ® ¥) и следовательно, решения задачи ЛП не существует.) среди коэффициентов при хк есть положительные aik > 0. Решая систему неравенств (3.9) получим:

хк £ bi /aik, для всех i, для которых aik > 0.(3.10)

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

хк = min {bi /aik} по всем i: aik > 0.

Пусть минимум достигается при i = r, то есть хк ? br /ark. Это означает, что базисная переменная хr в условиях (3.8) обращается в нуль.

хr = br - ark xk = br - ark (br /ark) = 0, 1 ??r ??m.

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

4 шаг.

Новый базисный план будет иметь вид

1 = (x1, x2,…, 0,…, xm, 0,…, хk,0,…, 0),

где на месте хr стоит ноль, а хк > 0.тому базисному плану соответствует новая базисная матрица:

Для нахождения координат новой угловой точки х1 каноническая задача ЛП приводится к новому предпочтительному виду, то есть к такой форме, чтобы матрица стала единичной (= E). Для этого столбец Аk нужно преобразовать к единичному представлению,

R-я строка,

в котором коэффициент = 1, а все остальные элементы =0, i ??r. Этого можно добиться с помощью элементарных операций над уравнениями системы. Решение заканчивается тогда, когда для некоторой точки все оценки Dj ³ 0.

3. Реализация симплекс-метода на примере

Продемонстрируем применение симплекс-метода на примере из главы 2.

Рассмотрим каноническую задачу ЛП

f(x) = x1+ 2x2 +0 x3 + 0 x4 max(3.11)-x1+ 2x2+ x3 = 4,(3.12)3 x1 +2x2 + x4 = 12,(3.13)xj ? 0, j = 1,2,3,4.(3.14)

Матрица условий A = (A1, A2, A3, A4), где

Целевой вектор c =(c1, c2, c3, c4)=(1, 2, 0, 0); вектор правых частей b=(b1, b2) = (4, 12).

0 шаг. Нахождение начальной угловой точки (базисного плана).

Задача имеет предпочтительный вид, так как правые части уравнений положительны, а столбцы матрицы условий A3, A4 образуют единичную подматрицу. Значит начальная базисная матрица = (A3, A4); x3 и x4 - базисные переменные, x1 и x2 - небазисные переменные, cБ = (c3, c4) = (0, 0).

Начальный базисный план имеет вид

x0 = (0, 0, x3, x4) = (0, 0, 4, 12); f(xo) = 0.

1 шаг. Проверка базисного плана на оптимальность.

Подсчитаем симплексные оценки для небазисных переменных по формуле (3.6)

D1 = < cБ, A1 > - c1 = 0 ·(-1) + 0 ·3 - 1 = -1.

D2 = < cБ, A2 > - c2 = 0 ·2 + 0 · 2 - 2 = -2.

Так как оценки отрицательны, то план xo - не оптимален. Будем искать новый базисный план (смежную угловую точку) с большим значением целевой функции.

2 шаг . Нахождение переменной вводимой в базис.

Целевую функцию можно увеличить, если ввести в состав базисных переменных (сделать положительной) одну из небазисных переменных x1 или x2, поскольку обе оценки Dj < 0. Обычно в состав базисных вводят небазисную переменную с наибольшей по модулю отрицательной оценкой, поэтому будем вводить в базис переменную x2.

3 шаг. Определение переменной выводимой из базиса.

После ввода в базис переменной x2 новый план будет иметь вид1 = (0, x2, x3, x4).

Этот план не является базисным, так как он содержит только одну нулевую координату, значит надо сделать нулевой (исключить из базиса) одну из переменных x3 или x4.

Подставим координаты плана x1 = (0, x2, x3, x4) в ограничения задачи. Получим

Выразим отсюда базисные переменные x3 и x4 через переменную x2, вводимую в базис.

x3 = 4 - 2x2,(3.15)x4 = 12 - 2x2.(3.16)

Так переменные x3 и x4 должны быть неотрицательны, получим систему неравенств

4 - 2x2 ³ 0,(3.17)12 - 2x2 ³ 0.(3.18)

Чем больше значение x2, тем больше возрастает целевая функция. Найдем максимальное значение новой базисной переменной, не нарушающее ограничения задачи, то есть удовлетворяющее условиям (3.17), (3.18).

Перепишем неравенства в виде

x2£ 4,

x2£12,

откуда максимальное значение x2 = min {4/2, 12/2} = 2. Подставляя это значение в выражения (3.15), (3.16) для x3 и x4, получаем x3 = 0. Следовательно x3 выводится из базиса.

4 шаг. Определение координат нового базисного плана.

Новый базисный план (смежная угловая точка) имеет вид

x1 = (0, x2, 0, x4).

Базис этой точки состоит из столбцов A2 и A4, так что = (A2, A4). Заметим, что этот базис не является единичным, так как вектор A2 = (2, 2), и следовательно задача (3.11) - (3.14) не имеет предпочтительного вида относительно нового базиса. Преобразуем условия задачи (3.12), (3.13) таким образом, чтобы она приняла предпочтительный вид относительно новых базисных переменных x2, x4, то есть чтобы переменная x2 входила в первое уравнение с коэффициентом, равным единице, и не присутствовала во втором уравнении. Перепишем уравнения задачи

x1+ 2x2+ x3 = 4, (p1)

x1 +2x2 + x4 = 12. (p2)

Поделим первое уравнение на коэффициент при x2. Получим новое уравнение = p1 / 2, эквивалентное исходному

1/2 x1+ x2+ 1/2 x3 = 2. ()

Используем это уравнение, которое назовем разрешающим, для исключения переменной x2 из второго уравнения. Для этого надо уравнение умножить на 2 и вычесть из p2. Получим уравнение = p2 - 2 = p2 - p1.

x1 - x3 + x4 = 8. ()

В итоге получили новое «предпочтительное» представление исходной задачи (3.11) - (3.14) относительно новых базисных переменных x2, x4:

f(x) = x1+ 2x2 + 0 x3 + 0 x4® max

1/2 x1+ x2+ 1/2 x3 = 2. ()

x1 - x3 + x4 = 8. ()

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

Подставляя сюда представление нового базисного плана x1 = (0, x2,0, x4), сразу найдем его координаты, так как значения базисных переменных равны правым частям уравнений

x1 = (0,2,0,8); f(x1)=4.

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

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

симплекс переменная канонический программирование

Литература

1. Эконометрика: Учебник / Под ред. И.И. Елисеевой. - М.: Финансы и статистика, 2002. - 344 с.: ил.

Практикум по эконометрике: Учеб. пособие / И.И. Елисеева, С.В. Курышева, Н.М. Гордеенко и др.; Под ред. И.И. Елисеевой. - М.: Финансы и статистика, 2002. - 192 с.: ил.

Кремер Н.Ш., Путко Б.А. Эконометрика: Учебник для вузов. - М.: ЮНИТИ-ДАНА, 2002. - 311 с.

Магнус Я.Р., Катышев П.К., Пересецкий А.А. Эконометрика. Начальный курс: учебник. - М.: Дело, 2001. - 400 с.

Катышев П.К., Магнус Я.Р., Пересецкий А.А. Сборник задач к начальному курсу эконометрики. - 3-е изд., испр. - М.: Дело, 2003. - 208 с.

Доугерти К. Введение в эконометрику. - М.: Финансы и статистика, 1999.

Джонстон Дж. Эконометрические методы. - М.: Статистика, 1980.

Кейн Э. Экономическая статистика и эконометрия. Введение в количественный экономический анализ. Вып. 1. - М.: Статистика, 1977.

Ланге О. Введение в эконометрику / Пер. с польск. - М.: Прогресс, 1964.

Лизер С. Эконометрические методы и задачи. - М.: Статистика, 1971.

Маленво Э. Статистические методы эконометрии. - М.: Статистика, 1976.

Тинтнер Г. Введение в эконометрию. - М.: Финансы и статистика, 1965.

Айвазян С.А., Мхитарян В.С. Прикладная статистика и основы эконометрики: учебник для вузов. - М.: ЮНИТИ, 1998.

Вентцель Е.С. Теория вероятностей: Учебник для вузов. - 6-е изд. - М.: Высш. шк., 1999.

2. Введение естественных базисных переменных. Построение симплексной таблицы. Определение нулевого плана.

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

Симплекс-метод - алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан американским математиком Джорджем Данцигом в 1947 году.

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

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

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

1. Приводим систему ограничений к каноническому виду (когда система ограничена). Причём в системе можно выделить единичный базис.

2. Находим первоначальный опорный план (неотрицательные базисные решения системы уравнений КЗЛП). Каждый из опорных планов определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов А 1 , А 2 ,…, А n . Верхняя граница количества опорных планов, содержащихся в данной задаче, определяется числом сочетаний С nm );

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

4. В симплексной таблице проверяем вектора на отрицательность, т.е. оценки Zj – Сj записанные в строке должны быть ≤ 0 (на минимум), Zj – Сj ≥ 0 (на максимум). Если оценки удовлетворяют условиям оптимальности то задача решена.

5. Если для некоторых векторов нарушаются условия оптимальности, то необходимо ввести в базис вектор, которому соответствует:

max[θ 0 j (Zj – Сj)] ; min[θ 0 j (Zj – Сj)] ; θ 0 j = min , где х i > 0

Элемент вектора θ j который соответствует θ 0 j называется разрешающим; строка и столбец в которых он находится, называется направляющим, из базиса уходит вектор, стоящий в направляющей строке.

6. Найдём коэффициент разложения для всех векторов в новом базисе. Применим метод Джордано Гаусса

Проверим на оптимальный опорный план. Если оценка удовлетворяет условиям оптимальности, то задача решена, если нет, то выполняются пункты 5-7.

2. Введение естественных базисных переменных. Построение симплексной таблицы. Определение нулевого плана.

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

Предприятие реализует n товарных групп, располагая m ограниченными материально-денежными ресурсами b i ≥0 (1 ≤ i ≤ m) . Известны расходы ресурсов каждого i - вида на производство и реализацию единицы товара каждой группы, представленные в виде матрицы (a ij) и прибыль, получаемая предприятием от реализации единицы товара j -группы, входящая в целевую функцию Z (X ). Метод линейного программирования не отличается от системы (1) - (2):

Z(X) = с 1 Х 1 + с 2 Х 2 + с 3 Х 3 + … +с n Х n →max(min) (1)

a 11 X 1 + a 12 X 2 +…a 1n X n ≤ b 1,

а 21 X 1 + a 22 X 2 +…a 2n X n ≤ b 2 (2)

a m1 X 1 + a m2 X 2 +…a mn X n ≤ b m,

X 1 ≥0 X 2 ≥0 X 3 ≥0 …X n ≥0

Этапы решения поставленной задачи симплексным методом включают:

1) Составление нулевого опорного плана. Вводим новые неотрицательные (базисные) переменные, благодаря которым система неравенств (2) становится системой уравнений:

a 11 X 1 + a 12 X 2 +…a 1n X n + X n+1 = b 1

a 21 X 1 + a 22 X 2 +…a 2n X n + X n+2 = b 2 (3)

……………………………………..

a m1 X 1 + a m2 X 2 +…a mn X n + X n+m = b m,

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

X n+1 = b 1, -a 11 X 1 - a 12 X 2 -…a 1n X n

X n+2 = b 2 - a 21 X 1 - a 22 X 2 -…a 2n X n (4)

………………………………………..

X n+m = b m, - a m1 X 1 + a m2 X 2 +…a mn X n

Целевую функцию перепишем в виде

Z (X) = 0-(-с 1 Х 1 -с 2 Х 2 -с 3 Х 3 -…-с n Х n) (5)

Полагая, что искомые основные переменные Х 1 = X 2 = X 3 = … = X n = 0, получаем нулевой опорный план Х = (0, 0, …0, b 1 , b 2, b 3 … b m), при котором Z(X) = 0 (все ресурсы на складе, ничего не производится). Заносим план в симплексную таблицу.

План	Базис	C i /C j	Знач. X i	X 1	X 2	X n	X n+1	X n+2	X n+ 3	Q min
	X n+1		b 1	a 11	a 12	a 13				b 1 / a 12
X n+2		b 2	a 21	a 22	a 23				b 2 / a 22
X n+3		b 3	a 31	a 32	a 33				b 3 / a 32
Z(X) = 0	-C 1	- C 2	- C 3				Индекс. строка

2) Из отрицательных коэффициентов индексной строки выбираем наибольший по абсолютной величине, что определяет ведущий столбец и показывает – какая переменная на следующей итерации (шаге) перейдет из основных (свободных) в базисные (фактически выбирается товарная группа, чья реализация приносит максимальный доход). Затем запасы сырья b i делим на соответствующие коэффициенты затрат, результаты заносим в таблицу и определяем минимальное значение Q min (выбирается ресурс, чей запас наиболее сильно ограничивает выпуск выбранной товарной группы). Это значение выделяет ведущую строку и переменную Х i , которая при следующем шаге (итерации) выйдет из базиса и станет свободной.

3) Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана-Гаусса. Сначала заменим в базисе Х j на Х i ведущего столбца. Разделим все элементы ведущей строки на разрешающий элемент (РЭ), в результате чего на месте РЭ в ведущей строке будет 1. Так как Х i стал базисным, то остальные его коэффициенты должны быть равны 0. Новые элементы этого плана находятся по правилу прямоугольника

НЭ=СЭ – (А*В)/РЭ (6)

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

Пример. На приобретение оборудования для производственного участка выделено 20 тыс.руб. Оборудование может быть размещено на площади, не превышающей 72 кв.м. Можно заказать оборудование двух типов: типа А, требующие производственную площадь 6кв.м и дающие 6 тыс.ед. продукции в смену (цена 5000 руб.) и типа В, требующие площадь 12 кв.м и дающие 3тыс.ед., (цена 2000 руб.). Каков оптимальный план приобретения оборудования, обеспечивающий максимальную производительность участка?

Обозначим количество приобретаемого оборудования типа А и В через Х 1 и Х 2 соответственно.

Производительность участка (целевая функция) : Z(X) =6Х 1 +3Х 2 .

Основные ограничения связаны

с денежными средствами: 5Х 1 +2Х 2 ≤ 20,

с площадью производственного участка: 6Х 1 +12Х 2 ≤ 72.

Вводим новые базисные переменные Х 3 (остаток денежных средств после закупки оборудования) и Х 4 (остаток площадей после размещения оборудования) и перепишем ограничения в виде системы уравнений:

5X 1 +2Х 2 +X 3 =20 (X 3 =20 – 5X 1 - 2X 2)

6Х 1 +12Х 2 +X 4 = 72 (X 4 =72 – 6X 1 – 12X 2)

При этом функция цели: Z(X) =6Х 1 +3Х 2 +0Х 3 +0Х 4 .

Составляем опорный (0-ой) план: Х= (0, 0, 20, 72), т.е. пока ничего не приобретено (деньги не потрачены, площади пустуют). Составляем симплексную таблицу

План	Базис	C i /C j	Знач. X i	X 1	X 2	X 3	X 4	Q min
	X 3							20/5=4
X 4							72/6=12
Z(X) = 0	- 6	- 3			Индексная строка
	→X 1				0,4	0,2		4/0,4=10
X 4				9,6	-1,2		48/9,6=5
Z(X) = 6*4=24		-0,6	1,2		Индексная строка
	X 1					0,25	-1/24	-
→X 2					-1/8	5/48	-
Z(X) =6*2+3*5=27			9/8	1/16	Индексная строка

Очевидно, что ведущий столбец соответствует Х 1 , так как имеет самый большой индекс 6. Находим минимальное значение Q min = 4 (самое жесткое ограничение ресурса), определяя ведущую строку, показывающую, что из базисных переменных выводится Х 3 , а вместо нее вводится Х 1 . Пересчитываем элементы ведущей строки, разделив их на 5, а по формуле (6) определяем элементы второй и индексной строк. Целевая функция для 1-ого плана равна Z(X) = 6*4+3*0 = 24.

Однако, один из коэффициентов индексной строки для столбца Х 2 остается отрицательным -0,6, следовательно данный план не оптимален, и требуется еще одна итерация (шаг) для его улучшения. Выбираем ведущим 2-ой столбец и по минимальному значению Q min = 5 определяем ведущую строку с базисной переменной Х 4 . Выполнив те же преобразования, получаем 2-ой план, который будет оптимальным, так как все индексные коэффициенты положительны.

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

Убедимся в этом: 5*2+2*5 = 20 тыс.руб., 6*2+12*5=72 кв.м. Искомое решение Х= (2; 5;0;0).Так бывает далеко не всегда.

Лекция № 10

Тема: Симплексный метод для задач с искусственным базисом

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

a i1 X 1 + a i2 X 2 +…a in X n ≥ b i (1)

или уравнений:

a i1 X 1 + a i2 X 2 +…a in X n = b i (1*),

то невозможно получить опорный план в искомом виде. В этом случае для соблюдения равенств (1*) вводится искусственный базис Y i , причем искусственные переменные не имеют непосредственного отношения к содержанию поставленной задачи, но позволяют построить опорный (стартовый) план:

a i1 X 1 + a i2 X 2 +…a in X n +Y i = b i (2)

Целевая функция при решении задачи на максимум запишется в виде:

Z(X) =∑C j X j +(-M)∑Y i (3),

при решении аналогичной задач на минимум:

Z(X)=∑C j X j +(M)∑Y i (3*),

где М – очень большое положительное число, своего рода штраф за использование искусственных переменных.

В случае неравенств (1) первоначально вводим дополнительные переменные Х n + i со знаком минус. Их матрица не будет единичной, поэтому в каждое неравенство системы (1) вводим искусственные переменные У i:

a i1 X 1 +a i2 X 2 +…a in X n –X n+i +Y i =b i (4)

Целевая функция при этом Z(X)=∑C j X j +0∑X n + i +(-M)∑Y i (для нахождения максимума). Применение искусственного базиса придает симплексному методу большую гибкость и позволяет использовать его для широкого круга задач.

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

Математически ограничения выпуска продукции запишутся в виде смешанной системы:

1Х 1 + 1Х 2 ≤ 6,

2Х 1 + 1Х 2 =8.

Введем для первого неравенства базисную переменную Х 3 , а для второго уравнения искусственную переменную Y 1:

1Х 1 + 1Х 2 + Х 3 = 6,

2Х 1 + 1Х 2 +Y 1 =8.

Выразим из полученной системы уравнений Х 3 и Y 1 и для определения максимума целевую функцию представим:

Z(X)= 3X 1 + 2X 2 +0X 3 –MY 1 = 3X 1 + 2X 2 –M(8 -2X 1 –X 2)=

3X 1 + 2X 2 –8M +2MX 1 + MX 2 = (2M + 3)X 1 + (M + 2)X 2 -8M

Для опорного плана - Х=(0,0,6,8). Построим симплексную таблицу:

План	Базис	C i /C j	Знач. X i	X 1	X 2	X 3	Y 1	Q min
	X 3							6/1=6
Y 1	-M						8/2=4
Z(X) = -8M	-2M-3	-M-2			Индексная строка
	X 3				0,5		-0,5	2/0,5=4
→X 1				0,5		0,5	4/0,5=8
Z(X) = 3*4=12		- 0,5		М+1,5	Индексная строка
	→X 2						-1	-
X 1					-1		-
Z(X) =3*2+2*4=14				М+1	Индексная строка

Как правило, улучшение опорного плана начинается с выведения из базиса искусственной переменной Y 1 .Оптимальный план Х=(2,4,0,0) получен на второй итерации, при этом доход максимален 14тыс. руб. , а коэффициенты индексной строки неотрицательны. Легко убедиться, что в данной задаче при оптимальном плане ресурсы использованы полностью (2*1+4*1=6; 2*2+1*4=8).

При нахождении минимальной доходности иначе формулируем целевую функцию (в качестве слагаемого вводится +MY 1:

Z(X)= 3X 1 + 2X 2 +0X 3 +MY 1 = 3X 1 + 2X 2 +M(8 -2X 1 –X 2)=

3X 1 + 2X 2 +8M - 2MX 1 - MX 2 = (3 - 2M)X 1 + (2 - M)X 2 +8M

Опорный план тот же, но коэффициенты индексной строки в симплексной таблице иные. Ведущий столбец, по-прежнему, выбираем по наибольшему по абсолютному значению положительному коэффициенту при X 1 , ведущая строка определяется по минимальному значению Q min =4.При первой итерации из базиса выводится искусственная переменная Y 1 .

План	Базис	C i /C j	Знач. X i	X 1	X 2	X 3	Y 1	Q min
	X 3							6/1=6
Y 1	M						8/2=4
Z(X) = 8М	2M-3	M-2			Индексная строка
	X 3				0,5		-0,5	2/0,5=4
→X 1				0,5		0,5	4/0,5=8
Z(X) = 3*4=12		- 0,5		-М+1,5	Индексная строка

Полученные отрицательные значения коэффициентов в индексной строке X i свидетельствуют об оптимальности 1-ого плана, при этом минимальный доход 12 тыс. рублей.

Он обеспечивается только выпуском продукции А (продукция В не выпускается), сырье не используется полностью (остаток Х 3 = 2т), при этом выполнено основное условие - рабочие полностью заняты на производстве.

Лекция № 11

Тема: Закрытая транспортная задача

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

2. Этапы определения плана решения транспортной задачи.

Лекция 3. Симплексные таблицы. Алгоритм симплексного метода.

§ 3 СИМПЛЕКСНЫЙ МЕТОД

3.1. Общая идея симплекс–метода. Геометрическая интерпретация

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

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

Пусть область допустимых решений изображается многоуголь­ником ABCDE . Предположим, что его угловая точка А соответствует исходному допустимому базисному решению. При беспорядочном переборе пришлось бы испытать пять допустимых базисных решений, соответствующих пяти угловым точкам мно­гоугольника. Однако из чертежа видно, что после вершины А выгодно перейти к соседней вершине В, а затем – к оптимальной точке С. Вместо пяти перебрали только три вершины, последовательно улучшая линейную функцию.

Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирова­ния – симплексного метода или метода последовательного улучшения плана.

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

Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским ученым Л.В. Канторовичем.

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

Для реализации симплексного метода – последовательного улучшения решения – необходимо освоить три основных элемента:

способ определения какого-либо первоначального допустимого базисного решения задачи;

правило перехода к лучшему (точнее, не худшему) решению;

критерий проверки оптимальности найденного решения.

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

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

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

Рассмотрим решение ЗЛП симплекс-ме­тодом и изложим ее применительно к задаче максимизации.

1. По условию задачи составляется ее математическая мо­дель.

2. Составленная модель преобразовывается к канонической форме. При этом может выделиться базис с начальным опорным планом.

3. Каноническая модель задачи записывается в форме симп­лекс-таблицы так, чтобы все свободные члены были неотрицатель­ными. Если начальный опорный план выделен, то переходят к пункту 5.

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

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

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

5. Найденный начальный опорный план исследуется на опти­мальность:

а) если в
–строке нет отрицательных элементов (не считая свободного члена), то план оптимален. Если при этом нет и нуле­вых, то оптимальный план единственный; если же есть хотя бы один нулевой, то оптимальных планов бесконечное множество;

б) если в
–строке есть хотя бы один отрицательный элемент, которому соответствует столбец неположительных элементов, то
;

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

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

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

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

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

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

3) из симплексных отношений выбирают наименьшее. Оно и определит разрешающую строку. Пусть ею будет, например, р –строка;

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

Если в форму ЗЛП облечена некоторая реальная производст­венная ситуация, то дополнительные переменные, которые прихо­дится вводить в модель в процессе преобразования ее к каноничес­кой форме, всегда имеют определенный экономический смысл.