Симплекс-метод. Пример. Рассмотрим задачу оптимизации плана про­изводства с целью получения максимальной прибыли (табл

Пример. Рассмотрим задачу оптимизации плана про­изводства с целью получения максимальной прибыли (табл. 5).

Таблица 5

Решение. Математическая модель задачи:

В ограничения задачи введем дополнительные перемен­ные y₁, y₂, y₃ перепишем условие задачи в виде уравнений:

Эту подстановку можно переписать в виде рис. 6.

Рис. 6

Последнюю постановку можно представить в виде таб­лицы - первой таблицы симплекс-метода.

Правила составления симплекс-таблиц.

Для первой таблицы:

1) в первый столбец записывают у_i - базисные пере­менные, которые находятся в уравнениях слева;

2) свободные переменные x_i, заключенные в скобках, выносят в верхнюю строку таблицы;

3) в остальные столбцы записывают коэффициенты пе­ред свободными переменными;

4) индексная строка есть результат вычитания из нуля коэффициентов перед свободными переменными.

Для последующих таблиц (табл. 6, 7, 8, 9):

1) выбирается наименьший отрицательный элемент в ин­дексной строке при отыскании максимума, но наибольший положительный - при отыскании минимума, исключая вектор свободных членов;

2) этот элемент определяет ключевой вектор-столбец, и он вводится в базис;

3) компоненты вектора свободных членов делятся на положительные элементы ключевого столбца;

4) из полученных отношений выбирается наименьшее;

Таблица 6

Первая симплекс-таблица

Таблица 7

Вторая симплекс-таблица

Таблица 8

Третья симплекс-таблица

Таблица 9

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

5) вектор-строка, содержащая наименьшее положитель­ное частное, - ключевая и выводится из базиса;

6) на пересечении ключевых строк и столбца находится разрешающий элемент;

7) преобразование матрицы:

7.1. Каждый элемент ключевой строки делится на раз­решающий элемент. Полученные частные являются эле­ментами ключевой строки следующей таблицы.

7.2.Ключевой столбец в новой таблице - нули, за ис­ключением разрешающего элемента.

Остальные элементы новой таблицы рассчитыва­ются по схеме:

где Э_н - новый элемент; Э_с - старый элемент; Э₁ - элемент ключевой строки; Э₂ - элемент ключевого столбца; Э_р - разрешающий элемент.

7.4. Если нулевая строка (столбец) содержит нуль, то соот­ветствующий столбец (строка) в новой таблице не изменится.

Пункты 1-7 повторяются до тех пор, пока в индексной строке не останется ни одного- отрицательного элемента при отыскании максимума (но ни одного положительного при отыскании минимума).

Из последней таблицы видно, что:

1) в столбце свободных членов все элементы положи­тельны, это значит, что полученное решение является до­пустимым;

2) в индексной строке все элементы также положитель­ны. Это значит, что полученное решение - оптимально, т.е. максимизирует целевую функцию. При этом опти­мальным планом будут величины: (значит, они базисные); (так как они свободные), целе­вая функция L =1320.

Из этой таблицы также следует, что базисная переменная у₂= 26, а свободные переменные у₁=у₃= 0, т.е. в опти­мальном плане резервы трудовых ресурсов и оборудования равны нулю, так как они используются полностью. А резерв ресурсов сырья у₂= 26, что свидетельствует о его излишках.

Поиск по сайту: