Введение в симплексный алгоритм

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

Решение оптимизационных задач методами линейного программирования

1. Построение линейных оптимизационных моделей:

• задача распределения ресурсов,

• задача о выполнении контракта,

• транспортная задача.

2. Алгебраическое представление линейных оптимизационных задач

3. Геометрическое представление линейных оптимизационных задач

4. Симплексный метод решения оптимизационных задачи линейного программирования (ЗЛП)

Задача о выполнении контракта

Фирма производит два типа химикатов. На предстоящий месяц она заключила контракт на поставку химиката типа 1 в количестве 100 т, химиката типа 2 – 120 т. Производство фирмы ограничено ресурсом времени работы двух химических реакторов. Каждый тип химикатов должен быть обработан сначала в реакторе 1, а затем в реакторе 2. Фонд рабочего времени, имеющийся у реактора 1 в следующем месяце составляет 300 часов, у реактора 2 – 400 часов. На обработку одной тонны химиката типа 1 в реакторе 1 необходимо 4 часа, в реакторе 2 – 3 часа. Для химиката типа 2 эти показатели составляют соответственно 2 и 6 часов. Затраты на производство химиката типа 1 равны 35 у.е. за тонну, химиката типа 2 – 56 у.е. за тонну.

Из-за ограниченных возможностей, связанных с существующим фондом времени на обработку химикатов в реакторах, фирма не имеет достаточных мощностей, чтобы выполнить обязательства по контракту. Поэтому фирма приняла решение купить какое-то количество этих химикатов у других производителей, чтобы использовать эти закупки для выполнения контракта. Цена других производителей на химикат типа 1 равна 45 у.е. за тонну, типа 2 – 65 у.е. за тонну.

Фирма должна принять решение: сколько химикатов каждого типа производить у себя, а сколько — закупать со стороны для того, чтобы выполнить контракт с минимальными издержками.

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

• Интерес представляют, прежде всего, значения целевой функции в вершинах многогранника допустимых решений.

• Для нахождения оптимального решения необходимо вычислить значения целевой функции в вершинах многогранника допустимых планов и выбрать ту, где значение целевой функции будет наилучшим

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

• Метод получил такое название после того, когда был применен в решении задачи с ограничением x₁ + x₂ +... + x_n £ 1, которое определяет в n-мерном евклидовом пространстве обобщенный полиэдр - симплекс, отсекающий на координатных осях единичные отрезки.

4. Симплексный метод решения ЗЛП

Шаг 1. Выбираем из уравнений-ограничений m переменных, задающих допустимое пробное решение.

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

Шаг 3. Находим предельное значение новой базисной переменной, то есть определяем уравнение-ограничение, из которого она войдёт в базис.

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

Дата добавления: 2014-01-20