Правило прямоугольника в симплекс методе пример – Алгоритм и пример симплекс-метода (ММЭ). Пример решения симплекс-методом

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

Базис	Переменные	Свободный член
	xm+1 … xk … xn
x1 . . . xi . . . xm	…… . . . …… . . . ……	. . . . . .
	……

Таблица 6.6

Симплекс-таблица для угловой точки x1

Базис	Переменные	Свободный член
	xm+1 … xq … xn
x1 . . . xk . . . xm	…… . . . …… . . ……	. . . . . .
	……

6.2.4. Алгоритм решения задач симплекс – методом

Для определенности считаем, что решается задача на отыскание минимума.

1. Задачу линейного программирования привести к каноническому виду.

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

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

2. Определить базисные и свободные переменные.

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

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

4. Определить возможность решения задачи по значениям согласно теоремам 6.7,…, 6.9.

5. Выбрать разрешающий (опорный) элемент

   . Если критерий оптимальности не выполнен (не выполнены условия теоремы 6.7 или 6.8), то наибольший по модулю отрицательный коэффициентв последней строке определяет разрешающий (опорный) столбец.

Составляем оценочные отношения каждой строки по следующим правилам:

1⁰), если всеиимеют разные знаки;

2⁰), если все

и;

3⁰), если;

4⁰) 0, еслии;

5⁰), еслииимеют одинаковые знаки.

Определим

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

6⁰) Переход к следующей таблице по правилам:

а) в левом столбце записываем новый базис: вместо основной переменной – переменную, т.е. поменяем местами переменные

и;

б) на место опорного элемента поставить 1;

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

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

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

, ,.

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

е) все полученные элементы новой таблицы разделить на опорный элемент .

7⁰) По значению элементаопределить, найдено ли оптимальное значение целевой функции. В случае отрицательного ответа продолжить решение (возврат к пункту 6).

Рис. 6.8. Правило прямоугольника для определения чисел:

а − , б −, в −.

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

Пример 6.8.Решить задачу, приведенную в примере 6.7, симплекс методом.

Решение.

В качестве начальной симплекс – таблицы возьмем таблицу, найденную в примере 6.7 и соответствующую допустимому базисному решению :

Таблица 6.7

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

Базис	Переменные		Свободный член	Оценочное отношение
	x1	x2
x3 x4 x5	1 2 0	2 1 1	7 8 3	7 4 
f(x)	-3	-3	0

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

Будем формировать новую таблицу в соответствии с описанным алгоритмом

п.6 а,б п.6 в,г

	x4	x2				x4	x2
x3					x3	-1
x1	1				x1	1	1	8
x5					x5	0
						3

Свободные места последней таблицы заполним по «правилу прямоугольника». Например, число, стоящие в строке при x₃и столбце приx₂этой таблицы, равно 2∙2-1∙1 = 3. Дляи т.д. В результате этих вычислений, а также пункта 6е (т.е. деления на опорный элемент) получим искомую симплекс – таблицу:

п.6д п.6е

	x4	x2				x4	x2
х3	-1	3	6		x3	-1/2	3/2	3
х1	1	1	8		x1	1/2	1/2	4
х5	0	2	6		x5	0	1	3
	3	-3	24			3/2	-3/2	12

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

В качестве опорного (см. п. 6е) можно взять только второй столбец (). С учетом (6.29) находим опорную строку:

Таблица 6.8

Симплекс-таблица для угловой точки х¹

Базис	Переменные		Свободный член	Оценочное отношение
	x4	x2
x3 x1 x5	-1/2 1/2 0	3/2 1/2 1	3 4 3	2 8 3
f(x)	3/2	-3/2	12

, т.е. это первая строка. Опорный элемент обведен рамкой.

Преобразуем таблицу согласно алгоритму, получаем

x4

x3

x4

x3

x4

x3

x2

-1/2

1

3

x2

-1/2

1

3

x2

-1/3

2/3

2

x1

-1/2

x1

1

-1/2

9/2

x1

2/3

-1/3

3

x5

-1

x5

1/2

-1

3/2

x5

1/3

-2/3

1

3/2

3/2

3/2

45/2

1

1

15

Таким образом, на данной итерации значение f(х) уменьшилось с –12 до –15.

Так как все элементы в последней строке таблицы неотрицательны, то, согласно теореме 6.9, базисное решение является точкой минимума в рассматриваемой задаче, т.е.х* = (3;2;0;0;1),f* = –15. Графическое решение задачи представлено на рис. 6.8, откуда видно, чтох* = (3;2),f* =f(х*) = –15

Рис. 6.8. Графическое решение задачи 6.10

studfiles.net

Презентация на тему: Правило прямоугольника на практике.

План	Базис							х3
				В	х1	х2
1	х4			1100	0.1	0.2
	х5			120	0.05	0.02		0.02
• НЭ=					НЭ=
НЭ= 1100:0.2=5500					НЭ= 0.1:0.2=0.5

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

В столбце “Базис” меняем базисные переменные на переменные уравнения.(Переменные уравнения выбираем по разрешающему элементу.)

Внимание

План	Бази	В	х1	х2	х3	х4	х5	х6	Q
	с
2	х4	1100	0.1	1	0.4	1	0	0
	х5	120	0.05	0	0.02	0	1	0
	х6	8000	3	0	2	0	0	1
Индексн	F(X1) 0		-3	0	-4	0	0	0	0
ая
строка

Разрешающий элемент необходимо привести к 1 . Для этого делим 0,2/0,2=1.

Коэффициенты под разрешающим элементом записываются нулями.

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

План	Ба	В	х1	х2	х3	х4	х5	х6	Q
	зи
	с
2	x2	5500	0.5	1	2	5	0	0
	x5	10	0.04	0	-0.02	-0.1	1	0
	x6	2500	2.5	0	0	-5	0	1
Индексна	F(X227500		-0.5	0	6	25	0	0
я строка	)

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

Разрешающий элемент

План	Ба	В	х1	х2	х3	х4	х5	х6	Q
	зи
	с
2	x2	5500	0.5	1	2	5	0	0	11000
	x5	10	0.04	0	-0.02	-0.1	1	0	250
	x6	2500	2.5	0	0	-5	0	1	1000
Индексна	F(X227500		-0.5	0	6	25	0	0	0
я строка
	)

1. Находим наименьшее Q. 2.Находим разрешающий элемент.

Новая симплекс таблица.

План	Бази	В	Х1	Х2	Х3	Х4	Х5	Х6	Q
	с
3	x2	5375	0	1	2.25	6.25	-12.5	0
	x1	250	1	0	-0.5	-2.5	25	0
Индексн	x6	1875	0	0	1.25	1.25	-62.5	1
	F(X3)	2762	0	0	5.75	23.75	12.5	0
ая
строка		5

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

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

Ответ= 27625.

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

studfiles.net

5.2. Симплексные таблицы и алгоритм решения задач

Рассмотрим алгоритм решения задач симплексным методом¹⁷.

1. Математическая модель задачи должна бать канонической. Если она неканоническая, то ее надо привести к каноническому виду.

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

Симплексная таблица имеет следующий вид:

сi	Базисная переменная (БП)	с1	с2		сm	сm+1		сn	f(X)
		x1	x2		xm	xm+1		xn	b1
c1	x1	1	0		0	h1, m+1		h1n	l1
c2	x2	0	1		0	h2, m+1		h2n	l2
									
cm	xm	0	0		1	hm, m+1		hmn	lm
	j	0	0		0	m+1		n	f(X1)

Индексная строка (_j) для переменных находится по формуле

и для свободного члена по формуле

.

При этом возможны следующие случаи решения задачи на максимум:

— если все оценки _j  0, то найденное решение оптимальное;

— если хотя бы одна оценка _j  0, но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращают, так как f(X)  , т.е. целевая функция не ограничена в области допустимых решений;

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

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

Пусть одна оценка _k  0 или наибольшая по абсолютной величине _k  0, тогда k-й столбец принимают за ключевой (разрешающий). За ключевую (разрешающую) строку принимают ту, которой соответствует минимальное отношение свободных членов (b_i) к положительным коэффициентам k-го столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называют ключевым (разрешающим) элементом.

3. Заполнение симплексной таблицы 2-го шага:

— переписывается ключевая строка, разделив ее элементы на ключевой элемент;

— заполняют базисные столбцы;

— остальные коэффициенты таблицы находят по правилу «прямоугольника». Оценки можно считать по приведенным выше формулам или по правилу «прямоугольника». Получается новое опорное решение, которое проверяется на оптимальность и т.д.

Примечание. Если целевая функция f(X) требует нахождения минимального значения, то критерием оптимальности задачи является неположительность оценок _j при всех .

Правило «прямоугольника» состоит в следующем. Пусть ключевым элементом 1-го шага является элемент 1-й строки (m+1)-го столбца h_{1, m+1}. Тогда элемент i-й строки (m+2)-го столбца 2-го шага, который обозначим , по правилу «прямоугольника» определяется по формуле

,

где h_{1, m+1}, h_{i, m+1}, h_{i, m+2} – элементы 1-го шага.

5.3. Применение симплексного метода в экономических задачах

Рассмотрим применение симплексного метода на примерах экономических задач¹⁸.

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

Производственный ресурс	Расход ресурсов за 1 месяц при работе		Общий ресурс
	по 1 способу	по 2 способу
Сырье	1	2	4
Оборудование	1	1	3
Электроэнергия	2	1	8

При первом способе производства предприятие выпускает за один месяц 3 тыс. изделий, при втором – 4 тыс. изделий.

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

Решение. Обозначим: х₁ – время работы предприятия по первому способу; х₂ – время работы предприятия по второму способу. Экономико-математическая модель задачи:

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

Приведем задачу к каноническому виду:

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

Составляем симплексную таблицу 1-го шага:

сi	БП	3		4		0		0		0
		х1		х2		х3		х4		х5		bi
0	x3	1		2		1		0		0		4
0	x4	1		1		0		1		0		3
0	x5	2		1		0		0		1		8
j			-3		-4		0		0		0		0

= (0, 0, 4, 3, 8), = 0.

В индексной строке _j имеются две отрицательные оценки, значит найденное решение не является оптимальным и его можно улучшить. В качестве ключевого столбца следует принять столбец базисной переменной х₂, а за ключевую строку – строку переменной х₃, где min (4/2, 3/1, 8/1) = min (2, 1, 8) = 2.

Ключевым элементом является «2». Вводим в столбец БП переменную х₂, выводим х₃. Составляем симплексную таблицу 2-го шага:

сi	БП	3		4		0		0		0
		х1		х2		х3		х4		х5		bi
4	x2	1/2		1		1/2		0		0		2
0	x4	1/2		0		-1/2		1		0		1
0	x5	3/2		0		-1/2		0		1		6
j			-1		0		2		0		0		8

= (0, 2, 0, 1, 6), =8.

В индексной строке имеется одна отрицательная оценка. Полученное решение можно улучшить. Ключевым элементом является «1/2». Составим симплексную таблицу 3-го шага:

сi	БП	3		4		0		0		0
		х1		х2		х3		х4		х5		bi
4	x2	0		1		1		-1		0		1
3	x1	1		0		-1		2		0		2
0	x5	0		0		1		-3		1		3
j			0		0		1		2		0		10

Все оценки свободных переменных _j  0, следовательно, найденное опорное решение является оптимальным:

= (2, 1, 0, 0, 3), = 10.

Ответ: максимальный выпуск продукции составит 10 тыс. ед., при этом по первому способу предприятие должно работать два месяца, по второму – один месяц.

studfiles.net

Основы симплекс — метода линейного программирования

Симплекс — метод представляет собой итеративную процедуру решения задач ЛП, в каноническом виде (любую задачу ЛП можно привести к каноническому виду:

(1)

Всего в задаче будет n+m переменных.

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

Будем считать, что решается задача на максимум (задачу на минимум можно свести к задаче на максимум, умножив целевую функцию на (-1))

Пример 1.

Решим задачу:

Приведем систему ограничений к каноническому виду. Получим расширенную систему:

Для нахождения первоначального базисного решения разобьем переменные на основные и неосновные. Так как определитель матрицы коэффициентов при х₃, х₄ х₅ и х₆ отличен от нуля (каждая из этих переменных входит только в одно ограничение причем с коэффициентом 1, то есть матрица коэффициентов при них будет единичной), то их можно взять за базисные переменные. Остальные переменные х₁ и х₂ будит неосновными.

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

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

1). Получим на первом шаге:

Базисные переменные	Не базисные переменные
х3, х4 х5 х6	х1 х2

Выразим неосновные переменные через основные:

(*)

Получим базисное решение системы Х₁=(0; 0; 18; 16; 5; 21). Если сравнить с графическим решением этой задачи, то Х₁ соответствует точке О(0;0) многоугольника ОАВСДЕ (см. рис. 1).

Так как это решение допустимое, нельзя исключать, что оно оптимальное.

Выразим целевую функцию через неосновные переменные: ,z(X₁)=0.

Функцию z можно увеличить за счет неосновной переменной (обе они входят в уравнение с коэффициентом >0). Это можно осуществить, перейдя к новому допустимому базисному решению, в котором одна из этих переменных станет основной. Если новое решение будет вырожденным, то целевая функция сохранит свое значение. Геометрически это переход к другой соседней вершине, в которой целевая функция будет по крайней мере не хуже. В рассматриваемой задаче можно переводить в базисные переменные как х₁ так и х₂, так как обе входят в целевую функцию со знаком «+».

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

Система ограничений (*) накладывает ограничения на рост х₂, так как необходимо сохранять допустимость решения (все переменные должны быть »0). Поэтому следующие неравенства должны быть выполнены при х₁=0:

Любое уравнение системы (*) (кроме последнего) определяет оценочное отношение – границу роста переменной х₂, сохраняющую неотрицательность соответствующей переменной. Эта граница определяется абсолютной величиной отношения свободного члена к коэффициенту при х₂, если они имеют разные знаки. Так как в последнее ограничение х₂ не входит (входит с коэффициентом 0), то рост х₂ не ограничен, х₂<∞. Будем так же считать, сто граница переменной х₂ равно ∞, если коэффициент перед х₂ и свободный член имеют одинаковые знаки. Нет ограничений на рост х₂ и в том случае, если свободные член равен 0. Но если при этом коэффициент при х₂ отрицательный, то рост этой переменной ограничен 0.

Так как неотрицательность должны сохранять все переменные, по новая базисная переменная х₂=min(6; 16; 5; ∞)=5. Уравнение, которое соответствует минимальной оценке, называется разрешающим. В этом примере – это третье уравнение

Следовательно, переменная х₅=0 и переходит в небазисные переменные.

2). Получим на втором шаге:

Базисные переменные	Не базисные переменные
х3, х4 х2 х6	х1 х5

Из третьего уравнения системы выразим :х₂:

Подставляя правую часть равенства во все остальные уравнения вместо х₂ получим:

Получим новое базисное решение системы Х₂=(0; 5; 3; 11; 0; 21). Это соответствует точке А(0;5) многоугольника ОАВСДЕ (см. рис. 1).

Выразим целевую функцию через неосновные переменные: ,z(X₂)=15.

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

х₁=min(∞; 13; 11/2; ∞)=3, следовательно второе уравнение разрешающее и х₃ выводится из базиса.

3). Получим на третьем шаге:

Базисные переменные	Не базисные переменные
х1, х4 х2 х6	х3 х5

Из второго уравнения системы выразим :х₁:

Подставляя правую часть равенства во все остальные уравнения вместо х₁ получим:

Получим новое базисное решение системы Х₃=(3; 5; 0; 5; 0; 12). Это соответствует точке В(3;5) многоугольника ОАВСДЕ (см. рис. 1).

Выразим целевую функцию через неосновные переменные: ,z(X₃)=21.

Аналогично первым двум шагам введем в базисные переменные х₅.

х₅=min(∞; 5; 1;4/3)=1, следовательно, третье уравнение разрешающее и х₄ выводится из базиса.

4). Получим на четвертом шаге:

Базисные переменные	Не базисные переменные
х1, х5 х2 х6	х3 х4

Из третьего уравнения системы выразим :х₅:

Подставляя правую часть равенства во все остальные уравнения, вместо х₅ получим:

Получим новое базисное решение системы Х₄=(6; 4; 0; 0; 1; 6). Это соответствует точке С(6;4) многоугольника ОАВСДЕ (см. рис. 1).

Выразим целевую функцию через неосновные переменные: ,z(X₄)=24.

Целевую функцию нельзя улучшить переходя к другому базисному решению, так как все коэффициенты при небазисных переменных меньше 0, следовательно, задача решена. Максимальная прибыль при этом равна 24, а оптимальный план производства: 6 единиц первой продукции и 4 единицы второй продукции. Дополнительные переменные показывают разницу между затратами ресурсов каждого вида и их потреблением. х₃=х₄=0, следовательно ресурсы S₁ иS₂ расходуются полностью в процессе производства, а остатки S₃ иS₄ равны 1 и 3 соответственно.

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

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

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

2. Исходную расширенную систему заносим в первую симплекс таблицу. Последняя строка в которой приведено уравнение для линейной функции цели, называется оценочной. В ней указываются коэффициенты функции цели с противоположным знаком. В левом столбце таблицы записываем базисные переменные (на первом шаге за базисные переменные берутся дополнительные переменные), в первой строке – все переменные, во втором столбце – свободные члены расширенной системы b₁,…,b_m. Последний столбец подготовлен для оценочных отношений, необходимый при расчете. В рабочую часть таблицы, начиная с третьего столбца и второй строки, занесены коэффициенты при переменных a_ij расширенной системы. Далее таблица преобразуется по определенным правилам.

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

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

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

   1. , если b_i и a_is имеют разные знаки;

   2. , если b_i=0 и a_is<0;

   3. , если a_is=0;

   4. 0, если b_i=0 и a_is>0;

   5. , если b_i и a_is имеют одинаковые знаки.

Определяем . Если конечного минимума нет, то задача не имеет конечного оптимума (z_max=). Если минимум конечен, то выбираем строку q, на которой он достигается (если их несколько, то любую), и называем ее разрешающей строкой. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент a_qs.

6. Переходим к следующей таблице по правилам (преобразования Гаусса-Жордана или правило прямоугольника):

   1. в левом столбце записываем новый базис: вместо основной переменной x_q – переменную x_s;

   2. в столбцах, соответствующих базисным переменным, проставляем нули и единицы: 1- на пересечении строки и столбца, соответствующих одной и той же базисной переменной; 0 – во всех других позициях столбцов базисных переменных;

   3. Новую строку q получаем из старой делением на разрешающий элемент a_qs;

   4. все остальные элементы а_ij^‘ вычисляем по правилу:

(2)

Далее переходим к шагу III.

Пример 6.

Решим задачу:

Приведем систему ограничений к каноническому виду. Получим расширенную систему:

Целевую функцию представим в виде z-2x₁-3x₂=0.

Базисными переменными будут являться дополнительные переменные x₃,x₄,x₅,x₆.

Заполним первую симплекс-таблицу:

Базис	Свободный член	Переменные						Оценочные отношения
		x1	x2	x3	x4	x5	x6
x3	18	1	3	1	0	0	0	18/3
x4	16	2	1	0	1	0	0	16
x5	5	0	1	0	0	1	0	5
x6	21	3	0	0	0	0	1	
z	0	-2	-3	0	0	0	0

Проверяем критерий оптимальности задачи. В последней оценочной строке имеются отрицательные коэффициенты. Выбираем из них наибольший по модулю – (-3). Следовательно s=2, переменная х₂является вводимой базис, а соответствующий ей столбец – разрешающим.

Находим оценочные отношения и выбираем из них минимальное (=5). Следовательно, q=3, переменная х₅является выводимой из базиса, а соответствующая ей строка – разрешающей.

Переходим к новой симплекс-таблице:

1. в новом базисе основные переменные x₃,x₄,x₂,x₆;

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

Получаем вторую симплекс таблицу:

Базис	Свободный член	Переменные						Оценочные отношения
		x1	x2	x3	x4	x5	x6
x3	3	1	0	1	0	-3	0	3
x4	11	2	0	0	1	-1	0	11/2
x2	5	0	1	0	0	1	0	
x6	21	3	0	0	0	0	1	7
z	15	-2	0	0	0	3	0

Критерий оптимальности вновь не выполнен. Теперь разрешающий первый столбец и х₁– вводимая переменная. Считаем оценочные отношения и находим разрешающую строку – первая и выводимую из базиса переменную – х₃. Разрешающий элемент а₁₁.

Переходим к новой симплекс-таблице:

Базис	Свободный член	Переменные						Оценочные отношения
		x1	x2	x3	x4	x5	x6
x1	3	1	0	1	0	-3	0	
x4	5	0	0	-2	1	5	0	5/5
x2	5	0	1	0	0	1	0	5/1
x6	12	0	0	-3	0	9	1	12/9
z	21	0	0	2	0	-3	0

И на этот раз критерий оптимальности не выполнен.

Выводимая переменная х₄; вводимая х₅. Переходим к новой таблице.

Базис	Свободный член	Переменные						Оценочные отношения
		x1	x2	x3	x4	x5	x6
x1	6	1	0	-1/5	3/5		0
x5	1	0	0	-2/5	1/5	1	0
x2	4	0	1	2/5	-1/5	0	0
x6	3	0	0	3/5	-9/5	0	1
z	24	0	0	4/5	3/5	0	0

Критерий оптимальности выполнен, значит z_max=24. Оптимальное решение (6; 4; 0; 0; 1; 3).

studfiles.net

Табличный симплекс-метод

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

F=a_0,1x₁+a_0,2x₂+…a_0,nx_n +b _{→ max}

a_1,1x₁+a_1,2x₂+…a_1,nx_n + x_n+1=b₁

a_2,1x₁+a_2,2x₂+…a_2,nx_n +x_n+2 =b₂

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

a_m,1x₁+a_m,2x₂+…a_m,nx_n+x_n+m=b_m

Исходная таблица для задачи имеет следующий вид:

	x1	x2	…	xn-1	xn	b
F	-a0,1	-a0,2	…	-a0,n-1	-a0,n	-b
xn+1	a1,1	a1,2	…	a1,n-1	a1,n	b1
xn+2	a2,1	a2,2	…	a2,n-1	a2,n	b2
…	…	…	…	…	…	…
xn+m	am,1	am,2	…	am,n-1	am,n	bm

x₁, x₂, x_n — исходные переменные, x_n+1, x_n+2, x_n+m — дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным правилам.

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

 Подготовительный этап

Приводим задачу ЛП  к каноническому виду

F=a_0,1x₁+a_0,2x₂+…a_0,nx_n +b _{→ max}

a_1,1x₁+a_1,2x₂+…a_1,nx_n+x_n+1=b₁

a_2,1x₁+a_2,2x₂+…a_2,nx_n+x_n+2=b₂

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

a_m,1x₁+a_m,2x₂+…a_m,nx_n+x_n+m=b_m

В случае если в исходной задаче необходимо найти минимум — знаки коэффициентов целевой функции F меняются на противоположные a_0,n=-a_0,n. Знаки коэффициентов ограничивающих условий со знаком «≥» так же меняются на противоположные. В случае если условие содержит знак «≤» — коэффициенты запишутся без изменений.

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

	x1	x2	…	xn-1	xn	b
F	-a0,1	-a0,2	…	-a0,n-1	-a0,n	-b
xn+1	a1,1	a1,2	…	a1,n-1	a1,n	b1
xn+2	a2,1	a2,2	…	a2,n-1	a2,n	b2
…	…	…	…	…	…	…
xn+m	am,1	am,2	…	am,n-1	am,n	bm

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

Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю — он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент a_k,l — он задает ведущий столбец — l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно правилам.

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

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

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

На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность Если среди элементов симплексной таблицы, находщихся в строке F (не беря в расчет элемент b₀ — текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.

Если в строке F есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b₎

a_0,l=min{a_0,i }

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

b_k/a_k,l =min {b_i/a_i,l } при a_i,l>0, b_i>0

k — cтрока, для которой это отношение минимально — ведущая. Элемент a_k,l — ведущий (разрешающий). Переменная, соответствующая ведущей строке (x_k) исключается из базиса, переменная соответствующая ведущему столбцу (x_l) включается в базис.

Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2

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

Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.

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

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

• • Вместо базисной переменной x_k записываем x_l; вместо небазисной переменной x_l записываем x_k.
  • ведущий элемент заменяется на обратную величину a_k,l‘= 1/a_k,l
  • все элементы ведущего столбца (кроме a_k,l) умножаются на -1/a_k,l
  • все элементы ведущей строки (кроме a_k,l) умножаются на 1/a_k,l
  • оставшиеся элементы симплекс-таблицы преобразуются по формуле a_i,j‘= a_i,j— a_i,lx a_k,j/ a_k,l

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

Преобразуемый элемент a_i,j и соответствующие ему три сомножителя как раз и являются вершинами ”прямоугольника”.

Пример

uchimatchast.ru

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

Поиск Лекций

---

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

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

(3.1)

при следующих ограничениях на переменные:

(3.2)

 

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

(3.2^’)

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

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

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

Таблица 3.1

Первая симплексная таблица

В первую таблицу заносят исходные данные задачи, содержащиеся в системе (3.2′) и уравнении (3.1). В табл. 3.1 приняты следующие обозначения: БП — базисные переменные. В этот столбец заносятся переменные , которые мы приняли за базисные. СЧ — свободные члены. В столбец СЧ заносят правые части уравнения (3.2′). Далее идет перечень всех переменных . В столбец , записывают коэффициенты, стоящие перед в уравнениях системы (3.2′). В третьем уравнении (3.2′). | отсутствует, т. е. коэффициент перед , равен нулю. Аналогично, в столбцы переменных заносят коэффициенты при этих переменных из системы (3.2′). Осталось объяснить, как заполняется последняя строка С. Эта строка отводится для коэффициентовцелевой функции z (см. 3.1). В столбец СЧ записывают свободный член (т.е. постоянное слагаемое) функции z. В данном случае он равен нулю. В столбцы заносят соответствующие коэффициенты с противоположными знаками. Коэффициент при равен 7, поэтому в табл.3.1 записывается -7. Таблица 3.1 заполнена.

В таблице 3.1 содержится решение задачи (3.1) — (3.2):
х₃= 19, х₄= 13, х₅= 15, х₆=18, х₁ = 0, х₂ = 0. (3.3)

Решение (3.3) называется опорным решением. Посмотрим, нельзя ли улучшить решение (3.3), т. е. нельзя ли, изменяя значения переменных , увеличить значение функции z (пока z = 0). Рассмотрим последнюю строку табл. 3.1, Она содержит отрицательные числа в столбцах . Это признак неоптимальности решения (3.3). Его можно улучшить. Для перехода к следующему улучшенному решению в табл. 3.1 выбирают разрешающий столбец и разрешающую сроку.

За разрешающий столбец принимается тот, который в последний строке С имеет наибольшее по абсолютной величине отрицательное число. (Среди других отрицательных чисел строки С). В табл. 3.1 это столбец . Он отмечается стрелкой. После этого определяется раз­решающая строка. Для ее определения составляют отношения свободных членов табл. 3.1 к соответствующим положительным элементам разрешающего столбца ( ): 19:2 = 9,5; 13 : 2 = 6,5; 18:3 = 6.

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

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

Вторая симплексная таблица (промежуточный этап заполнения)

Таблица 3.2а

 

В первую очередь табл. 3.2 заполняется строка , которая в табл. 3.1 была разрешающей. Поэтому она называется начальной строкой. Для ее заполнения все элементы разрешающей строки х₆табл. 3.1

делят на разрешающий элемент 3 и результаты записывают в соответствующие столбцы строки x₁ табл. 3.2:

18:3 = 6; 3 : 3 = 1; 0 : 3 = 0;…, 1 : 3 = 1/3.

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

Остальные элементы табл. 3.2 вычисляются по правилу прямоугольника.

Вторая симплексная таблица

Таблица 3.2

Вычислим, например, элемент табл. 3.2, стоящий в столбце СЧ строки .

В табл. 3.1 рассмотрим элемент, стоящий на такой же позиции – он равен 19.

Мысленно построим прямоугольник, в одной вершине которого стоит число 19, в другой — разрешающий элемент (число 3), а две другие вершины отмечены в табл. 3.1 кружками. Искомый элемент табл. 3.2 равен произведению элементов, стоящих на главной диагонали прямоугольника минус произведение элементов на второй диагонали ; разность надо разделить на разрешающий элемент:

.

Элемент столбца СЧ строки х₄ табл. 3.2 вычисляется по формуле

.

Элемент столбца СЧ строки х₅:

.

Наконец, элемент строки С столбца СЧ равен:

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

Например, x₃₂— элемент строки х₃ столбца х₂ вычисляется по формуле (см. табл.3.1):

Так заполняется вся таблица 3.2. Решение, содержащееся в этой таблице неоптимально, т. к. в строке С есть отрицательное число — 5. Следовательно это решение можно улучшить. Перейдем к построению таблицы 3.3. Все выкладки, проведенные нами для перехода к таблице 3.2 повторяются, начиная с нахождения разрешающего столбца и разрешающей строки. Разрешающим столбцом в таблице 3.2 является столбец х₂. Составим отношения СЧ к элементам столбца х₂:7:3=7/3;1:1=1;15 : 3 = 5. Наименьшее отношение дает строка х₄ — она и является разрешающей. Разрешающий элемент: 1.

Третья симплексная таблица

Таблица 3.3

 

Базисными переменными в таблице 3.3 являются х₃, х_2, х₅, x₁. Вначале заполняется строка х₂ (начальная), которая получается из строки x₄ табл. 3.2 делением на разрешающий элемент. Т.к. разрешающий элемент равен 1, строка x₄ просто переписывается в табл. 3.3.

Затем в столбце х₂ (бывшем разрешающем) пишем нули. Остальные элементы табл. 3.3 находим по правилу прямоугольника с помощью табл. 3.2. Решение, содержащееся в табл. 3.3 — неоптимально, т. к. в последней строке в столбце х₆ есть отрицательное число — 1. Еще раз применяя алгоритм симплекс-метода, получаем оптимальное решение.

Четвертая симплексная таблица

Таблица 3.4

 

Запишем оптимальное решение, содержащееся в табл. 3.4. Базисные

переменные равны свободным членам, т. е. , а свободные переменные (те, которых нет в столбце БП) равны нулю: . Элемент столбца СЧ строки С дает максимальное значение функции z : z_max = 50.

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

 

 

Рекомендуемые страницы:

Поиск по сайту

poisk-ru.ru

No related posts.