Симплекс-метод в уравнениях

Рассмотрим симплексные преобразования на конкретном примере

Приведенная математическая модель может быть моделью следующей экономической задачи:

Определить объемы производства двух видов продукции, обеспечивающий наибольший доход, если в производстве используется 3 типа ресурсов, запасы которых соответственно 160, 40, 200. Доход от единицы продукции 10 и 7 соответственно. Нормы расхода ресурсов заданы матрицей . Оставшийся неиспользованным второй ресурс можно реализовать по цене 2.

Обозначая объемы производства продукции , а остатки ресурсов – , получим

Сначала найдем опорный план. Возьмем за базисные переменные , занулим свободные переменные, тогда опорный план будет .

Для анализа этого опорного плана получим общее решение:

Проанализируем опорный план на оптимальность:

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

Будем увеличивать переменную , т.е. вводим ее в список базисных переменных.

При росте x ₁ уменьшаются базисные переменные x ₃ и x ₄. Определим, какая из них первая обратится в 0.

Первая обратится в 0 x ₄ при θ =20.

Следующее опорное решение будет . Это и есть новая угловая точка.

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

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

Минимальное значение из . Получим новое опорное решение .

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

Увеличением улучшить критерий нельзя, любое их увеличение уменьшает критерий.

Значит, найденное нами решение является оптимальным. Значение критерия на этом решении равно 240.

Симплекс-метод в таблицах

Приведенные выше преобразования удобно выполнять в специальных таблицах, называемых симплекс-таблицами.

В симплекс-таблице выделяются следующие блоки:

		Показатели критерия оптимальности (коэффициенты сj целевой функции)
Св	Бп	Шапка матрицы (наименование неизвестных)	b
коэффициенты целевой функции при базисных неизвестных	наименование базисных переменых	Текущая матрица технологических коэффициентов	итоговый столбец (значение базисных переменнных bi)
		Оценочная строка (оценки )	Значение целевой функции

Запишем решение задачи примера из раздела 3.3 в симплекс-таблицах:

Все исходные данные, содержащиеся в математическом условии задачи, переносятся в первую симплексную таблицу. Зануляя свободные переменные, получаем опорный план

В последнюю строку первой симплекс-таблицы заносим критерий в неявной форме

Исключаем из этого критерия базисную переменную x₄ , приводя критерий к виду

Для оптимальности решения все оценки должны быть неотрицательны

– решение не оптимальное, т.к. есть отрицательные оценки. (-6 и -5)

Оценки могут быть вычислены по формулам (12). Произведение

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

=

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

В итоге, мы получаем, что разрешающий столбец – , а разрешающая строка - . Значит из списка базисных выходит переменная и входит переменная .

– решение не оптимальное, т.к. есть отрицательная оценка -2.

- решение оптимальное, т.к. все оценки больше нуля. Очевидно, что увеличить нельзя.

Решим задачу графически.