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

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

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

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

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

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

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

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

Пример 2. (Задача об использовании сырья) Для производства четырех видов изделий A₁, A₂, A₃, A₄ завод должен использовать три вида сырья I, II, III, запасы которого на планируемый период составляют соответственно 1000, 600 и 150 условных единиц.

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

Виды сырья	Запасы сырья	Технологические коэффициенты
		А1	А2	А3	А4
I	1000	5	1	0	2
II	600	4	2	2	1
III	150	1	0	2	1
Прибыль от реализации		6	2	2.5	4

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

Обозначим через х1,х2,х3,х4 количество единиц соответствующих изделий: А1, А2, А3, А4. Тогда экономико-математическая модель задачи будет следующая: найти максимум функции

F = 6x₁ + 2x₂ + 2.5x₃ + 4x₄ ® max

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

(4.3)

                          (2.12)

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

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

(4.4)

              (2.13)

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

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

Базисные переменные	Свобод. члены	X5	X6	X7	X1	X2	X3	X4
X5	1000	1	0	0	5	1	0	2
X6	600	0	1	0	4	2	2	1
X7	150	0	0	1	1	0	2	1
F	0	0	0	0	-6	-2	-2.5	-4

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

.

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

Базисные переменные	Свобод. члены	X5	X6	X7	X1	X2	X3	X4
X5	250	1	0	-5	0	1	-10	-3
X6	0	0	1	-4	0	2	-6	-3
X1	150	0	0	1	1	0	2	1
F	900	0	0	6	0	-2	9.5	2

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

.

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

Базисные переменные	Свобод. члены	X5	X6	X7	X1	X2	X3	X4
X5	250	1	-0.5	-3	0	0	-7	-1.5
X2	0	0	0.5	-2	0	1	-3	-1.5
X1	150	0	0	1	1	0	2	1
F	900	0	1	2	0	0	3.5	-1

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

.

IV шаг. Основные переменные X₂, X₄, X₅. Переходим к следующей таблице:

Базисные переменные	Свобод. члены	X5	X6	X7	X1	X2	X3	X4
X5	475	1	-0.5	-1.5	1.5	0	-4	0
X2	225	0	0.5	-0.5	1.5	1	0	0
X4	150	0	0	1	1	0	2	1
F	1050	0	1	3	1	0	5.5	0

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