30. Примеры экономико-математических моделей, приводящих к задачам линейного программирования. Основная задача линейного программирования.

Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных и называется математическим программированием. В классическом математическом анализе рассматривается задача отыскания условного экстремума функции. Стандартной задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции при выполнении условий. Математическая модель ОЗЛП: целевая функция; система ограничений; условия не отрицательности. Примеры задач: Задача определения оптимального ассортимента выпуска; задача о диете; транспортная задача.

31. Геометрическая интеграция задачи линейного программирования для двух переменных. Графический метод решения. Решение задачи линейного программирования методом перебора вершин.

В графическом методе: система ограничений; условия не отрицательности; целевая функция. Найти оптимальный план означает на плоскости найти такую точку в которой удовлетворяются ограничения, а значение целевой функции достигает экстремума. Метод перебора вершин: прямые заданы уравнениями которые получили из системы ограничений заменив знаки неравенств на знаки равенств; отметить часть плоскости определяемую каждым уравнением; если система ограничений совместна, то получим часть плоскости многоугольник решений Q, в котором условия системы ограничений; Вектор P= – нормальный вектор целевой функции показывает направление максимального изменения целевой функции; При движении прямой Z перпендикулярной P по направлению P последняя точка на выходе из многоугольника решений соответствует максимальному значению целевой функции; при движении прямой Z в противоположном P направлении последняя точка на выходе из многоугольника решений соответствует Zmin.

32. Симплекс метод. Решение задач линейного программирования. Нахождение опорного плана, нахождение оптимального плана. Понятие о взаимно-двойственных задач.

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

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

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

Привести исходную задачу ЛП к стандартной форме.

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

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

Для новых переменных написать условия не отрицательности.