Материал: Разработка математической модели по формированию производственной программы

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

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

Можно доказать, что экстремум (минимум или максимум) целевой функции всегда достигается при значениях переменных X₁,₂,...,X_n, соответствующих одной из угловых точек ОДР. Другими словами, оптимальное решение всегда находится в угловой точке ОДР.

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

Проверяются смежные с ней угловые точки ОДР. Под смежной здесь понимается угловая точка, расположенная на той же границе ОДР, что и текущая угловая точка (для двухмерной ОДР - на той же стороне многоугольника, для трехмерной - на том же ребре многогранника, и т.д.). Если ни в одной из смежных угловых точек значение целевой функции не улучшается, то решение задачи завершается; текущая угловая точка ОДР соответствует оптимальному решению задачи. Если имеются смежные угловые точки ОДР, для которых значение целевой функции улучшается, то выполняется переход в ту из них, для которой достигается наиболее быстрое улучшение значения целевой функции.

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

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

. Задача линейного программирования приводится к стандартной форме.

. Определяется начальное допустимое решение (начальная угловая точка ОДР).

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

Реализация симплекс-метода существенно различается в зависимости от вида математической модели задачи. В данном разделе рассматривается реализация симплекс-метода для случая, когда математическая модель задачи состоит только из ограничений "меньше или равно", и целевая функция подлежит максимизации (как в примере 2.1). Реализация симплекс-метода для задач с математической моделью любого вида рассматривается в разделе 3.

1.6 Симплекс метод в общем виде

Требуется найти максимум целевой функции:

(1)

При ограничениях:

(2)

И условиях неотрицательности:

_i ≥ 0, i=1, 2, ..., n (3)

Из системы (2) видно, что если за свободные неизвестные принять х₁, х₂ и положить их равными нулю, то базисные неизвестные х₃, х₄, х₅ будут равны правым частям системы. в результате получаем план:

х₁=0, х₂=0, х₃=b₁, x₄=b₂, x₅=b₃ (4)

Для которого целевая функция равна

(5)

Выразим из (2) базисные неизвестные х₃, х₄, х₅ через свободные х₁, х₂:

(6)

Подставим (6) в целевую функцию (1) и после приведения подобных членов будем иметь:

= (c1-c3a11-c4a21-c5a31)x1 + (c2-c3a12-c4a22-c5a32)x2 + c3b1 + c4b2 + c5b3. (7)

Если коэффициенты перед х₁, х₂ в (7) окажутся отрицательными, то целевую функцию нельзя увеличить, переводя эти свободные неизвестные в базисные, то есть давая им какие-то положительное значения. Отрицательность коэффициентов перед неизвестными в (7) есть признак того, что найдено оптимальное решение. Коэффициенты перед свободными неизвестными в выражении для целевой функции принято называть оценками. Введем обозначения:

= c3a11 + c4a21 + c5a31, Z2 = c3a12 + c4a22 + c5a32. (8)

В этих обозначениях условия максимальности запишутся:

- Z1 < 0, c2 - Z2 < 0, (9)

Пусть условии оптимальности (9) не выполнены, а именно пусть, для определенности, коэффициент перед х₁ в (7) положителен, тогда, увеличивая х₁, мы увеличим целевую функцию по сравнению с ее значением (5). Посмотрим, насколько может быть увеличена переменная х₁по сравнению с нулем, при условии, что х₂ остается свободной, то есть будет иметь неизменное значение х₂=0. Из (6) видно, что увеличение х₁ будет вести к уменьшению х₃, х₄, х₅, если коэффициенты перед х₁ в (6) отрицательны. Увеличивать х₁ можно лишь до значения, при котором первая из неизвестных х₃, х₄, х₅ обратится в нуль. Положив нулю левые части (6), получим три уравнения:

= b1 - a11x1, 0 = b2 - a21x1, 0 = b3 - a31x1.

Если положить:

(10)

то только одна неизвестная из х₃, х₄, х₅ обратится в нуль, то есть станет свободной, а остальные останутся положительными. Предположим, что это будет х₃, тогда будем иметь в качестве свободных неизвестных х₂, х₃ и в качестве базисных х₁, х₄, х₅.

Для удобства дальнейших вычислений желательно преобразовать систему ограничений к виду (2), который характерен тем, что столбцы коэффициентов при базисных неизвестных образуют единичную матрицу. Так как старая базисная переменная х₃ заменяется новой базисной переменной х₁, то в первом уравнении коэффициент перед х₁ должен быть равен 1. Это достигается делением первого уравнения на a₁₁. Далее следует исключить неизвестную х₁ из второго и третьего уравнений. Для этого преобразованное первое уравнение умножим сначала на а₂₁ и вычтем из второго, затем на а₃₁ и вычтем из третьего. В результате этих преобразований система (2) примет вид:

(11)

Здесь через a¹_ij обозначены новые значения коэффициентов. Заметим, что подобные преобразования выполняются в методе Гаусса при решении систем линейных уравнений.

Описание выше действия по работе с системой ограничений (2) следует повторить для системы (11) и т.д., до тех пор, пока не будет выполнены условия оптимальности.

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

ГЛАВА 2. Описание объекта и логическая формулировка проблемы

Хлебобулочный завод производит 20 различных видов хлебобулочных изделий. Стоимость и возможные запасы основных ингредиентов представлены в таблице 1.

Таблица 1 - Исходные данные

Завод установил контракты с различными магазинами на продажу хлебобулочных изделий. Контрактом установлены минимальное количество изделий на поставку каждого вида в день. В таблице 2 отражен спрос в день для каждого вида выпечки, цена по каждому виду (стоимость указана без учета начинки для некоторых изделий).

Таблица 2 - Спрос в день по каждому виду выпечки, цена каждого вида

В таблице 3 отражены количество ингредиентов для создания одной единицы продукции.

Таблица 3 - Рецептура хлебобулочных изделий

Исходя из данных, представленных в таблице 2 и таблице 3, определим себестоимость ассортимента, чтобы вычислить чистую прибыль от продажи.

Таблица 4 - Вспомогательная таблица

2.1 Составление математической модели

Обозначения:

i - индекс изделия

j - индекс ингредиента

x_i - объем i-го изделия

y_j - объем j-го ингредиента

p_i - цена i-го изделия