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

Пример. Рассмотрим задачу оптимизации плана про­изводства с целью получения максимальной прибыли (табл. 5).

Таблица 5

Ресурсы	Норма расхода ресурсов				Запас ресурса
	П1	П2	П3	П4
Трудовые	1	1	1	1	16
Сырье	6	5	4	3	110
Оборудование	4	6	10	13	100
Прибыль	60	70	120	130	-
План	х1	х2	х3	х4	-

Решение. Математическая модель задачи:

В ограничения задачи введем дополнительные перемен­ные y₁, y₂, y₃ перепишем условие задачи в виде уравнений:

Эту подстановку можно переписать в виде рис. 6.

Рис. 6

Последнюю постановку можно представить в виде таб­лицы - первой таблицы симплекс-метода.

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

Для первой таблицы:

1. в первый столбец записывают у_i - базисные пере­менные, которые находятся в уравнениях слева;

2. свободные переменные x_i, заключенные в скобках, выносят в верхнюю строку таблицы;

3. в остальные столбцы записывают коэффициенты пе­ред свободными переменными;

4. индексная строка есть результат вычитания из нуля коэффициентов перед свободными переменными.

Для последующих таблиц (табл. 6, 7, 8, 9 ):

1) выбирается наименьший отрицательный элемент в ин­дексной строке при отыскании максимума, но наибольший положительный - при отыскании минимума, исключая вектор свободных членов;

2) этот элемент определяет ключевой вектор-столбец, и он вводится в базис;

3) компоненты вектора свободных членов делятся на положительные элементы ключевого столбца;

4) из полученных отношений выбирается наименьшее;

Таблица 6

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

Базис	Свободные члены	Свободные переменные
		х1	х2	х3	х4
y1	16	1	1	1	1
y2	110	6	5	4	3
y3	100	4	6	10	13
Индексная строка	0	-60	-70	-120	-130

Таблица 7

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

Базис	Свободные члены	Свободные переменные
		х1	х2	х3	х4
y1	108/13	9/13	7/13	3/13	0
y2	1130/13	66/13	47/13	22/13	0
x4	100/13	4/13	6/13	10/13	1
Индексная строка	1000	-20	-10	-20	0

Таблица 8

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

Базис	Свободные члены	Свободные переменные
		х1	х2	х3	х4
x1	12	1	7/9	1/3	0
y2	26	0	-1/3	0	0
x4	4	0	2/9	26/39	1
Индексная строка	1240	0	50/9	-40/3	0

Таблица 9

Последняя симплекс-таблица

Базис	Свободные члены	Свободные переменные
		х1	х2	х3	х4
x1	10	1	1/18	0	…
y2	26	0	-1/3	0	…
x4	6	0	13/6	1	…
Индексная строка	1320	0	70/9	0	…

5. вектор-строка, содержащая наименьшее положитель­ное частное, - ключевая и выводится из базиса;

6. на пересечении ключевых строк и столбца находится разрешающий элемент;

7. преобразование матрицы:

1. Каждый элемент ключевой строки делится на раз­решающий элемент. Полученные частные являются эле­ментами ключевой строки следующей таблицы.

2. Ключевой столбец в новой таблице - нули, за ис­ключением разрешающего элемента.

Остальные элементы новой таблицы рассчитыва­ются по схеме:

где Э_н - новый элемент; Э_с - старый элемент; Э₁ - элемент ключевой строки; Э₂ - элемент ключевого столбца; Э_р - разрешающий элемент.

7.4. Если нулевая строка (столбец) содержит нуль, то соот­ветствующий столбец (строка) в новой таблице не изменится.

Пункты 1-7 повторяются до тех пор, пока в индексной строке не останется ни одного- отрицательного элемента при отыскании максимума (но ни одного положительного при отыскании минимума).

Из последней таблицы видно, что:

1. в столбце свободных членов все элементы положи­тельны, это значит, что полученное решение является до­пустимым;

2. в индексной строке все элементы также положитель­ны. Это значит, что полученное решение - оптимально, т.е. максимизирует целевую функцию. При этом опти­мальным планом будут величины: (значит, они базисные); (так как они свободные), целе­вая функция L=1320.

Из этой таблицы также следует, что базисная переменная у₂=26, а свободные переменные у₁=у₃= 0, т.е. в опти­мальном плане резервы трудовых ресурсов и оборудования равны нулю, так как они используются полностью. А резерв ресурсов сырья у₂= 26, что свидетельствует о его излишках.