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

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

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

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

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

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

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

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

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

Пример:Для производства двух видов изделий А и В завод должен использовать три типа ресурсов электроэнергия, сырье, оборудование, запасы которых на планируемый период составляют соответственно 56, 80, 117 условных единиц.

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

Вид исходного продукта	Расход продуктов на 1 т.красок		Суточные запасы
A	1	2	56
B	2	1	80
C	3	1	117
Оптовые цены на 1 т	3	2

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

Обозначим через Х₁,Х₂, количество единиц соответствующей продукции. Тогда экономико-математическая модель задачи будет следующая: найти максимум функции

F= 3*Х₁+ 2*Х₂max

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

1.1

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

После введения добавочных переменных получим систему уравнений:

1.2

Нужно найти такое допустимое базисное решение системы 1.2, которое бы максимизировало целевую функцию F, т.е. необходимо найти оптимальное решение задачи. Так как система ограничений состоит из трех независимых уравнений с пятью переменными, то число основных (базисных) переменных должно равняться трем, а число неосновных – двум. Для решения задачи симплексным методом, прежде всего, нужно найти любое базисное решение. В условиях данной задачи оно может быть найдено без труда. Для этого достаточно принять за основные добавочные переменныех₃, х₄, х₅. Так как коэффициенты при этих переменных образуют единичную матрицу, то отпадает необходимость вычислять определитель (определитель единичной матрицы равен 1, т.е. отличен от нуля).

Положив неосновные (свободные) переменные х₁, х₂, равными нулю, получим базисное решение (0; 0; 20; 26; 14), которое оказалось допустимым. Поэтому в условиях данной задачи отпадает надобность в применении первого этапа симплексного метода. Переходим сразу ко второму этапу, т.е. к поискам оптимального решения.

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

бп	сч	х1	х2	х3	х4	х5
х3	56	1	2	1	0	0	56
х4	80	2	1	0	1	0	40
х5	117	3	1	0	0	1	39
F	0	-3	-2	0	0	0

.

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

бп	сч	х1	х2	х3	х4	х5
х3	17	0	1,666667	1	0	-0,33333	10,2
х4	2	0	0,333333	0	1	-0,66667	6
х1	39	1	0,333333	0	0	0,333333	117
F	117	0	-1	0	0	1

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

бп	сч	х1	х2	х3	х4	х5
х3	7	0	0	1	-5	3	2,333333
х2	6	0	1	0	3	-2	-3
х1	37	1	0	0	-1	1	37
F	123	0	0	0	3	-1

IV шаг.Основные переменные X₁, X₂, X₅. Составляем новую симплекс-таблицу. Находим разрешающий элемент:

бп	сч	х1	х2	х3	х4	х5
х5	2,333333	0	0	0,333333	-1,66667	1
х2	10,66667	0	1	0,666667	-0,33333	0
х1	34,66667	1	0	-0,33333	0,666667	0
F	125,3333	0	0	0,333333	1,333333	0

Эта таблица является последней, по ней читаем ответ задачи. Оптимальным будет решение (34,6;10,6;0;0;2,3) при котором Z_max= 125,3 т.е. для получения наибольшей прибыли, равной 524денежных единиц.

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