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

2.1. Основные операции и теоремы линейного программирования

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

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

Определение 3: Задача линейного программирования называетсядопустимой, если множество М - планов не пусто. ЗЛП называетсяразрешимой, если существует множество М^* оптимальных планов задачи.

Определение 4: Оптимальное значение ЗЛП представляет значение целевой функции , соответствующее оптимальному плану.

Определение 5:Алгебраическим аналогом в понятии вершины многогранной области является план опорной точки, или допустимое базисное решение (ДБР).

Пример 2.1:

найти minf(x) = -3x₁ - 2x₂

Каноническая ЗЛП:

maxf'(x) = 3x₁ + 2x₂

Решение системы из 4-х уравнений с 6-ю переменными можно получить, приравнивая 2 любые переменные к 0 и решая уравнение относительно 4-х других переменных:

Так как все, то данное базисное решение называется допустимым базисным решением (ДБР).

Переменные, приравненные к 0, называются свободными и не базисными.

(n-m)- количество не базисных переменных.

Остальные mпеременных – базисные и образуют базис.

Оптимальное решение следует искать среди ДБР .

(+). (2.1)

Таблица 2.1

N	x1	x2	x3	x4	x5	x6	ДБР>=0
1	0	0	6	8	1	2	+
2	0	3	0	5	-2	-1
3	0	8	-10	0	-7	-6
4	0	1	4	7	0	1	+
5	.	.	.	.	.	.	.
6	.	.	.	.	.	.	.
7	.	.	.	.	.	.	.
8	.	.	.	.	.	.	.
9	.	.	.	.	.	.	.
10	.	.	.	.	.	.	.
11	.	.	.	.	.	.	.
12	.	.	.	.	.	.	.
13	.	.	.	.	.	.	.
14	.	.	.	.	.	.	.
15	1	2	1	4	0	0	+

Пример 2.2:

- каноническая форма записи ЗЛП

Рис. 2.1

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

В приведенной ниже таблице записаны уже получившиеся решения 15 СЛАУ.

Допустимое базисное решение (ДБР) – это базисное решение при .

Таблица 2.2

N	x1	x2	x3	x4	x5	x6	ДБР≥0
1	0	0	4	21	43	44	+
2	0	4	0	9	39	56	+
3	0	7	-3	0	36	65
4	0	43	-39	-108	0	173
5	0	-14,6667	18,6667	65	57,6667	0
6	-4	0	0	17	55	60
7	-21	0	-17	0	106	128
8	14,3333	0	18,3333	35,3333	0	-13,3333
9	11	0	15	32	10	0	+
10	4,5	8,5	0	0	21	51,5	+
11	9,75	13,75	0	-10,5	0	46,25
12	56	60	0	-103	-185	0
13	10,8	10,6	4,2	0	0	32,6	+
14	21,6667	14,2222	11,4444	0	-36,2222	0
15	13,3077	3,0769	14,2308	25,07696	0	0	+

Так как оптимальное решение следует искать среди ДБР, то необходимо найти значения целевой функции, соответствующие ДБР. Максимальное из этих значений и будет решением рассматриваемой ЗЛП.

1)

2)

3)

4)

5)

6)

Наибольшее в заданной области значение, равное 32,2, рассматриваемая функция достигает в точке с координатами.

Данное решение совпадает с найденным с помощью графоаналитического метода значением.