Математические структуры данных. Задача на минимум Начальная симплекстаблица f 1 1 1

• Название: Задача на минимум Начальная симплекстаблица f 1 1 1
• Анкор: Математические структуры данных
• Дата: 27.10.2022
• Размер: 39.66 Kb.
• Имя файла: LR_2.docx
• Тип: Задача; #757778
• страница: 2 из 5

Т.к. Δ4 = 4/3, то решение не оптимально

F	1	1	1	0	0	0	0
базис							b	Q
	1	0				0		-
	0	1				0		13/10
	0	0				1		5/2
Δ	0	0				0

F	1	1	1	0	0	0	0
базис							b	Q
	1			0		0		-
	0			1		0		13/10
	0			0		1		5/2
Δ	0			0		0

Положительные дельты отсутствуют -> F=



Задача на максимум











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

F	1	1	1	0	0	0	0
базис							b
	1	0	0	-1	0	-2	5
	0	1	0	2	-3	1	3
	0	0	1	2	-5	6	5

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

Вычисляем дельты:

F	1	1	1	0	0	0	0
базис							b
	1	0	0	-1	0	-2	5
	0	1	0	2	-3	1	3
	0	0	1	2	-5	6	5
Δ	0	0	0	3	-8	5	13

Т.к. Δ5 = -8, то решение не оптимально. Разрешающий столбец – 5, все значения столба не положительны -> оптимальное решение отсутствует.

Двойственная задача на минимум











Найду задачу двойственную данной.

Исходная задача I		Двойственная задача II
x1 ≥ 0	↔	y1≤1
x2 ≥ 0	↔	y2≤1
x3 ≥ 0	↔	y3≤1
x4 ≥ 0	↔	-y1+2y2+2y3≤0
x5 ≥ 0	↔	-3y2-5y3≤0
x6 ≥ 0	↔	-2y1+y2+6y3≤0
x1+x2+x3 → min	↔	5y1+3y2+5y3 → max
x1-x4-2x6=5	↔	y1 любое число
x2+2x4-3x5+x6=3	↔	y2 любое число
x3+2x4-5x5+6x6=5	↔	y3 любое число