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

Этап 5. Построение нового опорного плана.

Переход к новому осуществляется в результате пересчета симплексной таблицы методом Жордана - Гаусса.

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

 

Если в ведущем столбце есть нулевой коэффициент, то соответствующая ему строка переносится в следующую итерацию без изменений (строка 4 первой итерации) (см.табл.).

Кроме этого на втором шаге свободная переменная, соответствующая ведущему столбцу (x₁), заменяет базисную переменную, соответствующую ведущей строке ( x₅) (см.табл.) вместе со своей оценкой.

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

Например, нам необходимо найти новое значение коэффициента a¹₅₂ =14 на втором шаге (см.табл.).

 

Прямоугольник для него будет:

 

Также находим значения всех коэффициентов на втором шаге (см.табл.).

 

 

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

- выпускается 100 кг сливочного мороженого (x₁=100); шоколадное не выпускается (x₂=0);

- избыток наполнителя составляет 325 кг (x₄=325);

- спрос на сливочное мороженое удовлетворяется полностью (уравнение 3 системы 3.6 ( x₁-x₂=100; 100-0=100, т.е. x₅=0);

- избыток спроса на шоколадное мороженое составляет 350 кг (x₆=350);

- доход составляет 1600 руб.

Указанные числа записаны в столбце свободных членов на втором шаге симплекс-таблицы. Как видно, данные этого столбца свободных членов по-прежнему представляют собой параметры рассматриваемой задачи, хотя они и претерпели значительные изменения. Изменились и данные других столбцов, а их экономическое содержание стало более сложным. Так, например, возьмем данные столбца переменной х_{2 .} Число ( -1) показывает, на сколько увеличится выпуск сливочного мороженого, если запланировать выпуск 1 кг. шоколадного мороженого. Число 30 в строке целевой функции показывает, что если будет запланирован выпуск шоколадного мороженого в количестве 1 кг., то это обеспечит увеличение дохода (значения целевой функции) на 30 руб.: 1600 +30=1630. Одновременно на 1 кг. вырастет выпуск сливочного мороженого, т.е. 16*101 + 14*1=1630 руб.

Числа 1, 3; 1, 2; 1 показывают соответственно, что при этом плане (х₁=101 и х₂=1) потребуется дополнительно увеличить расход молока на 1, 3 кг. , наполнителя – на 1, 2 кг. и на 1 кг. уменьшить лимит спроса на шоколадное мороженое:

320 – (400 – (0, 8*101 + 0, 5*1)) = 320 – 318, 7 = 1, 3

3 25 – (365 – (0.48101 + 0.8*1)) = 325 – 323.8 = 1, 2

350 – (350 – (1*1)) = 350 – 349 = 1

Несколько иное экономическое содержание имеют числа, записанные в столбце при переменной х_5. Число 1 во 3-й строке 2-го шага этого столбца показывает, что изменение разницы в спросе между сливочным и шоколадным мороженым на 1 кг. позволило бы увеличить выпуск сливочного мороженого на 1 кг.: ((100 + 1/1) – 100)) = 1. Одновременно, потребовалось бы дополнительно 0, 8 кг молока и 0, 4 кг наполнителя (т.е.

избыток этих ресурсов сократился бы соответственно до 320 – 0, 8 = 319, 8 кг.

и 325 – 0, 4 = 324, 6 кг.)

Увеличение выпуска сливочного мороженого на 1 кг. приведет к росту дохода на 16 руб (строка 5) – 16*(100 + 1) = 1616 руб.

 

Далее возвращаемся к этапу 3 и проверяем полученный план на оптимальность. Из строки целевой функции видно, что она содержит положительный коэффициент c ₅₂ = 30 (см.табл.), т.е. план не оптимальный и его можно улучшить путем введения в план выпуск шоколадного мороженого (x₂), так как любое значение x₂> 0 увеличивает значение целевой функции.

Выполняя последовательно этапа 3-5, получаем окончательную симплексную таблицу. В этой таблице все коэффициенты в строке целевой функции отрицательные или равные нулю, т.е. полученный план оптимален, т.е. нет ни одной переменной, введение которой в план увеличилось бы значение целевой функции в 9200 руб.

Оптимальное решение:

x₁=312, 5; x₂=300; x₃=x₄ =0; x₅= 87, 5 x₆ =312, 5; F(x)=9200.

Последовательность решения ЗЛП симплекс- методом

 

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: