6. Линейные модели оптимизации.

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

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

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

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

Линейное программирование является одной из основных частей того раздела современной математики, который получил название математического программирования.

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

Геометрическая интерпретация задач линейного программирования. Решение задач линейного программирования в стандартной форме при n=2 геометрическим способом. Геометрическая интерпретация задач линейного программирования в канонической форме при n - m=2 и её геометрическое решение.

Наиболее наглядна эта интерпретация для случая n =2, т.е. для случая двух переменных   и  .

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

1. На координатной плоскости строится область допустимых решений;

2. Строится вектор градиент линейной целевой функции; «˅»

3. Строится линия уровня. Для этого целевая функция приравнивается постоянной величине a.

4. Линия уровня передвигается в направлении вектора «˅» при максимизации, а в случае минимизации в противоположном направлении, до тех пор пока не покинет область допустимых решений.

28. Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан американским математиком Джорджем Данцигом в 1947 году.

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

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

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

• нахождение исходной вершины множества допустимых решений;

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

При этом в некоторых случаях исходное решение очевидно или его определение не требует сложных вычислений.

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

29. Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования является симплекс-метод.

Анализ оптимального решения начинается после успешного решения задачи, когда на экране появляется диалоговое окно «Результаты поиска решения». С его помощью можно подготовить три типа отчетов:

• по результатам (опция Результаты);

• по устойчивости (опция Устойчивость);

• по пределам (опция Пределы).

1. Подготовим отчет по результатам.

Отчет состоит из трех таблиц.

В первой таблице (Целевая ячейка) приводятся сведения о целевой функции: исходное значение (в графе «Исходно») и оптимальный результат (в графе «Результат»).

Во второй таблице (Изменяемые ячейки) приводятся исходные (в графе «Исходно») и полученные в результате решения задачи (в графе «Результат») значения переменных x1, x2, x3, x4, x5.

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

2. Отчет по устойчивости содержит две таблицы.

В первой таблице (Изменяемые ячейки) приводятся следующие значения переменных:

· результаты решения задачи (графа «Результ. значение»);

· нормированная стоимость, т.е. дополнительные двойственные переменные vj, , которые показывают, насколько изменяется целевая функция при принудительном включении единицы этой продукции в оптимальное решение;

· коэффициенты целевой функции (графа «Целевой коэффициент»);

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

Во второй таблице приводятся значения ограничений:

· значения используемых (графа «Результ. Значение») и заданных (графа «Ограничение, правая часть») ресурсов;

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

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

3. Отчёт по переделам показывает, в каких пределах может меняться выпуск продукции, вошедшей в оптимальное решение, при сохранении его структуры:

· приводятся значения хi в оптимальном решении (графа «Значение»);

· даются нижние и верхние пределы изменения хi и соответствующие значения целевой функции (в графах «Целевой результат»).

30. Работа по решению некоторой оптимизационной задачи всегда начинается с построения математической модели. При конструировании модели формулировка ограничений является самой ответственной частью конструкции. В некоторых случаях ограничения очевидны, например, ограничение на количество сырья. Другие же ограничения могут быть менее очевидны и могут быть указаны неверно. Таким образом, на данном этапе делаются выводы об исходных данных, искомых переменных, о (линейные пределах, в которых могут находиться значения искомых величин, о зависимостях между переменными, о критериях, по которым необходимо находить оптимальное решение. Сюда же входит преодоление несовместимости, а также неограниченности целевой функции: при максимизации целевой функции область допустимых решений должна быть ограничена сверху, при минимизации - ограничена снизу.

В случае неограниченной области целевая функция может быт задана таким образом, что соответствующая ей прямая не имеет точки «выхода» (или «входа»). Тогда максимальное значение функции (минимальное) не достигается никогда – говорят, что функция не ограничена. Графический метод применяется для решения задач, которые имели в системе ограничений только две переменные. Этот метод может применяться и для систем неравенств, имеющих три переменных. Геометрически ситуация будет иная, роль прямых будут играть плоскости в трехмерном пространстве, а решением неравенства от трех переменных будет являться полупространство, находящееся по одну сторону от плоскости. Роль областей будут играть многогранники, являющиеся пересечением полупространств.