§2. Графический способ решения злп

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

Пусть дана задача

(7)

(8)

(9)

Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (8), (9) задает на плоскости некоторую полуплоскость. Полу­плоскость – выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множест­вом. Отсюда следует, что область допустимых решений задачи (7) - (9) есть выпуклое множество.

Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП – не­пустое множество, например многоугольник .

Выберем произвольное значение целевой функ­ции . Получим . Это уравнение пря­мой линии. В точках прямой NМ целевая функция сохра­няет одно и то же постоянное значение . Считая в ра­венстве (7) параметром, получим уравнение семей­ства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).

Найдём частные производные целевой функции по и

(10)

(11)

Частная производная (10) ((11)) функции пока­зывает скорость ее возрастания вдоль данной оси. Следо­вательно, и — скорости возрастания соответст­венно вдоль осей и . Вектор называ­ется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:

Вектор (- ) указывает направление наискорейшего убывания целевой функции. Его называют антигра­диентом.

Вектор перпендикулярен к прямым семейства

Из геометрической интерпретации элементов ЗЛП вы­текает следующий порядок ее графического решения.

1. С учетом системы ограничений строим область до­пустимых решений .

2. Строим вектор наискорейшего возра­стания целевой функции — вектор градиентного направ­ления.

3. Проводим произвольную линию уровня

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

5. Определяем оптимальный план и экстре­мальное значение целевой функции .

§3. Симплексный метод

Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит:

1. умение находить начальный опорный план;

2. наличие признака оптимальности опорного пла­на;

3. умение переходить к нехудшему опорному плану.

Симплексный метод может быть реализован и «вручную», однако лучше воспользоваться компьютерными возможностями, например, возможностями Excel.