Содержание
-
Кафедра математики и моделирования Старший преподаватель Е.Г. Гусев Курс «Высшая математика» Лекция 17. Тема: Графический метод и симплекс-метод задачи линейного программирования. Цель: Научиться решать графическим и симплекс-методами задачу ЛП.
-
Графический метод решения ЗЛП.
-
Графический метод основан на геометрической интерпретации задачи линейного программирования. Найти минимальное решение функции
-
Найти минимальное решение функции
-
Предположим, что эта система совместна (имеет хотя бы одно решение) и ее многоугольник решений ограничен. Линейная функция Z при фиксированных значениях является уравнением прямой .
-
Построим многоугольник решений системы ограничений и график линейной функции . Тогда задачу линейного программирования можно сформулировать так: найти точку многоугольника решений, в которой прямая опорная и функция Z при этом достигает минимума.
-
Значения в направлении , поэтому прямую передвигаем параллельно самой себе в направлении N
-
Неединственность оптимального решения. Для некоторых задач линейного программирования может существовать несколько допустимых решений со значением целевой функции равной оптимальному значению задачи. В таких случаях все эти допустимые решения оптимальны и говорят, что задача линейного программирования имеет альтернативные оптимальные решения.
-
Симплексный метод решения ЗЛП.
-
Из свойств решений задачи ЛП следует, что существует такая угловая точка (вершина) многогранника решений, в которой целевая функция достигает своего наибольшего (наименьшего) значения.
-
Каждой угловой точке многогранника решений соответствует опорный план, а каждый опорный план определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов .
-
Для отыскания оптимального плана необходимо исследовать только опорные планы. Количество опорных планов, содержащихся в данной задаче, определим через .
-
Признак оптимальности опорного плана. После заполнения таблиц может иметь место один из случаев: 1. Все для любы , то работает признак оптимальности, и исходный опорный план является оптимальным.
-
2. Если для некоторы , но при этом все , тогда целевая функция неограниченна на множестве ее планов.
-
3. Если для некоторых j, и при этом , то можно перейти от исходного плана к новому опорному, при котором значение целевой функции будет больше, чем предыдущее. Этот переход осуществляется исключением из исходного базиса какого-нибудь вектора и введением в базис нового.
-
Неединственность оптимума. Если в оптимальной таблице небазисный вектор имеет нулевую оценку, то ЗЛП будет иметь неединственное решение. Можно перейти к другой оптимальной таблице с другим решением, но значение целевой функции будет оставаться прежним. График целевой функции параллелен той прямой, на которой лежит точка min или max.
-
Неограниченность оптимума. Говорят, что задача ЛП имеет неограниченный оптимум, если у нее нет конечного оптимального решения. А планом случая (для задачи максимизации), (для задачи минимизации).
-
Вырожденность и зацикливание При рассмотрении симплекс-метода предполагаем, что все . Если какое-то , то такой план задачи в качестве базисной переменной содержит нулевое значения, т.к. план называется вырожденным.
-
Правило для устранения зацикливания Если на каком-либо этапе расчета возникает неопределенность в выборе разрешающей строчки, т.е. 2 и более min одинаковых отношения, то следует выбрать ту строку, для которой отношение элементов следующего столбца к разрешающему является наименьшим. Если снова оказываются равными минимальные отношения, то выбирают следующий столбец и так до тех пор, пока разрешающая строка не определится однозначно.
-
Вопросы: 1)При каких условиях задача ЛП, решая графическим методом, имеет решение? 2)Симплекс метод – это аналитический метод решения задачи ЛП или нет?
Нет комментариев для данной презентации
Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.