Экономико-математическая модель в символическом виде

Система ограничений:

Целевая функция (суммарный доход)

Условия неотрицательности переменных

Символическая модель, наполненная численной информацией, будет иметь следующий вид:

Система ограничений:

Целевая функция (суммарный доход)

Условия неотрицательности переменных

Решение задачи

Для решения задачи симплекс-методом неравенства преобразуются в эквивалентные равенства путём добавления в каждое неравенство по одному дополнительному неизвестному с коэффициентом +1 и нулевым уравнением прибыли. Для удобства расчётов левые и правые части уравнения меняются местами. В этом случае исходные неравенства примут вид симплексных уравнений:

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

Сj	P0	X0
X1	X2	X3	X4	X5	X6
	X4
	X5
	X6
F		-24	-20	-28

В столбцах таблицы записывают: в первом (С_j) – прибыль единицы продукции, которая вводится в план выпуска; во втором (P₀) – свободные величины; в остальных – коэффициенты при неизвестных уравнений. В верхней части этих столбцов отражаются коэффициенты неизвестных целевой функции.

В нижней строке (целевой) записываются получаемые расчётным путём показатели: в столбце X₀ – суммарная прибыль планового выпуска, в остальных столбцах прибыль единицы продукции с отрицательным знаком.

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

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

I итерация

Сj	P0	X0
X1	X2	X3	X4	X5	X6
	X4		5/4	11/4				-1/4
	X5		7/4	5/4				-3/4
	X6		3/4	1/4				1/4
F		-3	-13

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

Наименьшее отношение 50 имеет строка X₄. Она и будет ключевой. Ключевой элемент 28.

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

В столбцах P₀ и C_j занимают место вводимая в план неизвестная x₁ с прибылью 28.

Остальные элементы преобразуются по следующему правилу:

§ для преобразуемого элемента в его столбце находят элемент ключевой строки, а в его строке – элемент ключевого столбца;

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

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

Следуя этому правилу, преобразование элементов столбцов будет:

Включение на первой итерации в план неизвестной x₁ (выпуска продукции П вида) обеспечит сумму прибыли 1400 рублей.

Решение задачи продолжается, так как в целевой строке два отрицательных элемента. Наибольший по модулю элемент (-13). Он находится в столбце X₃, который принимается за разрешающий, а ключевой строкой будет X₄.

Элементы таблицы преобразуются в том же порядке по изложенному правилу П записываются в новую таблицу.

II итерация

Сj	P0	X0
X1	X2	X3	X4	X5	X6
	X2		5/11			4/11		-1/11
	X5		13/11			-5/11		-7/11
	X3		7/11			-1/11		3/11
F		32/11			52/11		64/11