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

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

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

Заполняют столбцы для базисных переменных: на пересечении строки и столбца, в которых находится одна и та же переменная, ставят «1», в остальных клетках столбца нули.

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

Оценки D_j можно считать по приведенным ранее формулам или по правилу «прямоугольника».

Заполним симплекс-таблицу второго шага для варианта 0. Вместо переменной х₆ вводим в базис переменную х₂, в целевой функции ей соответствует коэффициент 20, который вносится в соответствующую клетку столбца с _i.

В строке, соответствующей переменной х₂ переписываем элементы из ключевой строки предыдущей таблицы, предварительно разделив их на ключевой элемент «4»:

с i	с j	16	20	18	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/ hij
0	x 4
0	x 5
20	х2	1/2	1	5/4	0	0	1/4	6
Dj									-

Заполняем столбцы для базисных переменных х₂, х₄, х₅:

с i	с j	16	20	18	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/ hij
0	x 4		0		1	0
0	x 5		0		0	1
20	х2	1/2	1	5/4	0	0	1/4	6
Dj			0		0	0			-

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

= ;

= ;

= ;

= ;

= ;

= ;

= ;

= .

с i	с j	16	20	18	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/ hij
0	x 4	1/2	0	-7/4	1	0	-3/4	2
0	x 5	4	0	-2	0	1	-1	16
20	х2	1/2	1	5/4	0	0	1/4	6
Dj			0		0	0			-

Находим оценки переменных:

D₁ = 0×(1/2) + 0×4 + 20×(1/2) – 16 = - 6;

D₃ = 0×(-7/4) + 0×(-2) + 20×(5/4) – 18 = 7;

D₆ = 0×(-3/4) + 0×(-1) + 20×(1/4) – 0 = 5; D₇ = 0×2 + 0×16 + 20×6 = 120.

с i	с j	16	20	18	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/ hij
0	x 4	1/2	0	-7/4	1	0	-3/4	2
0	x 5	4	0	-2	0	1	-1	16
20	х2	1/2	1	5/4	0	0	1/4	6
Dj		-6	0	7	0	0	5	120	-

 

Второе опорное решение имеет вид:  = (0, 6, 0, 2, 16, 0),  = 120.

Однако это решение не оптимальное, поскольку оценка D₁ = - 6 <0.

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

с i	с j	16	20	18	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/ hij
0	x 4	1/2	0	-7/4	1	0	-3/4	2
0	x 5	4	0	-2	0	1	-1	16
20	х2	1/ 2	1	5/4	0	0	1/4	6
Dj		-6	0	7	0	0	5	120	-

 

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

 

с i	с j	16	20	18	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/ hij
0	x 4	1/2	0	-7/4	1	0	-3/4	2	2/(1/2)
0	x 5	4	0	-2	0	1	-1	16	16/4
20	х2	1/ 2	1	5/4	0	0	1/4	6	6/(1/2)
Dj		-6	0	7	0	0	5	120	-

 

Минимальными являются два отношения в первой строке 2/(1/2) = 4 и во второй строке 16/4 = 4, поэтому в качестве разрешающей можно выбрать любую из них. Выбираем вторую строку, соответствующую переменной х₅, следовательно, переменная х₅ выводится из базисных переменных. На пересечении разрешающих строки и столбца находится разрешающий элемент «4»:

 

с i	с j	16	20	18	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/ hij
0	x 4	1/2	0	-7/4	1	0	-3/4	2	2/(1/2)
0	x 5	«4»	0	-2	0	1	-1	16	16/4
20	х2	1/ 2	1	5/4	0	0	1/4	6	6/(1/2)
Dj		-6	0	7	0	0	5	120	-

 

Переходим к третьему шагу симплекс-метода.

Заполним симплекс-таблицу третьего шага для варианта 0. Вместо переменной х₅ вводим в базис переменную х₁, в целевой функции ей соответствует коэффициент 16, который вносится в соответствующую клетку столбца с _i. Аналогично предыдущему шагу заполняем ключевую строку, столбцы базисных переменных и остальные клетки:

 

с i	с j	16	20	18	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/ hij
0	x 4	0	0	-3/2	1	-1/8	-5/8	0
16	x 1	1	0	-1/2	0	1/4	-1/4	4
20	х2	0	1	3/2	0	-1/8	3/8	4
Dj		0	0	4	0	3/2	7/2	144	-

 

Поскольку все оценки положительные D_j, то полученное опорное решение является оптимальным:  = (4, 4, 0, 0, 0, 0), а максимальное значение целевой функции равно  = 144.

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

 

с i	с j	16	20	18	0	0	0
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi
0	x 4	0	0	-3/2	1	-1/8	-5/8	0
16	x 1	1	0	-1/2	0	1/4	-1/4	4
20	х2	0	1	3/2	0	-1/8	3/8	4
Dj		0	0	4	0	3/2	7/2	144
yi		y 4	y 5	y 6	y 1	y 2	y 3

 

Таким образом,  = (0, 3/2, 7/2, 0, 0, 4), поскольку y ₁ « x ₄, y ₂ « x ₅, y ₃ « x ₆, y ₄ « x ₁, y ₅ « x ₂, y ₆ « x ₃. Значение целевой функции = 144.

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: