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

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

Таблица 2.5.

Исходные данные

Ресурсы	Норма расхода ресурсов	Запас ресурса
П1	П2	П3	П4
Трудовые Сырье Оборудование
Прибыль					–
План	x1	x2	x3	x4	–

Решение

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

.

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

Эту постановку можно переписать в следующем виде:

Рис. 2.5

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

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

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

1. В первый столбец записывают y_i – базисные переменные, которые находятся в уравнениях слева.

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

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

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

Для последующих таблиц (2.7, 2.8, 2.9):

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

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

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

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

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

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

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

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

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

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

Новый элемент	=	Старый элемент	–	Элемент ключевой строки . Элемент ключевого столбца
Разрешающий элемент

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

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

Таблица 2.6

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

Базис	Свободные члены	Свободные переменные
x1	x2	x3	x4
y1
y2
y3
Индексная строка		– 60	–70	–120	–130

Таблица 2.7

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

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

Таблица 2.8

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

Базис	Свободные члены	Свободные переменные
x1	x2	x3	x4
x1			7/9	1/3
y2			–1/3
x4			2/9	26/39
Индексная строка			50/9	– 40/3

Таблица 2.9

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

Базис	Свободные члены	Свободные переменные
x1	x2	x3	x4
x1			1/18		...
y2			–1/3		...
x4			13/6		...
Индексная строка			70/9		...

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

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

2) В индексной строке все элементы также положительны. Это значит, что полученное решение – оптимально, то есть максимизирует целевую функцию. При этом оптимальным планом будут величины: x ₁⁰ = 10, x ₃⁰ = 6 (значит они базисные); x ₂⁰ = x ₄⁰ = 0 (так как они свободные), целевая функция L = 1320.

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