Задачи линейного программирования (оптимизация)

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

Пример

Найти максимальное значение функции

при следующих ограничениях на переменные и

Линейная функция называется функцией цели или целевой функцией.

Ограничения могут быть как не жесткие, т.е. в виде строгих или нестрогих неравенств, а могут быть жесткими – в виде равенств.

ЗЛП являются прекрасными математическими моделями для большого числа экономических (и не только) задач, например: планирование производства, расход ресурсов, транспортные перевозки и др.

Рассмотрим процесс построения математической модели ЗЛП на примерах некоторых экономических задач.

Построение математических моделей для экономических задач

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

Задача планирования производства продукции (на максимизацию)

Рассмотрим следующую задачу.

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

Изучение рынка сбыта показало, что спрос на краску для внутренних работ никогда не превышает 4т. в сутки. Цена продажи 1т. краски для наружных работ – 3 ден.ед., для внутренних работ – 2 ден.ед. Определить какое количество краски каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным.

Итак, цель задачи – получение максимальной прибыли.

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

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

.

Перейдем к формулировке ограничений. Ограничения будут двух сортов. Первый – это не превышение расхода исходных продуктов для изготовления краски их суточных запасов. Второй – это не превышение продажи краски для внутренних работ ее суточного спроса.

Получаем следующую систему ограничений:

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

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

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

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