Примеры задач линейного программирования

Пример 1.1. Предприятие химической промышленности выпускает соляную и серную кислоту. Выпуск одной тонны соляной кислоты приносит предприятию прибыль в размере 25 ден.ед., выпуск одной тонны серной кислоты – 40 ден.ед. Для выполнения государственного заказа необходимо выпустить не менее 200 т соляной кислоты и не менее 100 т серной кислоты. Кроме того, необходимо учитывать, что выпуск кислот связан с образованием опасных отходов. При выпуске одной тонны соляной кислоты образуется 0, 5 т опасных отходов, при выпуске одной тонны серной кислоты – 1, 2 т опасных отходов. Общее количество опасных отходов не должно превышать 600 т, так как превышение этого ограничения приведет к выплате предприятием крупного штрафа.

Требуется определить, сколько соляной и серной кислоты должно выпустить предприятие, чтобы получить максимальную прибыль.

Составим математическую модель задачи. Для этого введем переменные. Обозначим через X₁ количество выпускаемой соляной кислоты (в тоннах), через X2 – количество серной кислоты.

Составим ограничения, связанные с необходимостью выполнения государственного заказа. Предприятию необходимо выпустить не менее 200 т соляной кислоты. Это ограничение можно записать следующим образом: X₁ ≥ 200. Аналогично составим ограничение, устанавливающее, что предприятие должно выпустить не менее 100 т серной кислоты: X₂ ≥ 100.

Составим ограничение на опасные отходы. При выпуске одной тонны соляной кислоты образуется 0, 5 т опасных отходов; значит, общее количество опасных отходов при выпуске соляной кислоты составит 0, 5·X₁ т. При выпуске серной кислоты образуется 1, 2·X₂ т опасных отходов. Таким образом, общее количество опасных отходов составит 0, 5·X₁ + 1, 2·X₂ т. Эта величина не должна превышать 600 т. Поэтому можно записать следующее ограничение:

0, 5·X₁ + 1, 2·X₂ ≤ 600.

Кроме того, переменные X₁ и X₂ по своему физическому смыслу не могут принимать отрицательных значений, так как они обозначают количество выпускаемых кислот. Поэтому необходимо указать ограничения неотрицательности): X₁ ≥ 0, X₂ ≥ 0.

В данной задаче требуется определить выпуск кислот, при котором прибыль будет максимальной. Прибыль от выпуска одной тонны соляной кислоты составляет 25 ден.ед.; значит, прибыль от выпуска соляной кислоты составит 25·X₁ ден.ед. Прибыль от выпуска серной кислоты составит 40·X₂ ден.ед. Таким образом, общая прибыль от выпуска кислот составит 25·X₁+40·X₂ ден.ед. Требуется найти такие значения переменных X₁ и X₂, при которых эта величина будет максимальной. Таким образом, целевая функция для данной задачи будет иметь следующий вид:

E = 25·X₁+40·X₂ → max.

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

X₁ ≥ 200

X₂ ≥ 100 (1.3)

0, 5·X₁ + 1, 2·X₂ ≤ 600

X₁ ≥ 0, X₂ ≥ 0.

E = 25·X₁+40·X₂ → max. (1.4)

В этой задаче имеется два ограничения “больше или равно” и одно ограничение “меньше или равно”. Целевая функция подлежит максимизации.

Пример 1.2. Пусть в условиях примера 1.1 из-за ужесточения требований к экологической безопасности требуется свести к минимуму количество опасных отходов. В то же время необходимо учитывать, что для того, чтобы производство кислот было экономически целесообразным, необходимо получить прибыль не менее 20 тыс. ден.ед.

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

X₁ ≥ 200

X₂ ≥ 100 (1.5)

25·X₁+40·X₂ ≥ 20000

X₁ ≥ 0, X₂ ≥ 0.

E = 0, 5·X₁ + 1, 2·X₂ → min. (1.6)

Третье ограничение в этой модели устанавливает, что прибыль от выпуска кислот должна составлять не менее 20 тыс. ден.ед. Целевая функция (1.6) представляет собой количество опасных отходов; эта величина подлежит минимизации.