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

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

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

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

Например поиск оптимальных плановых решений можно свести к получению запланированного эффекта при минимуме затрат или получение максимального эффекта при использовании заданных ограниченных ресурсах.

Линейное программирование [linear programming] — область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными.

В самом общем виде задачу Л. п. можно записать так. Даны ограничения типа

или в т. н. канонической форме, к которой можно привести все три указанных случая:

Требуется найти неотрицательные числа x_j (j = 1, 2, ..., n), которые минимизируют (или максимизируют) линейную форму

Неотрицательность искомых чисел записывается так: x_j ≥ 0.

Таким образом, представлена общая задача математического программирования с оговорками: как ограничения, так и целевая функция линейные, а искомые переменные неотрицательные.

Обозначения можно трактовать следующим образом:

b_i — количество ресурса вида i ;

m — количество видов этих ресурсов;

a_ij — норма расхода ресурса вида i на единицу продукции вида j;

x_j — количество продукции вида j, причем количество таких видов — n;

c_j — доход (или другой выигрыш) от единицы этой продукции, а в случае задачи на минимум — затраты на единицу продукции;

нумерация ресурсов разделена на три части:

от 1 до m₁, в первом случае — “не больше”

от m₁ + 1 до m₂ во втором — “столько же”

от m₂ + 1 до m

в зависимости от того, какие ставятся ограничения на расходование этих ресурсов;, , в третьем — “не меньше”;

Z — в случае максимизации, напр., объем продукции или дохода, в случае же минимизации — себестоимость, расход сырья и т. п.

Добавим еще одно обозначение, оно появится несколько ниже:

v_i — оптимальная оценка i-го ресурса.

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

Следует с самого начала предупредить: предпосылка линейности, когда в реальной экономике подавляющее большинство зависимостей носит более сложный нелинейный характер, есть огрубление, упрощение действительности. В некоторых случаях оно достаточно реалистично, в других же выводы, получаемые с помощью решения задач Л. п., оказываются весьма несовершенными.

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

Дано:

· ресурсы: персонал, техника и оборудование, сырье и материалы, финансы, информация, время, технология изготовления, земля и другие ресурсы.

(А и В - обозначим численные значения ресурсов 2-х видов соответственно);

· выпускается продукция разных видов, с одинаковыми единицами измерения, выраженных в руб. или в штуках.

(Х₁ и Х₂ - обозначим численные значения выпускаемой продукции 2-х);

· имеются нормы затрат ресурса на выпуск единицы продукции;

(а1 и а2 - численные значения норм затрат ресурса А на выпуск изделий 1-го и 2-го видов соответственно,

в1 и в2 - численные значения норм затрат ресурса В на выпуск изделий 1-го и 2-го видов соответственно)

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

(с1 и с2 - нормы прибыли, равные прибыли, получаемой от реализации единицы соответствующей продукции Х1 и Х2)

· имеется целевая функция, отражающая прибыль предприятия от продажи, выпускаемой продукции;

(Ф = с1Х1 + с2Х2 - прибыль )

Необходимо: определить такие значения выпускаемой продукции Х₁ и Х₂, при которых используемые ресурсы не превысили значений А и В, а целевая функция получила максимальное значение

Приведем постановку задачи в математическом (формализованном виде):

Целевая функция:

Ограничения:

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