Симплексный метод решения задач линейного программирования

Симплекс – метод

Симплекс – метод – универсальный метод для решения задач линейного программирования, представленных в канонической форме.

В канонической форме записи все переменные неотрицательны, ограничениями являются уравнения, и требуется найти такие значения переменных x_j, j=1,n, при которых целевая функция имеет максимум:

Переход к канонической форме записи можно осуществить с помощью следующих действий:

1. Ограничения вида «». В этом случае, для перехода к уравнению в левую часть неравенства добавляют дополнительную неотрицательную переменную.

2. Ограничения вида «» . В этом случае, для перехода к соответствующему уравнению, вычитают из левой части дополнительную неотрицательную переменную.

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

4. Если в задаче требуется найти минимум f , то заменяя f на – f, переходят к задаче максимизации, так как .

Алгоритм симплекс- метода

1. Приводим математическую модель задачи к каноническому виду ( в случае неканонической).

2. Находим начальное решение и проверяем его на оптимальность.

Получение начального решения:

Выбираются m переменных, называемых базисными и обладающих следующим свойством: они входят с коэффициентом 1 только в одно уравнение и с коэффициентом 0 в остальные уравнения системы :

(1)

Остальные n-m переменных называются свободными.

Все свободные переменные полагаются равными нулю, а базисные переменные – равные правым частям соответствующих ограничений системы (1).

Если все , то начальное решение является допустимым.

3. Выражение функции f только через свободные переменные:

.

4. Проверка решения на оптимальность.

Для этого составляется симплекс- таблица:

Для проверки решения на оптимальность просматривается последняя f-строка:

4.1 Если коэффициенты, стоящие при свободных переменных неотрицательны, то полученное решение оптимально.

4.2 Если все эти коэффициенты положительны, то полученное решение единственно.

4.3 Если среди неотрицательных коэффициентов встречается хотя бы один нулевой, то задача имеет бесконечное множество решений.

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

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

5. Получение нового решения.

5.1 Выбор переменной, вводимой в список базисных переменных.

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

5.2. Выбор переменной, выводимой из списка базисных переменных.

Находят отношение элементов столбца свободных членов к элементам разрешающего столбца. При делении на отрицательный элемент и 0 результат полагают равным +∞. Среди отношений находят минимальное. Строка соответствующая минимальному отношению, называется разрешающей. Базисная переменная, стоящая в этой строке, выводится из списка базисных переменных. Элемент, стоящий на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом.

5.3.Выполнение симплекс-преобразования и переход к новой симплекс- таблице.

Переписываем разрешающую строку, разделив ее на ключевой элемент; остальные коэффициенты таблицы находим по правилу «прямоугольника»: новый элемент = (старый элемент)×(разрешающий элемент) - × .

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

Получаем новое опорное решение, которое снова проверяем на оптимальность и т.д. по рассмотренному алгоритму, пока не получим оптимальное решение.

Пример.

Анализ эффективности использования производственного потенциала предприятия.

Предприятие располагает тремя производственными ресурсами (сырьем, электроэнергией, оборудованием) и может организовать производство продукции двумя различными способами. Расход ресурсов за один месяц и общий ресурс при каждом способе производства даны в таблице ( в у.е.)

При первом способе производства предприятие выпускает за 1 месяц – 3 тыс. изделий, при втором – 4 тыс. изделий.

Сколько месяцев должно работать предприятие каждым из этих способов, чтобы при наличных ресурсах обеспечить максимальный выпуск продукции?

Решение: Пусть - время работы предприятия 1-м способом, - вторым способом.

Математическая модель задачи имеет вид:

max, при ограничениях:

Приведем задачу к каноническому виду:

max, при ограничениях:

Решение:

1. Составляем симплекс – таблицу 1-го шага:

Решение (0;0;4;3;8), L(x) = 0

Видим, что в последней строке таблицы есть отрицательные числа - переходим к пункту 2.

2)Выбираем столбец, содержащий максимальное положительное число – 4 и отмечаем его. Переходим к пункту 3.

3)Делим, свободные члены на соответствующие положительные числа из выделенного столбца и выбираем наименьшее частное:

min=(4;3;2)=2

Отмечаем строку таблицы, которая соответствует наименьшему частному. Выделяем разрешающий элемент равный 2.

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

Переходим снова к шагу 1.

min=(4;3;2)=2

Все коэффициенты в строке f положительные, значит оптимальное решение получено. X опт = (2;1;0;0;3) , f= 3*2+4=10. Таким образом, по 1-ому способу предприятие должно работать 2 месяца, по 2-ому – 1 месяц, при этом максимальный выпуск продукции составит 10 тыс. рублей.

Контрольные задания по теме

«Симплекс – метод»

Предприятие рекламирует свою продукцию с использованием 4-ех источников массовой информации: телевидения, радио, газет и расклейки объявлений. Анализ рекламной деятельности в прошлом показал, что эти средства приводят к увеличению прибыли соответственно на a, b, c и d у .е. в расчете на 1 у.е., затраченную на рекламу. На рекламу выделено N у.е. Администрация предприятия не намерена тратить на телевидение более 40%, а на радио и газеты – не более 50% общей суммы выделенных средств. Как следует предприятию организовать рекламу, чтобы получить максимальную прибыль?