Порядок работы с симплекс таблицей

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

Алгоритм перехода к следующей таблице такой:

- просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;

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

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

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

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

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

- в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.

- столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же.

- строка, у которой в ключевом столбце имеется 0, в новой таблице будет такой же.

- в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:

В результате получают новую симплекс-таблицу, отвечающую новому базисному решению.

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

Рассмотрим порядок решения задачи с помощью симплекс-таблиц на примере.

Пример 1 Задача об использовании сырья

Для производства четырех видов изделий A1, A2, A3, A4 завод должен использовать три вида сырья I, II, III, запасы которого на планируемый период составляют соответственно 1000, 600 и 150 условных единиц. В приведенной ниже таблице даны технологические коэффициенты, т.е. расход каждого вида сырья на производство единицы каждого изделия и прибыль от реализации единицы изделия каждого вида.

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

Составим математическую модель задачи

Обозначим через x1, x2, x3, x4 количество единиц соответствующих изделий: A1, A2, A3, A4. Тогда экономико-математическая модель задачи будет следующая: найти максимум функции

при выполнении системы ограничений

Для обращения системы ограничений-неравенств в систему уравнений прибавим к левой части каждого неравенства добавочные неотрицательные переменные x5, x6, x7. Эти добавочные переменные в условиях данной задачи имеют конкретное экономическое содержание, а именно: объем остатков сырья каждого вида после выполнения плана выпуска продукции.

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

Для решения задачи симплексным методом, прежде всего, нужно найти любое базисное решение. В условиях данной задачи оно может быть найдено без труда. Для этого достаточно принять за основные добавочные переменные x5, x6, x7. Так как коэффициенты при этих переменных образуют единичную матрицу, то отпадает необходимость вычислять определитель (определитель единичной матрицы равен 1, т.е. отличен от нуля).

Положив неосновные (свободные) переменные x1, x2, x3, x4 равными нулю, получим базисное решение (0; 0; 0; 0; 1000; 600; 150), которое оказалось допустимым. Поэтому в условиях данной задачи отпадает надобность в применении первого этапа симплексного метода. Переходим сразу ко второму этапу, т.е. к поискам оптимального решения.

I шаг. Основные переменные x5, x6, x7. Составляем первую симплекс-таблицу. Находим разрешающий элемент.

Базисное решение (0; 0; 0; 0; 1000; 600; 150).

II шаг. Основные переменные x1, x5, x6. Составляем новую симплекс-таблицу. Снова находим разрешающий элемент.

Базисное решение (150; 0; 0; 0; 250; 0; 0).

III шаг. Основные переменные x1, x2, x5. Составляем новую симплекс-таблицу. Находим разрешающий элемент.

Базисное решение (150; 0; 0; 0; 250; 0; 0).

IV шаг. Основные переменные х2, х4, х5. Переходим к следующей таблице.

Эта таблица является последней, по ней читаем ответ задачи. Оптимальным будет решение (0; 225; 0; 150; 475; 0; 0) при котором Fmax =1050, т.е. для получения наибольшей прибыли, равной 1050 денежных единиц, предприятие должно выпустить 225 единиц продукции вида A2, 150 единиц продукции вида A4, (продукцию вида A1 и A3 в данных условиях производить не выгодно) при этом сырье типа II и III будет использовано полностью, а 475 единиц сырья типа I останутся неизрасходованными.

Конец примера

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

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

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

(2.16)

Этому способу разбиения переменных на основные и неосновные соответствует базисное решение (k1, k2,..., km, 0, 0,..., 0). Рассмотрим общий случай, когда это решение является недопустимым. От полученного базисного решения следует сначала перейти к какому-нибудь допустимому базисному решению. Причем не обязательно, чтобы этот переход осуществлялся сразу, за один шаг.

По предположению исходное базисное решение недопустимо. Следовательно, среди свободных членов системы ограничений (2.16) имеется хотя бы один отрицательный (число отрицательных свободных членов этой системы совпадает с числом отрицательных компонент исходного базисного решения). Пусть им является свободный член i-го уравнения ki, т. е. основная переменная xi в соответствующем базисном решении отрицательна.

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

Здесь может быть три исхода:

1. в i-м уравнении системы (2.16) нет основных переменных с положительными коэффициентами, т. е. все коэффициенты bi, m+j (как и свободный член ki) отрицательны. В этом случае система ограничений несовместна, она не имеет ни одного допустимого решения, а следовательно, и оптимального;

2. в i-м уравнения имеется одна переменная xm+j, коэффициент b при которой положителен. В этом случае именно эта переменная переводится в основные;

3. в i-м уравнении имеется несколько переменных с положительными коэффициентами bi, m+j. В этом случае в основные можно перевести любую из них.

Далее необходимо установить, какая основная переменная должна быть переведена в число неосновных на место переводимой в основные. В неосновные переводится та основная переменная, которая первой обратится в нуль при возрастании от нуля неосновной переменной, переводимой в основные. Иными словами, пользуемся тем же правилом, которое было установлено ранее. Находятся отношения свободных членов к коэффициентам при переменной, переводимой в основные, из всех уравнений, где знаки свободных членов и указанных коэффициентов противоположны, берется абсолютная величина этих отношений и из них выбирается наименьшая (если в некоторых уравнениях знаки свободных членов и указанных коэффициентов совпадают или в каких-то уравнениях переменная, переводимая в основные, отсутствует, то указанное отношение считается равным).

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

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

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

Итак, мы получим новое, улучшенное базисное решение, которое ближе к области допустимых решений системы ограничений. Если оно недопустимое, то к нему следует применить ту же схему еще раз. В результате через конечное число шагов мы получим допустимое базисное решение. Как только будет найдено допустимое базисное решение, переходят ко второму этапу симплексного метода, сущность которого рассмотрена при решении задачи примера 2.4.1.

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