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

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

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

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

 

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

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

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

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

 

 

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

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

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

 

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

 

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

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

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

При решении задач на максимум целевой функции наличие в целевой строке отрицательных чисел указывает на возможность начала или продолжения решения задачи. Порядок решения таков: из отрицательных чисел целевой строки выбирается наибольшее по модулю. Столбец, в котором оно находится, принимается за ключ (или разрешающий) и для удобства расчётов выделяется. В нашем примере таким столбцом будет X1, имеющий в целевой строке наибольшую по модулю величину (-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

 

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

 

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

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

В столбцах P0 и Cj занимают место вводимая в план неизвестная x1 с прибылью 28.

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

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

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

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

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

 

 

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

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

 

 

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

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