Решение задач симплексным методом

План решения:

•1.Составить систему неравенств. 2.Привести систему неравенств к каноническому виду.

3.Составить симплекс-таблицу. 4.Проверить знаки в индексной строке. 5.Найти наибольшее Q.

6.Найти разрешающий элемент.

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

•Симплекс-пример: Дано: F(x)=3х1+5х2+4х3→Max

0.1х1+0.2х2+0.4х3≤1100 0.05х1+0.02х2+0.02х3≤120 3х1+1х2+2х3≤8000

1.На данном этапе смотрим к чему стремиться функция Max,Min.От этого зависит знак неравенств. 2.Если функция стремится к Max,то знак неравенств ≤.Если функция стремится к Min,то знак неравенств ≥

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

0.1х1+0.2х2+0.4х3 0.05х1+0.02х2+0.02х3 3х1+1х2+2х3

0.1х1+0.2х2+0.4х3+0х4=1100 0.05х1+0.02х2+0.02х3+0х5=120 3х1+1х2+2х3+0х6=8000

1.Уравниваем правую и левую часть неравенства добавляя новый элемент. Элементы не должны повторяться.

3.Составить симплекс-

План	Баз В		таблицу.				х5	х6	Q
			х1	х2	х3	х4
	ис
1	х4	110	0.1	0.2	0.4	1	0	0
	х5	0
		120	0.05	0.02	0.02	0	1	0
	х6
		800	3	1	2	0	0	1
Индексн		0
	F(X1)0
ая
строка	записываем

2.Базис – записываем добавленные элементы(базисные элементы). 3.В-коэффициенты уравнений.

4.Q- это отношение столбца B к столбцу с наименьшим коэффициентом в индексной строке.

5.Индексная строка – коэффициенты функции.

Индексная строка

	План	Баз	В	х1	х2	х3	х4	х5	х6 Q
		ис
	1	х4	110	0.1	0.2	0.4	1	0	0
		х5	0
			120	0.05	0.02	0.02	0	1	0
		х6
			800	3	1	2	0	0	1
	Индексн		0
		F(X1)	0	-3	-5	-4	0	0	0
	ая
	строка
	В индексной строке записываем

произведение коэффициентов функции на -1.

Коэффициенты в базисных элементах равны 0.

4.Проверить знаки в индексной строке.

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

*Выбираем наименьшее отрицательное число. *В столбце с наименьшем отрицательным числом будет находиться разрешающий элемент.

5.Найти наименьшее Q.

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

разрешающий элемент *Q=Элементы столбца В делить на

элементы столбца с наименьшим числом в индексной строке.

*1100/0.2=5500

*Необходимо выбрать наименьшее Q.

План

1

6.Найти разрешающий

	Баз В		х1элемент.				х5	х6
				х2	х3	х4
	ис
	х4	110	0.1	0.2	0.4	1	0	0
	х5	0
		120	0.05	0.02	0.02	0	1	0
	х6
		800	3	1	2	0	0	1
		0

Q

5500

6000

8000

Индексн

ая РазрешающийF(X1) 0 -3 -5 -4 0 0полученный0 0

строка

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

Правилом

прямоугольника.

•Правило прямоугольника

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

НЭ = СЭ - (А*В)/РЭ