Анализ симплекс-таблиц

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

При оперативном управлении решается достаточно широкий и важный круг вопросов, которые возникают при ежедневном обеспечении производственного процесса. Мы рассмотрим лишь те вопросы оперативного управления, которые могут быть решены с помощью моделей, уже составленных при планировании. «Что будет, если пять человек из числа трудовых ресурсов отвлекут на другие работы? Что будет, если сырья поставят на 20% меньше? Какую продукцию следует выпускать, если изменились цены?» Рассмотрим, как находить ответы на эти вопросы на конкретном примере.

Допустим, предприятие должно выпускать продукцию четырех видов: П₁,П₂,П₃,П₄, используя для этого три вида ресурсов. Располагаемые ресурсы, нормы расходов материалов и прибыль приведены в Таблице 5А.

ТАБЛИЦА 5А

ìx₁ + x₂ + x₃+ x₄ £ 16

ï6x₁ + 5x₂ + 4x₃+ 3x₄ £ 110

(5.20) í4x₁ + 6x₂ + 10x₃+ 13x₄ £ 100

îx_j ³ 0, j ³ 1,4.

F = 60x₁ + 70x₂ + 120x₃ + 130x₄ ® max

От системы неравенств (5.20) перейдем к системе уравнений. Для этого, в каждое неравенство добавим по одной дополнительной переменной: y_i ³ 0, i ³ 1,m. Тогда получим систему уравнений:

ìx₁ + x₂ + x₃+ x₄ + y₁ =16

ï6x₁ + 5x₂ + 4x₃+ 3x₄ + y₂ =110

(5.21) í4x₁ + 6x₂ + 10x₃+ 13x₄ + y₃ =100

îx_j ³ 0, j = 1,4; y_i ³ 0, i = 1,3.

F = 60x₁ + 70x₂ + 120x₃ + 130x₄ ® max

Затем перепишем систему (5.21) в следующем виде:

ì y₁ =16 - (x₁ + x₂ + x₃+ x₄)

ï y₂ =110 - (6x₁ + 5x₂ + 4x₃+ 3x₄)

(5.22) í y₃ =100 - (4x₁ + 6x₂ + 10x₃+ 13x₄)

îF = 0 - (-60x₁ - 70x₂ - 120x₃ - 130x₄)

Систему (5.22) можно представить в виде Таблицы 5В, которую составляют следующим образом: свободные переменные, заключенные в скобки, выносят в верхнюю строку таблицы. В остальные столбцы записывают свободные члены и коэффициенты перед свободными переменными. Эта, так называемая симплекс таблица, служит основой для решения задач линейного программирования. В этой таблице переменные, являющиеся свободными, в данном случае x₁, x₂, x₃, x₄ по условию равны 0. Поскольку свободные переменные равны 0, то из системы (5.22) видно, что базисные переменные y₁, y₂, y₃, а также целевая функция F, которую записывают снизу, равны свободным членам. Значит y₁=16, y₂=110, y₃=100, F=0.

ТАБЛИЦА 5В

Напомним, что в системе (5.21) общее число переменных N=n+m, где n - число основных переменных, m - число дополнительных переменных. Все переменные можно подразделить с одной стороны на основные и дополнительные, а с другой - на базисные и свободные.

þ Свободными переменными будем называть такие, которые равны 0.

Из теории известно, что n переменных в допустимом решении должны быть равны 0 , т.е. столько же переменных, сколько и основных. Однако, из этого ни в коей мере не следует, что нулю равны все основные переменные. Если из общего числа переменных N=n+m будут свободными n переменных, то очевидно, что m переменных будут базисными, т.е. не равны нулю. С учетом введенных терминов можно сказать, что целью решения задачи ЛП является нахождение базисных и свободных переменных.

Для задачи ЛП, записанной в виде симплекс таблицы, можно сформулировать признаки допустимого и оптимального решений. Решение является допустимым, если в симплекс таблице в столбце свободных членов все значения, относящиеся к базисным переменным будут неотрицательными. Оптимальное значение, как мы знаем, может либо минимизировать, либо максимизировать значение целевой функции. В связи с этим, для оптимальных значений есть два признака: один для случая минимизации целевой функции, другой - для случая максимизации.

Целевая функция имеет минимальное значение, если, во-первых, решение является допустимым, т.е. свободные члены будут неотрицательными, а во=вторых, все элементы в строке целевой функции (свободный член не рассматривается) будут неположительными. При этом целевая функция равна свободному члену. Таким образом можно сделать вывод, что в Табл. 5В получено оптимальное решение нашей задачи для случая минимизации целевой функции.

Действительно, если x₁= x₂= x₃= x₄ = 0 мы никакой продукции не выпускаем и при этом прибыль F=0. Дополнительные переменные y₁, y₂, y₃, показывающие объем неиспользованных ресурсов, равны, соответственно: 16, 110,100, т.е. тому ресурсу, который имеется в наличии. В самом деле, мы ничего не выпускаем, но не тратим ресурсы. Следовательно, данные в Табл. 5В соответствуют такой вершине ОДР, в которой целевая функция принимает минимальное значение.

Признак максимизации целевой функции формируется следующим образом: целевая функция имеет максимальное значение, если, во-первых, решение является допустимым, а во-вторых, все элементы в строке целевой функции (свободный член не рассматривается) будут неотрицательными.

Поскольку Табл. 5В не удовлетворяет данному признаку, то необходимо перейти к другой вершине ОДР. Переход от одной вершины к другой, производится по определенному алгоритму симплекс-метода, который заключается в обмене переменных.

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

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

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

Таким образом, ведущим столбцом будет столбец х₃, а ведущей строкой будет строка y₃. На пересечении ведущего столбца и ведущей строки будет разрешающий элемент. В нашем случае это число 10. Таким образом, ведущей строкой будет строка y₃, обозначим ее через A_r. Ведущим столбцом будет столбец х₄, обозначим его через A_k, и, следовательно, разрешающий элемент A_rk = 10.

Теперь приступаем к составлению второй таблицы. В этой таблице элементы направляющей строки равны этому элементу ведущей строки, деленному на разрешающий элемент, и находятся в соотношении:

Элементы любой другой строки j находят из соотношения:

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

После этих преобразований новая симплексная таблица после первой итерации примет вид Таблицы 5С.

ТАБЛИЦА 5С

В Табл. 5С в индексной строке только один отрицательный элемент, следовательно, ведущим столбцом будет х₁, а ведущую строку определяем по наименьшему отношению:

Т. о. Ведущей строкой будет y₁, а разрешающим элементом число 0,6.

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

ТАБЛИЦА 5D

Из этой таблицы видно, что в столбце свободных членов все элементы положительные. Значит решение является допустимым. В строке целевой функции все элементы тоже положительные. Следовательно, это решение оптимальное и максимизирует целевую функцию. При этом оптимальным планом будут следующие величины: х₁^*=10, х₃^*=6 (значит, они - базисные) и х₂^*=х₄^*=0 (т.к. они свободные). При этом целевая функция F=1320.

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