Балашовский филиал

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

Прежде чем приступать к формулировке задачи линейного программирования (сокращенно ЗЛП), рассмотрим три часто встречающиеся экономические ситуации.
С и т у а ц и я 1. Фирма имеет одно предприятие, которое выпускает n видов продукции, затрачивая m видов ресурсов. Каждый вид продукции j характеризуется технологией A_j = (a_1j,…, a_mj, c_j) в виде набора {a_ij}, где a_ij — количество единиц ресурса i, затрачиваемого на единицу продукта j, и c_j — прибыль, получаемая фирмой с каждой единицы продукта j. Известны также объемы ресурсов B = (b₁,…, b_m), которыми располагает предприятие. Руководство фирмы заинтересовано в получении оптимального варианта своего бизнеса по прибыли. Для этого предприятию нужно, грамотно распорядившись имеющимися ресурсами, выпустить такую комбинацию всех видов продукции, при которой прибыль оказалась бы наибольшей.
Составим математическую модель данной экономической ситуации. Обозначим через X = (x₁,…, x_n)^T вектор производства, где x_j — объем выпуска продукции j. Вектор X часто называют еще планом производства. При этом координаты вектора X должны быть неотрицательны:
x_j 0, j =1, 2,…, n,
(иногда выпуск продукции j может быть ограничен d_j, в этом случае имеет место двойное неравенство 0 x_j d_j). Ограниченность ресурсов и линейная зависимость между расходами ресурсов и производством продукции приводит к системе линейных неравенств
b_i, i =1, 2, …, m.
Прибыль от реализации произведенного продукта равна
L(X) = c₁x₁ + c₂x₂ + ... + c_jx_j + ... + c_nx_n.
План производства X = (x₁,…, x_n)^T называется оптимальным по прибыли, если L(X) достигает наибольшего возможного значения при вышеописанных ограничениях. Поэтому, руководствуясь интересами фирмы, предприятие в качестве критерия экономической эффективности должно принять максимум прибыли:
L(X) = c₁x₁ + c₂x₂ + ... + c_jx_j + ... + c_nx_n  max.
При этом следует найти не только само значение max L(X), но (что
не менее важно!) точки, в которых оно достигается, то есть получить оптимальный вектор производства X = (x₁,…, x_n)^T.
Замечание 1. Возможно, что фирма решит использовать другую технологическую характеристику каждого вида продукции. Например, в описанной выше технологии A_j, не меняя экономической интерпретации a_1j,…, a_mj, изменит экономическую интерпретацию последней константы: под c_j будет понимать себестоимость каждой единицы продукта j. Это означает, что руководство фирмы заинтересовано в получении оптимального варианта своего бизнеса по себестоимости. Поэтому в качестве критерия экономической эффективности предприятие должно будет принять минимум себестоимости: