22. Теоремы двойственности. Вторая теорема двойственности.

Для того чтобы план Х^* и Y^* пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:

Эти условия называются условиями дополняющей нежесткости. Из них следует, что если какое-либо неравенство системы ограничений в одной из задач не обращается в строгое равенство оптимальным планом этой задачи, то соответствующий элемент оптимального плана двойственной задачи должен равняться нулю. Если какой-либо элемент оптимального плана одной из задач положителен, то соответствующее ограничение в двойственной задаче её оптимальным планом должно обращаться в строгое равенство, т.е.

если  b_j, то ;

если  0, то .

Аналогично,

если 

если 0 то

Экономически это означает, что если по некоторому оптимальному плану X^*= производства расход j-го ресурса меньше его запаса b_j, то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его j-й элемент больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс, т.е. полностью используемый по оптимальному плану производства, имеет положительную оценку, а избыточный ресурс, т.е. не используемый полностью имеет нулевую оценку.

23. Теоремы двойственности. Третья теорема двойственности.

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

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

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

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

24. Геометрический метод решения задач линейного программирования. Алгоритм решения.

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

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

Для нахождения экстремального значения целевой функции при графическом решении задач ЛП используют вектор gradZ на плоскости Х₂ОХ₂ .

Этот вектор показывает направление наискорейшего изменения целевой функции. Координатами вектора grandZ являются коэффициенты целевой функции Z(x).

Алгоритм геометрического метода решения задач ЛП.

Решение задач ЛП геометрическим методом осуществляется по следующему алгоритму:

1.Строим координатные оси Х₁ОХ₂ и с учетом коэффициентов математической модели выбираем масштаб.

2.Находим область допустимых решений (ОДР) системы ограничений математической модели.

3.Строим прямую целевой функции и показываем направление наискорейшего ее изменения (нормаль-gradL).

4.Линию целевой функции (линия уровня) перемещаем по направлению нормали для задач на максимум целевой функции и в противоположном направлении - для задач на минимум ЦФ.

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

Если окажется, что линия уровня совпадает с одной из сторон ОДР , то задача ЛП будет иметь бесчисленное множество решений.

Если ОДР представляет неограниченную область, то целевая функция – неограниченна.

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

5.Находим координаты точки экстремума и значение ЦФ в ней.