Математическое описание

Предположим, что:

X1 — время, потраченное на радиорекламу.

Х2 — время, потраченное на телерекламу.

Z — искомая целевая функция, отражающая максимальный сбыт от2-х видов рекламы.

Х1≥0, Х2≥0, Z≥0;

Max Z = X1+25X2;

5X1 + 100X2 ≤1000;

Х1-2Х2≥0.

Использование графического способа удобно только при решении задач ЛП с двумя переменными. При большем числе переменных необходимо применение алгебраического аппарата. В данной главе рассматривается общий метод решения задач ЛП, называемый симплекс-методом.

Информация, которую можно получить с помощью симплекс-метода, не ограничивается лишь оптимальными значениями переменных. Симплекс-метод фактически позволяет дать экономическую интерпретацию полученного решения и провести анализ модели на чувствительность.

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

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

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

- все ограничения записываются в виде равенств с неотрицательной правой частью;

- значения всех переменных моделей неотрицательны;

-целевая функция подлежит максимизации или минимизации. Покажем, каким образом любую линейную модель можно привести к стандартной.

Ограничения

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

Например, в левую часть исходного ограничения

5X1 + 100X2 ≤ 1000

вводится остаточная переменная S1 > 0, в результате чего исходное неравенство обращается в равенство

5X1 + 100X2 + S1 = 1000, S1 ≥ 0.

Если исходное ограничение определяет расход некоторого ресурса, переменную S1 следует интерпретировать как остаток, или неиспользованную часть данного ресурса.

Рассмотрим исходное ограничение другого типа:

XI - 2Х2≥0.

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

XI -2X2-S2 = 0,S2≥0.

2. Правую часть равенства всегда можно сделать неотрицательной, умножая обе части на -1.

Например, равенство XI - 2X2 - S2 = 0 эквивалентно равенству – X1 + 2X2+ S2=O.

3. Знак неравенства изменяется на противоположный при умножении обеих частей на -1.

Например, можно вместо 2 < 4 записать - 2 > - 4, неравенство XI - 2X2 ≤ 0 заменить на – X1 + 2X2 ≥ 0.