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

Графический метод решения ЗЛП.

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

Найти минимальное решение функции Найти минимальное решение функции

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

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

Значения в направлении , поэтому прямую передвигаем параллельно самой себе в направлении N Значения в направлении , поэтому прямую передвигаем параллельно самой себе в направлении N

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

Симплексный метод решения ЗЛП.

Из свойств решений задачи ЛП следует, что существует такая угловая точка (вершина) многогранника решений, в которой целевая функция достигает своего наибольшего (наименьшего) значения. Из свойств решений задачи ЛП следует, что существует такая угловая точка (вершина) многогранника решений, в которой целевая функция достигает своего наибольшего (наименьшего) значения.

Каждой угловой точке многогранника решений соответствует опорный план, а каждый опорный план определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов . Каждой угловой точке многогранника решений соответствует опорный план, а каждый опорный план определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов .

Для отыскания оптимального плана необходимо исследовать только опорные планы. Количество опорных планов, содержащихся в данной задаче, определим через . Для отыскания оптимального плана необходимо исследовать только опорные планы. Количество опорных планов, содержащихся в данной задаче, определим через .

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

2. Если для некоторы , но при этом все , тогда целевая функция неограниченна на множестве ее планов. 2. Если для некоторы , но при этом все , тогда целевая функция неограниченна на множестве ее планов.

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

Неединственность оптимума. Неединственность оптимума. Если в оптимальной таблице небазисный вектор имеет нулевую оценку, то ЗЛП будет иметь неединственное решение. Можно перейти к другой оптимальной таблице с другим решением, но значение целевой функции будет оставаться прежним. График целевой функции параллелен той прямой, на которой лежит точка min или max.

Неограниченность оптимума. Неограниченность оптимума. Говорят, что задача ЛП имеет неограниченный оптимум, если у нее нет конечного оптимального решения. А планом случая (для задачи максимизации), (для задачи минимизации).

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

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

Вопросы: Вопросы: 1)При каких условиях задача ЛП, решая графическим методом, имеет решение? 2)Симплекс метод – это аналитический метод решения задачи ЛП или нет?